Solução dos exercícios matemática discreta 1

Prévia do material em texto

Universidade Federal de Ouro Preto - UFOP 
Instituto de Ciências Exatas e Biológicas - ICEB 
Departamento de Computação - DECOM 
Matemática Discreta I – BCC 101 
 
 
 
 
Lista de Exercícios 1 
 
1. Quais dessas sentenças são proposições? 
a) Belo horizonte é capital de Minas Gerais. É Proposição 
b) Curitiba é capital de Santa Catarina. É Proposição 
c) 2+3 = 5 É Proposição 
d) 5+7 = 10 É Proposição 
e) X+2 = 11 Não é Proposição 
f) Responda esta questão. Não é Proposição 
g) Que horas são? Não é Proposição 
h) A lua é feita de queijo verde. É Proposição 
i) 2𝑛 ≥ 100. Não é Proposição 
 
2. Quais os valores-verdade das proposições do exercício 1. 
a)V b) F c) V d) F h) F 
 
3. Qual é a negação de cada proposição a seguir? 
a) Hoje é quinta-feira. Hoje não é quinta-feira 
b) Não há poluição em São Paulo. Há poluição em São Paulo 
c) 2+1 = 3 2 + 1 ≠ 3 
d) O verão em Ouro Preto é quente e ensolarado. O verão em Ouro Preto não é quente e nem 
ensolarado. 
 
4. Escreva a negação de cada fórmula bem-formada a seguir: 
a) Se a comida for boa, então o serviço será excelente. A comida é boa, mas o serviço é ruim. 
b) Ou a comida é boa, ou o serviço é excelente. A comida é ruim e o serviço também. 
c) Ou a comida é boa e o serviço é excelente, ou então está caro. A comida é ruim ou o serviço é 
ruim, mas é barato. 
d) Nem a comida é boa, nem o serviço é excelente. A comida é boa ou o serviço é excelente 
e) Se for caro, então a comida será boa e o serviço será excelente. É caro, mas a comida é ruim 
ou o serviço é ruim. 
 
5. Para cada uma das sentenças, determine se o ou é inclusivo ou exclusivo. Explique sua resposta. 
a) Café ou chá vem com o jantar. Ou exclusivo 
b) Uma senha deve ter ao menos três dígitos ou oito caracteres de comprimento. Ou inclusivo 
c) O pré-requisito para o curso é um curso em teoria dos números ou um curso em criptografia. Ou 
inclusivo 
d) Você pode jogar usando dólares americanos ou euros. Ambas as interpretações 
 
 
BCC101 – Matemática Discreta I 2 
 
 
 
6. Usando as letras indicadas para as proposições componentes, escreva as afirmações compostas a seguir 
usando a notação simbólica. 
a) A: preços subirem; 
B: haverá muitas casas disponíveis; 
C: as casas estarão caras. 
Se os preços subirem, então haverá muitas casas disponíveis e caras; mas se as casas não estiverem 
caras, ainda assim haverá muitas disponíveis. 
Resposta: [A → B ⋀ C] ∧ (¬C → B) 
b) A: ir para a cama; 
B: ir nadar; 
C: trocar de roupa. 
Ir para cama ou ir nadar é uma condição suficiente para trocar de roupa; no entanto, mudar de roupa 
não significa que você vai nadar. 
Resposta: [(A ∨ B) → C ] ∧ ¬(C → B) 
c) A: irá chover; 
B: irá nevar. 
Irá chover ou irá nevar, mas não os dois ao mesmo tempo. 
Resposta:(A ∨ B) ∧ ¬(A ∧ B) 
d) A: Janete vence 
B: Janete perde; 
C: Janete ficará cansada. 
Se Janete vencer ou se perder, ela ficará cansada. 
Resposta: ( A ∨ B) → C 
 
7. Dadas as seguintes proposições: 
A: Rosas são vermelhas. 
B: Violetas são azuis. 
C: Açúcar é doce. 
 
