Lista01_LogicaProposicional[solucao]

Prévia do material em texto

Área de Teoria DCC/UFMG Introdução à Lógica Computacional 2020/01
SOLUÇÃO DE LISTA DE EXERCÍCIOS
Lista 01
(Lógica Proposicional)
Leitura necessária:
• Matemática Discreta e Suas Aplicações, 6a Edição (Kenneth H. Rosen):
– Caṕıtulo 1.1: Lógica Proposicional
Revisão.
1. Responda formalmente as seguintes perguntas:
(a) O que é uma proposição, e quais valores de verdade ela pode assumir?
Solução do professor: Uma proposição é uma sentença declarativa (ou seja, uma sentença
que estabelece um fato) que pode ser verdadeira ou falsa, mas não ambos.
(b) O que é uma proposição condicional? Explique quando uma proposição condicional é verdadeira,
e quando ela é falsa.
Solução do professor: Uma proposição condicional é uma proposição da forma p → q (lida
como “se p, então q”). A condicional p→ q é sempre verdadeira, a menos que a premissa p seja
verdadeira e a conclusão q seja falsa.
(c) Descreva pelo menos cinco modos diferentes de escrever o condicional p→ q em português.
Solução do professor:
(i) Se p, então q.
(ii) p somente se q.
(iii) p é suficiente para q.
(iv) q é necessário para p.
(v) q a menos que ¬p.
Exerćıcios.
2. (Rosen 1.1.1) Quais das sentenças abaixo são proposições? Qual o valor de verdade das que são
proposições?
(a) Curitiba é a capital do Paraná.
Solução do professor: É uma proposição verdadeira.
(b) Joinville é a capital de Santa Catarina.
1
Solução do professor: É uma proposição falsa.
(c) 2 + 3 = 5
Solução do professor: É uma proposição verdadeira.
(d) 5 + 7 = 10
Solução do professor: É uma proposição falsa.
(e) x + 2 = 11
Solução do professor: Não é uma proposição.
(f) Responda a esta questão.
Solução do professor: Não é uma proposição.
3. (Rosen 1.1.5) Considere que p e q são as proposições: “Nadar na praia em Nova Jersey é permitido” e
“Foram descobertos tubarões perto da praia”, respectivamente. Expresse cada uma dessas proposições
compostas como uma sentença em português.
(a) ¬q
Solução do professor: “Não foram descobertos tubarões perto da praia.”
(b) p ∧ q
Solução do professor: “Nadar na praia em Nova Jersey é permitido, e foram descobertos
tubarões perto da praia.”
(c) ¬p ∨ q
Solução do professor: “Nadar na praia em Nova Jersey não é permitido ou foram descobertos
tubarões perto da praia.”
(d) p→ ¬q
Solução do professor: “Se nadar na praia em Nova Jersey é permitido então não foram
descobertos tubarões perto da praia.”
(g) p↔ ¬q
Solução do professor: “Nadar na praia em Nova Jersey é permitido se, e somente se, não
foram descobertos tubarões perto da praia.”
(h) ¬p ∧ (p ∨ ¬q)
2
Solução do professor: “Nadar na praia em Nova Jersey não é permitido, e ou nadar na praia
em Nova Jersey é permitido ou foram descobertos tubarões perto da praia.”
4. (Rosen 1.1.7) Considere que p e q são as proposições:
p: “Está abaixo de zero.”
q: “Está nevando.”
Escreva estas proposições usando p, q e conectivos lógicos.
(a) Está abaixo de zero e nevando.
Solução do professor: p ∧ q.
(b) Está abaixo de zero, mas não está nevando.
Solução do professor: p ∧ ¬q.
(c) Não está abaixo de zero e não está nevando.
Solução do professor: ¬p ∧ ¬q.
(d) Está nevando ou abaixo de zero (ou os dois).
Solução do professor: p ∨ q.
(e) Se está abaixo de zero, está também nevando.
Solução do professor: p→ q.
(f) Está ou nevando ou abaixo de zero, mas não está nevando se estiver abaixo de zero.
Solução do professor: (p ∨ q) ∧ (p→ ¬q).
(g) Para que esteja nevando é necessário, e suficiente, que esteja nevando.
Solução do professor: q ↔ p.
5. (Rosen 1.1.11) Sejam p, q e r as seguintes proposições:
p: “Ursos-cinzentos são vistos na área.”
q: “Fazer caminhada na trilha é seguro.”
r: “As bagas estão maduras ao longo da trilha.”
Escreva as seguintes proposições utilizando p, q, r e conectivos lógicos.
(a) As bagas estão maduras ao longo da trilha, mas os ursos-cinzentos não são vistos na área.
Solução do professor: r ∧ ¬p
(b) Ursos-cinzentos não são vistos na área e fazer caminhada na trilha é seguro, mas as bagas estão
maduras ao longo da trilha.
3
Solução do professor: ¬p ∧ q ∧ r
(c) Se as bagas estão maduras ao longo da trilha, fazer caminhada é seguro se, e somente se, ursos-
cinzentos não forem vistos na área.
Solução do professor: r → (q ↔ ¬p)
(d) Não é seguro fazer caminhada na trilha, mas os ursos-cinzentos não são vistos na área e as bagas
ao longo da trilha estão maduras.
Solução do professor: ¬q ∧ ¬p ∧ r
(e) Para a caminhada ser segura, é necessário, mas não suficiente que as bagas não estejam maduras
ao longo da trilha e que os ursos-cinzentos não sejam vistos na área.
Solução do professor: q → (¬r ∧ ¬q) ∧ ¬((¬r ∧ ¬p)→ q)
(f) Caminhada não é segura ao longo da trilha sempre que os ursos-cinzentos são vistos na área e as
bagas estão maduras ao longo da trilha.
Solução do professor: p ∧ r → ¬q
6. (Rosen 1.1.13) Determine se cada uma destas proposições condicionais é verdadeira ou falsa.
(a) Se 1 + 1 = 2, então 2 + 2 = 5.
Solução do professor: A implicação é falsa, já que a premissa é verdadeira e a conclusão é
falsa.
(b) Se 1 + 1 = 3, então 2 + 2 = 4.
Solução do professor: A implicação é verdadeira, já que a premissa é falsa.
(c) Se 1 + 1 = 3, então 2 + 2 = 5.
Solução do professor: A implicação é verdadeira, já que a premissa é falsa.
(d) Se macacos puderem voar, então 1 + 1 = 3.
Solução do professor: A implicação é verdadeira, já que a premissa é falsa.
7. (Rosen 1.1.17) Reescreva cada sentença em português explicitando o que ela significa caso o “ou”
utilizado seja inclusivo (ou seja, uma disjunção), e o que ela significa caso o “ou” utilizado seja
exclusivo. Quais dos significados do “ou” você acha que o autor queria usar?
(a) Para cursar matemática discreta, você deve ter tido cálculo ou um curso de ciência da computação.
4
Solução do professor: Ou inclusivo: Para cursar matemática discreta você deve ter tido ao
menos um dos dois cursos entre cálculo e ciência da computação.
Ou exclusivo: Para cursar matemática discreta você deve ter tido cálculo ou um curso de ciência
da computação, mas não ambos.
Intenção presumida: provavelmente a intenção era usar o ou inclusivo.
(b) Quando você compra um novo carro da Companhia Acme Motor, você pega de volta $ 2.000 ou
um empréstimo de 2%.
Solução do professor: Ou inclusivo: Quando você compra um novo carro da Companhia
Acme Motor, você pega de volta $ 2.000 ou um empréstimo de 2%, ou ambos.
Ou exclusivo: Quando você compra um novo carro da Companhia Acme Motor, você ou pega de
volta $ 2.000 ou um empréstimo de 2%, mas não ambos.
Intenção presumida: provavelmente a intenção era usar o ou exclusivo.
8. (Rosen 1.1.19) Escreva cada uma das proposições abaixo na forma “se p, então q” em português.
(a) Neva sempre que o vento sopra do nordeste.
Solução do professor: Se o vento sopra do nordeste, então neva.
(d) É necessário andar 8 milhas para chegar ao topo de Long’s Peak.
Solução do professor: Se você chegou ao topo de Long’s Peak, então você andou 8 milhas.
(e) Para ser efetivado como professor, é suficiente ser famoso mundialmente.
Solução do professor: Se você for famoso mundialmente, então você é efetivado como profes-
sor.
(g) Sua garantia é válida apenas se você comprou seu aparelho de som há menos de 90 dias.
Solução do professor: Se sua garantia é válida, então você comprou seu aparelho de som há
menos de 90 dias.
(h) Jan nadará a menos que a água esteja muito fria.
Solução do professor: Se a água não estiver muito fria, então Jan nadará.
9. (Rosen 1.1.23) Determine a oposta, a contrapositiva e a inversa de cada uma das proposições condici-
onais.
(a) Se nevar hoje, esquiarei amanhã.
Solução do professor: Oposta:Vai nevar hoje somente se eu esquiar amanhã.
Contrapositiva: Se eu não esquiar amanhã, não nevou hoje.
Inversa: Se não nevar hoje, não esquiarei amanhã.
(b) Eu venho à aula sempre que há uma prova.
5
Solução do professor: Oposta: Se eu venho à aula, então há uma prova.
Contrapositiva: Se eu não venho à aula, então não há uma prova.
Inversa: Se não há uma prova, eu não venho à aula.
10. (Rosen 1.1.27) Construa a tabela da verdade para cada uma das proposições compostas abaixo.
(a) (Rosen 1.1.27, item (c)) (p ∨ ¬q)→ q
Solução do professor:
p q ¬q p ∨ ¬q (p ∨ ¬q)→ q
T T F T T
T F T T F
F T F F T
F F T T F
(b) (Rosen 1.1.27, item (e)) (p→ q)↔ (¬q → ¬p)
Solução do professor:
p q (p→ q) ¬q ¬p ¬q → ¬q (p→ q)↔ (¬q → ¬p)
T T T F F T T
T F F T F F T
F T T F T T T
F F T T T T T
(c) (Rosen 1.1.29, item (b)) (p⊕ q)→ (p ∧ q)
Solução do professor:
p q p⊕ q p ∧ q (p⊕ q)→ (p ∧ q)
T T F T T
T F T F F
F T T F F
F F F F T
11. (Rosen 1.1.38) Dê os valores de cada uma destas expressões.
(a) 11000 ∧ (01011 ∨ 11011)
(c) (01010⊕ 11011)⊕ 01000
Solução do professor:
(a) 11000 ∧ (01011 ∨ 11011) = 11000 ∧ (11011) = 11000
(c) (01010⊕ 11011)⊕ 01000 = (10001)⊕ 01000 = 11001
6
12. (Rosen, 8th Edition, 1.2.9) Determine se as seguintes especificações de um sistema são consistentes.
“O sistema está no estado multiusuário se, e somente se, estiver operando normalmente. Se o sistema
estiver operando normalmente, o kernel está funcionando. O kernel não está funcionando ou o sistema
está no modo de interrupção. Se o sistema não estiver no estado multiusuário, então está no modo
de interrupção. O sistema não está no modo de interrupção.”
Solução do professor: Para determinar se essas especificações são consistentes, primeiro vamos
representá-las como expressões lógicas. Sejam as seguintes proposições atômicas:
m : “O sistema está no modo multiusuário.”
n : “O sistema está operando normalmente.”
k : “O kernel está funcionando.”
i : “O sistema está no modo de interrupção.”
As especificações do sistema podem ser modeladas como:
• m↔ n • n→ k • ¬k ∨ i • ¬m→ i • ¬i
Para verificar se as especificações são consistentes, vamos usar uma tabela da verdade para checar se
alguma atribuição de valores de verdade às proposições atômicas satisfaz todos os requisitos.
m n k i m↔ n n→ k ¬k ∨ i ¬m→ i ¬i
T T T T T T T T F
T T T F T T F T T
T T F T T F T T F
T T F F T F T T T
T F T T F T T T F
T F T F F T F T T
T F F T F T T T F
T F F F F T T T T
F T T T F T T T F
F T T F F T F F T
F T F T F F T T F
F T F F F F T F T
F F T T T T T T F
F F T F T T F F T
F F F T T T T T F
F F F F T T T F T
Pode-se notar que é imposśıvel satisfazer todos os requisitos ao mesmo tempo e, portanto, a especi-
ficação do sistema é inconsistente.
7