Relações Semânticas entre Conectivos e Formas Normais

Prévia do material em texto

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 
(∧, ∨, , , )
Num conjunto completo Ψ, dada uma fórmula H 
do tipo (P), (P∨Q), (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
 {,∨}
 As fórmulas com conectivos {∧,,} são 
trocadas por equivalências com {,∨}
 Achar tautologias do tipo
 (P*Q)  F, sendo
 * ∈ {∧,,} 
 F expressa com {,∨}
 Equivalência entre ∧ e {,∨}
 (P∧Q)  (P ∨  Q) é uma tautologia
 (P∧Q) e (P ∨  Q) são equivalentes
Equivalência entre  e {,∨}
 (PQ)  (P∨Q) é uma tautologia
 (PQ) e  (P∨Q) são equivalentes
 Resultado importante
 Olha  sob o ponto de vista de 
interpretação (valoração)
Equivalência entre  e {,∨}
 (P  Q)  ((P  Q)∧(Q  P))
 Substituindo  por seu equivalente
 (P  Q)  ((P ∨ Q)∧(Q ∨ P))
 Substituindo ∧ por seu equivalente
 (P  Q)  ((P ∨ Q)∨(Q ∨ P))
 Está provada a completude de {,∨}
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 {,∨} 
 Dada uma fórmula E, como obter G contendo 
apenas {,∨}
 e.g. Eg=(P  Q)∨(R  S)
 Substituir  PQ [G'] por
((P ∨ Q)∨(Q ∨ P)) [H']
 Eh'=((P ∨ Q)∨(Q ∨ P))∨(R  S)
 Substituir  RS [G] por (R ∨ S)  [H]
 Eh=((P ∨ Q)∨(Q ∨ P))∨(R∨S)
 Eh equivale a Eg!
Conjunto {nand}
 (P nand Q) = ((P^Q))
 {nand} é completo!
 Demonstração
 Se {nand} puder expressar {,∨} 
 P equivale a (P nand P) (1)
 (P∨Q) equivale a (P nand Q)
 Lei de Morgan: (P ^ Q) equivale a (P ∨ Q)
Transformação para o conectivo 
nand
 H=P∧(RS)
 Primeiro, transformar para {,∨} 
 Depois transformar para nand, usando as 
equivalências
 P equivale a (P nand P) 
 (P∨Q) 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: ( e )
 Símbolos de verdade: false
 true = false
 Símbolos proposicionais: P, Q, R, S, P1, Q1, P2, 
Q2...
 Conectivos proposicionais: ,∨ 
Formas normais e {,∨,∧} 
 Um literal é um símbolo proposicional ou sua 
negação
 Um bom conjunto completo é {,∨,∧}
 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 ∨ F2 ∨ ... ∨ Fn, onde 
 Fi é uma conjunção (da forma 
A1 ∧ A2 ∧ ... ∧ An ) e
 Ai é um literal
 Ex: H=(P∧Q) ∨ (R∧Q∧P) ∨ (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 ∨ A2 ∨ ... ∨ An ) e
 Ai é um literal
 Ex: G=(P∨Q) ∧ (R∨Q∨P) ∧ (P∨S)  
Obtenção de formas normais
 Observe que H e G são parecidos 
 H=(P∧Q) ∨ (R∧Q∧P) ∨ (P∧S), DNF
 G=(P∨Q) ∧ (R∨Q∨P) ∧ (P∨S), 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 ∨ L2 ∨ L3, DNF
 H=(P∧Q∧R) ∨ (P∧Q∧R) ∨ (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=(P∨Q∨R) ∧ (P∨Q∨R) ∧ 
(P∨Q∨R) ∧ (P∨Q∨R) ∧ (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
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 = (P∨Q)
 P  Q = (P  Q)∧(Q  P)
 2 ­Lei da negação
 (H)  H
 2 ­Leis de De Morgan
 (P∨Q) = P ∧ Q 
 (P∧Q) = P ∨ Q
 3 ­Leis distributivas:
 F ∨ (G∧H) = (F∨G) ∧ (F∨H)
 F ∧ (G∨H) = (F∧G) ∨ (F∧H)
Exercícios
 Obter DNF de (P ∨ Q) R
 = (P∨Q) ∨ R (eliminação de )
 = (P ∧^ (Q)) ∨ R (De Morgan)
 = (P ∧ Q) ∨ R (negação)
 Obter CNF de (P∧(QR))S
CNF e DNF: Completude
 Para toda sentença A, existe uma sentença 
Ac na CNF e uma sentença Ad na DNF, tal 
que A ≡ Ac ≡ Ad.
 Prova por indução:
 Caso base: Fórmulas atômicas já estão 
tanto na CNF quanto na DNF
 Passo Indutivo:
 Slide seguinte
Passo Indutivo: 
 Verdade para A   Verdade para → A
 Seja Ac uma fórmula CNF e Ad uma 
fórmula DNF tal que A ≡ Ac ≡ Ad.
 Seja
  ¬Ac=¬(∧i=1
n
Di)≡∨i=1
n
¬Di≡∨
i=1
n
D i a última está na DNF
continuar...
	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
	Slide 19
	Slide 20
	Slide 21