Truth table of big boolean expression

46 Views Asked by At
A'B'C'D' + A'B'C'D + A'B'CD +A'BC'D'+A'BC'D + A'BCD + ABC'D' + ABC'D + ABCD

I am trying to create the truth table for the expression above problem is that it will take a really long time to create it are there any short cut methods to get the out put of the created truth table. This is a 4 input expression.

1

There are 1 best solutions below

0
On BEST ANSWER

Here's the K-map:

\begin{array}{c|c|c|c|c|} &AB&A'B&A'B'&AB'\\ \hline CD&1&1&1&0\\ \hline C'D&1&1&1&0\\ \hline C'D'&1&1&1&0\\ \hline CD'&0&0&0&0\\ \hline \end{array}

Remember that you want to group together all $1$'s in blocks of $m \times n$, with both $m$ and $n$ powers of $2$, that are as large as possible. In this case, you can create $4$ blocks of $2 \times 2$ $1$'s, corresponding to $BD$, $A'D$, $BC'$, and $A'C'$

So, expression simplifies to: $BD+A'D+BC'+A'C'$

Alternatively, we can focus on the $0$'s, and notice we can cover all them with two $4 \times 1$ strips, corresponding to $AB'$ and $CD'$, meaning that the expression is also equivalent to the negation of $AB' +CD'$, which is $(A'+B)(C'+D)$

Indeed, if you apply Distribution to this latter expression, you're back at the former.

Of course, you can also just directly work with the very starting expression. If you do so, you can use:

Adjacency

$PQ +PQ'=P$

(it's called Adjacency since in a K-map this amounts to grouping together adjacent (groups of) cells into larger groups)

So, for example, you can apply Adjacency to the first two terms $A'B'C'D'$ and $A'B'C'D$ to obtain $A'B'C'$. Likewise, $A'BC'D'$ and $A'BC'D$ combine to $A'BC'$, and the just obtained $A'B'C'$ and $A'BC'$ can be further combined to $A'C'$.

So, keep combining pairs as much as possible ...

For example, taking terms 5,6,8, and 9:

$A'BC'D + A'BCD + ABC'D + ABCD= A'BD+ABD=BD$

Likewise, terms 2,3,5, and 6 combine to:

$A'B'C'D + A'B'CD +A'BC'D + A'BCD=A'B'D+A'BD=A'D$

So note that you just used terms 5 and 6 again, but that's ok, because using Idempotence, you can always duplicate terms if needed. Indeed, if you look at the K=-map, you'll find that $A'BC'D$ will be used in al four blocks.

Anyway, continuing this should get you to $BD+A'D+BC'+A'C'$ as well, no K-Map needed.