MAT01375 - MATEMÁTICA DISCRETA B Eduardo Brietzke Lista 2

Prévia do material em texto

MAT 01375 – Matemática Discreta B – 2019/2 – Lista 2
1. Determine o valor verdade de cada uma das proposições:
a) (∀n ∈ N)(∃m ∈ N)(n2 = m)
b) (∀n ∈ N)(∃m ∈ N)(n = m2)
c) (∀x ∈ R)[x 6= 0 → (∃y ∈ R)xy = 1]
d) (∃x ∈ R)(∀y ∈ R)(y 6= 0 → xy = 1)
e) (∃x ∈ R)(∃y ∈ R)(x+ 2y = 2 ∧ 2x+ 4y = 5)
f) (∀x ∈ R)(∃y ∈ R)(x+ y = 2 ∧ x− y = 1)
2. Quais das proposições seguintes são verdadeiras? Justifique.
a) (∃x)(A(x) ∧ B(x) → [(∃x)A(x) ∧ (∃x)B(x)])
b) [(∃x)A(x) ∧ (∃x)B(x)] → (∃x)(A(x) ∧ B(x))
c) [(∃x)(A(x) ∨B(x))] ↔ [(∃x)A(x) ∨ (∃x)B(x)]
d) [(∀x)A(x) → (∀x)B(x)] → [(∀x)(A(x) → B(x))]
e) (∃x)(∀y)(P (x, y)) → (∀y)(∃x)(P (x, y))
f) [(∀x)A(x) ∨ (∃x)B(x)] → [(∀x)(A(x) ∨B(x))]
g) [(∀x)(A(x) → B(x))] → [(∃x)A(x) → (∃x)B(x)]
3. Encontre um contraexemplo, se posśıvel, para as proposições:
a) (∀x ∈ Z)(∃y ∈ Z)(xy = 1)
b) (∀x ∈ Z)(∃y ∈ Z)(y2 − x < 100)
c) (∀x ∈ Z)(∀y ∈ Z)(x2 6= y3)
c) (∀x ∈ Z)(∀y ∈ Z)(x2 = y2 → x = y)
4. Seja Q(x, y) a afirmação “x+ y = x− y”. Se Z for o domı́nio das variáveis, qual é o valor
lógico de cada uma das proposições:
a) Q(1, 1)
b) Q(2, 0)
c) (∀y)Q(1, y)
d) (∃x)Q(x, 2)
e) (∃x)(∃y)Q(x, y)
f) (∀x)(∃y)Q(x, y)
g) (∃y)(∀x)Q(x, y)
h) (∀y)(∃x)Q(x, y)
i) (∀x)(∀y)Q(x, y)
5. Seja P (n) um predicado envolvendo a variável n que tem como domı́nio o conjunto dos
números naturais N = {1, 2, 3, . . .}. Use quantificadores para expressar o fato de que
vale P (n) para n suficientemente grande (por exemplo, se P (n) : 2n > n2, temos que
(∀n ≥ 5)(P (n)), logo P (n) vale para n suficientemente grande).
6. Encontre um dominio comum para as variáveis x, y, z de modo que a proposição
(∀x)(∀y)[x 6= y → (∀z)(z = x ∧ z = y)]
seja verdadeira. Encontre um outro domı́nio para o qual a proposição seja falsa.
7. Mostre que o produto de dois números ı́mpares é um número ı́mpar. Mostre que o produto
de dois inteiros é ı́mpar se e somente se ambos os fatores forem ı́mpares.
8. Mostre que o quadrado de um número inteiro não diviśıvel por 5, deixa resto 1 ou 4
quando dividido por 5.
9. Mostre que se n for um inteiro não diviśıvel por 3, então seu quadrado deixa resto 1
quando dividido por 3.
10. Mostre que não existem soluções inteiras para a equação x2 + 3y2 = 11.
11. Mostre que o algarismo das unidades do quadrado de qualquer inteiro n é 0, 1, 4, 5, 6 ou
9.
12. Mostre que o algarismo das unidades da quarta potência de qualquer inteiro n é 0, 1, 5
ou 6.
13. Mostre que se x é um número irracional, então
1
x
também é irracional.
14. Mostre que um inteiro positivo n é para se e somente se 7n+ 4 for par.
15. Mostre que se a for um inteiro impar, então a equação x2 + x − a = 0 não tem soluções
inteiras.
16. Mostre que existem 100 naturais consecutivos tais que nenhum deles é um quadrado
perfeito.
2