Cap3 (Propriedades Semânticas - LP)

Prévia do material em texto

Capítulo 3 
 
Propriedades semânticas da 
Lógica Proposicional 
Propriedades semânticas básicas 
Uma fórmula H é uma tautologia (ou é 
válida) se e somente se para toda 
interpretação I, I[H]=T 
 
H é factível ou satisfazível se e somente se 
existe uma interpretação I tal que I[H]=T 
 
H é contraditória se e somente se para toda 
interpretação I, I[H]=F 
Propriedades semânticas básicas 
Dadas 2 fórmulas H e G,HG se e 
somente se para toda interpretação I, 
se I[H]=T então I[G]=T 
Dadas H e G,HG se e somente se 
para toda interpretação I, I[H]=I[G] 
Dados H e uma interpretação I, I 
satisfaz H se e somente se I[H]=T 
Propriedades semânticas básicas 
Um conjunto de fórmulas 
b={H1,H2,...Hn} é satisfazível se e 
somente se existe uma interpretação I 
tal que I[H1]= I[H2]= ... = I[Hn]= T 
I satisfaz o conjunto de fórmulas b, ou 
I[b]=T 
Toda I satisfaz o conjunto de fórmulas 
vazio 
Exemplo de Tautologia 
A fórmula H=PvP é uma tautologia, 
pois toda I[H]=T 
I[H]=T I[PvP]=T 
  I[P]=T e/ou I[P]=T 
  I[P]=T e/ou I[P]=F 
( aqui quer dizer “o mesmo que, equivale a”) 
Como I é uma função binária com imagem 
{T,F}, então I[P]=T e/ou I[P]=F é verdade e 
I[H]=T. 
Exemplo de Satisfatibilidade 
A fórmula H=(PvQ) é satisfazível, pois há 
interpretações que a interpretam como 
verdadeira. 
H é tautologia? Por quê? 
Exemplo de Contradição 
A fórmula H=(P^P) é contraditória 
Suponham (por absurdo) que exista I[H]=T 
 
I[H]=T  I[P^P]=T 
  I[P]=T e I[P]=T 
  I[P]=T e I[P]=F 
 
Como I é uma função binária, ocorre apenas um 
dos valores, i.e. I[P]=T ou I[P]=F. Então 
I[P]=T e I[P]=F é falsa, e portanto I[H]=T também 
é falsa. 
Implicação 
Se E=((P^Q)VQ), H=(P^Q) e G=(PQ) 
E G? 
E H? 
H G? 
H E? 
G H? 
 
Equivalência 
Exemplo (Lei de Morgan) 
H=(P^Q) e G=(PvQ) 
 
Temos que demonstrar que, para toda 
interpretação I, I[H]=I[G] 
 
Casos I[H]=T e I[H]=F 
(P^Q)  (PvQ) ? 
Caso I[H]=T 
I[H]=T 
 I[P^Q]=T 
 I[P]=T e I[Q]=T 
 I[P]=F e I[Q]=F 
 I[PvQ]=F 
 I[(PvQ)]=T 
 I[G]=T 
 I[H]=T 
 I[H]=I[G] 
Exemplos de Satisfatibilidade e 
Insatisfatibilidade 
Qual(is) conjunto(s) são 
(in)satisfazíveis: 
H1=P, H2=P e H3=Q 
E=(P  Q), H=(Q  R) e G=(R  P) 
Relações entre as Propriedades 
Semânticas 
Validade e factibilidade 
H é válida  H é contraditória 
H é válida  H é satisfazível 
H não é satisfazível  H é 
contraditória 
 
 
Relações entre as Propriedades 
Semânticas 
Dadas 2 fórmulas H e G, 
H implica G  (H  G) é tautologia 
H equivale a G  (H  G) é tautologia 
Provar que (H  G) e (G  H) 
Transitividade da equivalência 
E  H e H  G a E  G 
Relações entre as Propriedades 
Semânticas 
Satisfabilidade e factibilidade 
Seja {H1,H2,...Hn} um conjunto de 
fórmulas 
{H1,H2,...Hn} é satisfatível  
{H1^H2^...^Hn} é satisfatível 
Equivalências 
 aqui quer dizer “o mesmo que, equivale 
a” e  quer dizer “se … então …” 
Cuidado: Há uma diferença entre eles: 
H equivale a G  
{H é tautologia  G é tautologia}? (1) 
H equivale a G  
{H é tautologia  G é tautologia}? (2) 
Equivalência e Validade 
H equivale a G  
{H é tautologia  G é tautologia} (1) 
é dividida em 2 implicações: 
H equivale a G  
{H é tautologia  G é tautologia} (2) 
e 
{H é tautologia  G é tautologia}  
H equivale a G (3) 
Contra-exemplo de Equivalência 
e Validade 
{H é tautologia  G é tautologia}  
 H equivale a G (3) 
H=P e G=Q, que não são equivalentes 
– “H equivale a G” é falsa 
No entanto, o antecedente é verdadeiro 
– H e G não são tautologias 
(Falso  Falso)  Falso 
Verdadeiro  Falso, o que é falso 
Proposição 
Proposição 1 (equivalência e validade) 
Sejam H e G duas fórmulas então H 
equivale a G {H é tautologia  G é 
tautologia} 
 
Proposição 2 (implicação e validade) Sejam 
H e G duas fórmulas então H implica G 
{H é tautologia  G é tautologia} 
 
Proposição 
Lema (implicação) Sejam A, B e C, então (A 
 (B  C)) equivale a ((A  B)  C) 
 
Proposição 3 (implicação e validade) Sejam 
H e G duas fórmulas, então {{H implica G} e 
{H é tautologia}}  {G é tautologia}