Todos

JOÃO NUNES de SOUZA

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

Uma introdução concisa
21 de maio de 2008

1 A linguagem da Lógica Proposicional

Introdução Alfabeto da Lógica Proposicional
Definição 1.1 (alfabeto) O alfabeto da Lógica Proposicional é constituído por: • • • • símbolos de pontuação: (, ); símbolos de verdade: true, false; símbolos proposicionais: P, Q, R, S, P1 , Q1 , R1 , S1 , P2 , Q2 , . . .; conectivos proposicionais: ¬ ,∨ ,∧ ,→ ,↔ .

Fórmulas da Lógica Proposicional
Definição 1.2 (fórmula) As fórmulas da linguagem da Lógica Proposicional são construídas, de forma indutiva, a partir dos símbolos do alfabeto conforme as regras a seguir. O conjunto das fórmulas é o menor conjunto que satisfaz as regras: • • • • • • • todo símbolo de verdade é uma fórmula; todo símbolo proposicional é uma fórmula; se H é uma fórmula, então (¬H), a negação de H, é uma fórmula; se H e G são fórmulas, então a disjunção de H e G, dada por: (H ∨ G), é uma fórmula; se H e G são fórmulas, então a conjunção de H e G, dada por: (H ∧ G), é uma fórmula; se H e G são fórmulas, então a implicação de H em G, dada por: (H → G), é uma fórmula. Nesse caso, H é o antecedente e G o conseqüente da fórmula (H → G); se H e G são fórmulas, então a bi-implicação de H e G, dada por: (H ↔ G), é uma fórmula. Nesse caso, H é o lado esquerdo e G o lado direito da fórmula (H ↔ G).

ELSEVIER

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

Notação. Neste livro, os parênteses ou símbolos de pontuação das fórmulas são omitidos quando não há problemas sobre a sua interpretação. Além disso, as fórmulas podem ser escritas em várias linhas para uma melhor leitura. Assim, a fórmula: (((P ∨ R) → true) ↔ (Q ∧ S)) pode ser escrita como (P ∨ R) → true ↔ Q∧S ou ainda como ((P ∨ R) → true) ↔ (Q ∧ S). Definição 1.3 (ordem de precedência) Na Lógica Proposicional, a ordem de precedência dos conectivos proposicionais é definida por: • • • maior precedência: ¬; precedência intermediária: → , ↔; menor precedência: ∧ ,