Lista 5 de Lógica Matemática

Prévia do material em texto

Lista 5 de Lógica Matemática 
 
Um conjunto 𝐹 de operadores lógicos é dito ser funcionalmente completo se para cada fórmula 
𝑋 da lógica proposicional, há uma fórmula 𝑌, expressa apenas com os conectivos do conjunto 𝐹, de tal 
forma que 𝑋 é equivalente logicamente a 𝑌. 
 
1. Mostre que {¬, ∧ , ∨} é um conjunto funcionalmente completo. 
 
2. Mostre que {¬, ∧} é um conjunto funcionalmente completo. 
 
3. Mostre que {¬, ∨} é um conjunto funcionalmente completo. 
 
4. Construa uma tabela verdade para o operador barra de Sheffer: “|” (na informática é conhecido 
como NAND). 
 
𝑝|𝑞 é definido como: não p ou não q. 
 
5. Mostre que 𝑝|𝑞 é logicamente equivalente a ¬(𝑝 ∧ 𝑞). 
 
6. Construa uma tabela verdade para o operador seta de Peirce: “↓” (na informática é conhecido 
como NOR). 
 
 𝑝 ↓ 𝑞 é definido como: não p e não q. 
 
7. Mostre que 𝑝 ↓ 𝑞 é logicamente equivalente a ¬(𝑝 ∨ 𝑞). 
 
8. Mostre que {↓} é um conjunto funcionalmente completo. 
 
9. Mostre que {|} é um conjunto funcionalmente complete. 
 
10. Mostre que 𝑝 ↓ 𝑝 é logicamente equivalente a ¬𝑝.