Boolean Functions

A Multiplexer Can Do More Than Just Select Data

A multiplexer, or MUX, is normally introduced as a circuit that selects one of several inputs and forwards the selected input to the output.

For example, a 4-to-1 multiplexer has:

4 data inputs

↓

2 select inputs

↓

1 output

However, a multiplexer can also be used to IMPLEMENT A BOOLEAN FUNCTION.

This means that instead of thinking:

"Which data signal do I want?"

we can think:

"How can I choose the mux inputs so that the output behaves like the Boolean function I want?"

General Idea

Suppose we have a Boolean function:

F(A,B,C,D)

We want to implement F using a multiplexer.

A useful strategy is:

Choose some variables as mux SELECT inputs.

Then:

For each possible selector combination

↓

Determine what F becomes

↓

Use that result as the corresponding mux DATA input

Conceptually:

Boolean function

↓

Choose selector variables

↓

Break function into cases

↓

Determine mux data inputs

↓

Connect mux

↓

MUX implements the function

Using a 4-to-1 Multiplexer

A 4-to-1 mux requires:

4 data inputs

and:

2 select inputs

Therefore, for:

F(A,B,C,D)

we can choose two of the variables to become the mux selectors.

For example:

A and B

can be used as:

S1 and S0

Then the four possible selector combinations are:

AB = 00

AB = 01

AB = 10

AB = 11

Each of these four cases corresponds to one mux data input.

The Four Mux Data Inputs

For a 4-to-1 mux:

AB = 00

↓

Data input I0

AB = 01

↓

Data input I1

AB = 10

↓

Data input I2

AB = 11

↓

Data input I3

Therefore, the problem becomes:

"What should I0, I1, I2, and I3 be so that the final mux output equals F?"

Fix the Selector Variables

Suppose:

A and B

are the mux selectors.

Now temporarily fix:

A = 0

B = 0

Then ask:

"What does F become when A and B are fixed to 00?"

Since A and B are fixed, the remaining behavior can only depend on:

So the resulting mux data input may be:

or some function of C and D.

Repeat for Every Selector Combination

Repeat the same reasoning for:

AB = 00

AB = 01

AB = 10

AB = 11

For each selector combination:

Fix A and B

↓

Observe how F depends on C and D

↓

Simplify that dependency

↓

Use the simplified result as the mux data input

At the end:

I0 = function for AB = 00

I1 = function for AB = 01

I2 = function for AB = 10

I3 = function for AB = 11

Truth Table Method

One way to determine the mux inputs is from a truth table.

Suppose the truth table contains all combinations of:

Group the rows according to:

AB = 00

AB = 01

AB = 10

AB = 11

Then inspect the output values of F within each group.

For each group, ask:

"How does F depend on C and D?"

That answer becomes the corresponding mux data input.

K-Map Method

A K-map can make the same process easier visually.

Suppose the K-map represents:

F(A,B,C,D)

Choose:

A and B

as the mux selector variables.

Then divide the K-map into regions corresponding to:

AB = 00

AB = 01

AB = 10

AB = 11

Each region tells us the function that should be connected to one mux data input.

The K-Map Is Not Being Used Only for SOP Minimization

Normally, a K-map may be used to derive a minimized Boolean expression.

But here, we are using it differently.

We are asking:

"For this fixed selector combination, what does the output depend on?"

So the K-map becomes a convenient way to derive:

for the multiplexer.

Example: Data Input Equals 0

Suppose that when:

AB = 00

the function is always:

regardless of C and D.

Then:

I0 = 0

This means the mux data input corresponding to:

AB = 00

can be tied directly to logic 0.

Example: Data Input Equals 1

Suppose when:

AB = 01

the function is always:

regardless of C and D.

Then:

I1 = 1

So the corresponding mux input can be tied directly to logic 1.

Example: Data Input Equals C

Suppose when:

AB = 10

the output follows:

regardless of D.

Then:

I2 = C

This means:

if C = 0

↓

F = 0

if C = 1

↓

F = 1

Therefore, the mux data input can be connected directly to C.

Example: Data Input Equals C'

Suppose the output behaves opposite to C.

When:

C = 0

↓

F = 1

When:

C = 1

↓

F = 0

Then:

I = C'

or:

I = NOT C

Example: Data Input Equals D

Similarly, if the output follows D:

D = 0

↓

F = 0

D = 1

↓

F = 1

Then the corresponding mux input is:

Example: Data Input Equals D'

