Concurso: Simplificação booleana

Esta questão vem do NC-UFPR, Concurso da Itaipu para Engenharia Eletrônica em 2019.

Questão interessante sobre simplificação booleana.

Veremos três formas de realizar a simplificação: através de álgebra e através da criação da tabela verdade e através do mapa de Karnaugh.

Note que estamos utilizando ‘ (aspas simples) para identificar a operação de complementar, ou seja, x’ = NOT x.

Questão

(Adaptado) 38 – Um engenheiro precisa implementar um circuito lógico para a expressão x = (A’+B)(A+B+D)D’. O objetivo da equipe de projeto é criar um circuito otimizado e de baixo custo. Para o alcance deste objetivo, uma das etapas do projeto envolve a simplificação da expressão algébrica apresentada. Levando em consideração esses dados, assinale a alternativa com a expressão algébrica simplificada de x.

a) x = (A’+B)+D.

b) x = (A’+B)D’.

c) x = BD’.

d) x = D’.

e) x = (A+D)’.

Simplificação por álgebra

Vamos iniciar com a expressão original.

x = (A’+B)(A+B+D)D’

Quando termos vários termos com mesmas variáveis podemos realizar simplificações na maioria dos casos. Outros casos onde geralmente podemos simplificar são operações com constantes (ex: x+1=1) e termos com mesma variável repetida (ex: x+x’=1).

Vamos comparar o que há em cada termo.

O primeiro termo tem A e B. O segundo termo tem A, B e D. O terceiro termo tem apenas D.

Vamos primeiro expandir o segundo e terceiro termos utilizando a propriedade distributiva da álgebra boolenana: (x+y)z = xz+yz.

x = (A’+B)(AD’+BD’+DD’)

Temos a propriedade DD’=0 então podemos remover ele da expressão. Novamente utilizamos a propriedade distributiva, mas dessa vez para extrair o termo D’.

x = (A’+B)(AD’+BD’) = (A’+B)(A+B)D’

Agora temos apenas um termo com a variável D. Vamos agora expandir o primeiro e o segundo termo desta última equação.

x = (A’A+A’B+BA+BB)D’

Temos as propriedades A’A=0 e BB=B, que podemos simplificar.

x = (A’B+BA+B)D’

Novamente podemos utilizar a propriedade distributiva, agora para extrair B.

x = (A’+A+1)BD’

Podemos agora simplificar A’+A+1=1.

x = BD’

Agora cada termo possui variáveis distintas e não há mais o que simplificar.

Portanto, a alternativa correta é c) x = BD’.

Comentários:

  • Várias propriedades da álgebra booleana foram utilizadas para simplificar esta expressão.
  • A explicação é relativamente grande, mas se escrevermos apenas as equações podemos ver que é fácil e rápido.
  • Caso o problema seja mais complexo e não conseguiu realizar alguma simplificação construa a tabela verdade.

Simplificação pela tabela verdade

Suponhamos que a expressão é bem complicada e chegou a um ponto que não sabe mais se é possível simplificar. Então vamos montar a tabela verdade.

Para simplificar vamos dividir o problema em quatro partes, calculando primeiro três variáveis intermediárias:

U = A’+B

V = A+B+D

W = D’

x = (A’+B)(A+B+D)D’ = UVW

Cada parte é fácil de determinar. Vejamos a tabela verdade montada abaixo.

       U=   V=    W= x=
A B D  A'+B A+B+D D' UVW
------------------------
0 0 0  1    0     1   0
0 0 1  1    1     0   0
0 1 0  1    1     1   1
0 1 1  1    1     0   0
1 0 0  0    1     1   0
1 0 1  0    1     0   0
1 1 0  1    1     1   1
1 1 1  1    1     0   0

As vezes é fácil ver um padrão na tabela verdade. Isso depende da ordem em que colocamos as variáveis de entrada. Note que sequência da tabela verdade de x é a mesma para A=0 e para A=1. Isso indica que A não influencia no resultado.

Vamos remover A da tabela verdade, junto com as variáveis intermediárias.

B D  x
------
0 0  0
0 1  0
1 0  1
1 1  0

Agora vemos que a saída é 1 apenas quando B=1 e D=0. Assim podemos determinar x facilmente.

x = BD’

Portanto, a alternativa correta é c) x = BD’.

Comentários:

  • Ver o padrão na tabela verdade é mais fácil dependendo da ordem em que as variáveis aparecem.
  • Caso não haja padrão algum ou não o veja, construir a tabela verdade é um passo intermediário para construir o mapa de Karnaugh.

Simplificação por mapa de Karnaugh

O mapa de Karnaugh é o último passo para a simplificação de uma expressão booleana. Com ele é possível determinar a expressão mínima.

x = (A’+B)(A+B+D)D’

A partir da expressão booleana montamos a tabela veradde.

A B D  x
--------
0 0 0  0
0 0 1  0
0 1 0  1
0 1 1  0
1 0 0  0
1 0 1  0
1 1 0  1
1 1 1  0

Agora construímos o mapa de Karnugh a partir da tabela verdade.

No mapa de Karnaugh a sequência em que as entradas são invertidas é importante! As entradas devem ser invertidas de acordo com o código de Gray: 00 01 11 10. Veja a sequência das variáveis A e B.

A linha 1 e coluna 2 (A’B’ e D) identifica o valor da tabela verdade quando A=0, B=0 e D=1, que é 0.

A linha 2 e coluna 1 (A’B e D’) identifica o valor da tabela verdade quando A=0, B=1 e D=0, que é 1.

E assim por diante.

  x  | D' D
------------
A'B' | 0  0
A'B  | 1  0
A B  | 1  0
A B' | 0  0

Podemos ver que há um par de uns (1) juntos. Isso remove uma variável ambígua, que no caso é A. Já podemos visualmente determinar qual a expressão mínima.

x = BD’

Podemos também realizar a soma de produtos, onde podemos facilmente ver a simplificação da variável ambígua A.

x = A’BD’ + ABD’ = (A’+A)BD’ = BD’

Comentários:

  • Nesse tipo de problema, no pior dos casos será necessário criar o mapa de Karnaugh.
  • Com o mapa de Karnaugh é fácil determinar a expressão mínima.
  • No mapa é essencial colocar as entradas na sequência correta e obter o valor certo da tabela verdade.

Mande seu problema e Compartilhe!

Como você resolveria este problema? Explique nos comentários!

Você tem um problema interessante? Envie para nós resolvermos! Veja como na página Problemas de Concursos.

Autor: Djones Boni

Engenheiro Eletricista e Eletrônico. Professor de Engenharia Eletrônica na UTFPR Toledo. Interesses: Sistemas eletrônicos embarcados e de tempo real.

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *