Aula 3 - Propriedades Semânticas

Prévia do material em texto

Prof. Ricardo Mesquita 
Propriedades Semânticas da 
Lógica Proposicional 
Propriedades Semânticas 
1. Seja H uma fórmulas da Lógica proposicional. H é uma 
tautologia se e somente se, para toda interpretação I, 
I[H] = V. 
 
Exemplo: 
 Verifique que as fórmulas: 
 H = (P  P) e G = (P  Q)  (P  Q) são tautologias. 
02/19 
Resolução 
P P P  P 
V F V 
F V V 
P Q P  Q P  Q (P  Q)  (P  Q) 
V V V V V 
V F F F V 
F V F F V 
F F F V V 
Todas as interpretações 
são verdadeiras. 
Logo, são tautologias! 
03/19 
Propriedades Semânticas 
2. Dada uma interpretação I, I satisfaz H, se I[H] = V. 
3. H é satisfatível se e somente se existe uma interpretação 
I que satisfaz H. 
4. H é uma contingência se e somente se existem duas 
interpretações I1 e I2, tais que I1[H] = V e I2[H] = F 
 
Exemplo: 
Construa a tabela-verdade para a fórmula H = (P  Q)  P 
e verifique que H é satisfatível. Observe também que H é uma 
contingência. 
04/19 
Resolução 
 
 
 
 
 
 A fórmula H é satisfatível: note a Interpretação 2, na qual 
I[P] = V e I[Q] = F, temos que I[H] = V. 
 Note que a fórmula H também é uma contingência: existem 
interpretações verdadeiras (linha 2) e falsas (as demais 
linhas!) 
P Q Q P  Q (P  Q)  P 
V V F F F 
V F V V V 
F V F V F 
F F V V F 
05/19 
Propriedades Semânticas 
5. H é contraditória se e somente se para toda 
interpretação I, I[H] = F. 
 
Exemplo: 
Verifique que 
 H = (P  P) 
 G = (P  Q)  (P  Q) 
são contradições. 
06/19 
Resolução 
P P P  P 
V F F 
F V F 
P Q P  Q P  Q (P  Q) (P  Q)  (P  Q) 
V V V V F F 
V F F V F F 
F V F V F F 
F F F F V F 
Todas as interpretações 
são falsas. Logo, são 
contradições! 
07/19 
Propriedades Semânticas 
6. H implica semanticamente em G (ou G é consequência 
lógica semântica de H) se e somente se para toda 
interpretação I, sempre que I[H] = V, tem-se que I[G] = V. 
 
 Escreve-se: H╞ G. 
 
 Considere as fórmulas: 
 
E = ((P  Q)  Q) 
H = (P  Q) 
G = (P  Q) 
 
Verifique que E╞ G, H╞ G, H╞ E, mas que não é verdade que 
G╞ E, G╞ H e E╞ H. 
 08/19 
Resolução 
P Q P  Q P  Q (P  Q)  Q 
V V V V V 
V F F F F 
F V F V V 
F F F V F 
H G E 
Note que: 
• Sempre que I[E] = V, temos que I[G] = V, logo E╞ G 
• Sempre que I[H] = V, temos que I[G] = V, logo H╞ G 
• Sempre que I[H] = V, temos que I[E] = V, logo H╞ E 
Mas, 
• Existe situação onde I[G] = V, mas que I[E] = F, logo G╞ E 
• Existe situação onde I[G] = V, mas que I[H] = F, logo G╞ H 
• Existe situação onde I[E] = V, mas que I[H] = F, logo E╞ H 09/19 
Propriedades Semânticas 
7. H equivale semanticamente a G se e somente se, para 
toda interpretação I, I[H] = I[G]. 
 
Exemplo: (Lei de De Morgan) 
Mostre que as fórmulas 
 
H = (P  Q) 
G = (P  Q) 
 
São equivalentes. 
 
 10/19 
Resolução 
P Q P  Q (P  Q) P Q P  Q 
V V V F F F F 
V F V F F V F 
F V V F V F F 
F F F V V V V 
Note que todas as 
interpretações são iguais! 
Logo, as fórmulas indicadas 
são semanticamente 
equivalentes. 
11/19 
Propriedades Semânticas 
Observação: 
 
Duas fórmulas H e G são equivalentes semanticamente se e 
somente se H  G é uma tautologia. 
 
Exemplo: 
Mostre que H = (P  Q) é equivalente a G = (P  Q). 
12/19 
Resolução 
P Q P  Q P P  Q (P  Q)  (P  Q) 
V V V F V V 
V F F F F V 
F V V V V V 
F F V V V V 
H G 
Note que a bi-implicação entre H e G 
é uma tautologia. Logo, H e G são 
semanticamente equivalentes! 
13/19 
Propriedades Semânticas 
8. O conjunto  = {H1, H2, ..., Hn} é satisfatível se e 
somente se existe uma interpretação I, tal que 
 
 I[H1] = V, I[H2] = V, ..., I[Hn] = V 
 
 ou seja, I satisfaz o conjunto de fórmulas. 
 
Observação: se um dado conjunto de fórmulas é vazio, então 
toda interpretação I satisfaz esse conjunto. 
14/19 
Propriedades Semânticas 
Exemplo: 
Verifique a satisfatibilidade dos seguintes conjunto de fórmulas: 
 
1 = {(P  Q), (Q  R), (R  P)} 
 
2 = {(P  Q), (Q  R), (R  S), (S  P), (S  Q)} 
 
15/19 
Resolução 
Para um conjunto de fórmulas ser satisfatível, basta apresentar uma 
interpretação na qual todas as fórmulas do conjunto são 
interpretadas como verdadeiras simultaneamente. O primeiro 
conjunto é simples: 
 
1 = {(P  Q), (Q  R), (R  P)} 
 
Se tomarmos I[P] = I[Q] = I[R] = V, teremos I[P  Q] = V, 
I[Q  R] = V e I[R  P] = V, o que mostra que o conjunto é 
satisfatível. 
 
 
16/19 
Resolução 
 Já o segundo conjunto, 
 
 2 = {(P  Q), (Q  R), (R  S), (S  P), (S  Q)} 
 
Para que I[(S  Q)] = V, teremos, necessariamente, que I[(S  Q)] = F; mas, 
para isso, teremos que ter, I[S] = V e I[Q] = F. Note que, como I[Q] = F e 
queremos que I[P  Q] = V, necessariamente, teremos que ter I[P] = F; mas se 
I[P] = F e I[S] = V, teremos que I[S  P] = F. 
 
Logo, o conjunto é insatisfatível! 
17/19 
Propriedades Semânticas 
9. O conjunto  = {H1, H2, ..., Hn} implica 
semanticamente numa fórmula H, se para todo I, se I[] = 
V, então I[H] = V. (H é uma consequência lógica semântica de 
). 
Notação: 
 Consequência lógica semântica: 
 
 ╞ H 
 
 No caso em que  é vazio, escrevemos╞ H. 
 H ser consequência lógica do vazio, significa que H é uma tautologia. 
18/19 
Exercícios 
1. Determine se as proposições a seguir são tautologias, 
contradições ou contingências: 
a. P  ((P  Q)  R) 
b. (P  Q)  (P  Q) 
c. ((P  Q)  P)  (Q  P) 
 
2. Determine se os conjuntos de fórmulas a seguir são 
satisfatíveis: 
a. {S  Q, P  (S  P), S} 
b. {(Q  P), P  R, Q  R} 
c. {(Q  R)  P, Q  (P R), P  R} 
19/19