Four identities relate a function to its cofactors. Choose the one that holds for every function.
Shannon expansion says f = x ? f1 : f0 for every function f. Any expression that gives f1 wherever x is 1 and f0 wherever x is 0, whatever f1 and f0 are, is the same identity written another way; an expression that fails on one value of x for some f is not an identity.
f = x ? f1 : f0
f
f1
x
f0
Is f = f1 & f0 | x an identity? Test it with each value of x.
f = f1 & f0 | x
With x = 1, the right-hand side is f1 & f0 | 1, which is 1. But f with x = 1 is f1, which can be 0.
x = 1
f1 & f0 | 1
Take f = x & y: then f1 = y and f0 = 0. At x = 1, y = 0, f is 0 while the right-hand side is 1.
f = x & y
f1 = y
f0 = 0
x = 1, y = 0
One function and one assignment where the two sides differ is enough: f = f1 & f0 | x is not an identity.
Write f1 for a function f with x set to 1, and f0 for f with x set to 0.
Which identity holds for every function f?
f = x & f0 | ~x & f1
f = f1 ^ f0
f = (x | f0) & (~x | f1)
f = x & f1 | f0
Choose one of the four options.
One identity.
For an option, substitute x = 1 and simplify: the right-hand side must become f1. Then substitute x = 0: it must become f0.
x = 0
In Explore the example, write f1 and f0 for its f, then define the option's right-hand side and compare it with f.
Kata 1.4 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.