Quem sou eu

Minha foto
Salvador, BA, Brazil
Analista de sistemas, expert em telecom, formado em Eng. Elétrica e nerd assumido

quarta-feira, 20 de outubro de 2010

Sistemas de Numeração 1 - Sistemas de Numeração Posicionais

Um sistema de numeração posicional é aquele onde o valor atribuído a cada símbolo usado na representação dos números depende da posição que ele ocupa na representação. O exemplo trivial é o sistema de numeração que estamos acostumados a utilizar no dia a dia: o sistema decimal (porque a base do sistema é 10) ou indo-arábico (por causa da origem dos símbolos - algarismos - utilizados). Considere a representação decimal 56782. O algarismo 2 vale exatamente o seu valor intrínseco, porque está posicionado na ordem de grndeza das unidades. Já o algarismo 8 tem valor posicional 80, por ocupar a ordem de grandeza das dezenas. E assim por diante com os demais algarismos.

O interessante é que esta idéia pode ser generalizada. Para entender isto primeiro precisamos provar um teorema, que poderíamos chamar de teorema geral da enumeração (TGE). Vou apresentar aqui apenas a versão da demonstração para números naturais (porque é só o que interessa para o caso dos sistemas de computação). Mas é fácil estender a prova para os números reais (sugiro que vocês tentem).


A prova que vou apresentar depende da definição da operação de divisão no conjunto dos naturais.


Para efeito de generalidade vamos supor que x seja muito maior que b. Então podemos fazer a seguinte série de divisões:


Substituindo a última expressão obtida para o quociente na penúltima, e assim por diante até voltar à primeira expressão obtida para o quociente temos:


A última expressão encontrada satisfaz às características do polinômio desejado, porque todos os coeficientes que correspondem a restos das divisões efetuadas tem valores naturais no intervalo [0,b), e o último quociente, por construção, também é um número natural no intervalo [0,b), o que prova a existência do polinômio desejado.

Para a prova da unicidade deste polinômio suponhamos que exista um outro polinômio tal que:


Os dois polinômios serão diferentes se houver pelo menos um dos coeficientes de mesma ordem de grandeza em b com valores diferentes. Então, subtraindo um polinômio do outro temos


Mas isto só é possível se todos os coeficientes dos dois polinômios forem iguais. Se quiser alongar ainda mais a prova, suponha também que o novo polinômio possa ter grau superior ao que já foi encontrado (porque menor não pode ser). Não mudaria nada o resultado. Ao subtrair um do outro fica evidente que os eventuais coeficientes dos termos de ordem superior a n também teriam que ser zero, o que prova a unicidade do polinômio encontrado.

Muito bem. E como fazemos uso deste teorema para construir todos os sistemas de numeração posicionais? Da seguinte forma: primeiro escolhemos o valor b para a base do nosso sistema; depois escolhemos um conjunto com b símbolos diferentes (não importa quais, pode ser quadradinho, estrelinha, etc.) para representar, respectivamente, as quantidades 0, 1, ... , b - 1 e são chamados de algarismos; a partir daí qualquer número natural é representado pela sequência de algarismos cujos valores correspondem aos coeficientes do polinômio de potências de b que é igual ao número a representar, com o algarismo mais à esquerda correspondendo ao coeficiente do termo de mais alta ordem do polinômio, e o algarismo mais à direita ao termo independente do polinômio.

Como o TGE garante que para qulquer valor da base escolhida existe um e somente um polinômio que satisfaz as suas regras (e no qual baseia-se o sistema de numeração daquela base), a consequência lógica é que todos os sistemaas de numeração são equivalentes. E isto nos traz duas perguntas (que responderei depois, em outros artigos):
  • Dada a representação de um número em um sistema de numeração qualquer, como obter a sua representação equivalente em um outro sistema?
  • Como generalizar os procedimentos da aritmética para que eles sejam válidos para qualquer sistema de numeração?

Os sistemas de numeração que nos interessam diretamente, além do decimal, claro, são o sistema binário (base 2) e o sistema hexadecimal (base 16). Por uma questão de familiaridade, sempre que possível usamos como algarismos os mesmos do sistema indo-arábico, com os mesmos valores intrínsecos. Então os algarismos do sistema binário são 0 e 1; e os algarismos do sistema hexadecimal são 0, 1, 2, 3, 4, 5, 6, 7, 8. 9, A (representando o valor decimal 10), B (representando o valor decimal 11), C (representando o valor decimal 12), D (representando o valor decimal 13), E (representando o valor decimal 14) e F (representando o valor decimal 15),

No próximo artigo desta série vou responder à primeira das perguntas que deixei pendentes.

7 comentários:

  1. Parabéns, Smolka, pelo excelente texto. Aguardo ansiosamente a continuação do tema.
    Um abração carioca!
    Paulo Sérgio Argolo
    Rio de Janeiro, RJ

    ResponderExcluir
  2. Prof. Desculpe se estiver errado mas a questão de unicidade não foi bem provada.

    ResponderExcluir
  3. Bom... Pode não ser uma prova bonitinha (afinal de contas, não estou conduzido o assunto com *todo* o rigor matemático). Mas me parece que a unicidade ficou bem provada. Você poderia ser mais específico quanto à parte da prova que você achou incompleta ou que esteja faltando?

    ResponderExcluir
    Respostas
    1. TODOS OS SISTEMAS DE NUMERAÇAO SAO POSICIONAIS?

      Excluir
    2. Não. Além dos sistemas posicionais (que nos interessam) existem os sistemas aditivos, onde cada símbolo tem valor fixo, e o número representado é obtido pela adição dos valores individuais de cada símbolo.

      O principal exemplo deste tipo é o sistema romano de numeração.

      Excluir
  4. Desculpe-me incomodar.
    mais gostaria de saber sobre

    Como surgiram:

    - O Sistema de Numeração Decimal.
    - O Sistema Decimal Posicional.
    - Sistema de Numeração Romana.

    ResponderExcluir
    Respostas
    1. A origem dos sistemas de numeração posicionais (entre eles o nosso sistema decimal - ou indo-arábico, considerando a herança cultural que o legou) é bastante antiga.

      Cerca de 3100 AC os Babilônios usavam um sistema de numeração posicional de base 60, aperfeiçodo a partir de um sistema de numeração não posicional herdado dos Sumérios e dos Acádios. Ainda temos traços culturais deste sistema, por exemplo, nos nossos minutos de 60 segundos e horas de 60 minutos, bem como na divisão do círculo em 360 graus. (referência http://en.wikipedia.org/wiki/Babylonian_numerals).

      No período anterior à unificação da China (de 575 AC a 221 AC, aproximadamente), os chineses já usavam um sistema de numeração decimal, embora os algarismos fossem representados de cinco em cinco - o que provavelmente influenciou a maneira como os ábacos foram construídos (referência http://en.wikipedia.org/wiki/Counting_rods).

      Da China para a Índia, o sistema aperfeiçoou-se. Os indianos chegaram à forma moderna do nosso sistema decimal no século 6. Através do comércio, os árabes tomaram conhecimento deste sistema, e passaram a usá-lo. Com a expansão muçulmana até a Europa, este conhecimento chegou a nós (referência http://en.wikipedia.org/wiki/Numeral_system).

      BTW, os Maias desenvolveram independentemente um sistema de numeração posicional de base 20, que tem muita semelhança com o sistema chinês (referência http://en.wikipedia.org/wiki/Maya_numerals).

      Já o sistema romano de numeração evoluiu a partir do sistema etrusco, que aparentemente descende de um método simples para registro de contagem (referência http://en.wikipedia.org/wiki/Roman_numerals).

      Excluir