Exercícios Resolvidos sobre Relações, Teoria dos Conjuntos e Funções Geradoras

Considere a relação R x y 2x y 5 definida no conjunto dos números naturais e as seguintes afirmações I nR II R¹ x y 2x y 5 III nDomR¹ DomR IV nR¹ 2 É correto o que se afirma em a I e IV b II e III c III e IV d I e II e I e III Considere o teorema a seguir e sua demonstração Teorema Seja R uma relação de equivalência sobre um conjunto A se aRb então a b Demonstração Considere que aRb Provaremos que a b mostrando que a b e b a Suponha que c a e assim aRc Sabendo que aRb e que R é simétrica então A Como R é B bRc Assim c b Isso mostra que C A inclusão b a é análoga Assim podemos afirmar que a A bRa B reflexiva e C a b b A cRa B transitiva e C b a c A bRa B transitiva e C a b d A cRa B transitiva e C a b e A bRa B reflexiva e C b a Considere a sequência numérica 1 1 1 1 e as seguintes afirmações I A função geradora de 1 1 1 1 é Gx 11x II A função geradora de 2 0 2 0 é Gx 21x² III A função geradora de 0 0 0 1 1 1 é Gx x³1x IV A função geradora de 1 2 3 4 é Gx 11x² É correto o que se afirma em a II e IV b I e III c I e IV d II e III e III e IV A interseção entre dois conjuntos A e B é o conjunto formado pelos elementos que estão em A e B simultaneamente Considere as seguintes afirmações sobre a interseção de conjuntos I Se A números pares e B números ímpares então AB II A interseção entre os conjuntos A 1 4 7 8 e B 3 4 9 10 é um conjunto unitário III Os conjuntos A números pares e B números múltiplos de quatro são disjuntos IV Se A e B são conjuntos disjuntos então nAB 1 É correto o que se afirma em a II e III b I e II c I e IV d III e IV e I e III Considere o problema a seguir e sua solução Problema Encontre a função geradora ordinária fechada para a sequência 0 0 2 3 11 5 1 1 1 1 Solução Pela definição a série de potência procurada é dada por Gx 2x² 3x³ 11x⁴ 5x⁵ x⁶ x⁷ A 1 x x² x³ x⁴ 1 x x² 2x³ 10x⁴ 4x⁵ B Pois 1 x x² x³ x⁴ 11x Portanto Gx C Assim podemos afirmar que a A 1 x x² 2x³ 10x⁴ 4x⁵ B 11x e c 2x² x³ 8x⁴ 6x⁵ 4x⁶1x b A 1 x x² 2x³ 10x⁴ 4x⁵ B 11x e c 2x² x³ 8x⁴ 6x⁵ 4x⁶1x c A 1 x x² 2x³ 10x⁴ 4x⁵ B 11x e c 2x² x³ 8x⁴ 6x⁵ 4x⁶1x d A 1 x x² 2x³ 10x⁴ 4x⁵ B 11x e c 2x² x³ 8x⁴ 6x⁵ 4x⁶1x e A 1 x x² 2x³ 10x⁴ 4x⁵ B 11x e c 2x²x³8x⁴6x⁵4x⁶1x Considere a propriedade a seguir e sua demonstração Propriedade Seja f X Y uma função e C D Y então a imagem inversa de f é tal que f1C D A Demonstração De fato x f1CD fx CD fx C e B x f1C e x f1D x f1C f1D Portanto K Assim podemos afirmar que a A f1Cf1D B fx D e K f1CD f1DC b A f1DC B fx D e K f1CD f1Cf1D c A f1DC B fx D e K f1CD f1DC d A f1Cf1D B fx D e K f1CD f1Cf1D e A f1Cf1D B f1x D e K f1CD fCfD Considere a função f N0 Z definida de maneira recursiva por f0 1 f1 2 fx 1 fx 3 fx 1 e as seguintes afirmações I f2 é um número primo II f3 é um número par III f4 é um número primo IV f5 17 É verdadeiro o que se afirma em a II e IV b III e IV c II e III d I e II e I e IV Considere os conjuntos A a b c d e B 1 2 3 4 5 e as seguintes afirmações I R 1 a 2 b 3 c 4 d define uma função de B em A II R a 1 e 2 c 1 d 4 b 3 define uma função sobrejetora de A em B III R a 1 c 2 d 4 b 3 define uma função injetora de A em B IV Não existe uma função sobrejetora de A em B É correto o que se afirma em a III e IV b I e IV c I e III d II e IV e II e III Considere a seguinte proposição e sua demonstração Proposição Sejam a b Z tais que ab 0 a b e b a então a b Demonstração Suponha que ab 0 Como a b e b a por definição existem k1 k2 Z tais que a bk1 e b ak2 Então ab A Utilizando B concluímos que k1k2 1 então k1 k2 1 ou C Sendo assim a 1b b Assim podemos afirmar que a A abk1k2 B a lei do corte e C k1 k2 1 b A abk1k2 B a lei do corte e C k1 k2 0 c A abk1 B o algoritmo da divisão de Euclides e C k1 k2 0 d A abk1 B a lei do corte e C k1 k2 1 e A abk1 B o algoritmo da divisão de Euclides e C k1 k2 1 Considere os conjuntos A x N x 3 10 x B 4 e a relação R x y B x A x y 5 Analise as seguintes afirmações I nR 2 II DomR 4 III ImR 1 2 IV nADomR 1 É correto o que se afirma em a I e II b II e III c III e IV d II e IV e I e IV Considere a relação R x y 2x y 5 definida no conjunto dos números naturais e as seguintes afirmações I nR II R¹ x y 2x y 5 III nDomR¹ DomR IV nR¹ 2 É correto o que se afirma em a I e IV b II e III c III e IV d I e II e I e III Considere o teorema a seguir e sua demonstração Teorema Seja R uma relação de equivalência sobre um conjunto A se aRb então a b Demonstração Considere que aRb Provaremos que a b mostrando que a b e b a Suponha que c a e assim aRc Sabendo que aRb e que R é simétrica então A Como R é B bRc Assim c b Isso mostra que C A inclusão b a é análoga Assim podemos afirmar que a A bRa B reflexiva e C a b b A cRa B transitiva e C b a c A bRa B transitiva e C a b d A cRa B transitiva e C a b e A bRa B reflexiva e C b a Considere a sequência numérica 1 1 1 1 e as seguintes afirmações I A função geradora de 1 1 1 1 é Gx 1 1 x² II A função geradora de 2 0 2 0 é Gx 2 1 x² III A função geradora de 0 0 0 1 1 1 é Gx x³ 1 x² IV A função geradora de 1 2 3 4 é Gx 1 1 x² É correto o que se afirma em a II e IV b I e III c I e IV d II e III e III e IV A interseção entre dois conjuntos A e B é o conjunto formado pelos elementos que estão em A e simultaneamente Considere as seguintes afirmações sobre a interseção de conjuntos I Se A números pares e B números ímpares então AB II A interseção entre os conjuntos A 1 4 7 8 e B 3 4 9 10 é um conjunto unitário III Os conjuntos A números pares e B números múltiplos de quatro são disjuntos IV Se A e B são conjuntos disjuntos então nAB 1 É correto o que se afirma em a II e III b I e II c I e IV d III e IV e I e III Considere o problema a seguir e sua solução Problema Encontre a função geradora ordinária fechada para a sequência 0 0 2 3 11 5 1 1 1 1 Solução Pela definição a série de potência procurada é dada por Gx 2x² 3x³ 11x⁴ 5x⁵ x⁶ x⁷ Δ 1 x x² x³ x⁴ ⁿ 1 x x² 2x³ 10x⁴ 4x⁵ B Pois 1 x x² x³ x⁴ 1 1 x Portanto Gx C Assim podemos afirmar que a A 1 x x² 2x³ 10x⁴ 4x⁵ B 1 1 x e c 2x² x³ 8x⁴ 6x⁵ 4x⁶ 1 x b A 1 x x² 2x³ 10x⁴ 4x⁵ B 1 1 x e c 2x² x³ 8x⁴ 6x⁵ 4x⁶ 1 x c A 1 x x² 2x³ 10x⁴ 4x⁵ B 1 1 x e c 2x² x³ 8x⁴ 6x⁵ 4x⁶ 1 x d A 1 x x² 2x³ 10x⁴ 4x⁵ B 1 1 x e c 2x² x³ 8x⁴ 6x⁵ 4x⁶ 1 x e A 1 x x² 2x³ 10x⁴ 4x⁵ B 1 1 x e c 2x² x³ 6x⁴ 4x⁵ 4x⁶ 1 x Considere a propriedade a seguir e sua demonstração Propriedade Seja f X Y uma função e C D Y então a imagem inversa de f é tal que f1CD Á Demonstração De fato x ε f1CD fx ε CD fx ε C ε B x ε f1C e x ε f1D x ε f1Cf1D Portanto K Assim podemos afirmar que a A f1Cf1D B fx ε D e K f1CD f1DC b A f1DC B fx ε D e K f1CD f1Cf1D c A f1DC B fx ε D e K f1CD f1DC d A f1Cf1D B fx ε D e K f1CD f1Cf1D e A f1Cf1D B fx ε D e K f1CD fCfD Considere a função f Nu0 Z definida de maneira recursiva por f0 1 f12 fx 1 fx 3 fx 1 e as seguintes afirmações I f2 é um número primo II f3 é um número par III f4 é um número primo IV f5 17 É verdadeiro o que se afirma em a I e IV b III e IV c I e III d I e II e I e IV Considere os conjuntos A a b c d e B 1 2 3 4 5 e as seguintes afirmações I R 1 a 2 b 3 c 4 d define uma função de B em A II R a 1 e 2 c 1 d 4 b 3 define uma função sobrejetora de A em B III R a 1 c 2 d 4 b 3 define uma função injetora de A em B IV Não existe uma função sobrejetora de A em B É correto o que se afirma em a III e IV b I e IV c I e III d II e IV e II e III Considere a seguinte proposição e sua demonstração Proposição Sejam a b e Z tais que ab 0 a b e b a então a b Demonstração Suponha que ab 0 Como a b e b a por definição existem k1 k2 e Z tais que a bk1 e b ak2 Então ab A Utilizando B concluímos que k1k2 1 então k1 k2 1 ou Ç Sendo assim a 1b b Assim podemos afirmar que a A abk1k2 B a lei do corte e C k1 k2 1 b A abk1k2 B a lei do corte e C k1 k2 0 c A abk1 B o algoritmo da divisão de Euclides e C k1 k2 0 d A abk1 B a lei do corte e C k1 k2 1 e A abk1 B o algoritmo da divisão de Euclides e C k1 k2 1 Considere os conjuntos A x e N x 3 10 x B 4 e a relação R x y e B x A x y 5 Analise as seguintes afirmações I nR 2 II DomR 4 III ImR 1 2 IV nADomR 1 É correto o que se afirma em a I e II b II e III c III e IV d II e IV e I e IV