01/04/2024

Álgebra booleana e o Python

Primeiro um pouquinho de história

Há cerca de 2.500 anos, os filósofos gregos já se envolviam em desafios de lógica, explorando problemas que exigiam um pensamento estruturado para alcançar conclusões corretas.

Conhecidos como "problemas de lógica", esses exercícios demandavam a aplicação de regras de dedução e análise para chegar a uma solução baseada nas informações fornecidas.

Em 1847, o matemático inglês George Boole introduziu os conceitos de lógica simbólica, demonstrando que a lógica podia ser representada por equações algébricas.

Boole introduziu três operadores fundamentais: E, OU e NÃO (em inglês, AND, OR e NOT), os quais eram utilizados em um domínio restrito a apenas dois valores: 1 e 0, representando respectivamente Verdadeiro e Falso, ou Sim e Não.

Atualmente conhecida como álgebra booleana, essa estrutura matemática para lidar com o raciocínio lógico se tornou fundamental, não apenas na matemática e na filosofia, mas também na ciência da computação.

Em 1937, cerca de 75 anos após a morte de Boole, o matemático estadunidense Claude Shannon, então estudante no MIT, estabeleceu a relação entre a álgebra booleana e os circuitos eletrônicos, associando os estados lógicos (Sim e Não) a diferentes potenciais elétricos no circuito.

Voltando à atualidade

--

Em todas as linguagens de programação temos algum tipo de variável específico para guardar esses valores booleanos.

Em Python o tipo dessas variáveis se chama Boolean, que aceita os valores True e False (Verdadeiro e Falso).

Os operadores fundamentais introduzidos por Boole também estão em todas as linguagens de programação. Em Python eles são: and, or e not, como os originais, em inglês, porém em minúsculas, e são chamados de Operadores Lógicos:

  • and (e): Operador dual, opera sobre dois valores, à esquerda e à direita, e retorna True se ambos os valores forem True, senão retorna False.
  • or (ou): Operador dual, opera sobre dois valores, à esquerda e à direita, e retorna True se algum dos dois valores for True, senão retorna False.
  • not (não): Operador unário, opera sobre um valor, à direita, e retorna True, se este for False, ou False, se for True.

Com esses operadores é possível calcular um novo valor booleano, baseado em um ou mais valores booleanos.

Porém, novos valores booleanos podem ser calculados também utilizando outro tipo de operadores, os Operadores de Comparação. Estes operam sobre dois valores, à esquerda e à direita, chamados operandos. No Python os Operadores de Comparação são:

  • == (igual a): Retorna True se os operandos forem iguais.
  • != (diferente de): Retorna True se os operandos forem diferentes.
  • < (menor que): Retorna True se o operando esquerdo for menor que o operando direito.
  • > (maior que): Retorna True se o operando esquerdo for maior que o operando direito.
  • <= (menor ou igual a): Retorna True se o operando esquerdo for menor ou igual ao operando direito.
  • >= (maior ou igual a): Retorna True se o operando esquerdo for maior ou igual ao operando direito.

Para todos os operadores acima, caso não seja atendida a condição para retornar True, retornam o único outro valor booleano, False.

Atenção ao operador de comparação de igualdade, que é composto de dois sinais de igual, "==", não apenas um.

Em Python o operador de apenas um sinal de igual, "=", é o Operador de Atribuição.

  • = (atribuição): A variável, à esquerda, recebe o valor da expressão, à direita.

Para montar expressões lógicas complexas utilizando os operadores lógicos e de comparação, podemos necessitar de ajuda de parênteses, "(" e ")", para definir precedências. O mesmo uso que as expressões matemáticas fazem dos parênteses.

Exemplo matemático do uso de parênteses: Eu quero calcular o dobro do dinheiro que está no meu bolso e na minha mochila. Tenho R$10 no bolso e R$20 na mochila.

Conta errada: 2 * 10 + 20 = 40

Conta correta: 2 * ( 10 + 20 ) = 60

A segunda conta é a correta pois, com o auxílio dos parênteses, fica claro que, especificamente na resolução desta expressão, a soma deve ser feita antes da multiplicação.

"Chega de papo! Mostre-me o código!"

Operadores Lógicos

Primeiro inicializando algumas variáveis, com o operador de atribuição:

verdadeiro1 = True
verdadeiro2 = True
falso1 = False
falso2 = False

Obs.: Em Python o uso do símbolo "#" indica o início de um comentário, que é um texto livre, não sendo considerado como um trecho de código da linguagem.

Exemplos de uso do "and":

resultado = verdadeiro1 and verdadeiro2 # resultado recebe True
resultado = verdadeiro1 and falso1 # resultado recebe False
resultado = falso1 and verdadeiro1 # resultado recebe False
resultado = falso1 and falso2 # resultado recebe False

Exemplos de uso do "or":

resultado = verdadeiro1 or verdadeiro2 # resultado recebe True
resultado = verdadeiro1 or falso1 # resultado recebe True
resultado = falso1 or verdadeiro1 # resultado recebe True
resultado = falso1 or falso2 # resultado recebe False

Exemplos de uso do "not":

resultado = not verdadeiro1 # resultado recebe False
resultado = not falso1 # resultado recebe True

Os exemplos acima cobrem todas as combinações de valores possíveis e mostram os resultados das aplicações dos operadores.

Geralmente, é mais fácil visualizar toda a informação dos exemplos acima utilizando um recurso conhecido como Tabela Verdade, mostrada abaixo.

Nesta Tabela Verdade apresento:

  • duas variáveis, "p" e "q", com todas as possíveis combinações dos valores "True" e "False"; e
  • os resultados da aplicação, sobre estas variáveis, dos 3 operadores lógicos já apresentados.

Operadores de Comparação

Primeiro inicializando algumas variáveis:

numero1 = 10
numero2 = 10
numero3 = 20
texto1 = "letras"
texto2 = "letras"
texto3 = "palavra"

Observação: Os operadores de comparação podem comparar qualquer tipo de variável, dependendo da configuração do tipo, não apenas número e texto. Porém, para simplificar, vou utilizar apenas números e textos na montagem dos exemplos abaixo.

