AD1-MD-2013-2-resoluções

Prévia do material em texto

Matema´tica Discreta – AD1 – 2013/2
Resoluc¸o˜es
1. Considere os enunciados a seguir, formados pela aplicac¸a˜o de conectivos a enunciados
atoˆmicos:
(a) Irei ao Polo na segunda, mas na˜o na quarta e nem no sa´bado.
(b) Na segunda havera´ tutoria de Pre´-ca´lculo ou de Discreta e, com certeza, de Geo-
metria.
(c) Nem na quarta nem no sa´bado havera´ tutoria de Discreta.
(d) Eu na˜o me matriculei em Ca´lculo, pois vou me dedicar a` Discreta e a` Geometria.
Para cada enunciado, determine uma legenda e simbolize-o, de acordo com a legenda
dada.
Resoluc¸a˜o da Questa˜o 1:
(a) Considerando a legenda:
s : irei ao Polo na segunda
q : irei ao Polo na quarta
b : irei ao Polo no sa´bado
o enunciado pode ser simbolizado por:
s ∧ (¬q ∧ ¬b).
(b) Considerando a legenda:
p : na segunda havera´ tutoria de Pre´-ca´lculo
d : na segunda havera´ tutoria de Discreta
g : na segunda havera´ tutoria de Geometria
o enunciado pode ser simbolizado por:
(p ∨ d) ∧ g.
(c) Considerando a legenda:
q : na quarta havera´ tutoria Discreta
s : no sa´bado havera´ tutoria de Discreta
o enunciado pode ser simbolizado por:
¬q ∧ ¬s.
(d) Considerando a legenda:
c : eu me matriculei em Ca´lculo
d : eu vou me dedicar a` Discreta
g : eu vou me dedicar a` Geometria
o enunciado pode ser simbolizado por:
d ∧ g → ¬c.
1
2. Uma aluna ouviu o seguinte enunciado nos corredores do Polo, dito por um tutor:
Desorganizac¸a˜o, falta de tempo e preguic¸a, atrapalham os estudos.
Mas isto e´ falso, ela disse para uma colega, basta uma destas coisas para atrapalhar
os estudos. E´ verdade, concordou colega, e´ exatamente a negac¸a˜o do que ele esta´
dizendo o que acontece.
(a) Determine uma u´nica legenda e simbolize cada um dos seguintes enunciados, de
acordo com a legenda dada:
(i) o enunciado que a aluna ouviu;
(ii) o enunciado que ela considera ser o correto;
(iii) o enunciado que a amiga considera ser o correto.
(b) Determine se os enunciados que a aluna e a amiga consideram serem os corretos
sa˜o equivalentes ou na˜o.
Resoluc¸a˜o da Questa˜o 2:
(a) Consideremos a legenda:
d : desorganizac¸a˜o atrapalha os estudos
f : falta de tempo atrapalha os estudos
p : preguic¸a atrapalha os estudos
(i) O enunciado que a aluna ouviu pode ser simbolizado por:
d ∧ (f ∧ p).
(ii) O enunciado que a aluna considera ser o correto pode ser simbolizado por:
d ∨ (f ∨ p).
(iii) O enunciado que a amiga considera ser o correto pode ser simbolizado por:
¬[d ∧ (f ∧ p)].
(b) Considere a seguinte tabela conjunta dos enunciados d∨ (f ∨ p) e ¬[d∧ (f ∧ p)]:
d f p f ∨ p
ϕ1︷ ︸︸ ︷
d ∨ (f ∨ p) f ∧ p
ϕ2︷ ︸︸ ︷
d ∧ (f ∧ p) ¬ϕ2 ϕ1 ↔ ¬ϕ2
V V V V V V V F F
V V F V V F F V V
V F V V V F F V V
V F F F V F F V V
F V V V V V F V V
F V F V V F F V V
F F V V V F F V V
F F F F F F F V F
Como ϕ1 ↔ ¬ϕ2 na˜o e´ uma tautologia, os enunciados na˜o sa˜o equivalentes.
2
3. Considere a seguinte sequeˆncia de equivaleˆncias, que mostra que os enunciados
(a ∧ (¬b ∨ c)) ∨ (¬a ∧ c) ∨ ((a ∨ ¬b) ∧ ¬a) e ¬b ∨ c sa˜o equivalentes:
(a ∧ (¬b ∨ c)) ∨ (¬a ∧ c) ∨ ((a ∨ ¬b) ∧ ¬a)
e´ equivalente a
(a ∧ ¬b) ∨ (a ∧ c) ∨ (¬a ∧ c) ∨ ((a ∨ ¬b) ∧ ¬a)
e´ equivalente a
(a ∧ ¬b) ∨ (a ∧ c) ∨ (¬a ∧ c) ∨ (a ∧ ¬a) ∨ (¬b ∧ ¬a)
e´ equivalente a
(a ∧ ¬b) ∨ (a ∧ c) ∨ (¬a ∧ c) ∨ (¬b ∧ ¬a)
e´ equivalente a
(a ∧ ¬b) ∨ (a ∧ c) ∨ (¬a ∧ c) ∨ (¬a ∧ ¬b)
e´ equivalente a
(a ∧ ¬b) ∨ (a ∧ c) ∨ (¬a ∧ ¬b) ∨ (¬a ∧ c)
e´ equivalente a
[(a ∧ ¬b) ∨ (a ∧ c)] ∨ [(¬a ∧ ¬b) ∨ (¬a ∧ c)]
e´ equivalente a
[a ∧ (¬b ∨ c)] ∨ [(¬a ∧ ¬b) ∨ (¬a ∧ c)]
e´ equivalente a
[a ∧ (¬b ∨ c)] ∨ [¬a ∧ (¬b ∨ c)]
e´ equivalente a
(a ∨ ¬a) ∧ (¬b ∨ c)
e´ equivalente a
¬b ∨ c
Explicite as equivaleˆncias usadas em cada passo.
Resoluc¸a˜o da Questa˜o 3:
Nos passos acima, foram usadas:
(1) Distributividade do ∧ sobre o ∨,
(2) Distributividade do ∧ sobre o ∨,
(3) Elemento neutro do ∨,
(4) Comutatividade de ∧,
(5) Comutatividade de ∨,
(6) Associatividade do ∨,
(7) Distributividade do ∧ sobre o ∨,
(8) Distributividade do ∧ sobre o ∨,
(9) Distributividade do ∧ sobre o ∨,
(10) Elemento neutro do ∧.
3
4. Mostre que os seguintes enunciados sa˜o equivalentes, usando uma sequeˆncia de equi-
valeˆncias. Explicite as equivaleˆncias usadas em cada passo.
((a ∧ ¬b) ∧ c) ∨ (¬a ∧ (¬b ∧ c)) ∨ (b ∧ c) e c.
Resoluc¸a˜o da Questa˜o 4:
Temos que:
((a ∧ ¬b) ∧ c) ∨ (¬a ∧ (¬b ∧ c)) ∨ (b ∧ c)
e´ equivalente a
(a ∧ (¬b ∧ c)) ∨ (¬a ∧ (¬b ∧ c)) ∨ (b ∧ c)
e´ equivalente a
[(a ∨ ¬a) ∧ (¬b ∧ c)] ∨ (b ∧ c)
e´ equivalente a
(¬b ∧ c) ∨ (b ∧ c)
e´ equivalente a
(¬b ∨ b) ∧ c
e´ equivalente a
c
Nos passos acima, usamos:
(1) Associatividade do ∧,
(2) Distributividade do ∧ sobre o ∨,
(3) Elemento neutro do ∧,
(4) Distributividade do ∧ sobre o ∨,
(5) Elemento neutro do ∧.
4
5. Comentando sobre a resoluc¸a˜o de questo˜es de Matema´tica Discreta com uma amiga,
uma aluna disse o seguinte:
E1 : A questa˜o na˜o e´ fa´cil, quando a resoluc¸a˜o depende da interpretac¸a˜o
do enunciado.
E2 : A questa˜o e´ fa´cil, quando a resoluc¸a˜o depende da construc¸a˜o de
uma tabela.
Baseada nos enunciados E1 e E2, a amiga concluiu que:
E3 : A resoluc¸a˜o na˜o depende da interpretac¸a˜o dos enunciados, se, e somente se,
ela na˜o depende da construc¸a˜o de uma tabela.
(a) Considerando os enunciados E1, E2 e E3 como formados pela aplicac¸a˜o de co-
nectivos a enunciados atoˆmicos, determine uma legenda e simbolize-os, de acordo
com a legenda dada.
(b) Determine se a conclusa˜o da amiga decorre, ou na˜o, dos enunciados que a aluna
disse.
Resoluc¸a˜o da Questa˜o 5:
(a) Os enunciados E1, E2 e E3 podem ser reescritos como:
E1 : se a resoluc¸a˜o depende da interpretac¸a˜o do enunciado, enta˜o
na˜o ( a questa˜o e´ fa´cil )
E2 : se a resoluc¸a˜o depende da construc¸a˜o de uma tabela, enta˜o
a questa˜o e´ fa´cil
E3 : na˜o ( a resoluc¸a˜o depende da interpretac¸a˜o do enunciado )
se, e somente se,
na˜o ( a questa˜o depende da construc¸a˜o de uma tabela )
Considere a seguinte legenda:
i : a resoluc¸a˜o depende da interpretac¸a˜o do enunciado
f : a questa˜o e´ fa´cil
t : a resoluc¸a˜o depende da construc¸a˜o de uma tabela
De acordo com esta legenda, os enunciados podem ser simbolizados por:
E1 : i→ (¬f)
E2 : t→ f
E3 : ¬i↔ ¬t
Agora, o problema se resume em verificar a validade do argumento:
E1 : i→ (¬f)
E2 : t→ f
E3 : ¬i↔ ¬t
Ou seja, verificar se o enunciado
ϕ : [(i→ (¬f)) ∧ (t→ f)]→ (¬i↔ ¬t)
5
e´ uma tautologia.
Construindo a tabela verdade de ϕ, temos:
i f t ¬i ¬f ¬t
ϕ1︷ ︸︸ ︷
i→ (¬f)
ϕ2︷ ︸︸ ︷
t→ f ϕ1 ∧ ϕ2 ¬i↔ ¬t ϕ
V V V F F F F V F V V
V V F F F V F V F F V
V F V F V F V F F V V
V F F F V V V V V F F
F V V V F F V V V F F
F V F V F V V V V V V
F F V V V F V F F F V
F F F V V V V V V V V
Como ϕ na˜o e´ V em todas as interpretac¸o˜es, ϕ na˜o e´ uma tautologia e o argumento
e´ inva´lido. Assim, a conclusa˜o da amiga na˜o decorre dos enunciados que a aluna
disse.
c© 2013 Ma´rcia Cerioli e Petrucio Viana
Coordenac¸a˜o da Disciplina MD/CEDERJ-UAB
6