Digital Logic — Glossary
Boolean Algebra
Boolean algebra is an algebra over binary values {0,1} (False/True) that defines logical operations and rules used to model digital circuits and logical expressions.
Boolean algebra underpins simplification and analysis of logic used in electronics, computer science and telecommunications.
Boolean Operations
NOT (Negation)
Unary operator that flips a bit: NOT A or A'. If A=1 then A’=0, and vice versa.
AND (Conjunction)
Binary operator: output is 1 only when A=1 and B=1. Notation: A ⋅ B or A & B.
OR (Disjunction)
Binary operator: output is 1 when at least one input is 1. Notation: A + B.
Other gates
- XOR (Exclusive OR): true if exactly one input is 1 (
A ⊕ B). - NAND: inverse of AND. Useful as a universal gate.
- NOR: inverse of OR. Also a universal gate.
- XNOR: inverse of XOR — true when inputs are equal.
Truth Table
A truth table lists all possible input combinations and the resulting outputs. For n inputs there are 2n combinations.
Example: A + B and A ⋅ B
| A | B | A + B | A ⋅ B |
|---|---|---|---|
| 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 |
| 0 | 0 | 0 | 0 |
Boolean Expressions & Variables
Boolean variable: stores 0 or 1. Literal: a variable or its complement (e.g., A or A').
Boolean expression: formula built from variables and operators; evaluates to 0 or 1. Example: P + Q = R.
Laws & Theorems
Key laws used to manipulate and simplify expressions. (Selection of the laws from the source.)
- Identity:
A + 0 = A,A ⋅ 1 = A - Idempotent:
A + A = A,A ⋅ A = A - Commutative:
A + B = B + A - Associative:
(A + B) + C = A + (B + C) - Distributive:
A ⋅ (B + C) = A⋅B + A⋅C - Complement:
A + A' = 1,A ⋅ A' = 0 - De Morgan:
(A ⋅ B)' = A' + B'and(A + B)' = A'⋅B' - Absorption:
A + (A⋅B) = A
De Morgan — small diagram
Combinational Circuits
Circuits whose outputs depend only on the current inputs (no memory). Examples: adders, multiplexers, decoders.
Sequential Circuits
Circuits whose outputs depend on current inputs and previous states — i.e., they include memory (flip-flops). Examples: counters, shift registers.
Minimization of Boolean Functions
Techniques to simplify Boolean expressions to reduce gates and cost:
- Boolean algebraic manipulation — apply laws and theorems to reduce expressions.
- Karnaugh map (K-map) — visual grouping of minterms to find simplified sum-of-products (best for up to ~6 variables).
Fixed Point Representation
Representation of real numbers where the binary point position is fixed. Notation: fixed<w,b> where w is bit width and b is number of fractional bits.
Example: 11010.12 = 26.5
Signed Representations
Common ways to encode negative numbers in binary:
- Sign-magnitude: MSB is sign bit, remaining bits magnitude.
- 1’s complement: complement each bit; two representations of zero exist (+0 and -0).
- 2’s complement: invert bits and add 1 — standard for signed integers; unique zero; range for 8-bit: -128..127.
