Universidade Federal de Uberlândia
Bacharelado em Ciência da Computação
1a Prova de Lógica para Ciência da Computação - 10/10/2003
NOME :
NÚMERO :
VALOR DA PROVA : 100 PONTOS
NOTA =
Resolver as questões logo após o enunciado das mesmas, se preciso utilizando
o verso da página.
Questão 1 (Valor = 20 pontos) : Considere a seguinte fórmula da lógica de predicados:
Em cada um dos itens abaixo, diga se as duas fórmulas F e G são equivalentes e
justifique sua resposta : se for “sim”, prove; se for “não” dê um contraexemplo.
1. (Valor = 10 pontos) F = ∀x∀yP (x, y); G = ¬∃x∃y¬P (y, x)
Solução
Verdadeiro. As duas fórmulas são equivalentes. Para provar isto, vamos mostrar
que para toda interpretação I, tem-se que I(F) = I(G).
Seja I uma interpretação qualquer.
Vamos “traduzir em portugues” o que significa I(F) = T :
I(F) = T ⇔ para todo valor d para x e para todo valor c para y tem-se que
< x ← d >< y ← c > I (P (x, y)) = T
⇔ para todo valor d valor e todo valor c para y tem-se que (d,c) satisfaz I(P )
⇔ para todos valores d e c tem-se que (d,c) satisfaz I(P )
Vamos “traduzir em portugues” o que significa I(G) = T :
I(G) = T ⇔ não existe valor c para x e valor d para y tais que < x ← c >< y ← d >
I(¬P (x, y)) = T
⇔ não existe valor c para x e valor d para y tais que < x ← c >< y ← d >
I(P (y, x)) = F
⇔ não existem valores c e d tais que (d,c) não satisfaz I(P )
Comparemos agora as duas frases :
(a) ⇔ para todos valores d e c tem-se que (d,c) satisfaz I(P )
(b)
⇔ não existem valores c e d tais que (d,c) não satisfaz I(P )
Repare que estas frases dizem a mesma coisa. Logo I(F) = T se e somente se I(G)
= T. Portanto, as duas fórmulas são equivalentes.
Observação : Caso houvesse quantificadores distintos em F e G, por exemplo, se
F = ∀x∃yP (x, y) e G = ¬∃x∀y¬P (y, x), então as fórmulas F e G não seriam equivalentes, por causa da “troca” nas variáveis x, y dentro do predicado P . Explique
isto !
2. (Valor = 10 pontos) F = ∀x(P (x) ∨ Q(y)); G = (∀xP (x) ∨ Q(y))
Solução
Verdadeiro. As duas fórmulas são equivalentes. Para provar isto, vamos mostrar
que para toda interpretação I, tem-se que I(F) = I(G).
Seja I uma interpretação qualquer.
Vamos “traduzir em portugues” o que significa I(F) = T :
I(F) = T ⇔ para todo valor d para x tem-se que < x ← d > I(P (x) ∨ Q(y)) = T
⇔ para todo valor d para x tem-se que < x ← d > I(P (x)) ou < x ← d > I(Q(y))
⇔ para todo valor d tem-se que x satisfaz I(P ) ou I(y) satisfaz I(Q).
Vamos “traduzir em portugues” o que significa I(G) = T :
I(G) = T ⇔ I(∀xP (x)) = T ou I(Q(y))) = T
⇔ para todo valor d para x tem-se que < x ← d > I(P (x)) ou I(Q(y))) = T
⇔ para todo valor d tem-se que x satisfaz I(P ) ou I(Q(y))) = T
⇔ para todo valor d tem-se que x satisfaz I(P ) ou I(y) satisfaz I(Q).
Comparemos agora as duas frases :
1.
⇔ para todo valor d tem-se que x satisfaz I(P ) ou I(y) satisfaz I(Q).
2. ⇔ para todo valor d tem-se que x satisfaz I(P ) ou I(y) satisfaz I(Q).
Repare que estas frases dizem a mesma coisa. Logo I(F) = T se e somente se I(G) =
T. Portanto, as duas fórmulas são equivalentes.
Questão 2 (Valor = 30 pontos): Para cada um dos itens abaixo, dizer se a fórmula é
válida, uma contradição ou apenas satisfatı́vel mas não válida. Você tem que provar sua
afirmação. Não serão aceitas respostas sem justificativas.
1. (Valor = 15 pontos) ∀x¬P (x) → ¬∀xP (x)
Solução
A fórmula é válida. Para provar isto, vamos mostrar que para toda interpretação
I, tem-se que I(F) = T.
Podemos mostrar por absurdo. Suponha que exista uma interpretação I tal que
I(F) = Falso. Então
I(∀x¬P (x)) = T e I(¬∀xP (x)) = F.
Vamos traduzir em portugues o que significa I(∀x¬P (x)) = T :
I(∀x¬P (x)) = T ⇔ para todo valor d para x tem-se que < x ← d > I(¬P (x)) = T
⇔ para todo valor d para x tem-se que < x ← d > I(P (x)) = F
⇔ para todo valor d tem-se que d não satisfaz I(P ). , isto é, em outras palavras :
⇔ para nenhum valor d tem-se que d satisfaz I(P ).
Vamos agora traduzir em portugues a expressão I(¬∀xP (x)) = F.
I(¬∀xP (x)) = F ⇔ I(∀xP (x)) = T
⇔ para todo valor d para x tem-se que < x ← d > I(P (x)) = T
⇔ para todo valor d tem-se que d satisfaz I(P ).
Comparemos agora as duas frases :
(a) para nenhum valor d tem-se que d satisfaz I(P ).
(b) para todo valor d tem-se que d satisfaz I(P ).
Tais frases são contraditórias. Logo, temos o absurdo que querı́amos. Assim, não é
possı́vel que exista uma interpretação I tal que I(F) = Falso. Portanto, a fórmula
F é válida.
2. (Valor = 15 pontos) F = ∃xP (x) → ¬∀xP (x)
Solução
A fórmula F é satisfatı́vel, mas não é válida.
Para mostrar que F é satisfatı́vel, basta exibir uma interpretação I tal que I(F) =
T. Considere a seguinte interpretação I :
• Universo : alunos de LCC2
• I(P(x)) = T se e somente se I(x) gosta de lógica.
Suponha que exista alguém na sala de LCC2 que goste de lógica e alguém que deteste lógica. Então I(∃xP (x)) = T e I(¬∀xP (x)) = T. Portanto I(F) = T.
Para mostrar que F não é válida, basta exibir uma interpretação J tal que I(F) =
Falso. Considere a seguinte interpretação J :
• Universo : alunos de LCC2
• J(P(x)) = T se e somente se J(x) gosta de namorar.
Vamos imaginar que na turma de LCC2, todo mundo goste de namorar (o que é
mais ou menos óbvio). Então J(F) = Falso, pois segundo a interpretação J, temos
que J(∃xP (x)) = T mas J(¬∀xP (x)) = Falso.
Questão 3 (Valor = 35 pontos):
1. (Valor = 10 pontos) Considere o seguinte discurso:
(a) Todo aluno de Ciência da Computação é mais inteligente que algum aluno de
Engenharia.
(b) Todo aluno de Engenharia se deprime se é menos inteligente que algum aluno
de Ciência da Computação.
Conclusão 1: Existe um aluno de Engenharia que está deprimido.
Conclusão 2: Todo aluno de Engenharia está deprimido.
Transforme as frases (a) e (b) e a conclusão 1 e a conclusão 2 em fórmulas da Lógica
de Predicados.
(a) Existem duas maneiras :
(a1) F1 = ∀x(C(x) → ∃y(E(y) ∧ T (x, y)))
(a2) F10 = ∃zC(z) ∧ ∀x(C(x) → ∃y(E(y) ∧ T (x, y)))
Veja que aqui, estamos garantindo a existência de alunos do curso de ciência da
computação.
(b) F2 = ∀x((E(x) ∧ ∃y(C(y) ∧ T (y, x)) → D(x))
Conclusão 1 : C1 = ∃x(E(x) ∧ D(x))
Conclusão 2 : C2 = ∀x(E(x) → D(x))
2. (Valor = 15 pontos) Diga se o raciocı́nio que permite inferir a conclusão 1 a partir
das premissas (a) e (b) é correto, verificando (provando !!) se a fórmula correspondente à conclusão 1 é consequência lógica do conjunto de fórmulas correspondentes
às premissas (a) e (b).
Solução
• Se a frase (a) for traduzida na lógica pela fórmula F1 , então o raciocı́nio é
incorreto. Considere a seguinte interpretação I :
(a)
(b)
(c)
(d)
(e)
Universo : números naturais
I(C(x)) = T se e somente se I(x) < 0
I(E(x)) = T se e somente se I(x) é primo e diferente de 2.
I(D(x)) = T se e somente se I(x) é par.
I(T (x, y)) = T se e somente se I(x) ≥ I(y)
I é modelo de F1 . De fato, para todo número natural d tem-se que
< x ← d > (C(x) → ∃y ∧ T (x, y))) = T, pois d não satisfaz o predicado I(C)
(d não é menor do que zero.)
I é modelo de F2 . De fato, para todo número natural d tem-se que
< x ← d > I((E(x) ∧ ∃y(C(y) ∧ T (y, x))) → D(x)) = T, pois d não pode ser
primo diferente de 2 e existir um número natural que seja negativo e que seja
superior ou igual a d.
Mas, I não é modelo de C1 : De fato, não existe um número primo diferente
de dois que seja par !
Logo, acabamos de mostrar que o raciocı́nio é incorreto, pois exibimos um
modelo das premissas que não é modelo da conclusão C1 .
• Se a frase (a) for traduzida na lógica pela fórmula F10 , então o raciocı́nio é
correto.
De fato, seja uma interpretação qualquer que é modelo de F10 e de F2 . Vamos
mostrar que I é modelo de C1 .
Pelo fato de I ser modelo de F10 , sabemos que I(F10 ) = T. Logo :
(1) existe um valor b para x tal que b satisfaz o predicado I(C) e
(2) para todo valor d para x, caso d satisfizer o predicado I(C) então existe c
tal que c satisfaz o predicado E e o par (b, c) satisfaz o predicado I(T ).
Pelo fato de I ser modelo de F2 , sabemos que I(F2 ) = T. Logo :
(3) para todo valor a para x, caso a satisfizer o predicado I(E) e existir a0 tal
que a0 satisfaz o predicado I(C) e o par (a0 , a) satisfaz o predicado I(T ) então
podemos garantir que a satisfaz o predicado I(D).
Vamos reunir todas as frases (1), (2) e (3) e vermos o que concluimos:
Da frase (1), podemos garantir que o valor particular b satisfaz o predicado
I(C). Logo, disto e da frase (2), podemos concluir que existe c tal que c satisfaz I(E) e (b, c) satisfaz I(T ). Disto e da frase (3), podemos concluir que c
satisfaz o predicado I(D).
Logo : c satisfaz I(E) e c satisfaz I(D). Portanto, I(C1 ) = T, isto é, I é modelo
de C1 .
3. (Valor = 10 pontos) Diga se o raciocı́nio que permite inferir a conclusão 2 das
premissas (a) e (b) é correto, verificando (provando !!) se a fórmula correspondente
à conclusão 1 é consequência lógica do conjunto de fórmulas correspondentes às premissas (a) e (b).
O raciocı́nio está incorreto, não importa a maneira como traduzimos na lógica a
frase (a), tanto utilizando a fórmula F1 quanto a fórmula F2 .
• Vamos mostrar que o raciocı́nio está incorreto, supondo a tradução da frase
(a) pela fórmula F1 .
Para isto, vamos exibir um modelo I tal que I(F1 ) = T e I(F2 ) = T mas I(C2 )
= Falso. Para isto considere a mesma interpretação que demos no item (2)
anterior. Vimos que I é modelo de F1 , é modelo de F2 . É claro que I não é
modelo de C2 , pois para todo número natural, se ele for primo e diferente de
dois então ele é IMPAR (e não par).
• Vamos mostrar que o raciocı́nio está incorreto, supondo a tradução da frase
(a) pela fórmula F10 .
De fato, consideremos a seguinte interpretação J:
–
–
–
–
Universo : números naturais
I(C(x)) = T se e somente se I(x) é múltiplo de quatro
I(E(x)) = T se e somente se I(x) é primo.
I(D(x)) = T se e somente se I(x) é impar.
– I(T(x,y)) = T se e somente se I(x) ≥ I(y)
I é modelo de F10 : existe um número natural que é múltiplo de 4, por exemplo o número 4 e qualquer número que for múltiplo de 4, existe um número
primo que é menor ou igual a ele (por exemplo, o número 2).
I é modelo de F2 : para todo número natural, se ele for primo e existir um
múltiplo de 4 que é maior ou igual a ele então necessariamente este número
primo deve ser impar (isto é, não pode ser o primo 2).
I não é modelo de C2 : obviamente, não é verdade que se um número natural
for primo ele é impar (pode ser o número 2 !!).
Questão 4 (Valor = 15 pontos): Prove por indução na estrutura das fórmulas, que
o número de parênteses de uma fórmula qualquer da Lógica de Predicados é par. Vamos
denotar por NPar(F) o número de parênteses da fórmula F.
Solução
Base da indução
• se F é uma fórmula atômica do tipo R(x1 , ..., xn ). Então NPar(F) = 2, que é um
número par.
• se F é uma fórmula atômica do tipo t1 = t2 então NPar(F) = 0, que é um número
par.
• se F é uma fórmula atômica do tipo true ou false então NPar(F) = 0, que é um
número par.
Hipótese de Indução : suponhamos que já tenhamos provado que o número de parênteses
das fórmulas F e G é par. Mostremos que o número de parênteses da fórmula H é par,
nos seguintes casos :
• H = (F ∨ G). Neste caso, NPar(H) = NPar(F) + NPar(G) + 2 = par + par + par
= par.
• Analogamente, mostramos que NPar(H) é par nos casos em que H = (F ∧ G),
H = (F → G), H = (F → G).
• H = ¬F . Neste caso, NPar(H) = NPar(F) que é par, por hipótese de indução.
• H = ∃xF . Neste caso, NPar(H) = NPar(F) que é par, por hipótese de indução.
• H = ∀xF . Neste caso, NPar(H) = NPar(F) que é par, por hipótese de indução.