In short
A proposition (or statement) is a sentence that is either true or false — never both, never neither. Propositions combine through five logical connectives: conjunction (\land, "and"), disjunction (\lor, "or"), negation (\lnot, "not"), implication (\Rightarrow, "if...then"), and biconditional (\Leftrightarrow, "if and only if"). A truth table lists every possible combination of truth values for the component propositions and computes the truth value of the compound expression. An expression that is always true is a tautology; one that is always false is a contradiction. Two expressions are logically equivalent when they have identical truth tables — and the most important equivalences are De Morgan's laws, the contrapositive rule, and the double-negation law.
Here is a sentence: "The sum of the interior angles of a triangle is 180°." Is it true or false? True — you can verify it with a protractor, and the proof is in every geometry textbook. Here is another sentence: "7 is an even number." True or false? False — 7 leaves a remainder of 1 when divided by 2.
Now consider: "What time is it?" That is neither true nor false — it is a question. Or: "Please close the door." That is a command, not a claim. Or: "x + 3 = 7." That depends on what x is — if x = 4 it is true, if x = 5 it is false. As written, without specifying x, it is not a statement because its truth value is not determined.
The first two sentences are propositions. The last three are not. The distinction is simple but absolute: a proposition is a declarative sentence that has a definite truth value — true (T) or false (F) — and nothing else. Every definition, every theorem, every proof in mathematics is built out of propositions. The connectives you will learn in this article are the rules for combining propositions into more complex ones, and truth tables are the bookkeeping tool that tracks the result.
Statements and truth values
Proposition
A proposition (or statement) is a declarative sentence that is either true or false, but not both. The truth value of a proposition p is denoted T (true) or F (false).
Propositions are usually named with lowercase letters: p, q, r. Some examples:
- p: "2 + 3 = 5" — truth value T.
- q: "Every prime number is odd" — truth value F (because 2 is prime and even).
- r: "Delhi is the capital of India" — truth value T.
And some non-examples (sentences that are not propositions):
- "How beautiful is the Taj Mahal?" (question)
- "Study hard for your exam." (command)
- "n is a prime number." (open sentence — depends on n)
The last one, "n is a prime number," is called an open sentence or predicate. It becomes a proposition once you substitute a specific value for n: "7 is a prime number" (T) or "9 is a prime number" (F). Until then, it hovers in an indeterminate state. Predicates are important in their own right — they are the building blocks of quantified logic — but for this article, the focus is on propositions with definite truth values.
The five logical connectives
You build complex propositions from simpler ones using connectives. There are five.
Negation (\lnot) — "not"
The negation of p, written \lnot p, flips the truth value. If p is true, \lnot p is false, and vice versa.
| p | \lnot p |
|---|---|
| T | F |
| F | T |
If p is "5 is odd" (T), then \lnot p is "5 is not odd" (F). Negation is the simplest connective — it operates on a single proposition.
Conjunction (\land) — "and"
The conjunction p \land q is true when both p and q are true, and false otherwise.
| p | q | p \land q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
"It is raining and I have an umbrella" is true only when both parts are true. If it is not raining, the whole statement is false regardless of the umbrella.
Disjunction (\lor) — "or"
The disjunction p \lor q is true when at least one of p or q is true.
| p | q | p \lor q |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
This is the inclusive or — it is true even when both parts are true. In everyday Hindi or English, "or" sometimes means "one or the other but not both" (exclusive or), but in mathematics the default is inclusive. When you order chai or coffee at a canteen, the server assumes you want one — but mathematical "or" happily accepts both.
Implication (\Rightarrow) — "if...then"
The implication p \Rightarrow q reads "if p, then q." The proposition p is the hypothesis (or antecedent), and q is the conclusion (or consequent).
| p | q | p \Rightarrow q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
The first two rows are intuitive: if the hypothesis is true and the conclusion follows, the implication holds (T). If the hypothesis is true but the conclusion fails, the implication is broken (F).
The last two rows are the tricky ones. When the hypothesis p is false, the implication p \Rightarrow q is true regardless of what q is. This is called vacuous truth. Think of it as a promise: "If it rains, I will carry an umbrella." On a sunny day (p is false), you haven't broken the promise whether you carry an umbrella or not. The promise only fails when it does rain and you show up without one.
This convention might feel strange, but it is exactly the one that makes mathematical proofs work. Every theorem of the form "if A holds, then B holds" is an implication. The theorem is "wrong" only when the hypothesis A is satisfied but the conclusion B fails. When the hypothesis is not satisfied, the theorem says nothing — it is vacuously true.
Biconditional (\Leftrightarrow) — "if and only if"
The biconditional p \Leftrightarrow q is true when p and q have the same truth value — both true or both false.
| p | q | p \Leftrightarrow q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
You can read p \Leftrightarrow q as "p if and only if q" (often shortened to "p iff q"). It combines two implications: p \Rightarrow q and q \Rightarrow p. The biconditional is true exactly when both directions hold.
"A number is even if and only if it is divisible by 2." Both parts say the same thing in different words, so they always have the same truth value. The biconditional is true.
Truth tables
A truth table is the systematic way to compute the truth value of a compound proposition for every possible combination of its components. If there are n component propositions, the table has 2^n rows — one for each combination of T and F.
Here is the truth table for \lnot(p \land q) — the negation of a conjunction:
| p | q | p \land q | \lnot(p \land q) |
|---|---|---|---|
| T | T | T | F |
| T | F | F | T |
| F | T | F | T |
| F | F | F | T |
And here is the truth table for \lnot p \lor \lnot q — the disjunction of two negations:
| p | q | \lnot p | \lnot q | \lnot p \lor \lnot q |
|---|---|---|---|---|
| T | T | F | F | F |
| T | F | F | T | T |
| F | T | T | F | T |
| F | F | T | T | T |
Compare the last columns of both tables. They are identical: F, T, T, T. This means \lnot(p \land q) and \lnot p \lor \lnot q always have the same truth value, no matter what p and q are. That is De Morgan's first law, now proved for propositions.
Tautologies and contradictions
Tautology and contradiction
A tautology is a compound proposition that is true for every combination of truth values of its components. A contradiction is one that is false for every combination.
The simplest tautology: p \lor \lnot p. Either p is true or p is false — in both cases, one of the two disjuncts holds, so the disjunction is true.
| p | \lnot p | p \lor \lnot p |
|---|---|---|
| T | F | T |
| F | T | T |
This is the law of the excluded middle: every proposition is either true or false. There is no third option.
The simplest contradiction: p \land \lnot p. A proposition cannot be both true and false at the same time.
| p | \lnot p | p \land \lnot p |
|---|---|---|
| T | F | F |
| F | T | F |
A more interesting tautology is the form used in every mathematical proof by contradiction:
This says: "if p then q" is logically the same as "if not q then not p." The second form is the contrapositive of the first. You will meet this in Proof by Contrapositive, where it becomes a powerful proof technique: instead of proving p \Rightarrow q directly, you prove the contrapositive \lnot q \Rightarrow \lnot p, which is logically identical.
Build the truth table:
| p | q | p \Rightarrow q | \lnot q | \lnot p | \lnot q \Rightarrow \lnot p | (p \Rightarrow q) \Leftrightarrow (\lnot q \Rightarrow \lnot p) |
|---|---|---|---|---|---|---|
| T | T | T | F | F | T | T |
| T | F | F | T | F | F | T |
| F | T | T | F | T | T | T |
| F | F | T | T | T | T | T |
The last column is all T's — the biconditional is always true. So the original implication and its contrapositive are equivalent, and the equivalence itself is a tautology.
Logical equivalence
Logical equivalence
Two propositions P and Q are logically equivalent, written P \equiv Q, if P \Leftrightarrow Q is a tautology — that is, P and Q have the same truth value in every possible scenario.
Logical equivalence is the core engine of mathematical reasoning. Every time you "simplify" an expression, rewrite a condition in an equivalent form, or transform a proof strategy, you are using a logical equivalence. Here are the most important ones, each provable by truth table:
De Morgan's laws:
Double negation:
Contrapositive:
Implication as disjunction:
Distributive laws:
These equivalences mirror the set-operation identities from Set Operations almost symbol for symbol. That is not a coincidence — the Boolean algebra of sets and the Boolean algebra of propositions are the same abstract structure.
The connection to sets
Every logical connective has a set-operation twin:
| Logic | Sets | Meaning |
|---|---|---|
| \lnot p | A' | complement / negation |
| p \land q | A \cap B | intersection / conjunction |
| p \lor q | A \cup B | union / disjunction |
| p \Rightarrow q | A \subseteq B | subset / implication |
De Morgan's laws in set theory — (A \cup B)' = A' \cap B' and (A \cap B)' = A' \cup B' — are exactly De Morgan's laws in logic — \lnot(p \lor q) \equiv \lnot p \land \lnot q and \lnot(p \land q) \equiv \lnot p \lor \lnot q — wearing different notation. Once you see this dictionary, you never have to memorise the two versions separately.
Interactive: building a truth table
Drag the red point below to select one of the four rows of the truth table for p \Rightarrow q. The readout shows the current truth values of p and q and the resulting value of the implication.
Two worked examples
Example 1: Build the truth table for $(p \Rightarrow q) \land (q \Rightarrow p)$ and show it is equivalent to $p \Leftrightarrow q$
Step 1. Set up the table with all four combinations of p and q.
There are two propositions, so there are 2^2 = 4 rows.
Why: each proposition has two possible truth values, and the combinations are independent. So the total is 2 \times 2 = 4.
Step 2. Compute p \Rightarrow q for each row.
- Row 1: p = T, q = T. T \Rightarrow T = T.
- Row 2: p = T, q = F. T \Rightarrow F = F.
- Row 3: p = F, q = T. F \Rightarrow T = T.
- Row 4: p = F, q = F. F \Rightarrow F = T.
Why: the implication is false only when the hypothesis is true and the conclusion is false (row 2).
Step 3. Compute q \Rightarrow p for each row.
- Row 1: T \Rightarrow T = T.
- Row 2: F \Rightarrow T = T.
- Row 3: T \Rightarrow F = F.
- Row 4: F \Rightarrow F = T.
Step 4. Compute the conjunction (p \Rightarrow q) \land (q \Rightarrow p).
- Row 1: T \land T = T.
- Row 2: F \land T = F.
- Row 3: T \land F = F.
- Row 4: T \land T = T.
Results: T, F, F, T.
Step 5. Compare with p \Leftrightarrow q.
The biconditional is T when p and q have the same truth value, and F otherwise. So: T, F, F, T. Identical.
Result. (p \Rightarrow q) \land (q \Rightarrow p) \equiv p \Leftrightarrow q. The biconditional is exactly the conjunction of the two one-directional implications.
This is why, whenever you prove an "if and only if" theorem, you prove two separate implications — the "if" direction and the "only if" direction. The biconditional is true exactly when both directions hold.
Example 2: Prove that $p \Rightarrow q \equiv \lnot p \lor q$ using a truth table, and use the equivalence to negate the statement "if $n$ is a perfect square, then $n$ is non-negative"
Step 1. Build the truth table for p \Rightarrow q.
| p | q | p \Rightarrow q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
Why: the implication is false only in row 2 — hypothesis true, conclusion false.
Step 2. Build the truth table for \lnot p \lor q.
| p | q | \lnot p | \lnot p \lor q |
|---|---|---|---|
| T | T | F | T |
| T | F | F | F |
| F | T | T | T |
| F | F | T | T |
Why: \lnot p \lor q is false only when \lnot p is false (i.e. p is true) and q is false — exactly the same row as the implication.
Step 3. Compare. Both have the pattern T, F, T, T. So p \Rightarrow q \equiv \lnot p \lor q.
Step 4. Apply the equivalence. Let p = "n is a perfect square" and q = "n is non-negative." The statement "if p, then q" is p \Rightarrow q.
Its negation is \lnot(p \Rightarrow q) \equiv \lnot(\lnot p \lor q) \equiv p \land \lnot q (using De Morgan on the disjunction).
In plain language: "n is a perfect square and n is negative." That is, the negation of "if n is a perfect square then n \ge 0" is "there exists n that is a perfect square and is negative."
Since no perfect square is negative, the negation is false — which confirms the original statement is true.
Result. p \Rightarrow q \equiv \lnot p \lor q, and the negation of an implication is p \land \lnot q.
The technique of negating an implication by converting it to p \land \lnot q is the logical foundation of Proof by Contradiction: you assume the negation of what you want to prove and derive something impossible.
Common confusions
-
"The converse of p \Rightarrow q is the same as p \Rightarrow q." No. The converse is q \Rightarrow p — the hypothesis and conclusion are swapped. The converse can have a completely different truth value from the original. "If it rains, the ground is wet" is true. Its converse, "if the ground is wet, it rained," is not necessarily true — someone might have turned on the sprinkler.
-
"p \Rightarrow q is false when p is false." No — it is vacuously true. The implication is false only when p is true and q is false. This is the single most counterintuitive row of the truth table, and it trips up students every time.
-
"p \lor q means either p or q but not both." In mathematics, "or" is always inclusive unless explicitly stated otherwise. p \lor q is true even when both p and q are true. If you mean exclusive or, you must say so explicitly.
-
"A tautology is a true statement." More precisely, a tautology is a statement that is true under every possible assignment of truth values. "2 + 3 = 5" is true, but it is not a tautology — it is a specific fact about specific numbers. p \lor \lnot p is a tautology because it is true no matter what p stands for.
-
"Logically equivalent means the two statements say the same thing in English." Not exactly. Logically equivalent means the two expressions have the same truth table. They might look very different in English. "p \Rightarrow q" and "\lnot p \lor q" look nothing alike in words, but they are logically equivalent — they produce the same truth value in every scenario.
-
"\lnot(p \Rightarrow q) \equiv \lnot p \Rightarrow \lnot q." No. \lnot p \Rightarrow \lnot q is the inverse of the original, not the negation. The negation is p \land \lnot q. The inverse has a different truth table from both the original and its negation.
Going deeper
If you came here for the five connectives, truth tables, and the key equivalences, you have the toolkit for every proof chapter that follows. The rest of this section is for readers who want to see where propositional logic sits in the larger landscape.
Propositional logic vs. predicate logic
Everything in this article is propositional logic — the logic of statements that are simply true or false. But many mathematical statements involve quantifiers: "for all x..." (\forall x) and "there exists x..." (\exists x). These belong to predicate logic (also called first-order logic), which is a strictly more powerful system. The statement "for all n \in \mathbb{N}, n + 0 = n" cannot be expressed in propositional logic — it would require infinitely many conjunctions, one for each n. Predicate logic adds the quantifiers \forall and \exists to handle this, and the rules for negating quantified statements are:
These are De Morgan's laws for quantifiers. The negation of "every student passed" is "there exists a student who did not pass" — not "every student failed."
Functional completeness
A surprising fact: you do not need all five connectives. The set \{\lnot, \land\} is functionally complete — every truth table of any compound proposition can be expressed using only negation and conjunction. The same is true of \{\lnot, \lor\}. Even more remarkably, the single connective NAND (not-and, written p \uparrow q, defined as \lnot(p \land q)) is functionally complete by itself — every logical operation can be built from NAND gates alone. This is why NAND gates are the universal building block of digital circuits.
Logic gates and computation
The five connectives of propositional logic correspond directly to logic gates in digital electronics: AND, OR, NOT, NAND, and XOR. Every digital computer is, at the hardware level, a vast network of logic gates computing truth tables billions of times per second. The Boolean algebra you met in Set Operations and this article is not an abstract curiosity — it is literally the operating principle of every phone, laptop, and server on the planet.
Where this leads next
The logic on this page is the invisible operating system of every proof you will read or write.
- Mathematical Proof — Direct Proof — the simplest proof technique, where you assume p and derive q to establish p \Rightarrow q.
- Proof by Contradiction — assume \lnot q (or p \land \lnot q) and derive a contradiction. The logical foundation is that the negation of p \Rightarrow q is p \land \lnot q.
- Proof by Contrapositive — prove \lnot q \Rightarrow \lnot p instead of p \Rightarrow q. The two are logically equivalent, as the truth table in this article showed.
- Set Operations — the Boolean algebra of sets is the same algebra as propositional logic, with a different notation. De Morgan, distributivity, and complement all carry over.
- Sets — Introduction — the prerequisite article, where the ideas of "element of" and "subset of" were first defined, and where the logical quantifiers "for all" and "there exists" were used implicitly throughout.