Lista 1 de Lógica Matemática

Prévia do material em texto

Lista 1 de Lógica Matemática 
1. Verifique por meio de tabelas verdade se as fórmulas abaixo são tautologias, 
contradição (inconsistente) ou contingentes. 
a. 𝑝 → 𝑝 
b. 𝑝 → 𝑝 
c. (𝑝 → 𝑝) 
d. 𝑝 
e. 𝑝 → (𝑝 → 𝑞) 
f. (𝑝 ↔ 𝑞) ↔ (𝑝 ↔ 𝑞) 
g. (𝑝 ∧ 𝑞) ∧(𝑝 ↔ 𝑞) 
h. (𝑝 ∨ 𝑞) ∧ (𝑝 → 𝑞) 
i. (𝑝 ∧ 𝑞 → 𝑟) → (𝑝 → 𝑟) ∧ (𝑞 → 𝑟) 
j. (𝑝 ∨ 𝑞 → 𝑟) ↔ (𝑝 → 𝑟) ∧ (𝑞 → 𝑟) 
k. (𝑝 → 𝑞) ∧ (𝑟 → 𝑠) → (𝑝 ∨ 𝑟 → 𝑞 ∨ 𝑠) 
 
2. Para os itens do exercício acima que, como resultado, obteve-se contingência, 
elabore uma substituição que os torne tautologia e uma substituição que os torne 
contradição. 
 
3. Determine fórmulas para as 16 possíveis funções de verdade de duas variáveis 
proposicionais empregando: 
a. No máximo os conectivos "" e " ∧ ", 
b. No máximo os conectivos "" e " ∨ ", 
c. Seja ( 𝑝 ∣∣ 𝑞 ), por definição “não p ou não q” e seja (𝑝 ↓ 𝑞) por definição 
“não p e não q”. Em informática, são conhecidos por NAND E NOR, 
respectivamente. Elabore fórmulas para as 16 possíveis funções de 
verdade de duas variáveis proposicionais empregando: 
(i) No máximo o conectivo ∣ 
(ii) No máximo o conectivo ↓ 
 
4. Seja 𝑨 uma fórmula contendo variáveis proposicionais e apenas o conectivo " ∧ ". 
Mostre que A não pode ser uma tautologia e mostre que A não pode ser 
inconsistente. 
 
5. Seja 𝑨 uma fórmula contendo variáveis proposicionais e apenas o conectivo " ∨ ". 
Mostre que A não pode ser uma tautologia e mostre que A não pode ser 
inconsistente. 
 
6. Considere as três fórmulas abaixo: 
a. 𝑝 ∧ (𝑟 → 𝑟) → 𝑞 
b. 𝑝 ∧ (𝑞 ∨ 𝑟) 
c. 𝑝 → (𝑞 ↔ 𝑟) 
i. Mostre que nenhuma dessas fórmulas implica logicamente as outras. 
ii. Mostre que uma e somente uma é subcontrária das outras duas. (𝑨 e 𝑩 
são subcontrárias se e somente se 𝑨 ∨ 𝑩 é uma tautologia.) 
 
7. Mostre que, para quaisquer fórmulas 𝐴 e 𝐵, se 𝐴 e 𝐵 são contrárias então cada 
uma implica a negação da outra e suas negações são subcontrárias. (𝐴 e 𝐵 são 
contrárias se e somente se (𝐴 ∧ 𝐵) é uma tautologia) 
 
8. Mostre que, para quaisquer fórmulas 𝐴 e 𝐵, se 𝐴 e 𝐵 são subcontrárias então a 
negação de cada uma implica a outra e suas negações são contrárias. 
 
9. Mostre que, para quaisquer fórmulas 𝐴 e 𝐵, 𝐴 e 𝐵 são equivalentes 
a. se e somente se 𝐴 e 𝐵 são equivalentes 
b. se e somente se 𝐴 e 𝐵 são contraditórias (𝐴 e 𝐵 são contraditórias se e 
somente se (𝐴 ↔ 𝐵) é uma tautologia) 
 
10. Construa uma tabela verdade com todas as possíveis funções de verdade de uma 
variável proposicional e expresse para cada coluna da tabela uma fórmula 
equivalente utilizando apenas os conectivos " → " e "”. É possível fazer o 
mesmo procedimento para funções de duas variáveis proposicionais? 
 
11. Quantas possíveis funções de verdades distintas existem para 3 variáveis 
proposicionais? E para 𝑛 variáveis proposicionais?