If the output is the complement of D:

D = 0

↓

F = 1

D = 1

↓

F = 0

then:

MUX input = D'

The Simplest Mux Data Inputs

The most convenient mux data-input functions are often:

These require either:

- a constant

- a direct signal

- an inverted signal

This makes the final circuit relatively simple.

What If a Data Input Is More Complicated?

Suppose one selector region gives:

F = C XOR D

or:

F = C AND D

Then the corresponding mux data input is not just:

or D'

Instead, the mux input itself must be produced by another logic function.

Conceptually:

C,D

↓

small logic circuit

↓

mux data input

Using Another Multiplexer for the Subfunction

Instead of using gates for that smaller function, another mux can sometimes implement it.

For example:

Main 4-to-1 mux

↓

one data input requires function of C and D

↓

small 2-to-1 mux implements that function

↓

feeds main mux input

This produces a CASCADED MUX implementation.

Cascaded Multiplexers

CASCADED MULTIPLEXERS means:

The output of one mux or selection network feeds an input of another mux.

Conceptually:

Subfunction

↓

small mux

↓

data input of larger mux

↓

final output

This allows more complicated Boolean functions to be implemented entirely using muxes.

A Multiplexer Can Act Like a Logic Building Block

This is the deeper idea.

A mux can implement:

selection

but it can also implement:

Boolean logic

because the data inputs can be connected to:

variables

complements

other Boolean functions

Therefore, a mux is a very flexible combinational building block.

Why Muxes Can Implement Boolean Functions

A Boolean function ultimately says:

For every possible input combination

↓

produce either 0 or 1

A mux does something similar:

For every possible selector combination

↓

choose the corresponding data input

If the data inputs are chosen carefully:

MUX output

desired Boolean function

Selector Variables Partition the Function

Choosing selector variables divides the Boolean function into smaller cases.

For example:

F(A,B,C,D)

with selectors:

A,B

creates four subcases:

F when AB = 00

F when AB = 01

F when AB = 10

F when AB = 11

Each subcase becomes one mux data input.

This is the central design strategy.

Why the Choice of Selector Variables Matters

Suppose we choose:

A,B

as selectors.

The mux inputs become functions of:

C,D

But if we instead choose:

C,D

as selectors

then the mux inputs become functions of:

A,B

These two implementations can have different complexity.

Therefore:

The choice of selector variables can affect how simple the mux data inputs become.

Good Selector Choice

A good selector-variable choice tends to produce mux inputs that simplify to:

one variable

one complemented variable

or another very simple function.

If the resulting data inputs are very complicated, another selector choice may produce a simpler implementation.

Mux-Based Implementation Is Not Unique

A Boolean function can often be implemented using multiplexers in several different ways.

Different choices of selector variables can produce different mux networks.

Therefore:

One Boolean function

↓

multiple valid mux implementations

The goal is usually to find one that is:

correct

and

reasonably simple

2-to-1 Mux as a Boolean Function

A 2-to-1 mux has:

one selector S

two data inputs:

Its behavior is:

S = 0

↓

output = I0

S = 1

↓

output = I1

By choosing I0 and I1 carefully, many two-variable Boolean functions can be implemented.

Example: NOT Using a 2-to-1 Mux

Suppose:

selector = A

Choose:

I0 = 1

I1 = 0

Then:

A = 0

↓

output = 1

A = 1

↓

output = 0

Therefore:

output = A'

So a mux can implement inversion.

Example: AND Using a 2-to-1 Mux

Let:

selector = A

Choose:

I0 = 0

I1 = B

Then:

A = 0

↓

output = 0

A = 1

↓

output = B

Therefore:

output = A AND B

Example: OR Using a 2-to-1 Mux

Let:

selector = A

Choose:

I0 = B

I1 = 1

Then:

A = 0

↓

output = B

A = 1

↓

output = 1

Therefore:

output = A OR B

Example: XOR Using a 2-to-1 Mux

Let:

selector = A

Choose:

I0 = B

I1 = B'

Then:

A = 0

↓

output = B

A = 1

↓

output = B'

This produces:

A XOR B

Why These Examples Matter

These examples show that muxes are not limited to routing unrelated signals.

By selecting:

constants

variables

complements

as data inputs, the mux itself realizes Boolean logic.

4-to-1 Mux for a 4-Variable Function

For:

F(A,B,C,D)

choose:

A and B

as selectors.

Then:

I0 = function of C,D for AB = 00

