UNIVESP - 2021 - Exercícios de apoio 1 - Semana 4 - Fundamentos Matemáticos da Computação

Prévia do material em texto

QUESTÃO 1. Sabe-se que uma propriedade P(n) acerca dos números naturais é verdadeira para n = 10 e que
se P(n) é verdadeira então P(2n) é verdadeira. Considere as afirmações abaixo e informe se cada uma delas é
verdadeira, falsa ou se não é possível decidir. 
 
 
QUESTÃO 2. Indique com V as afirmações verdadeiras e com F as falsas: 
 
a. ( ) Se I é uma relação sobre 𝐴={1,2,3}, definida pelo produto cartesiano A × A, então I = { (1,1), (2,2),
(3,3)}.
F 
b. ( ) A relação K = {(1, 9), (2, 9), (4, 9)} é uma relação do conjunto A ={0, 1, 2, 3, 4}, no conjunto B = {1, 5,
7, 9}.
EXERCÍCIOS DE APOIO
Apenas para praticar. Não vale nota.
( ) P(n) é verdadeira para todos os números naturais. 
Não há dados para decidir.
a.
( ) P(n) é verdadeira para todos os números naturais pares. 
Não há dados para decidir.
b.
( ) P(n) é verdadeira para todos os números os múltiplos de 5. 
Não há dados para decidir.
c.
( ) É possível concluir que P(n) é verdadeira para todo múltiplo de 10, a partir de 0. 
F
d.
( ) P(0) é falsa. 
Não há dados para decidir.
e.
( ) P(n) é verdadeira para todos os números naturais múltiplos de 10 e maiores ou iguais a
10. 
Não há dados para decidir.
f.
( ) P(5) provavelmente é falsa. 
Não há dados para decidir.
g.
V 
c. ( ) R = S, se R = {(x, y):x, y ∈ Z |x ≤ y e y ≤ x} e S = {(x, y):x, y ∈ Z|x = y}.
V 
d. ( ) Y = {(-4, -1), (-2, 0), (0, 0), (2, 4)} é a relação inversa de X = {(4,1), (2, 0), (0, 0), (-2, -4)}.
F 
e. ( ) A imagem da relação W = {(x, y):x, y ∈ Z| y = |x|} é o conjunto dos naturais N.
V 
f. ( ) Sejam as relações Y = {(a, b):a, b ∈ N| b = a + 2} e H = Z × Z. Então, Y ⊂ H.
V
 
QUESTÃO 3. Para cada relação abaixo, determine o domínio (DomR) e a imagem (ImgR):
 
 
QUESTÃO 4. Determine a relação inversa de:
R = {(0, 0), (2, 0), (6, 0), (8, 0), (12, 0)}. 
DomR = {0, 2, 6, 8, 12} ImgR = {0}.
 
 
a.
S = {(0, -2), (0, -1), (0, 0), (0, 1), (0, 3)}. 
DomS = {0} ImgS = {-2, -1, 0, 1, 3}.
 
 
b.
W = {(a, b): a ∈ A e b ∈ Z| b = " "} e A = {1, 3, 5, 7, 9}. 
DomW = A = {1, 3, 5, 7, 9}, ImgW = {0, 8, 24, 48, 80}.
c.
R = {(1, -1), (-2, 3), (0, 1), (0, -1), (4, -4), (-2, 4)}. 
R = {(-1, 1), (3, -2), (1, 0), (-1, 0), (-4, 4), (4, -2)}.
a.
-1
S = A x A, para o conjunto A = {0, 1, 2, 3}. 
S = S .
b.
-1
Y = {(a, b):a, b ∈ R| b = 2a + 3}. 
Y = {(a, b):a, b ∈ R| b = (a-3)/2}.
c.
-1
 
QUESTÃO 5. Sejam as relações R = {(0, 0), (0, 1), (1, 2), (2, 3), (3, 6)}, S = {(0, 3), (1, 0), (1, 2), (3, 1), (6, 0)} e
R = {(0, 0), (1, 0), (2, 1), (3, 2), (6, 3)}.
 
QUESTÃO 6. Sejam os conjuntos A = {0, 1, 2} e B = {0, 2, 3, 4} e as relações ARB e ASB dadas por R = {(0, 0),
(0, 2), (1, 2), (1, 4), (2, 0), (2, 3)} e S = {(1, 0), (1, 2), (1, 4), (2, 0), (2, 4)}.
 
QUESTÃO 7. A partir do Princípio de Indução Finita (PIF), aponte quais das afirmações abaixo são
verdadeiras. 
-1
Determine SoR e RoS. 
SoR = {(0, 3), (0, 0), (0, 2), (2, 1), (3, 0)} e 
RoS = {(0, 6), (1, 0), (1, 1), (1, 3), (3, 2), (6, 0), (6, 1)}.
a.
Determine R oR e RoR . 
R oR = {(0, 0), (1, 1), (2, 2), (3, 3)} e 
RoR = {(0, 0), (0, 1), (1, 0), (1, 1), (2, 2), (3, 3), (6, 6)}.
b. -1 -1
-1
-1
Represente R e S por suas matrizes booleanas M e N, respectivamente. 
 
e
a.
Determine M∪N. b.
Determine M∩N. c.
Para todo com , tem-se que .I.
Para todo , e dois números reais positivos, é válida a expressão 
.
II.
Para todo , com , o número é sempre ímpar.III.
Somente I
 
QUESTÃO 8. Utilizando o Princípio de Indução Finita (PIF), aponte quais das afirmações abaixo são
verdadeiras para todo 
I e II
 
QUESTÃO 9. Dado , seja a função . Considere a tentativa de demonstração da afirmação
abaixo por indução matemática:
Afirmação: , para todo 
Ao aplicar o passo de indução de para , não é possível utilizar a hipótese de indução de forma a
obter 
 
 
QUESTÃO 10. Sejam os conjuntos A e B e a relação definida pelo diagrama abaixo.
I.
II.
III.
Base da indução: para I.
Hipótese de indução: é verdade para todo para algum II.
Passo de indução em (n+1):
 
Obviamente, a tentativa de demonstração acima é falsa. Assinale a alternativa que melhor
justifique o EQUÍVOCO da resolução acima.
III.
Qual a matriz booleana que representa essa relação?
 
 
QUESTÃO 11. Considere os seguintes conjuntos: de frutas , de
vendedores , e de consumidores .
Considere, ainda, as relações tal como definidas pelo diagrama abaixo:
Qual é o resultado da relação composta 
 
X = {(Maçã,Marluce),(Banana,Pedro),(Morango,Marluce),(Açaí,Rafael)}
 
 
ESCONDER
GABARITO