resultado = numero1 == numero2 # resultado recebe True
resultado = numero1 != numero2 # resultado recebe False
resultado = numero1 < numero2 # resultado recebe False
resultado = numero1 < numero3 # resultado recebe True
resultado = numero1 > numero3 # resultado recebe False
resultado = texto1 <= texto2 # resultado recebe True
resultado = texto1 <= texto3 # resultado recebe True
resultado = texto1 >= texto3 # resultado recebe False

Expressão lógica

Uma expressão lógica sempre retorna um valor booleano. Algumas operaram apenas valores booleanos, como no primeiro exemplo abaixo. Porém, é mais comum que envolvam vários tipos de variáveis e operadores, como nos demais exemplos.

Exemplo puramente booleano:

terminou = True
no_prazo = True
resultado = terminou and no_prazo # resultado recebe True

Exemplo com outros tipos de variáveis e operadores:

ganha_bonus = num_faltas <= 1 and tarefas_entregues > 20

Obs.: Esse exemplo não precisa de parênteses, pois no Python a precedência dos Operadores de Comparação é maior que dos Operadores Lógicos. Ou seja, caso não sejam utilizados parênteses para indicar outra ordem, o operador lógico sempre será o último a ser avaliado.

Supondo a inicialização das variáveis conforme as atribuições abaixo:

num_faltas = 1
tarefas_entregues = 17

Segue uma demonstração, passo a passo, de como o Python resolveria a expressão que calcula o ganha_bonus:

Regra do passo a passo: O que é destacado em negrito em uma linha é avaliado e o resultado é destacado em vermelho na próxima linha.

ganha_bonus = num_faltas <= 1 and tarefas_entregues > 20
ganha_bonus = True and tarefas_entregues > 20
ganha_bonus = True and False
ganha_bonus = False

"Pelo resultado da expressão lógica, não ganharei o bônus. 😭"

Novo exemplo, imaginando que a expressão para calcular o ganha_bonus foi alterada:

ganha_bonus = num_faltas <= 1 and (tarefas_entregues > 20 or se_formou)

Atente que agora a expressão tem parênteses, forçando que a avaliação do or ocorra antes da avaliação do and, apesar de este aparecer primeiro na expressão.

Supondo a inicialização das variáveis conforme as atribuições abaixo:

num_faltas = 1
tarefas_entregues = 17
se_formou = True

Segue, novamente, um passo a passo:

ganha_bonus = num_faltas <= 1 and (tarefas_entregues > 20 or se_formou)
ganha_bonus = True and (tarefas_entregues > 20 or se_formou)
ganha_bonus = True and (False or se_formou)
ganha_bonus = True and (False or True)
ganha_bonus = True and True
ganha_bonus = True

"Ainda bem que a regra da empresa mudou! Bônus! 😁🎉"

Valores booleanos utilizados fora de expressões lógicas

Além de serem utilizados para calcular outros valores booleanos, os valores booleanos são vitais para viabilidade de praticamente 100% dos programas.

Isso, porque valores booleanos são necessários em comandos de decisão, como por exemplo, if (se) e while (enquanto).

Breve explicação desses comandos:

  • if : Uma condição de execução. Ex.: Se um valor booleano é verdadeiro, faça alguma coisa.
  • while : Um laço de repetição. Ex.: Enquanto um valor booleano for verdadeiro, faça alguma coisa.

Nesses locais, onde um valor booleano é necessário, caso o valor apresentado não seja booleano, este valor é convertido para booleano, apenas para avaliação da condição.

Para forçar a conversão de um valor para booleano, simulando o que acontece em um comando que necessita um valor booleano, podemos utilizar a função bool.

Todos os tipos padrão em Python podem ser convertidos para Boolean. E a ideia é um tanto intuitiva. Tudo que "parece vazio ou nulo" é convertido em False, o resto é convertido True.

resultado = bool(7891.23) # resultado recebe True
resultado = bool(0) # resultado recebe False
nome_informado = "Anselmo"
nome_nao_informado = ""
resultado = bool(nome_informado) # resultado recebe True
resultado = bool(nome_nao_informado) # resultado recebe False
lista_com_conteudo = [1, 'a', False]
lista_vazia = []
resultado = bool(lista_com_conteudo) # resultado recebe True
resultado = bool(lista_vazia) # resultado recebe False
dict_com_conteudo = {'nome': "Anselmo", 'idade': 56}
dict_vazia = {}
resultado = bool(dict_com_conteudo) # resultado recebe True
resultado = bool(dict_vazia) # resultado recebe False

Objetos de classes criadas pelo programador também podem ter regras para conversão em Boolean, mas aí seria papo para outro artigo. 😉

Falando em conversão

"Tudo" pode ser convertido em booleano, mas... Booleano pode ser convertido em quê?

Aí voltamos à história. Mais exatamente a George Boole. Lembra que ele definiu que os possíveis valores da álgebra booleana seriam restritos a 1 e 0?

Pois bem, em Python os valores booleanos, True e False, são conversíveis apenas para o tipo numérico, respectivamente para 1 e 0.

Assim, onde é esperado um valor numérico e se encontra um booleano, este é automaticamente convertido para 1 ou 0.

Por exemplo: O Operador Aritmético de soma, "+", espera encontrar dois valores numéricos para operar. Assim sendo, veja o que acontece com a seguinte expressão:

resultado = 123 + True # resultado recebe 124

Pelo exemplo acima, esse recurso não parece muito útil, mas pode ser útil, sim.

O próximo exemplo demonstra uma possível utilidade.

Digamos que a empresa onde você trabalha dobra um auxílio que você recebe, se você atender a pelo menos duas dessas condições: ter filhos, ter pets, morar longe.

A expressão para calcular se seu auxílio dobrará poderia ser assim:

dobra_auxilio = (tem_filhos and tem_pets) or (tem_pets and mora_longe) or (mora_longe and tem_filhos)

Porém, utilizando a conversão automática de booleano em numérico, sem perder a legibilidade do código, podemos simplificar a expressão assim:

dobra_auxilio = (tem_filhos + tem_pets + mora_longe) >= 2

"Bem fácil de entender! Certo?"

Curto-circuito

"Avaliação de curto-circuito", também conhecida "avaliação preguiçosa", é um recurso bem útil nas expressões lógicas. Significa que as vezes o Python não precisa avaliar todas as partes de uma expressão para calcular o resultado desta.

Antes de julgar a "preguiça" do Python 😁, saiba que muitas vezes nós mesmos utilizamos esse tipo de "curto-circuito" em nosso raciocínio. Por exemplo, ao calcular a seguinte expressão matemática:

