Are || and ! operators sufficient to make every possible logical expression?

JakeTheSnake picture JakeTheSnake · Oct 15, 2015 · Viewed 21.3k times · Source

The logical expression ( a && b ) (both a and b have boolean values) can be written like !(!a || !b), for example. Doesn't this mean that && is "unneccesary"? Does this mean that all logical expressions can be made only using || and !?

Answer

Peter Olson picture Peter Olson · Oct 16, 2015

Yes, as the other answers pointed out, the set of operators comprising of || and ! is functionally complete. Here's a constructive proof of that, showing how to use them to express all sixteen possible logical connectives between the boolean variables A and B:

Note that both NAND and NOR are by themselves functionally complete (which can be proved using the same method above), so if you want to verify that a set of operators is functionally complete, it's enough to show that you can express either NAND or NOR with it.

Here's a graph showing the Venn diagrams for each of the connectives listed above:

enter image description here

[source]