Lista 1 Resolvida de Lógica Proposicional

Prévia do material em texto

Universidade Federal do Rio Grande do Sul
Instituto de Informática
Departamento de Informática Teórica
INF05508 – Lógica para Computação
2018/1
André Grahl Pereira
Lista 1 – Lógica Proposicional
Entrega: 05/04/2018
• Os exercícios podem ser resolvidos com colaboração, mas a entrega é individual informando even-
tuais colaboradores.
• A entrega é feita pelo Moodle com um único arquivo em formato PDF preferencialmente não
escrito a mão. Se escrito a mão a letra deve ser legível.
• O nome do arquivo deve ser “l1_número do cartão do aluno”.
• As folhas de respostas devem conter a resolução das questões na ordem apresentada no enunciado.
• Para receber pontos todas as respostas devem ser justificadas.
• Somente entregue respostas se você sabe explicar pessoalmente.
Questão 1.
Dadas as fórmulas abaixo, remova os parênteses desnecessários de forma a gerar uma fórmula equiva-
lente:
(a) (p→ (q → (p ∧ q))).
p→ (q → (p ∧ q)) pois (→) é associativa à direita.
p→ q → (p ∧ q) pois (→) é associativa à direita.
p→ q → p ∧ q pois (∧) precede (→).
(b) (¬(p ∨ (q ∧ r))).
¬(p ∨ (q ∧ r)).
(c) ((p ∧ (p→ q))→ q).
(p ∧ (p→ q))→ q.
p ∧ (p→ q)→ q pois (∧) precede (→).
(d) ((p ∨ q) ∨ (r ∨ s)).
(p ∨ q) ∨ (r ∨ s).
Questão 2.
Desenhe as árvores sintáticas das fórmulas abaixo e liste as subfórmulas:
(a) (p→ q) ∧ ¬(r ∨ p→ q).
(b) p ∨ (¬q → p ∧ q).
(a) (b)
∧
→
p q
¬
→
∨
r p
q
∨
p →
¬
q
∧
p q
Universidade Federal do Rio Grande do Sul
Instituto de Informática
Departamento de Informática Teórica
INF05508 – Lógica para Computação
2018/1
André Grahl Pereira
Questão 3.
Use os símbolos ¬, →, ∧ e ∨ para expressar as frases declarativas a seguir em lógica proposicional,
colocando o significado de cada proposição atômica utilizada (p, q, . . . ):
(a) Se eu estou contente, você não está contente e se você não está contente, eu não estou contente.
e = “Eu estou contente”.
v = “Você está contente”.
(e→ ¬v) ∧ (¬v → ¬e)
(b) A novela será exibida a menos que seja exibido o programa político.
n = “A novela será exibida”.
p = “O programa político será exibido”.
p→ ¬n (que equivale a n→ ¬p).
Questão 4.
Formalize os seguintes argumentos utilizando sequentes (`), colocando o significado de cada proposição
atômica utilizada (p, q, . . . ):
(a) Se o tanque está sem combustível, o carro não anda. O tanque está sem combustível. Logo, o carro
não anda.
t = “O tanque está sem combustível”.
c = “O carro anda”.
t→ ¬c , t ` ¬c.
(b) Quando vejo a porta amarela, entro na porta azul ou vermelha. Vejo a porta azul caso entro na
porta vermelha ou amarela. Entro na porta vermelha. Não vejo tanto a porta vermelha quanto a
porta azul. Logo, vejo a porta azul.
vcor = “Vejo a porta cor ”.
ecor = “Entro na porta cor ”.
Sejam:
A = vamarela → (eazul ∨ evermelha)
B = (evermelha ∨ eamarela)→ vazul
C = evermelha
D = ¬vvermelha ∧ ¬vazul
Temos: A,B,C,D ` vazul.
Universidade Federal do Rio Grande do Sul
Instituto de Informática
Departamento de Informática Teórica
INF05508 – Lógica para Computação
2018/1
André Grahl Pereira
Questão 5.
Determine se as seguintes fórmulas são tautologias, insatisfazíveis, contingentes, falsificáveis ou satisfa-
zíveis, usando o método da tabela-verdade:
(a) ((¬p→ q)→ (¬q → p)) ∧ (p ∨ q).
p q ¬p ¬q
A︷ ︸︸ ︷¬p→ q B︷ ︸︸ ︷¬q → p A→ B C︷ ︸︸ ︷p ∨ q (A→ B) ∧ C
0 0 1 1 0 0 1 0 0
0 1 1 0 1 1 1 1 1
1 0 0 1 1 1 1 1 1
1 1 0 0 1 1 1 1 1
Contingente, satisfazível e falsificável.
(b) (p→ (q ∧ r))→ ((p ∧ q)→ r).
p q r q ∧ r p ∧ q
A︷ ︸︸ ︷
p→ (q ∧ r)
B︷ ︸︸ ︷
(p ∧ q)→ r A→ B
0 0 0 0 0 1 1 1
0 0 1 0 0 1 1 1
0 1 0 0 0 1 1 1
0 1 1 1 0 1 1 1
1 0 0 0 0 0 1 1
1 0 1 0 0 0 1 1
1 1 0 0 1 0 0 1
1 1 1 1 1 1 1 1
Tautologia e satisfazível.
Questão 6.
Prove ou refute as seguintes consequências lógicas, usando tabela-verdade:
(a) p→ (q ∧ ¬p) � (p→ ¬q) ∧ (p→ q).
p q ¬p q ∧ ¬p
Γ︷ ︸︸ ︷
p→ (q ∧ ¬p) ¬q
A︷ ︸︸ ︷
p→ ¬q
B︷ ︸︸ ︷
p→ q
X︷ ︸︸ ︷
A ∧B
0 0 1 0 1 1 1 1 1
0 1 1 1 1 0 1 1 1
1 0 0 0 0 1 1 0 0
1 1 0 0 0 0 0 1 0
Como ∀ valoração V temos que V (Γ) = V (X), então Γ � X.
(b) (p→ q)→ ¬q � (p ∧ ¬q)→ ¬p.
p q p→ q ¬q
Γ︷ ︸︸ ︷
(p→ q)→ ¬q) p ∧ ¬q ¬p
X︷ ︸︸ ︷
(p ∧ ¬q)→ ¬p
0 0 1 1 1 0 1 1
0 1 1 0 0 0 1 1
1 0 0 1 1 1 0 0
1 1 1 0 0 0 0 1
Como existe valoração V (p = 1, q = 0) tal que V (Γ) = 1 6= 0 = V (X), então Γ 2 X.
Universidade Federal do Rio Grande do Sul
Instituto de Informática
Departamento de Informática Teórica
INF05508 – Lógica para Computação
2018/1
André Grahl Pereira
Questão 7.
Prove os seguintes sequentes usando dedução natural aplicando apenas as regras ∧i,∧e1,2,¬¬i,¬¬e,→e
e MT :
(a) (p ∧ q) ∧ r, s ∧ t ` ¬¬(q ∧ s).
1 (p ∧ q) ∧ r PREMISSA
2 s ∧ t PREMISSA
3 p ∧ q ∧e1 1
4 q ∧e2 3
5 s ∧e1 2
6 q ∧ s ∧i 4,5
7 ¬¬(q ∧ s) ¬¬i 6
(b) ¬p,¬¬q,¬p ∧ q → r ∨ ¬p ` r ∨ ¬p.
1 ¬p PREMISSA
2 ¬¬q PREMISSA
3 ¬p ∧ q → r ∨ ¬p PREMISSA
4 q ¬¬e 2
5 ¬p ∧ q ∧i 1,4
6 r ∨ ¬p →e 5,3
(c) p ∧ (q → r),¬r ` ¬q.
1 p ∧ (q → r) PREMISSA
2 ¬r PREMISSA
3 q → r ∧e2 1
4 ¬q MT 3,2
(d) ¬p→ q,¬q ` p.
1 ¬p→ q PREMISSA
2 ¬q PREMISSA
3 ¬¬p MT 1,2
4 p ¬¬e 3
Questão 8.
Prove os seguintes sequentes usando dedução natural aplicando apenas as regras básicas, sem regras
derivadas i.e. ¬¬i,MT, PPC e LEM :
(a) ` (p ∧ q)→ p.
1 p ∧ q HIPÓTESE
p ∧e1 12
3 (p ∧ q)→ p →i 1-2
Universidade Federal do Rio Grande do Sul
Instituto de Informática
Departamento de Informática Teórica
INF05508 – Lógica para Computação
2018/1
André Grahl Pereira
(b) p→ (q ∨ r), q → s, r → s ` p→ s.
1 p→ (q ∨ r) PREMISSA
2 q → s PREMISSA
3 r → s PREMISSA
4 p HIPÓTESE
q ∨ r →e 4,1
q HIPÓTESE
s →e 6,2
r HIPÓTESE
s →e 8,3
s ∨e 5, 6-7,8-9
5
6
7
8
9
10
11 p→ s →i 4-10
(c) ¬p, p ∨ q ` q.
1 ¬p PREMISSA
2 p ∨ q PREMISSA
3 p HIPÓTESE
⊥ ¬e 3,1
q ⊥e 4
4
5
6 q HIPÓTESE
7 q ∨e 2, 3-5,6-6
(d) ¬p ∧ ¬q ` ¬(p ∨ q).
1 ¬p ∧ ¬q PREMISSA
2 ¬p ∧e1 1
3 ¬q ∧e2 1
4 p ∨ q HIPÓTESE
p HIPÓTESE
⊥ ¬e 5,2
q HIPÓTESE
⊥ ¬e 7,3
⊥ ∨e 4, 5-6,7-8
5
6
7
8
9
10 ¬(p ∨ q) ¬i 4-9
(e) ` ¬p→ (p→ (p→ q)).
1 ¬p HIPÓTESE
p HIPÓTESE
⊥ ¬e 2,1
p→ q ⊥e 3
p→ (p→ q) →i 2-4
2
3
4
5
6 ¬p→ (p→ (p→ q)) →i 1-5
(f) p→ (q ∨ r),¬q,¬r ` ¬p.
Universidade Federal do Rio Grande do Sul
Instituto de Informática
Departamento de Informática Teórica
INF05508 – Lógica para Computação
2018/1
André Grahl Pereira
1 p→ (q ∨ r) PREMISSA
2 ¬q PREMISSA
3 ¬r PREMISSA
4 p HIPÓTESE
q ∨ r →e 4,1
q HIPÓTESE
⊥ ¬e 6,2
r HIPÓTESE
⊥ ¬e 8,3
⊥ ∨e 5, 6-7, 8-9
5
6
7
8
9
10
11 ¬p ¬i 4-10
(g) (p→ q) ∧ (p→ ¬q) a` ¬p.
1) Provar `
1 (p→ q) ∧ (p→ ¬q) PREMISSA
2 p→ q ∧e1 1
3 p→ ¬q ∧e2 1
4 p HIPÓTESE
q →e 4,2
¬q →e 4,3
⊥ ¬e 5,6
5
6
7
8 ¬p ¬i 4-7
2) Provar a
1 ¬p PREMISSA
2 p HIPÓTESE
⊥ ¬e 2,1
q ⊥e 3
3
4
5 p→ q →i 2-4
6 p HIPÓTESE
⊥ ¬e 6,1
¬q ⊥e 7
7
8
9 p→ ¬q →i 6-9
10 (p→ q) ∧ (p→ ¬q) ∧i 5,9
(h) ` ((p→ q)→ q)→ ((q → p)→ p).
Universidade Federal do Rio Grande do Sul
Instituto de Informática
Departamento de Informática Teórica
INF05508 – Lógica para Computação
2018/1
André Grahl Pereira
1 (p→ q)→ q HIPÓTESE
q → p HIPÓTESE
¬p HIPÓTESE
q HIPÓTESE
p →e 2,4
⊥ ¬e 5,3
¬q ¬i 4,6
p→ q HIPÓTESE
q →e 1,8
⊥ ¬e 9,7
¬(p→ q) ¬i 8-9
p HIPÓTESE
⊥ ¬e 12,3
q ⊥e 13
p→ q →i 12-14
⊥ ¬e 15,11
¬¬p ¬i 3,16
p ¬¬e 17
(q → p)→ p →i 2-18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 ((p→ q)→ q)→ ((q → p)→ p) →i 1-19