Buscar

Lista Teoria P1

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 7 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 7 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

Teoria dos conjuntos 
 
1) Dados os conjuntos A={3, 98, 55} B={x, y, 3}. Se , responda: A ⊆ B 
a) Quais os valores de x e y? 
b) Qual o conjunto das partes (ou conjunto potência) de ?A ⋃ B 
c) Qual a cardinalidade de ?A ⋂ B 
 
2) Em uma pesquisa realizada, contabilizou-se que 100 pessoas preferem pizza, 50 
hambúrguer, 127 batata frita, 53 dizem gostar igualmente de pizza e hamburguer, 20 de 
hambúrguer e batata frita, 100 de pizza e batata frita e 50 não conseguem escolher nenhum 
deles. Quais afirmações a seguir são falsas? Justifique. 
 
I - De acordo com o princípio de inclusão e exclusão a cardinalidade do conjunto 
universo é 500. 
 
II - Chamando os que escolheram pizza de A, hambúrguer de B, e batata frita de C a 
sentença a seguir é verdadeira: |A - B| +|B C A| = 127.⋂ ⋂ 
 
III - O dobro do complemento dos que preferem hambúrguer somado ao valor dos que 
preferem batata frita é 646. (2x ( ))B + C 
 
3) Mostre que A ⊂ (A ∪ B). 
 
4) Prove que: Dados conjuntos A, A’, B e B’ com A ⊂ B e A’ ⊂ B’, então ​A ∪ A’ ⊂ B ∪ B’​. 
 
5) Dados U = {0,1,2,3,4,5,6,7,8,9}, A = {0,2,4,6,8}, B = {1,3,5,7,9} e C = {2,4}, determine: 
 
a) Complemento de A em relação a U. 
b) Complemento de B em relação a U. 
c) Complemento de C em relação a U. 
d) Complemento de C em relação a A. 
 
 
 
 
 
 
 
 
Relações 
 
1) Dado o conjunto ​S = {1,5,10,20} e a Relação ​R = {(1,1),(1,5),(5,10),(10,20),(20,20)}​, 
determine o fecho: 
 
1. transitivo 
2. reflexivo 
3. simétrico 
 
2) Para cada uma das relações a seguir, defina se ela possui relação de Ordem ou não. 
Justifique sua resposta. 
 
1. {a,b} tal que ​a<=b​ (sobre o conjunto dos números naturais) 
2. {a,b} tal que se ​a/b​ (sobre o conjunto dos números inteiros) 
3. {a,b} tal que ​a <<​ b,onde << define ordem alfabética (sobre o conjunto de 
palavras de um dicionário) 
 
3) Para cada uma das relações a seguir, defina se ela possui relação de Equivalência ou não. 
Justifique sua resposta. 
 
1. Conexão entre andares de um prédio por um elevador 
2. Divisa entre Países 
3. Parentesco em uma árvore genealógica 
 
4) Supondo que em uma relação binária os pares ordenados são dados pelos trajetos 
percorridos entre lugares, resolva: 
 
Klaiton sai de casa a caminho da padaria. No caminho, percebeu que tinha esquecido 
sua carteira e então voltou para casa, pegou-a e completou seu trajeto. Após a padaria, Klaiton 
foi para o supermercado, local onde combinou de encontrar sua mãe. Concluída as compras, o 
tio de Klaiton, que mora com eles, saiu de casa e foi de carro para buscá-los. Ao retornarem 
para casa, o percurso foi concluído. 
Que relação é essa? Explique as propriedades dessa relação. 
 
5) Existe um servidor WEB “S” e 3 clientes estão fazendo requisições a este servidor. 
Considerando que em todas as requisições ocorre a resposta, qual a relação apresentada pelo 
tráfego de rede? 
 
 
Funções 
 
1) Uma função f é uma regra que relaciona cada elemento do conjunto A a um único elemento 
do conjunto B. A respeito das definições de domínio, contradomínio e imagem de uma função, 
assinale a alternativa correta: 
 
a) Seja f(x) = y a função acima, o domínio dessa função é o conjunto de números que 
podem ser relacionados à variável y dependente. 
b) Seja f(x) = y a função acima, o domínio dessa função é o conjunto de números 
relacionados à variável independente x. 
c) O contradomínio de uma função é o conjunto de todos os resultados que se 
relacionam a qualquer um dos elementos do domínio de uma função. 
d) A imagem de uma função é o conjunto com todos os valores possíveis que podem 
ser relacionados a algum elemento do domínio. 
e) Uma função em nenhuma hipótese poderá ter domínio igual ao contradomínio. 
 
2) Sobre os tipos de funções, é correto afirmar que: 
a) Uma função bijetora é aquela que o conjunto imagem aparece muitas vezes no 
conjunto domínio de R 
b) Uma função sobrejetora é aquela que o contradomínio é igual a imagem do domínio. 
c) Uma função injetora é aquela que todo elemento do conjunto imagem aparece em 
até uma vez no domínio. 
 
