Propositional Logic Explained: Connectives, Equivalences and Inference
Last updated · Part of the Discretiq guides
Propositional logic studies statements that are either true or false and the ways of combining them. It is the foundation of mathematical proof, digital circuits and programming conditions.
This guide covers the vocabulary, the connectives, the equivalences you will use most, and how to tell a valid argument from a fallacy.
Statements and connectives
A proposition is a sentence that is definitely true or definitely false, such as '7 is prime'. Questions and commands are not propositions. Letters such as P and Q stand for propositions, and connectives build new ones.
| Connective | Symbol | Read as | True when |
|---|---|---|---|
| Negation | ¬P | not P | P is false |
| Conjunction | P ∧ Q | P and Q | both are true |
| Disjunction | P ∨ Q | P or Q | at least one is true |
| Implication | P → Q | if P then Q | not (P true and Q false) |
| Biconditional | P ↔ Q | P if and only if Q | P and Q have the same value |
The implication is the one that surprises people: P → Q is true whenever P is false. 'If the moon is cheese, then 2 + 2 = 5' is a true implication in logic, because its condition is false.
Converse, inverse and contrapositive
Start from 'If it rains, the ground is wet' (P → Q). Its relatives are:
- Converse: Q → P, 'if the ground is wet, it rained'.
- Inverse: ¬P → ¬Q, 'if it does not rain, the ground is not wet'.
- Contrapositive: ¬Q → ¬P, 'if the ground is not wet, it did not rain'.
| P | Q | P → Q | Q → P | ¬P → ¬Q | ¬Q → ¬P |
|---|---|---|---|---|---|
| T | T | T | T | T | T |
| T | F | F | T | T | F |
| F | T | T | F | F | T |
| F | F | T | T | T | T |
The columns for P → Q and ¬Q → ¬P match, so an implication is equivalent to its contrapositive. The converse and inverse match each other, but not the original. A wet ground does not prove it rained: a sprinkler could have been running.
Equivalences worth memorising
- De Morgan: ¬(P ∧ Q) ≡ ¬P ∨ ¬Q and ¬(P ∨ Q) ≡ ¬P ∧ ¬Q.
- Implication as disjunction: P → Q ≡ ¬P ∨ Q.
- Double negation: ¬¬P ≡ P.
- Biconditional: P ↔ Q ≡ (P → Q) ∧ (Q → P).
- Absorption: P ∧ (P ∨ Q) ≡ P.
Two formulas are logically equivalent when their truth tables have identical final columns.
Tautologies, contradictions and contingencies
- A tautology is true in every row, such as P ∨ ¬P.
- A contradiction is false in every row, such as P ∧ ¬P.
- A contingency is true in some rows and false in others, such as P → Q.
Valid arguments and common fallacies
An argument form is valid when its premises together imply the conclusion in every row. Checking this means testing whether the combined implication is a tautology.
| Argument form | Formula | Result |
|---|---|---|
| Modus ponens: P → Q, P, therefore Q | ((P → Q) ∧ P) → Q | Tautology (valid) |
| Modus tollens: P → Q, ¬Q, therefore ¬P | ((P → Q) ∧ ¬Q) → ¬P | Tautology (valid) |
| Affirming the consequent: P → Q, Q, therefore P | ((P → Q) ∧ Q) → P | Not a tautology (fallacy) |
Affirming the consequent fails in the row where P is false and Q is true: both premises are true but the conclusion is false.
Common mistakes
- Reading 'or' as exclusive. In logic P ∨ Q is true when both are true.
- Treating P → Q as meaning the same as Q → P.
- Thinking an implication with a false condition is false. It is vacuously true.
- Distributing a negation without flipping ∧ and ∨ (De Morgan).
- Dropping brackets. In P ∨ Q ∧ R, ∧ binds tighter, so brackets are safer.
Frequently asked questions
What is the difference between propositional and predicate logic?
Propositional logic treats whole statements as atoms. Predicate logic looks inside statements and adds variables and the quantifiers ∀ (for all) and ∃ (there exists).
How many rows does a truth table have?
2ⁿ rows for n variables, so 8 rows for three variables.
Is P → Q the same as ¬P ∨ Q?
Yes. They have identical truth tables, which is a standard way to remove implications from a formula.
Try it yourself
Work the examples above by hand first, then confirm your answers.
Test your own formulas with the free propositional logic calculatorReferences and further reading
- Rosen, K. H. Discrete Mathematics and Its Applications. McGraw-Hill (standard undergraduate text).
- Enderton, H. B. A Mathematical Introduction to Logic. Academic Press.