Buscar

Cap5 (Relações Semânticas entre Conectivos)

Prévia do material em texto

Capítulo 5 
 
Relações semânticas 
entre os conectivos da 
Lógica Proposicional 
 
Conjunto de conectivos completo 
Um conjunto de conectivos é qualquer 
conjunto cujos elementos sejam conectivos 
(^, v, , , ) 
Definição 5.1 (conjunto de conectivos 
completo) Seja  um conjunto de conectivos. 
Esse conjunto é completo se, 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  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=(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) 
Substituindo  (1), (PvQ) equivale a 
((P nand P) nand (Q nand Q)) 
Transformação para o conectivo 
nand 
H=P^(RS) 
Primeiro, transformar para {,v} 
Depois transformar para nand, usando 
as equivalências 
H equivale a G onde G = (P nand (R nand (S 
nand S))) nand (P nand (R nand (S nand S))) 
(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 
 
E com nand??? 
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 
Os mesmos, trocando-se T por 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

Outros materiais