Part IV: Digital Electronics | Chapter 10

Boolean Algebra & Logic Gates

AND, OR, NOT, NAND, NOR, XOR gates, De Morgan's theorems, truth tables, canonical forms, Karnaugh maps, and gate-level implementation

1. Boolean Algebra

Boolean algebra, introduced by George Boole in 1854, is a mathematical system operating on variables that take only two values: 0 (False) and 1 (True). Three fundamental operations are sufficient to express any digital function:

AND (·)

\( F = A \cdot B \)

F=1 only if both inputs are 1

OR (+)

\( F = A + B \)

F=1 if at least one input is 1

NOT (‾)

\( F = \overline{A} \)

Inversion: F=1 iff A=0

Key identities: \( A \cdot 0 = 0 \), \( A + 1 = 1 \),\( A \cdot A = A \), \( A + A = A \),\( A \cdot \overline{A} = 0 \), \( A + \overline{A} = 1 \). Absorption: \( A + AB = A \).

2. Logic Gate Symbols

Standard logic gate symbols and their Boolean expressions

NAND and NOR are universal gates — any Boolean function can be implemented using only NAND gates (or only NOR gates). This is exploited in integrated circuit fabrication where a single gate cell is used for all logic.

3. De Morgan's Theorems

De Morgan's theorems provide the key equivalences between AND/OR and complemented functions:

First Theorem

\[ \overline{A \cdot B} = \overline{A} + \overline{B} \]

NAND = negative-OR

Second Theorem

\[ \overline{A + B} = \overline{A} \cdot \overline{B} \]

NOR = negative-AND

These theorems are used to convert between SOP (sum of products) and POS (product of sums) forms, and to simplify Boolean expressions by pushing inversions through logic gates.

4. Canonical Forms & Karnaugh Maps

Any Boolean function can be written as a Sum of Products (SOP) — OR of AND terms, one per minterm — or Product of Sums (POS). The minimal SOP is found by grouping 1s in a Karnaugh map (K-map) into rectangles of size \( 2^k \).

K-Map Rules

• Group cells filled with 1 in powers of 2: 1, 2, 4, 8
• Groups may wrap around edges (toroidal)
• Larger groups give simpler (fewer literal) terms
• Every 1 must be covered; 1s may belong to multiple groups

SOP vs POS

SOP: group the 1s → simpler for active-high outputs. POS: group the 0s, complement → simpler for active-low outputs.\( F = \sum m(1,3,5,7) = C \) is the simplest possible.

5. Python: Truth Tables, K-Map & Expression Solver

Generate truth tables for all 2-input gates, display a 3-variable Karnaugh map, and evaluate five Boolean expressions over all 8 combinations of three variables (A, B, C).

Python

script.py140 lines

import numpy as np
import matplotlib.pyplot as plt
import matplotlib.gridspec as gridspec
from itertools import product as iproduct

plt.style.use('dark_background')
fig = plt.figure(figsize=(14, 11))
fig.patch.set_facecolor('#0a0a0a')
gs = gridspec.GridSpec(2, 2, figure=fig, hspace=0.5, wspace=0.35)

# ---- 1. Truth table for all basic gates (2-input) ----
ax1 = fig.add_subplot(gs[0, 0])
ax1.set_facecolor('#0f0f0f')

rows = [(a, b) for a in [0,1] for b in [0,1]]
A_vals = [r[0] for r in rows]
B_vals = [r[1] for r in rows]
AND_out  = [a & b  for a,b in rows]
OR_out   = [a | b  for a,b in rows]
NAND_out = [int(not (a & b)) for a,b in rows]
NOR_out  = [int(not (a | b)) for a,b in rows]
XOR_out  = [a ^ b  for a,b in rows]

x = np.arange(4)
w = 0.15
bars = [
    (AND_out,  '#34d399', 'AND'),
    (OR_out,   '#60a5fa', 'OR'),
    (NAND_out, '#fbbf24', 'NAND'),
    (NOR_out,  '#f87171', 'NOR'),
    (XOR_out,  '#a78bfa', 'XOR'),
]
offsets = np.linspace(-2*w, 2*w, 5)
for (vals, col, lbl), off in zip(bars, offsets):
    ax1.bar(x + off, vals, width=w, color=col, label=lbl, alpha=0.85)

ax1.set_xticks(x)
ax1.set_xticklabels(['A=0,B=0', 'A=0,B=1', 'A=1,B=0', 'A=1,B=1'], fontsize=7, rotation=15, color='#9ca3af')
ax1.set_yticks([0, 1])
ax1.set_yticklabels(['0', '1'], color='#9ca3af')
ax1.set_title('Truth Table: All 2-Input Gates', color='#6ee7b7', fontsize=10)
ax1.legend(fontsize=7, framealpha=0.2)
ax1.tick_params(colors='#9ca3af')
ax1.grid(True, color='#1f2937', axis='y', alpha=0.6)
for sp in ax1.spines.values(): sp.set_edgecolor('#374151')

