What a truth table actually settles
A truth table is an exhaustive proof by cases. Classical propositional logic makes one strong assumption — every proposition is either true or false, with nothing in between — and that assumption turns any question about a formula into a finite search. If a formula has n distinct variables, there are exactly 2n ways to assign truth values to them, and checking all of them settles the question completely.
Three verdicts are possible, and they are the three this calculator reports. A tautology is true in every row: it says nothing about the world, which is precisely why it is useful as a law of logic. A contradiction is true in no row; its negation is a tautology. A contingency is true in some rows and false in others, which means its truth depends on facts the formula alone does not settle.
Two further questions reduce to the same table. Two formulas are logically equivalent exactly when the biconditional joining them is a tautology, so you can test the equivalence of A and B by entering A <-> B and looking for a tautology verdict. An argument with premises P₁…Pk and conclusion C is valid exactly when (P1 AND P2 AND … ) -> C is a tautology. One tool, three jobs.
How each connective is defined, and why implication looks wrong
Each connective is a function from truth values to truth values, and the table below is its complete definition. Negation flips a value. Conjunction is true only when both parts are true. Disjunction in logic is inclusive: p ∨ q is true when both hold, unlike the everyday "or" that often means one or the other. Exclusive-or is the connective that captures the everyday sense, and it is true exactly when the two operands differ.
Material implication is where nearly every student stops and objects. p → q is false in exactly one row — p true and q false — and true in the other three, including both rows where p is false. So "if the moon is cheese then 2 + 2 = 5" comes out true. That feels wrong because natural-language conditionals carry a claim of relevance that the truth-functional connective does not.
The reason logic keeps this definition is that it is the only truth-functional connective that never lets you infer a falsehood from truths. A conditional must be false when the antecedent holds and the consequent fails; if it were also false in some row where the antecedent fails, then p → q would depend on facts irrelevant to the inference, and the rule of modus ponens would stop being sound. The equivalence p → q ≡ ¬p ∨ q is the compact way to remember the whole table: the conditional asserts only that you do not get p without q.
The biconditional is the conjunction of both directions, so it is true exactly when the two sides agree. NAND and NOR are the negations of conjunction and disjunction; each on its own is functionally complete, meaning every connective can be rebuilt from it alone, which is why physical gate libraries are built around them. If you want the minimal gate expression rather than the table, use the Boolean algebra simplification calculator.
Worked example: is (p ∧ q) → (p ∨ q) a tautology?
Two variables give 2² = 4 rows. Work outward from the innermost sub-formulas, one column at a time, exactly as the calculator does.
- List the rows. With p and q in that order the assignments are TT, TF, FT, FF.
- Column for p ∧ q. True only when both are true: T, F, F, F.
- Column for p ∨ q. True unless both are false: T, T, T, F.
- Column for the whole conditional. Apply the implication table to the two columns you just built, row by row. Row 1: T → T = T. Row 2: F → T = T. Row 3: F → T = T. Row 4: F → F = T.
- Read the verdict. All four rows are true, so the formula is a tautology: 4 true rows out of 4.
Now change one symbol and redo it. For (p ∨ q) → (p ∧ q), the antecedent column is T, T, T, F and the consequent is T, F, F, F. Row by row: T → T = T, T → F = F, T → F = F, F → F = T. Two rows out of four are true, so this is a contingency, not a tautology. The falsifying rows are exactly TF and FT — the rows where p and q disagree, which is the same set of rows where p ⊕ q is true. Swapping the antecedent and consequent of a conditional is not a valid move, and the table shows you precisely where it breaks.
How to read the verdict, and what to do next
Read the classification first, then the count. Tautology means the formula is a law: it holds under every interpretation, so it can be added to a proof at any point. If you built the formula as premises -> conclusion, a tautology verdict is a proof that the argument is valid.
Contradiction means the formula is unsatisfiable. If you built it as the conjunction of a set of constraints, that verdict tells you the constraints cannot all hold at once — and it is the same question a SAT solver answers, just settled by brute force instead of by search. Contingency means the formula is satisfiable but not valid; the satisfying assignments the calculator lists are exactly the models you can use as a witness.
The count of true rows carries extra information. A formula over n variables with t true rows corresponds to a Boolean function with t minterms, and the ratio t / 2n is sometimes called the density of the function. A formula that is true in exactly half its rows is balanced — negation, exclusive-or and the identity function are all balanced, and so is any formula equivalent to a single literal.
If your verdict is contingency but you expected a tautology, find the first false row and read the variable assignment across it. That single row is a counter-example, and it is normally enough to see which step of your reasoning failed. This is why the sub-formula columns matter: the row tells you the assignment, and the columns tell you which sub-formula first went the wrong way.
The complete truth tables for every connective this calculator accepts
| p | q | ¬p | p ∧ q | p ∨ q | p ⊕ q | p → q | p ↔ q | p ↑ q (NAND) | p ↓ q (NOR) |
|---|---|---|---|---|---|---|---|---|---|
| T | T | F | T | T | F | T | T | F | F |
| T | F | F | F | T | T | F | F | T | F |
| F | T | T | F | T | T | T | F | T | F |
| F | F | T | F | F | F | T | T | T | T |
Memorise two rows and derive the rest: conjunction is true only in the first row, disjunction is false only in the last, and implication is false only in the second.
Precedence, brackets and the errors they cause
This calculator binds the connectives in the conventional order, tightest first: ¬, then ∧ and NAND, then ⊕, then ∨ and NOR, then →, then ↔. Implication associates to the right, so p -> q -> r parses as p → (q → r); the other binary connectives associate to the left. The Formula as parsed output shows you exactly how your input was grouped, and you should read it before you trust the table.
Precedence is where most disagreements between a hand-drawn table and a generated one come from. NOT p AND q parses as (¬p) ∧ q, not as ¬(p ∧ q), and those two formulas differ in two of the four rows. Textbooks vary on where exclusive-or sits, and some place it at the same level as disjunction. If your source uses a different convention, add brackets — an over-bracketed formula is never ambiguous, and it costs you nothing.
A second common source of mismatch is variable naming. P and p are different variables here, so P OR NOT p has four rows and is a contingency, while p OR NOT p has two rows and is a tautology. Variables are listed in alphabetical order in the table, which is why the columns may not appear in the order you typed them.
Mistakes that make a hand-built table disagree with this one
- Reading implication backwards.
p → qis false only in the row where p is true and q is false. If your column has two Fs, you have probably built the biconditional instead. - Treating ∨ as exclusive. Logical disjunction is true when both disjuncts hold. Use XOR when you mean one or the other but not both.
- Dropping brackets around a negated compound.
NOT p AND qandNOT (p AND q)agree only in the two rows where q is false. - Skipping a row. With n variables you need exactly 2n rows: 8 for three variables, 16 for four. A table with 6 rows for three variables is missing two cases and can report a false tautology.
- Reusing a variable letter for two different propositions. Each distinct letter gets its own column, and each occurrence of the same letter must take the same value in a row.
- Assuming a tautology in one direction gives you the other.
(p ∧ q) → (p ∨ q)is valid; the converse is not. Test both directions separately, or test the biconditional.
What truth tables cannot do, and what to use instead
The method is complete for propositional logic and useless beyond it. A truth table cannot evaluate quantifiers: "every prime greater than two is odd" has no finite table because it ranges over an infinite domain, and deciding it needs first-order proof methods, not enumeration. Nor can it handle modal operators, probabilities, or any many-valued logic in which a proposition can be other than true or false.
The cost is the other limit. The table doubles with each variable: 10 variables give 1,024 rows, 20 give more than a million, and 40 give more than a trillion. That growth is why this calculator stops at six variables and why real satisfiability problems are attacked with DPLL and CDCL solvers, which prune the search rather than enumerating it. Deciding satisfiability of a propositional formula is the original NP-complete problem, so no method is known that avoids exponential worst-case behaviour — see the Big-O growth comparison calculator for how 2n compares with the growth rates you meet elsewhere.
For the related engineering questions there are better tools than a table. To turn a table into the cheapest two-level circuit, use a Karnaugh map solver, which is the graphical form of the same enumeration. To reason about collections rather than propositions, the algebra is the same but the objects are different — the set operations calculator applies the identical De Morgan laws to unions and intersections. And when your propositions describe steps of a recursive process rather than a fixed circuit, the linear recurrence relation calculator is the right instrument.
Key terms
- Valuation (assignment)
- One complete choice of truth value for every variable — that is, one row of the table.
- Tautology
- A formula true under every valuation. Also called logically valid. Its negation is a contradiction.
- Satisfiable
- True under at least one valuation. Every tautology and every contingency is satisfiable; contradictions are not.
- Logical equivalence
- Two formulas have identical columns in every row. Equivalently, the biconditional joining them is a tautology.
- Functional completeness
- A set of connectives from which every truth function can be built. {¬, ∧} is complete; so is {NAND} on its own, and so is {NOR}.
- Minterm
- A row in which the formula is true, written as a conjunction of literals. The count of minterms is the true-row count this calculator reports.