Lógica Matemática_Atividade_Semana4

Prévia do material em texto

Curso: ​Ciência de Computação 
Atividade: ​Semana 4​ Período: ​1º 
Disciplina: ​Lógica Matemática 
RESPOSTAS NAS PÁGINAS 2, 3 E 4 
1. (2 Pontos) ​Simplifique as proposições, indicando em cada caso as propriedades 
utilizadas: 
a) ¬ (¬p∨¬q) 
b) p(p )⋁ q ⋀ ¬ 
c) (p→q) ⋀ (¬p→q) 
d) p ⋀ (p )→ q ⋀ (p→¬q) 
2. (2 Pontos) Use o método dedutivo para demonstrar as seguintes implicações e 
equivalências, indicando em cada caso as propriedades utilizadas: 
a) p → p ⋀ q ⇔ p → q 
b) (p )→ r ⋁ (q )→ r ⇔ p ⋀ q → r 
c) ⇔p(p )→ q → q ⋁ q 
d) p⇒qp ⋀ ¬ 
3. (2 Pontos)​ Responda as seguintes perguntas: 
a) Defina o que é um conjunto completo de operadores lógicos; 
b) De um exemplo de conjuntos completos com três, dois e um operador; 
c) Qualquer expressão lógica pode ser sempre representada nas formas normais 
disjuntiva e conjuntiva?. Explique. 
d) Toda equivalência corresponde a duas implicações? Explique. 
 
