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

Prévia do material em texto

Lo´gica Computacional
Gabarito da Primeira Prova
To´picos: Lo´gica proposicional
Semaˆntica e Deduc¸a˜o
Instituto de Cieˆncias Exatas, Universidade de Bras´ılia
24 de novembro de 2010
Prof. Mauricio Ayala-Rinco´n
Monitor: Andre´ Figueira Lourenc¸o
Nome: Matr´ıcula:
Durac¸a˜o: 100 min.
Inicio: 16:00; Fim: 17:45
Duas Pa´ginas, treˆs questo˜es
Deduc¸a˜o natural
1. (4.0 pontos) Construa deduc¸o˜es da seguinte versa˜o de uma das Leis de De Morgan:
¬(¬p ∧ ¬q) a` p ∨ q
(a) (2.0 pontos) Construa uma prova por deduc¸a˜o natural, indicando o nome das regras uti-
lizadas e as suposic¸o˜es descarregadas, de
p ∨ q ` ¬(¬p ∧ ¬q)
R/
p ∨ q
[¬p ∧ ¬q]u
¬p ∧e1 [p]x
⊥ ¬e
[¬p ∧ ¬q]u
¬q ∧e2 [q]y
⊥ ¬e
⊥ ∨e, x, y
¬(¬p ∧ ¬q) ¬i, u
(b) (2.0 pontos) Construa uma prova por deduc¸a˜o natural, indicando o nome das regras uti-
lizadas e as suposic¸o˜es descarregadas, de
¬(¬p ∧ ¬q) ` p ∨ q
R/
q ∨ ¬q LEM
[q]x
p ∨ q ∨i
¬(¬p ∧ ¬q)
[¬p]u [¬q]y
¬p ∧ ¬q ∧i
⊥ ¬e
p PBC, u
p ∨ q ∨i
p ∨ q ∨e, x, y
Semaˆntica
2. (3.0 pontos) Dado um sequente φ ` ψ, podemos verificar sua validade de duas formas, com duas
etapas cada:
(a) Determinando que
i. φ→ ψ e´ uma tautologia e,
ii. enta˜o, concluindo que o sequente ` φ→ ψ e´ va´lido.
(b) Determinando que
i. ¬(φ→ ψ) na˜o e´ satisfat´ıvel e,
ii. enta˜o, concluindo que ` φ→ ψ e´ va´lida.
Utilizando tabelas de verdade e os teoremas de Correc¸a˜o/Completude, decida e justifique a
validade dos sequentes abaixo:
(a) (1.5 pontos) p→ q ` ¬q → ¬p atrave´s do me´todo ??. Discrimine, na sua resposta, os dois
passos deste me´todo.
R/ Seguindo o me´todo i) temos: ` (p → q) → (¬q → ¬p). Podemos, enta˜o, construir a
tabela de verdade, considerando φ→ ψ : (p→ q) → (¬q → ¬p):
p ¬p q ¬q p→ q ¬q → ¬p φ→ ψ
T F T F T T T
T F F T F F T
F T T F T T T
F T F T T T T
Como φ → ψ possui todas as suas avaliac¸o˜es T, podemos concluir que � φ → ψ e´ va´lido,
isto e´, φ→ ψ e´ uma tautologia (1). Assim, pelo Teorema da Completude, conclu´ımos que
` φ→ ψ e´ va´lido (2).
(b) (1.5 pontos) ¬(p → q) ` q → p atrave´s do me´todo ??. Discrimine, na sua resposta, os
dois passos deste me´todo.
R/ Seguindo o me´todo ii) temos: ` ¬(¬(p → q) → (q → p)). Podemos, enta˜o, construir a
tabela de verdade, considerando ¬(φ→ ψ) : ¬(¬(p→ q) → (q → p)):
p q p→ q ¬(p→ q) q → p ¬(φ→ ψ)
T T T F T F
T F F T T F
F T T F F F
F F T F T F
Como ¬(φ→ ψ) possui todas as suas avaliac¸o˜es F, podemos concluir que � ¬(φ→ ψ) na˜o
e´ satisfat´ıvel (1). No entanto, φ → ψ possui todas as suas avaliac¸o˜es T, logo � φ → ψ e´
va´lida. Assim, pelo Teorema da Completude, conclu´ımos que ` φ→ ψ e´ va´lida (2).
Satisfazibilidade
¬
¬
∧
}}
}}
}}
}}
}}
}}
}}
}}
}}
PPP
PPP
PPP
PPP
PP
¬
¬ ¬
∧
}}
}}
}}
}
AA
AA
AA
A ∧
}}
}}
}}
}
AA
AA
AA
A
¬
@@
@@
@@
@@
¬
PPP
PPP
PPP
PPP
PP ¬
iiii
iiii
iiii
iiii
iiii
i ¬
nnn
nnn
nnn
nnn
nn
p q
Figure 1: DAG para ¬¬(¬(¬p ∧ ¬q) ∧ ¬¬(¬p ∧ ¬q))
3. (3.0 pontos) Utilize a te´cnica de solucionador SAT para demonstrar que a Lei de De Morgan
(p ∨ q) → ¬(¬p ∧ ¬q)
do exerc´ıcio ?? e´ va´lida; i.e., demonstre que a sua negac¸a˜o, ¬((p ∨ q) → ¬(¬p ∧ ¬q)), e´ insatis-
faz´ıvel, conforme o seguinte roteiro:
(a) (0.5) Apresente todos os passos da aplicac¸a˜o da transformac¸a˜o T a` negac¸a˜o da Lei de De
Morgan acima de forma a obter a fo´rmula equivalente no fragmento negativo-conjuntivo da
lo´gica 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)) =
¬¬(¬(¬p ∧ ¬q) ∧ ¬¬(T (¬p) ∧ T (¬q)) =
¬¬(¬(¬p ∧ ¬q) ∧ ¬¬(¬T (p) ∧ ¬T (q)) =
¬¬(¬(¬p ∧ ¬q) ∧ ¬¬(¬p ∧ ¬q))
(b) (0.5) Construa um DAG para esta fo´rmula;
R/ Veja figura ??.
(c) (2.0) Utilizando a te´cnica de solucionadores SAT, demonstre que esta´ fo´rmula e´ insatis-
faz´ıvel.
¬ 1: T
¬ 2: F
∧
}}
}}
}}
}}
}}
}}
}}
}}
}}
PPP
PPP
PPP
PPP
PP3: T
¬ 4: T
¬ 4: T ¬ 5: F
∧
}}
}}
}}
}
AA
AA
AA
A
5: F 10: T ∧
}}
}}
}}
}
AA
AA
AA
A
6: T
¬
@@
@@
@@
@@
9: T ¬
PPP
PPP
PPP
PPP
PP9: T ¬
iiii
iiii
iiii
iiii
iiii
i 7: T ¬
nnn
nnn
nnn
nnn
nn
7: T
p 8: F q 8: F
Figure 2: Verificac¸a˜o da insatisfazibilidade de ¬¬(¬(¬p ∧ ¬q) ∧ ¬¬(¬p ∧ ¬q))
R/ Aplicando o me´todo SAT na figura ??, obtem-se uma contradic¸a˜o na de´cima iterac¸a˜o
(veja figura ??), o que implica a insatisfazibilidade da negac¸a˜o da fo´rmula.