Prove Shannons expansion theorem presented in Section 4.1.2. Section 4.1.2 Figures 4.6 through 4.9 illustrate how truth

Question:

Prove Shannon’s expansion theorem presented in Section 4.1.2.

Section 4.1.2

Figures 4.6 through 4.9 illustrate how truth tables can be interpreted to implement logic functions using multiplexers. In each case the inputs to the multiplexers are the constants 0 and 1, or some variable or its complement. Besides using such simple inputs, it is possible to connect more complex circuits as inputs to a multiplexer, allowing functions to be synthesized using a combination of multiplexers and other logic gates. Suppose that we want to implement the three-input majority function in Figure 4.7 using a 2-to-1 multiplexer in this way. Figure 4.10 shows an intuitive way of realizing this function. The truth table can be modified as shown on the right. If w₁= 0, then f = w₂w₃, and if w₁= 1, then f = w₂ + w₃. Using w₁as the select input for a 2-to-1 multiplexer leads to the circuit in Figure 4.10b.
This implementation can be derived using algebraic manipulation as follows. The function in Figure 4.10a is expressed in sum-of-products form as

f = w₁w₂w₃+ w₁w₂w₃ + w₁w₂w₃ + w₁w₂w₃
It can be manipulated into
f = w₁(w₂w₃) + w₁(w₂w₃ + w₂w₃ + w₂w₃)
= w₁(w₂w₃) + w₁(w₂+ w₃)

which corresponds to the circuit in Figure 4.10b.
Multiplexer implementations of logic functions require that a given function be decomposed in terms of the variables that are used as the select inputs. This can be accomplished by means of a theorem proposed by Claude Shannon [1].