Propositional logic underpins formal reasoning in computing: conditions in if statements, queries, digital circuits, program verification. It is simple, provided you start from the definitions rather than from the intuitions of everyday language, which often mislead.
What a proposition is
A proposition is a statement that can be true or false, but not both. "7 is a prime number" is a proposition (a true one). "The file is larger than 2 MB" is a proposition once the file is fixed. "Close the door" is not: it is a command and has no truth value.
Elementary propositions are written with letters: p, q, r. Combining them with connectives gives compound propositions whose value depends only on the values of their parts.
The basic connectives
| 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 | except when p is true and q false |
| Biconditional | p ↔ q | p if and only if q | p and q have the same value |
Two points deserve attention.
Logical "or" is inclusive
In everyday speech "tea or coffee?" suggests an exclusive choice. In logic, p ∨ q is true even when both p and q are true. If you need the exclusive version you use a separate connective, XOR (p ⊕ q), which is true when exactly one of the two is true.
An implication with a false premise is true
p → q is false in only one case: p true and q false. If the premise is false, the implication is true whatever q is. It sounds odd, but think of a promise: "if it rains, I'll lend you my umbrella". If it doesn't rain, I haven't broken the promise, whatever I do. This convention, called material implication, is what keeps the whole system consistent.
Building a truth table
A truth table lists every combination of values of the variables and, for each one, the value of the formula. With n variables there are 2ⁿ rows: 4 rows with two variables, 8 with three, 16 with four.
An orderly method so you never miss a row:
- Write the variables as columns from left to right.
- In the rightmost column alternate T and F row by row; in the previous one, in pairs; in the one before that, in groups of four, and so on. It is the same pattern as counting in binary.
- Add a column for each subformula, from the innermost to the outermost.
- Compute each column using only columns already filled in.
Example with the formula (p → q) ∧ ¬q:
| p | q | p → q | ¬q | (p → q) ∧ ¬q |
|---|---|---|---|---|
| T | T | T | F | F |
| T | F | F | T | F |
| F | T | T | F | F |
| F | F | T | T | T |
The formula is true only when p and q are both false. Notice that whenever the formula is true, ¬p is true as well: that is the basis of the inference rule called modus tollens.
Tautologies, contradictions, satisfiable formulas
The last column of a table classifies a formula:
- Tautology: true in every row. Example: p ∨ ¬p.
- Contradiction: false in every row. Example: p ∧ ¬p.
- Satisfiable: true in at least one row. The formula in the example above is satisfiable but not a tautology.
Two formulas are logically equivalent when they have the same final column. For instance p → q is equivalent to ¬p ∨ q, and this equivalence is extremely useful for simplifying conditions in code.
Precedence of connectives
To avoid parentheses everywhere, the usual precedence, from strongest to weakest, is: ¬, ∧, ∨, →, ↔. So ¬p ∧ q ∨ r reads as ((¬p) ∧ q) ∨ r. By convention, implication associates to the right: p → q → r means p → (q → r). When I write complex conditions in my own work I still prefer to add parentheses: they cost little and remove any doubt for the reader.
Where it is used in practice
- Programming: simplifying a condition with many
&&and||, checking that two versions of a test are equivalent, writing tests that cover every combination. - Databases: WHERE clauses are logical formulas; understanding negation prevents filters that exclude rows by mistake.
- Circuits: every logic gate implements a connective; a truth table is literally the specification of a combinational circuit.
The limit of truth tables is exponential growth: with 20 variables there are more than a million rows. For large formulas we use algebraic transformations and SAT solvers.
In short
- A proposition is a statement that is true or false; connectives combine propositions looking only at truth values.
- Disjunction is inclusive, and an implication with a false premise is always true.
- With n variables a truth table has 2ⁿ rows: fill it in using the binary counting pattern.
- Tautologies, contradictions and equivalences are recognised by comparing final columns.
- The same rules govern conditions in code, queries and circuits.