3) Dada a função h: {-3, 0, 3, 8} {-20, 0, 1, 18, 20, 31, 35, 40} definida pela lei h(x)=x​2​−3x, 
indique o : 
a) Domínio 
b) Contradomínio 
c) Imagem 
 
4) Sejam A, B e C conjuntos de números inteiros, tais que A tem 8 elementos, B tem 4 
elementos, C tem 7 elementos e A U B U C tem 16 elementos. Então, o número de elementos 
que o conjunto imagem D = (A ∩ B) U (B ∩ C) pode ter é igual a: 
a) 1 
b) 2 
c) 3 
d) 4 
 
5) Analise os conjuntos e sua respectiva regra. Baseado na definição de função diga se os 
conjuntos representam uma função e caso represente se a função é injetora, sobrejetora e 
bijetora. 
 
a) f(x)= 2x + 1 
Domínio: {–1, 0, 2, 3, 4} 
Contradomínio: {–1, 0, 1, 5, 6, 7, 8, 9} 
Imagem: {–1, 1, 5, 7, 9} 
 
b) f(x)= x² - 2 
Domínio: {–1, 1, 0, 2, -2} 
Contradomínio: {–2, –1, 2} 
Imagem: {–2, –1, 2} 
 
c) f(x)= x³ 
 Domínio: {-3, –2, –1, 0, 1, 2, 3} 
Contradomínio: {–8, –1, 0, 1, 8, 27} 
 Imagem: {–8, –1, 0, 1, 8, 27} 
 
d) f(x)= 2.5x 
Domínio: {1, 2, 3, 4, 5, 10, 15, 20} 
Contradomínio: {2.5, 5, 7.5, 10, 12.5, 25, 37.5, 50} 
Imagem: {2.5, 5, 7.5, 10, 12.5, 25, 37.5, 50} 
 
e) f(x)= e​0 
Domínio: {-1000, -543, -201, -91, 0, 3, 49, 332, 799} 
Contradomínio: {0} 
Imagem: {0} 
 
Conjuntos Contáveis 
 
 
1) ​Mostre que o conjunto de inteiros, positivos e negativos, é contável. 
 
2)​ Sobre a Teoria de Conjuntos, defina os seguintes termos: Conjunto Finito, Conjunto Infinito, 
Conjunto Contavelmente Infinito, Conjunto Incontável. 
 
3)​ Utilize o método da diagonalização de Cantor para provar que o conjunto dos números 
naturais é incontavelmente infinito. 
 
4) ​Prove que o conjunto ZxZ é enumerável. 
 
5) ​Usando a Definição de Conjuntos Contáveis, faça a correspondência entre Q*+ e N, 
mostrando como é possível fazer a correspondência entre os seus elementos, sem que haja 
números desconsiderados. 
 
GLD, LLD, Linguagem Regular 
 
1) Insira uma expressão regular que denota a linguagem L = {ω | ω ∈ Σ* e o número de b’s em 
w é par}, dado que Σ = {a,b}. 
 
2) Encontre uma expressão regular que denota todas as strings de a’s e b’s que têm pelo 
menos dois b’s consecutivos. 
 
3) As cadeias formadas pelos símbolos do alfabeto devem possuir uma sequência de um ou 
mais símbolos “b” imediatamente à direita de cada símbolo “a”. Dado que Σ = {a,b, c}. Faça a 
expressão regular e a gramática regular: 
Exemplos: {abccabc, abbabbbccbcb, caabca,abcccb, abc, bababc, b, bacacc, bcbabca, ccabb, 
... } 
 
4) Dada a expressão regular (aa* | bb*)cc*, faça a gramática regular correspondente e sua 
quádrupla G = (T,V,P,S). 
 
5) Seja o Σ= {a,b}. Encontre uma expressão regular e a gramática denotando a linguagem L = 
{ω | ω ∈ Σ* tal que toda a ocorrência de “a” em w é imediatamente seguida de “b”}. 
Autômatos Finitos, Gramáticas e Linguagens Livres de Contexto 
 
1) Considere uma gramatica G = [Σ, V, S, P], onde Σ = [a, b], V = [S,B], P = {S -> aB, B -> bC, 
C -> aB | λ}. É possível construir um autômato mínimo que processa L(G)? Caso positivo, 
desenhe o autômato. Caso negativo, explique o porquê. 
 
2) Construa um automato de estados finitos mínimo que aceite a linguagem regular L5 = {(ab)*b 
+ c*} 
 
3) Seja o alfabeto terminal Σ = {a, b}. Considere a seguir a linguagem L4 = {w = w1 ou w = 
aw2b | w1, w2 ∈ Σ*}. Escreva uma gramática G4 para gerar a linguagem L4. 
 
4) Qual gramática que define o AFD a seguir: 
 
 
 
5) Considere a seguinte gramática livre de contexto G = {{S}, {0,1}, S, P}, onde P = {S -> S | 
0S0 | 1S1 | λ} 
a) Quala linguagem gerada pela gramática? 
b) Para a cadeia 01010111101010, construa sua árvore de derivação

Outros materiais