If only one multiplexer and one inverter are allowed to be used t

SOLUTION

We have one MUX and one inverter, then we can implement any Boolean function of n variables with 2^n-1 line to 1 line MUX.

Explanation:

Suppose we have 2^n-1:1 MUX, then we can implement Boolean function of (n – 1) variables

Example Let n = 3

n – 1 = 2

f(A, B) → Boolean function of 2 variables

Total number of Boolean function = 2²⁽²⁾ = 2⁴ = 16

We will provide AB to select lines S₁ and S₀ and input lines are fed with the help of V_cc and ground to implement any of the 16 functions mentioned above.

So, with the help of 2^n-1 : 1 MUX, we have implemented (n – 1) variables functions easily without any inverter.

But, now consider that we are provided with 2^n-1 : 1 MUX and one inverter. Now we can implement functions of n-variables as well.

Example:

Let n = 3

So, we have 2² : 1 or 4 : 1 MUX and one inverter.

Now consider a function of n = 3 variables.

f(A, B, C) = ∑ m (1, 4, 5, 6), let us implement this function

Now 4: 1 MUX can accept only 4 input and 2 select lines. Let the 2 select lines be A and B.

We can write our truth table as follows:

Now, here A B is used as select lines and the input is provided with C to MUX, and that C could be in its true form, or complemented form, hence an inverter is required.

Summary:

1) If we have 2ⁿ : 1 MUX, we can implement all n number of variables functions.

2) If we have 2ⁿ : 1 MUX along with an inverter, we can implement all n and n + 1 number of variables functions.