A Lógica Binária – Álgebra Booleana

Por volta do século III a.C., o matemático indiano Pingala inventou o sistema de numeração binário. Ainda usado atualmente no processamento de todos computadores modernos, o sistema estabelece que sequências específicas de uns e zeros podem representar qualquer número, letra ou imagem.

Em 1703 Gottfried Leibniz desenvolveu a lógica em um sentido formal e matemático, utilizando o sistema binário. Em seu sistema, uns e zeros também representam conceitos como verdadeiro e falso, ligado e desligado, válido e inválido. Levou mais de um século para que George Boole publicasse a álgebra booleana (em 1854), com um sistema completo que permitia a construção de modelos matemáticos para o processamento computacional. Em 1801 apareceu o tear controlado por cartão perfurado, invenção de Joseph Marie Jacquard, no qual buracos indicavam os uns, e áreas não furadas indicavam os zeros. O sistema está longe de ser um computador, mas ilustrou que as máquinas poderiam ser controladas pelo sistema binário.

As máquinas do início do século XIX utilizavam base decimal (0 a 9), mas foram encontradas dificuldades em implementar um dígito decimal em componentes eletrônicos, pois qualquer variação provocada por um ruído causaria erros de cálculo consideráveis.

O matemático inglês George Boole (1815-1864) publicou em 1854 os princípios da lógica booleana, onde as variáveis assumem apenas valores 0 e 1 (verdadeiro e falso), que passou a ser utilizada a partir do início do século XX.

Álgebra booleana

Na matemática e na ciência da computação, as álgebras booleanas (também conhecida como “Álgebra de Boole”) são estruturas algébricas que “capturam a essência” das operações lógicas E, OU e NÃO, bem como das operações da teoria de conjuntos soma, produto e complemento. Ela também é o fundamento da matemática computacional, baseada em números binários.

Receberam o nome de George Boole, matemático inglês, que foi o primeiro a defini-las como parte de um sistema de lógica em meados do século XIX. Mais especificamente, a álgebra booleana foi uma tentativa de utilizar técnicas algébricas para lidar com expressões no cálculo proposicional. Hoje, as álgebras booleanas têm muitas aplicações na electrônica. Foram pela primeira vez aplicadas a interruptores por Claude Shannon, no século XX.

Os operadores da álgebra booleana podem ser representados de várias formas. É frequente serem simplesmente escritos como E, OU ou NÃO (são mais comuns os seus equivalentes em inglês: AND, OR e NOT). Na descrição de circuitos também podem ser utilizados NAND (NOT AND), NOR (NOT OR) e XOR (OR exclusivo). Os matemáticos usam com frequência + para OU e . para E (visto que sob alguns aspectos estas operações são análogas à adição e multiplicação noutras estruturas algébricas) e representam NÃO com uma linha traçada sobre a expressão que está a ser negada.

Uma álgebra booleana é um reticulado (lattice) (A, ∧, ∨) com as quatro propriedades adicionais que seguem:

  1. limitado inferiormente: Existe um elemento 0, tal que a ∨ 0 = a para qualquer a em A.
  2. limitado superiormente: Existe um elemento 1, tal que a ∧ 1 = a para qualquer a em A.
  3. lei distributiva: Para quaisquer a, b, c em A, (ab) ∧ c = (ac) ∨ (bc).
  4. existência de complementos: Para qualquer a em A existe um elemento ¬a em A tal que a ∨ ¬a = 1 e a ∧ ¬a = 0.

Destes axiomas, podemos mostrar directamente que o elemento menor 0 e o elemento maior 1 são únicos, que todo o elemento tem um só complemento, que

a ∧ 0 = 0 e a ∨ 1 = 1,
¬1 = 0 e ¬0 = 1, e que as Leis de De Morgan
¬(ab) = (¬a) ∧ (¬b)
¬(ab) = (¬a) ∨ (¬b)

são válidas. A versão dual da lei distributiva,

(ab) ∨ c = (ac) ∧ (bc)

também se verifica. Em geral, qualquer lei sobre álgebras Booleanas podem ser transformadas em outra, igualmente válida, lei “dual” pela troca de 0 por 1 e ∧ por ∨, e vice-versa.

Como qualquer reticulado, uma álgebra Booleana pode ser vista como um conjunto parcialmente ordenado (POSET) definindo-se

ab sse a = ab

(o que é equivalente a b = ab).

  • A mais importante álgebra Booleana tem apenas 2 elementos, 0 e 1, e é definida pelas regras
0 1
0 0 0
1 0 1
0 1
0 0 1
1 1 1

Isso tem aplicação em lógica, onde 0 é interpretado como “falso”, 1 é “verdadeiro”, ∧ é “e”, ∨ é “ou”, e ¬ “não”. Expressões envolvendo variáveis e operações Booleanas representam formas de indicações, e as tais duas expressões podem ser mostradas para ser usadas igualmente utilizando o axioma acima se e somente se as formas indicadas correspondentes forem equivalentes lógicos.