4. (2 Pontos) ​Determine uma forma normal conjuntiva FNC equivalente para cada uma 
das seguintes proposições, indicando em cada caso, as propriedades utilizadas: 
a) p → q 
b) (p↔¬p) 
c) q(¬p∧q) ⋁ 
d) (p p)⋀ ¬ ↓ (q q)⋀ ¬ 
5. (2 Pontos) ​Determine uma forma normal disjuntiva FND equivalente para cada uma 
das seguintes proposições, indicando em cada caso, as propriedades utilizadas: 
a) p(p )→ q ⋀ ¬ 
b) (p↑q) 
c) q(¬p∧q) ⋁ 
d) (p p)⋀ ¬ ↓ (q q)⋀ ¬ 
RESPOSTAS 
1-a) (De Morgan)¬¬p ¬q)¬ (¬p∨¬q)⇔ ( ⋀ ¬ 
 (Dupla Negação)p )¬ (¬p∨¬q)⇔ ( ⋀ q 
b)​ (Distributiva)p p p) q p)(p )⋁ q ⋀ ¬ ⇔ ( ⋀ ¬ ⋁ ( ⋀ ¬ 
 (Def. da conjunção)p q p)(p )⋁ q ⋀ ¬ ⇔ C ⋁ ( ⋀ ¬ 
 (Identidade)p q p)(p )⋁ q ⋀ ¬ ⇔ ( ⋀ ¬ 
 
c)​ (Equivalência da condicional)(p→q) ⋀ (¬p→q)⇔ (¬p )⋁ q ⋀ (¬¬p )⋁ q 
 (Dupla negação)(p→q) ⋀ (¬p→q)⇔ (¬p )⋁ q ⋀ (p )⋁ q 
 (Dupla negação)¬ ¬(p→q) ⋀ (¬p→q)⇔ ¬ (¬p )⋁ q ⋀ ¬ (p )⋁ q 
 (De Morgan)(p→q) ⋀ (¬p→q)⇔ ¬ (¬¬p q)⋀ ¬ ⋀ ¬ (¬p q)⋀ ¬ 
 (Associativa e comutativa)(p→q) ⋀ (¬p→q)⇔ ¬ (¬¬p p)⋀ ¬ ⋀ ¬ (¬q q)⋀ ¬ 
 (De Morgan)(p→q) ⋀ (¬p→q)⇔ (¬¬¬p ¬p)⋁ ¬ ⋀ (¬¬q ¬q)⋁ ¬ 
 (Dupla negação)(p→q) ⋀ (¬p→q)⇔ (¬p )⋁ p ⋀ (q )⋁ q 
 (Idempotência)(p→q) ⋀ (¬p→q)⇔ (¬p )⋁ p ⋀ q 
 (Def. da conjunção)(p→q) ⋀ (¬p→q)⇔ T ⋀ q 
 (Identidade)(p→q) ⋀ (¬p→q)⇔ T 
 
d)​ (Equivalência da condicional)p ⋀ (p )→ q ⋀ (p→¬q)⇔ p ⋀ (¬p )⋁ q ⋀ (¬p q)⋁ ¬ 
 (Distributiva)p p)p ⋀ (p )→ q ⋀ (p→¬q)⇔ ( ⋀ ¬ ⋁ (p )⋀ q ⋀ (¬p q)⋁ ¬ 
 (Def. da conjunção) p ⋀ (p )→ q ⋀ (p→¬q)⇔ C ⋁ (p )⋀ q ⋀ (¬p q)⋁ ¬ 
 (Identidade) p ⋀ (p )→ q ⋀ (p→¬q)⇔ (p )⋀ q ⋀ (¬p q)⋁ ¬ 
 (De Morgan) p ⋀ (p )→ q ⋀ (p→¬q)⇔ (p )⋀ q ⋀ ¬ (p )⋀ q 
 (Associativa e comutativa) p ⋀ (p )→ q ⋀ (p→¬q)⇔ (p )⋀ p ⋀ ¬ (q )⋀ q 
 (Idempotência) qp ⋀ (p )→ q ⋀ (p→¬q)⇔ p ⋀ ¬ 
2-a) p → p ⋀ q ⇔ p → q 
 (Equivalência da condicional)p p )p → p ⋀ q ⇔ ¬ ⋁ ( ⋀ q 
 (Distributiva)¬p ) ¬p )p → p ⋀ q ⇔ ( ⋁ p ⋀ ( ⋁ q 
 (Def. da conjunção)¬p )p → p ⋀ q ⇔ T ⋀ ( ⋁ q 
 (Identidade)¬p )p → p ⋀ q ⇔ ( ⋁ q 
 (Equivalência da condicional)p → p ⋀ q ⇔ p → q 
 
b)​ (p )→ r ⋁ (q )→ r ⇔ p ⋀ q → r 
 (Equivalência da condicional)(p )→ r ⋁ (q )→ r ⇔ (¬p )⋁ r ⋁ (¬q )⋁ r 
 (Associativa e comutativa)(p )→ r ⋁ (q )→ r ⇔ (¬p q)⋁ ¬ ⋁ (r )⋁ r 
 (De Morgan)(p )→ r ⋁ (q )→ r ⇔ ¬ (p )⋀ q ⋁ (r )⋁ r 
 (Idempotência)(p )→ r ⋁ (q )→ r ⇔ ¬ (p )⋀ q ⋁ r 
 (Equivalência da condicional)(p )→ r ⋁ (q )→ r ⇔ p ⋀ q → r 
 
c)​ ⇔p(p )→ q → q ⋁ q 
 (Equivalência da condicional)⇔(¬ )(p )→ q → q (¬p )⋁ q ⋁ q 
 (De Morgan)⇔((¬¬p q) )(p )→ q → q ⋀ ¬ ⋁ q 
 (Dupla Negação)⇔((p q) )(p )→ q → q ⋀ ¬ ⋁ q 
 (Distributiva)⇔ ¬q )(p )→ q → q (p )⋁ q ⋀ ( ⋁ q 
 (Def. da Disjunção)⇔(p )→ q → q (p )⋁ q ⋀ T 
 (Identidade)⇔p(p )→ q → q ⋁ q 
 
d)​ p⇒qp ⋀ ¬ 
 (Equivalência da condicional)p (p p)p ⋀ ¬ → q ⇔ ¬ ⋀ ¬ ⋁ q 
 (De Morgan)p ¬p ¬p)p ⋀ ¬ → q ⇔ ( ⋁ ¬ ⋁ q 
 (Dupla negação)p ¬p )p ⋀ ¬ → q ⇔ ( ⋁ p ⋁ q 
 (Def. da disjunção)pp ⋀ ¬ → q ⇔ T ⋁ q 
 (Def. da disjunção)pp ⋀ ¬ → q ⇔ T 
3-a) Um conjunto completo de operadores lógicos é aquele que consegue reproduzir as 
cinco operações básicas: negação, conjunção, disjunção, condicional e bicondicional. 
b) ​Exemplo de um conjunto completo com três operadores: Com dois , ,¬ ⋀ ⋁ . 
operadores: Com um operador: ¬ → . ↑ . 
c) ​Sim, já que essas formas utilizam o conjunto e podem ser obtidas através de , ,¬ ⋀ ⋁ 
tabela-verdade. 
d) ​Sim, toda equivalência corresponde a uma bicondicional tautológica que pode ser 
decomposta em duas condicionais. 
4-a) (Equivalência da condicional)pp → q ⇔ ¬ ⋁ q 
b)​ (Equivalência da bicondicional)p p) p p) ¬p )( ↔ ¬ ⇔ ( → ¬ ⋀ ( → p 
 (Equivalência da condicional)p p) ¬p p) ¬¬p )( ↔ ¬ ⇔ ( ⋁ ¬ ⋀ ( ⋁ p 
 (Dupla negação)p p) ¬p p) p )( ↔ ¬ ⇔ ( ⋁ ¬ ⋀ ( ⋁ p 
 (Idempotência)p p) p( ↔ ¬ ⇔ ¬ ⋀ p 
 
c)​ (Def. dos operadores ) q ((¬p∧q) q)(¬p∧q) ⋁ ⇔ ¬ ↔ e ⋁ ↔ 
 (Equivalência da bicondicional) q (((¬p∧q) ) ¬ q))(¬p∧q) ⋁ ⇔ ¬ ⋀ q ⋁ ( (¬p∧q) ⋀ ¬ 
 (De Morgan) q ((¬p∧q) ) (¬ q)(¬p∧q) ⋁ ⇔ ¬ ⋀ q ⋀ ¬ (¬p∧q) ⋀ ¬ 
 (De Morgan) q ¬ q) (¬p∧q) q)(¬p∧q) ⋁ ⇔ ( (¬p∧q) ⋁ ¬ ⋀ ( ⋁ ¬ 
 (De Morgan) q (p q) q) (¬p∧q) q)(¬p∧q) ⋁ ⇔ ( ⋁ ¬ ⋁ ¬ ⋀ ( ⋁ ¬ 
 (Distributiva) q (¬p q) q q))(¬p∧q) ⋁ ⇔ (p q)⋁ ¬ ⋀ ( ⋁ ¬ ⋁ ( ⋀ ¬ 
 (Idempotência) q(¬p∧q) ⋁ ⇔ (p q)⋁ ¬ ⋀ (¬p q)⋁ ¬ 
 
d)​ (Def. do Sheffer )(p p)⋀ ¬ ↓ (q q)⋀ ¬ ⇔ ¬ (p p)⋀ ¬ ⋀ ¬ (q q)⋀ ¬ ↓ 
 (De Morgan)(p p)⋀ ¬ ↓ (q q)⋀ ¬ ⇔ ¬ (p ¬p)⋁ ¬ ⋀ (¬q ¬q)⋁ ¬ 
 (Dupla Negação)(p p)⋀ ¬ ↓ (q q)⋀ ¬ ⇔ (¬p )⋁ p ⋀ (¬q )⋁ q 
 
5-a)​ (Equivalência da condicional)p ¬p ) p(p )→ q ⋀ ¬ ⇔ ( ⋁ q ⋀ ¬ 
 (Distributiva) p¬p p) q p) (p )→ q ⋀ ¬ ⇔ ( ⋀ ¬ ⋁ ( ⋀ ¬ 
 (Idempotência) p ¬p) q p) (p )→ q ⋀ ¬ ⇔ ( ⋁ ( ⋀ ¬ 
 
b)​ (Def. do Sheffer )p q(p↑q)⇔ ¬ ⋁ ¬ ↑ 
 
c)​ (Def. dos operadores ) q ((¬p ) )(¬p∧q) ⋁ ⇔ ¬ ⋀ q ↔ q e ⋁ ↔ 
 (Equivalência da bicondicional) q (((¬p ) ) q ¬p )))(¬p∧q) ⋁ ⇔ ¬ ⋀ q → q ⋀ ( → ( ⋀ q 
 (Equivalência da condicional) q ((¬(¬p ) ) ¬q ¬p )))(¬p∧q) ⋁ ⇔ ¬ ⋀ q ⋁ q ⋀ ( ⋁ ( ⋀ q 
 (De Morgan) q (((p q) ) ¬q ¬p )))(¬p∧q) ⋁ ⇔ ¬ ⋁ ¬ ⋁ q ⋀ ( ⋁ ( ⋀ q 
 (Identidade) q (¬q ¬p ))(¬p∧q) ⋁ ⇔ ¬ ⋁ ( ⋀ q 
 (De Morgan) q q (¬p ))(¬p∧q) ⋁ ⇔ ( ⋀ ¬ ⋀ q 
 (De Morgan) q q p q))(¬p∧q) ⋁ ⇔ ( ⋀ ( ⋀ ¬ 
 (Distributiva) q q ) q q)(¬p∧q) ⋁ ⇔ ( ⋀ p ⋁ ( ⋀ ¬ 
 
d)​ (Def. do Sheffer )(p p) (q q)(p p)⋀ ¬ ↓ (q q)⋀ ¬ ⇔ ¬ ⋀ ¬ ⋀ ¬ ⋀ ¬ ↓ 
 (De Morgan)¬p ¬p) ¬q ¬q)(p p)⋀ ¬ ↓ (q q)⋀ ¬ ⇔ ( ⋁ ¬ ⋀ ( ⋁ ¬ 
 (Dupla Negação)¬p ) ¬q )(p p)⋀ ¬ ↓ (q q)⋀ ¬ ⇔ ( ⋁ p ⋀ ( ⋁ q 
 (Identidade)¬p )(p p)⋀ ¬ ↓ (q q)⋀ ¬ ⇔ ( ⋁ p 
 (Identidade)¬q )(p p)⋀ ¬ ↓ (q q)⋀ ¬ ⇔ ( ⋁ q