Lógica Computacional Gabarito da Primeira Prova

Lógica Computacional Gabarito da Primeira Prova

Lógica Computacional
Gabarito da Primeira Prova
Tópicos:
Lógica proposicional
Semântica e Dedução
Instituto de Ciências Exatas, Universidade de Brası́lia
07 de Maio de 2012
Prof. Mauricio Ayala-Rincón
Bolsista Reuni: Heitor Henrique de Paula Moraes Costa
Dedução natural
Table 1: Rules of natural deduction for propositional (classical) logic
introduction rules
elimination rules
ϕ ψ
(∧i )
ϕ∧ψ
ϕ∧ψ
ϕ (∧e )
ϕ
(∨i )
ϕ∨ψ
[ϕ]u
..
.
ψ
(→i ), u
ϕ→ψ
[ϕ]u
..
.
⊥ (¬ ), u
i
¬ϕ
ϕ∨ψ
[ϕ]u
..
.
χ
χ
[ψ]v
..
.
χ
(∨e ), u, v
ϕ→ψ
(→e )
ψ
ϕ
ϕ
¬ϕ
(¬e )
⊥
¬¬ϕ
ϕ (¬¬e )
1. (2.0 pontos) Considere o cálculo da lógica proposicional, como apresentado na Tabela 1.
Construa deduções para as seguintes regras derivadas:
[¬ϕ]u
..
.
⊥
(⊥e ), u
(a) (1.0 ponto) Prova por contradição ou ϕ
R/
[¬ϕ]u
..
.
⊥
¬¬ϕ (¬i ), u
(¬¬e )
ϕ
(b) (1.0 ponto) Lei do meio excluı́do ou
R/
[¬(ϕ ∨ ¬ϕ)]u
(ϕ ∨ ¬ϕ)
(LEM )
[ϕ]v
(∨i )
[¬(ϕ ∨ ¬ϕ)]u (ϕ ∨ ¬ϕ)
(¬e )
⊥ (¬ ), v
i
¬ϕ
(∨i )
(ϕ ∨ ¬ϕ)
(¬e )
⊥
(⊥e ), u
(ϕ ∨ ¬ϕ)
2. (4.0 pontos) Construa derivações para a Lei de De Morgan (ϕ ∧ ψ) a` ¬(¬ϕ ∨ ¬ψ).
(a) (2.0 pontos) (ϕ ∧ ψ) ` ¬(¬ϕ ∨ ¬ψ).
R/
[¬ϕ ∨ ¬ψ]u
ϕ∧ψ
ϕ (∧e ) [¬ϕ]x
(¬e )
⊥
⊥
¬(¬ϕ ∨ ¬ψ)
ϕ∧ψ
(∧e )
ψ
[¬ψ]y
(¬e )
⊥
(∨e ), x, y
(¬i ), u
(b) (2.0 pontos) (ϕ ∧ ψ) a ¬(¬ϕ ∨ ¬ψ).
R/
[¬ψ]y
[¬ϕ]x
(∨i ) ¬(¬ϕ ∨ ¬ψ) (¬ϕ ∨ ¬ψ) (∨i )
¬(¬ϕ ∨ ¬ψ) (¬ϕ ∨ ¬ψ)
(¬e )
(¬e )
⊥ (⊥ ), y
⊥ (⊥ ), x
e
e
ϕ
ψ
(∧i )
(ϕ ∧ ψ)
Semântica
3. (4.0 pontos) Utilize a técnica de solucionador SAT para demonstrar que a Lei de Pierce
((ϕ → ψ) → ϕ) → ϕ
é válida; i.e., demonstre que a negação da Lei de Pierce é insatisfazı́vel, conforme os seguintes
passos.
¬
¬
ϕ
∧*
}} **
}
**
}}
**
}}
**
¬
**
**
**
**
∧ PPP
PPP
*
}}
P
}
P
}
PPP **
}
P
PP *
}}
¬
r¬
rr
r
r
rr
rr
r
r
rr
∧A
rr
A
r
AA rrr
rA
rr AA
r
r
rr
¬
rrrr
r
r
r
rrr
rrr
ψ
Figure 1: DAG para ¬¬(¬(¬(ϕ ∧ ¬ψ) ∧ ¬ϕ) ∧ ¬ϕ)
(a) (1.0 ponto) Transforme a negação da Lei de Pierce numa fórmula equivalente no fragmento negativo-conjuntivo da lógica proposicional, utilizando o operador T passo a passo;
R/
T (¬(((ϕ → ψ) → ϕ) → ϕ)) =
...
¬¬(T ((ϕ → ψ) → ϕ) ∧ ¬ϕ) =
...
¬¬(¬(T (ϕ → ψ) ∧ ¬ϕ) ∧ ¬ϕ) =
...
¬¬(¬(¬(ϕ ∧ ¬ψ) ∧ ¬ϕ) ∧ ¬ϕ)
(b) (1.5 pontos) Construa um DAG para esta fórmula;
R/ Veja Figura 1.
(c) (1.5 pontos) Utilizando a técnica de solucionadores SAT, demonstre que está fórmula é
insatisfazı́vel.
R/ Veja Figura 2.
{1 : >}¬
{2 : F }¬
{3 : >}∧
22
22
22
22
22
{4 : >}¬
22
22
22
22
{5 : F }∧ VV
22
VVVV
q
22
q
V
q
V
VVVV
q
22
q
q
V
V
q
VVVV
2
VV
qqq
qq
qqq
q
q
qqq
{6 : F }¬
k
kkk
kkk
k
×
k
k
kkk
kkk
k
k
k
{6 : F }∧
kkk
NNN
kkk
w
k
k
w
N
NNN kkkk
ww
kkkNNNN
ww
k
w
k
k
N
w
k
k
w
w
kk
¬
kkk
ww
k
k
w
w
kk
k
w
k
k
w
ww kkkk
ww kkk
{5 : F }ϕ
{4 : >}¬
ψ
Figure 2: Verificação da (in)satisfazibilidade de ¬¬(¬(¬(ϕ ∧ ¬ψ) ∧ ¬ϕ) ∧ ¬ϕ)