P1 - 2011.2 - Gabarito

Prévia do material em texto

P1 de Lo´gica (INF1009) – 2011.2
Profs. Alexandre Rademaker e Cecilia Lustosa
Nome/Matr.:
1. Usando a tabela verdade, justifique se a sentenc¸a “Se eu estudar, enta˜o passo em lo´gica” e´ logicamente
equivalente a: (1) “Na˜o estudo ou passo em lo´gica”; e (2) “Estudo ou na˜o passo em lo´gica”.
Solution:
EE → PL ≡ ¬EE ∨ PL
EE → PL 6≡ EE ∨ ¬PL
EE | PL | EE | PL |
----------- -----------
T | T | T T | T | T
T | F | T T | F | F
F | T | T F | T | F
F | F | T F | F | T
2. Considerando o texto:
“Se o partido apoiar o candidato ou votar a emenda, ganharemos a eleic¸a˜o. So´ se na˜o
disputarmos o segundo mandato ganharemos a eleic¸a˜o. Disputaremos o segundo mandato.”.
Desejamos verificar se podemos concluir as sentenc¸as: (A) “O partido na˜o apoiou o candidato”; e
(B) “Se o partido na˜o apoiar o candidato, votaremos a emenda”.
(a) Formalize todas as sentenc¸as do problema.
(b) Usando Tableaux, justifique se podemos concluir (A) e (B) a partir do texto.
Solution:
(((PA ∨ V O)→ GE) ∧ (¬DS ↔ GE) ∧DS)→ ¬PA
(((PA ∨ V O)→ GE) ∧ (¬DS ↔ GE) ∧DS)→ (¬PA→ V O)
Construindo o Tableaux de ambas as fo´rmulas, concluimos que A e´ va´lida, ou seja, ¬PA e´
consequeˆncia lo´gica do texto. E B na˜o e´ va´lida, ou seja, e´ poss´ıvel tornar a premissa verdadeira
e´ a consequeˆncia falsa. Usei o site http://www.umsu.de/logik/trees/.
3. Nos itens abaixo, α e β sa˜o fo´rmulas. Escolha 3 itens e indique se a afirmac¸a˜o e´ (V) ou (F)
justificando:
(a) Se β e´ insatisfat´ıvel, enta˜o na˜o existe α tal que α |= β.
(b) Se β na˜o e´ consequeˆncia lo´gica de α, enta˜o α e´ satisfat´ıvel.
(c) Se α e´ insatisfat´ıvel, enta˜o α→ β tambe´m e´.
(d) Se α→ β e´ va´lida, enta˜o β e´ satisfat´ıvel.
(e) α ∨ β na˜o e´ logicamente equivalente a ¬(¬α ∧ ¬¬¬(β ∨ β)).
(f) Se α ∨ β e´ va´lida, enta˜o α e´ va´lida ou β e´ va´lida.
Solution:
(a) falso. Basta α ser insatisfat´ıvel.
(b) verdade. Pois e´ necessa´rio alguma linha da tabela verdade onde α seja verdade e β falso.
(c) falso. Na realidade a implicac¸a˜o e´ tautologia.
(d) falso. Basta α ser insatisfat´ıvel.
(e) falso. Sabemos que β ∨ β ≡ β e que ¬¬β ≡ β. Finalmente, α ∨ β ≡ ¬(¬α ∧ ¬β)
(f) falso. α ∨ ¬α e´ tautologia mas nem α nem ¬α sa˜o tautologias.
4. Ana e Maria foram a uma festa usando vestidos de cores diferente. Um vestido era azul e o outro
era branco. Traduza as sentenc¸as abaixo para a linguagem da lo´gica proposicional. Use a seguinte
representac¸a˜o: AA Ana veste azul; AB Ana veste branco; MA Maria veste azul; e MB Maria veste
branco.
(a) Ana e Maria vestem branco ou azul.
(b) Cada menina usa apenas uma cor.
(c) Ana e Maria na˜o vestem a mesma cor.
Solution:
(AB ∨AA) ∧ (MA ∨MB) (1)
(AB → ¬AA) ∧ (AA→ ¬AB) ∧ (MA→ ¬MB) ∧ (MB → ¬MA) (2)
(AA→ ¬MA) ∧ (AB → ¬MB) ∧ (MA→ ¬AA) ∧ (MB → ¬AB) (3)
5. Dizemos que duas fo´rmulas X e Y sa˜o equivalentes quando X |= Y e Y |= X. Utilizando tabelas
verdade para justificar sua resposta, apresente uma fo´rmula equivalente a` A→ B que utilize apenas
os conectivos lo´gicos {¬,∧}.
Solution: ¬(A ∧ ¬B)
6. Escolha dois dos itens abaixo e indique se a fo´rmula e´ uma tautologia (va´lida ou verdadeira em
toda valorac¸a˜o) ou na˜o. Justifique sua resposta com o uso de Tableaux em ambos os casos. Se a
fo´rmula na˜o for uma tautologia, apresente uma interpretac¸a˜o que a falsifique.
(a) ((A→ B) ∨ (B → A))→ (C → C)
(b) ((A ∨B) ∧ (¬B ∨ C))→ (¬A→ C)
(c) (((A ∧B) ∨ (¬B ∨ C))→ A)→ C
Solution: Usando o site http://www.umsu.de/logik/trees/, A e B sa˜o tautologias e C e´ falso
para na˜o e´ para “A” verdade e “C” falso.
Page 2