Lista1_2

Prévia do material em texto

Pontif´ıcia Universidade Cato´lica do Parana´
Centro de Cieˆncias Exatas e de Tecnologia
Departamento de Informa´tica
Programa de Aprendizagem em Lo´gica Matema´tica
Prof. Bra´ulio Coelho A´vila
Lista 1.2 — 2008
1. Dada as expresso˜es, dizer quais sa˜o fo´rmulas bem formadas do Ca´lculo Proposicional.
(a) p ∨ (q ∧ r)
(b) p↔ 1
(c) (p→ ¬q) → (q → ¬p)
(d) q + 2 → p
(e) (p ∧ q) → ¬r → q
2. Identificar dentre as fo´rmulas abaixo as tautologias e as contradic¸o˜es.
(a) ¬(p ∨ q) ∨ ¬q
(b) p ∨ (p→ q)
(c) (p→ q) → (¬q → ¬p)
(d) p ∧ ¬(¬q ∨ p)
(e) p→ (q → p)
(f) ¬(p→ p)
(g) p→ (¬p→ q)
3. Verificar se os seguintes enunciados sa˜o equivalentes.
(a) ¬(p→ q) e p ∧ ¬q
(b) p ∧ q e ¬(¬p ∧ q)
(c) p ∧ q e ¬(¬p ∨ ¬q)
(d) p ∨ (q ∧ r) e (p ∨ q) ∧ (p ∨ r)
(e) ¬(p→ q) e (p ∨ q) ∧ (p ∨ r)
4. Sejam:
(a) Negra˜o e Maur´ıcio sa˜o jogadores da Selec¸a˜o Brasileira de Volei Masculino (v);
(b) Negra˜o esta´ contundido (v);
(c) O Brasil tem uma boa Selec¸a˜o de Volei Masculino (v);
(d) A Selec¸a˜o de Volei na˜o esta´ desfalcada (f).
Dar o valor lo´gico das seguintes fo´rmulas:
i. a→ d
ii. (a ∧ b) ∧ ¬d
iii. (¬b→ a) → (c→ d)
iv. (a ∧ b) ∨ ¬d
5. Sabendo-se que p∧r tem valor (v), qual valor deve-se atribuir a` q para que o enunciado
abaixo seja verdadeiro?
¬r ∨ (p ∧ r) → ¬p ∨ q
6. Verificar se a informac¸a˜o dada e´ suficiente para determinar um u´nico valor-verdade da
fo´rmula.
(a) p→ (p→ q ∨ r), se r e´ falso;
(b) (p→ q) → r, se r e´ verdadeiro;
(c) p ∨ (p→ r), se r e´ falso;
(d) ((p ∨ q) ↔ (q ∧ q)) → ((r ∨ p) ∨ q), se q e´ verdadeiro;
(e) ¬((p→ q ∧ r) → ((¬q ∨ ¬r) → ¬p)), se p e´ verdadeiro;
(f) (p ∨ (q ∧ r)) → (p ∨ s→ (q → ((p ∨ s) ∧ q))), se r e´ falso.
7. Admitindo-se verdadeiro o condicional ¬(p→ q). Dar o valor lo´gico de:
(a) (p→ q) → (q ∨ r)
(b) (q ∨ r) → ((p→ ¬q) → r)
(c) (p→ r) → ((q ∨ r) → (p→ r))
8. Verificar, justificando, quais dos enunciados abaixo sa˜o verdadeiros.
(a) ¬(p ∨ q) ∧ q e´ contradic¸a˜o;
(b) (p↔ q ∧ ¬p) ↔ ¬q e´ contradic¸a˜o;
(c) (p→ q ∧ ¬p) → ¬q e´ insatisfat´ıvel;
(d) Se p e´ falso enta˜o q e´ equivalente a ¬p ∨ q.
9. Encontrar um enunciado equivalente a p→ (q → r), onde somente ocorram os conec-
tivos ¬ e ∨.
10. Encontrar um enunciado equivalente a ¬(p ∧ q) ∨ r, onde somente ocorra o conectivo
→.
11. Encontrar uma fo´rmula do Ca´lculo Proposicional que na˜o seja logicamente va´lida e
nem insatisfat´ıvel.
12. Considerar as fo´rmulas: p→ q,¬q,¬p
Mostrar que ¬p e´ uma consequ¨eˆncia lo´gica de p→ q e ¬q.
13. Mostrar que as fo´rmulas abaixo sa˜o logicamente va´lidas.
(a) ¬(p ∨ q) ↔ ¬p ∧ q
(b) p ∨ (q ∧ r) ↔ (p ∨ q) ∧ (p ∨ r)
14. Verificar se as informac¸o˜es dadas abaixo, sa˜o verdadeiras ou falsas. Justificar sua
resposta.
(a) Uma fo´rmula e´ va´lida se sua negac¸a˜o e´ insatisfat´ıvel;
(b) Se uma fo´rmula e´ insatisfat´ıvel enta˜o sua negac¸a˜o e´ inva´lida;
(c) Uma fo´rmula e´ inva´lida se ha´ pelo menos uma interpretac¸a˜o sob a qual a fo´rmula
e´ falsa;
(d) Se uma fo´rmula e´ satisfat´ıvel enta˜o ha´ pelo menos uma interpretac¸a˜o sob a qual
a fo´rmula e´ verdadeira;
(e) Se uma fo´rmula e´ satisfat´ıvel enta˜o ela e´ va´lida;
(f) Uma fo´rmula e´ inva´lida se e´ insatisfat´ıvel.
15. Justificar:
(a) p ∧ p e´ insatisfat´ıvel — contradic¸a˜o;
(b) p ∨ ¬p e´ va´lida — tautologia;
(c) p→ p e´ satisfat´ıvel.