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

Ver o tópico anterior Ver o tópico seguinte Ir em baixo

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

Mensagem por PedroX em Sab 28 Mar 2015, 20:30

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

Ranking : Nota C
Número de Mensagens : 6034
Idade : 21
Data de inscrição : 26/07/2008
Notas recebidas : C+B
Reputação : 286
Insignia 1 x 0 Insignia 2 x 0 Insignia 3 x 0
Prêmios
   :
   :
   :

Voltar ao Topo Ir em baixo

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

Mensagem por fredcobain em Seg 30 Mar 2015, 18:02

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:
http://gmbr.forumeiros.com/t27761-logica-e-operadores-de-bits-por-brendan640


fredcobain

Ranking : Sem avaliações
Número de Mensagens : 691
Idade : 35
Data de inscrição : 14/04/2011
Reputação : 162
Insignia 1 x 0 Insignia 2 x 0 Insignia 3 x 0
Prêmios
   : 0
   : 0
   : 0

Voltar ao Topo Ir em baixo

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

Mensagem por Gonzo em Seg 30 Mar 2015, 20:56

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


Gonzo

Número de Mensagens : 927
Data de inscrição : 29/05/2012
Reputação : 33
Insignia 1 x 0 Insignia 2 x 0 Insignia 3 x 0

Voltar ao Topo Ir em baixo

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

Mensagem por PedroX em Ter 31 Mar 2015, 22:21

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

Ranking : Nota C
Número de Mensagens : 6034
Idade : 21
Data de inscrição : 26/07/2008
Notas recebidas : C+B
Reputação : 286
Insignia 1 x 0 Insignia 2 x 0 Insignia 3 x 0
Prêmios
   :
   :
   :

Voltar ao Topo Ir em baixo

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

Mensagem por luan.alc em Qua 01 Abr 2015, 12:38

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?

luan.alc

Ranking : Nota B
Número de Mensagens : 293
Idade : 20
Data de inscrição : 13/03/2012
Notas recebidas : B
Reputação : 3
Insignia 1 x 0 Insignia 2 x 0 Insignia 3 x 0
Prêmios
   : 0
   : 0
   : 1

Voltar ao Topo Ir em baixo

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

Mensagem por PedroX em Qua 01 Abr 2015, 13:46

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.

PedroX

Ranking : Nota C
Número de Mensagens : 6034
Idade : 21
Data de inscrição : 26/07/2008
Notas recebidas : C+B
Reputação : 286
Insignia 1 x 0 Insignia 2 x 0 Insignia 3 x 0
Prêmios
   :
   :
   :

Voltar ao Topo Ir em baixo

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

Mensagem por Conteúdo patrocinado Hoje à(s) 16:41


Conteúdo patrocinado


Voltar ao Topo Ir em baixo

Ver o tópico anterior Ver o tópico seguinte Voltar ao Topo

- Tópicos similares

 
Permissão deste fórum:
Você não pode responder aos tópicos neste fórum