MATA47 - Resolução da Prova 1 - José Jorge, Juliana Nascimento, Litiano Moura, Guilherme do Valle e Pietro Bompet

Prévia do material em texto

MATA47 - Lógica para Computação
Resolução da Prova 1
José Jorge Alcântara, Juliana Nascimento, Litiano Moura, Guilherme do Valle e Pietro Bompet
19 de Novembro de 2020
Questão 1. Resposta :
Seja Fm∧ um conjunto que possua a variável ϕ, isto é, ϕ ∈ Fm∧. Sendo ϕ uma veriável, ϕ é satisfat́ıvel.
Base:
Sendo ϕ uma variável, ϕ é satisfat́ıvel, isto é, não é válida. Portanto, existe uma valoração v ∈ 2v tal que
v 2 ϕ.
Hipótese de Indução:
Consideremos agora uma nova variável ψ ∈ Fm∧.
Existem então ϕ, ψ ∈ Fm∧ tal que ϕ e ψ são satisfat́ıveis, não válidas.
Passo Indutivo:
Sejam ϕ, ψ ∈ Fm∧ tal que, por Hipótese de Indução, ϕ e ψ são satisfat́ıveis, ou seja, existem valorações
que não as satisfazem.
Sendo assim, podemos afirmar que para a fórmula complexa ψ ∧ ϕ existe uma valoração v ∈ 2v tal que
v 2 ψ ∧ ϕ, já que existem valorações que não satisfazem as variáveis ϕ e ψ.
Já que para toda fórmula de Fm∧ existe uma valoração que não a satisfaça, {∧} não é uma base de
conectivos, pois não pode constituir uma fórmula válida, como, por exemplo, >.
Questão 2. Resposta :
Item (i) da Questão
Ida: ”⇒”
Assumamos Φ 
 ϕ ∧ ψ. Seja v ∈ Mod (Φ).
