Lógica
Proposicional
Métodos para
determinação de
validade de fórmulas
Métodos para determinação
de validade de fórmulas



Tabela verdade
Árvore semântica
Método da negação ou absurdo
Conseqüência Lógica



B é conseqüência lógica de A se toda
valorização v que satisfaz A também
satisfaz B
B pode ser satisfeito por valores que
não satisfazem A
Podemos usar: A implica
logicamente em B
Conseqüência Lógica
Se eu ganhar na loteria, serei rico.
Eu ganhei na Loteria.
Logo, sou rico.
G = Ganhar na loteria
R = Ser rico
G
V
V
F
F
R
V
F
V
F
GR
V
F
V
V
(G  R)^G
V
F
F
F
Tabelas-verdade



Método exaustivo
Criar uma valorização para cada
subfórumla
Descobrir se é
válida(tautologia)/satisfazível/
intetisfazível(contraditória)/falsificavél
Tabelas-verdade

Tabelas verdade associada a fórmulas


Como fazer para obter a tabela verdade
associada à fórmula H=((P)vQ)(Q^P)?
Colunas intermediárias: P,Q,P, PvQ e
Q^P
Tabelas-verdade

Tabelas das Principais Operações do
Cálculo Proposicional
Negação

Conjunção

Tabelas-verdade

Tabelas das Principais Operações do
Cálculo Proposicional
Disjunção

Condicional

Tabelas-verdade


Tabelas das Principais Operações do
Cálculo Proposicional
Bi-Condicional
Árvore
1
2
3
4
Nós - números
Raiz – 1
Folhas – 2,6,7,8
6
5
7
8
Método da
árvore semântica


Usa a estrutura de árvore para
determinar a validade de uma fórmula
Determinar: (PQ) ((Q)(P))
Método da
árvore semântica







Nó 2:
H=(PQ) ((Q)(P))
T
T
T
FT
Nó 3:
H=(PQ) ((Q)(P))
FT
T
T TF
1
I[P]=T
2
I[P]=F
3
T
Método da árvore semântica






Nó 4:
H=(PQ) ((Q)(P))
T T T T FT T FT
Nó 5:
H=(PQ) ((Q)(P))
TF F T TF T FT
1
I[P]=T
I[P]=F
1
I[Q]=T
4
T
2
I[Q]=F
T
5
3
T
Método da negação ou
absurdo

Para provar que H é uma tautologia

Supõe-se inicialmente, por absurdo que



H NÃO é uma tautologia
As deduções desta fórmula levam a um
fato contraditório (ou absurdo)
Portanto, a suposição inicial é falsa e:


H é uma tautologia
(A não-validade de H é um absurdo)
Exemplo do método da
negação ou absurdo

Lei da transitividade:


((P  Q)^(Q  R)) (P  R)
Por absurdo:





((P  Q)^(Q  R)) (P  R)
F
I[(P  Q)^(Q  R) ]=T e I[(P  R)]=F
((P  Q)^(Q  R)) (P  R)
T
T
T
F T F F
Exemplo do método da
negação ou absurdo (cont.)







((P  Q)^(Q  R))
T
T
T
T T
T
T F
T T T T F TF


Portanto:
((P  Q)^(Q  R))


Então, sempre
(P 
F T F
F T F
F T F
R)
F
F
F
(P  R)
F não pode existir!
T (tautologia!)
Aplicações do método da
negação ou absurdo

Fórmulas com o conectivo 

Só existe uma possibilidade de absurdo


I[Antecedente]=T e I[Conseqüente]=F
Fórmulas com o conectivo ^

Também 1 só forma: I[A]=T e I[B]=T
Ausência de absurdo

Se uma asserção é negada, mas o
absurdo não aparece,


Nada se pode concluir sobre a veracidade
da asserção
Exemplo:



(PQ) ((P)(Q))
Por absurdo:
Possibilidade 1: T
Possibilidade 2: F
F
F
F
F
T
Exemplo de Ausência de
absurdo

Exemplo: H= (PQ) ((P)(Q))





Possibilidade 1:
T
FTT
Possibilidade 2: F
TFF
F
F
F
F
F
TF F FT
T
FT F TF
Não se pode concluir que H é tautologia

Se I[P]=F e I[Q]=T, então I[H]=F
Exercício do método de
negação ou absurdo

H=(P^Q) ((PvQ)) é tautologia?

Só se H levar a absurdo em TODAS as
possibilidades