Glossary: Boolean Algebra

Key terms and definitions for Unit 2. Definitions follow ISO 11179 metadata registry standards.

A

Absorption Law — A Boolean theorem that eliminates redundant terms from an expression, stated as \(A + AB = A\) and \(A(A + B) = A\).

Algebraic Simplification — The process of reducing a Boolean expression to a simpler equivalent form by systematically applying Boolean theorems and identities to minimize the number of literals, terms, and gates needed for implementation.

AND Gate — A logic gate that implements the AND operation, producing a HIGH output only when all of its inputs are HIGH. Its standard symbol features a flat left edge and a curved right edge (D-shape).

AND Operation — The fundamental Boolean operation (logical conjunction) that produces a 1 output only when all inputs are 1, denoted by a dot (\(\cdot\)), adjacency, or the wedge symbol, and analogous to multiplication in ordinary algebra.

Associative Law — A Boolean algebraic law stating that the grouping of operands does not affect the result: \((A + B) + C = A + (B + C)\) and \((A \cdot B) \cdot C = A \cdot (B \cdot C)\).

B

Boolean Algebra — A mathematical system developed by George Boole in 1854 for manipulating logical values, operating exclusively on binary values (0 and 1) and forming the theoretical foundation for digital logic design.

Boolean Constant — A fixed Boolean value that is either 0 or 1, as opposed to a variable whose value can change.

Boolean Expression — An algebraic formula composed of Boolean variables, constants, and operations (AND, OR, NOT) that can be represented by a truth table and evaluated to produce a binary output.

Boolean Variable — An unknown quantity in Boolean algebra that can take on only one of two values (0 or 1), typically denoted by uppercase letters such as A, B, C.

Buffer Gate — A logic gate that passes its input unchanged to the output (\(F = A\)), providing signal amplification, isolation, and timing delay in physical circuits despite performing no logical transformation.

C

Canonical Form — A Boolean expression in which every product term (for SOP) or every sum term (for POS) contains all variables of the function, providing a unique representation derived directly from minterms or maxterms.

Cascading Gates — A technique of connecting multiple gates in series to handle more inputs than a single gate can accommodate, such as using three 2-input AND gates to implement a 4-input AND function.

Circuit Analysis — The process of deriving the Boolean expression from an existing logic circuit diagram by labeling intermediate gate outputs and substituting expressions to obtain the final output function.

Circuit Synthesis — The process of constructing a logic circuit from a Boolean expression by identifying the required gates from the operations and connecting them according to the expression's structure.

Commutative Law — A Boolean algebraic law stating that the order of operands does not affect the result: \(A + B = B + A\) and \(A \cdot B = B \cdot A\).

Complement — The result of inverting a Boolean value or variable, where the complement of 0 is 1 and the complement of 1 is 0, denoted by an overbar, prime, or the NOT symbol.

Complement Law — A Boolean identity stating that a variable operated with its own complement produces a constant: \(A + \overline{A} = 1\) and \(A \cdot \overline{A} = 0\).

Consensus Theorem — A Boolean theorem that identifies and eliminates a redundant consensus term, stated as \(AB + \overline{A}C + BC = AB + \overline{A}C\), where the \(BC\) term is already covered by the other two terms.

D

DeMorgan's First Theorem — The Boolean theorem stating that the complement of a product equals the sum of the complements: \(\overline{A \cdot B} = \overline{A} + \overline{B}\), meaning a NAND gate is equivalent to an OR gate with inverted inputs.

DeMorgan's Second Theorem — The Boolean theorem stating that the complement of a sum equals the product of the complements: \(\overline{A + B} = \overline{A} \cdot \overline{B}\), meaning a NOR gate is equivalent to an AND gate with inverted inputs.

Distributive Law — A Boolean algebraic law that allows distribution of one operation over another: \(A(B + C) = AB + AC\) and, uniquely in Boolean algebra, \(A + BC = (A + B)(A + C)\).

Duality Principle — The principle stating that any valid Boolean theorem remains valid if AND and OR operators are interchanged and the constants 0 and 1 are interchanged throughout the expression.

F

Fan-In — The maximum number of inputs that a logic gate can accept, typically limited to 8–12 inputs for standard logic families due to speed and power constraints.

Fan-Out — The maximum number of gate inputs that a single gate output can drive without signal degradation, typically limited to 10 for standard TTL gates.

G – H

Gate Symbols — Standardized graphical representations of logic gates, including both distinctive-shape symbols (e.g., D-shape for AND, pointed shape for OR) and IEEE rectangular symbols with function labels (e.g., "&" for AND, ">=1" for OR).

High and Low States — The two voltage levels in physical digital circuits (HIGH and LOW) that correspond to the binary logic values 1 and 0 respectively in positive logic convention.

High-Impedance State (Z) — A third output state (beyond 0 and 1) in which a tri-state buffer effectively disconnects from the circuit, enabling multiple devices to share a common data bus without signal conflicts.

I

Idempotent Law — A Boolean identity stating that a repeated operation of a variable with itself returns the variable unchanged: \(A + A = A\) and \(A \cdot A = A\).

Identity Law — A Boolean identity stating that a variable operated with an identity element returns the variable: \(A + 0 = A\) and \(A \cdot 1 = A\).

