Formas Normais

Prévia do material em texto

Lógica proposicional
 Relações semânticas entre conectivos 
 Formas normais 
 Disjuntiva
 Conjuntiva
Conjunto de conectivos completo
 Conjunto de conectivos: (∧, ∨, →, ↔, ¬)
 Definição (conjunto de conectivos completo): Seja Ψ um conjunto 
de conectivos. Ψ é um conjunto completo se as condições a seguir 
são satisfeitas. Dada uma fórmula H do tipo (¬P), (P∨Q), (P∧Q), 
(P→Q) ou (P↔Q), então é possível determinar uma outra fórmula 
G, equivalente a H tal que G contém apenas conectivos do 
conjunto Ψ e os símbolos P e Q presentes em H.
Exemplo de conjunto de conectivos completo
 {¬,∨}
 As fórmulas com conectivos {∧,→,↔} são trocadas por 
equivalências com {¬,∨}
 Equivalência entre ∧ e {¬, ∨}
 (P ∧ Q) ↔ ¬(¬P ∨ ¬ Q) é uma tautologia
 Equivalência entre → e {¬, ∨}
 (P→Q) ↔ (¬P ∨ Q) é uma tautologia
 Equivalência entre ↔ e {¬, ∨}?
Equivalência entre ↔ e {¬,v}
 (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 {¬,∨}
O conjunto {¬,∨}
 O conjunto {¬,∨} é completo?
 É possível encontrar fórmulas equivalentes para (P∧Q), (P→Q) e 
(P↔Q) usando o conjunto {¬,∨} ?
 Qual seria uma possível redefinição da Linguagem da Lógica 
Proposicional?
Redefinição
 Alfabeto
 Símbolos de pontuação: ( , )
 Símbolos de verdade: false.
 Símbolos proposicionais: P,Q,R,S,P1,Q1,R1,S1,Q2...
 Conectivos proposicionais: ¬,∨
 O conjunto {¬,∧} também é completo
Formas normais
 Uma fórmula H está na forma normal disjuntiva (fnd) se é uma 
disjunção de conjunções de literais
 Uma fórmula H está na forma normal conjuntiva (fnc) se é uma 
conjunção de disjunções de literais
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
 Os mesmos, trocando-se T por F
Algoritmo
 Obtenção de fnd e fnc para a fórmula H
 Passo 1: obtenção da tabela verdade associada a H
 Passo 2: Extraia da tabela verdade as linhas que interpretam a 
fórmula H como T (para fnd) e como F(para fnc)
 Passo 3: 
 (fnd) Se a interpretação do literal A é F então ¬A 
Se a interpretação do literal A é T então A 
 (fnc) Se a interpretação do literal A é F então A 
Se a interpretação do literal A é T então ¬A 
 Passo 4: Obtenha a conjunção/disjunção dos literais
Exemplo – fnd (disjunção de conjunções)
 H=(P→Q) ∧ R
 Linhas em que H=T
P Q R H
T T T T L1
F T T T L5
F F T T L7
 L1 = P ∧ Q ∧ R
 L5 = ¬P ∧ Q ∧ R
 L7 = ¬P ∧ ¬Q ∧ R
 H = L1 ∨ L5 ∨ L7, FND
 H = (P ∧ Q ∧ R) ∨ (¬P ∧ Q ∧ R) ∨(¬P ∧ ¬Q ∧ R)
P Q R H
T T T T L1
T T F F L2
T F T F L3
T F F F L4
F T T T L5
F T F F L6
F F T T L7
F F F F L8
Exemplo - fnc
 H=(P→Q) ∧ R
 Linhas em que H=F
P Q R H
T T F F L2
T F T F L3
T F F F L4
F T F F L6
F F F F L8
 L2= ¬ P ∨ ¬ Q ∨ R
 L3=¬P ∨ Q ∨ ¬ R
 ...
 H=L2 ∧ L3 ∧ L4 ∧ L6 ∧ L8, FNC
 H=(¬P ∨ ¬Q ∨ R) ∧ (¬P ∨ Q ∨ ¬R) ∧ (¬P ∨ Q ∨ R) ∧(P ∨ ¬Q ∨ R) ∧ (P 
∨ Q ∨ R)
P Q R H
T T T T L1
T T F F L2
T F T F L3
T F F F L4
F T T T L5
F T F F L6
F F T T L7
F F F F L8
Exercícios
Obter FND e FNC de ¬(P ∧Q) →R
As fórmulas H e G são equivalentes?
H = (P↔Q)∨(R → S)
G = ¬(¬(¬P∨Q) ∨ ¬(¬Q ∨ P)) ∨(¬ R∨S)
	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