Escreva as proposições compostas a seguir na notação simbólica: 
 
a) Rosas são vermelhas e violetas são azuis. Resposta: 𝐴 ∧ 𝐵 
b) Rosas são vermelhas, e ou violetas são azuis ou açúcar é doce. Resposta: 𝐴 ∧ ( 𝐵 ∨ 𝐶) 
c) Sempre que violetas forem azuis, rosas serão vermelhas e açúcar será doce. Resposta: 𝐵 → ( 𝐴 ∧ 𝐶) 
d) Rosas só serão vermelhas se violetas não forem azuis ou se açúcar for amargo. Resposta: 𝐴 →
( ¬𝐵 ∨ ¬𝐶) 
e) Rosas são vermelhas, e, se açúcar for amargo, então ou violetas não são azuis ou açúcar é doce. 
Resposta: 𝐴 ∧ [ ¬𝐶 → ( ¬𝐵 ∨ 𝐶)] 
 
Escrevas as proposições compostas a seguir em português: 
f) 𝐵 ∨ ¬𝐶 (Violetas são azuis ou o açúcar é azedo) 
g) ¬𝐵 ∨ (𝐴 → 𝐶) (Violetas não são azuis ou, se as rosas forem vermelhas, então o açúcar será doce.) 
h) (𝐶 ∧ ¬𝐴) → 𝐵 (Se o açúcar é doce e as rosas não são vermelhas, então as violetas são azuis.) 
i) 𝐶 ∧ (¬𝐴 → 𝐵) (O açúcar será doce e, as rosas não são vermelhas somente se as violetas forem 
azuis.) 
BCC101 – Matemática Discreta I 3 
 
 
 
8. Considere que P, Q e R são proposições: 
P = Você tira A no exame final. 
Q = Você faz todos os exercícios dessa lista. 
R = Você tira A em Matemática Discreta. 
 
Escreva estas proposições em notação simbólica: 
a) Você tira uma A em Matemática Discreta, mas não faz todos os exercícios desta lista. 
𝑅𝑒𝑠𝑝𝑜𝑠𝑡𝑎: 𝑅 ∧ ¬𝑄 
b) Você não tira um A no exame final, faz todos os exercícios desta lista e tiram um A em Matemática 
Discreta. 𝑅𝑒𝑠𝑝𝑜𝑠𝑡𝑎: ¬𝑃 ∧ 𝑄 ∧ 𝑅 
c) Tirar um A no exame final é necessário para tirar um A em Matemática Discreta. 𝑅𝑒𝑠𝑝𝑜𝑠𝑡𝑎: 𝑃 → 𝑅 
d) Você vai tirar um A em Matemática Discreta se, e somente se, você fizer todos os exercícios desta 
lista ou tirar um A no exame final. 𝑅𝑒𝑠𝑝𝑜𝑠𝑡𝑎: 𝑅 ↔ (𝑄 ∨ 𝑃) 
 
9. Determine se cada uma destas proposições condicionais é verdadeira ou falsa. 
a) Se 1+1 =3, então unicórnios existem. 𝐹 → 𝐹, então é V 
b) Se 1+1=3, então cachorros podem voar. 𝐹 → 𝐹, então é V 
c) Se 1+1=2, então cachorros podem voar. 𝑉 → 𝐹, então é F 
d) Se 2+2=4, então 1+2=3. 𝑉 → 𝑉, então é V 
 
10. Qual o valor lógico de cada uma das proposições a seguir? 
a) 8 é ímpar e 6 é ímpar 𝐹 ∧ 𝐹, então é F 
b) Se 8 for ímpar, então 6 é ímpar. 𝐹 → 𝐹, então é V 
c) Se 8 for par, então 6 será ímpar. 𝑉 → 𝐹, então é F 
d) Se 8 for ímpar, então 6 será par. 𝐹 → 𝑉, então é V 
e) Se 8 for ímpar e 6 for par, então 8 < 6. (𝐹 ∧ 𝑉) → 𝐹, então é V 
 
