Define negation, or and exclusive-or with only if-then-else, variables and constants.
ITE, if-then-else, takes three functions: f ? g : h is g where f is 1 and h where f is 0. Every operator of two operands can be written with ITE, its operands and the constants 0 and 1. Expand the operator on its first operand, as Shannon expansion does: for each value of that operand, what remains is a function of the second one alone.
f ? g : h
g
f
h
Write k = p & q & r with ITE, variables and constants only. Expand it on p: with p = 0, k is 0; with p = 1, it is q & r. So k = p ? (q & r) : 0.
k = p & q & r
p
p = 0
k
p = 1
q & r
k = p ? (q & r) : 0
q & r still uses &. Expand it on q: with q = 0 it is 0, and with q = 1 it is r. So q & r is q ? r : 0.
&
q
q = 0
q = 1
r
q ? r : 0
Put the two together: k = p ? (q ? r : 0) : 0.
k = p ? (q ? r : 0) : 0
Check one row: at p = 1, q = 1, r = 0, the outer ITE takes q ? r : 0, which takes r, which is 0; and p & q & r is 0 too.
p = 1, q = 1, r = 0
p & q & r
Given: order: a b;
order: a b;
Using only ? :, variables and the constants 0 and 1, define three functions of a and b: n, the negation of a; o, a or b; and x, a exclusive-or b.
? :
a
b
n
o
x
Three definitions, one per line, each name = expression;: n, o and x. Use only the conditional p ? q : r, the variables a and b, the constants 0 and 1, and parentheses. For example, a function of other variables might read m = s ? (t ? 0 : u) : 1;.
name = expression;
p ? q : r
m = s ? (t ? 0 : u) : 1;
n is ~a.
o is a | b.
x is a ^ b.
Only ? :, variables and the constants 0 and 1.
Watch the conditions: they tick once n, o and x are defined, and the last one stays met only while you use nothing but ? :, variables and constants.
For each function, set a = 1 in your expression and simplify, then a = 0: compare each result with what the negation, the or and the exclusive-or give for that value of a.
a = 1
a = 0
Read each diagram from its root: the then edge out of the node on a leads to the function with a = 1, and the else edge to the function with a = 0.
Kata 3.1 of Binary Decision Diagrams with CUDD on formal.org. The site checks the answer when you press Check answer; sign in to keep your progress.