Are || and ! operators sufficient to make every possible logical expression?
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
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:
- True:
A || !A - A NAND B:
!A || !B - B implies A:
!B || A - A implies B:
!A || B - A OR B:
A || B - Not B:
!B - Not A:
!A - A XOR B:
!(!A || B) || !(A || !B) - A XNOR B:
!(!A || !B) || !(A || B) - A:
A - B:
B - A NOR B:
!(A || B) - A does not imply B:
!(!A || B) - B does not imply A:
!(!B || A) - A AND B:
!(!A || !B) - False:
!(A || !A)
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:
[source]
