0
$\begingroup$

I have been given a truth table. I want find a boolean expression for it. However , I am not able to come up with one. Is there a specific way to go about , in order to get it done ? enter image description here

Also, Can this solution be possible using a single ssi 7400 chip ? (max of 4 nand gates)

$\endgroup$
2
$\begingroup$

$$C \wedge (A \vee \neg B)$$

By looking at the TT you can easily see that $\phi(A,B,C) \Rightarrow C$ wich means that $\phi \equiv C \wedge ?$. The rest is simple.

If you only want to come up with some formula, regardless of the number of conjuctives, the TT can be directly translated to a formula in CNF. (It has $2^n$ clauses each with $n$ literals for a total of $(n-1)2^n + 2^n - 1 = n2^n - 1$ gates. This case would result in $23$ gates compared to the two we actually needed)

To arrive at a circuit using 4 NAND gates we remember (using $\sqcap$ for NAND):

$$A \sqcap A = \neg A \\ A \wedge B = \neg (A \sqcap B) = (A\sqcap B)\sqcap(A\sqcap B)\\ A \vee B = \neg A \sqcap \neg B$$

Where the middle one only needs two NAND gates by reusing the result of $A\sqcap B$.

$$\begin{align*} C \wedge (A \vee \neg B) & \stackrel{(3)}\equiv C \wedge (\neg A \sqcap B) \\ & \stackrel{(1)}\equiv C \wedge ((A\sqcap A) \sqcap B) \\ & \stackrel{(2)}\equiv (C\sqcap((A\sqcap A) \sqcap B)) \sqcap (C\sqcap((A\sqcap A)\sqcap B)) \end{align*}$$

So this is possible with 4 NAND gates on your chip.

$\endgroup$
11
  • $\begingroup$ How did you come up with an answer this quickly ? $\endgroup$ – harveyslash Sep 15 '15 at 21:00
  • 1
    $\begingroup$ @user2670775 Practice ^^ There is an algorithm as well, but it needs many more gates (read about CNF if you're interested). $\endgroup$ – AlexR Sep 15 '15 at 21:04
  • $\begingroup$ But how does one use 4 nand gates (and 4 only) to get the same output given the same input ? $\endgroup$ – harveyslash Sep 15 '15 at 21:10
  • $\begingroup$ @user2670775 is a not gate allowed? $\endgroup$ – AlexR Sep 15 '15 at 21:14
  • 1
    $\begingroup$ @user2670775 I actually consider my second solution to have taken "too much time" ^^ I played around with MATLAB to represent the standard conjunctives used in my original solution by NANDs, since I'm not really thinking in terms of NANDs. After figuring out the three rules above it was just a matter of plugging in and checking that we only need four NANDs. $\endgroup$ – AlexR Sep 15 '15 at 21:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.