Lógica Computacional - Primeira Prova Resolvida - 1º/2010 (Ayala)

Prévia do material em texto

L
�
ogica Computacional
Gabarito da Primeira Prova
T
�
opicos: L
�
ogica proposicional
Sem
^
antica e Deduc�
~
ao
Instituto de Ci
^
encias Exatas, Universidade de Bras
�
�lia
23 de junho de 2010
Prof. Mauricio Ayala-Rinc
�
on
Monitor: Andr
�
e Figueira Lourenc�o
Nome: Matr��cula:
Dura�c~ao: 100 min.
Inicio: 16:00; Fim: 17:45
Duas P�aginas, tre^s quest~oes
Deduc�
~
ao natural
1. (4.0 pontos) Considere a seguinte dedu�c~ao de ¬p ∨ ¬q ` ¬(p ∧ q).
�
1
=

¬p ∨ ¬q
[p ∧ q]u
p
∧e
1
[¬p]x
⊥ ¬e
[p ∧ q]u
q
∧e
2
[¬q]y
⊥ ¬e
⊥
∨e, x, y
¬(p ∧ q) ¬i, u
Construa dedu�c~oes da seguinte vers~ao de uma das Leis de De Morgan:
¬(¬p ∨ ¬q) a` p ∧ q
(a) (2.0 pontos) Constua uma prova por dedu�c~ao natural, indicando o nome das regras uti-
lizadas e as suposi�c~oes descarregadas, de
¬(¬p ∨ ¬q) ` p ∧ q
Pode-se derivar o absurdo de supor ¬p, assim como de supor ¬q. Dessa forma poder�a
derivar-se tanto p como q.
R/
¬(¬p ∨ ¬q)
[¬p]u
¬p ∨ ¬q ∨i
⊥ ¬e
p PBC, u
¬(¬p ∨ ¬q)
[¬q]v
¬p ∨ ¬q ∨i
⊥ ¬e
q PBC, v
p ∧ q ∧i
(b) (2.0 pontos) Constua uma prova por dedu�c~ao natural, indicando o nome das regras uti-
lizadas e as suposi�c~oes descarregadas, de
p ∧ q ` ¬(¬p ∨ ¬q)
Pode-se utilizar a dedu�c~ao �
1
, para obter uma prova de ` (¬p ∨ ¬q) → ¬(p ∧ q) e, logo
aplicar Modus Tollens desta �ultima f�ormula com ¬¬(p ∧ q).
R/
[¬p ∨ ¬q]x
�
1
¬(p ∧ q)
(¬p ∨ ¬q)→ ¬(p ∧ q) →i, x
(p ∧ q) [¬(p ∧ q)]y
⊥ ¬e
¬¬(p ∧ q) ¬i, y
¬(¬p ∨ ¬q) MT
Sem
^
antica
2. (3.0 pontos) Lembre que o operador T utilizado no m�etodo de SAT �e de�nido como:
T (p) = p T (¬φ) = ¬T (φ)
T (φ
1
∧ φ
2
) = T (φ
1
) ∧ T (φ
2
) T (φ
1
∨ φ
2
) = ¬(¬T (φ
1
) ∧ ¬T (φ
2
))
T (φ
1
→ φ
2
) = ¬(T (φ
1
) ∧ ¬T (φ
2
))
Deseja-se demonstrar que este operador �e correto; i.e., que para qualquer f�ormula φ,
φ ≡ T (φ)
ou, em outras palavras, que para qualquer designa�c~ao de valores de verdade das vari�aveis que
ocorrem em φ, o valor de verdade de φ e de T (φ) �e o mesmo.
Para isto �e necess�ario completar a demonstra�c~ao por indu�c~ao na estrutura dos termos embaixo.
Prova indutiva de que T �e uma transforma�c~ao correta: para toda φ, φ ≡ T (φ).
Base da Indu�c~ao. φ = p, uma vari�avel proposicional. Por de�ni�c~ao T (p) = p. Dessa forma,
p ≡ T (p).
Passo da Indu�c~ao.
Caso nega�c~ao: φ = ¬φ
1
. Por hip�otese de indu�c~ao, φ
1
≡ T (φ
1
), j�a que φi �e sub f�ormula de
φ. Assim, ¬φ
1
≡ ¬T (φ
1
), mas por de�ni�c~ao T (¬φ
1
) = ¬T (φ
1
). Logo, ¬φ
1
≡ T (¬φ
1
).
Caso conjun�c~ao: φ = φ
1
∧ φ
2
. Por hip�otese de indu�c~ao, φ
1
≡ T (φ
1
) e φ
2
≡ T (φ
2
), j�a
que φi e φ2 s~ao sub f�ormulas de φ. Sempre que T (φ1 ∧ φ2) = T (φ1) ∧ T (φ2), obtem-se
φ
1
∧ φ
2
≡ T (φ
1
) ∧ T (φ
2
).
(a) (1.5 pontos) Caso disjun�c~ao: φ = φ
1
∨ φ
2
. Provar φ
1
∨ φ
2
≡ T (φ
1
∨ φ
2
).
R/ Por hip�otese de indu�c~ao, φ
1
≡ T (φ
1
) e φ
2
≡ T (φ
2
), j�a que φi e φ2 s~ao sub f�ormulas de
φ. Por de�ni�c~ao
T (φ
1
∨ φ
2
) = ¬(¬T (φ
1
) ∧ ¬T (φ
2
))
Para qualquer designa�c~ao de valores de verdade das vari�aveis em φ, φ
1
e φ
2
tem valor de
verdade T ou F , e esses valores coincidem, respectivamente, com os valores de T (φ
1
) e
T (φ
2
), por hip�otese de indu�c~ao. Dessa forma, basta comparar uma tabela de valores de
verdade para as f�ormulas φ e T (φ):
φ
1
= T (φ
1
) φ
2
= T (φ
2
) φ = φ
1
∨ φ
2
¬T (φ
1
) ¬T (φ
2
) T (φ) = ¬(¬T (φ
1
) ∧ ¬T (φ
2
))
T T T F F T
T F T F T T
F T T T F T
F F F T T T
Assim, φ ≡ T (φ).
(b) (1.5 pontos) Caso implica�c~ao: φ = φ
1
→ φ
2
. Provar φ
1
→ φ
2
≡ T (φ
1
→ φ
2
).
R/ Por hip�otese de indu�c~ao, φ
1
≡ T (φ
1
) e φ
2
≡ T (φ
2
), j�a que φi e φ2 s~ao sub f�ormulas de
φ. Por de�ni�c~ao
T (φ
1
→ φ
2
) = ¬(T (φ
1
) ∧ ¬T (φ
2
))
φ
1
= T (φ
1
) φ
2
= T (φ
2
) φ = φ
1
→ φ
2
¬T (φ
2
) T (φ) = ¬(T (φ
1
) ∧ ¬T (φ
2
))
T T T F T
T F F T F
F T T F T
F F T T T
Assim, φ ≡ T (φ).
Observe que para completar a prova dos �ultimos dois itens, pode-se supor a hip�otese de indu�c~ao
(i.e., φ
1
≡ T (φ
1
) e φ
2
≡ T (φ
2
) ) e trabalhar com tabelas de verdade.
Satisfazibilidade
3. (3.0 pontos) Utilize a t�ecnica de solucionador SAT para demonstrar que a Lei de De Morgan
(p ∧ q)→ ¬(¬p ∨ ¬q)
do exerc��cio 1 �e v�alida; i.e., demonstre que a sua nega�c~ao, ¬((p∧q)→ ¬(¬p∨¬q)), �e insatisfaz��vel,
conforme o seguinte roteiro:
(a) (0.5) Apresente todos os passos da aplica�c~ao da transforma�c~ao T �a nega�c~ao da Lei de De
Morgan acima de forma a obter a f�ormula equivalente no fragmento negativo-conjuntivo da
l�ogica proposicional embaixo:
¬¬((p ∧ q) ∧ ¬¬¬(¬¬p ∧ ¬¬q))
R/
T (¬((p ∧ q)→ ¬(¬p ∨ ¬q))) =
¬T ((p ∧ q)→ ¬(¬p ∨ ¬q)) =
¬¬(T (p ∧ q) ∧ ¬T (¬(¬p ∨ ¬q))) =
¬¬((T (p) ∧ T (q)) ∧ ¬T (¬(¬p ∨ ¬q))) =2
¬¬((p ∧ q) ∧ ¬T (¬(¬p ∨ ¬q))) =
¬¬((p ∧ q) ∧ ¬¬T (¬p ∨ ¬q)) =
¬¬((p ∧ q) ∧ ¬¬¬(¬T (¬p) ∧ ¬T (¬q))) =2
¬¬((p ∧ q) ∧ ¬¬¬(¬¬T (p) ∧ ¬¬T (q))) =2
¬¬((p ∧ q) ∧ ¬¬¬(¬¬p ∧ ¬¬q))
(b) (0.5) Construa um DAG para esta f�ormula;
R/ Veja �gura 1.
¬
¬
∧
p
p
p
p
p
p
p
p
p
p
p
p
p
N
N
N
N
N
N
N
N
N
N
N
N
N
∧
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
¬
¬
¬
∧
p
p
p
p
p
p
p
p
p
p
p
p
p
A
A
A
A
A
A
A
¬ ¬
¬ ¬
p q
Figure 1: DAG para ¬¬((p ∧ q) ∧ ¬¬¬(¬¬p ∧ ¬¬q))
(c) (2.0) Utilizando a t�ecnica de solucionadores SAT, demonstre que est�a f�ormula �e insatis-
faz��vel.
R/ Aplicando o m�etodo SAT na �gura 1, obtem-se uma contradi�c~ao na oitava itera�c~ao (veja
�gura 2), o que implica a insatisfazibilidade da nega�c~ao da f�ormula.
{1 : >}¬
{2 : F}¬
{3 : >}∧
l
l
l
l
l
l
l
l
l
l
l
l
l
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
{4 : >}∧
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
{4 : >}¬
{5 : F}¬
{6 : >}¬
{7 : F} ∧ {8 : >}
j
j
j
j
j
j
j
j
j
j
j
j
j
j
j
j
Q
Q
Q
Q
Q
Q
Q
Q
Q
Q
Q
Q
{7 : >}¬ {7 : >}¬
{6 : F}¬ {6 : F}¬
{5 : >}p {5 : >}q
Figure 2: Veri�ca�c~ao da (in)satisfazibilidade de ¬¬((p ∧ q) ∧ ¬¬¬(¬¬p ∧ ¬¬q))