Métodos para Determinação de Validade de Fórmulas
18 pág.

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


DisciplinaLógica I9.475 materiais139.619 seguidores
Pré-visualização1 página
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
\uf06e Tabela verdade
\uf06e Árvore semântica
\uf06e Método da negação ou redução ao absurdo
Tabelas-verdade
\uf06e Método exaustivo
\uf06e Criar uma valorização para cada subfórmula
\uf06e Descobrir se é válida(tautologia)/satisfazível/ 
insatisfazível(contraditória)/falsificável
Tabelas-verdade
\uf06e Tabelas verdade associada a fórmulas
\uf06e Como fazer para obter a tabela 
verdade associada à fórmula 
H=((\uf0d8P)vQ)\uf0e0(Q^P)?
\uf06e Colunas intermediárias: P,Q,\uf0d8P, \uf0d8PvQ 
e Q^P
Tabelas-verdade
\uf06e Tabelas das Principais Operações do Cálculo 
Proposicional
\uf06e Negação
\uf06e Conjunção
Tabelas-verdade
\uf06e Tabelas das Principais Operações do Cálculo 
Proposicional
\uf06e Disjunção
\uf06e Condicional
Tabelas-verdade
\uf06e Tabelas das Principais Operações do Cálculo 
Proposicional
\uf06e Bi­Condicional
Árvore
1
2 3
4 5
6 7 8Nós - números
Raiz \u2013 1
Folhas \u2013 2,6,7,8
Método da 
árvore semântica 
\uf06e Usa a estrutura de árvore para determinar a 
validade de uma fórmula
\uf06e Determinar: (P\uf0aeQ) \uf0ab((\uf0d8Q)\uf0ae(\uf0d8P))
Método da 
árvore semântica 
\uf06e Nó 2:
\uf06e H=(P\uf0aeQ) \uf0ab((\uf0d8Q)\uf0ae(\uf0d8P))
\uf06e       T                     T
\uf06e       T                   FT
\uf06e Nó 3:
\uf06e H=(P\uf0aeQ) \uf0ab((\uf0d8Q)\uf0ae(\uf0d8P))
\uf06e       FT      T      T TF
1
2 3
I[P]=T I[P]=F
T
Método da árvore semântica
\uf06e Nó 4:
\uf06e H=(P\uf0aeQ) \uf0ab((\uf0d8Q)\uf0ae(\uf0d8P))
\uf06e       T T T  T    FT  T   FT
\uf06e Nó 5:
\uf06e H=(P\uf0aeQ) \uf0ab((\uf0d8Q)\uf0ae(\uf0d8P))
\uf06e       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
\uf06e Para provar que H é uma tautologia
\uf06e Supõe-se inicialmente, por absurdo que
\uf06e H NÃO é uma tautologia
\uf06e As deduções desta fórmula levam a um 
fato contraditório (ou absurdo)
\uf06e Portanto, a suposição inicial é falsa e:
\uf06e H é uma tautologia
\uf06e (A não-validade de H é um absurdo)
Exemplo do método da negação 
ou absurdo
\uf06e Lei da transitividade: 
\uf06e ((P \uf0ae Q)^(Q \uf0ae R)) \uf0ae(P \uf0ae R)
\uf06e Por absurdo:
\uf06e ((P \uf0ae Q)^(Q \uf0ae R)) \uf0ae(P \uf0ae R)
\uf06e F
\uf06e I[(P \uf0ae Q)^(Q \uf0ae R) ]=T e I[(P \uf0ae R)]=F
\uf06e ((P \uf0ae Q)^(Q \uf0ae R)) \uf0ae(P \uf0ae R)
\uf06e 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.)
\uf06e ((P \uf0ae Q)^(Q \uf0ae R)) \uf0ae(P \uf0ae R)
\uf06e       T     T     T        F  T F  F
\uf06e ((P \uf0ae Q)^(Q \uf0ae R)) \uf0ae(P \uf0ae R)
\uf06e   T  T  T     F T  F   F  T  F  F
\uf06e           \uf04c     \uf04c
\uf06e Portanto: 
\uf06e ((P \uf0ae Q)^(Q \uf0ae R)) \uf0ae(P \uf0ae R)
\uf06e                               F não pode existir!
\uf06e Então, sempre T  (tautologia!)
Aplicações do método da 
negação ou absurdo
\uf06e Fórmulas com o conectivo \uf0ae
\uf06e Só existe uma possibilidade de absurdo 
\uf06e I[Antecedente]=T e I[Conseqüente]=F 
\uf06e Fórmulas com o conectivo ^
\uf06e Também 1 só forma: I[A]=T e I[B]=T
Ausência de absurdo
\uf06e Se uma asserção é negada, mas o absurdo 
não aparece,
\uf06e Nada se pode concluir sobre a 
veracidade da asserção
\uf06e Exemplo:  (P\uf0aeQ) \uf0ab((\uf0d8P)\uf0ae(\uf0d8Q)) 
\uf06e Por absurdo: F
\uf06e Possibilidade 1: T F F
\uf06e Possibilidade 2: F F T
Exemplo de Ausência de absurdo
\uf06e Exemplo:  H=   (P\uf0aeQ) \uf0ab((\uf0d8P)\uf0ae(\uf0d8Q)) 
\uf06e Possibilidade 1: T F F
\uf06e F T T F TF F FT
\uf06e Possibilidade 2: F F T
\uf06e T F F F FT T TF
\uf06e Não se pode concluir que H é tautologia
\uf06e Se I[P]=T e I[Q]=F, então I[H]=F
Exercício do método de negação 
ou absurdo
\uf06e H=(P^Q) \uf0ab((\uf0d8PvQ)) é tautologia?
\uf06e Só se \uf0d8H 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