Exercícios Preliminares da Matemática Para Linguagens Formais e Autômatos

1.         Se A = {1, 2} e B = {x, y, z} então: A x B = {      };

        R:

        {1, 2} x {x, y, z} = { (1,x), (1, y), (1, z), (2, x), (2, y), (2, z) }

2.         Se A e B são os conjuntos de 1) então A x B x A = {    };

        R:

        A x B x C = {(1,x), (1, y), (1, z), (2, x), (2, y), (2, z) } x { 1, 2 }

A x B x A = {(1,x,1), (1,x,2), (1,y,1), (1,y,2), (1,z,1), (1,z,2), (2,x,1), (2,x,2), (2,y,1),

                      (2,y,2), (2,z,1), (2,z,2)}

3.         Se A tem a elementos e B tem b elementos, quantos elementos tem A x B? Explique sua resposta;

        R:

        Como A e B são conjuntos finitos, então |A x B| = |A| * |B|.

        Foi fado que |A| = a e |B| = b.

        Então, o número de elementos será a*b.

        

4.          Se C é um conjunto com c elementos. Quantos elementos têm o conjunto Potência de C?

                R:

                O conjunto potência de um conjunto A é dado por 2|A|, nesse caso, como temos um

                conjunto C que possui c elementos, o conjunto potência de C será 2c.

5.         Seja X = {1, 2, 3} e Y = {a, b}. Calcule:

1. X x Y;

R:

{1,2,3} x {a,b} = {(1,a), (1,b), (2,a), (2,b), (3,a), (3,b)}

1. Y x X;

R:

{a,b} x {1,2,3} = {(a,1), (a,2), (a,3), (b,1), (b,2), (b,3)}

1. Y x Y = Y2;

R:

Y x Y = {(a,a), (a,b), (b,a), (b,b)}

1. X x Y x Y = X x Y2;

R:

Y2 = {(a,a), (a,b), (b,a), (b,b)}

X x Y2 = { (1,a,a), (1,a,b), (1,b,a), (1,b,b), (2,a,a), (2,a,b), (2,b,a), (2,b,b), (3,a,a),

                   (3,a,b), (3,b,a), (3,b,b) }

      6.Seja N = {a, b, c, d} o conjunto dos vértices de um grafo;

Seja A = {[a, b], [b, a], [b, c], [b, d], [c, b], [c, d], [d, a], [d, d]};

Dê as principais características do grafo descrito acima, faça o diagrama e classifique-o (tipo, grau, etc.)

R:[pic 1]

[pic 2][pic 3]

[pic 4]

[pic 5][pic 6][pic 7]

[pic 8][pic 9]

[pic 10][pic 11]

                

        Podemos classificar o grafo acima como sendo cíclico, orientado (ou dirigido), não

        valorado e conexo  

        Grau de emissão de cada vértice:

A: 1

B: 3

C: 2

D: 2

Grau de recepção de cada vértice:

A: 2

B: 2

C: 1

D: 3

1. Uma descrição formal de um grafo é dada por:

({1, 2, 3, 4, 5}, {(1, 2), (2, 3), (3, 4), (4, 5), (5, 1)})

        Desenhe o grafo e dê suas principais características.

        R:

[pic 12][pic 13]

[pic 14]

[pic 15][pic 16]

[pic 17][pic 18][pic 19]

[pic 20][pic 21]

Podemos classificar o grafo acima como sendo cíclico, não orientado (ou não dirigido), não

        valorado e conexo

1. Uma descrição formal de um grafo é dada por:

({1, 2, 3, 4}, {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)})

        Desenhe o grafo e dê suas principais características

R:

[pic 22][pic 23]

[pic 24][pic 25]

[pic 26][pic 27][pic 28]

[pic 29][pic 30]

[pic 31]

Podemos classificar o grafo acima como sendo cíclico, não orientado (ou não dirigido), não

        valorado e fortemente conexo, regular (todos os seus vértices tem o mesmo grau) e