L ogica Computacional Gabarito da Primeira Prova

 gica Computacional
Lo
Gabarito da Primeira Prova
picos:
To
gica proposicional
Lo
^ ntica e Deduc
~o
Sema
a
^ncias Exatas, Universidade de Bras
Instituto de Cie
lia
05 de outubro de 2009
n
Prof. Mauricio Ayala-Rinco
~ o natural
Deduc
a
1. (4.0 pontos) Considere a seguinte deduca~o
1
da regra de contra posica~o:
[¬q]
p ∨ ¬p
z
[p]y [p → q]u
q
→e
¬e
⊥
¬p ⊥e
¬q → ¬p → i, z
∨e, x, y
→ i, u
[¬p]x
¬q → ¬p → i, ∅
¬q → ¬p
(p → q) → (¬q → ¬p)
(a) (2.0) Complete a deduca~o, apresentando uma arvore de deduca~o natural da lei do meio
excludo; i.e., uma deduca~o de p ∨ ¬p.
R/
[p]m
[¬(p ∨ ¬p)]l p ∨ ¬p ∨i
⊥
¬p ¬i, m
[¬(p ∨ ¬p)]l
p ∨ ¬p ∨i
¬e
⊥ PBC, l
p ∨ ¬p
(b) (2.0) Apresente uma arvore de deduca~o natural
2
¬e
do recproco:
` (¬q → ¬p) → (p → q )
R/
[p]
q ∨ ¬q
[q]x
z
p → q → i, ∅
p→q
(¬q → ¬p) → (p → q)
[¬q → ¬p]u [¬q]y
¬p
→e
¬e
⊥
q ⊥e
p → q → i, z
∨e, x, y
→ i, u
2. (2.0 pontos) Considere a seguinte agrumentaca~o sobre a correca~o da Lei de Peirce tomada da
Wikipedia:
Para mostrar que a implicac~ao ((A → B ) → A) → A e valida sup~oe-se, por absurdo, que ela e
falsa, isto e, ¬(((A → B ) → A) → A). Portanto, ((A → B ) → A) e verdadeira e A e falsa, de
donde, A → B e falsa, e portanto A e verdadeira, o que resulta em um absurdo.
Conclui-se que ((A → B ) → A) → A.
Construir-se-a uma arvore de deduca~o natural traduzindo a argumentaca~o precedente. P.ex.,
\Portanto, ((A → B ) → A) e verdadeira e A e falsa, de donde, A → B e falsa" pode ser
expressa na seguinte deduca~o, 1 :
[A → B ]u (A → B ) → A
A
→e
¬A ¬e
⊥
¬i, u
¬(A → B )
E a seguir, \, e portanto A e verdadeira", na seguinte arvore de deduca~o, 2 :
[¬A]v
1
¬(A → B )
⊥
A
¬B → ¬A
(
2 item 1b
A→B
PBC, v
→ i, ∅
)
¬e
Utilizando as deduco~es 1 e 2 e deduco~es 3 e 4 de que \se ¬(((A → B ) → A) → A) ent~ao
((A → B ) → A) e verdadeira e A e falsa", a saber:
[¬(((A → B ) → A) → A)]w
3
(A → B ) → A
e
[¬(((A → B ) → A) → A)]w
4
¬A
Pode-se obter a deduca~o da Lei de Peirce, por contradica~o:
[¬(((A → B ) → A) → A)]w
4
¬A
[¬(((A → B ) → A) → A)]w [¬(((A → B ) → A) → A)]w
3
4
(A → B ) → A
¬A
1
¬(A → B )
2
⊥
((A → B ) → A) → A
PBC, w
A ¬e
Complete a deduca~o construndo arvores de deduca~o natural para
(a) (1.0) 3 e
R/
[¬(((A → B ) → A) → A)]w
⊥
[¬((A → B ) → A)]x
→ i, ∅
¬A → ¬((A → B ) → A)
2 (1b)
((A → B ) → A) → A
¬e
PBC, x
(A → B ) → A
(b) (1.0) 4 .
R/
[¬(((A → B ) → A) → A)]w
[A]y
((A → B ) → A) → A
⊥ ¬i, y
¬A
→ i, ∅
¬e
^ ntica
Sema
3. (4.0 pontos)
(a) (1.0) Construa uma formula em forma normal conjuntiva equivalente a Lei de Peirce
((A → B ) → A) → A
Utilize os algoritmos especcos para esta tarefa descritos no texto da disciplina.
R/
CNF(NNF(IMPL FREE(((A → B ) → A) → A))) =
. . . (todos os passos devem ser includdos na resposta)
CNF(NNF(¬(¬(¬A ∨ B ) ∨ A) ∨ A)
. . . (todos os passos devem ser includdos na resposta)
CNF(((¬A ∨ B ) ∧ ¬A) ∨ A)
. . . (todos os passos devem ser includdos na resposta)
(¬A ∨ B ∨ A) ∧ (¬A ∨ A)
(b) (3.0) Utilize a tecnica de solucionador SAT para demonstrar que a Lei de Pierce e valida;
i.e., demonstre que a negaca~o da Lei de Pierce e insatisfazvel:
i. (1.0) Transforme a negaca~o da Lei de Pierce numa formula equivalente no fragmento
negativo-conjuntivo da logica proposicional, utilizando o operador T ;
R/
T (¬(((A → B ) → A) → A)) =
...
¬¬(T ((A → B ) → A) ∧ ¬A) =
...
¬¬(¬(T (A → B ) ∧ ¬A) ∧ ¬A) =
...
¬¬(¬(¬(A ∧ ¬B ) ∧ ¬A) ∧ ¬A)
ii. (1.0) Construa um DAG para esta formula;
R/ Veja Figura 1.
iii. (1.0) Utilizando a tecnica de solucionadores SAT, demonstre que esta formula e insatisfazvel.
R/ Veja Figura 2.
¬
¬
A
∧*
}} **
}
}
**
}}
**
}}
**
¬
**
**
**
**
∧ PPP
PPP
**
}}
}
P
PPP
*
}}
P
}
PPP *
}}
¬
¬
rr
rr
r
r
rr
rr
r
r
∧
rr
AAA rrrr
AArr
rA
rr AA
r
r
r
r
¬
rrrr
r
r
rrr
rrr
B
Figure 1: DAG para ¬¬(¬(¬(A ∧ ¬B ) ∧ ¬A) ∧ ¬A)
{1 : >}¬
{2 : F }¬
{3 : >}∧
{4 :
{5 :
q
qq
qq
q
qq
qq
{6 : F }¬
22
22
22
22
22
>}¬
22
22
22
22
F }∧ VV
22
VVVV
22
VVVV
22
VVVV
VVVV
2
VV
qq
qq
qq
q
q
qq
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
ww kkkkkk
w
ww kkk
ww kkk
{5 : F }A
{4 : >}¬
B
Figure 2: Vericaca~o da (in)satisfazibilidade de ¬¬(¬(¬(A ∧ ¬B ) ∧ ¬A) ∧ ¬A)