3

Boa noite, galera!

Estou a realizar um trabalho que tenho que simplificar uma expressão algébrica booleana de um circuito:

circuito

E a expressão mais simples que achei foi essa:

expressão

Mas acho que ela pode ser mais simples, alguém teria uma solução melhor que esta?

3
  • A fórmula está correta. Sua intenção é ter menos níveis de porta and/porta or? Commented 3/11/2017 às 23:28
  • Essa questão trata de uma das ferramentas usadas para diminuir a profundidade para o mínimo possível de portas n-árias, o mapa de Karnaugh: pt.stackoverflow.com/q/228005/64969 Commented 3/11/2017 às 23:30
  • 1
    Desculpe ter trocado o NOR com NAND. Já arrumei as duas respostas. Commented 7/11/2017 às 3:03

2 Respostas 2

4

Esta resposta é uma solução por meio de redução de expressões booleanas. Também postei uma outra resposta baseada na análise da tabela-verdade.

A primeira porta NOR na figura produz isso:

(1) j = NOT (a OR b OR c)

A porta NOT abaixo dessa NOR:

(2) k = NOT b

A porta XOR:

(3) m = d XOR k

A porta NOT acima da XOR:

(4) n = NOT d

A penúltima porta NAND:

(5) p = NOT (j AND n)

A porta final:

(6) f = NOT (p AND m)

Substituindo-se (5) em (6):

(7) f = NOT (NOT (j AND n) AND m)

Substituindo-se (4) em (7):

(8) f = NOT (NOT (j AND NOT d) AND m)

Substituindo-se (3) em (8):

(9) f = NOT (NOT (j AND NOT d) AND (d XOR k))

Substituindo-se (2) em (9):

(10) f = NOT (NOT (j AND NOT d) AND (d XOR NOT b))

Substituindo-se (1) em (10):

(10) f = NOT (NOT (NOT (a OR b OR c) AND NOT d) AND (d XOR NOT b))

Essa é a expressão equivalente. Agora, vamos simplificá-la. Aplicando a lei de Morgan nos parênteses mais internos de (10):

z = NOT (a OR b OR c)
f = NOT (NOT (z AND NOT d) AND (d XOR NOT b))
z = NOT a AND NOT b AND NOT c
(11) f = NOT (NOT ((NOT a AND NOT b AND NOT c) AND NOT d) AND (d XOR NOT b))

Aplicando a lei de Morgan de novo em (11):

z = NOT ((NOT a AND NOT b AND NOT c) AND NOT d)
x = (NOT a AND NOT b AND NOT c)
y = NOT d
z = NOT (x AND y)
z = NOT x OR NOT y
z = NOT (NOT a AND NOT b AND NOT c) OR d
(12) f = NOT ((NOT (NOT a AND NOT b AND NOT c) OR d) AND (d XOR NOT b))

Mais uma vez:

z = NOT (NOT a AND NOT b AND NOT c)
z = a OR b OR c
(13) f = NOT (((a OR b OR c) OR d) AND (d XOR NOT b))

De novo:

x = ((a OR b OR c) OR d)
y = (d XOR NOT b)
f = NOT (x AND y)
f = NOT x OR NOT y
(14) f = NOT ((a OR b OR c) OR d) OR NOT (d XOR NOT b)

Simplificando os parênteses:

(15) f = NOT (a OR b OR c OR d) OR NOT (d XOR NOT b)

Aplicando de Morgan de novo:

z = NOT (a OR b OR c OR d)
z = NOT a AND NOT b AND NOT c AND NOT d
(16) f = (NOT a AND NOT b AND NOT c AND NOT d) OR NOT (d XOR NOT b)

Considerando que (x XOR NOT y) é a equivalente a (x <-> y), então:

(17) f = (NOT a AND NOT b AND NOT c AND NOT d) OR NOT (d <-> b)

Considerando que NOT (x <-> y) é a equivalente a (x XOR y), então:

(18) f = (NOT a AND NOT b AND NOT c AND NOT d) OR (d XOR b)

Considerando que (x XOR y) é equivalente a (x AND NOT y) OR (NOT x AND y):

(19) f = (NOT a AND NOT b AND NOT c AND NOT d) OR (d AND NOT b) OR (NOT d AND b)

Agora, temos duas possibilidades, agrupar o NOT d AND alguma-coisa. Ou agrupar o NOT b AND alguma-coisa. Vamos começar com o NOT d:

(20a) f = (NOT d AND ((NOT a AND NOT b AND NOT c) OR b)) OR (d AND NOT b)

Distribuindo-se o OR b:

(21a) f = (NOT d AND (NOT a OR b) AND (NOT b OR b) AND (NOT c OR b)) OR (d AND NOT b)

Ora, NOT b OR b é verdadeiro! Então:

(22a) f = (NOT d AND (NOT a OR b) AND TRUE AND (NOT c OR b)) OR (d AND NOT b)

E temos que (x AND TRUE) = x. Logo:

(23a) f = (NOT d AND (NOT a OR b) AND (NOT c OR b)) OR (d AND NOT b)

Colocando-se o b em evidência de novo:

