Lista de Exercício Lógica para Computação

Prévia do material em texto

Exercı´cios de Lo´gica 1
November 20, 2017
1 Ache as subfo´rmulas das seguintes fo´rmulas apresentando a´rvores sinta´ticas:
• p→ q → p→ p
• ((p→ q)→ p)→ p
• p ∧ ¬q → s
2 Sejam A1, A2, ..., An conjuntos (n ≥ 2) tais que para dois conjuntos quaisquer
Ai e Aj temos que Ai ⊆ Aj ou Aj ⊆ Ai. Prove por induc¸a˜o em n ≥ 2 que um dos n
conjuntos e´ subconjunto de todos.
3 Desenvolva uma FND e uma FNC, respectivamente, das fo´rmulas seguintes:
(p→ q)→ ¬(q ∧ p), ¬(p→ q)→ ¬(q ∨ p).
4 Seja FORM∨ o menor conjunto que satisfaz o seguinte:
(i) V ⊆ FORM∨
(ii) Se ϕ,ψ ∈ FORM∨, enta˜o (ϕ ∨ ψ) ∈ FORM∨.
Isto e´, FORM∨ somente conte´m varia´veis e disjunc¸o˜es. Prove por induc¸a˜o que to-
das as fo´rmulas de FORM∨ sa˜o satisfatı´veis. Como este fato pode ser utilizado para
mostrar que {∨} na˜o e´ base de conectivos?
5 Prove sem tabela verdade:
(i) ¬ϕ ≡ ϕ→ ⊥
(ii) ¬(ϕ ∧ ψ) ≡ ¬ϕ ∨ ¬ψ.
6 Classifique as seguintes fo´rmulas conforme validade, satisfatibilidade e insatis-
fatibilidade sem uso de tabela verdade. Tente justificar suas respostas de maneira mais
eficiente possı´vel.
(i) ((p→ q)→ p)→ p
(ii) (¬p→ (p ∧ q)) ∧ ¬p
(iii) ¬p→ (> → q)→ p
1
(iv) ((p→ p)→ p)→ p
7 Ache dois modelos do conjunto infinito:
Φ = {p1 ∨ p2,¬p2 ∨ ¬p3, p3 ∨ p4,¬p4 ∨ ¬p5, ...}.
8 Prove o seguinte:
(i) Se ϕ 
 ψ, enta˜o ϕ ∧ χ 
 ψ ∧ χ.
(ii) Se ϕ 
 ψ, enta˜o ϕ ∨ χ 
 ψ ∨ χ.
9 Prove ou refute o seguinte:
(i) {ϕ→ (ψ ∨ χ), (% ∧ χ)→ δ} 
 (ϕ ∧ χ)→ (ψ ∨ δ)
(ii) {(ϕ ∨ ψ)→ χ, ψ} 
 (δ → δ ∨ ψ) ∧ (ϕ ∧ %→ χ)
(iii) {ϕ→ ⊥, ψ → χ, χ→ ϕ,ψ → >} 
 ⊥
10 Prove ou refute o seguinte:
(i) Se Φ 
 ϕ ou Φ 
 ψ, enta˜o Φ 
 ϕ ∨ ψ
(ii) Se Φ 
 ϕ ∨ ψ, enta˜o Φ 
 ϕ ou Φ 
 ψ
(iii) Se Φ 
 ϕ e Φ 
 ψ, enta˜o Φ 
 ϕ ∧ ψ
(iv) Se Φ 
 ϕ ∧ ψ, enta˜o Φ 
 ϕ e Φ 
 ψ
11Mod(Φ ∪Ψ) ⊆Mod(Φ) ∩Mod(Ψ) ⊆Mod(Φ ∩Ψ).
12 Φ 
 ϕ sse o conjunto Φ ∪ {¬ϕ} e´ insatisfatı´vel.
2