Métodos para Determinação de Validade de Fórmulas

Prévia do material em texto

Lógica Proposicional
Introdução a 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 redução ao absurdo
Tabelas-verdade
 Método exaustivo
 Criar uma valorização para cada subfórmula
 Descobrir se é válida(tautologia)/satisfazível/ 
insatisfazível(contraditória)/falsificável
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 5
6 7 8Nós - números
Raiz – 1
Folhas – 2,6,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
2 3
I[P]=T I[P]=F
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
2 3
I[P]=T I[P]=F
 4 5
 T T
I[Q]=T          I[Q]=F        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
Aqui já se sabe que I[P] = T e I[R] = F
Exemplo do método da negação 
ou absurdo (cont.)
 ((P  Q)^(Q  R)) (P  R)
       T     T     T        F  T F  F
 ((P  Q)^(Q  R)) (P  R)
   T  T  T     F T  F   F  T  F  F
                
 Portanto: 
 ((P  Q)^(Q  R)) (P  R)
                               F não pode existir!
 Então, sempre 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: F
 Possibilidade 1: T F F
 Possibilidade 2: F F T
Exemplo de Ausência de absurdo
 Exemplo:  H=   (PQ) ((P)(Q)) 
 Possibilidade 1: T F F
 F T T F TF F FT
 Possibilidade 2: F F T
 T F F F FT T TF
 Não se pode concluir que H é tautologia
 Se I[P]=T e I[Q]=F, 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
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18