resultado = 0 × ( 3,1415926535 / 2,7182818284 )

É bem provável que você responda rapidamente que o resultado é 0 (zero), não por ser um gênio (Desculpe-me por isso!), mas sim por saber que qualquer número multiplicado por zero resultará em zero. Então, porque perder tempo calculando o que está à direita do sinal de multiplicação?

Essa é uma "preguiça" muito válida.

Sempre que o Python encontra uma expressão com dois valores e um operador, assim:

variavel_a_esquerda determinado_operador variavel_a_direita

O Python trabalha da seguinte forma:

  1. Avalia o variavel_a_esquerda.
  2. Verifica se o valor de variavel_a_esquerda causa um curto-circuito em determinado_operador.
    • Se sim, já tem o resultado da expressão e não executa os próximos passos.
    • Se não, segue para o próximo passo.
  3. Avalia variavel_a_direita.
  4. Se necessário, avalia a operação de determinado_operador sobre os dois valores avaliados. Senão, assume o valor de variavel_a_direita.

Esse quarto passo pode soar estranho. "Como assim 'se necessário'?"

Porém, fará sentido quando eu der outro exemplo de raciocínio matemático humano. Ao calcular a seguinte expressão matemática:

resultado = 0 + 3,1415926535

É bem provável que você responda rapidamente que o resultado é o valor à direita do sinal de adição, pois somar zero a um valor, não altera este valor. Você simplesmente ignora o "0 +" e entende que a expressão equivale à:

resultado = 3,1415926535

Seguindo a mesma lógica do passo 4 do funcionamento do Python, seu raciocínio não vai avaliar a operação sobre os dois valores, pois não é necessário.

Para não parecer que os exemplos de raciocínio matemático humano sempre incluem o 0 (zero), pense que você também simplificaria essa expressão:

resultado = 1 × 3,1415926535

Assim:

resultado = 3,1415926535

Importante: Python só utiliza "avaliação preguiçosa" com Operadores Lógicos. Nunca com qualquer outro operador. Nem nas expressões matemáticas utilizadas nos exemplos de raciocínio humano, acima.

Repetindo a tabela verdade aqui para nos ajudar a perceber os possíveis curtos-circuitos:

  • Quando é usado or:
    • Caso o valor de p seja True, não importa o valor de q, o resultado já está definido como True.
    • Caso o valor de p seja False, este valor pode ser ignorado, pois o resultado da expressão será igual ao valor de q.
  • Quando é usado and:
    • Caso o valor de p seja True, este valor pode ser ignorado, pois o resultado da expressão será igual ao valor de q.
    • Caso o valor de p seja False, não importa o valor de q, o resultado já está definido como False.

Na prática

Para ver como isso funciona na prática, vou detalhar quais seriam os passos do Python ao avaliar a seguinte expressão:

selecionado = condicao or ( teste and (situacao and not (excecao or valor >= 90)))

  • Avalia a variável condicao, notando que está à esquerda de um or:
    • Se condicao for True, o Python atribui True a selecionado e ignora todo o resto da expressão, interrompendo o processo de avaliação da expressão.
    • Se condicao for False, ignora esse valor, pois o resultado dessa expressão será o valor à direita do or, e continua a avaliação.
  • Avalia a expressão dentro do primeiro parênteses, iniciando pela variável teste, notando que teste está à esquerda de um and:
    • Se teste for False, o Python ignora todo o resto da expressão dentro do primeiro parênteses e assume False como valor para este perênteses. Assim, selecionado recebe False, lembrando que no passo anterior foi decidido ignorar o valor de condicao.
    • Se teste for True, ignora esse valor, pois o resultado dessa expressão será o valor à direita do and, e continua a avaliação.
  • Avalia a expressão dentro do segundo parênteses, iniciando pela variável situacao:
    • Como situacao está à esquerda de um and, passa por uma situação parecida com a da variável teste, descrita acima.
  • Se chegar a avaliar a expressão dentro do terceiro parênteses, inicia pela variável excecao:
    • Como excecao está à esquerda de um or, passa por uma situação parecida com a da variável condicao, descrita acima.

Ou seja, durante a avaliação de uma expressão lógica há várias possibilidades de interrompermos o processo por já termos o resultado final. Python aproveita todas essas oportunidades sendo "preguiçoso" e economizando recursos computacionais e tempo.

Operador ternário (não recomendado)

Um dos usos desses curto-circuitos é definir um valor de acordo com uma condição, utilizando apenas uma expressão (operador ternário), ao invés de utilizar uma comando de condição de execução, if.

Este trecho de programa, por exemplo:

if condicao:
    cargo = 'gerente'
else:
    cargo = 'funcionário'

pode ser escrito em uma expressão assim:

cargo = condicao and 'gerente' or 'funcionário'

Se você exclamou "Como é que é?!", calma. Vamos analisar.

    Supondo que condicao igual a True

Sendo condicao igual a True e estando à esquerda de um and, este valor é ignorado e o resultado da operação é o que está à direita do and. Então a expressão passa a ser:

valor = 'gerente' or 'funcionário'

Um operador lógico (or) requer dois valores booleanos, assim, valor 'gerente', não sendo vazio ou nulo, é entendido como equivalente a um True.

Quando temos um valor True (ou equivalente) à esquerda de um or, este é o resultado da operação, não importando o que está a direita do or. Então a expressão passa a ser:

valor = 'gerente'

    Supondo que condicao igual a False

Sendo condicao igual a False e estando à esquerda de um and, não importa o que está à direita do and, o resultado da operação será False. Então a expressão passa a ser:

valor = False or 'funcionário'

Quando temos um valor False à esquerda de um or, este é ignorado e o resultado da operação é o que está à direita do or. Então a expressão passa a ser:

valor = 'funcionário'

Comprovamos assim que esse operador ternário funciona corretamente, é equivalente à versão utilizando o if.

Essa construção é um pouco inusitada, mas encontrada em códigos Python por aí, então é bom saber como compreendê-la.

Segue uma forma simples de lembrar o funcionamento desse operador ternário:

resultado = condicao and valor_se_verdadeiro or valor_se_falso

