FEUP / LEIC
TEORIA DA COMPUTAÇÃO II
EXERCÍCIOS DE LÓGICA PROPOSICIONAL
CONJUNÇÃO, DISJUNÇÃO E NEGAÇÃO
1 {3-6, 3-9} Negação, conjunção e disjunção. Abra um novo ficheiro de frases e o
mundo Wittgenstein’s World. Escreva as frases seguintes:
1. Tet(f) ∧ Small(f)
2. Tet(f) ∧ Large(f)
3. Tet(f) ∧ ¬Small(f)
4. Tet(f) ∧ ¬Large(f)
5. ¬Tet(f) ∧ ¬Small(f)
6. ¬Tet(f) ∧ ¬Large(f)
7. ¬(Tet(f) ∧ Small(f))
8. ¬(Tet(f) ∧ Large(f))
9. ¬(¬Tet(f) ∧ ¬Small(f))
10. ¬(¬Tet(f) ∧ ¬Large(f))
Qual o valor de verdade de cada uma delas? Verifique o resultado com Tarski’s World.
Sempre que haja desacordo, use o jogo para ver quem ganha. (Se houver sempre acordo,
jogue na mesma, para experimentar).
Mude o tamanho e forma do bloco f e preveja como isso afecta o valor das frases. Qual
o número máximo de frases que podem ficar verdadeiras num único mundo? Construa
um mundo no qual o máximo número de frases seja verdadeiro.
Repita o exercício trocando ∧ por ∨.
2 {3-11} Disjunção construtiva. Por vezes, é possível afirmar que uma frase é
verdadeira sem se saber como ganhar garantidamente o jogo respectivo. Por exemplo,
pode-se dizer que P ∨ ¬P é verdade mesmo sem se saber o valor de P. Abra Kleene’s
World e Kleene’s Sentences. Alguns objectos estão escondidos atrás de outros, pelo
que é impossível decidir a verdade de algumas frases. Todos os nomes a-f estão em
uso, referindo-se a algum objecto. Atribua um valor de verdade a cada frase atendendo
à informação, incompleta, de que dispõe (sem recorrer á vista 2D). Jogue o jogo. Se
tiver feito a atribuição certa, mas perder o jogo, desfaça alguns passos e retome até
conseguir ganhar. Finalmente verifique as atribuições com a vista 2D.
3 {3-13} Construir um mundo. Abra Schröder's Sentences. Construa um mundo em
que todas essas frases sejam verdadeiras.
4 {3-16} Equivalências de DeMorgan. Abra DeMorgan’s Sentences. Construa um
mundo em que todas as frases ímpares sejam verdadeiras. Seja qual for a solução, todas
as frases pares serão também verdadeiras. Depois construa um mundo em que todas as
frases ímpares sejam falsas. As pares ficam falsas. Porquê?
CRISTINA RIBEIRO
BOOLE - 1
FEUP / LEIC
TEORIA DA COMPUTAÇÃO II
5 {3-21, 3.22} Tradução. Abra um novo ficheiro de frases para escrever as traduções das
seguintes frases em Português para FOL.
1. a é pequeno ou tanto c como d são grandes.
2. d e e estão ambos atrás de b.
3. d e e estão ambos atrás de b e são maiores do que ele.
4. Tanto d como c são cubos; além disso nenhum deles é pequeno.
5. Nem e nem a estão à direita de c e à esquerda de b.
6. e não é grande ou está atrás de a.
7. c nem está entre a e b nem à frente de qualquer um deles.
8. a e e são ambos tetraedros ou são-no ambos a e f.
9. Nem d nem c estão à frente de c ou b.
10. c está entre d e f ou é menor que ambos.
11. Não se verifica que b esteja na mesma linha que c.
12. b está na mesma coluna que e, que está na mesma linha que d, que por sua vez
está na mesma coluna que a.
Para a tradução ser correcta os valores de verdade das frases em língua natural e das
suas traduções têm que ser os mesmos em todos os mundos. Use Wittgenstein’s
World, onde todas as frases são verdadeiras, e Boole’s World, onde apenas as frases 6 e
11 são verdadeiras, para testar a tradução. Construa alguns mundos em que as frases
assumam valores diversos e verifique a correcção da tradução também nesses casos (não
prova, mas ajuda a convencer!). Faça-o, alterando os tamanhos dos objectos e rodando o
tabuleiro.
6 {4.2} Tautologias. Assuma que A, B e C são frases atómicas. Use o Boole para
construir tabelas de verdade para cada uma das frases seguintes. Usando as tabelas,
diga quais das frases são tautologias.
1. (A ∧ B) ∨ (¬A ∨ ¬B)
2. (A ∧ B) ∨ (A ∧ ¬B)
3. ¬(A ∧ B) ∨ C
4. (A ∨ B) ∨ ¬(A ∨ (B ∧ C)).
7 {4.3} Frases não independentes. Suponha agora que as frases A, B e C do problema
anterior não são logicamente independentes. Determine quais das frases 1-4 do
problema anterior são satisfazíveis ou logicamente verdadeiras, em cada uma das
seguintes situações:
1. A é necessariamente verdadeira (e.g. A é b=b).
2. A é necessariamente falsa (e.g. Smaller(a,a)).
3. C é uma consequência lógica de A e B, i.e., sempre que A e B são verdadeiros, C
também o é (e.g. A é Larger(a,b), B é Larger(b,c) e C é Larger(a,c)).
CRISTINA RIBEIRO
BOOLE - 2
FEUP / LEIC
TEORIA DA COMPUTAÇÃO II
8 {4.4, 4.5, 4.6, 4.7} Tabelas de verdade. Suponha que A, B, C e D são frases atómicas
independentes. Construa tabelas de verdade para cada uma das frases seguintes. Indique
quais são satisfazíveis e quais são tautologias.
1. ¬(B ∧ ¬(C ∨ B))
2. A ∨ ¬(B ∨ ¬(C ∧ A))
3. ¬[(¬A ∨ ¬( B ∧ C)) ∨ (A ∧ B)]
4. ¬[(¬A ∨ B) ∧ ¬(C ∧ D)]
9 {Sec 4.3} Consequência lógica. As tabelas de verdade, para além da determinação da
verdade lógica, também podem servir para verificar a consequência lógica. Para saber
se Q é uma consequência lógica de P, construa uma tabela de verdade com todas as
frases atómicas de P e Q e os próprios P e Q e verifique se, em todas as linhas não
espúrias, sempre que P é verdade Q também o é (se esta propriedade se mantiver
mesmo nas linhas espúrias, fala-se de consequência tautológica).
1. Cubo(b) é uma consequência tautológica de (Cubo(a) ∨ Cubo(b)) ∧ Tet(a)?
2. Cubo(b) é uma consequência lógica de (Cubo(a) ∨ Cubo(b)) ∧ Tet(a)?
3. Cubo(b) é uma consequência tautológica de (Cubo(a) ∨ Cubo(b)) ∧ ¬Cubo(a)?
4. Cubo(b) é uma consequência lógica de (Cubo(a) ∨ Cubo(b)) ∧ ¬Cubo(a)?
5. Dodec(c) é uma consequência tautológica de Dodec(b) ∧ c=b?
6. Dodec(c) é uma consequência lógica de Dodec(b) ∧ c=b?
7. Dodec(c) é uma consequência lógica de Dodec(b) ∧ e=c?
10 {4.31} Forma normal negativa. Abra Turing’s Sentences. Escreva nas frases em
branco a forma normal negativa da frase imediatamente anterior. Construa um mundo
qualquer em que todos os nomes sejam usados. Cada frase par deve ter o mesmo valor
que a ímpar que a antecede. Verifique.
11 {4.39} Conversão de formas normais. Abra CNF Sentences. Converta cada frase
ímpar na outra forma normal e coloque-a na frase par a seguir. Construa um mundo em
que todas as frases ímpares sejam verdadeiras. Verifique se as pares também o são. As
formas normais habitualmente facilitam a determinação do valor de verdade de uma
expressão. A forma normal mais adequada depende do caso.
12 {4.40} Forma normal conjuntiva. Abra More CNF Sentences. Neste ficheiro existem
frases de três em três linhas. As duas linhas em branco destinam-se às mesmas frases
nas formas normais negativa e conjuntiva. Analise a correcção das transformações
abrindo vários mundos e verificando a igualdade dos valores de verdade em cada trio
de frases.
13 {4.41, 4.42, 4.43} Formas normais. Para cada uma das frases seguintes encontre uma
frase na forma normal disjuntiva que lhe seja logicamente equivalente. Assuma que A,
B, C e D são literais.
1. C ∧ (A ∨ (B ∧ C)).
2. B ∧ (A ∧ B ∧ (A ∨ B ∨ (B ∧ C))).
3. A ∧ (A ∧ (B ∨ (A ∧ C))).
CRISTINA RIBEIRO
BOOLE - 3
FEUP / LEIC
TEORIA DA COMPUTAÇÃO II
14 {5.1, 5.2, 5.3, 5.4, 5.5, 5.6} Passos válidos. Lista-se a seguir um conjunto de passos de
inferência dos quais apenas alguns são válidos. Diga quais, justificando com as tabelas
de verdade respectivas ou mostrando como um determinado passo pode levar de
premissas verdadeiras a conclusões falsas.
1. De P ∨ Q e ¬P inferir Q.
2. De P ∨ Q e Q inferir ¬P.
3. De ¬(P ∨ Q) inferir ¬P.
4. De ¬(P ∧ Q) e P inferir ¬Q.
5. De ¬(P ∧ Q) inferir ¬P.
6. De P ∧ Q e ¬P inferir Q.
15 {5.7} Prova informal. Prove Happy(carl) a partir das seguintes premissas, anotando
apenas os passos importantes, tais como o uso da prova por casos ou da prova por
contradição:
1. Home(max) ∨ Home(claire)
2. ¬Home(max) ∨ Happy(carl)
3. ¬Home(claire) ∨ Happy(carl)
16 {5.8} Consequência lógica. Prove BackOf(a,b) a partir das quatro premissas seguintes:
1. LeftOf(a,b) ∨ RightOf(a,b)
2. BackOf(a,b) ∨ ¬LeftOf(a,b)
3. FrontOf(b,a) ∨ ¬RightOf(a,b)
4. SameCol(c,a) ∧ SameRow(c,b)
17 {5.23, 5.24, 5.25} Números naturais. Prove os três factos seguintes sobre os números
naturais, a partir dos factos básicos da aritmética e das definições de par e ímpar.
a) Assuma que n2 é ímpar. Prove que n é ímpar.
b) Assuma que n+m é ímpar. Prove que n×m é par.
c) Assuma que n2 é divisível por 3. Prove que n2 é divisível por 9.
18 {6.2} Prova incompleta no Fitch. Abrir Exercise 6.2 que contém uma prova
incompleta. Completar os passos e as justificações e verificar a prova.
19 {6.3, 6.6} Provas em Fitch. Use o Fitch para construir provas formais para as
seguintes fórmulas.
a) a=c ∧ b=d
a partir de a=b ∧ b=c ∧ c=d
b) A ∧ (B ∨ C) a partir de (A ∧ B) ∨ (A ∧ C)
20 {Sec 6.3} Abrir Negation 2 com Fitch. A prova apresentada tem como premissas um
conjunto de fórmulas, das quais alguns subconjuntos são contraditórios.
-
Foque cada passo que contém o símbolo ⊥ e veja as frases que são citadas. Só um
destes passos é uma aplicação da regra ⊥ Intro. Complete-o e verifique.
-
Dos restantes passos, há um em que as frases citadas são contradições tautológicas.
Atribua-lhe a justificação Taut Con e verifique. (Este passo poderia ser derivado
das mesmas premissas apenas com as regras Booleanas.)
CRISTINA RIBEIRO
BOOLE - 4
FEUP / LEIC
TEORIA DA COMPUTAÇÃO II
-
Dos restantes passos, há dois cujas frases de suporte são contraditórias atendendo
ao significado do =. Atribua-lhe a justificação FO Con e verifique. (Este passo
poderia ser derivado das mesmas premissas usando as regras para o =.)
-
Verifique que os restantes passos não podem ser justificados pelas regras ⊥ Intro,
Taut Con e FO Con. Atribua-lhes a justificação Ana Con e verifique.
21 { 6.24, 6.25} DeMorgan. Construa provas informais e, em seguida, provas formais
semelhantes em estrutura, das seguintes frases, sem recorrer às leis de DeMorgan:
a) ¬P ∧ ¬Q a partir da premissa ¬(P ∨ Q).
b) ¬(P ∨ Q) a partir da premissa ¬P ∧ ¬Q.
22 {6.35, 6.38} Provas sem premissas. Construa provas formais sem premissas de:
a) ¬ (a=b ∧ Dodec(a) ∧ Cube(b))
b) ¬ (SameRow(a,b) ∧ SameRow(b,c) ∧ FrontOf(c,a))
c) ¬(a=b ∧ b≠a).
23 {6.28} Contradição em sentido lato. Produza uma prova formal no Fitch de Small(c)
a partir das premissas Cube(c) ∨ Small(c) e Dodec(c). Pode usar Ana Con
envolvendo literais e ⊥.
CRISTINA RIBEIRO
BOOLE - 5