ESTRUTURAS DISCRETAS - PROF: Carlos Augusto Ribeiro

UNIDADE I – SISTEMAS DE NUMERAÇÃO

1.1 INTRODUÇÃO

É razoável admitir que a espécie humana, mesmo nas épocas mais primitivas, tinha algum senso numérico, pelo menos ao ponto de reconhecer mais e menos quando se acrescentavam ou retiravam alguns objetos de uma coleção pequena, pois há estudos que mostram que alguns animais são dotados desse senso. Com a evolução gradual da sociedade, tornaram-se inevitáveis contagens simples.Uma tribo tinha que saber quantos eram seus membros e quantos eram seus inimigos e tornava-se necessário a um homem saber se seu rebanho de carneiros estava diminuindo. É provável que a maneira mais antiga de contar se baseasse em algum método de registro simples, empregando o princípio da correspondência biunívoca. (enumeração).Para uma contagem de carneiros, por exemplo, podia-se dobrar um dedo para cada animal. Podia-se também contar fazendo-se ranhuras no barro ou numa pedra, produzindo-se entalhes num pedaço de madeira ou fazendo-se nós numa corda.Então, talvez mais tarde, desenvolveu-se um arranjo de sons vocais para registrar verbalmente o número de objetos de um grupo pequeno. E mais tarde ainda, com o aprimoramento da escrita, foram surgindo arranjos de símbolos para representar esses números. Quando se tornou necessário efetuar contagens mais extensas, o processo de contar teve de ser sistematizado. Isso foi feito dispondo-se os números em grupos básicos convenientes, sendo a ordem de grandeza desses grupos determinada em grande parte pelo processo de correspondência empregado. Fundamentalmente o método consistia em escolher um certo número b como base e atribuir nomes aos números 1, 2, ..., b. Para os números maiores do que b os nomes eram essencialmente combinações dos nomes dos números já escolhidos. Como os dedos do homem constituíam um dispositivo de correspondência conveniente, o 10 era escolhido frequentemente como base. Considerem-se por exemplo, as palavras-números atuais na língua inglesa, formadas tomando-se 10 como base. Há os nomes especiais one (um), two (dois), ..., tem (dez) para os números 1, 2, ..., 10. Quando se chega a 11 a palavra usada é eleven, que deriva de ein lifon, cujo significado é “ um acima de dez” . Analogamente, twelve (doze) provém de twe lif (“dois acima de dez” ) e assim sucessivamente até nineteen (“nove e dez”). Chega-se então a twenty (twe-tig, ou “dois dez”).

1.2. SISTEMA DE NUMERAÇÃO POSICIONAL

Atualmente, usamos um sistema de numeração em que os dez símbolos de dígitos, 0, 1, 2, 3, ..., 9, representam o zero e os nove primeiros inteiros positivos. Um inteiro maior, como “ quatrocentos e setenta e cinco”, pode ser expresso na forma: 400 + 70 + 5 = 4.102 + 7.10 + 5 e é representado no sistema decimal pelo símbolo 475.

Página 1

Neste caso, o fato importante é que o significado dos algarismos 4,7,5 dependem de sua posição na casa das unidades, dezenas e centenas. Assim, podemos representar qualquer inteiro utilizando-se apenas os dez algarismos em diferentes arranjos. Generalizando, qualquer número inteiro positivo x pode ser escrito de maneira

única na forma: x = +... + onde b é o número

que indica a base ( inteiro maior que 1) e . Na prática representamos o

número x na base b pela sequência de símbolos onde cada símbolo

representa um múltiplo da potência .

Exemplos: 1) Considere o sistema de base 10. O número x expresso por 6283 indica:

x =

2) Considere o sistema de base 5 (sistema quinário). O número x = indica:

x =

3) Considere o sistema de base 2 ( sistema binário). O número x =

indica:x =

4) Considere o sistema de base 12 ( sistema duodecimal). O número x = (3t1e)12

onde t = 10 e e = 11 indica:x =

