Faça assim para simplificar Expressões Lógicas

🔢 Simplificação de Expressão Lógica

📌 Introdução

A simplificação de expressões lógicas é fundamental na otimização de circuitos digitais e na redução da complexidade computacional. Em sistemas embarcados e aplicações industriais, expressões lógicas mais simples resultam em menor consumo de energia, maior eficiência e menor custo de implementação pois necessitam de menos componentes.

Na área da programação, muitas vezes ocorre de o programador se deparar com um complexo aninhamento de expressões lógicas, em um fluxo de controle (ifs, elses, do cases..). Não raro, é possível encontrar expressões equivalentes lógicas simplificadas. É isso o que mostraremos neste artigo.

💡 Contexto e Necessidade

As expressões lógicas são utilizadas nas mais diversas áreas, em sistemas eletrônicos e softwares. A formulação correta e eficiente das regras de implementação da funções lógicas e dos circuitos equivalentes evita falhas e otimiza a segurança do sistema, além de tornar os códigos mais simples e legíveis.

🔬 Fundamentos Teóricos

📘 Álgebra Booleana

A Álgebra Booleana é a base da lógica digital. Ela se fundamenta em operações com os operadores ou portas lógicas (AND, OR e NOT em especial), e é essencial para a formulação e simplificação tanto circuitos quanto de aplicativos de programação.

📊 Mapa de Karnaugh

O Mapa de Karnaugh é uma técnica gráfica utilizada para minimizar expressões booleanas, reduzindo a complexidade de circuitos lógicos. Ele permite visualizar padrões e agrupar termos semelhantes para encontrar expressões equivalentes mais simples.

Aplicativos como o Logisim permitem a visualização dos mapas de Karnaugh relacionados a uma expressão lógica. O aplicativo online Circuit Verse também permite a simplificação lógica, além de apresentar o circuito correpondente, assim como o Logisim.

A simplificação das expressões lógicas na prática

📝 Vejamos, na prática, como uma expressão complexa pode ser simplificada. Suponhamos algum dos sistemas exemplificados na parte final deste artigo. Como esses exemplos são formados por 4 variáveis boleanas na entrada, a tabela verdade de sua função lógica conterá 16 linhas. Isso porque as tabelas verdade contêm tantas linhas quanto o resultado da fórmula: 2 elevado a n, onde n é a quantidade de variáveis de entrada. Portanto, para n=4, haverá 16 linhas (2^4=16). Caso se tratasse de exemplos com 3 variáveis, haveria 8 linhas (2^3=8); se fossem 5 variáveis, 32 linhas (2^5=32) e assim por diante.

Digamos que, em uma abordagem ingênua (naive no inglês), um programador ou projetista de circuitos estivesse analisando uma tabela verdade de 16 linhas, igual à do Exemplo 1 , "Controle de Acesso a um Sistema" apresentado lá embaixo e, para programar seus vários casos, utilizasse o seguinte fluxo de execução:

if A:
    if B:
        if C:
            if D:
                return true
            else:
                return true
        else:
            if D:
                return false
            else:
                return false
    else:
        if C:
            if D:
                return true
            else:
                return false
        else:
            if D:
                return false
            else:
                return false
else:
    if B:
        if C:
            if D:
                return false
            else:
                return false
        else:
            if D:
                return false
            else:
                return false
    else:
        if C:
            if D:
                return false
            else:
                return false
        else:
            if D:
                return false
            else:
                return false

🪟Tabela verdade do exemplo 1

A tabela verdade em questão, que o programador teria presumidamente utilizado, seria esta:

===============
A  B  C  D | Resultado da função lógica
---------------
0 0 0 0 | 0
0 0 0 1 | 0
0 0 1 0 | 0
0 0 1 1 | 0
0 1 0 0 | 0
0 1 0 1 | 0
0 1 1 0 | 0
0 1 1 1 | 0
1 0 0 0 | 0
1 0 0 1 | 0
1 0 1 0 | 0
1 0 1 1 | 1
1 1 0 0 | 0
1 1 0 1 | 0
1 1 1 0 | 1
1 1 1 1 | 1

🐞 Expressão lógica boleana, não simplificada, para trabalhar com a tabela verdade acima

((AB'CD)+(ABCD')+(ABCD))

✅ Expressão lógica boleana simplificada

função lógica: S = (A and C and (B or D))
ou, na notação da álgebra boleana: 
S=(AC(B+D))

⚖️Código para comparar os resultados entre os algoritmos nas versões "ingênua" e simplificada

Comparem as duas versões da função contidas no código abaixo. Ambas produzem o mesmo resultado. Porém, enquanto a versão simplificada contém apenas 3 linhas de código, a versão "ingênua" contém quase 50 linhas.

