Combinational Logic Circuits#

Source: Combinational Logic Circuits

Learning Goals#

  • Be able to analyze higher-level, purely behavioral digital system descriptions, and design circuits to implement the behavior;

  • Know how to find a minimum expression for any given logic requirement.


Following problems will have a binary output. For that truth tables come handy.

Exercise 49

From which perspective does a truth table describe a circuit?

A) behavioral B) structural C) algorithmic D) data flow E) I don’t know

Exercise 50

You are asked to build the most efficient circuit for a given functional specification.

What do you have to pay attention to? In other words, what does efficient in this context mean?

Exercise 51

What is the advantage of minimizing the logic for a truth table?


Exercise 52

What do we do when we simulate a circuit?

Exercise 53

Why should we work with the simulator if we can directly verify our design on the FPGA?

Introduction to Logic Minimization#

Same Logic Function, Different Circuit Implementations#

Exercise 54

___ truth table exists to describe the relationship between Boolean inputs and outputs. The same relationship can be implemented by ___ logic equations or circuits.


Exercise 55

Why do the minimized SOP and POS versions require less transistors in the figure below?

Different circuit implementations of same logic function ( CC-BY SA 4.0)

Exercise 56

What is the difference between a canonical form and a minimized form?

Find the Most Efficient Circuit#

Exercise 57

Which parameters can we optimize for in a circuit?


The numbers on Figure 2 In the following figure the numbers show the number of logic gates and the total input count of the gates. On the first sight the numbers seem like the number of inputs and total number of transistors, but it is not.

For example the first figure has three gates, a NAND, an AND, an OR. The inverter is not counted as an individual gate. What about the input count? We have three gates and every of them has two inputs, so six in total. CC-BY SA 4.0

Exercise 58

In the following figure the circuits are augmented with

  1. total number of gates

  2. the total number of gate inputs.

Why are these measures important in context of logic minimization?

Boolean Algebra#

Boolean Algebra: Basic Operations#

Exercise 59

What does an

  • unary

  • binary

  • ternary

operation mean? Give examples.


Author’s definition with three set elements 0, 1, A The author writes

Boolean algebra is a proper algebraic system, with three set elements {‘0’, ‘1’, and ‘A’} (where ‘A’ is any variable that can assume the values ‘0’ or ‘1’), two binary operations (AND or intersection, OR or union), and one unary operation (inversion or complementation).

According to Wikipedia: Boolean algebra/Values Boolean algebra does not introduce an A which stands for any value. Boolean algebra includes only True, False, or 1 and 0.

Exercise 60

According to the Boolean algebra \(\overline{x} \cdot x = 0\)


Associative, Commutative, and Distributive Laws#

Exercise 61

What do

  • associative

  • commutative

  • distributive

laws in context of Boolean algebra mean?

DeMorgan’s Law#

Exercise 62

What does DeMorgan’s law state?

Laws for XOR and XNOR#

Exercise 63

How can we apply DeMorgan’s law on XOR and XNOR?

Circuit Illustration for Boolean Algebra#

Use Boolean Algebra to Find Simpler Logic Equations#

Introduction to K-Maps#



Logic graph The author writes:

… Logic graphs offer the easiest and most useful pen-and-paper method of minimizing a logic system. A logic graph and a truth table contain identical information, but patterns that indicate redundant inputs can be readily identified in a logic graph

According to my research logical graph and logic diagram have the same meaning, so the author probably means the same with logic graph.

There are many kinds of logical graphs though and Karnaugh map – in short K-map is one of them.

K-map is not the logical graph but a logical graph.

Exercise 64

en:User:Cburnett, CC BY-SA 3.0, via Wikimedia Commons

You see a K-Map above. What does each cell in a K-Map describe?

A) K-term B) minterm C) maxterm D) K-reduce E) I don’t know

Exercise 65

You want to minimize the logic equation of a truth table with four inputs.

  1. How you you draw it?

  2. How do you fill it out?

Exercise 66

What is the advantage of a K-map over a truth table?

Find Minimum Logic Expressions Using K-maps#

Exercise 67

What does it mean if two adjacent (neighboring) cells have the same output, e.g., 1 in a K-map?

Exercise 68

In the following K-map there are two yellow rectangles which can be compiled together as a square with two variables (\(A\overline{D}\)). Why are we allowed to draw a loop by wrapping around the rectangle? These cells are not adjacent at all!

en:User:Cburnett, CC BY-SA 3.0, via Wikimedia Commons

Super K-maps#


The naming super K-map does not exist

I could not find any reference to super K-maps in literature. The author most likely means K-maps with more than four variables. There are various ways to draw K-maps with five or six variables, e.g.:

Exercise 69

Below is a K-map with six variables. Which grouping makes no sense?

A) red B) blue C) I don’t know

Martin David Johannes Rosenau, CC BY-SA 3.0 DE <>, via Wikimedia Commons

Exercise 70

In the previous exercise we have seen an inconvenient way of minimizing a six input K-map. How can we improve this?

Exercise 71

K-Maps with Don’t Cares#

Incompletely Specified Logic Functions (Don’t Cares)#

Exercise 72

What does don’t care in digital logic mean?

Exercise 73

How can we leverage don’t care in minimization?


Don’t care or the value X in various HDL languages like Verilog and VHDL denote a signal which value is not known

K-Maps with Entered Variables#


This approach is also called reduced Karnaugh map, infrequent variables, map-entered variables, variable-entered map, variable-entered Karnaugh map according to WP: logic minimization – graphical methods.

Exercise 74

  1. How can we get compacter K-maps?

  2. How does it work?

Exercise 75

How can we minimize a K-map with entered variables?

K-Maps with Multiple Outputs#

Exercise 76

We discussed some approaches how to minimize circuits with a single output. How do we minimize when we have multiple outputs?

Computer-Based Logic Minimum#

Exercise 77

We have seen the visual minimization technique K-map.

  • Which computer-based techniques exist?

  • How do they basically work?

Final notes on K-Maps#


K-maps can also be drawn as Venn diagrams or hypercubes.


Minimization methods We focused on K-maps, but there are many more approaches to graphical minimization. Some are:

An introduction to the Vivado logic simulator#

Exercise 78

  1. What is a testbench?

  2. How does the testbench work?

Creating a test bench for a Majority-of-Five circuit


1. Design a “majority of five” circuit#

Exercise 79

Minimize the majority of five circuit using an entered variable K-map.