11. Dados os valores lógicos A verdadeiro, B falso e C verdadeiro, qual o valor lógico de cada uma das 
fórmulas bem-formadas a seguir? 
a) 𝐴 ∧ (𝐵 ∨ 𝐶) 𝑉 ∧ (𝐹 ∨ 𝑉), então é V 
b) (𝐴 ∧ 𝐵) ∨ 𝐶 (𝑉 ∧ 𝐹) ∨ 𝑉), então é V 
c) ¬(𝐴 ∧ 𝐵) ∨ 𝐶 ¬(𝑉 ∧ 𝐹) ∨ 𝑉, então é V 
d) ¬𝐴 ∨ ¬(¬𝐵 ∧ 𝐶) ¬𝑉 ∨ ¬(¬𝐹 ∧ 𝑉), então é F 
 
12. Construa tabelas-verdade para as fórmulas bem-formadas a seguir. Indique, para cada uma, se trata de 
uma tautologia, contradição ou uma contingência. 
 
a) (𝐴 → 𝐵) ↔ ¬𝐴 ∨ 𝐵 
 (Tautologia.) 
 
 
 
 
 
A B (𝑨 → 𝑩) ¬𝑨 ¬𝑨 ∨ 𝑩 (𝑨 → 𝑩) ↔ ¬𝑨 ∨ 𝑩 
V V V F V V 
V F F F F V 
F V V V V V 
F F V V V V 
BCC101 – Matemática Discreta I 4 
 
 
 
 
 
 
b) (𝐴 ∧ 𝐵) ∨ 𝐶 → 𝐴 ∧ (𝐵 ∨ 𝐶) 
(Contingência) 
A B C (𝑨 ∧ 𝑩) (𝑨 ∧ 𝑩) ∨ 𝑪 (𝑩 ∨ 𝑪) 𝑨 ∧ (𝑩 ∨ 𝑪) (𝑨 ∧ 𝑩) ∨ 𝑪 → 𝑨 ∧ (𝑩 ∨ 𝑪) 
V V V V V V V V 
V V F V V V V V 
V F V F V V V V 
V F F F F F F V 
F V V F V V F F 
F V F F F V F V 
F F V F V V F F 
F F F F F F F V 
c) (¬(𝐴 ∨ 𝐵) ∨ ¬𝐴) ∧ 𝐴 
(Contradição) 
A B (𝐴 ∨ 𝐵) ¬(𝐴 ∨ 𝐵) ¬𝐴 ¬(𝐴 ∨ 𝐵) ∨ ¬𝐴 (¬(𝐴 ∨ 𝐵) ∨ ¬𝐴) ∧ 𝐴 
V V V F F F F 
V F V F F F F 
F V V F V V F 
F F F V V V F 
 
d) (𝐴 → 𝐵) → [(𝐴 ∨ 𝐶) → (𝐵 ∨ 𝐶)] 
(Tautologia) 
A B C (𝑨 → 𝑩) (𝑨 ∨ 𝑪) (𝑩 ∨ 𝑪) (𝑨 ∨ 𝑪) → (𝑩 ∨ 𝑪) (𝑨 → 𝑩) → [(𝑨 ∨ 𝑪) → (𝑩 ∨ 𝑪)] 
V V V V V V V V 
V V F V V V V V 
V F V F V V V V 
V F F F V F F V 
F V V V V V V V 
F V F V F V V V 
F F V V V V V V 
F F F V F F V V 
 
e) 𝐴 ∨ (𝐵 → 𝐶) 
(Contingência) 
A B C 𝑨 ∨ (𝑩 → 𝑪) 
V V V V 
V V F V 
V F V V 
V F F V 
F V V V 
F V F F 
BCC101 – Matemática Discreta I 5 
 
 
 
F F V V 
F F F V13. O Operador lógico ou exclusivo (⨁) é definido pela seguinte tabela-verdade: 
 