Porém, como destacado logo no subtítulo, é uma construção "não recomendada". Os motivos são:

  • não tem boa legibilidade
  • apresenta problemas quando os possíveis valores, valor_se_verdadeiro e valor_se_falso, são equivalentes a False; que seria o caso de 0 (zero), "" (texto vazio), [] (lista vazia), entre outros.

Valor default

Outro uso desses curto-circuitos é definir um "valor por omissão" (default value), que é o valor a ser assumido na falta de definição.

Para entender melhor, primeiro imagine que uma função, executa_algo, que retorna texto vazio ("") se tudo correu bem, ou uma mensagem de erro, caso haja algum erro.

Exemplo de trecho de programa utilizando o retorno da função executa_algo para montar uma mensagem:

erro_na_funcao = executa_algo()
if erro_na_funcao:
    mensagem = erro_na_funcao
else:
    mensagem = "Programa executado sem erros"

Esse trecho de programa pode ser simplificado para:

mensagem = executa_algo() or "Programa executado sem erros"

Vamos analisar.

Python avalia o valor à esquerda do or, que é a função executa_algo.

Supondo que executa_algo() retorne "Erro X"

mensagem = "Erro X" or "Programa executado sem erros"

O valor à esquerda do or será avaliado com o booleano True, o que fará o Python ignorar o valor à direita, ficando assim a expressão:

mensagem = "Erro X"

Supondo que executa_algo() retorne ""

mensagem = "" or "Programa executado sem erros"

O valor à esquerda do or será avaliado com o booleano False, o que fará o Python ignorar este valor e assumir o valor da direita, ficando assim a expressão:

mensagem = "Programa executado sem erros"

Comprovamos assim que o curto-circuito para valor defult funciona corretamente, é equivalente à versão utilizando o if.

Operador ternário (forma recomendada)

Como, ao falar de curto-circuito, mostrei a forma não recomendada do operador ternário, não posso deixar de falar da forma recomendada.

Lembrando o exemplo dado para a forma não recomendada:

cargo = condicao and 'gerente' or 'funcionário'

Utilizando a forma recomendada fica assim:

cargo = 'gerente' if condicao else 'funcionário'

É muito mais legível! Em português leríamos isso assim:

"cargo é igual a 'gerente', se condição, senão é igual a 'funcionário'"

Além de melhorar a legibilidade, não tem nenhum problema com os tipos e valores da expressões nas três posições do operador ternário.

Segue uma forma simples de lembrar o funcionamento desse operador ternário recomendado:

resultado = valor_se_verdadeiro if condicao else valor_se_falso

"Valores restritos a 1 e 0"

Tudo até aqui foi inspirado pela álgebra criada por George Boole para operar valores restritos a 1 e 0.

"Valores restritos a 1 e 0. Onde mais eu vi isso? 🤔"

No bit!

O nome bit é a contração de binary digit, dígito binário, ou "que só aceita dois valores".

Em números na base binária, cada dígito pode ter dois diferentes valores: 0 ou 1.

Lembrando: Utilizamos diariamente em nossas vidas números da base decimal, nos quais cada dígito pode ter 10 diferentes valores: 0, 1, 2, 3, 4, 5, 6, 7, 8 ou 9.

Convencionou-se chamar de byte um conjunto de oito bits.

Sempre que falamos, nos mais variados contextos, em megabytes, gigabytes etc., estamos nos referindo a múltiplos de byte. Consequentemente, também a múltiplos de bit.

Tudo em computação está baseado em bits!

Voltando à história: Quando Claude Shannon relacionou a Álgebra de Boole aos circuitos eletrônicos com dois estados lógicos, ele estava criando operadores para trabalhar com bits.

Esses operadores é que proporcionaram toda revolução tecnológica que se viu deste então.

Representação de números no Python

Antes de seguir, precisamos relembrar como os números inteiros são represenados em binário, pois isso tem muito a ver com a forma como esses números são armazenados, em bits, na memória do computador. 

Vamos cobrir todos os tipos de representação de números inteiros no Python

Uma vez que os "números na base decimal" são os que utilizamos no nosso dia a dia, nos acostumamos a chamá-los apenas de "números".

Para servir de base de comparação, apresento exemplos de representação de números inteiros (no caso, apenas inteiros não negativos):

0 ; 1 ; 2 ; 3 ; 4 ; 8 ; 10 ; 16 ; 20 ; 32 ; 100 ; 256 ; 1000 ; 1024

Na computação, além de trabalharmos com representações de números na base decimal, também é bem comum trabalharmos com representações em outras três bases:

  • Base 2: números binários ou números na base binária
    • números representados iniciando com "0b" (zero e letra "b")
    • seguido pela representação binária do número, com um ou mais dígitos, que podem assumir valores de 0 ou 1
  • Base 8: números octais ou números na base octal
    • números representados iniciando com "0o" (zero e letra "o")
    • seguido pela representação octal do número, com um ou mais dígitos, que podem assumir valores 0, 1, 2, 3, 4, 5, 6 ou 7
  • Base 16: números hexadecimais ou números na base hexadecimal
    • números representados iniciando com "0h" (zero e letra "h")
    • seguido pela representação hexadecimal do número, com um ou mais dígitos, que podem assumir valores 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e ou f

Abaixo, como exemplo, vou repetir os mesmos números listados anteriormente.

Representações de números binários:

0b0 ; 0b1 ; 0b10 ; 0b11 ; 0b100 ; 0b1000 ; 0b1010 ; 0b10000 ; 0b10100 ; 0b100000 ; 0b1100100 ; 0b100000000 ; 0b1111101000 ; 0b10000000000

Representações de números octais:

0o0 ; 0o1 ; 0o2 ; 0o3 ; 0o4 ; 0o10 ; 0o12 ; 0o20 ; 0o24 ; 0o40 ; 0o144 ; 0o400 ; 0o1750 ; 0o2000

Representações de números hexadecimais:

0x0 ; 0x1 ; 0x2 ; 0x3 ; 0x4 ; 0x8 ; 0xa ; 0x10 ; 0x14 ; 0x20 ; 0x64 ; 0x100 ; 0x3e8 ; 0x400

Bitwise Logical Operators (Operadores Lógicos Bit-a-Bit)

A lógica dos operadores sobre bits é a mesma que já vimos para operadores de valores booleanos, mas não funciona com as mesmas palavras-chave no Python.

Esses operadores trabalham com um ou dois valores numéricos inteiros, retornando um novo valor numérico inteiro, em que cada bit do valor retornado é resultado da operação lógica dos bits, nas posições equivalentes, dos valores envolvidos na operação.

