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

logiclogical-operators

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 !?

Best 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]

Related Solutions

Python – How to get the logical xor of two variables in Python

If you're already normalizing the inputs to booleans, then != is xor.

bool(a) != bool(b)

C++ – Is short-circuiting logical operators mandated? And evaluation order

Yes, short-circuiting and evaluation order are required for operators || and && in both C and C++ standards.

C++ standard says (there should be an equivalent clause in the C standard):

1.9.18

In the evaluation of the following expressions
a && b
a || b
a ? b : c
a , b
using the built-in meaning of the operators in these expressions, there is a sequence point after the evaluation of the first expression (12).

In C++ there is an extra trap: short-circuiting does NOT apply to types that overload operators || and &&.

Footnote 12: The operators indicated in this paragraph are the built-in operators, as described in clause 5. When one of these operators is overloaded (clause 13) in a valid context, thus designating a user-defined operator function, the expression designates a function invocation, and the operands form an argument list, without an implied sequence point between them.

It is usually not recommended to overload these operators in C++ unless you have a very specific requirement. You can do it, but it may break expected behaviour in other people's code, especially if these operators are used indirectly via instantiating templates with the type overloading these operators.

Best Answer

Related Solutions

Python – How to get the logical xor of two variables in Python

C++ – Is short-circuiting logical operators mandated? And evaluation order

Related Topic