I1 = function of C,D for AB = 01

I2 = function of C,D for AB = 10

I3 = function of C,D for AB = 11

This is the standard conceptual pattern for implementing a 4-variable function with a 4-to-1 mux.

Detailed Design Procedure

STEP 1

Start with the Boolean function or truth table/K-map.

STEP 2

Choose the mux size.

STEP 3

Choose the variables that will act as mux selectors.

STEP 4

Partition the function according to all selector combinations.

STEP 5

For each region, determine the required data-input function.

STEP 6

Simplify each data-input function.

STEP 7

Connect the appropriate:

variable

complement

or smaller logic function

to each mux data input.

STEP 8

Verify the final mux output against the original Boolean function.

Example of the Procedure

Suppose:

A,B

are selectors.

After analyzing the K-map, imagine we obtain:

AB = 00

↓

F = 0

AB = 01

↓

F = C

AB = 10

↓

F = D'

AB = 11

↓

F = 1

Then connect:

I0 = 0

I1 = C

I2 = D'

I3 = 1

with:

A,B

connected to the mux select lines.

The mux now implements the required function.

How to Verify the Mux Implementation

After designing the mux network, verify it.

For every possible selector combination:

1. Determine which mux input is selected.

2. Evaluate that data input using the remaining variables.

3. Compare the resulting output against the original truth table or K-map.

If all combinations match:

the mux implementation is correct.

Verification by Selector Region

Suppose:

AB = 10

Then the mux selects:

If:

I2 = D'

then:

the mux output should match D' for every possible C,D combination within the AB = 10 region.

This local verification makes debugging easier.

Constants as Data Inputs

Using:

or:

as mux data inputs is perfectly valid.

It simply means:

For that selector combination, the Boolean function has a constant output.

Therefore, connecting a mux input directly to logic 0 or logic 1 is a normal logic-design technique.

Variables as Data Inputs

A mux input can be connected directly to a Boolean variable.

Example:

I1 = C

This means:

Whenever I1 is selected:

output follows C

Complemented Variables as Data Inputs

A mux input can also be connected to:

or:

This requires the complemented signal to be available or generated.

Conceptually:

variable

↓

NOT

↓

mux data input

Subfunctions as Data Inputs

A mux data input may itself be:

C + D

C•D

C XOR D

or another function.

Then that function can be generated using:

gates

or:

another mux network.

Mux Networks and Hierarchical Decomposition

A complex Boolean function can be decomposed into smaller functions.

Conceptually:

Large Boolean function

↓

divide using select variables

↓

smaller subfunctions

↓

implement each subfunction

↓

combine using main mux

This is a form of hierarchical combinational design.

Boolean Function vs Ordinary Data Selection

ORDINARY DATA-SELECTION VIEW:

Mux chooses one of several independent data signals.

BOOLEAN-FUNCTION VIEW:

Mux data inputs are deliberately chosen so that the output reproduces a desired Boolean function.

The physical device is the same.

The design intention is different.

Connection to Verilog

In Verilog, selection constructs such as:

ternary expressions

case statements

variable indexing

can lead synthesis to infer mux structures.

But in this Unit, we are doing the reverse reasoning.

Instead of:

Verilog

↓

What mux hardware is inferred?

we ask:

Boolean function

↓

How can I intentionally realize it with muxes?

Unit 2 vs Unit 4

UNIT 2:

Variable indexing

↓

MUX INFERENCE

Question:

"What selection hardware does this Verilog expression imply?"

UNIT 4:

Boolean function

↓

MUX DESIGN

Question:

"How can I deliberately use muxes to implement this function?"

These are related ideas, but they are not the same skill.

K-Map Role in Mux Design

The K-map helps reveal the subfunction for each selector combination.

For example:

Choose A,B as selectors.

Then each AB region contains output values as C,D vary.

That small pattern may correspond to:

or another simple function.

Therefore, the K-map helps us derive the mux data inputs.

Common Mistake: Choosing Select Variables Without Checking Simplicity

Any valid selector choice can potentially work.

But some choices may lead to very complicated mux data-input functions.

Therefore, after choosing selectors:

inspect the resulting subfunctions.

If they are unnecessarily complex:

consider a different selector choice.

Common Mistake: Treating the Remaining Variables as Selectors Too

If:

A,B

are the select variables

then:

C,D

normally determine the DATA INPUT FUNCTIONS.

Do not confuse these roles.

Conceptually:

A,B

↓

choose which mux input is active