São esses os Operadores Lógicos Bit-a-Bit do Python:

  • & (and bit-a-bit) (caractere "e comercial")
  • | (or  bit-a-bit) (caractere pipe ou barra vertical)
  • ~ (not  bit-a-bit) (caractere til)
  • ^ (xor  bit-a-bit) (caractere circunflexo)

"Opa! XOR??"

Sim, os Operadores Lógicos Bit-a-bit têm um operador a mais que os Operadores Lógicos "booleanos".

O operador ^ (xor) retorna 1 se apenas um dos dois bits operados for 1. Se ambos os bits forem 0 ou ambos os bits forem 1, o resultado será 0.

Apesar de eu achar que o Python poderia ter um operador lógico "booleano" xor, entendo que, na prática, ele é muito mais útil em seu uso bit-a-bit. Então OK ficar sem um xor. Até porque, o caso tem solução, siga a leitura para entender.

Segue uma nova tabela verdade. Agora com os 4 operadores lógicos bit-a-bit e com 1 e 0 no lugar de True e False.

Obs.: Na hora de contar ou indexar os bits dentro de um byte, é costume fazê-lo da direita para a esquerda, começando pelo bit menos representativo. Lembrando que a indexação, como de costume, começa pelo índice 0 (zero).

Esse é o número 42 em representação binária:

0b00101010

Esse número apresenta ligados (com valor 1) o segundo, o quarto e o sexto bit.

Podemos também dizer que estão ligados os bits 1, 3 e 5.

Ou seja, o "bit 0" é o "primeiro bit" à direita, o "bit 1" é o "segundo bit", e assim por diante.

Agora seguem os primeiros exemplos em Python do resultado dos operadores lógicos bit-a-bit, operando dois números:

resultado = 0b0010 & 0b0111 # resultado recebe 0b0010
resultado = 0b111100 & 0b010110 # resultado recebe 0b010100
resultado = 0b0010 | 0b0111 # resultado recebe 0b0111
resultado = 0b111100 | 0b010110 # resultado recebe 0b111110
resultado = 0b0010 ^ 0b0111 # resultado recebe 0b0101
resultado = 0b111100 ^ 0b010110 # resultado recebe 0b101010

Repetindo os exemplos acima, porém mostrando os números em representação decimal, afinal não precisam estar em representação binária para serem operados bit-a-bit:

resultado = 2 & 7 # resultado recebe 2
resultado = 60 & 22 # resultado recebe 20
resultado = 2 | 7 # resultado recebe 7
resultado = 60 | 22 # resultado recebe 62
resultado = 2 ^ 7 # resultado recebe 5
resultado = 60 ^ 22 # resultado recebe 42

Ainda não apresentei o operador ~ (não) pois, ao operar um número bit-a-bit, geralmente este muda de sinal (positivo para negativo ou vice-versa) e isso, com certeza, causaria estranheza, se visto antes de entender a próxima explicação.

Além disso, em todos os exemplos acima, por simplificação, estávamos lidando apenas com inteiros não negativos.

Para evitar esse "medo" de trabalhar com os números negativos, temos que entender a técnica utilizada para armazená-los em bits na memória do computador.

Números inteiros em bits na memória

Se não fosse pelos números negativos esse assunto seria muito simples. Então vamos nos aprofundar principalmente em tudo que envolve os negativos.

Quando pedimos para o Python nos mostrar a representação de qualquer número negativo, simplesmente ele coloca um sinal negativo, "-", a esquerda do valor absoluto do número.

Assim, a representação do -10 em base decimal é, obviamente, o sinal "-" seguido no valor absoluto, que é 10. Ou seja: "-10".

Da mesma forma, para representar o número -10 nas outras três bases, é como se pegássemos a representação do valor absoluto:

  • 10 na base binária: "0b1010"
  • 10 na base octal: "0o12"
  • 10 na base hexadecimal: "0xa"

E inseríssemos, antes dessa representação, um sinal "-":

  • -10 na base binária: "-0b1010"
  • -10 na base octal: "-0o12"
  • -10 na base hexadecimal: "-0xa"

As representações de números negativos acima são bem simples de entender.

Destaquei as representações binárias, pois estas nos ajudarão a entender a técnica utilizada para o armazenamento dos valores em bits na memória.

Relação entre a representação binária e o armazenado em bits:

  • Números não negativos (positivos e zero):
    • A representação binária de números não negativos é equivalente à forma como o número é armazenado em bits na memória.
  • Números negativos:
    • A representação binária de números negativos NÃO é equivalente à forma como o número é armazenado em bits na memória.

A computação já passou por várias técnicas para lidar com esse armazenamento de inteiros negativos. Algumas até bem intuitivas, mas com desvantagens práticas.

A técnica mais utilizada hoje em dia chama-se Complemento a Dois (Two’s Complement). Apesar de menos intuitiva, traz muitas vantagens para cálculos.

Vamos à explicação.

Primeiramente é importante saber que o bit utilizado para indicar que um número armazenado é negativo é o bit mais representativo. Ou seja, o bit mais à esquerda. O índice desse bit depende da quantidade de bits utilizada para representação do número na memória do computador.

Para facilitar o entendimento, vou imaginar aqui que estamos em um "computador bem limitado", que dispõe de apenas 3 bits para representar um número inteiro com sinal.

Em 3 bits podemos representar até 8 valores diferentes. Seriam 4 com sinal negativo e 4 sem sinal negativo. Lembrando que entre os números sem sinal consta o 0 (zero).

Primeiro vou mostrar como os números ficam na memória desse nosso imaginado "computador bem limitado", depois explico o método.

Listo abaixo, em ordem crescente, todos os possíveis valores inteiros desse computador limitado.

Cada linha inicia com uma demonstração de como o número é armazenado em bits na memória, depois aparece o próprio número em base decimal e, por fim, sua representação em base binária (adicionando zeros á direita para melhor comparação com os 3 bits do armazenamento):

  • 100-4 = -0b100
  • 101-3 = -0b011
  • 110-2 = -0b010
  • 111-1 = -0b001
  • 000 →  0 =  0b000
  • 001 →  1 =  0b001
  • 010 →  2 =  0b010
  • 011 →  3 =  0b011

Em negrito está o bit que representa o sinal.

