Matemática Discreta

Contagem

Problemas de contagem se resumem muitas vezes em determinar o número de elementos em algum conjunto finito.

Principio da Multiplicação

Se existem N1 resultados possíveis para um primeiro exemplo e N2 para um segundo, então existe N1, N2 resultados possíveis para a seqüência dos dois eventos.

Este principio é útil para se contar o numero total de possibilidades para uma tarefa que pode ser dividida em uma seqüência de etapas sucessivas.

Ex: 1- Quantas linhas te uma tabela-verdade com três letras de proposição? Desenha a TV utilizando uma arvore de possibilidades.

2 – Uma criança pode escolher uma entre duas balas, uma azul e outra vermelha, e um entre três chicletes, um amarelo outro verde e outro branco. Quantos conjuntos diferentes a criança pode ter? Desenhe a arvore de possibilidades.

Principio de Adição

Se A e B são eventos disjuntos com N1 e N2 resultados possíveis, respectivamente, então o numero total de possibilidades para o evento “A ou B” é n1 + n2. Este principio é útil para se contar o numero total de possibilidades para a tarefa para a tarefa que pode ser divida em casos disjuntos.

Os dois princípios podem ser utilizados de forma conjuntos.

Ex1 – Queremos selecionar uma sobremesa entre três e quatro bolos. De quantas maneiras isto pode ser feito?

Ex2 – A ultima parte do seu numero de telefone possui quatro dígitos. Quantos desses números de quatro dígitos existem?

Ex3 – Com relação ao Exemplo 1, quantos números e quatro dígitos existem se um mesmo digito não puder ser repetido? Resp. 5040

Ex4 - Se um homem tem quatro termos, oito camisas e cinco gravatas, de quantas maneiras ela pode se vestir?

Ex5 – Um consumidor deseja comprar um veiculo em uma concessionária A concessionário tem 23 automóveis e 14 caminhões. Quantas escolhas possíveis o consumidor tem?

Ex6 – Uma criança pode escolher entre duas balas, uma vermelha e um azul, e três chicletes, um amarelo, um verde e m branco.

Ex7 – Se uma mulher tem sete blusas, cinco saias e nove vestidos, de quantas maneiras diferentes ela pode se vestir?

Ex8 – Quantos inteiros de 3 dígitos (entre 100 e 999, inclusive) são pares?

Principio da Inclusão e Exclusão

Para desenvolver este principio, deve observar primeiro que, se A e B são subconjuntos de um conjunto universo S, então A-B, B-A e A^B são disjuntos dois a dois. Imagem no caderno.

Ex1.Usando as identidades básicas simplifique a seguinte expressão:

(A-B) U (B-A) U (A ^ B)=AUB

A-B = A^B‘

(A^B‘)U(B^A‘)U(A^B)

(A^B)U(B^(A‘U A)) // S = (A‘U A) // B=(B^(A‘U A))

(A^B‘)UB=(AUB)^(BUB‘)

O nome Principio da Inclusão e Exclusão vem do fato que ao contar o numero de elementos na união de A e B, precisamos “incluir” (contar) o numero de elementos de A e os de B, mas precisamos “excluir” (subtrair) os elementos de A^B para evitar conta-los duas vezes. Sendo assim para dois conjuntos, a formula para contagem se dá por:

|AUB|= |A|+|B|-|A^B|

Ex2: Um pesquisador de opinião publica entrevista 35 eleitores todos apoiando o candidato 1, o candidato 2 ou ambos, e descobrir que 14 eleitores apóiam o candidato 1 e 26 apóiam o candidato 2. Quantos eleitores apóiam ambos?

Resposta: Cinco eleitores

Para três conjuntos, a forma deste principio é:

|AUBUC|= |A|+|B|+|C|-|A^B|-|A^C|-|B^C|+|A^B^C|

Generalizando este principio, temos:

-Considere os conjuntos finitos A1,.., Na, n>=2

Ver caderno. 123

Ex3. Um grupo de estudantes está planejando encomendar pizzas. Se 13 comem calabresa, 10 comem salame, 12 comem queijo chedar, 4 comem tanto calabresa quanto salame, 5 comem tanto salame quanto chedar, 7 comem tanto calabresa quanto chedar e 3 comem de tudo. Quantos estudantes há no grupo?

Ex4. Um feirante vende apenas brócolis, cenoura e cebola. Em um dia o feirante atende 207 pessoas. Se 114 pessoas compraram brócolis, 152 compraram cenoura, 25 compraram cebola, 64 compraram brócolis e cenoura, 12 compraram cenoura e cebola e 9 compraram os três produtos. Quantas pessoas compraram brócolis e cebola?

Principio das Casas de Pombos

Este principio recebeu este nome da seguinte idéia: se mais de K pombos entram em K casas de pombos, então pelo menos uma casa vai ter mais de um pombo.

