How to rewrite all the boolean operations using if-then-else operator?

Question

Cited by Conditional Term Rewriting Systems: 1st International Workshop Orsay, France, July 8-10, 1987, p. 105

Additional Boolean operations are not needed, because all the usual Boolean operations can be expressed as derived operations in terms of the if-then-else.

This is also mentioned in Functional Programming Principles in Scala course on Coursera.org by Martin Odersky (compendium):

Turns out that all the operations on booleans can be defined in terms of ifThenElse.

I guess that could be obvious for those who is familiar with the topic, but how do we know this is possible? How to formulate general rules for performing these operations?

Answer 1

Let's try it:

AND(x, y) = ITE(x, y, x)
OR(x, y) = ITE(x, x, y)
NOT(x) = ITE(x, false, true)
EXOR(x, y) = ITE(x, ITE(y, false, true), y)
EXNOR(x, y) = ITE(x, y, ITE(y, false, true))
IMPLIES(x, y) = ITE(x, y, true)
NAND(x, y) = ITE(x, ITE(y, false, true), false)
NOR(x, y) = ITE(x, false, ITE(y, false, true))

IfThenElse (ITE) is not functionally complete, because constants true and false are required to implement certain functions.