Lógica: Simplificação de expressões

A lógica desse artigo pode ser usada na maioria das linguagens de programação, com simples adaptações. GML é uma delas. Os códigos aqui usados rodam corretamente.

O artigo pode ser um pouco "confuso" para quem não está acostumado com lógica binária (digital). É recomendado para quem já sabe no mínimo usar bem os operadores AND e OR (&& e ||).

Tags: lógica digital, binário, and, or, mapa de Karnaugh, tabela da verdade, simplificação de expressões lógicas.

Código:

if ( ( (a && !b) or (b && !c) ) && ( (!b && c) or (a && !c)))
{

}

Achou a expressão acima exagerada? Se sim, saiba que eu também.

Existe um método de simplificar expressões. Geralmente é usado para diminuir a quantidade de portas lógicas necessárias na arquitetura de um processador. Mas os programadores também podem tirar proveito disto e tornar seus códigos mais eficientes, inteligentes e elegantes.

Para simplificar uma expressão que usa apenas valores true/false (também pode ser >0 e <0), podemos utilizar o Mapa de Karnaugh (acho que se pronuncia "Carnô").

Antes de montar esse mapa, você precisa construir uma "tabela da verdade". Isso quer dizer que você deve fazer uma tabela que contenha cada variável como a primeira célula de sua coluna, além de uma coluna para o resultado.

Simplificando o código de exemplo, podemos fazer o seguinte (lembrando que 1=true e 0=false):

a|b|c|r
0|0|0|0 ---> se a, b, c são false, então o resultado é false
0|0|1|0 ---> se somente c é true, então o resultado é false
0|1|0|0 ---> se somente b é true, então o resultado é false
0|1|1|0 ---> se somente a é false, então o resultado é false
1|0|0|1 ---> se somente a é true, então o resultado é true
1|0|1|1 ---> se somente b é false, então o resultado é true
1|1|0|1 ---> se somente c é false, então o resultado é true
1|1|1|0 ---> se todos são true, então o resultado é false

Note que a combinação das três colunas a, b, c vai de 000 a 111, ou seja, de 0 a 7 em binário. Como temos 3 variáveis, temos 2³=8 combinações possíveis. Se fossem 4 variáveis, teríamos 2^4=16.

Devemos testar cada combinação possível. Para isso, você pode fazer um programa que teste o resultado de cada combinação ou fazer manualmente (mentalmente).

Depois que você fizer a tabela da verdade, é hora de fazer o Mapa de Karnaugh.

Para isso, vamos pegar apenas as combinações que resultaram em 1:

a|b|c
1|0|0
1|0|1
1|1|0

No mapa de três variáveis, as linhas representam o valor de A e as colunas representam as combinações dos valores de B e C.

Marcamos com um X as células dessas combinações (100, 101, 110).


Agora é hora de simplificar a expressão.

Para isso, vamos eliminar as variáveis que podem assumir tanto o valor 0 como o 1.

Vamos procurar no mapa por X's adjacentes (conjuntos de 2 ou 4). No mapa acima, encontramos uma dessas combinações. Note que C pode ser tanto 0 como 1 desde A=1 e B=0. Ou seja, 100 e 101 possuem um X.

Logo, vamos eliminar C nessa expressão. Temos então:
A && !B (ou seja, A=1 e B=0)

A última célula (A=B=C=1) não forma um grupo, portanto ela não pode ser simplificada. Mas deve ser usada.

Reunimos o resultado A && !B (em que A deve ser true e B false) ao resultado A && B && C (em que todos devem ser true). Para reuni-los, usamos OR.

A expressão final será:

Código:

if ((A && !B) or (A && B && C))
{
}

É interessante notar que a operação AND pode ser usada como uma multiplicação e a operação OR como uma soma, desde que todos possam assumir somente os valores 0 e 1.

Código:

if ((A * !B) + (A*B*C))
{
}

Esse é apenas um exemplo de simplificação, com o objetivo de incentivar a pesquisa nessa área. Para saber mais, pesquise sobre esse mapa, tabela da verdade e lógica digital.

Em breve, mais artigos.

PedroX, essa disciplina é interessantíssima... eu mesmo tinha essa curiosidade de saber mais sobre isso.

Obrigado por disponibilizar.

Obs: Me lembrou essa série muito bacana do brendan:
https://gmbr.forumeiros.com/t27761-logica-e-operadores-de-bits-por-brendan640

Muito bacana PedroX poderia fazer um exemplo de como manipular os sinais de controle remoto pelo celular, sendo que esse é o ponto de partida correto ?!
vlw

Fred, estou tendo essas aulas na faculdade. Conforme eu for aprendendo, vou reforçando por ensinar.

Não entendi a pergunta sobre o controle remoto, Gonzo. Na verdade, nunca achei um app que funcionasse de verdade.

PedroX escreveu:Fred, estou tendo essas aulas na faculdade. Conforme eu for aprendendo, vou reforçando por ensinar.

Não entendi a pergunta sobre o controle remoto, Gonzo. Na verdade, nunca achei um app que funcionasse de verdade.

Me vi na sala de aula, estudando lógica da programação hahaha
Parabéns, é uma boa iniciativa pegar o que vemos na faculdade e trazer para o fórum! Parabéns..

Estás em qual período de CC?

Na verdade estou fazendo Engenharia de Telecomunicações. A disciplina é Organização e Arquitetura de Computadores e o assunto, por enquanto, é lógica digital.

Com o tempo essa parte de sinais, ondas, frequências etc vai ser rotina. Posto o que achar mais interessante.