Em verde vê-se que todos os não negativos têm o armazenado em bits e a representação binária similares.

Em vermelho vê-se que os negativos, em geral, têm o armazenado em bits e a representação binária diferentes.

Aplicação da técnica de Complemento a Dois:

  • O maior número positivo é igual à metade do número de possíveis valores, menos 1.
    • Em nosso exemplo, metade de 8, que é 4, menos 1, que é 3.
  • Números não negativos, de zero até o máximo positivo, são representados nos bits de memória exatamente como na representação na base binária.
  • Números negativos são representados executando os seguintes passos:
    • pega-se a representação do número absoluto (como se fosse positivo)
    • invertem-se todos os bits (complemento a um)
    • soma-se 1 (um)

Exemplos:

  • número 2 na memória é 010, pois:
    • 2 = 0 × 2² + 1 × 2¹ + 0 × 2°
    • 2 em binário com 3 dígitos: 010
    • igual à representação em Python: 0b010
  • número -3 na memória é 101, pois:
    • 3 = 0 × 2² + 1 × 2¹ + 1 × 2°
    • 3 em binário com 3 dígitos: 011
    • invertendo todos os bits: 100
    • somando 1: 101
    • diferente da representação em Python: -0b011

Tudo entendido. "Tomara! 🤞"

Operador ~ (não bit-a-bit)

Seguem exemplos em Python do resultado do operador bit-a-bit de negação, apresentando entre colchetes "[]" os bits de armazenamento:

resultado = ~  0b010 [010] # resultado receberá -0b011 [101]
resultado = ~ -0b001 [111] # resultado receberá  0b000 [000]

Repetindo os exemplos acima, porém mostrando os números em representação decimal (lembrando da suposição de um computador que utiliza 3 bits para representar inteiros com sinal):

resultado = ~  2 [010] # resultado receberá -3 [101]
resultado = ~ -1 [111] # resultado receberá  0 [000]

Operadores Lógicos Bit-a-bit sobre inteiros com valor 0 e 1

Agora vamos imaginar que o armazenamento dos números inteiros seja feito em um byte, ou seja em 8 bits.

Quando utilizamos variáveis numéricas que contêm apenas valores 0 ou 1, os armazenamentos desses valores em bits são, respectivamente, [00000000] e [00000001].

Ao utilizar o operador ~ (não), todos os bits do número são afetados, sejam 8, como representado acima, ou mais.

Porém, ao utilizarmos & (and), | (or) ou ^ (xor), não importa quais ou quantas operações fazemos, apenas o primeiro bit poderá receber valores 1 ou 0. Todos os demais bits se manterão como 0 (zero).

Como os Operadores Lógicos Bit-a-Bit trabalham com valores numéricos inteiros, caso operem valores booleanos, estes são convertidos de True ou False para, respectivamente, 1 ou 0.

Por conta disso, sobre valores booleanos, os Operadores Lógicos Bit-a-Bit, & (and) e | (or), funcionam exatamente como os equivalentes Operadores Lógicos booleanos.

Não existe um Operador Lógico booleano equivalente ao ^ (xor), porém é possível utilizar esse operador bit-a-bit ^ (xor) com valores booleanos, que serão entendidos como 0 ou 1. O resultado dessa operação será também 0 ou 1. E, caso o resultado seja utilizado em um contexto que espera um valor booleano, este será convertido para False ou True.

Exemplo de ^ (xor) operando valores booleanos:

resultado = True ^ True # resultado recebe 0 (equivalente a False)

Ao utilizar resultado em um if, por exemplo, o valor de resultado será avaliado como booleano. No exemplo, em False.

Simulando essa avaliação como booleano com a utilização da função bool, seguem todas as possibilidades:

resultado = bool(True ^ True) # resultado recebe False
resultado = bool(True ^ False) # resultado recebe True
resultado = bool(False ^ True) # resultado recebe True
resultado = bool(FalseFalse) # resultado recebe False

Outros Operadores Bit-a-Bit

Já que destrinchamos a representação em bits dos valores inteiros, vale a pena aproveitar a oportunidade para apresentar os Bitwise Shift Operators (Operadores de Deslocamento Bit-a-Bit).

Obs.: A abordagem desses operadores foge do assunto principal deste artigo, que são os valores e a aritmética booleana.

Os Operadores de Deslocamento Bit-a-Bit (Bitwise Shift Operators) são:

  • << (left shift): deslocamento para esquerda
  • >> (right shift): deslocamento para direita
Ambos os Bitwise Shift Operators são operadores duais, ou seja, precisam de dois valores para operar.

À esquerda do operador é informado o valor cujos bits serão deslocados, e à direita, o número de deslocamentos que serão executados

Left shift (deslocamento à esquerda)

Para entendimento inicial, vamos trabalhar com inteiros limitados, armazenados em 8 bits.

Por exemplo, a expressão 10 << 1 equivale a deslocar os bits [00001010] uma posição para a esquerda, ou seja [00010100]. Sendo [00001010] a representação de como é armazenado na memória o número 10, em representação binária 0b1010.

Esse deslocamento para a esquerda segue as seguintes regras:

  1. O primeiro bit, à direita, cujo valor passa para a segunda posição, recebe o valor 0 (zero);
  2. O valor do último bit, à direita, ao "ser deslocado para fora" da área disponível para os bits, é simplesmente descartado.

Assim:

10 << 1 ↔ (equivale a) [00001010] << 1 = [00010100] = 20
10 << 2 ↔ [00001010] << 2 = [00101000] = 40
10 << 3 ↔ [00001010] << 3 = [01010000] = 80

Talvez você tenha percebido que a cada posição deslocada à esquerda, o valor resultante é dobrado.

Esse padrão de funcionamento muda quando o último bit, que representa o sinal negativo do número, troca de valor.

10 << 4 ↔ [00001010] << 4 = [10100000] =  -96
10 << 5 ↔ [00001010] << 5 = [01000000] =   64
10 << 6 ↔ [00001010] << 6 = [10000000] = -128
10 << 7 ↔ [00001010] << 7 = [00000000] =    0

Depois desse entendimento inicial, vamos passar a trabalhar com inteiros ilimitados, que é como o Python trabalha com inteiros, positivos ou negativos.