(24a) f = (NOT d AND ((NOT a AND NOT c) OR b)) OR (d AND NOT b)

Distribuindo-se o NOT d AND:

(25a) f = (NOT d AND NOT a AND NOT c) OR (NOT d AND b) OR (d AND NOT b)

Considerando que (NOT d AND b) OR (d AND NOT b) é o mesmo que (d XOR b):

(26a) f = (NOT a AND NOT c AND NOT d) OR (d XOR b)

Se tivéssemos agrupado com o NOT b ao invés do NOT d:

(20b) f = (NOT b AND ((NOT a AND NOT c AND NOT d) OR d)) OR (NOT d AND b)

Distribuindo-se o OR d:

(21b) f = (NOT b AND (NOT a OR d) AND (NOT c OR d) AND (NOT d OR d)) OR (NOT d AND b)

Ora, NOT d OR d é verdadeiro! Então:

(22b) f = (NOT b AND (NOT a OR d) AND (NOT c OR d) AND TRUE) OR (NOT d AND b)

E temos que (x AND TRUE) = x. Logo:

(23b) f = (NOT b AND (NOT a OR d) AND (NOT c OR d)) OR (NOT d AND b)

Colocando-se o b em evidência de novo:

(24b) f = (NOT b AND ((NOT a AND NOT c) OR d)) OR (NOT d AND b)

Distribuindo-se o NOT b AND:

(25b) f = (NOT b AND NOT a AND NOT c) OR (NOT b AND d) OR (NOT d AND b)

Considerando que (NOT b AND d) OR (NOT d AND b) é o mesmo que (d XOR b):

(26b) f = (NOT a AND NOT b AND NOT c) OR (d XOR b)

Temos como resultados:

  • f = (NOT a AND NOT c AND NOT d) OR (d XOR b).
  • f = (NOT a AND NOT b AND NOT c) OR (d XOR b).

Essas são as possíveis soluções.

2
  • Creio que está seja a solução mais completa que achei, simplesmente sensacional! Muito obrigado pela ajuda e contribuição,amigo!
    – Dwcleb
    Commented 4/11/2017 às 14:42
  • em (1) você faz menção a uma porta NAND, quando na verdade é uma porta NOT OR.
    – Dwcleb
    Commented 7/11/2017 às 1:17
3

Esta resposta é uma solução por meio de análise da tabela-verdade. Também postei uma outra resposta baseada em redução de expressões booleanas.

Vamos ver como fica a tabela-verdade:

A B C D F
0 0 0 0 1
0 0 0 1 1
0 0 1 0 0
0 0 1 1 1
0 1 0 0 1
0 1 0 1 0
0 1 1 0 1
0 1 1 1 0
1 0 0 0 0
1 0 0 1 1
1 0 1 0 0
1 0 1 1 1
1 1 0 0 1
1 1 0 1 0
1 1 1 0 1
1 1 1 1 0

Vamos reorganizar as colunas, colocando na ordem CABD e permutando as linhas de acordo para ficar na ordem onde os números das quatro colunas da esquerda crescem em ordem binária do 0000 até o 1111:

C A B D F
0 0 0 0 1
0 0 0 1 1
0 0 1 0 1
0 0 1 1 0
0 1 0 0 0
0 1 0 1 1
0 1 1 0 1
0 1 1 1 0
1 0 0 0 0
1 0 0 1 1
1 0 1 0 1
1 0 1 1 0
1 1 0 0 0
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0

Observe que os valores de F da primeira metade da tabela são quase idênticos aos da segunda, com exceção da primeira linha de cada (0000 e 1000). Vamos ver o que há de especial nessas linhas (e para essa parte, o C não importa):

A B D F
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 0

Observe que os casos onde a saída é um são os casos B XOR D.

Voltando na primeira linha de cada metade da tabela:

C A B D F
0 0 0 0 1
1 0 0 0 0

Isso daí equivale a (NOT A AND NOT B AND NOT C AND NOT D).

Juntando as duas subexpressões temos:

(NOT A AND NOT B AND NOT C AND NOT D) OR (B XOR D)

No entanto, se voltarmos a olhar na tabela, dá para simplificar (NOT A AND NOT B AND NOT C AND NOT D) cortando uma (mas não as duas) subexpressões NOT B ou NOT D. Assim, chega-se em duas possíveis soluções:

  • (NOT A AND NOT B AND NOT C) OR (B XOR D)

  • (NOT A AND NOT C AND NOT D) OR (B XOR D)

3
  • Na terceira tabela vc diz ter colocado o C na frente, mas apenas trocou a leta, e a coluna permanece a mesma...
    – Dwcleb
    Commented 7/11/2017 às 1:18
  • 1
    @Dwcleb Não. Observe a coluna do F. Onde era "B=1, C=0, D=1, F=0", agora é "C=0, B=1, D=1, F=0". Onde era "B=1, C=1, D=1, F=0", agora é "C=1, B=1, D=1, F=0". Não apenas permutei as colunas, mas também as linhas para ficar na ordem 000 -> 111. Commented 7/11/2017 às 1:55
  • @Dwcleb Editei a resposta para explicar melhor. Commented 7/11/2017 às 1:56

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .