30 - Relações semânticas entre conectivos e formas normais

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
Lógica Proposicional
Relações semânticas 
entre conectivos e 
formas normais 
*
Conjunto de conectivos completo
Um conjunto de conectivos é qualquer conjunto cujos elementos sejam conectivos (^, v, , , )
Num conjunto completo C, dada uma fórmula H do tipo (P), (PvQ), (P^Q), (PQ) ou (PQ), então é possível determinar uma fórmula G, equivalente, usando apenas os conectivos de C e os símbolos proposicionais de H.
*
Exemplo de conjunto de conectivos completo
{,v}
As fórmulas com conectivos {^,,} são trocadas por equivalências com {,v}
Achar tautologias do tipo
(P*Q)  F, sendo
* € {^,,} 
F expressa com {,v}
Equivalência entre ^ e {,v}
(P^Q)  (Pv  Q) é uma tautologia
(P^Q) e (Pv  Q) são equivalentes
*
Equivalência entre  e {,v}
(PQ)  (PvQ) é uma tautologia
(PQ) e (PvQ) são equivalentes
Resultado importante
Olha  sob o ponto de vista de interpretação (valoração)
*
Equivalência entre  e {,v}
(P  Q)  ((P  Q)^(Q  P))
Substituindo  por seu equivalente
(P  Q)  ((P v Q)^(Q v P))
Substituindo ^ por seu equivalente
(P  Q)  ((P v Q)v(Q v P))
Está provada a completude de {,v}
*
Regra de substituição de subfórmulas
Dadas as fórmulas da lógica proposicional Eg, Eh, G e H onde
G é subfórmula de Eg
H é subfórmula de Eh e
Eh é obtida de Eg substituindo as ocorrências de G em Eg por H
então se G equivale a H, Eg equivale a Eh 
*
Transformação para o conjunto {,v} 
Dada uma fórmula E, como obter G contendo apenas {,v}
e.g. E=(P  Q)v(R  S)
Substituir PQ por 			((P v Q)v(Q v P))
E=((P v Q)v(Q v P))v(R  S)
Substituir PQ por (Q v P)
G=((P v Q)v(Q v P))v(RvS)
G equivale a E!
*
Conjunto {nand}
(P nand Q) = ((P^Q))
{nand} é completo!
Demonstração
Se {nand} puder expressar {,v} 
P equivale a (P nand P) (1)
(PvQ) equivale a (P nand Q)
Lei de Morgan: (P ^ Q) equivale a (P v Q)
*
Transformação para o conectivo nand
H=P^(RS)
Primeiro, transformar para {,v} 
Depois transformar para nand, usando as equivalências
P equivale a (P nand P) 
(PvQ) equivale a 
((P nand P) nand (Q nand Q))
(PvQ) equivale a 
((P nand P) nand (Q nand Q))
*
Possível Redefinição da Linguagem da Lógica Proposicional
Alfabeto
Símbolos de pontuação: (,)
Símbolos de verdade: false
true = false
Símbolos proposicionais: P, Q, R, S, P1, Q1, P2, Q2...
Conectivos proposicionais: ,v 
*
Formas normais e {,v,^} 	
Um literal é um símbolo proposicional ou sua negação
Um bom conjunto completo é {,v,^}
Formas normais são obtidas a partir desse conjunto de conectivos
*
Forma normal disjuntiva 	
Uma fórmula está na forma normal disjuntiva (fnd ou DNF, em inglês) se é uma disjunção de conjunções de literais
F é da forma F1 v F2 v ... v Fn, onde 
Fi é uma conjunção (da forma 		A1 ^ A2 ^ ... ^ An ) e
Ai é um literal
Ex: H=(P^Q) v (R^Q^P) v (P^S) 
*
Forma normal conjuntiva 	
Uma fórmula está na forma normal conjuntiva (fnc ou CNF, em inglês) se é uma conjunção de disjunções de literais
F é da forma F1 ^ F2 ^ ... ^ Fn, onde 
Fi é uma disjunção (da forma 			A1 v A2 v ... v An ) e
Ai é um literal
Ex: G=(PvQ) ^ (RvQvP) ^ (PvS) 
*
Obtenção de formas normais
Observe que H e G são parecidos 
H=(P^Q) v (R^Q^P) v (P^S), DNF
G=(PvQ) ^ (RvQ vP) ^ (PvS), CNF
Para obtê-las a partir de fórmulas quaisquer usam-se algoritmos duais
Tabela verdade: DNF usa o T e CNF usa o F
*
Obtenção de formas normais a partir de tabelas-verdade
H=(PQ) ^ R
Pegam-se as linhas em que H=T
P Q R H
T T T T L1
F T T T L2
F F T T L3
L1=P^Q^R
L2=P^Q^R
L3=P^Q^R
H=L1 v L2 v L3, DNF
H=(P^Q^R) v (P^Q^R) v (P^Q^R)
P Q R H
T T T T	
T T F F
T F T F
T F F F
F T T T
F T F F
F F T T 
F F F F
*
Obtenção de formas normais conjuntivas
H=(PQ) ^ R
Pegam-se as linhas em que H=F
P Q R H
T T F F 
T F T F
T F F F
F T F F
F F F F
H=L1 ^ L2 ^ L3 ^ L4 ^ L5, DNF
H=(PvQvR) ^ (PvQvR) ^ (PvQvR) ^ (PvQvR) ^ (PvQvR)
P Q R H
T T T T	
T T F F
T F T F
T F F F
F T T T
F T F F
F F T T 
F F F F
*
Exercícios de obtenção de formas normais 
Obter DNF de (P ^Q) R
Obter CNF de (P ^Q) R
*
Algoritmos usando leis (repetidamente)
1 -Leis de eliminação 
PQ = (PvQ)
P  Q = (P  Q)^(Q  P)
2 -Lei da negação
(H)  H
2 -Leis de De Morgan
(PvQ) = P ^ Q 
(P^Q) = P v Q
3 -Leis distributivas:
F v (G^H) = (FvG) ^ (FvH)
F ^ (GvH) = (F^G) v (F^H)
*
Exercícios
Obter DNF de (P v Q) R
= (PvQ) v R (eliminação de )
= (P ^ (Q)) v R (De Morgan)
= (P ^ Q) v R (negação)
Obter CNF de (P^(QR))S