Neste caso a segunda regra citada acima, para o deslocamento à esquerda, não se aplica mais, pois não há como um bit "ser deslocado para fora" da área disponível para os bits, uma vez que os números pode crescer indefinidamente para a esquerda.

Bits em negrito representam bits que guardam a informação de sinal do número.

Assim, os exemplos de deslocamentos do número 10 em Python ficam assim:

10 << 1 ↔ [01010] << 1 =       [010100] =   20
10 << 2 ↔ [01010] << 2 =      [0101000] =   40
10 << 3 ↔ [01010] << 3 =     [01010000] =   80
10 << 4 ↔ [01010] << 4 =    [010100000] =  160
10 << 5 ↔ [01010] << 5 =   [0101000000] =  320
10 << 6 ↔ [01010] << 6 =  [01010000000] =  640
10 << 7 ↔ [01010] << 7 = [010100000000] = 1280

Neste caso a característica de dobrar o valor a cada deslocamento é preservada para qualquer valor.

O mesmo se observa para valores negativos. Por exemplo:

-10 << 1 ↔ [10110] << 1 =    [101100] =  -20
-10 << 2 ↔ [10110] << 2 =   [1011000] =  -40
-10 << 3 ↔ [10110] << 3 =  [10110000] =  -80
-10 << 4 ↔ [10110] << 4 = [101100000] = -160

Para ajudar o entendimento neste contexto, vou categorizar os operadores de deslocamento bit-a-bit como operadores de "deslocamento matemático" ou "deslocamento de janela", sendo o "deslocamento matemático" quando a característica matemática da operação é preservada, e "deslocamento de janela", quando não.

No Python os dois operadores de deslocamento bit-a-bit são da categoria "deslocamento matemático". Diferente de outras linguagens, onde estes deslocamentos podem ser de outra categoria.

Por exemplo, no Java e no Javascript o deslocamento bit-a-bit à esquerda, << (left shift), é da categoria "deslocamento de janela" e se comporta como nos primeiros exemplos de << (left shift), que consideram inteiros limitados.

Right shift (deslocamento à direita)

O operador deslocamento à direita do Python, como já indicado, também é da categoria "deslocamento matemático", pois, independentemente de o número ser positivo ou negativo, cada deslocamento para a direita é equivalente ao piso da divisão por 2.

Lembrando: Em matemática, "piso" é o arrendondamento para o menor valor entre os dois inteiros mais próximos. Por exemplo, "piso" de 2,6 é 2, e "piso" de -3,6 é -4.

Em Python há um operador matemático que calcula exatamente isso, o piso de uma divisão: É o operador // (divisão inteira). Só que ele aceita dividir por qualquer número, não apenas por potências de 2, como no caso do operador >> (right shift).

100 >> 1 == 100 // 2
100 >> 3 == 100 // 2**3

Porém, para acontecer esse "deslocamento matemático", há uma regra a seguir que depende do sinal.

O deslocamento para a direita, na categoria "deslocamento matemático", segue as seguintes regras:

  1. O último bit, à esquerda, cujo valor passa para a penúltima posição, mantém o valor que tinha antes da operação:
    • 0 (zero) caso o número seja positivo;
    • 1 (um) caso o número seja negativo;
  2. O valor do primeiro bit, à esquerda, ao ser "deslocado para fora" da área disponível para os bits, é simplesmente descartado.

Inteiros no Python têm valor ilimitado. Isso significa que eles podem crescer ilimitadamente para a esquerda, mas não para a direita. Com isso, a aplicação contínua de deslocamentos leva o valor a um limite, a partir do qual o deslocamento não altera mais o valor, como será visto nos exemplos abaixo.

Exemplos de deslocamentos à direita do número positivo 83:
83 >> 1 ↔ [01010101] >> 1 = [0101010] = 42
83 >> 2 ↔ [01010101] >> 3 =  [010101] = 21
83 >> 3 ↔ [01010101] >> 3 =   [01010] = 10
83 >> 4 ↔ [01010101] >> 4 =    [0101] =  5
83 >> 5 ↔ [01010101] >> 5 =     [010] =  2
83 >> 6 ↔ [01010101] >> 6 =      [01] =  1
83 >> 7 ↔ [01010101] >> 1 =      [00] =  0
...
83 >> 100 ↔ [01010101] >> 100 = [00] = 0

Exemplos de deslocamentos à direita do número negativo -83:

-83 >> 1 ↔ [10101011] >> 1 = [1010101] = -43
-83 >> 2 ↔ [10101011] >> 2 =  [101010] = -22
-83 >> 3 ↔ [10101011] >> 3 =   [10101] = -11
-83 >> 4 ↔ [10101011] >> 4 =    [1010] =  -6
-83 >> 5 ↔ [10101011] >> 5 =     [101] =  -3
-83 >> 6 ↔ [10101011] >> 6 =      [10] =  -2
-83 >> 7 ↔ [10101011] >> 7 =      [11] =  -1
...
-83 >> 100 ↔ [10101011] >> 100 = [11] = -1

Como demonstrado nos exemplos, deslocamentos consecutivos de valores positivos tendem a 0 (zero) e deslocamentos consecutivos de valores negativos tendem a -1.

Como no caso do operador de deslocamento à esquerda, outras linguagens podem diferir do Python quanto ao funcionamento do operador de deslocamento à direita.

Novamente citando o Java e o Javascript. Nessas duas linguagens há duas variações do operador de deslocamento à direita:

  • >> (signed right shift): deslocamento à direita com sinal, que funciona de forma análoga ao do Python, ou seja, encaixa-se na categoria "deslocamento matemático"
  • >>> (unsigned right shift): deslocamento à direita sem sinal, que se encaixa na categoria "deslocamento de janela"

Nesse deslocamento à direita sem sinal, o primeiro passo, do dois apresentados acima, funciona diferente:

  1. O último bit, à esquerda, cujo valor passa para a penúltima posição, sempre recebe 0 (zero);

Ou seja, para valores não negativos esses dois operadores, >> (signed right shift) e >>> (unsigned right shift), apresentam os mesmos resultados.

Porém, para valores negativos os resultados são diferentes.

Segue um pequeno exemplo de deslocamento à direita sem sinal, >>> (unsigned right shift), aplicado a um número negativo.

O primeiro deslocamento utilizando esse operador sempre transforma o número negativo em positivo, e assim continua, com os próximos deslocamentos, até chegar ao valor limite 0 (zero):

