Exercícios resolvidos de Lógica Computacional - Lista 3

Prévia do material em texto

Soluc¸o˜es da Terceira Lista de Exerc´ıcios - Lo´gica
Computacional
Universidade de Bras´ılia - UnB
Instituto de Cieˆncias Exatas
Departamento de Ciencia da Computac¸a˜o - CIC
Andre´ Figueira Lourenc¸o
Mauricio Ayala Rinco´n
1. (a) q ∨ (¬p ∨ r)
p ¬p q r ¬p ∨ r q ∨ r q ∨ (¬p ∨ r) p→ (q ∨ r)
T F T T T T T T
T F T F F T T T
T F F T T T T T
T F F F F F F F
F T T T T T T T
F T T F T T T T
F T F T T T T T
F T F F T F T T
* E´ equivalente.
(b) (q ∧ ¬r)→ p
p q r ¬r q ∧ ¬r (q ∧ ¬r)→ p p→ (q ∨ r)
T T T F F T T
T T F T T T T
T F T F F T T
T F F T F T© F©
F T T F F T T
F T F T T F© T©
F F T F F T T
F F F T F T T
* Na˜o e´ equivalente.
1
(c) (p ∧ ¬r)→ q
p q r ¬r p ∧ ¬r (p ∧ ¬r)→ q p→ (q ∨ r)
T T T F F T T
T T F T T T T
T F T F F T T
T F F T T F F
F T T F F T T
F T F T F T T
F F T F F T T
F F F T F T T
* E´ equivalente.
(d) (¬q ∧ ¬r)→ ¬p
¬p ¬q ¬r p ∧ ¬r (p ∧ ¬r)→ q p→ (q ∨ r)
F F F F T T
F F T F T T
F T F F T T
F T T T F F
T F F F T T
T F T F T T
T T F F T T
T T T T T T
* E´ equivalente.
2
2. De acordo com o teorema da completude se � φ e´ va´lida enta˜o ` φ tambe´m e´ va´lida. Para provar a
validade de � (p→ q) ∨ (r → p) basta provar que ¬((p→ q) ∨ (r → p)) na˜o e´ satisfat´ıvel, isto e´, todas
suas avaliac¸o˜es sa˜o F e, portanto, todas as avaliac¸o˜es da fo´rmula sem a negac¸a˜o sa˜o T.
φ : ¬((p→ q) ∨ (r → p))
T (φ) : T (¬((p→ q) ∨ (r → p)))
T (φ) : ¬T ((p→ q) ∨ (r → p))
T (φ) : ¬¬(¬T (p→ q) ∧ ¬T (r → p))
T (φ) : ¬¬(¬¬(T (p) ∧ ¬T (q)) ∧ ¬¬(T (r) ∧ ¬T (p)))
T (φ) : ¬¬(¬¬(p ∧ ¬q) ∧ ¬¬(r ∧ ¬p))
¬ 1: T
¬ 2: F
∧ 3: T
¬
qqqqqqqqqqqqqqq4: T ¬
NNNNNNNNNNNNNNN
4: T
¬5: F ¬ 5: F
∧6: T ∧ 6: T
¬
��������
7: T ¬
��������
7: T r
;;;;;;;;
7: T
q8: F p7: T 8: F
---------------
pppppppppppppppp
contradic¸a˜o
O DAG mostra que φ na˜o e´ satisfat´ıvel, provando tanto a validade de � (p→ q) ∨ (r → p) como de
` (p→ q) ∨ (r → p).
3
3. O DAG deve representar a seguinte fo´rmula:
φ : ¬(((p ∨ q) ∧ (p→ r))→ r)
T (φ) : T (¬(((p ∨ q) ∧ (p→ r))→ r))
T (φ) : ¬T (((p ∨ q) ∧ (p→ r))→ r)
T (φ) : ¬¬((T ((p ∨ q) ∧ (p→ r))) ∧ ¬T (r))
T (φ) : ¬¬((T (p ∨ q) ∧ T (p→ r)) ∧ ¬r)
T (φ) : ¬¬((¬(¬T (p) ∧ ¬T (q)) ∧ ¬(T (p) ∧ ¬T (r))) ∧ ¬r)
T (φ) : ¬¬((¬(¬p ∧ ¬q) ∧ ¬(p ∧ ¬r)) ∧ ¬r)
¬1: T
¬2: F
∧
00
00
00
00
00
00
00
00
00
00
00
00
00
3: T
∧
kkkkkkkkkkkkkkkkkkkkkkk4: T
¬
qqqqqqqqqqqqqqq5: T ¬
<<<<<<<<
5: T
∧6: F ∧ 6: F ¬
yy
yy
yy
yy
yy
yy
yy
yy
yy
yy
yy
yy
y
4: T
¬
��������
7: F ¬
<<<<<<<<
8: T ¬
<<<<<<<<
6: T
q8: T p
��������������������
7: F r 5: F
O DAG prova que φ e´ satisfat´ıvel (possui uma avaliac¸a˜o T), fato que indica que a fo´rmula ((p∨q)∧(p→
r)) → r possui uma avaliac¸a˜o F, portanto � ((p ∨ q) ∧ (p → r)) → r na˜o e´ va´lida. Por conseguinte,
p ∨ q, p→ r � r tambe´m na˜o e´ va´lida e, portanto, pelo teorema da correc¸a˜o, provamos que a sequente
p ∨ q, p→ r ` r na˜o e´ va´lida.
4
5. Uma tautologia e´ uma fo´rmula cujas avaliac¸o˜es sa˜o todas T, portanto, a negac¸a˜o de uma tautologia
possui apenas avalic¸o˜es F. Seja φ uma fo´rmula que queremos verificar se e´ ou na˜o uma tautologia,
usamos o SAT para verificar se ¬φ e´ satisfat´ıvel:
- Se ¬φ for satisfat´ıvel, provamos que essa fo´rmula possui uma avaliac¸a˜o T, implicando que φ possue
uma avaliac¸a˜o F e, portanto, na˜o e´ uma tautologia.
- Se ¬φ na˜o for satisfat´ıvel, provamos que essa fo´rmula na˜o possui uma avaliac¸a˜o T, implicando que
φ possue apenas avaliac¸o˜es T e, portanto, e´ uma tautologia.
6. Para simplificar a fo´rmula vamos adicionar colchetes e chaves e dividir a fo´rmula e pequenas fo´rmulas.
φ : {(p ∨ (q ∨ r)) ∧ [(p ∨ ¬q) ∧ [(q ∨ ¬r) ∧ [(r ∨ ¬p) ∧ (¬p ∨ (¬q ∨ ¬r)) ] ] ]}
φ : {φ1 ∧ [φ2 ∧ [φ3 ∧ [φ4 ∧ φ5] ] ]}
φ1 : (p ∨ (q ∨ r))
T (φ1) : T (p ∨ (q ∨ r))
T (φ1) : ¬(¬T (p) ∧ ¬T (q ∨ r))
T (φ1) : ¬(¬p ∧ ¬¬(¬T (q) ∧ ¬T (r)))
T (φ1) : ¬(¬p ∧ ¬¬(¬q ∧ ¬r))
φ2 : (p ∨ ¬q)
T (φ2) : T (p ∨ ¬q)
T (φ2) : ¬(¬T (p) ∧ ¬T (¬q))
T (φ2) : ¬(¬p ∧ ¬¬T (q))
T (φ2) : ¬(¬p ∧ ¬¬q)
φ3 : (q ∨ ¬r)
T (φ3) : T (q ∨ ¬r)
T (φ3) : ¬(¬T (q) ∧ ¬T (¬r))
T (φ3) : ¬(¬q ∧ ¬¬T (r))
T (φ3) : ¬(¬q ∧ ¬¬r)
φ4 : (r ∨ ¬p)
T (φ4) : T (r ∨ ¬p)
T (φ4) : ¬(¬T (r) ∧ ¬T (¬p))
T (φ4) : ¬(¬r ∧ ¬¬T (p))
T (φ4) : ¬(¬r ∧ ¬¬p)
φ5 : (¬p ∨ (¬q ∨ ¬r))
T (φ5) : T (¬p ∨ (¬q ∨ ¬r))
T (φ5) : ¬(¬T (¬p) ∧ ¬T (¬q ∨ ¬r))
T (φ5) : ¬(¬¬T (p) ∧ ¬¬(¬T (¬q) ∧ ¬T (¬r)))
T (φ5) : ¬(¬¬p ∧ ¬¬(¬¬T (q) ∧ ¬¬T (r)))
T (φ5) : ¬(¬¬p ∧ ¬¬(¬¬q ∧ ¬¬r))
T (φ) : {¬(¬p∧¬¬(¬q∧¬r))∧[¬(¬p∧¬¬q)∧[¬(¬q∧¬¬r)∧[¬(¬r∧¬¬p)∧¬(¬¬p∧¬¬(¬¬q∧¬¬r)) ] ]}
5