Logica

JOÃO NUNES de SOUZA

LÓGICA para CIÊNCIA da COMPUTAÇÃO

Uma introdução concisa
2 de junho de 2009

1 A linguagem da Lógica Proposicional

Errata
Caso você encontre algum erro nesse capítulo ou tenha algum comentário a fazer, envie-o para [e-mail]. Muito obrigado.

Sugestões e soluções de exercícios selecionados
1. a) Não é fórmula b) É fórmula c) É fórmula d) Não é fórmula e) É fórmula 2. a) Sim, por exemplo, as fórmulas P , true, etc c) Não 3. a) comprimento igual a 11. 4. a) ¬¬P ↔ (¬(¬¬(P ∨ Q) → R) ∧ P ). 5. c) ((¬P ) ∨ (Q ↔ Q)). 6. a) A fórmula do item a) do exercício 4 é escrita como: ↔ ¬¬ ∧ ¬ → ¬¬ ∨ P QRP. b) ↔→ ¬P ∨ QR ↔ ∧P Q ∨ ¬¬R¬P . 7. a) Não. b) Não. 8. 9. Par.

ELSEVIER 10. a) comp[H] é um número ímpar.

LÓGICA para CIÊNCIA da COMPUTAÇÃO

b) comp[H] é o dobro do número de conectivos de H, mais um.

4

2 A semântica da Lógica Proposicional

Errata
Caso você encontre algum erro nesse capítulo ou tenha algum comentário a fazer, envie-o para [e-mail]. Muito obrigado.

Sugestões e soluções de exercícios selecionados
1. No contexto deste livro, qual a diferença entre os símbolos? a) true é um símbolo sintático, que pertence ao alfabeto da Lógica Proposicional e T é um símbolo semântico. c) → é um conectivo, que pertence ao alfabeto da Lógica Proposicional e ⇒ é um símbolo da metalinguagem. Observe, portanto, que ⇒ não pertence à linguagem da Lógica Proposicional. 2. 3. 4. a) Não temos a possibilidade: I[P ] = T e I[Q] = F . b) I[Q] = T c) I[H] = T d) Nada podemos concluir a respeito de I[Q]? e) I[H] = F 5. a) I[(¬P ∨ Q) ↔ (P → Q)] = T e nada podemos concluir a respeito de J[Q] e J[R]. 6. a) I[(P ∨ R) → (Q ∨ R)] = T b) I[(P ∧ R) → (Q ∧ R)] = T c) Nada se pode concluir a respeito de I[(¬P ∨ Q) → (P ∨ Q)] 7.

ELSEVIER 8. a) I[H] = F b) I[H] = T 9.

LÓGICA para CIÊNCIA da COMPUTAÇÃO

10. a) Considere as associações: P = eu sou feliz, Q = você é feliz. Neste caso, a representação é dada por (P → ¬Q) ∧ (¬Q → ¬P ) b)