Propositions, connectives, and conditionals
Last modified: 2026-10-27 13:24:37 (PDT)
Source
Adapted from Kameron Decker Harris’s Fall 2026 lecture notes “Logic 1” and “Logic 2”, which are typed transcriptions of Scott Wehrwein’s Spring 2025 handwritten lecture notes. The examples of propositions, the truth tables to decode, the list of English phrasings of a conditional, and the “only if” example come from those notes; the other exercises are new.
The definitions are included from the mathematics prerequisites notes, so they read the same in both places.
Exercise 1 (True, false, or neither?) Which of these sentences and expressions are definitely true or definitely false?
Solution 1.
The four sentences with a definite truth value are propositions. The last sentence, whose truth value depends on \(x\), is a predicate.
Definition 1 (Proposition (statement)) A proposition (Wikipedia contributors 2026j), or statement, is a declarative sentence that is either true or false.
Definition 2 (Predicate) A predicate (Wikipedia contributors 2026i) \(P(x)\) is a declarative sentence about a variable \(x\) that becomes a proposition (Definition 1) whenever a value is substituted for \(x\).
Remark 1 (Other names). Many textbooks call a proposition a statement, and call a predicate an open sentence or a propositional function. These notes say proposition and predicate.
Example 1 (A proposition whose truth value nobody knows) Start with a positive integer \(n\). If \(n\) is even, replace it with \(n / 2\); if \(n\) is odd, replace it with \(3n + 1\). Repeat. Starting from \(n = 6\) gives \(6, 3, 10, 5, 16, 8, 4, 2, 1\).
The Collatz conjecture (Wikipedia contributors 2026a) is the sentence “starting from any positive integer, the process reaches 1 after finitely many steps”. It is a proposition, because it is either true or false, but nobody has yet proved which. A proposition needs a definite truth value, not a known one.
Exercise 2 (What do these symbols mean?) Each table lists every combination of truth values of propositions \(P\) and \(Q\) (T for true, F for false), and the truth value of a new proposition built from them. Describe in words when each new proposition is true.
| \(P\) | \(Q\) | \(P \land Q\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
| \(P\) | \(Q\) | \(P \lor Q\) |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
| \(P\) | \(\neg P\) |
|---|---|
| T | F |
| F | T |
Solution 2.
Definition 3 (Logical connective) A logical connective (Wikipedia contributors 2026e) builds a new proposition (Definition 1) from one or two propositions \(P\) and \(Q\), with a truth value that depends only on the truth values of \(P\) and \(Q\). These notes use five, each defined next: not, and, or, implies, and if and only if.
Definition 4 (Not) The logical connective (Definition 3) not (Wikipedia contributors 2026h) is written \(\neg P\) (“not \(P\)”); it is true when \(P\) is false, and false when \(P\) is true.
Definition 5 (And) The logical connective (Definition 3) and is written (Wikipedia contributors 2026d) \(P \land Q\) (“\(P\) and \(Q\)”); it is true when \(P\) and \(Q\) are both true, and false otherwise.
Definition 6 (Or) The logical connective (Definition 3) or is written (Wikipedia contributors 2026f) \(P \lor Q\) (“\(P\) or \(Q\)”); it is true when at least one of \(P\) and \(Q\) is true, and false when both are false.
Remark 2 (Notation, and the inclusive “or”). Some textbooks write \(\sim P\) for \(\neg P\). Programming languages spell the same three connectives as words or symbols: Racket writes (not p), (and p q) and (or p q), and Java and C write !p, p && q and p || q.
In everyday English, “soup or salad” often means one but not both. The logical “or” always allows both, as the first row of the table for \(P \lor Q\) in Exercise 2 shows.
Exercise 3 (Evaluate a compound proposition) Suppose \(P\) is true, \(Q\) is false, and \(R\) is false. Is \((\neg P \lor Q) \land \neg R\) true or false?
Solution 3. Substitute the truth values, then evaluate from the innermost parentheses outward:
\[ \begin{aligned} (\neg P \lor Q) \land \neg R &= (\neg \mathrm{T} \lor \mathrm{F}) \land \neg \mathrm{F} \\ &= (\mathrm{F} \lor \mathrm{F}) \land \mathrm{T} \\ &= \mathrm{F} \land \mathrm{T} \\ &= \mathrm{F} \end{aligned} \]
The proposition is false.
Exercise 4 (Evaluate another compound proposition) With the same truth values as Exercise 3 (\(P\) true, \(Q\) false, \(R\) false), is \(\neg (P \land Q) \lor R\) true or false?
Solution 4. \[ \begin{aligned} \neg (P \land Q) \lor R &= \neg (\mathrm{T} \land \mathrm{F}) \lor \mathrm{F} \\ &= \neg \mathrm{F} \lor \mathrm{F} \\ &= \mathrm{T} \lor \mathrm{F} \\ &= \mathrm{T} \end{aligned} \]
The proposition is true.
Exercise 5 (How many cases?) Exercise 4 found the truth value of \(\neg (P \land Q) \lor R\) for one choice of truth values of \(P\), \(Q\) and \(R\). How many different choices are there?
Solution 5. Each of \(P\), \(Q\) and \(R\) is either true or false, independently of the other two, so there are \(2 \times 2 \times 2 = 2^3 = 8\) choices. With \(n\) propositions there are \(2^n\).
Definition 7 (Truth table) A truth table for a proposition built from \(P_1, \ldots, P_n\) with logical connectives (Definition 3) has one row for each of the \(2^n\) combinations of truth values of \(P_1, \ldots, P_n\), and gives the truth value of the proposition in each row.
Exercise 6 (A truth table with three propositions) Make a truth table (Definition 7) for \(\neg (P \land Q) \lor R\).
Hint
Add columns for the pieces, \(P \land Q\) and \(\neg (P \land Q)\), before the last column.
Solution 6.
| \(P\) | \(Q\) | \(R\) | \(P \land Q\) | \(\neg (P \land Q)\) | \(\neg (P \land Q) \lor R\) |
|---|---|---|---|---|---|
| T | T | T | T | F | T |
| T | T | F | T | F | F |
| T | F | T | F | T | T |
| T | F | F | F | T | T |
| F | T | T | F | T | T |
| F | T | F | F | T | T |
| F | F | T | F | T | T |
| F | F | F | F | T | T |
The proposition is false in only one row: \(P\) and \(Q\) true, and \(R\) false. The fourth row is the case in Exercise 4.
Exercise 7 (When is a promise broken?) A parent tells a child, “If you clean your room, then you get dessert.” In which of these four situations did the parent break the promise?
| Room cleaned? | Dessert? |
|---|---|
| yes | yes |
| yes | no |
| no | yes |
| no | no |
Solution 7. Only in the second row: the child cleaned the room and got no dessert.
When the room was not cleaned, the promise says nothing about dessert, so the parent kept it whether or not dessert came.
Writing \(P\) for “you clean your room” and \(Q\) for “you get dessert”, the promise “if \(P\), then \(Q\)” is false only when \(P\) is true and \(Q\) is false.
Definition 8 (Implies) The logical connective (Definition 3) implies is written (Wikipedia contributors 2026g) \(P \Rightarrow Q\) (“if \(P\), then \(Q\)”, or “\(P\) implies \(Q\)”); it is false when \(P\) is true and \(Q\) is false, and true otherwise.
Remark 3 (Names for the parts, and other notation). In \(P \Rightarrow Q\), \(P\) is the premise (also called the hypothesis or antecedent) and \(Q\) is the conclusion (also called the consequent). A proposition of this form is also called a conditional or an implication.
Many textbooks write \(P \rightarrow Q\) for \(P \Rightarrow Q\).
Example 2 (Implications with a true and a false premise) Take \(x = 3\).
Exercise 8 (A false premise) Is each of these propositions true or false?
Solution 8. Both are true. The premise “\(7\) is even” is false, so each implication (Definition 8) is true whatever its conclusion says. The conclusion of the first is false and the conclusion of the second is true, and neither matters.
Remark 4 (Reading an implication). An implication with a false premise, as in Exercise 8, is sometimes called vacuously true. Three habits help with implications that sound strange:
Exercise 9 (Reverse an implication) For all real numbers \(x\) and \(y\), “if \(x = y\), then \(x^2 = y^2\)” is true. Is “if \(x^2 = y^2\), then \(x = y\)” also true for all real numbers \(x\) and \(y\)?
Solution 9. No. Take \(x = 1\) and \(y = -1\). Then \(x^2 = 1 = y^2\), so the premise is true, but \(x \ne y\), so the conclusion is false.
Swapping the premise and the conclusion of a true implication can give a false one.
Definition 9 (Converse) The converse (Wikipedia contributors 2026b) of the proposition “if \(P\), then \(Q\)” is the proposition “if \(Q\), then \(P\)”.
Exercise 10 (“Only if”) Rewrite “I go to class only if I am healthy” in the form “if \(P\), then \(Q\)”.
Solution 10. “If I go to class, then I am healthy.”
The sentence says that going to class requires being healthy, so whenever I go to class, I am healthy. It does not say “if I am healthy, then I go to class”; that is its converse (Definition 9), and a healthy person may still skip class.
In general, “\(P\) only if \(Q\)” means \(P \Rightarrow Q\).
Remark 5 (English phrasings of \(P \Rightarrow Q\)). Each of these sentences means \(P \Rightarrow Q\):
Exercise 11 (Split “if and only if”) “\(P\) if and only if \(Q\)” combines “\(P\) if \(Q\)” and “\(P\) only if \(Q\)”. Write each of the two halves as an implication.
Solution 11.
So “\(P\) if and only if \(Q\)” says that \(P \Rightarrow Q\) and \(Q \Rightarrow P\) are both true.
Definition 10 (If and only if) The logical connective (Definition 3) if and only if is written (Wikipedia contributors 2026c) \(P \Leftrightarrow Q\) (“\(P\) if and only if \(Q\)”); it is true when \(P\) and \(Q\) have the same truth value, and false otherwise.
Remark 6 (Other names and notation). “If and only if” is often shortened to “iff”. A proposition of the form \(P \Leftrightarrow Q\) is also called a biconditional, and many textbooks write \(P \leftrightarrow Q\).
Exercise 12 (Check a biconditional) Is “\(n\) is even if and only if \(n\) is divisible by \(3\)” true or false when \(n = 6\)? When \(n = 4\)? When \(n = 5\)?
Solution 12.
| \(n\) | \(n\) is even | \(n\) is divisible by \(3\) | biconditional |
|---|---|---|---|
| \(6\) | T | T | T |
| \(4\) | T | F | F |
| \(5\) | F | F | T |
By Definition 10, the biconditional is true exactly when its two sides have the same truth value. When \(n = 5\), both sides are false, so the biconditional is true.