Propositional logic
The logic of statements that are either true or false, and of the words that join them: not, and, or, if-then and if and only if. It is what a logic or discrete maths course starts with, and it is the same algebra that logic gates compute.
Tools: truth table calculator for logic statements, which also checks arguments, and the logical equivalence calculator.
Propositions and statements
A proposition (or statement) is a sentence that is either true or false, not both. "Paris is in France" is a true proposition and "7 is even" is a false one. "Close the door" and "Is it raining?" are not propositions, since neither is true or false, and nor is "x is even" until you know what x is.
Propositional logic does not look inside a proposition. It names each one with a letter, usually p, q and r, and cares only about its truth value: true (T) or false (F). A letter on its own is an atomic statement. Joining statements with connectives gives compound statements such as p ∧ ¬q, and the truth value of a compound statement is fixed completely by the truth values of its letters. That is why a truth table, which lists every combination, can answer every question in propositional logic.
Logic symbols and how to read them
Five connectives appear in every textbook, and exclusive or joins them in computing. Books and keyboards write them in several ways, and the calculator accepts every alternative listed. Some books also write p ∧ q as pq; the calculator needs the symbol, since it reads each letter as its own statement. The last column is each connective's truth table, rows from all true down, computed rather than typed.
| Symbol | Name | Read as | Also written | Truth values |
|---|---|---|---|---|
| ¬ | Negation | not p | ~p, !p, p̄, −p, NOT p | FT |
| ∧ | Conjunction | p and q | p & q, p · q, p AND q | TFFF |
| ∨ | Disjunction | p or q (or both) | p v q, p + q, p OR q | TTTF |
| ⊕ | Exclusive or | p or q, but not both | p ⊻ q, p ↮ q, p XOR q | FTTF |
| → | Conditional (implication) | if p then q; p implies q | p ⊃ q, p ⇒ q | TFTT |
| ↔ | Biconditional | p if and only if q | p ≡ q, p ⇔ q, p iff q | TFFT |
For two letters the four values are for p, q = TT, TF, FT, FF; for ¬p they are for p = T, F. Select a column to open its full truth table.
Other symbols you will meet
| Symbol | Name | Meaning |
|---|---|---|
| ⊤ | Top, verum | A statement that is always true. Also written T or 1. |
| ⊥ | Bottom, falsum | A statement that is always false. Also written F or 0. |
| ∴ | Therefore | Marks the conclusion of an argument. |
| ≡ | Logically equivalent | Written between two statements with the same truth table, as in p → q ≡ ¬p ∨ q. Some books write ⇔. |
| ⊨ | Entails | The premises on the left make the conclusion on the right true in every row: the argument is valid. |
| ⊢ | Proves | The conclusion can be derived from the premises with the rules of a proof system. |
≡ and ⊨ are not connectives: they are statements about statements. p ↔ q is a statement that can be true or false; p ≡ q is the claim that p ↔ q is true in every row.
Printable logic symbols chart
The connectives, how to read them, their other notations and their truth values on one sheet, for printing or revision.
Click to download: Logic symbols chart
Order of operations
Like × before + in arithmetic, the connectives have an order that saves brackets. ¬ binds tightest, then ∧, then ∨, then →, and ↔ binds loosest. A chain of → groups to the right. Books differ on where ⊕ sits, so it is safest to bracket it; here it sits between ∧ and ∨. When in doubt, write the brackets.
| Written | Means |
|---|---|
| ¬p ∨ q → r | (¬p ∨ q) → r |
| p ∧ q ∨ r | (p ∧ q) ∨ r |
| p → q ↔ ¬q → ¬p | (p → q) ↔ (¬q → ¬p) |
| p → q → r | p → (q → r) |
What to learn next
- Conditional statements: why p → q is true when p is false, and which of the converse, inverse and contrapositive mean the same thing.
- Tautologies, contradictions and contingencies: classifying a statement by its truth table, and what that has to do with valid arguments.
- Logical equivalences: the laws that let you rewrite a statement without changing its meaning.
- Rules of inference: modus ponens and friends, and how to chain them into a proof.
To check your own work, type any statement into the truth table calculator for its full table, a list of statements separated by commas to compare them, or premises, ∴ and a conclusion to test an argument. The logical equivalence calculator checks whether two statements mean the same.
From logic to logic gates
In 1938 Claude Shannon showed that switching circuits obey the same algebra as propositional logic. Write 1 for true and 0 for false and every connective becomes a logic gate:
The conditional has no gate of its own: p → q is built as ¬p ∨ q. The laws of boolean algebra are the logical equivalences in circuit notation, where ∧ is written as multiplication and ∨ as +, and De Morgan's laws are the same in both.
Questions
What is propositional logic?
Propositional logic is the part of logic that studies how the truth of compound statements depends on the truth of their parts. Each basic statement is a single letter that is either true or false, and connectives such as not, and, or, if-then and if-and-only-if build larger statements from them. It is also called sentential logic, statement logic or the propositional calculus.
What does the symbol → mean in logic?
p → q is the conditional, read "if p then q" or "p implies q". It is false in exactly one case: when p is true and q is false. Some books write it as p ⊃ q or p ⇒ q.
What is the difference between ∧ and ∨?
∧ is AND (conjunction): p ∧ q is true only when both are true. ∨ is OR (disjunction): p ∨ q is true when at least one is true, including when both are. The OR of logic is inclusive; the exclusive version, "one or the other but not both", is written ⊕.
What is the difference between propositional logic and predicate logic?
Propositional logic treats "Socrates is mortal" as an indivisible letter such as p. Predicate (first-order) logic looks inside the statement, with predicates like Mortal(x) and the quantifiers ∀ (for all) and ∃ (there exists). Everything in propositional logic can be decided with a truth table; predicate logic in general cannot.
Is "x > 3" a proposition?
Not on its own. Its truth depends on x, so it is an open sentence, or predicate. It becomes a proposition once x is fixed ("5 > 3" is true) or once it is quantified ("for every x, x > 3" is false). Questions and commands are not propositions either, since they are neither true nor false.
How is propositional logic used in computer science?
Every if statement in a program tests a proposition, digital circuits compute propositional formulas with logic gates, and SAT solvers decide whether huge propositional formulas can be made true, which is how chips are verified and many scheduling problems are solved. Boolean algebra is propositional logic written with 1, 0, + and multiplication.