Ch 6. Key Terms

AND gate: A basic logic gate that outputs 1 only if both inputs are 1.

Boolean algebra: A formal system on a set [latex]B[/latex] with binary operations [latex]+[/latex] and [latex]\cdot[/latex], a unary operation (complement), and distinguished elements [latex]0[/latex] and [latex]1[/latex], satisfying closure, commutativity, associativity, distributivity, identity, and complement axioms.

Boolean expression: A formula composed of variables (literals) and logical operators (AND, OR, NOT), where each literal represents a binary input (0 or 1).

Boolean function: A mapping [latex]f: \{ 0, 1 \} \times \{ 0, 1 \} \times \cdots \{ 0, 1 \} \rightarrow \{ 0, 1 \}[/latex] assigning a binary output to each combination of [latex]n[/latex] binary inputs.

Combinatorial circuit: A digital logic circuit whose output is determined solely by the current input values.

Circuit synthesis: The process of converting a Boolean function into a logic circuit using gates.

Dual (duality principle): The transformation obtained by swapping AND with OR, OR with AND, 0 with 1, and 1 with 0.

Equal (Boolean expressions): Two Boolean expressions are equal if they produce the same output for every combination of inputs.

Equivalent (circuits): Two combinatorial circuits are equivalent if they compute the same Boolean function, even if their internal structure differs.

Exclusive OR (XOR): The function that outputs 1 when the inputs differ.

Literal: A Boolean variable or its complement used as a basic factor in expressions.

Maxterm: An OR of literals corresponding to a row where a function is 0 in a truth table; used to form a POS expression.

Minterm: An AND of literals corresponding to a row where a function is 1 in a truth table; used to form an SOP expression.

Multi-input AND/OR gate: An AND gate that outputs 1 only if all inputs are 1, or an OR gate that outputs 1 if at least one input is 1; used to simplify circuits with many conditions.

NOT gate: A gate that outputs the inverse of its input.

OR gate: A basic logic gate that outputs 1 if at least one input is 1.

POS (Product of Sums): A conjunction (AND) of maxterms (ORs of literals) derived from the rows where a function is 0.

SOP (Sum of Products): A disjunction (OR) of minterms (ANDs of literals) derived from the rows where a function is 1.

Truth table: A table listing all input combinations and the corresponding output for a Boolean function or gate.