Truth Table

A truth table is a tabular representation of how the truth value of a logical expression depends on the values assigned to its variables. In classical propositional logic, each variable is either true or false, and the table includes every possible combination of these values. Truth tables provide an explicit account of logical meaning and a systematic method for testing expressions. They also describe the input–output behavior of digital circuits using Boolean algebra. (logical.stanford.edu)

Structure and construction

A table begins with columns for the distinct propositional variables, conventionally written $p,q,r,\ldots$. Each row represents a truth assignment, or valuation: an assignment of one truth value to every variable. Additional columns contain the values of component expressions and the complete formula. True and false may be written as T and F, or as 1 and 0. These symbols represent logical values rather than measured quantities. (logical.stanford.edu)

For $n$ distinct two-valued variables, there are $2^n$ assignments. A one-variable table therefore has two rows, a two-variable table four, and a three-variable table eight. Repeated occurrences of a variable receive the same value within a row; they do not create additional independent inputs. A common enumeration follows binary counting, although any ordering works if every assignment appears exactly once. (logical.stanford.edu)

To evaluate a compound formula, its syntactic structure must be respected. Parentheses determine which expressions are combined, and intermediate columns allow evaluation from the innermost components outward. For example, evaluating $(p\lor q)\land\neg p$ involves first computing $p\lor q$ and $\neg p$, then applying conjunction to those results. This illustrates the distinction between an expression’s written structure and its meaning under an assignment. (logic.stanford.edu)

Tables for basic connectives

A truth-functional connective produces an output determined entirely by its operands’ truth values. The following table displays several standard operations; T means true and F means false. (logic.stanford.edu)

Negation, $\neg p$, reverses a truth value. Conjunction, $p\land q$, is true only when both operands are true. Inclusive disjunction, $p\lor q$, is true when at least one operand is true, including when both are true. Exclusive OR, $p\oplus q$, instead requires exactly one true operand. (logic.stanford.edu)

Material implication, $p\to q$, is false only when $p$ is true and $q$ is false. In particular, it is true whenever its antecedent is false. The biconditional, $p\leftrightarrow q$, is true precisely when the operands have matching values. These definitions specify formal operations, not every nuance of conditional statements in ordinary language. (logic.stanford.edu)

Classification and equivalence

The final column classifies a formula according to its behavior across assignments:

• A tautology is true in every row.
• A contradiction is false in every row.
• A contingent formula is true in some rows and false in others.
• A formula is satisfiable if at least one row makes it true; both tautologies and contingent formulas are satisfiable. (logical.stanford.edu)

For example, $p\lor\neg p$ expresses the law of excluded middle and is a tautology under classical two-valued interpretation. By contrast, $p\land\neg p$ is a contradiction. Truth tables establish these classifications by exhaustive evaluation rather than by selecting particular examples. (logic.stanford.edu)

Two formulas are logically equivalent when their output columns agree in every row of a table containing all their variables. One of De Morgan’s laws states

Both sides are true only when $p$ and $q$ are false. Equivalent formulas can replace one another within propositional expressions without changing their truth values. (logical.stanford.edu)

Testing arguments

Truth tables test logical validity by checking whether an assignment makes every premise true while making the conclusion false. Such a row is a counterexample. If no counterexample exists, the premises logically entail the conclusion. This concerns truth preservation in deductive reasoning, not whether the premises accurately describe the world. (logic.stanford.edu)

For modus ponens, the premises are $p\to q$ and $p$, and the conclusion is $q$. The only assignment satisfying both premises also satisfies the conclusion. Thus the inference rule is valid. For finitely many premises, the same test can be expressed by asking whether the conditional from their conjunction to the conclusion is a tautology. (logic.stanford.edu)

Digital circuits and computational limits

In computer science and electrical engineering, truth tables specify logic gates and combinational circuits. Inputs and outputs are represented by bits, with 0 and 1 corresponding to false and true. Multiple output columns describe several Boolean functions of the same inputs. (ocw.mit.edu)

A table can be converted into a sum-of-products expression: construct a conjunction identifying each row with output 1, then disjoin those conjunctions. This gives a systematic circuit implementation using NOT, AND, and OR. A Karnaugh map rearranges table entries to expose opportunities for simplifying such expressions. (ocw.mit.edu)

The exhaustive method has an important computational limitation: its row count grows exponentially. Truth-table enumeration is a straightforward algorithm for the Boolean satisfiability problem, but large formulas require methods that avoid explicitly processing every assignment. The table describes logical input–output behavior; circuit timing, including propagation delays and transient glitches, requires additional analysis. (worksheets.stanford.edu)