Documento_8

Prévia do material em texto

Lista de exercícios 
3. Achar a tabela-verdade de cada uma das proposições: 
 (a) ∼ p ∧ q. 
p q ∼ p ∧ q 
V V F 
V F F 
F V V 
F F F 
 
 (d) ∼ (p ∧ q) ∨ ∼ (p ↔ q). 
p q p ∧ q ∼ (p ∧ q) (p ↔ q) ∼ (p ↔ q). ∼ (p ∧ q) ∨ ∼ (p ↔ q). 
V V V F V F F 
V F F V F V V 
F V F V F V V 
F F F V V F V 
 
 (f) p ↔ (q → r). 
p q r (q → 
r) 
p ↔ (q → r) 
V V V V V 
V V F F F 
V F V V V 
V F F V V 
F V V V F 
F V F F V 
F F V V F 
F F F V F 
 
 (h) [p ∧ (q ∨ r)] ∧ [q ∧ (p ∨ r)]. 
p q r (q ∨ r) [p ∧ (q ∨ r)] (p ∨ r) [q ∧ (p ∨ r)] [p ∧ (q ∨ r)] ∧ [q ∧ (p ∨ r)] 
V V V V V V V V 
V V F V V V V V 
V F V V V V F F 
V F F F F V F F 
F V V V F V V F 
F V F V F F F F 
F F V V F V F F 
F F F F F F F F 
 
 
 
 
 
5. Suponha que se defina um novo conector, denotado por ∗, tal que p ∗ q é verdadequando q é 
verdade e p é falso e é falso em todos os outros casos. Construa astabelas verdade para: 
(a) p ∗ q. 
p q p ∗ q 
V V F 
V F F 
F V V 
F F F 
(b) q ∗ p. 
P q q ∗ p 
V V F 
V F F 
F V V 
F F F 
 
(c) (p ∗ q) ∗ p. 
p q (p ∗ q) (p ∗ q) ∗ p 
V V F V 
V F F V 
F V V F 
F F F F 
 
8. Simplifique as proposiçõoes abaixo, utilizando expressões equivalentes, sem alterar ovalor 
verdade da expressão: 
(a) p ∨ (q∧ ∼ p). 
(q∧ ∼ p) ≡ F 
p ∨ F 
(c) ∼ (∼ p∧ ∼ q). (p V q). 
 
(d) (p ∧ r) ∨ [∼ r ∧ (p ∨ q)]. 
 ( p & r ) | ( !r & ( p | q )) 
Distributiva: ( ~r ^ ( p V q )) == (( ~r ^ p ) V ( ~r ^q )) 
Associativa: ( p ^ r ) V (( ~r ^ p ) V ( ~r ^ q )) == 
(( p ^ r ) V ( ~r ^p )) V ( ~r ^ q ) 
Distributiva: ( p ^ r ) V ( ~r ^ p ) == p V( r ^ ~r) 
Complementar: r ^~r == false 
de Identidade: ( p ^false) V( ~r ^ q ) == false | ( ~r ^q ) 
de Identidade: false V ( ~r ^ q ) == ~r ^ q 
Final: ( p ^ r ) V ( ~r ^ ( p Vq )) == ~r ^ q 
 
9. Verificar se ∼ (a ↔∼ b) implica tautologicamente as seguintes formas abaixo: 
(b) ∼ a ↔∼ b ∧ a 
p q (~p) (~q) ((~q)^p) ((~p)↔((~q)
^p)) 
F F V V F F 
F V V F F F 
V F F V V F 
V V F F F V 
 
 
(d) ∼ a∧ ∼ b∨ ∼ a →∼ a ↔∼ b 
(((((~p)^(~q))v(~p))→(~p))↔(~q)) 
 
V 
F 
V 
F 
 
 
 