OBSERVAÇÃO: A invenção da “notação posicional” atribuída aos sumérios ou aos babilônios e desenvolvida pelos hindus, foi de uma enorme importância para a civilização. Os sistemas anteriores de numeração eram baseados num princípio puramente aditivo. No simbolismo romano, por exemplo, escrevia-se:MDCXVIII = mil + quinhentos + cem + dez + cinco + um + um + um para indicar o número 1618. As principais desvantagens desses sistemas aditivos são:* a necessidade de uma quantidade cada vez maior de símbolos à medida que os números se tornam maiores.* a dificuldade na computação com esses números. Já no sistema posicional, qualquer número, seja grande ou pequeno pode ser representado utilizando um número limitado de algarismos ( no sistema decimal, são os “algarismos arábicos” 0,1, 2, 3 , ..., 9). Além disso, as regras para calcular com números

Página 2

representados em notação posicional podem ser dadas sob forma de tabelas de adição e de multiplicação para números com um só algarismo, as quais podem ser memorizadas de uma vez por todas.1.3. CONVERSÃO DE UM NÚMERO DO SISTEMA DECIMAL PARA OUTROS SISTEMAS Seja x um número inteiro escrito na base 10. Para escrevermos x numa base

arbitrária b temos que determinar os números inteiros tais que :

x = +... + com .

Observe que x = +... + , ou x = x1.b +

onde x1 = +... + ,isto é, é o resto da divisão de x por b.

Fazendo o mesmo para x1, temos x1 = +... + ou

x1 = x2.b + onde x2 = +... isto é, é o resto da

divisão de x1 por b. Analogamente obtém-se os demais .

Exemplo: Representar o número 198 na base 4.

1.4. EXERCÍCIOS:

01. Em que base se tem 3.3 = 10 ? e 3.3 = 11 ? e 3.3 = 12 ?

02. a) Pode um número par ser representado em alguma base por 27? E por 37? b) Pode um número ímpar ser representado em alguma base por 72? E por 82?

03. Determine b de modo que 79 =

04. Qual a menor base em que 301 representa um inteiro quadrado?

05. Representar o número 6647 na base 12.

Página 3

06. Expresse na base 8.

07. Perguntado sobre quantos alunos havia em sua classe, um professor respondeu: “ 100 alunos, dos quais 24 são homens e 32, mulheres”. Inicialmente a resposta nos pareceu estranha, mas logo compreendemos que o professor não empregou o sistema decimal. Qual sistema usou?

08. O fato de que o sistema binário se tornou popular no mundo dos computadores se deve a duas de suas características: ele usa somente dois algarismos (0 e 1), e isso concorda bem com as duas coisas que uma lâmpada pode fazer – estar acesa ou apagada; e suas tábuas de adição e multiplicação são facilmente ensinadas a uma máquina. O preço que se paga por esta simplicidade é o comprimento bem grande de números razoavelmente pequenos.a) Expressar 1968 no sistema bináriob) Usando as tábuas de adição e multiplicação do sistema binário:

+ 1 01 10 1 0 1 0

x 1 0 1 1 0 0 0 0 Calcule i) 100101 + 11110 ii) 1101 x 110

09. Se b > 2, mostre que (121)b é um inteiro quadrado.

10. Um número de três algarismos na base 7 se expressa pelos mesmos algarismos, porém na ordem contrária, na base 9. Expresse esse número na base 10.

GABARITO: 01. 9, 8 e 7 02. a) não; sim b) sim; não 03. b = 7 04. 4 05. (3t1e)12

Página 4

06. (576)8 07. Senário (base 6) 08. a) 11110110000 b) i) 1000011 ii) 1001110 10. 248

UNIDADE II – DIVISIBILIDADE

2.1. RELAÇÃO DE DIVISIBILIDADE EM Z

Definição:

Sejam a e b dois inteiros, com a . Diz- se que a divide b (indica-se se e somente

se existe um inteiro q tal que b = aq. Também se diz que a é um divisor de b , que a é um fator de b , que b é múltiplo de a , que b é divisível por a .

Obs: Se então pois a igualdade b = aq implica b = (- a).(- q)

Exemplos: pois 15 = 3.5 ( q = 5) pois 48 = 4.12 ( q = 12 )

pois 6 = (-2).(-3) ( q = -3) pois não existe q tal que 12 = 5q

Teorema :

Sendo a , b e c inteiros quaisquer, temos:

I) , e

Dem:

II) Se , então a =

Dem:

III) Se então

Dem:

IV) Se então ( Propriedade transitiva)

Dem:

Página 5

V) Se então a =

Dem:

VI) Se com , então

Dem:

VII) Se e então para todo x, y .

Dem:

2.2. ALGORITMO DA DIVISÃO

