Exercícios resolvidos 1 - operação Binária

Exercícios resolvidos 1 - operação Binária

(Parte 1 de 2)

Antes do inıcio

Algumas observacoes, antes do inıcio da lista de exercıcios resolvidos:

• Os exercıcios foram colocados em ordem crescente de dificuldade. Os que iniciam com “A”

(Ex.: A1, A2, etc.) sao os mais faceis, os que iniciam com “B” (Ex.: B1, B2, etc.) sao os “medios” e os que iniciam com “C” sao os mais difıceis.

• Para demonstrar que determinada propriedade e valida em um conjunto, e preciso usar elementos genericos x,y,z, etc. desse conjunto. Veja, por exemplo, os dois primeiros itens da solucao de A6.

• Para mostrar que determinada propriedade nao e valida, basta encontrar um contra-exemplo no qual a propriedade falhe. Neste caso, escolhemos alguns valores para as variaveis x,y,z, etc. e testamos se a propriedade falha nesse exemplo particular. Se a primeira escolha nao funcionar, entao tentamos uma segunda escolha e assim, por tentativas, prosseguimos ate encontrarmos um exemplo no qual a propriedade falhe. Veja, por exemplo, o segundo item da solucao de A7.

• As vezes, e conveniente testar alguns casos particulares para tentarmos obter determinadas informacoes. Veja, por exemplo, o terceiro item da solucao de A7 ou a solucao de B2.

Operacoes binarias – exercıcios resolvidos

Verifique: a) se tem elemento neutro; b) se e comutativa; c) quais sao os elementos de A que sao invertıveis.

Solucao:

a) Primeiramente, vamos verificar se a operacao e comutativa. Para isso, verificamos que a parte da tabua que esta acima da diagonal que vai do canto superior esquerdo ao inferior direito e simetrica com relacao a parte que esta abaixo da diagonal.

b) Agora, vamos verificar se a operacao tem elemento neutro. Observamos a primeira linha da tabua (o cabecalho) e verificamos se ela se repete em algum lugar. Ela se repete na linha do elemento ♦. Isso signifca que: ♦ ♥ = ♥, ♦ ♠ = ♠, ♦ ♦ = ♦ e ♦ ♣ = ♣. Logo, ♦ e um elemento neutro a esquerda para a operacao .

Observamos novamente a tabua para ver se a primeira coluna se repete em algum lugar. Verificamos que ela se repete no elemento ♦. Isso significa que ♦ e um elemento neutro a direita. Portanto, ♦ e o elemento neutro da operacao .

Verifique se ? tem elemento neutro, se e comutativa e quais sao os elementos de B que sao invertıveis.

Solucao:

• A primeira linha da tabela se repete na ultima linha, a linha que corresponde ao elemento 5. Note que a primeira coluna se repete tambem na coluna que corresponde ao elemento 5. Isso significa que o e = 5 e o unico elemento neutro dessa operacao.

• A tabela e simetrica com relacao a diagonal que inicia na parte superior esquerda e termina na parte inferior direita. Logo, a operacao e comutativa.

• O elemento neutro e aparece na tabua apenas uma unica vez, como resultado da operacao 5 ? 5 = 5 = e. Isso significa que o 5 e o unico elemento invertıvel e o inverso do 5 e igual a ele mesmo.

• x ⊕ y = resto da divisao de x + y por 5. Construa a tabua dessas duas operacoes sobre o conjunto A.

Solucao: Alguns exemplos:

Prosseguindo dessa forma, obtemos as seguintes tabelas:

Solucao: Como X so tem 3 elementos, entao so podem existir 3 funcoes constantes definidas de X em X:

Observando a tabua, vemos que a primeira linha da tabua (o cabecalho) nao se repete em lugar algum; logo, a operacao nao tem elemento neutro a esquerda. Por outro lado, note que a primeira coluna se repete 3 vezes na tabua; isso significa que a

A5) Considere a seguinte operacao ∗ definida sobre o conjunto dos numeros racionais:

Verifique se ∗ e comutativa, se e associativa, se tem elemento neutro e se existem elementos invertıveis.

Solucao:

comutativa.

• Suponhamos que e seja o elemento neutro dessa operacao. Entao, por exemplo,

• Se a operacao nao tem elemento neutro, entao nao faz sentido a definicao de elemento invertıvel.

A6) Considere a seguinte operacao ⊕ definida sobre o conjunto dos numeros reais nao negativos:

Verifique se ⊕ e comutativa, se e associativa, se tem elemento neutro e se existem elementos invertıveis.

Solucao:

x para todo x real nao negativo. Elevando a ultima igualdade ao quadrado, obtemos: e2 + x2 = x2 e, daı, chegamos a e2 = 0, ou seja, e = 0. Assim, o zero

todo x real nao negativo.

• Dado um real nao negativo a, seu inverso (simetrico) e o real nao negativo b tal

A7) Considere a seguinte operacao ∗ definida sobre o conjunto dos numeros reais: x ∗ y = 2x·y. Verifique se ∗ e comutativa, se e associativa e se tem elemento neutro.

Solucao:

(distributividade a direita da multiplicacao

•(a2+ab)︸︷︷ ︸x
+(ab+b2)=((a2+ab)︸︷︷ ︸x

Observacao. O objetivo deste exercıcio e mostrar que varias propriedades da adicao e da multiplicacao estao “escondidas” em uma formula tao conhecida como essa do quadrado da soma. E essencial, por exemplo, a multiplicacao ser comutativa para que a formula seja valida. Por exemplo, com matrizes quadradas A e B nao e valida a formula (A + B)2 = A2 + 2AB + B2 em geral.

B1) Quantas operacoes diferentes e possıvel definir em um conjunto A que tenha exatamente n elementos? Entre essas operacoes, quantas sao comutativas?

Solucao: Uma operacao fica perfeitamente determinada se conhecermos sua

entaohaumtotalden·n·n...n︸︷︷ ︸

Como a quantidade total de • e n2, e cada uma pode ser preenchida com n opcoes, n2 fatores

Se a operacao for comutativa, entao ao preenchermos a diagonal e a parte acima da diagonal, a operacao ja fica determinada. A parte que esta abaixo da diagonal fica determinada por simetria. O total de • que esta na diagonal e acima dela e de

temosqueototaldeoperacoescomutativaseden·n·n···n︸︷︷ ︸

Observacao. A quantidade de operacoes e um numero gigantesco, mesmo para valores pequenos de n. Por exemplo, quando n = 4 ha um total de n(n2) = 416 = 4294967296 (mais de 4 bilhoes) operacoes que podem ser definidas; entre elas, um

Solucao: Suponhamos que o elemento neutro dessa operacao seja e. Entao, por

numero real nao nulo.

Concluımos dessa forma que a operacao ∗ tem elemento neutro quando a = b = 0 e

Solucao:

realmente o elemento neutro da operacao.

Logo, ∗ e associativa.

(Parte 1 de 2)

Comentários