PrimeiraProva_MATA47_2020 1

Prévia do material em texto

Prova de Lógica 1
November 17, 2020
Pontuação máxima: 10
1 (2P) Seja Fm∧ o menor conjunto que contém todas as variáveis V e é fechado
sob a condição seguinte: se ϕ,ψ ∈ Fm∧, então (ϕ ∧ ψ) ∈ Fm∧. Prove por indução
que nenhuma fórmula ϕ ∈ Fm∧ é válida. Mostre que isto implica que {∧} não é base
de conectivos.
2 (2P) Sejam Φ ∪ {ϕ,ψ} ⊆ Fm. Prove:
(i) Φ 
 ϕ ∧ ψ ⇔ [Φ 
 ϕ e Φ 
 ψ].
(ii) Φ 
 ϕ ∨ ψ ⇐ [Φ 
 ϕ ou Φ 
 ψ].
(iii) Φ 
 ϕ ∨ ψ ; [Φ 
 ϕ ou Φ 
 ψ]. Isto é, a implicação é falsa. Apresente um
contra-exemplo (isto é, um exemplo para Φ, ϕ, ψ tal que a implicação não vale).
3 (2P) Sejam ϕ,ψ, χ ∈ Fm. Prove:
(i) Se {ϕ} 
 ψ, então {ϕ ∧ χ} 
 ψ ∧ χ.
(ii) Se {ϕ} 
 ψ, então {ϕ ∨ χ} 
 ψ ∨ χ.
4 (1P) Suponha que nos é dado um cálculo de sequentes da Lógica Proposicional
na base de conectivos {¬,∧}. Mostre que as seguintes duas regras são corretas:
(a)
∆ ∪ {ϕ} ` ψ,∆ ∪ {¬ϕ} ` ψ
∆ ` ψ
(b)
∆ ` ϕ,∆ ` ψ
∆ ` ϕ ∧ ψ
5 (3P) Use Resolução para mostrar que a fórmula ϕ = (x → y) → (¬y → ¬x) é
uma tautologia. (Dica: Lembre que para qualquer fórmula ϕ: ϕ é tautologia sse ¬ϕ é
insatisfatı́vel.)
6 (1P) Prove: ¬(ϕ ∧ ψ) ≡ ¬ϕ ∨ ¬ψ.
7 (1P) Apresente um modelo do conjunto infinito
Φ = {x1 ∨ x2,¬x2 ∨ ¬x3, x3 ∨ x4,¬x4 ∨ ¬x5, ...}.
1