A álgebra Booleana de dois elementos é também utilizada no projeto de circuitos em engenharia elétrica; aqui 0 e 1 representam os dois diferentes estados de um bit em um circuito digital, tipicamente alta e baixa voltagem.

Os circuitos são descritos por expressões contendo variáveis, e as tais duas expressões são iguais para todos os valores das variáveis se e somente se o circuito correspondente tiver o mesmo comportamento de entrada-saída.

Além disso, cada possibilidade do comportamento de entrada e saída pode ser modelada pela expressão Booleana apropriada.

A álgebra booleana binária é também importante na teoria geral de álgebras booleanas, porque uma equação envolvendo diversas variáveis é verdadeira em todas as álgebras booleanas se e só se é verdadeira na álgebra booleana de dois elementos. Isto pode, por exemplo, ser usado para mostrar que os seguintes teoremas (Teoremas de consenso) são válidos em todas as álgebras booleanas em geral:

(ab) ∧ (¬ac) ∧ (bc) = (ab) ∧ (¬ac)
(ab) ∨ (¬ac) ∨ (bc) = (ab) ∨ (¬ac)
  • O conjunto das partes de um conjunto S forma uma álgebra booleana com as operaçôes ∨ = união e ∧ = intersecçâo. O menor elemento 0 é o conjunto vazio e o maior elemento 1 é o próprio conjunto S.
  • O conjunto dos subconjuntos finitos ou co-finitos de um conjunto S, com as operações de união e interseção é uma álgebra Booleana.

Um homomorfismo entre as álgebras Booleanas A e B é uma função f: AB tal que para todos a, b em A:

f(ab) = f(a) ∨ f(b)
f(ab) = f(a) ∧ f(b)
f(0) = 0
f(1) = 1

Segue-se que fa) = ¬f(a) para todo a em A.

A classe de todas as álgebras Booleanas, com esta noção de morfismo, forma uma categoria. Um isomorfismo de A para B é um homomorfismo bijetivo de A para B. O inverso de um isomorfismo é ainda um isomorfismo, e chamamos as duas álgebras Booleanas A e B de isomorfas. Do ponto de vista da teoria das álgebras Booleanas, elas não podem ser distinguidas entre si; somente diferem na notação de seus elementos.

Quanto à Lógica Binária:

A lógica binária, ou bitwise operation é a base de todo o cálculo computacional. Na verdade, são estas operações mais básicas que constituem todo o poderio dos computadores. Qualquer operação, por mais complexa que pareça, é traduzida internamente pelo processador para estas operações.

O operador unário NOT, ou negação binária resulta no complemento do operando, ou seja, será um bit ‘1’ se o operando for ‘0’, e será ‘0’ caso contrário, conforme podemos confirmar pela tabela de verdade, onde A é o bit de entrada e S é o bit-resposta, ou bit de saida:

   |  A  |  S  |
 --+-----+-----+
   |  0  |  1  |
 --+-----+-----+
   |  1  |  0  |
 --+-----+-----+

O operador binário AND, ou conjunção binária devolve um bit 1 sempre que ambos operandos sejam '1', conforme podemos confirmar pela tabela de verdade,  onde A e B são bits de entrada e S é o bit-resposta, ou bit de saida:

 |  B  |  A  |  S  |
 +-----+-----+-----+
 |  0  |  0  |  0  |
 +-----+-----+-----+
 |  0  |  1  |  0  |
 +-----+-----+-----+
 |  1  |  0  |  0  |
 +-----+-----+-----+
 |  1  |  1  |  1  |
 +-----+-----+-----+

O operador binário OR, ou disjunção binária devolve um bit 1 sempre que pelo menos um dos operandos seja '1', conforme podemos confirmar pela tabela de  verdade, onde A e B são os bits de entrada e S é o bit-resposta, ou bit  de saida:

 |  B  |  A  |  S  |
 +-----+-----+-----+
 |  0  |  0  |  0  |
 +-----+-----+-----+
 |  0  |  1  |  1  |
 +-----+-----+-----+
 |  1  |  0  |  1  |
 +-----+-----+-----+
 |  1  |  1  |  1  |
 +-----+-----+-----+

O operador binário XOR, ou disjunção binária exclusiva devolve um bit 1 sempre que apenas um dos operandos é '1', conforme podemos confirmar pela tabela de verdade:

 |  B  |  A  |  S  |
 +-----+-----+-----+
 |  0  |  0  |  0  |
 +-----+-----+-----+
 |  1  |  0  |  1  |
 +-----+-----+-----+
 |  0  |  1  |  1  |
 +-----+-----+-----+
 |  1  |  1  |  0  |
 +-----+-----+-----+

O operador unário de bit shifting, ou deslocamento bit-a-bit,  equivale à multiplicação ou divisão por 2 do operando que, ao contrário  dos casos anteriores, é um grupo de bits, e consiste no deslocamento  para a esquerda ou para a direita do grupo de bits. O bit inserido é  sempre 0, e o bit eliminado pode ser opcionalmente utilizado (flag CF  dos registos do processador).

 ( 101011(43) >> 1 ) =    010101[1]  
 ( 101011(43) << 1 ) = [1]010110
Anúncios