Ex1. Quantas pessoas precisam estar presentes em uma sala para garantir que duas delas tenham o primeiro nome começando com a mesma letra?

Resposta: 27, pois é necessário a da quantidade de letras do alfabeto +1.

Ex2. Quantas vezes é preciso jogar um dado para garantir que um mesmo valor apareça duas vezes?

Resposta: 7, lados do dado + 1

Casa dos Pombos Generalizada

Se tivermos n casas para dispor Kn+1 elementos, então ao menos uma casa contem K+1 elementos.

Ex1. Em um grupo e 40 pessoas, é verdade, que pelo menos quatro pessoas possuem o mesmo signo?

Sim, pois necessitamos de 12*3+1=37 pessoas.

Leis e Composição Interna (LCI)

Seja E um conjunto e S uma parte do produto cartesiano E x E. Toda -aplicação (estrela):S->E é denominada lei de composição interna (LCI) em E. Quando S= E x E dize-se que a LCI está completamente definida ou que a lei é uma operação em E.

Uma LCI sobre E, associa a cada par ordenado (x,y) e E x E ao elemento definido por x(estrela)y e é denotado por (x,y)->x(estrela)y

O elemento x(estrela)y passa a ser denominado composto de x e y relativo a (estrela); e x e y passam a ser os termos do compostos x(estrela)y.

O conjunto S, que é o domínio da aplicação (estrela), passa a ser também o domínio LCI.

Ex1: Sejam E=Inteiros e a operação (estrela) definida por x(estrela)y =x+y para todo (x,y) e Z x Z (Inteiro x Inteiro).

(x,y)=(1,2) | 1(estrela)2= 1+2=3

(5/8) | 5(estrela)8=5+8=13

Seja E um conjunto e (estrela): E x E -> E uma LCI sobre E. Seja A e E um subconjunto não vazio do E.

Diz-se que A é fechado em relação à lei (estrela) se para todo (x,y) pertencente à A x A tem-se x(estrela)y pertencente à A.

Ex2. Sejam E={...,-2,-1,0,1,2,...} e A={...,-4,-2,0,2,4,...}. Mostre que A é fechado em relação às leis de adição (+) e multiplicação (*) sobre Z (inteiros).

Toda e qualquer multiplicação e adição entre números pares são valores pares.

Adição (*) x*y=x+y

X=2*M

Y=2*N

M e N pertencem aos Inteiros

.x*y = x+y= 2m+2n = 2(m+n) pertencente à A, (m+n)pertencente aos inteiros.

Tábua de uma LCI

Quando o conjunto é finito, uma LCI pode ser representado através de uma tabela.

Seja E={a,a2,...,an} n>=1, um conjunto de elementos e seja * uma LCI sobre E, A tabelada da LCI * sobre E é dada por:

*

A1

A2

...

.An

Coluna fundamental

A1

A1* A1

A2* A1

...

.An* A1

A2

A1* A2

A2* A2

...

.An* A2

...

...

...

...

...

.An

A1*.An

A2*.An

...

.An*.An

Coluna Fundamental

A leitura é feito linha por coluna. As operações que não estão definidas são representadas por ‘||’.

Ex: Seja E={1,2,3,4} pertencente à Naturais e considere a LCI de subtração (-). Qual a tábua desta lei? Esta lei é uma operação?

-

1

2

3

4

1

||

||

||

||

2

1

||

||

||

3

2

1

||

||

4

3

2

1

||

Ex: Seja E={1,3,5,15,30} e *:mdc(x,y), para todo x,y pertencente à E. Qual a tabua desta lei? Esta lei é uma operação sobre E?

mdc

1

3

5

15

30

1

1

1

1

1

1

3

1

3

1

3

3

5

1

1

5

5

5

15

1

3

5

15

15

30

1

3

5

15

30

Propriedades de uma tábua de LCI

Algumas propriedades de uma LCI podem ser estruturadas quando a lei é dada por uma tábua.

a)Comutativo: Uma operação * é comutativo se a tábua for simétrica em relação a diagonal principal.

Ex: x*y = y*x

*

A

B

C

E

A

C

A

E

A

B

A

E

C

B

C

E

C

B

C

E

A

B

C

E

b) Elemento Neutro: (e*x=x=x*e): Para encontrar o elemento neutro para a operação *, procura-se o elemento que pertence a intersecção da linha com a coluna em que estão repetidos a linha e colunas fundamentadas.

Para as tábuas dos exercícios anteriores, identifique qual o elemento neutro.

c)Elemento Simétricos: para determinar à simétrico e um elemento a pertencente E, basta verificar se estão satisfeitos as relações a*a’=e e a’*a=e