-83 >>> 1 ↔ [10101011] >>> 1 = [01010101] = 85
-83 >>> 2 ↔ [10101011] >>> 2 = [00101010] = 42
-83 >>> 3 ↔ [10101011] >>> 3 = [00010101] = 21
-83 >>> 4 ↔ [10101011] >>> 4 = [00001010] = 10
...
-83 >>> 100 ↔ [10101011] >>> 100 = [00] = 0

Lembrando que >>> não existe em Python, expliquei e exemplifiquei aqui apenas para completar o entendimento do assunto.

Uma interessante utilidade de XOR

Comentei na primeira citação do ^ (xor) que ele é mais útil em aplicações em bit-a-bit.

Gostaria de comentar uma utilidade que gosto muito do XOR.

Há uma técnica, da qual não vou entrar em detalhes, que distribui dados em diversas unidades de armazenamento de modo a obter mais velocidade e menor probabilidade de perda de dados.

Em um exemplo extremamente simples, digamos que quero guardar o texto "Oi!" distribuído em três unidades de armazenamento.

Lembrando que cada letra, no caso, é um número que pode ser guardado em um byte (sem entrar em complicações do Unicode), esse texto "equivale" à seguinte lista de números: 79, 105, 33

Por sua vez o armazenamento desses números em bytes (8 bits) ficaria assim: [01001111], [01101001], [00100001]

Simplificando muito, quanto à velocidade, podemos imaginar o ganho de velocidade quando o computador lê cada byte desses em uma unidade diferente e os concatena na memória.

Porém, quanto à probabilidade de perda de dados, a probabilidade parece maior, pois tenho 3 vezes mais chance de ter um defeito em uma unidade de armazenamento. Se eu perder um dos 3 bytes, perco a integridade do meu texto.

Para resolver esse problema é calculado um quarto byte, chamado de byte de paridade, e é guardado em uma quarta unidade. Com isso, se der defeito em qualquer das quatro unidades eu consigo recalcular o dado perdido.

O cálculo do byte da paridade é o exemplo de uso do XOR que gosto muito e que queria mostrar.

Vou chamar as três unidades de dados de A, B e C. Sendo os três bytes acima armazenados da primeira posição de cada unidade.

A unidade de paridade será chamada de P e guarda em cada posição, um byte de paridade dos 3 bytes na mesma posição nas unidades A, B e C.

O cálculo é assim, para o byte no índice "n":

P[n] = A[n] ^ B[n] ^ C[n] 

Vou calcular apenas para a primeira posição:

P[0] =  A[0] ^ B[0] ^ C[0]
P[0] = [01001111] ^ [01101001] ^ [00100001]
P[0] = [000100110] ^ [00100001]
P[0] = [00000111]

Se perder qualquer uma das unidades, como recuperar a dado que estava lá?

Aplicando a mesma fórmula do calculo da paridade.

Exemplo: Se perdermos a unidade B, compramos uma nova e calculamos o que estava lá baseado no que está nas unidades A, C e P, assim:

B[0] =  A[0] ^ C[0] ^ P[0]
B[0] = [01001111] ^ [00100001] ^ [00000111]
B[0] = [01101110] ^ [00000111]
B[0] = [01101001]

Pode conferir que o byte de B calculado baseado nos bytes de A, C e P tem exatamente o mesmo valor original.

Acho essa propriedade do XOR muito incrível! Está de parabéns a primeira pessoa que percebeu essa aplicação do XOR.

E aí você se pergunta: "Como operadores lógicos tão simples podem ter tantas utilidades?"

Bem... Como eu disse lá no início, os operadores lógicos na verdade proporcionaram todo o advento da computação e seus desdobramentos, dos primeiros computadores, à internet e à inteligência artificial.

Tudo isso com 2 operadores lógicos!

"Dois? Mas este artigo fala de pelo menos 4!"

Isso é só uma curiosidade: Em um computador que tivesse o operador lógico NOT, só seria necessário ter mais um operador lógico básico, AND ou OR, para poder fazer qualquer expressão lógica.

Por exemplo, se estivéssemos trabalhando em um computador que só tivesse os operadores NOT e AND.

Poderíamos calcular o OR assim:

A OR B = NOT(NOT A AND NOT B)

E poderíamos calcular o XOR assim:

A XOR B = NOT (NOT A AND NOT B) AND NOT (A AND B)

Outros operadores booleanos lógicos

Há ainda outros operadores booleanos:

  • nor: Operador dual, opera sobre dois valores, à esquerda e à direita, e retorna True se ambos os valores forem False, senão, retorna False.
    • A nor B equivale a not A or B
  • nand: Operador dual, opera sobre dois valores, à esquerda e à direita, e retorna False se ambos os valores forem False, senão, retorna True.
    • A nand B equivale a not A and B
  • xnor: Operador dual, opera sobre dois valores, à esquerda e à direita, e retorna retorna True se ambos os valores forem iguais, senão, retorna False.
    • A xnor B equivale a not A xor B

Apesar de esses operadores não existirem no Python, nem na maioria das linguagens populares, são fáceis de serem calculados, devido às equivalências citadas acima.

A lógica desses operadores é comumente encontrada em circuitos eletrônicos, desde os primeiros chips criados. Nesse contexto esses operadores são chamados de portas lógicas.

Tudo isso com 1 operador lógico!

"Peraí! Ainda pouco era com 2!"

As portas nor e nand apresentam uma característica especial: Completude funcional.

Isso significa que todos os outros operadores podem ser calculados em função de apenas um dos dois.

Vejam como calcular os 3 operadores básicos utilizando apenas nor:

  • not A = A nor A
  • A and B = (A nor A) nor (B nor B)
  • A or B = (A nor B) nor (A nor B)

Curiosidade: o computador da primeira nave que levou o homem até a Lua, foi construído usando apenas portas lógicas NOR!

Ufa!

Confesso que, quando pensei "Vou falar de booleanos em Python", eu não imaginava que iria escrever tanto.

As vezes, coisas tão básicas são tão importantes que vale se aprofundar e entender de verdade, para nunca mais esquecer.

Espero que a utilidade do conhecimento descrito neste artigo vá além do que foi exposto aqui.

Uma vez dominada a base, várias coisas vão clareando em áreas que, a princípio, podem parecer desconectadas.

Links


Nenhum comentário:

Postar um comentário