# ---- 2. Karnaugh map solver (3-variable) ----
ax2 = fig.add_subplot(gs[0, 1])
ax2.set_facecolor('#0a0a0a')
ax2.axis('off')

# Example 3-variable function: F(A,B,C) = sum of minterms {1,3,5,7}
# i.e., F = C (since output is 1 whenever C=1)
# Display K-map as a colored grid (2x4): rows = A, columns = BC in Gray code
f_vals = [0, 1, 0, 1,   # A=0: BC=00,01,11,10
          0, 1, 0, 1]    # A=1: BC=00,01,11,10

# K-map layout (3 var): rows = A (0,1), cols = BC (00,01,11,10) Gray code
kmap = np.array(f_vals).reshape(2, 4)
bc_labels = ['BC=00', 'BC=01', 'BC=11', 'BC=10']
a_labels  = ['A=0', 'A=1']

cell_colors = [['#1a3a2a' if v == 1 else '#1a1a2a' for v in row] for row in kmap]

table_data = []
for i, row in enumerate(kmap):
    table_data.append([a_labels[i]] + [str(v) for v in row])

col_labels = [''] + bc_labels
table = ax2.table(cellText=table_data,
                  colLabels=col_labels,
                  loc='center', cellLoc='center')
table.auto_set_font_size(False)
table.set_fontsize(9)
for (row, col), cell in table.get_celld().items():
    cell.set_facecolor('#0f0f0f')
    cell.set_edgecolor('#374151')
    if row == 0:
        cell.set_text_props(color='#6ee7b7', fontweight='bold')
    elif col == 0:
        cell.set_text_props(color='#6ee7b7')
    else:
        val = table_data[row-1][col]
        if val == '1':
            cell.set_facecolor('#064e3b')
            cell.set_text_props(color='#34d399', fontweight='bold')
        else:
            cell.set_text_props(color='#9ca3af')

ax2.set_title('Karnaugh Map: F = C
(minterms: 1,3,5,7 — all shaded)',
              color='#6ee7b7', fontsize=9, pad=20)
ax2.text(0.5, 0.08, 'Minimized SOP: F = C', transform=ax2.transAxes,
         ha='center', color='#fbbf24', fontsize=10, fontweight='bold')

# ---- 3. Boolean expression truth table generator ----
ax3 = fig.add_subplot(gs[1, :])
ax3.set_facecolor('#0f0f0f')

# Evaluate several Boolean expressions over all 3-variable combinations
inputs = list(iproduct([0,1], repeat=3))
A_arr = np.array([r[0] for r in inputs])
B_arr = np.array([r[1] for r in inputs])
C_arr = np.array([r[2] for r in inputs])

expressions = {
    'F1 = A AND B':            A_arr & B_arr,
    'F2 = A OR C':             A_arr | C_arr,
    'F3 = NOT(A) AND B':       (~A_arr & 1) & B_arr,
    'F4 = (A XOR B) OR C':     (A_arr ^ B_arr) | C_arr,
    'F5 = NAND(A,B,C)':        1 - (A_arr & B_arr & C_arr),
}

x_idx = np.arange(8)
width = 0.16
cols_expr = ['#34d399', '#60a5fa', '#fbbf24', '#f87171', '#a78bfa']
offsets2 = np.linspace(-2*width, 2*width, 5)

for (expr_name, vals), off, col in zip(expressions.items(), offsets2, cols_expr):
    ax3.bar(x_idx + off, vals, width=width, color=col, label=expr_name, alpha=0.85)

tick_labels = [f'({a},{b},{c})' for a,b,c in inputs]
ax3.set_xticks(x_idx)
ax3.set_xticklabels(tick_labels, fontsize=8, rotation=20, color='#9ca3af')
ax3.set_yticks([0, 1])
ax3.set_yticklabels(['0 (False)', '1 (True)'], color='#9ca3af')
ax3.set_title('Boolean Expression Truth Table: 3-Variable Functions (A, B, C)', color='#6ee7b7', fontsize=11)
ax3.legend(fontsize=8, framealpha=0.2, loc='upper right', ncol=2)
ax3.tick_params(colors='#9ca3af')
ax3.grid(True, color='#1f2937', axis='y', alpha=0.6)
for sp in ax3.spines.values(): sp.set_edgecolor('#374151')
ax3.set_xlabel('Input combinations (A, B, C)', color='#9ca3af')

plt.suptitle('Boolean Logic: Truth Tables, K-Map & Expression Evaluation', color='#6ee7b7', fontsize=13, y=1.01)
plt.savefig('output.png', dpi=130, bbox_inches='tight', facecolor='#0a0a0a')
print('Saved output.png')
print('Truth tables generated for AND, OR, NAND, NOR, XOR')
print('K-map solved: F(A,B,C) = C  (minterms 1,3,5,7)')
print('5 three-variable Boolean expressions evaluated over all 8 input combinations')

Click Run to execute the Python code

Code will be executed with Python 3 on the server

← Feedback & Stability Next: Flip-Flops & Counters →