d)Elementos Regulares: Um elemento A é regular quando, composto com elementos distintos, produz resultados distintos.

Em uma tábua, um elemento A é regular quando na linha e na coluna de a não haver resultados iguais.

Propriedades Algébricas de uma LCI

a) Associativa: Seja E um conjunto e *:ExE->E uma LCI em E. Diz-se que * é associativa se dados x,y,z e E vale-se a igualdade.
(x*y)*z = x*(y*z)
Ex: Seja E= Inteiros (Z) um conjunto e *:ZxZ->Z uma LCI sobre Z definida por a*b = a+b-ab para todo par pertencente ZxZ. Mostre que * é associativa.
(x*y)*z = x*(y*z)
(x+y-xy)*z = x*(y+z-yz)
xz+yx-xyz = xy+xz-xyz

b) Comutativa: Diz-se que * é comutativa se x*y = y*z.
Ex: Verifique se a*b é comutativo

c) Elemento Neutro: Um elemento A pertence à E é denominado neutro se para todo x pertencente à E tem-se:
x*A=x=e*A
O elemento neutro, se existe, é único.
Ex: Verifique se para a lei * definida por a*b = a+b-ab, existe elemento neutro.
x*e = x
x+e – xe = x
e = 0
Obs: Para se encontrar o elemento neutro não se desenvolve o exercício, somente se analisa em busca de um valor que torne a equação valida.

d) Elementos Simetrizaveis: Um elemento A pertencente à E é dito simetrizavel se existir A pertencente à E tal que:
a*a’ = b e a’*a=b
No caso de existir a’, este é denominado simétrico de a.
Ex: Identifique os elementos simétricos para a lei * definida por a*b = a+b-ab
a’*a = e
a’+a-a’a = 0
a’=-a/1-a (Não é encontrado simétrico quando a==1)

e) Distributiva: Seja E um conjunto e * = ExE->E e ∆ é distributiva a direito em relação a’ * se:
(x*y) ∆ x = (x∆y)*(z∆x)
e que ∆ é distributiva a esquerda de * se:
x∆(y*z) = (x∆y)*(x∆z)
Caso ∆ seja distributiva tanto a esquerda quanto a direita de *, diz que é totalmente distributiva em relação à *.
Se ∆ for comutativo , então a distributiva esquerda e direita são equivalentes.
Obs: Observar quem está inferindo, pois ∆ sobre * é diferente de * sobre ∆.

Ex: Seja E=Inteiros e *:ZxZ->Z e ∆:ZxZ->Z duas LCI sobre Z definidas por x*y= x+y-3 e x∆y = x.y. Verifique se ∆ é distributiva em relação à *.
∆ é comutativa? Sim xy = yx
Distributiva à esquerda
x∆(y*z) = (x∆y)*(x∆z)
x∆(x+z-z) = xy * zx
xy + xz – 3x != xy + zx - 3
∆ não é distributiva em relação à *.
Ex2: Verifique se * é distributiva em relação à ∆.
Ex3: Verifique se a lei de multiplicação em Z é distributiva em relação à lei de adição em Z.
∆: multiplicação (*)
*: adição (+)
∆ é comutativo? Sim
Distribuição à esquerda:
x∆(y*z) = (x∆y)*(x∆z)
x∆(y+z) = xy*xz
xy+xz = xy + xz
∆ é distributiva em relação à *.
1) Em cada caso abaixo considere a operação * sobre E. Verifique se * é associativa, comutativa, se possui neutro e determine os simetrizaveis.
a) E em Inteiros e x*y = (x+y)/2
Associativa=>
(x*y)*z = x*(y*z)
z*(x+y)/2 = x*(y+z)/2
(zx+zy+2z)/2 != (xy+xz+2x) /2
Como as expressões não são iguais a operação não é associativa.
Comutativa=>
x*y = y*x
(x+y)/2 = (y+x)/2
Neutro=>
x*e = x
(x+e)/2 = x
Não existe elemento neutro.
Obs: O elemento neutro necessita ser um elemento único, ou seja, não pode ser igual à x.
Simetrizaveis
a*a = e
Não é simetrizavel
b)* sobre inteiros x inteiros e (x,y)*(s,t) = (xs,xt+ys)
Comutativa=>
(x,y)*(s,t) = (s,t)*(x,y)
(xs,st+ys) = (sx,sy+tx)
É comutativa pois as expressões são equivalentes.
Associativa=>
((x,y)*(s,t))*(u,v) = (x,y)*((s,t)*(u,v))
(xs,xt+ys)*(u,v) = (x,y)* (su,sv+tu)
(xsu,xsv+xtv+ysv) = (xsu,xsv+xtu+xsv+ysu)
Neutro=>
(x,y)*(e1,e2) = (x,y)
(xe1,xe2+ye1) = (x,y)
Logo (e1,e2)==(1,0).
Simétricos=>
(x,y)*(x’,y’) = (1,0)
(xx’,xy’+yx’) = (1,0)
x’=1/x y’= -yx/x
Existe simétrico para x!= 0.

