Truth Table Solver
Enter a logical expression using variables (p, q, r, s) and operators. The solver generates a complete truth table for all variable combinations, evaluates sub-expressions, and classifies the result as a tautology, contradiction, or contingency.
Insert operators:
Quick examples:
p AND q p OR NOT p q) & (q -> p)')" style="font-size:13px">Biconditional equiv. (!p | !q)')" style="font-size:13px">De Morgan's Law q) <-> (!q -> !p)')" style="font-size:13px">Contrapositive Complete DNFWhat Are Truth Tables
A truth table is a structured mathematical tool that enumerates every possible combination of truth values for the variables in a logical expression and computes the resulting truth value for each combination. If an expression contains n distinct variables, the truth table has 2 raised to the power of n rows, because each variable can independently be either true or false.
Truth tables were formalized by Ludwig Wittgenstein in his 1921 work Tractatus Logico-Philosophicus and independently by Emil Post in 1921. They provide a mechanical, algorithmic method for determining the logical properties of any proposition in propositional logic. Before truth tables, verifying logical arguments required informal reasoning that was prone to errors, especially for complex expressions with many variables.
The power of truth tables lies in their exhaustiveness. By considering every possible combination of inputs, a truth table proves properties with certainty. If the output column contains only true values, the expression is a tautology. If it contains only false values, the expression is a contradiction. If it contains a mix, the expression is a contingency. This classification is definitive because no combinations have been overlooked.
In computer science education, truth tables serve as the bridge between abstract logic and concrete computation. They map directly to the behavior of combinational logic circuits, the truth conditions of if-else statements, and the semantics of database query predicates. A student who can construct a truth table can verify any Boolean expression in any programming language.
Logical Operators Explained
NOT (Negation)
The NOT operator is a unary operator that inverts the truth value of its operand. If p is true, NOT p is false. If p is false, NOT p is true. In this tool, you can write NOT as ! or the symbol ¬. NOT has the highest precedence among all logical operators, meaning it binds more tightly than any binary operator.
| p | NOT p |
|---|---|
| T | F |
| F | T |
AND (Conjunction)
AND is a binary operator that returns true only when both operands are true. In all other cases, it returns false. AND corresponds to the English word "and" in its strictest sense: both conditions must hold. Write it as & or the symbol ∧. In programming, the logical AND operator (&&) follows the same semantics.
| p | q | p AND q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
OR (Disjunction)
OR returns true when at least one operand is true. It is the inclusive disjunction, meaning it also returns true when both operands are true. Write it as | or the symbol ∨. This differs from everyday English "or," which often implies exclusivity ("soup or salad" typically means one but not both). Logical OR includes the both-true case.
| p | q | p OR q |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
XOR (Exclusive Or)
XOR returns true when exactly one operand is true and the other is false. When both are true or both are false, XOR returns false. Write it as ^ or the symbol ⊕. XOR captures the everyday sense of "one or the other but not both." In binary arithmetic, XOR is equivalent to addition modulo 2.
IMPLIES (Material Conditional)
IMPLIES (p -> q) is false only when p is true and q is false. In all other cases, including when p is false, the implication is true. This definition, called the material conditional, surprises many students because a false premise makes the entire implication vacuously true. Write it as -> or the symbol →.
The implication "If it rains, then the ground is wet" is false only when it does rain and the ground is not wet. If it does not rain, the statement is considered true regardless of the ground's condition. This convention ensures that IMPLIES behaves consistently in formal logic systems.
BICONDITIONAL (If and Only If)
The BICONDITIONAL (p <-> q) returns true when both operands have the same truth value: both true or both false. It is equivalent to (p -> q) AND (q -> p). Write it as <-> or the symbol ↔. In mathematics, "if and only if" (abbreviated iff) is one of the most important connectives for stating precise definitions and theorems.
Tautology, Contradiction, and Contingency
Every logical expression falls into exactly one of three categories based on its truth table output.
Tautology
A tautology is an expression that is true under every possible assignment of truth values to its variables. The classic example is p OR NOT p (the law of excluded middle). No matter whether p is true or false, the disjunction of p with its negation is always true. Other tautologies include (p IMPLIES q) OR (q IMPLIES p) and ((p IMPLIES q) AND p) IMPLIES q (modus ponens).
Tautologies are the logical truths of propositional logic. They cannot be falsified by any interpretation. In formal proof systems, tautologies can be derived from axioms using only the rules of inference, and every theorem of propositional logic is a tautology.
Contradiction
A contradiction is an expression that is false under every possible assignment. The classic example is p AND NOT p. A variable cannot be simultaneously true and false, so this conjunction always fails. The negation of any tautology is a contradiction, and vice versa.
Contradictions are important in proof by contradiction (reductio ad absurdum). If assuming a statement leads to a contradiction, the assumption must be false. This proof technique is one of the most powerful tools in mathematics and is also used in automated theorem proving.
Contingency
A contingency is an expression that is true for some assignments and false for others. Most practical expressions are contingencies. For example, p AND q is true only when both p and q are true and false in all other cases. Contingencies are neither logically necessary nor logically impossible. Their truth value depends on the actual state of affairs.
De Morgan's Laws
De Morgan's laws are two fundamental equivalences that relate AND, OR, and NOT. They are named after Augustus De Morgan, a 19th-century British mathematician.
The first law states: NOT (p AND q) is equivalent to (NOT p) OR (NOT q). Negating a conjunction converts it to a disjunction of the negated operands. In everyday language: "It is not the case that both A and B are true" means the same as "Either A is false, or B is false, or both."
The second law states: NOT (p OR q) is equivalent to (NOT p) AND (NOT q). Negating a disjunction converts it to a conjunction of the negated operands. "It is not the case that A or B is true" means "Both A is false and B is false."
You can verify both laws by generating truth tables. Enter !(p & q) <-> (!p | !q) into this solver. The result will be a tautology, confirming the equivalence. Similarly, !(p | q) <-> (!p & !q) will also be a tautology.
De Morgan's laws extend to more than two operands. NOT (p AND q AND r) is equivalent to (NOT p) OR (NOT q) OR (NOT r). This generalization is essential in digital circuit design, where it allows engineers to convert between AND-gate and OR-gate implementations, optimizing circuits for available components.
Logical Equivalence
Two logical expressions are logically equivalent if they produce the same truth value for every possible assignment of truth values to their variables. In other words, their truth tables have identical output columns. Logical equivalence is denoted by the biconditional symbol (p <-> q), and you can verify equivalence by checking whether the biconditional of two expressions is a tautology.
Several important equivalences are used routinely in logic:
- Double Negation: NOT NOT p is equivalent to p
- Commutativity: p AND q is equivalent to q AND p, and p OR q is equivalent to q OR p
- Associativity: (p AND q) AND r is equivalent to p AND (q AND r)
- Distributivity: p AND (q OR r) is equivalent to (p AND q) OR (p AND r)
- Absorption: p AND (p OR q) is equivalent to p
- Contrapositive: (p IMPLIES q) is equivalent to (NOT q IMPLIES NOT p)
- Material implication: (p IMPLIES q) is equivalent to (NOT p) OR q
Each of these equivalences can be verified using this truth table solver. Enter the biconditional of both sides and confirm that the result is a tautology. This provides a concrete, computational proof of the equivalence.
Truth Tables in Digital Circuit Design
Every combinational logic circuit can be fully described by a truth table. The inputs are the circuit's input signals (each either 0 or 1), and the output column specifies the circuit's output for every input combination. This direct correspondence makes truth tables the standard starting point for circuit design.
The design process typically follows these steps. First, specify the desired behavior as a truth table. Second, derive a Boolean expression from the truth table using either sum-of-products (SOP) or product-of-sums (POS) form. Third, simplify the expression using Boolean algebra, Karnaugh maps, or the Quine-McCluskey algorithm. Fourth, implement the simplified expression using logic gates (AND, OR, NOT, NAND, NOR).
For example, a 2-input multiplexer has three inputs (two data inputs and one select line) and one output. The truth table defines the output as equal to the first data input when the select line is 0, and equal to the second data input when the select line is 1. From this truth table, the Boolean expression is derived and then implemented in hardware.
NAND and NOR gates are called universal gates because any Boolean function can be implemented using only NAND gates or only NOR gates. De Morgan's laws provide the theoretical basis for this universality, and truth tables verify that the NAND-only or NOR-only implementation produces the same output as the original design.
Propositional Logic in Computer Science
Propositional logic underpins multiple areas of computer science. In programming, every if-else statement evaluates a Boolean expression that can be analyzed with a truth table. Complex conditional logic with multiple AND, OR, and NOT operators is easier to debug and optimize when you can see the complete truth table.
Database query languages like SQL use Boolean logic in WHERE clauses. A query like SELECT * FROM orders WHERE status = 'shipped' AND (total > 100 OR priority = 'high') evaluates a propositional expression for each row. Understanding how AND and OR interact, including operator precedence and the effect of parentheses, directly determines which rows the query returns.
In formal verification, truth tables (and their generalization, Binary Decision Diagrams) are used to verify that hardware designs and software implementations satisfy their specifications. Model checking tools explore all possible states of a system, which is analogous to generating a truth table over the state variables.
SAT solvers, which determine whether a Boolean formula has a satisfying assignment, are among the most important tools in modern computer science. They power applications ranging from chip verification to scheduling to cryptanalysis. While practical SAT solvers use sophisticated heuristics rather than exhaustive truth table enumeration, the theoretical foundation is the same: finding an assignment of variables that makes an expression true.
Type systems in programming languages also draw on propositional logic. The Curry-Howard correspondence establishes a deep connection between logical propositions and types: a type is "inhabited" (has values) if and only if the corresponding proposition is provable. This correspondence drives the design of typed functional languages and proof assistants like Coq and Agda.
Operator Precedence
When an expression contains multiple operators without parentheses, precedence rules determine the order of evaluation. This solver follows the standard precedence from highest (evaluated first) to lowest (evaluated last):
- NOT (!) - highest precedence, unary
- AND (&)
- OR (|) and XOR (^)
- IMPLIES (->)
- BICONDITIONAL (<->) - lowest precedence
For example, the expression p | q & r is evaluated as p | (q & r) because AND has higher precedence than OR. If you intend (p | q) & r, you must use parentheses. When in doubt, always use parentheses to make your intended grouping explicit. Parenthesized expressions are unambiguous regardless of precedence rules.
IMPLIES is right-associative, meaning p -> q -> r is parsed as p -> (q -> r), not (p -> q) -> r. BICONDITIONAL, AND, and OR are left-associative. These conventions match standard usage in mathematical logic textbooks.
