Lista 3 de Lógica Matemática

Prévia do material em texto

Lista 3 de Lógica Matemática 
1. Encontre demonstrações para os seguintes sequentes: 
 
a) 𝑃 ⊢ 𝑄 → ( 𝑃 ∧ 𝑄) 
b) 𝑃 ∧ (𝑄 ∧ 𝑅) ⊢ 𝑄 ∧ (𝑃 ∧ 𝑅) 
c) (𝑃 → 𝑄) ∧ (𝑃 → 𝑅) ⊢ 𝑃 → (𝑄 ∧ 𝑅) 
d) 𝑄 ⊢ 𝑃 ∨ 𝑄 
e) 𝑃 ∧ 𝑄 ⊢ 𝑃 ∨ 𝑄 
f) (𝑃 → 𝑅) ∧ (𝑄 → 𝑅) ⊢ (𝑃 ∨ 𝑄) → 𝑅 
g) 𝑃 → 𝑄, 𝑅 → 𝑆 ⊢ (𝑃 ∧ 𝑅) → (𝑄 ∧ 𝑆) 
h) 𝑃 → 𝑄, 𝑅 → 𝑆 ⊢ (𝑃 ∨ 𝑅) → (𝑄 ∨ 𝑆) 
i) 𝑃 → (𝑄 ∧ 𝑅) ⊢ (𝑃 → 𝑄) ∧ (𝑃 → 𝑅) 
j) ¬ 𝑃 → 𝑃 ⊢ 𝑃 
 
2. Mostre que os sequentes abaixo não são corretos, ou seja, para 𝑥 ⊢ 𝑦, determine uma 
valoração que torne 𝑥 verdadeira e 𝑦 falsa. 
a) 𝑃 ⊢ 𝑃 ∧ 𝑄 
b) 𝑃 ∨ 𝑄 ⊢ 𝑃 
c) 𝑃 ∨ 𝑄 ⊢ 𝑃 ∧ 𝑄 
d) 𝑃 → 𝑄 ⊢ 𝑃 ∧ 𝑄 
 
3. Demonstre: 
 𝑿 ⊣⊢ 𝒀 é o mesmo que 𝑿 ⊢ 𝒀 e 𝒀 ⊢ 𝑿 
 
a) 𝑄, 𝑃 ↔ 𝑄 ⊢ 𝑃 
b) 𝑃 → 𝑄, 𝑄 → 𝑃 ⊢ 𝑃 ↔ 𝑄 
c) 𝑃 ↔ 𝑄 ⊢ ¬ 𝑃 ↔ ¬𝑄 
d) ¬ 𝑃 ↔ ¬ 𝑄 ⊢ 𝑃 ↔ 𝑄 
e) (𝑃 ∨ 𝑄) ↔ 𝑃 ⊢ 𝑄 → 𝑃 
f) 𝑃 ↔ ¬𝑄, 𝑄 ↔ ¬𝑅 ⊢ 𝑃 ↔ 𝑅 
g) 𝑃 ∨ 𝑄 ⊢ 𝑃 ∨ 𝑄 
h) 𝑃 ∧ 𝑃 ⊣⊢ 𝑃 
i) 𝑃 ∧ (𝑄 ∨ 𝑅) ⊣⊢ (𝑃 ∧ 𝑄) ∨ (𝑃 ∧ 𝑄) 
j) 𝑃 ∨ (𝑄 ∧ 𝑅) ⊣⊢ (𝑃 ∨ 𝑄) ∧ (𝑃 ∨ 𝑅) 
k) 𝑃 ∧ 𝑄 ⊣⊢ ¬(𝑃 → ¬𝑄) 
l) ¬(𝑃 ∨ 𝑄) ⊣⊢ ¬𝑃 ∧ ¬𝑄 
m) ¬(𝑃 ∧ 𝑄) ⊣⊢ ¬𝑃 ∨ ¬𝑄 
n) 𝑃 ∧ 𝑄 ⊣⊢ ¬(¬𝑃 ∨ ¬𝑄) 
o) 𝑃 → 𝑄 ⊢ ¬𝑃 ∨ 𝑄 
p) ¬𝑃 → 𝑄 ⊢ 𝑃 ∨ 𝑄 
 
4. A regra DN (Dupla Negação) estabelece que 
¬¬𝑋
𝑋
 e 
𝑋
¬¬𝑋
 . Mostre que “de A deriva-se ¬¬A” pode ser 
obtida como regra derivada, ou seja, seria possível definir a regra DN simplesmente como: “de ¬¬A 
deriva-se A”. 
5. Mostre que se A ⊢ B é demonstrado então ⊢ 𝐴 → 𝐵 é demonstrável. 
6. Mostre que se 𝐴 ⊣⊢ 𝐵 é demonstrável então ⊢ 𝐴 ↔ 𝐵 é demonstrável. 
7. Mostre que cada regra é CORRETA, ou seja, se 𝑥1, 𝑥2, … , 𝑥2 ⊢ 𝑥 então 𝑥1, 𝑥2, … , 𝑥𝑛 ⊨ 𝑥. 
8. Mostre que a regra 𝑋 → 𝑌, ¬𝑋 ⊢ ¬𝑌 não é correta. Se essa regra fosse aceita, teríamos 
demonstrações de: 
 ⊢ (𝑋 → 𝑌) → (¬𝑋 → ¬𝑌) e ⊢ (¬𝑋 ∨ 𝑌) → (𝑋 ∨ ¬𝑌), 
𝑁𝑜𝑡𝑒 𝑞𝑢𝑒 𝑒𝑠𝑠𝑎𝑠 𝑓ó𝑟𝑚𝑢𝑙𝑎𝑠 𝑛ã𝑜 𝑠ã𝑜 𝑡𝑎𝑢𝑡𝑜𝑙ó𝑔𝑖𝑐𝑎𝑠.