Combinational Logic Design

Abstract

Combinational Logic Design translates functional behavioral descriptions into physical gate-level circuits. Logic problems are specified using Truth Tables that define output behavior for every combination of input signals. Standard arithmetic building blocks such as Half Adders and Full Adders illustrate how multi-output truth tables synthesize into optimized Boolean expressions. Formal circuit analysis relies on fundamental canonical terms: literals, implicants, implicates, minterms, and maxterms.

---

Converting Boolean Equations to Gate Circuits

To construct a circuit diagram from a Boolean expression:

1. Identify the primary output function.
2. Work backwards from the output gate toward the input variables.
3. Sub-expressions inside parentheses or under complement bars represent intermediate logic gate outputs.

Example Construction

Given the Boolean expression:

$$F=a\cdot \overline{b+\overline{c}}$$

• Output Gate: An AND gate combining $a$ with the intermediate signal $\overline{b+\overline{c}}$.
• Intermediate Logic: A NOR gate operating on input $b$ and the inverted input $\overline{c}$ (NOT gate on $c$).

Gate-level Circuit Diagram for $F=a\cdot \overline{b+\overline{c}}$

---

Specifying Logic Functions with Truth Tables

Truth tables provide a complete, non-ambiguous specification of a combinational circuit by listing all $2^n$ possible input state combinations and their corresponding outputs.

1. Half Adder

A Half Adder adds two 1-bit binary inputs ($a,b$) and produces a 1-bit Sum ($S$) and a Carry-out ($C_{out}$).

Half Adder Logic Gate Implementation

Half Adder Truth Table

$a$	$b$	Carry ($C_{out}$)	Sum ($S$)
$0$	$0$	$0$	$0$
$0$	$1$	$0$	$1$
$1$	$0$	$0$	$1$
$1$	$1$	$1$	$0$

Half Adder Boolean Equations

$$\begin{array}{rl}\text{Sum}(a,b)& =a^{\prime }b+a{b}^{\prime }=a\oplus b\\ \text{Carry}(a,b)& =ab\end{array}$$

2. Full Adder

A Full Adder adds three 1-bit binary inputs: two primary operands ($A,B$) and an incoming Carry-in ($C_{in}$) from a less significant bit position. It produces a Sum ($S$) and a Carry-out ($C_{out}$).

Full Adder Circuit Schematic

Full Adder Truth Table

$C_{in}$	$A$	$B$	Carry-out ($C_{out}$)	Sum ($S$)
$0$	$0$	$0$	$0$	$0$
$0$	$0$	$1$	$0$	$1$
$0$	$1$	$0$	$0$	$1$
$0$	$1$	$1$	$1$	$0$
$1$	$0$	$0$	$0$	$1$
$1$	$0$	$1$	$1$	$0$
$1$	$1$	$0$	$1$	$0$
$1$	$1$	$1$	$1$	$1$

Full Adder Boolean Equations

$$\begin{array}{rl}S& =A\oplus B\oplus C_{in}\\ C_{out}& =AB+A{C}_{in}+B{C}_{in}=AB+C_{in}(A+B)\end{array}$$

---

Canonical Definitions & Terminology

Understanding algebraic structure requires precise terminology for variables and expressions:

Term	Definition	Examples
Complement	A variable negated with a bar or prime.	$A^{\prime }$, $B^{\prime }$, $\overline{C}$
Literal	A single variable or its complement.	$A,A^{\prime },B,B^{\prime },C,C^{\prime }$
Implicant	A product (AND term) of one or more literals.	$ABC,A^{\prime }C,BC,AC$
Implicate	A sum (OR term) of one or more literals.	$(A+B+C),(A+C),(A+B)$
Minterm ($m_i$)	A product (AND term) containing every input variable in true or complemented form. Evaluates to $1$ for exactly one input combination.	$ABC,A^{\prime }BC,A{B}^{\prime }{C}^{\prime }$
Maxterm ($M_i$)	A sum (OR term) containing every input variable in true or complemented form. Evaluates to $0$ for exactly one input combination.	$(A+B+C),(A^{\prime }+B+C),(A^{\prime }+B^{\prime }+C)$

---

Related Notes

• Number Systems and Boolean Algebra
• Transistors & Gates
• SOP, POS, K-Maps & Logic Simplification
• Mux & Demux
• Encoder & Decoder
• Adders & Subtractors
• Digital Systems