Inverter — Another name for the NOT gate, a logic gate that inverts its single input, drawn as a triangle with a small circle (bubble) at the output to indicate inversion.

Involution Law — A Boolean identity stating that complementing a variable twice returns the original value: \(\overline{\overline{A}} = A\), also known as the double complement law.

L

Literal — A Boolean variable or its complement appearing in a Boolean expression; for example, the expression \(AB + \overline{A}C\) contains four literals: \(A\), \(B\), \(\overline{A}\), and \(C\).

Logic Function — A mapping from all possible input combinations to output values, where multiple different Boolean expressions can represent the same logic function.

Logic Gates — Physical electronic devices that implement Boolean operations, each having one or more inputs and producing an output based on a specific Boolean function, serving as the building blocks of all digital circuits.

Logic Levels — The designation of voltage ranges in digital circuits as either HIGH or LOW, corresponding to the Boolean values 1 and 0, with specific voltage thresholds defined by the logic family (e.g., TTL: LOW = 0–0.8V, HIGH = 2.0–5.0V).

M

Maxterm — A sum term (OR of literals) in a POS expression in which every variable of the function appears exactly once, either in complemented or uncomplemented form, corresponding to an input combination for which the function output is 0.

Minterm — A product term (AND of literals) in an SOP expression in which every variable of the function appears exactly once, either in complemented or uncomplemented form, corresponding to an input combination for which the function output is 1.

Multiple Input Gates — Logic gates extended beyond two inputs to accept \(n\) inputs, where an \(n\)-input AND outputs 1 only if all \(n\) inputs are 1, and an \(n\)-input XOR outputs 1 if an odd number of inputs are 1.

N

NAND Gate — A derived logic gate (NOT-AND) that produces the complement of the AND operation, outputting LOW only when all inputs are HIGH, and recognized as a universal gate.

Noise Margin — The amount of voltage deviation from the ideal logic level that a circuit can tolerate without producing incorrect logic outputs, determined by the difference between guaranteed output levels and required input levels.

NOR Gate — A derived logic gate (NOT-OR) that produces the complement of the OR operation, outputting HIGH only when all inputs are LOW, and recognized as a universal gate.

NOT Gate — A basic logic gate (also called an inverter) that implements the NOT operation by inverting its single input, drawn as a triangle with a bubble at the output.

NOT Operation — The fundamental Boolean operation (logical negation) that inverts the input value, changing 0 to 1 and 1 to 0, denoted by an overbar, prime symbol, or the logical negation symbol.

Null Law (Dominance Law) — A Boolean identity stating that a variable operated with a dominant element returns the dominant element: \(A + 1 = 1\) and \(A \cdot 0 = 0\).

O

Operator Precedence — The defined order in which Boolean operations are evaluated: parentheses first, then NOT (highest), then AND, then OR (lowest), analogous to how multiplication precedes addition in ordinary algebra.

OR Gate — A basic logic gate that implements the OR operation, producing a HIGH output when any of its inputs is HIGH. Its standard symbol features a curved left edge and a pointed right edge.

OR Operation — The fundamental Boolean operation (logical disjunction) that produces a 1 output when at least one input is 1, denoted by a plus sign or the "vee" symbol, and analogous to addition in ordinary algebra.

P

Product of Sums (POS) — A standard Boolean expression form structured as an AND of OR terms (sum terms), mapping directly to an OR-AND two-level circuit implementation, preferred when the function has few 0-output rows.

Product Term — A single literal or an AND (product) of multiple literals in a Boolean expression, such as \(A\), \(AB\), or \(\overline{A}BC\).

Propagation Delay — The time required for a signal change at a gate's input to produce the corresponding change at its output, which accumulates through cascaded gate levels and determines the maximum operating speed of a circuit.

S

Standard Form — A Boolean expression written in one of two consistent representations — Sum of Products (SOP) or Product of Sums (POS) — that provide systematic starting points for circuit implementation and enable direct mapping to two-level gate structures.

Sum of Products (SOP) — A standard Boolean expression form structured as an OR of AND terms (product terms), mapping directly to an AND-OR two-level circuit implementation, preferred when the function has few 1-output rows.

Sum Term — A single literal or an OR (sum) of multiple literals in a Boolean expression, such as \(A\), \(A + B\), or \(\overline{A} + B + C\).

T

Tri-State Buffer — A buffer gate with an added enable (EN) control input that, when disabled, places the output in a high-impedance (Z) state, effectively disconnecting from the circuit to allow bus sharing.

Truth Table — A systematic tabular listing of all possible input combinations and their corresponding outputs for a Boolean function, containing \(2^n\) rows for \(n\) input variables.

U

Universal Gate — A single gate type (NAND or NOR) that is functionally complete, meaning any Boolean function can be implemented using only that gate type, which simplifies integrated circuit fabrication.

X

XNOR Gate — A derived logic gate (exclusive NOR) that produces a HIGH output when all inputs are the same (equality detector), expressed as \(F = \overline{A \oplus B} = AB + \overline{A}\,\overline{B}\).

XOR Gate — A derived logic gate (exclusive OR) that produces a HIGH output when inputs differ (odd number of 1s among inputs), expressed as \(F = A \oplus B = \overline{A}B + A\overline{B}\).