C,D

↓

determine the value placed on that input

Common Mistake: Assuming Every Data Input Must Be a Variable

Mux inputs can be:

or more complex expressions.

There is no rule that every data input must be one original input variable.

Common Mistake: Assuming Every Function Needs Gates Before the Mux

Sometimes all derived mux inputs are only:

constants

variables

complements

In such a case, very little additional logic may be needed.

The mux itself performs most of the function implementation.

Common Mistake: Forgetting Selector Ordering

For a 4-to-1 mux, the mapping:

00 → I0

01 → I1

10 → I2

11 → I3

depends on the selector bit ordering.

If the selector variables are connected in the opposite order, the input mapping changes.

Therefore:

Always define clearly which Boolean variable corresponds to which selector bit.

Selector Ordering Example

Suppose:

S1 = A

S0 = B

Then:

AB = 00 → I0

AB = 01 → I1

AB = 10 → I2

AB = 11 → I3

But if:

S1 = B

S0 = A

then the mapping changes.

Therefore, selector assignment must remain consistent during the entire derivation.

Multiplexer as a Universal Combinational Building Block

Because mux data inputs can be tied to:

constants

variables

complements

subfunctions

muxes can be used to realize arbitrary combinational Boolean functions when enough mux resources are available.

This makes the multiplexer a highly flexible logic-building block.

Final Comparison

MUX ORDINARY USE

Purpose:

Select one of several data inputs.

MUX BOOLEAN-FUNCTION USE

Purpose:

Implement a Boolean function by carefully choosing selector variables and data-input functions.

SELECT VARIABLES

Purpose:

Partition the Boolean function into separate cases.

DATA INPUT FUNCTION

Purpose:

Describe what the Boolean function becomes for one fixed selector combination.

CONSTANT DATA INPUT

Examples:

VARIABLE DATA INPUT

Examples:

COMPLEMENTED DATA INPUT

Examples:

SUBFUNCTION DATA INPUT

Examples:

C XOR D

C•D

C + D

CASCADED MUX

Meaning:

One mux helps generate a subfunction that feeds another mux.

Final Mental Model

Suppose we want:

F(A,B,C,D)

implemented with a 4-to-1 mux.

Think:

STEP 1

↓

Choose two variables as selectors

Example:

A,B

STEP 2

↓

Break the function into four selector cases

AB = 00

AB = 01

AB = 10

AB = 11

STEP 3

↓

For each case, ask:

"What does F become as the remaining variables change?"

STEP 4

↓

Simplify each answer

Possible results:

or another subfunction

STEP 5

↓

Connect those results to:

STEP 6

↓

Connect A,B to the mux selectors

STEP 7

↓

Verify against the original truth table or K-map

The most important ideas are:

A MULTIPLEXER CAN IMPLEMENT BOOLEAN FUNCTIONS, NOT JUST ROUTE DATA.

MUX SELECT VARIABLES PARTITION THE BOOLEAN FUNCTION INTO CASES.

EACH SELECTOR COMBINATION DETERMINES ONE MUX DATA-INPUT FUNCTION.

THE DATA INPUT MAY SIMPLIFY TO 0, 1, A VARIABLE, A COMPLEMENT, OR ANOTHER BOOLEAN SUBFUNCTION.

A K-MAP CAN BE USED TO DERIVE THE MUX DATA INPUTS FOR EACH SELECTOR REGION.

THE CHOICE OF SELECT VARIABLES CAN AFFECT THE COMPLEXITY OF THE RESULTING IMPLEMENTATION.

SMALLER MUXES CAN IMPLEMENT SUBFUNCTIONS AND FEED A LARGER MUX.

A 2-TO-1 MUX CAN IMPLEMENT FUNCTIONS SUCH AS NOT, AND, OR, AND XOR WITH APPROPRIATE DATA-INPUT CONNECTIONS.

MULTIPLE DIFFERENT MUX IMPLEMENTATIONS MAY REALIZE THE SAME BOOLEAN FUNCTION.

ALWAYS KEEP SELECTOR ORDERING CONSISTENT WHEN MAPPING SELECTOR COMBINATIONS TO I0, I1, I2, AND I3.

UNIT 2 TAUGHT HOW VERILOG CAN INFER MUX HARDWARE.

THIS UNIT TEACHES THE REVERSE SKILL:

START WITH A BOOLEAN FUNCTION

↓

DELIBERATELY BUILD A MUX IMPLEMENTATION.