P Q 𝑷⨁𝑸 
V V F 
V F V 
F V V 
F F F 
 
 
a) Prove que 𝑃⨁𝑄 ≡ (𝑃 ∧ ¬𝑄) ∨ (¬𝑃 ∧ 𝑄), construindo a tabela-verdade para esta segunda fórmula 
e comparando-a com a tabela-verdade da primeira. 
P Q (𝑷 ∧ ¬𝑸) (¬𝑷 ∧ 𝑸) (𝑷 ∧ ¬𝑸) ∨ (¬𝑷 ∧ 𝑸) 
V V F F F 
V F V F V 
F V F V V 
F F F F F 
 
b) Prove também que 𝑃⨁𝑄 ≡ (𝑃 ∨ 𝑄) ∧ ¬(𝑃 ∧ 𝑄) 
P Q (𝑷 ∨ 𝑸) (𝑷 ∧ 𝑸) ¬(𝑷 ∧ 𝑸) (𝑷 ∨ 𝑸) ∧ ¬(𝑷 ∧ 𝑸) 
V V V V F F 
V F V F V V 
F V V F V V 
F F F F V F 
 
 
14. Construa tabelas-verdades para cada uma das proposições compostas. 
a) 𝑃 ∧ ¬𝑃 
P ¬𝑷 𝑷 ∧ ¬𝑷 
V F F 
F V F 
 
b) (𝑃 → 𝑄) ↔ (¬𝑄 → ¬𝑃) 
P Q (𝑷 → 𝑸) ¬𝑷 ¬𝑸 ¬𝑸 → ¬𝑷 (𝑃 → 𝑄) ↔ (¬𝑄 → ¬𝑃) 
V V V F F V V 
V F F F V F V 
F V V V F V V 
F F V V V V V 
 
 
c) (𝑃 ∨ 𝑄) → (𝑃 ⨁ 𝑄) 
BCC101 – Matemática Discreta I 6 
 
 
 
P Q (𝑷 ∨ 𝑸) (𝑷 ⨁ 𝑸) (𝑷 ∨ 𝑸) → (𝑷⨁𝑸) 
V V V F F 
V F V V V 
F V V V V 
F F F F V 
 
 
d) (𝑃 ∨ 𝑄) ⨁(𝑃⋀𝑄) 
P Q (𝑷 ∨ 𝑸) (𝑷 ∧ 𝑸) (𝑷 ∨ 𝑸) ⨁(𝑷⋀𝑸) 
V V V V F 
V F V F V 
F V V F V 
F F F F F 
 
15. Construa uma tabela-verdade para (𝑃 ↔ 𝑄) ↔ (𝑅 ↔ 𝑆) 
 
P Q R S (𝑷 ↔ 𝑸) (𝑹 ↔ 𝑺) (𝑷 ↔ 𝑸) ↔ (𝑹 ↔ 𝑺) 
V V V V V V V 
V V V F V F F 
V V F V V F F 
V V F F V V V 
V F V V F V F 
V F V F F F V 
V F F V F F V 
V F F F F V F 
F V V V F V F 
F V V F F F V 
F V F V F F V 
F V F F F V F 
F F V V V V V 
F F V F V F F 
F F F V V F F 
F F F F V V V 
 
 
16. Encontre a disjunção binária OR, a conjunção binária AND e a disjunção binária exclusiva XOR de 
cada um destes pares de sequências de bit. 
 
a) 101 1110 e 010 000 
OR: 111 1111 
AND: 000 0000 
XOR: 111 1111 
b) 1111 0000 e 1010 1010 
OR: 1111 1010 
AND: 1010 0000 
BCC101 – Matemática Discreta I 7 
 
 
 
XOR: 0101 1010 
 
c) 00 0111 0001 e 10 0100 1000 
OR: 10 0111 1001 
AND: 00 0100 0000 
XOR: 10 0011 1001 
 
d) 11 1111 1111 e 00 0000 0000 
OR: 11 1111 1111 
AND: 00 0000 0000 
XOR: 11 1111 1111