Prove the following Expansion Theorem in two dual forms (due toClaude Shannon) u

ID: 3608290 • Letter: P

Question

Prove the following Expansion Theorem in two dual forms (due toClaude Shannon) using only the postulates/axiomsof Boolean Set Theory.

A. f(x1,…, xk, …, xN) = xk .f(x1,…, 1, …, xN) + xk’.f(x1, …, 0,…, xN)

B. f(x1,…, xk, …, xN) = [xk + f(x1, …,0, …, xN)] . [xk’ + f(x1, …, 1,…, xN)]

Hint: Don’t try to prove the general case,consider base cases and work from there using substitution andother “tricks”.

I really just don't know where to start, any tips would be greatlyappreciated, or an example of what to use for the base case.

Proof of Shannon’s Expansion Theorem:

The proof of Shannon’s Expansion Theorem is broken up intotwo cases: one case for when x1 = 1 and one forwhen x1 = 0.

Case 1: x1 = 1

Since x1 = 1, f (x1, x2, . . .,xn ) = f (1, x2, . . . ,xn).

Because X = 1. X, 0 =0. X, and X + 0 = X, f (1,x2, . . . ,xn) = f (1, x2, . . .,xn).1+ f (0,x2, . . . ,xn) .0.

Since x1 = 1, f (1, x2, . . . ,xn).1 + f (0,x2, . . . ,xn) . 0 = f (1,x2, . . . ,xn). x1 + f(0,x2, . . . ,xn) . x11 .

Therefore, by transitivity, f (x1, x2, . .. ,xn) = x1. f (1, x2, . . . ,xn)+x11 . f (1, x2, . . .,xn).

Case 2: x1 = 0

Since x1 = 0, f (x1, x2, . . .,xn) = + f (0,x2, . . . ,xn).

Because X = 1.X, 0 = 0.X, and 0 + X = X, + f (0,x2, .. . ,xn) = f (1, x2, . . . ,xn). 0+ + f (0,x2, . . . ,xn).1.

Since x1 = 0, f (1, x2, . . . ,xn).0 + + f(0,x2, . . . ,xn).1 = f (1, x2, .. . ,xn). x1 + + f (0,x2, . . .,xn). x11 .

Therefore, by transitivity, f (x1, x2, . .. ,xn) = x1. f(1, x2 ,..., xn) +x11 . + f (0,x2, . . .,xn).

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.