Lógida - AP2-2010-2 -Gabarito

Prévia do material em texto

Segunda Avaliac¸a˜o Parcial
Prof. Davi Romero de Vasconcelos
16 de junho de 2009
SIN015 – Lo´gica para Computac¸a˜o Questa˜o 1 2.0 pontos
Nome: pontos
Prove ou refute os itens abaixo utilizando o sistema de Tableau Semaˆntico. Caso
o item seja refutado, apresente um contra-exemplo de acordo com o tableau
apresentado.
1. (A ∨ (B ∧ C)) ` (A ∧ C)
1(A ∨ (B ∧ C))
0(A ∧ C)
1A
0A
↙
0C
1B ∧ C
1B
1C
0A 0C
↙
Contra-exemplos:
• v(A) = 1 e v(C) = 0;
• v(A) = 0 e v(B) = v(C) = 1.
2. (A ∨ (B ∧ C)) ` ((A ∨B) ∧ (A ∨ C))
1(A ∨ (B ∧ C))
0((A ∨B) ∧ (A ∨ C))
1A
0A ∨B
0A
0B
↙
0A ∨ C
0A
0C
↙
1B ∧ C
1B
1C
0A ∨B
0A
0B
↙
0A ∨ C
0A
0C
↙
1
SIN015 – Lo´gica para Computac¸a˜o Questa˜o 2 3.0 pontos
Nome: pontos
Considere uma linguagem na˜o-lo´gica contendo apenas um s´ımbolo predicativo
bina´rio R. Sejam I uma estrutura e s uma func¸a˜o de varia´veis no universo de
I como definidas abaixo.
1. Universo de |I| = {a, b, c, d}
2. O s´ımbolo predicativoR e´ interpretado comoRI = {〈a, a〉, 〈b, c〉, 〈c, d〉, 〈b, a〉 〈c, a〉 〈d, a〉}
3. s(x) = a
Demonstre, utilizando a definic¸a˜o de |=, os itens abaixo.
1. |=I ∀yR(y, x)[s]
⇐⇒ ∀k ∈ |I| temos que |=I R(y, x)[s(y|k)]
⇐⇒ ∀k ∈ |I| temos que 〈s¯(y|k)(y), s¯(y|k)(x)〉 ∈ RI
⇐⇒ ∀k ∈ |I| temos que 〈k, a〉 ∈ RI
⇐⇒ 〈a, a〉 ∈ RI , 〈b, a〉 ∈ RI , 〈c, a〉 ∈ RI , 〈d, a〉 ∈ RI
2. |=I ∃xR(x, x)[s]
⇐⇒ ∃k ∈ |I| tal que |=I R(x, x)[s(x|k)]
⇐⇒ ∃k ∈ |I| tal que 〈s¯(x|k)(x), s¯(x|k)(x)〉 ∈ RI
⇐⇒ ∃k ∈ |I| tal que 〈k, k〉 ∈ RI
⇐⇒ 〈a, a〉 ∈ RI
3. 6|=I ∀x∀y(R(x, y) ↔ R(y, x))[s]
⇐⇒ NA˜O ∀k ∈ |I| temos que |=I ∀y(R(x, y) ↔ R(y, x))[s(x|k)]
⇐⇒ NA˜O ∀k ∈ |I|, ∀l ∈ |I| temos que |=I (R(x, y) ↔ R(y, x))[s(x|k)(y|l)]
⇐⇒ NA˜O ∀k ∈ |I|, ∀l ∈ |I| temos que |=I R(x, y)[s(x|k)(y|l)] sse |=I R(y, x)[s(x|k)(y|l)]
⇐⇒ NA˜O ∀k ∈ |I|, ∀l ∈ |I| temos que 〈s¯(x|k)(y|l)(x), s¯(x|k)(y|l)(y)〉 ∈ RI sse 〈s¯(x|k)(y|l)(y), s¯(x|k)(y|l)(x)〉 ∈ RI
⇐⇒ NA˜O ∀k ∈ |I|, ∀l ∈ |I| temos que 〈k, l〉 ∈ RI sse 〈l, k〉 ∈ RI
⇐⇒ 〈b, c〉 ∈ RI e 〈c, b〉 6∈ RI
2
SIN015 – Lo´gica para Computac¸a˜o Questa˜o 3 2.0 pontos
Nome: pontos
Seja DN∧ um sistema de deduc¸a˜o natural que contenha apenas as regras de
introduc¸a˜o e eliminac¸a˜o do conectivo ∧. Defina uma func¸a˜o t que recebe uma
derivac¸a˜o e retorne o tamanho da derivac¸a˜o, ou seja, o nu´mero de fo´rmulas
que ocorrem na a´rvore de derivac¸a˜o. Abaixo temos treˆs exemplos da func¸a˜o t
aplicada a treˆs derivac¸o˜es diferentes.
t(A ∧B) = 1 t
(
A B
A ∧B
)
= 3 t

A B
A ∧B
A
 = 4

t(ϕ) = 1
t

∏
1
ϕ
∏
2
ψ
ϕ ∧ ψ
 = t
∏1ϕ
+ t

∏
2
ψ
+ 1
t

∏
ϕ ∧ ψ
ϕ
 = t

∏
ϕ ∧ ψ
+ 1
t

∏
ϕ ∧ ψ
ψ
 = t

∏
ϕ ∧ ψ
+ 1
3
SIN015 – Lo´gica para Computac¸a˜o Questa˜o 4 3.0 pontos
Nome: pontos
Prove, utilizando o sistema de Deduc¸a˜o Natural, os itens abaixo.
1. ¬∀xϕ(x) ` ∃x¬ϕ(x)
¬∀xϕ(x)
[¬∃x¬ϕ(x)]1
[¬ϕ(a)]2
∃x¬ϕ(x)
⊥
ϕ(a)
2
∀xϕ(x)
⊥ 1
∃x¬ϕ(x)
2. (∀xϕ(x) ∨ ψ) ` ∀x(ϕ(x) ∨ ψ), onde x 6∈ V L(ψ)
(∀xϕ(x) ∨ ψ)
[∀xϕ(x)]1
ϕ(a)
ϕ(a) ∨ ψ
∀x(ϕ(x) ∨ ψ)
[ψ]1
ϕ(a) ∨ ψ
∀x(ϕ(x) ∨ ψ)
∀x(ϕ(x) ∨ ψ)
1
3. ∃x(ϕ(x) → ∀xϕ(x))
[¬∃x(ϕ(x) → ∀xϕ(x))]1
[∀xϕ(x)]2
ϕ(a) → ∀xϕ(x)
∃x(ϕ(x) → ∀xϕ(x))
⊥
¬∀xϕ(x)
2
[¬∃x(ϕ(x) → ∀xϕ(x))]1
[¬ϕ(a)]3 [ϕ(a)]4
⊥
∀xϕ(x)
ϕ(a) → ∀xϕ(x)
4
∃x(ϕ(x) → ∀xϕ(x))
⊥
ϕ(a)
3
∀xϕ(x)
⊥
∃x(ϕ(x) → ∀xϕ(x))
1
4