Se a e b são dois inteiros, com b 0, então existem e são únicos os inteiros q e r que

satisfazem as condições: a = bq + r e .

Obs: I) Os inteiros q e r chamam-se respectivamente o quociente e o resto da divisão de a por b .

II) Se r = 0, temos a = bq, isto é, b é divisor de a e o quociente q é indicado por

Exemplo: Achar o quociente e o resto na divisão de a por b que satisfazem às condições do algoritmo da divisão nos seguintes casos:

a)a = 30 e b = 7 b) a = 53 e b = -12 c) a = -47 e b = 5 d) a = 3 e b = - 6

2.3. EXERCÍCIOS

01. Sejam a , b e c inteiros. Mostrar que:

Página 6

a) Se então

b) Se e se então

c) se e somente se ( c

02. Verdadeiro ou falso: Se então ou .

03. Verdadeiro ou falso: Se e se , então

04. Sendo a um inteiro qualquer, mostrar :

a) b)

05. Mostrar que , se e se então

06. Determinar os inteiros positivos que divididos por 17 deixam resto igual ao quadrado do quociente.

07. Achar inteiros a , b e c tais que mas e .

08. Mostre que é múltiplo de 3.

2.4. REPRESENTAÇÃO DE UM NÚMERO EM UMA BASE QUALQUER

Teorema:

Qualquer número inteiro positivo x pode ser escrito de maneira única na forma:

x = +... + onde b é o número que indica a base

( inteiro maior que 1) e .

Dem:

Página 7

Obs: O número x = +... + pode ser escrito

abreviadamente pela notação em que os coeficientes são

obtidos pelas sucessivas divisões de N e seus quocientes por b.

Exemplo: Escrever o número 2147 no sistema de base 5

2.5. EXERCICIOS:

01. Escrever no sistema de base 10:

a) (31322)4 b) (3141)7 c) (3141)11

02. Escrever 285 e 31415 no sistema de base 8

03.Escrever (6165)7 no sistema de base 12, denotando 10 e 11 por a e b , respectivamente.

04. Determine a base do sistema em que 73 se escreve 243.

05. Determinar a base do sistema no qual (346)7 se escreve 91.

06. Escrever (7645)8 no sistema de base 5.

07. a) Construir as tábuas de adição e de multiplicação no sistema de base 2.

b) Calcule i) (1011101)2 + (100110)2 ii) (10110)2 x (101)2

08. Existem alguns critérios simples que permitem determinar se um número é divisível por exemplo por 3, 5,9, etc. Demonstra-se por exemplo, que um inteiro é divisível por 3 se e

Página 8

somente se a soma de seus algarismos é divisível por 3. Analogamente um número é divisível por 9 se e somente se a soma de seus algarismos é divisível por 9. Determinar o algarismo x de modo que o inteiro: a) 5x9 seja divisível por 9 b) 934x1x seja divisível por 2 e 3

09. Demonstra-se que um inteiro é divisível por 4 se e somente se o número formado pelos

seus dois últimos algarismos da direita é divisível por 4. Exemplo: 57832 pois

Determinar o algarismo x de modo que o inteiro 7x6 seja divisível por 3 e 4.

10. Demonstra-se que um inteiro é divisível por 5 se seu último algarismo da direita é 5 ou 0. Determinar os algarismos x e y de modo que o inteiro 231xy seja divisível por 5 e 9.

11. Seja N = escrito no sistema decimal. Demonstra-se que N é divisível por

11 se somente se ( ) é divisível por 11.

Exemplo: 280918 pois 8 - 1+ 9 - 0 + 8 - 2 = 22 que é divisível por 11 Determinar os algarismos x e y de modo que o inteiro 34xx58y seja divisível por 9 e por 11.

12. Mostrar que todo inteiro de três algarismos, todos iguais, é divisível por 37.

13.Mostrar que a diferença entre os inteiros abc e cba (a>c) é um múltiplo de 11.

14..Mostrar que todo inteiro de seis algarismos, todos iguais, é divisível por 11.

Gabarito:

01. a) 890 b) 1107 c) 4159 02. (435)8 e (75267) 03. (12b6)1 04. 5 05. 20 06. (112010)5 07. b) i) (10000011)2 ii) (1101110)2 08. a) x = 4 b) x = 2 e x = 8 09. 5 10. x = 3 e y = 0 ou x = 7 e y = 5 11. x = 6 e y = 4

Página 9