0

Is it possible to do without brute forcing it?

| a | b | out |
---------------
| 0 | 0 |  1 |
| 0 | 1 |  0 |
| 1 | 0 |  1 |
| 1 | 1 |  1 |

I managed to bruteforce my way through it and figured that it is possible to implement AND/OR/NOT gates, but it took way too long to figure out. Is there a faster way to do this?

integralfx
  • 21
  • If you can make either one of NAND or NOR, you have made a universal gate, so you can make every other logic gate. – Patrick Stevens Nov 13 '17 at 08:26
  • You didn't manage, I'd say. Show how you imagine to implement a NOT gate with this, please! –  Nov 13 '17 at 09:04

1 Answers1

0

You notice that if $a$ is true, then the out is true. Thus you can say that it should be out = a OR (...) for some expression in the brackets. This alone takes care of the bottom two rows without affecting the top two rows.

As for the top two rows, we see that those correspond exactly to NOT b. So we let that be our bracket, and we get the final expression out = a OR NOT b quite quickly.

There is also a way to do this relatively quickly in general. If you have some truth table like yours, then it is quite easy to find the full disjunctive normal form of the final column. We begin by looking at each row, and what combination of variables they represent. For instance, the first row represents NOT a AND NOT b, and the last column represents a AND b (these lines are always the combination of every single variable with AND, and with NOT put in at appropriate places). Then you just take every single one of these that gives a 1 in the final column, and you OR them all together. In our case, this gives us

out = (NOT a AND NOT b) OR (a AND NOT b) OR (a AND b)

This will always work, and always be correct. Can it be simplified? Probably. Is it easy to simplify? Not always.

Arthur
  • 199,419
  • And because we've figured out that we can make the NOT and OR gates, we know we can create the AND gate because NOT(a AND b) = NOT a OR not B which we can just NOT the output again, to get a AND b – integralfx Nov 13 '17 at 09:02
  • This doesn't answer the question, it shows how to get a boolean expression from the truth table. –  Nov 13 '17 at 09:07
  • @integralfx I'm answering a completely different question. I'm telling you how to implement you truth table using the standard logic connectors, while you ask how to make the standard logic connectors using your table. I would delete this answer, but I can't since it's accepted. – Arthur Nov 13 '17 at 11:19