Logic gates. Simplification of Boolean functions

Definition

A logic gate is an electronic circuit that implements a Boolean operation on binary variables and produces a binary output.

A Boolean function is an algebraic expression made from binary variables, logical operations such as AND, OR, and NOT, and constants 0 and 1.

Simplification of Boolean functions means rewriting a Boolean expression into an equivalent expression with minimum complexity while preserving the same input-output behavior.

Main Content

1. Logic Gates and Their Basic Operation

AND gate, OR gate, and NOT gate

• The AND gate gives output 1 only when all inputs are 1.
• The OR gate gives output 1 when at least one input is 1.
• The NOT gate inverts the input, changing 0 to 1 and 1 to 0.

Truth examples:

• AND: if $A=1$ and $B=0$, output $Y=0$
• OR: if $A=1$ and $B=0$, output $Y=1$
• NOT: if $A=0$, output $Y=1$

Universal and special gates

• NAND and NOR are universal gates, meaning any Boolean function can be implemented using only NAND gates or only NOR gates.
• XOR produces 1 when inputs are different; XNOR produces 1 when inputs are same.
• These gates are widely used in parity checking, arithmetic circuits, and comparisons.

Common meanings:

• NAND = NOT-AND
• NOR = NOT-OR
• XOR = exclusive OR
• XNOR = exclusive NOR

2. Boolean Algebra and Canonical Forms

Boolean algebra rules

• Boolean functions follow algebraic laws such as commutative, associative, distributive, identity, complement, and absorption laws.
• These laws allow expressions to be transformed without changing their logical meaning.
• Example:
  • $A + A B = A$ using absorption law
  • $A + A' = 1$ using complement law

Standard representations of Boolean functions

• Boolean functions are often written in canonical forms:
  • Sum of minterms (SOP): function is written as an OR of AND terms.
  • Product of maxterms (POS): function is written as an AND of OR terms.
• Canonical forms are useful for analysis, truth-table conversion, and systematic simplification.

Example:

• If a function is 1 for rows 1, 3, and 7, it can be written as:
  • $F = \Sigma m(1,3,7)$

3. Simplification of Boolean Functions

Purpose of simplification

• Reduces the number of gates and connections.
• Decreases propagation delay and improves speed.
• Lowers power consumption and cost.
• Improves reliability by reducing circuit complexity.

Methods of simplification

• Algebraic simplification uses Boolean laws to reduce expressions step by step.
• Graphical simplification uses Karnaugh maps to identify adjacent 1s or 0s and form groups.
• Tabulation methods such as the Quine–McCluskey method are used for systematic minimization, especially when many variables are involved.

Example of algebraic simplification: $$F = A B + A B' = A(B + B') = A(1) = A$$

Example of the idea behind minimization:

• Original: $F = A B C + A B C' + A B' C$
• Grouping common terms can reduce the number of literals and gates.

Working / Process

1. Obtain the Boolean expression or truth table

• Start with the circuit, algebraic expression, minterms, maxterms, or truth table.
• Identify which input combinations produce output 1 or 0.
• Convert the given information into a Boolean form if necessary.

2. Apply simplification rules or techniques

• Use Boolean algebra laws such as absorption, De Morgan’s theorem, distribution, and complement laws.
• For graphical methods, place values in a Karnaugh map and group adjacent cells in powers of 2.
• For larger functions, use systematic tabulation to find prime implicants and essential prime implicants.

Example rules:

• $A + A B = A$
• $A(A + B) = A$
• $(A + B)' = A'B'$
• $(A B)' = A' + B'$

3. Verify and implement the simplified result

• Compare the simplified expression with the original truth table to ensure equivalence.
• Draw the final logic circuit using fewer gates.
• Check whether the simplified form reduces hardware, delay, and cost.

Example:

• Original: $F = A B + A B'$
• Simplified: $F = A$
• Implementation changes from two AND gates and one OR gate to a direct connection of $A$

Advantages / Applications

Reduces circuit complexity

• Fewer gates and fewer interconnections make the design easier to build and test.

Improves speed and efficiency

• Simplified circuits usually have shorter logic paths, resulting in less delay.

Widely used in digital system design

• Essential in CPUs, ALUs, control units, memory decoding, and combinational logic circuits.

Useful in practical applications

• Found in calculators, traffic light controllers, alarm systems, digital displays, and communication circuits.

Supports cost and power reduction

• Less hardware means lower manufacturing cost and reduced energy consumption.

Summary

• Logic gates are the basic electronic components that perform binary operations.
• Boolean functions can be simplified to make digital circuits smaller and more efficient.
• Important terms to remember: AND, OR, NOT, NAND, NOR, XOR, XNOR, Boolean algebra, minterm, maxterm, Karnaugh map, simplification