11. Prove que a operação de disjunção inclusiva pode ser escrita em termos das operações de 
conjunção e negação. 
Utilizando a lei de Morgan 
∼ (p ∨ q) ≡∼ p∧ ∼ q 
12. Prove que a operação condicional se distribui na operação de conjunção 
Equivalência de implicação 
p → q ≡∼ p ∨ q 
13. Prove que a operação de disjunção exclusiva pode ser escrita em termos dos três operadores 
básicos ∧, ∨ e ∼. 
p Y q ≡ (∼ p ∧ q) ∨ (p∧ ∼ q) 
14. O sinal proposicional ↓ é chamado de negação conjunta: p ↓ q lê-se “Nem p nem q”. Pede-se: 
(a) Construir uma tabela verdade para p ↓ q 
(b) Provar que os três operadores básicos ∧, ∨ e ∼ podem ser expressos em termos do sinal ↓ da 
seguinte maneira: 
i. ∼ p ≡ p ↓ p 
 ii. p ∧ q ≡ (p ↓ p) ↓ (q ↓ q) 
 iii. p ∨ q ≡ (p ↓ q) ↓ (p ↓ q) 
15. Determinar se cada um dos conjuntos abaixo ´e um conjunto completo de conectivos: 
 {∼, ∨, ∧}, {∼, ∧}, {∼, ∨}, {∼, →}, {V, →} 
{∼, ∨, ∧} é completo pois é possível expressar equivalentemente todos os conectivos {∧, ∨, →, ↔} 
usando somente {∼, ∨, ∧}: P ∨ Q: ~ (~ P ∧ ~Q) 
 P → Q: ~(P ∧ ~ Q) 
 P ↔ Q: (~(P ∧~Q)) ∧ (~ Q ∧ ~ P)) 
 P ∧ Q: ~ (~ P ∨ ~ Q) 
 
 
{~, ∧} é completo pois é possível expressar equivalentemente todos os conectivos {∨, →, ↔} usando 
somente {~, ∧}. P ∨ Q: ~ (~ P ∧ ~Q) 
 P → Q: ~(P ∧ ~ Q) 
 P ↔ Q: (~(P ∧~Q)) ∧ (~ Q ∧ ~ P)) 
{~, v} é completo pois é possível expressar equivalentemente os conectivos {∧, →, ↔} usando 
somente {~ ∧}. P ∧ Q: ~ (~ P ∨ ~ Q) 
 P → Q: ~ P ∨ Q 
 P ↔ Q: ~(~(~ P ∨ Q) ∨ ~( ~ Q ∨ P)) 
{~, →} é completo pois é possível expressar equivalentemente todos os conectivos {∧, ∨, ↔} usando 
somente {~, →}. P ∧ Q: ~ (~ P ∨ ~Q) 
 P ∨ Q: ~ P → Q 
 P ↔ Q: (P → Q) ∧ (Q → P) 
{V, →} não é completo pois não é possível expressar equivalentemente todos os conectivos {~, ∧, 
↔} usando somente {V, →}. 
 
16. Determinar as formas normais disjuntivas e conjuntivas associadas as seguintes fórmulas: 
(a) (p → q) ↔ (r ∧ p) 
(p ∧ q ∧ r) ∨ (p ∧ ~q ∧ ~r) disjuntiva 
 (~p ∨ ~q ∨ r) ∧ (~p ∨ q ∨ ~r) ∧ (p ∨ ~q ∨ ~r) ∧ (p ∨ ~q ∨ r) ∧ (p ∨ q ∨ ~r) ∧ (p ∨ q ∨ r) conjuntiva 
(b) (p ↔ q) → (p ∨ q) 
(p ∧ q ∧ r) ∨ (p ∧ q ∧ ~r) ∨ (p ∧ ~q ∧ r) ∨ (p ∧ ~q ∧ ~r) disjuntiva 
(p ∨ q ∨ r) ∧ (p ∨ q ∨ ~r) ∧ (p ∨ ~q ∨ r) ∧ (p ∨ ~q ∨ ~r)