Forma Normal De Sentenças (Solução) - Monteiro

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

1
Anexo 
 
Solução dos Exercícios do Capítulo-8 (Forma Normal) 
 
8.15.1 Indicar se as expressões abaixo estão na Forma Normal Conjuntiva 
(FNC) ou na Forma Normal Disjuntiva (FND) 
a) p ∨ (q ∧ r) � Não está na FNC 
b) (q ∧ r) ∨ (q ∨ r) � Está na FND 
c) ¬q ∨ p � Está na FND 
d) (¬p ∨ q) ∧ (¬q ∨ ¬r) � Está na FNC 
e) (¬p ∧ q) ∨ (¬q ∧ ¬r) � Está na FND 
 
8.15.2 Determinar a FNC da proposição: 
(p → q) ↔ (¬q → ¬p) 
 
Solução 
(¬p ∨ q) ↔ (¬¬q ∨ ¬p) 
(¬p ∨ q) ↔ (q ∨ ¬p) 
[¬(¬p ∨ q) ∨ (q ∨ ¬p)] ∧ [(¬p ∨ q) ∨ ¬(q ∨ ¬p)] 
[(¬¬p ∧¬ q) ∨ (q ∨ ¬p)] ∧ [(¬p ∨ q) ∨ (¬q ∧ ¬ ¬p)] 
[(p ∧ ¬q) ∨ (q ∨ ¬p)] ∧ [(¬p ∨ q) ∨ (¬q ∧ p)] 
[(p ∨ q ∨ ¬p) ∧ (¬ q ∨ q ∨ ¬p)] ∧ [(¬p ∨ q ∨ ¬q) ∧ 
(¬p ∨ q ∨ p)] 
(p ∨ q ∨ ¬p) ∧ (¬ q ∨ q ∨ ¬p) ∧ (¬p ∨ q ∨ ¬q) ∧ (¬p ∨ q ∨ p) � é 
tautológica 
 
8.15.3 Determinar a FNDC ou a FNCC das seguintes proposições: 
a) (p → r) ∧ ¬q 
Solução: 
(p → r) ∧ ¬q ≡ (¬p ∨ r) ∧ ¬q ≡ distributividade ≡ (¬p ∧ ¬q) ∨ (r ∧ ¬q) 
Agregando um termo sempre verdadeiro (V) a cada parcela: 
(¬p ∧ ¬q ∧∧∧∧ V) ∨ (r ∧ ¬q ∧∧∧∧ V) 
Substituindo o símbolo verdadeiro pela disjunção da letra sentencial que 
falta ao termo e sua negação: (¬p ∧ ¬q ∧∧∧∧ (r ∨∨∨∨ ¬¬¬¬r)) ∨ (r ∧ ¬q ∧∧∧∧ (p ∨∨∨∨ ¬¬¬¬p)) 
Fazendo a distributividade: 
(¬p ∧ ¬q ∧ r) ∨∨∨∨ (¬p ∧ ¬q ∧ ¬r) ∨∨∨∨ (r ∧ ¬q ∧ p) ∨∨∨∨ (r ∧ ¬q ∧ ¬p) � FNDC 
 
b) p ↔ (q ∨ ¬r) 
Solução: 
p ↔ (q ∨ ¬r) ≡ [p → (q ∨ ¬r)] ∧ [(q ∨ ¬r) → p] ≡ 
≡ [¬p ∨ (q ∨ ¬r)] ∧ [¬(q ∨ ¬r) ∨ p] ≡ (¬p ∨ q ∨ ¬r) ∧ [(¬q ∧ ¬¬r) ∨ p] ≡ 
≡ (¬p ∨ q ∨ ¬r) ∧ [(¬q ∧ r) ∨ p] ≡ distributividade ≡ 
≡ (¬p ∨ q ∨ ¬r) ∧ [(¬q ∨ p) ∧ (r ∨ p)] 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 2
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Agregando um termo falso (F) a cada parcela: 
≡ (¬p ∨ q ∨ ¬r) ∧ (¬q ∨ p ∨∨∨∨ F) ∧ (r ∨ p ∨∨∨∨ F) 
Substituindo o símbolo falso pela conjunção da letra sentencial que falta ao 
termo e sua negação: 
≡ (¬p ∨ q ∨ ¬r) ∧ (¬q ∨ p ∨∨∨∨ (r ∧∧∧∧ ¬¬¬¬r)) ∧ (r ∨ p ∨∨∨∨ (q ∧∧∧∧ ¬¬¬¬q)) 
Fazendo a distributividade: 
≡ (¬p ∨ q ∨ ¬r) ∧ (¬q ∨ p ∨∨∨∨ (r ∧∧∧∧ ¬¬¬¬r)) ∧ (r ∨ p ∨∨∨∨ (q ∧∧∧∧ ¬¬¬¬q)) 
≡ (¬p ∨ q ∨ ¬r) ∧∧∧∧ (¬q ∨ p ∨ r) ∧∧∧∧ (¬q ∨ p ∨ ¬r) ∧∧∧∧ (r ∨ p ∨ q) ∧∧∧∧ (r ∨ p ∨ ¬q) 
� FNCC 
 
