0

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)

harveyslash
  • 153

1 Answers1

2

$$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.

AlexR
  • 24,905
  • How did you come up with an answer this quickly ? – harveyslash Sep 15 '15 at 21:00
  • 1
    @user2670775 Practice ^^ There is an algorithm as well, but it needs many more gates (read about CNF if you're interested). – AlexR Sep 15 '15 at 21:04
  • But how does one use 4 nand gates (and 4 only) to get the same output given the same input ? – harveyslash Sep 15 '15 at 21:10
  • @user2670775 is a not gate allowed? – AlexR Sep 15 '15 at 21:14
  • Only allowed to use one single ssi 7400 – harveyslash Sep 15 '15 at 21:18
  • You might use a Karnaugh map to arrive at an answer. – Jan Stout Sep 15 '15 at 21:32
  • @user2670775 Okay I found a solution. But what do you need this for? – AlexR Sep 15 '15 at 21:32
  • just experimenting with boolean algebra. don't need it for anything in particular – harveyslash Sep 15 '15 at 21:35
  • @user2670775 Allright, I've added the solution as a bonus. The wiring would chain $A\sqcap A$ into NAND with $B$ into a nand with $C$ and then feed that to both inputs of the fourth NAND. – AlexR Sep 15 '15 at 21:39
  • how are you coming to these solutions so quickly ? is there a certain way you are going about ? – harveyslash Sep 15 '15 at 21:42
  • 1
    @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. – AlexR Sep 15 '15 at 21:45