The Game Makers Brasil

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.
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á:
É 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.
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.