'''
Compararemos, aqui, as duas versões do algoritmo: a versão "ingênua" e a versão simplificada.

O contexto é o do exemplo 1: Controle de Acesso a um Sistema

Entrada:

A = Usuário autenticado
B = Possui permissão de administrador
C = Senha válida
D = Autenticação de dois fatores ativada

Saída:

S = Acesso permitido

Função Lógica simplificada:
S = A ∧ C ∧ (B V D)

Explicação:
Usuário autenticado com senha válida e, além disso, ou é administrador ou tem 2FA ativado

'''
def controle_acesso_algoritmo_ingenuo(A: int, B: int, C: int, D:int) -> int:
    resultado=None
    if A:
        if B:
            if C:
                if D:
                    resultado = 1
                else:
                    resultado = 1
            else:
                if D:
                    resultado = 0
                else:
                    resultado = 0
        else:
            if C:
                if D:
                    resultado = 1
                else:
                    resultado = 0
            else:
                if D:
                    resultado = 0
                else:
                    resultado = 0
    else:
        if B:
            if C:
                if D:
                    resultado = 0
                else:
                    resultado = 0
            else:
                if D:
                    resultado = 0
                else:
                    resultado = 0
        else:
            if C:
                if D:
                    resultado = 0
                else:
                    resultado = 0
            else:
                if D:
                    resultado = 0
                else:
                    resultado = 0
    return resultado

def controle_acesso_algoritmo_simplificado(A: int, B: int, C: int, D:int) -> int:
    S=(A and C and (B or D))  #S=((AC(B+D))
    return int(S)	

# Exibir os resultados
print("#"*100)
print("Algoritmo ingênuo")
print("="*25)
print("A  B  C  D | Resultado da função lógica 'ingênua'")
print("-"*25)
for A in range(2):
    for B in range(2):
        for C in range(2):
            for D in range(2):
                print(f"{A}  {B}  {C}  {D} | {controle_acesso_algoritmo_ingenuo(A, B, C, D)}")
print("#"*100)                
print("Algoritmo resultante da simplificação da expressão lógica")
print("="*25)
print("A  B  C  D | Resultado da função lógica simplificada")
print("-"*25)
for A in range(2):
    for B in range(2):
        for C in range(2):
            for D in range(2):
                print(f"{A}  {B}  {C}  {D} | {controle_acesso_algoritmo_simplificado(A, B, C, D)}")
print("#"*100)

🔎 No exemplo 8, as vantagens da simplificação são mais evidentes

Se analisarmos o exemplo 8, do "Sistema de Controle de Tráfego", veremos ainda mais nítidas as vantagens da simplificação.

🪟Tabela verdade do exemplo 8

Tabela verdade (exemplo 8)
===============
A  B  C  D | Resultado da função lógica 
---------------
0 0 0 0 | 0
0 0 0 1 | 1
0 0 1 0 | 1
0 0 1 1 | 1
0 1 0 0 | 0
0 1 0 1 | 1
0 1 1 0 | 1
0 1 1 1 | 1
1 0 0 0 | 0
1 0 0 1 | 1
1 0 1 0 | 1
1 0 1 1 | 1
1 1 0 0 | 1
1 1 0 1 | 1
1 1 1 0 | 1
1 1 1 1 | 1

🐞 Expressão lógica boleana, não simplificada, para trabalhar com a tabela verdade do exemplo 8

((A'B'C'D)+(A'B'CD')+(A'B'CD)+(A'BC'D)+(A'BCD')+(A'BCD)+(AB'C'D)+(AB'CD')+(AB'CD)+(ABC'D')+(ABC'D)+(ABCD')+(ABCD))

✅ Expressão lógica boleana simplificada para o exemplo 8

função lógica: S = (A and B) or C or D
ou, na notação da álgebra boleana: 
S= (AB) + C + D

⚡ Como realizar, na prática, a simplificação das expressões lógicas?

Bem, o melhor conselho seria estudar e aprofundar-se nas técnicas de álgebra boleana. Tudo fica mais fácil quando, além das experiências práticas, domina-se também a teoria envolvida.

Apresentaremos três outras formas de resolver essa simplificação:

1️⃣ Resolver com a ajuda do ChatGPT

Esta é a opção mais simples, mas também a menos indicada por ora, ao menos na versão gratuita.

Copie a expressão a simplificar, por exemplo, F=(((A'B'C'D)+(A'B'CD')+(A'B'CD)+(A'BC'D)+(A'BCD')+(A'BCD)+(AB'C'D)+(AB'CD')+(AB'CD)+(ABC'D')+(ABC'D)+(ABCD')+(ABCD))) e, no prompt do ChatGPT, solicite a simplificação.

Um exemplo de prompt pode ser:

Simplifique esta expressão lógica o máximo que puder, considerando-se que utiliza a notação do caracter ' para o operador lógico not e + para o operador or. A expressão em questão: ((A'B'C'D)+(A'B'CD')+(A'B'CD)+(A'BC'D)+(A'BCD')+(A'BCD)+(AB'C'D)+(AB'CD')+(AB'CD)+(ABC'D')+(ABC'D)+(ABCD')+(ABCD)). Quando não houver caractere nenhum, considere que ali vai um operador lógico and. As variáveis de entrada são A, B, C e D e a função de saída é S=f(A,B,C,D).

Repito o alerta de que, por ora ao menos, e na versão gratuita, e nos momentos em que estiver utilizando os modelos mais simples dessa IA, este é o método mais sujeito a falhas e respostas erradas. Ainda assim, é bastante útil para uma visão geral, e como começo de verificação, para confirmação posterior por outros métodos, como os apresentados abaixo.

2️⃣ Resolver a simplificação da expressão lógica com o Circuit Verse

O Circuit Verse é uma ferramenta online que permite simular circuitos digitais. Para utilizar a ferramenta de análise combinacional que o Circuit Verse mantém disponível, siga estes passos:

1. Acesse o Circuit Verse.
2. Clique em "Launch Simulator".
3. No menu superior, vá em Tools > Combinational Analysis.
4. No campo "Enter boolean function", insira a expressão lógica ((A+B')C)+((A B C)(A C')).
5. Clique em "Next" para visualizar a tabela verdade resultante da expressão.
6. Clique em "Generate circuit"
7. Apague todas as conexões não utilizadas
8. O circuito que restar corresponderá à versão lógica simplificada

3️⃣ Resolver a simplificação no aplicativo Logisim

A simplificação realizada no aplicativo Logisim é, de certo modo, ainda mais simples do que a apresentada acima, do Circuit Verse. Isso por que é diretamente apresentada na janela em que mostra o mapa de Karnaugh. O ponto negativo é que tem menos flexibilidade para tabelas maiores, pois tem um limite baixo de possíveis variáveis de entradas (limite de 12, na versão testada: 2.7.1).

1. Depois de baixá-lo e instalá-lo na pasta de sua preferência, abra o aplicativo
2. Acesse a análise combinacional em "Projeto > Analisar Circuito"
3. Ao contrário do Circuit Verse, o Logisim não permite a entrada direta da expressão a minimizar, portanto, é preciso entrar com as variáveis de entrada (A,B,C) e com a de saída (F).
4. Depois disso, manualmente configurar a tabela verdade.
5. A expressão resultante dependerá da configuração (manual) da tabela verdade
6. Aí, sim, é que, na aba "Minimizada" é que o usuário terá o resultado da simplificação da expressão.
7. Na aba "Minimizada", poderá escolher entre uma das formas de minimização: Soma de Produtos ou Produto das somas. Em cada caso, um ou outro pode ser o mais vantajoso em termos de simplicidade e de economia de recursos.

Exemplos de sistemas hipotéticos relativamente complexos

Solicitei ao ChatGpt para indicar alguns exemplos de sistemas hipotéticos relativamente complexos, com 4 variáveis booleanas na entrada e 1 na saída. Vejam as sugestões recebidas, já com as adaptações que fiz:

S = A ∧ C ∧ (B V D)

S = C ∧ (A V B) ∧ ¬D

S = A V B V ( C ∧ ¬D)

S = A ∧ B ∧ (C V D)

S = A ∧ C ∧ (¬B V D)

S = A ∧ (B V ¬C) ∧ ¬D

S = A ∧ B ∧ (¬C V D)

S = (A ∧ B) V C V D

S = (A ∧ C) V (B ∧ ¬D)

S = A ∧ C ∧ ¬B ∧ ¬D

S = A V B V (C ∧ D)

S = A ∧ B ∧ C ∧ ¬D

'''
Variáveis booleanas do exemplo 1, sendo que os outros exemplos seguem modelo semelhante:
1. Controle de Acesso a um Sistema
Entrada:

A = Usuário autenticado
B = Possui permissão de administrador
C = Senha válida
D = Autenticação de dois fatores ativada
Saída:

S = Acesso permitido
Função Lógica:
S=A∧C∧(B∨D)
(Usuário autenticado com senha válida e, além disso, ou é administrador ou tem 2FA ativado)
'''
def fluxo_controle_complexo(A: int, B: int, C: int, D: int, exemplo: int)->int:
    if A:
        if B:
            if C:
                if D:
                    caso="Caso 15: A, B, C e D são verdadeiros"
                else:
                    caso="Caso 14: A, B e C são verdadeiros"
            else:
                if D:
                    caso="Caso 13: A e B são verdadeiros, mas C é falso e D verdadeiro"
                else:
                    caso="Caso 12: A e B são verdadeiros, mas C e D são falsos"
        else:
            if C:
                if D:
                    caso="Caso 11: A e C são verdadeiros, mas B é falso e D verdadeiro"
                else:
                    caso="Caso 10: A e C são verdadeiros, mas B e D são falsos"
            else:
                if D:
                    caso="Caso 9: Apenas A e D são verdadeiros"
                else:
                    caso="Caso 8: Apenas A é verdadeiro"
    else:
        if B:
            if C:
                if D:
                    caso="Caso 7: Apenas A é falso"
                else:
                    caso="Caso 6: Apenas A e D são falsos"
            else:
                if D:
                    caso="Caso 5: Apenas A e C são falsos"
                else:
                    caso="Caso 4: Apenas B é verdadeiro"
        else:
            if C:
                if D:
                    caso="Caso 3: Apenas A e B são falsos"
                else:
                    caso="Caso 2: Apenas C é verdadeiro"
            else:
                if D:
                    caso="Caso 1: Apenas D é verdadeiro"
                else:
                    caso="Caso 0: Nenhuma variável é verdadeira"    
    S=None
    if (exemplo==1):  
        S = (A and C and (B or D))  #S = A ∧ C ∧ (B ∨ D)
    if (exemplo==2):
        S = (C and (A or B) and not D)  #S = C ∧ (A ∨ B) ∧ ¬D
    if (exemplo==3):
        S = (A or B or (C and not D))  #S = A V B V ( C ∧ ¬D)
    if (exemplo==4):
        S = A and B and (C or D)  #S = A ∧ B ∧ (C V D)
    if (exemplo==5):
        S = A and C and (not B or D)  #S = A ∧ C ∧ (¬B V D)
    if (exemplo==6):
        S = A and (B or not C) and not D  #S = A ∧ (B V ¬C) ∧ ¬D
    if (exemplo==7):
        S = A and B and (not C or D)  #S = A ∧ B ∧ (¬C V D)
    if (exemplo==8):
        S = (A and B) or C or D  #S = (A ∧ B) V C V D
    if (exemplo==9):
        S = (A and C) or (B and not D)  #S = (A ∧ C) V (B ∧ ¬D)
    if (exemplo==10):
        S = A and C and not B and not D  #S = A ∧ C ∧ ¬B ∧ ¬D
    if (exemplo==11):
        S = A or B or (C and D)  #S = A V B V (C ∧ D)
    if (exemplo==12):
        S = A and B and C and not D  #S = A ∧ B ∧ C ∧ ¬D
  
    return int(S), caso

# Exibir os resultados
print("="*15)
print("A  B  C  D | Resultado")
print("-"*15)
exemplos=["Controle de Acesso a um Sistema",
          "Sistema de Segurança Residencial",
          "Carro Autônomo em Situação de Tráfego",
          "Sistema de Aprovação de Crédito",
          "Sistema de Irrigação Automática",
          "Sistema de Detecção de Fraude em Transações",
          "Gerenciamento de Carga em Veículo Elétrico",
          "Sistema de Controle de Tráfego",
          "Sistema de Iluminação Pública Inteligente",
          "Controle de Temperatura em Estufas",
          "Sistema de Verificação de E-mails Suspeitos",
          "Automação de Marketing Digital"                   
         ]
funcaoLogica=[
             "S = (A and C and (B or D))",
             "S = (C and (A or B) and not D)",
             "S = (A or B or (C and not D))",
             "S = A and B and (C or D)",
             "S = A and C and (not B or D)",
             "S = A and (B or not C) and not D",
             "S = A and B and (not C or D)",
             "S = (A and B) or C or D",
             "S = (A and C) or (B and not D)",
             "S = A and C and not B and not D",
             "S = A or B or (C and D)",
             "S = A and B and C and not D",
             ]
for exemplo in range (1,13):
    print(f"Exemplo: {exemplo} : {exemplos[exemplo-1]}")
    print(f"função lógica: {funcaoLogica[exemplo-1]}")
    for A in range(2):
        for B in range(2):
            for C in range(2):
                for D in range(2):
                    print(f"{A} {B} {C} {D} | {fluxo_controle_complexo(A, B, C, D, exemplo)}")

📈 Conclusão

A simplificação de expressões lógicas é essencial para tornar circuitos mais eficientes e econômicos. Utilizando técnicas de simplificação das expressões lógicas, seja com o uso de álgebra booleana, do Mapa de Karnaugh ou de ferramentas como o CircuitVerse, o Logisim e os portais de IA como o ChatGPT, podemos construir sistemas otimizados e de melhor desempenho.