8.15.4 Determine a FNDC da proposição abaixo usando o método de POST 
p ∧ q → q 
 
Solução: 
p ∧ q → q ≡ ¬(p ∧ q) ∨ q ≡ De Morgan ≡ ¬p ∨ ¬q ∨ q ≡ ¬p ∨ T ≡ T 
Tautologia � só tem FNDC 
 
p q p ∧∧∧∧ q p ∧∧∧∧ q →→→→ q 
V V V V 
V F F V 
F V F V 
F F F V 
 
Todas as linhas possuem V na coluna (p ∧ q → q) 
Conjunções correspondentes a cada linha: 
(p ∧ q), (p ∧ ¬q), (¬p ∧ q), (¬p ∧ ¬q) 
Fazendo a disjunção de cada conjunção: 
(p ∧ q) ∨ (p ∧ ¬q) ∨ (¬p ∧ q) ∨ (¬p ∧ ¬q) 
 
8.15.5 Escreva a negação das seguintes proposições: 
a) A resposta é 5 ou 7. 
b) a ≤ 5. 
c) Se 8 é par, então 5 é ímpar. 
d) Se 2 é primo e 5 é ímpar, então 3 é ímpar. 
e) Se 9 é primo, então 2 < 4. 
f) 3 é primo se, e somente se, 8 é par. 
g) 2 > 5 e 3 é par. 
h) 3 ≥ 8 ou 2 é primo. 
Solução: 
a) A resposta é 5 ou 7. 
p = A resposta é 5 H = p ∨ q 
q = A resposta é 7 
Negando: ¬H = ¬ (p ∨ q) � De Morgan: ¬H = ¬ p ∧ ¬q 
� A resposta não é 5 e não é 7 
 3
b) a ≤ 5. � a > 5 
c) Se 8 é par, então 5 é ímpar. 
p = 8 é par Se p então q � H: p → q 
q = 5 é ímpar 
Negando: ¬H = ¬ (p → q) = ¬(¬ p ∨ q) � De Morgan: ¬H =¬¬ p ∧ ¬ q 
:¬H = p ∧ ¬ q �8 é par e 5 não é ímpar 
 
d) Se 2 é primo e 5 é ímpar, então 3 é ímpar. 
p = 2 é primo 
q = 5 é ímpar H: (p ∧ q) → r 
r = 3 é ímpar 
Negando: ¬H = ¬ ((p ∧ q) → r) = ¬(¬(p ∧ q) ∨ r) � De Morgan: 
¬H =¬¬( p ∧ q) ∧ ¬r � ¬H = ( p ∧ q) ∧ ¬r 
� 2 é primo e 5 é ímpar e 3 não é ímpar 
 
e) Se 9 é primo, então 2 < 4. 
p = 9 é primo Se p então q � H: p → q 
q = 2 < 4 
Negando: ¬H = ¬ (p → q) = ¬(¬ p ∨ q) � De Morgan: ¬H =¬¬ p ∧ ¬ q 
¬H = p ∧ ¬ q �9 é primo e 2 ≥ 4 
 
f) 3 é primo se, e somente se, 8 é par. 
p = 3 é primo H: p ↔ q 
q = 8 é par 
Negando: ¬H = ¬ (p ↔ q) = ¬ ((p → q) ∧ (q → p)) � De Morgan: 
¬H = ¬ (p → q) ∨ ¬(q → p) = ¬ (¬p ∨ q) ∨ ¬(¬q ∨ p) = 
= (¬¬p ∧ ¬q) ∨ (¬¬q ∧ ¬p) = (p ∧ ¬q) ∨ (q ∧ ¬p) 
� 3 é primo e 8 não é par ou 8 é par e 3 não é primo 
 
g) 2 > 5 e 3 é par. 
p = 2 > 5 H: p ∧ q 
q = 3 é par 
Negando: ¬H = ¬ (p ∧ q) � De Morgan: ¬H = ¬p ∨ ¬q 
� 2 ≤ 5 ou 3 não é par (não é par = ímpar) 
 
h) 3 ≥ 8 ou 2 é primo. 
p = 3 ≥ 8 H: p ∨ q 
q = 2 é primo 
Negando: ¬H = ¬ (p ∨ q) � De Morgan: ¬H =¬p ∨ ¬q 
� 3<8 e 2 não é primo