Given a truth table, is there a way to know if it's possible to create any/all logic gates?

Question

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?

Answer 1

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.