Estudante

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:
•