Grupos e SubGrupos

Seja G um conjunto não vazio e *(x,y)|->(x*y) uma LCI em G. Diz-se que G é um grupo em relação a lei se:
a) a*(b*c)= (a*b)*c ASSOCIATIVA

b) Existe e tal que x * e = e*a=a, para todo e qualquer a pertencente à G NEUTRO

c) se a pertencente à G então a’ € G tal que a*a’=e SIMETRICO

O par (G,*) é denominado grupo em relação a operação *. Caso * por comutativa então (G,*) é denominada grupo abeliano.

Seja (G,*) um grupo. Seja H um subgrupo não vazio de G. Diz-se que H é subgrupo de G se:

a) Para todo a,b € H, a*b €H. Isto é fechado em relação a operação .
b) (H,) também é grupo em relação a *.

Em uma tábua, para que um subconjunto não vazio H c G seja um subconjunto de G é necessário que:
¥ a,b € H=> a*b’ € H, onde H=>a*b’ € H, onde b’ é o simétrico de b.

Ex: Seja G= Inteiro e a LCI (*) definido por x*y = x+y-3 para todo x, y € G. Verifique se o par (G,*) é um grupo.

Associativa:

(x*u)*z = x*(y*z)

(x+y-3)*z = x*(y+z-3)

x+y-3+z-3 = x+y-z-3-3

x+y+z-6 = x+y+z-6

É associativa.

Simétricos

x*x’=e

x+x’-z = 3

x’= 6-x

É simétrico, pois para todo x existe um simétrico.

Neutro

x*e = x

x+e-3 = x

e = 3

Possui elemento neutro.

Ex: Seja E= {e,a,b,c,d,f} e a operação * dada por:

*

e

a

b

c

d

f

e

e

a

b

c

d

f

a

a

b

c

d

f

e

b

b

c

d

f

e

a

c

c

d

f

e

a

b

d

d

f

e

a

b

c

f

f

e

a

b

c

d

Admita a propriedade associativa, mostre que (E,*) é um grupo abeliano.

Verifique se são subgrupos:
{e} é subgrupo
Comutativa (analisar a diagonal principal)
Neutro = e (analisar primeira linha e coluna)
Simétrico = {(a,f),(b,d),...}(combinações que geram o elemento neutro)
{b} não é subgrupo
{e,c} é subgrupo
{a,f} nao
{e,b,d} é subgrupo

Grupo das Permutações

Seja E um conjunto não vazio e S(E) o conjunto de todas as bijeções de E.

Como sabe-se, f◦g, ¥ f, g pertence S(E) é uma LCI em S(E), associativo, possui neutro e todo elemento S(E) é simetrizável.

O grupo (S(E), ◦) é chamado grupo das permutações sobre E.

Se E={1,2,...,n}, n>=1, S(E) pode ser indicado por Sn, sendo Sn um grupo de ordem n!

Um elemento f e Sn é representado como:

F = { 1 2 ... n ->Dominio

i1 i2 ... in } ->Imagem

Ex1: Faca a operação de composição em S4 para os seguintes elementos:

(1 2 3 4) ◦(1 2 3 4) = (1 2 3 4)

(2 4 1 3) (3 1 4 2) (1 2 3 4)

Ex2:

a)Faça a tábua do grupo das permutações (S(E), ◦) para S2.
E ={1,2}

S(E)= {F1 = (1 2)

(1 2)

F2 = (1 2)

(2 1)}

◦

F1

F2

F1

F1◦f1 = f1

F1◦f2 = f2

F2

F2◦f1 = f2

F2◦f2 = f1

b) (G,*) com G = ZxZ e * definido por (x,y)*(s,t)=(x+s, y+t)

Associativa - ok

((x,y)*(s,t))*(u,v)= (x,y)*(s,t)*(u,v)

Neutro - ok

(x,y)*(e1,e2)=(x,y)

(e1,e2)=(0,0)

Simétricos – ok

Comutativa - ok

Ex. Faça a quarta coluna da tábua do grupo das permutações (S(E), ◦) para S3.

E = {1,2,3}

Abaixo somente imagens

F1 = (1,2,3)

F2 = (2,3,1)

F3 = (3,1,2)

F4 = (1,3,2)

F5 = (3,2,1)

F6 = (2,1,3)

◦

F1

F2

F3

F4

F5

F6

F1

F1◦ F4=f1

F2

F2◦ F4=f2

F3

F3◦ F4=f3

F4

F4◦ F4=f4

F5

F5◦ F4=f5

F6

F6◦ F4=f6