A partir disso, por hipótese, temos que v � ϕ ∧ ψ ⇒ v � ϕ e v ` ψ.
Desse modo, temos que Φ 
 ϕ ∧ ψ.
Volta ”⇐”
Assumamos Φ � ϕ e Φ � ψ. Seja v ∈ Mod (Φ).
Por hipótese, temos que v � ϕ e v � ψ.
A partir disso, temos que v � ϕ ∧ ψ.
Desse modo, conclúımos que Φ � ϕ e Φ � ψ.
1
Item (ii) da Questão
Assumamos Φ 
 ϕ ∨ ψ e sabendo que se v ∈ 2v satisfaz ϕ, então também satisfaz ϕ ∨ ψ.
Desse modo, temos que Mod ({ϕ}) ⊆ Mod ({ϕ ∨ ψ}). A partir disso, temos os seguintes casos:
Caso 1: Φ 
 ϕ
Neste primeiro caso 1, temos que Mod (Φ) ⊆ ({ϕ}).
Como Mod ({ϕ}) ⊆ Mod ({ϕ ∨ ψ}), então temos Mod (Φ) ⊆ Mod ({ϕ ∨ ψ}).
Ou seja, Φ � ϕ ∨ ψ.
Caso 2: Φ 
 ϕ
Este segundo é análogo ao primeiro caso apresentado.
Item (iii) da Questão
Assumamos Φ = {ϕ ∨ ψ}. Tomemos, por exemplo, ψ ∈ Fm, sendo ψ = ¬ ϕ, temos que ϕ ∨ ψ ≡ ϕ ∨ ¬
ϕ, que é evidentemente verdadeiro.
Percebemos que qualquer valoração pode satisfazer o conjunto {ϕ ∨ ψ}.
Ou seja, temos valorações que não satisfazem ϕ e valorações que não satisfazem ψ, mesmo que uma dessas
valorações satisfaça uma das duas. Ou seja, Φ 1 ϕ e Φ 1 ψ.
Um contra-exemplo:
Suponhamos que ϕ = ”o número é múltiplo de dois” e ψ = ”o número não é múltiplo de de 2” e assumamos
Φ como o conjunto de fórmulas dos números inteiros.
É óbvio que Φ 
 ϕ ∨ ψ, porque todo número inteiro é múltiplo de 2 ou não é. Porém, também é óbvio
que nem todos os números inteiros são múltiplos de 2, assim como também nem todos não são, isto é, nem
Φ 
 ϕ Φ 
 ψ o que prova a afirmação Φ 
 ϕ ∨ ψ ; Φ 
 ϕ ou Φ 
 ψ.
Questão 3. Resposta :
Item (i) da Questão
Assumamos ϕ 
 ψ.
Tomemos v ∈ 2v tal que v � (ϕ ∧ χ). Temos que v � ϕ.
A partir disso, temos que, por hipótese, v � ψ. Como v também satifaz χ, temos que v � χ.
Portanto, temos que v � (ψ ∧ χ), e segue que Mod ({ϕ}) ⊆ Mod ({ψ})⇒ Mod ({ϕ ∧ χ}) ⊆ Mod ({ψ ∧
χ}).
Q.E.D.
Item (ii) da Questão
Assumamos ϕ 
 ψ.
Tomemos v ∈ 2v tal que v � (ϕ ∨ χ). Temos que v � ϕ.
A partir disso, temos que, por hipótese, v � ψ. Como v também satifaz χ, temos que v � χ.
Portanto, temos que v � (ψ ∨ χ), e segue que Mod ({ϕ}) ⊆ Mod ({ψ})⇒ Mod ({ϕ ∨ χ}) ⊆ Mod ({ψ ∨
χ}).
Q.E.D.
2
Questão 4. Resposta :
Item (a) da Questão
Suponhamos ∆ ∪ ϕ 
 ψ e ∆ ∪ ¬ ϕ 
 ψ. Seja v ∈ Mod ∆.
Se v � ϕ, temos que v � ∆ ∪ ϕ, e, pela hipótese, segue que v � ψ.
Se v � ¬ ϕ, então v � ∆ ∪ ¬ ϕ, e temos v � ψ pela hipótese.
A partir disso, podemos concluir que se v � ∆, então v � ψ, ou seja, ∆ 
 ψ.
Item (b) da Questão
Suponhemos ∆ ` e ∆ ` ψ sejam corretos, ou seja, ∆ � ϕ e ∆ � ψ.
Então todo modelo de ∆ é modelo de ϕ: Mod (∆) ⊆ Mod ({ϕ}) e todo modelo de ∆ é modelo de ψ:
Mod (∆) ⊆ Mod ({ψ}).
Logo, Mod ({ϕ}) ⊆ Mod ({ϕ ∧ ψ}) e Mod ({ψ}) ⊆ ({ϕ ∧ ψ}).
Então Mod (∆) ⊆ Mod ({ϕ ∧ ψ}).
Isto é, ∆ � ϕ ∧ ψ e a sequente ∆ ` ϕ ∧ ψ é correta.
Questão 5. Resposta :
ϕ = (x → y) → (¬y → ¬x)
¬ ϕ = ¬ ( (x → y) → (¬y → ¬x) )
= ¬ (¬ (x → y) ∨ (¬y → ¬x) )
= (x → y) ∧ ¬ (¬y → ¬x)
= (¬x ∨ y) ∧ ¬ (y ∨ ¬x)
= (¬x ∨ y) ∧ (¬y ∧ x) FNC
Os passos a seguir constituem uma derivacão a partir de ¬ ϕ :
¬ ϕ = (¬x ∨ y) ∧ ¬y ∧ x
1. C1 = {¬ x, y }, cláusula de ¬ ϕ.
2. C2 = {¬ y }, cláusula de ¬ ϕ.
3. C3 = { x }, cláusula de ¬ ϕ.
4. C4 = {¬ x}, resolvente de C1 e C2.
5. C5 = �, resolvente de C4 e C3.
A partir do Cálculo de Resolução aplicado a fórmula ¬ ϕ, chegamos ao resolvente C5 = ∅, ou seja,
conclúımos que ¬ ϕ é insatisfat́ıvel, provando assim que ϕ é uma tautologia.
Questão 6. Resposta :
Seja v ∈ 2v tal que v � ¬ (ϕ ∧ ψ) ⇔
⇔ v 2 (ϕ ∧ ψ)
3
⇔ v 2 ϕ ou v 2 ψ
⇔ v � ¬ ϕ ou v � ¬ ψ
⇔ v � ¬ ϕ ∨ ¬ ψ
Questão 7. Resposta :
Seja Φ = { x1∨ x2, ¬x2∨ ¬x3, x3∨ x4, ¬x4∨ ¬x5, ...}
Assumamos v ∈ 2v tal que v � x; para todo i ı́mpar e v 2xk para todo k par.
Logo, v é modelo de Φ.
4