+ Alfabeto
– Símbolos Proposicionais
P, Q, R, P1, Q1, R1, P2, Q2, R2, …
– Símbolos de Pontuação
( )
– Símbolos de Verdade
True, False
Verdadeiro, Falso
– Conectivos Lógicos
v ou Disjunção (também encontrada com o símbolo + )
^ ou Conjunção (também encontrada com o símbolo . )
¬ ou negação (não)
→ também conhecido como implicação ou se-então
←→ também conhecido como “iff”, “se e somente se” ou bi-implicação
+ Fórmulas
– Conjunto de símbolos do alfabeto da lógica proposicional concatenados seguindo um conjunto específico de regras:
– Todo Símbolo de Verdade é uma Fórmula
– Todo Símbolo proposicional é uma fórmula
– Se H é uma fórmula, (¬H) (a negação de H) é uma fórmula
– Se H e G são fórmulas, então (HvG) (a disjunção de H e G) é uma fórmula
– Se H e G são fórmulas, então (H^G) (a conjunção de H e G) é uma fórmula
– Se H e G são fórmulas, então (H→G) é uma fórmula e é dito que H é o antecedente e G é o consequente da fórmula
– Se H e G são fórmulas, então (H←→G) é uma fórmula e é dito que H é o lado (ou componente) esquerdo e G é o lado (ou componente) direito da fórmula
Cada item acima define uma regra para a construção de fórmulas.
Observe a obrigatoriedade do uso dos símbolos de pontuação ( e )
Exemplos de Fórmulas
P
Q
True
(PvQ)
((PvQ)→True)
Símbolos de pontuação
– São utilizados para eliminar ambiguidades nas fórmulas
– Quando não há possibilidade de ambiguidade tais símbolos podem ser omitidos
– Ambiguidade surge devido à precedência dos operadores (conectivos lógicos) na álgebra de boole
Ordem de precedência (maior para menor):
¬
→, ←→
v,^
Exemplo de Ambiguidade:
P→Q←→R
Pode ser interpretada como
(P→(Q←→R)) ou ((P→Q)←→R)
Pode-se utilizar várias linhas para eliminar ambiguidade:
P→Q
←→
R
Não se considera o significado dos símbolos. A manipulação é puramente simbólica e avalia-se o relacionamento entre eles
+ Comprimento de uma Fórmula
Comp(H) define-se como:
– Se H é um símbolo de verdade ou um símbolo preposicional, então Comp[H]=1
– Se H é um símbolo de verdade, então Comp[¬H] = Comp[H]+1
– Se H e G são fórmulas, então Comp[HvG]=Comp[H]+Comp[G]+1
– Se H e G são fórmulas, então Comp[H^G]=Comp[H]+Comp[G]+1
– Se H e G são fórmulas, então Comp[H→G]=Comp[H]+Comp[G]+1
– Se H e G são fórmulas, então Comp[H←→G]=Comp[H]+Comp[G]+1