Visual Tools
Calculators
Tables
Mathematical Keyboard
Converters
Other Tools

How to Check Whether a Formula Is a Contradiction

A contradiction is false in every row of its truth table: no assignment makes it true. Prove it by checking all rows or by reducing it to ⊥\bot; disprove it by finding a single row where it is T.

Recognize the task

The question asks "is this a contradiction", "is this unsatisfiable", "can these statements all be true", or whether a set of premises is consistent: P↔¬PP \leftrightarrow \neg P, (P∨Q)∧¬P∧¬Q(P \lor Q) \land \neg P \land \neg Q, (P∧Q)∧(¬P∨¬Q)(P \land Q) \land (\neg P \lor \neg Q). Test: several conditions are joined by ∧\land and seem to fight each other.
Contradictions are defined in what is a contradiction; the contradiction lesson covers them in depth.

Ways to do it

Full truth tableusual
all 2n rows are F\text{all } 2^n \text{ rows are F}
Build the table and scan the final column; a single T row ends the check.
Reduce to a clashlaws
A∧¬A≡⊥A \land \neg A \equiv \bot
Rewrite until a part and its negation are joined by ∧\land, then use the law of non-contradiction.
Negate and test for a tautologydual
A≡⊥  ⟺  ¬A≡⊤A \equiv \bot \iff \neg A \equiv \top
A formula is a contradiction exactly when its negation is a tautology; then use checking for a tautology.

Steps

StepOn (P∨Q)∧¬P∧¬Q(P \lor Q) \land \neg P \land \neg Q
1Set up the rows. List all 2n2^n assignments as in building a truth table.2 letters, 4 rows
2Evaluate the parts. Fill one column for each part joined by ∧\land.P∨QP \lor Q: T, T, T, F; ¬P\neg P: F, F, T, T; ¬Q\neg Q: F, T, F, T
3Combine with the main connective. A conjunction is T only in a row where every part is T. Look for such a row.no row has all three parts T: F, F, F, F
4Read the verdict. All F: a contradiction. Any T: the formula is satisfiable, and that row is the witness to report.all four rows F: a contradiction

Worked examples

Example 1 · a self-denying biconditional

1 letter
P=TP = T: T↔FT \leftrightarrow F is F
the sides differ
P=FP = F: F↔TF \leftrightarrow T is F
the sides differ
P↔¬PP \leftrightarrow \neg P is a contradiction
both rows are F

Example 2 · exclusive or

satisfiable
(P∧¬Q)∨(¬P∧Q)(P \land \neg Q) \lor (\neg P \land Q): F, T, T, F
T when exactly one is T
not a contradiction: P=TP = T, Q=FQ = F
one T row is a witness

Example 3 · by the laws

no table
(P∧Q)∧(¬P∨¬Q)(P \land Q) \land (\neg P \lor \neg Q)
start
≡(P∧Q)∧¬(P∧Q)\equiv (P \land Q) \land \neg(P \land Q)
De Morgan, read backward
≡⊥\equiv \bot
a part and its negation
The proposition analyzer labels a formula Contradiction when its whole column is F.

See it happen

Think of each part of a conjunction as a filter on the rows. P∨QP \lor Q throws away the row where both letters are F; ¬P\neg P throws away the rows where PP is T; ¬Q\neg Q throws away the rows where QQ is T. A contradiction is a set of filters that together throw away every row. In the Venn diagram and truth table tool this shows up as a shaded region that ends up empty.

Common mistakes

Judging from a single row

✗ P∧¬QP \land \neg Q is F at P=Q=TP = Q = T, so it is a contradiction
✓ at P=TP = T, Q=FQ = F it is T, so it is satisfiable

Pushing the negation in without flipping the connective

✗ in (P∧Q)∧(¬P∨¬Q)(P \land Q) \land (\neg P \lor \neg Q), write ¬P∨¬Q\neg P \lor \neg Q as ¬(P∨Q)\neg(P \lor Q)
✓ ¬P∨¬Q≡¬(P∧Q)\neg P \lor \neg Q \equiv \neg(P \land Q), which clashes with P∧QP \land Q

Joining a contradiction with or

✗ (P∧¬P)∨Q≡⊥(P \land \neg P) \lor Q \equiv \bot
✓ (P∧¬P)∨Q≡⊥∨Q≡Q(P \land \neg P) \lor Q \equiv \bot \lor Q \equiv Q

Negating a formula that is not a tautology

✗ P→QP \to Q is not a tautology, so ¬(P→Q)\neg(P \to Q) is a contradiction
✓ ¬(P→Q)≡P∧¬Q\neg(P \to Q) \equiv P \land \neg Q is T at P=TP = T, Q=FQ = F