In geometry you worked with if-then statements and their converses. Discrete math starts one step earlier, with the smallest pieces of reasoning: sentences that are simply true or false, and the words that glue them together. Getting these pieces exactly right is what lets a proof run without gaps.
🔑 Key idea
A statement (or proposition) is a sentence that is either true or false, but not both. From statements $P$ and $Q$ we build new ones: the negation $\neg P$ ("not $P$"), the conjunction $P \wedge Q$ ("$P$ and $Q$"), true only when both are true, and the disjunction $P \vee Q$ ("$P$ or $Q$"), true when at least one is true.
"$17$ is prime" is a true statement. "$2 + 2 = 5$" is a false statement; being false does not stop it from being a statement. But "Is $7$ prime?" (a question), "Add $3$ to both sides" (a command) and "$x + 4 = 9$" are not statements. The last one is true for $x = 5$ and false otherwise, so until we know $x$ it has no single truth value. Sentences like that are called open sentences; the lesson on quantifiers shows how to turn them into statements.
The three basic connectives. Each row is one combination of truth values.
$P$
$Q$
$\neg P$
$P \wedge Q$
$P \vee Q$
T
T
F
T
T
T
F
F
F
T
F
T
T
F
T
F
F
T
F
F
💡 Why it works
Why is "or" true when both parts are true? Because that is what mathematics needs. "$n$ is divisible by $2$ or by $3$" should be true for $n = 6$, which is divisible by both. Mathematicians fixed the meaning of "or" so that a statement like this never has an exception. When we really mean "one or the other but not both," we say so in words: "exactly one of $P$, $Q$" (sometimes written $P \oplus Q$, the exclusive or).
The disjunction is false in only one row: when both parts are false. Notice the top row: both parts true, and $P \vee Q$ is true.
Worked examples
✏️ Worked example: Evaluating compound statements
Let $P$: "$6$ is even" and $Q$: "$6$ is a multiple of $5$." Decide $P \vee Q$, $P \wedge \neg Q$ and $\neg(P \wedge Q)$.
First the letters: $P$ is true, and $Q$ is false (since $6 = 5 \cdot 1 + 1$).
$P \vee Q$: at least one part ($P$) is true, so it is true.
$P \wedge \neg Q$: $\neg Q$ is true, and $P$ is true, so both parts are true: true.
$\neg(P \wedge Q)$: $P \wedge Q$ is false because $Q$ is false, so its negation is true.
Answer: true, true, true
✏️ Worked example: Translating English into symbols
Let $P$: "it is raining" and $Q$: "the game is canceled." Write "It is raining, but the game is not canceled" and "It is not raining, or the game is canceled" in symbols.
"But" sounds like a contrast, yet logically it means "and": both parts are claimed. So the first sentence is $P \wedge \neg Q$.
The second sentence joins "not $P$" and "$Q$" with "or": $\neg P \vee Q$.
Check by reading back: $P \wedge \neg Q$ says "raining, and not canceled." That matches.
Answer: $P \wedge \neg Q$ and $\neg P \vee Q$
⚠️ Common mistake
Reading "or" as "one or the other but not both." Many people say $P \vee Q$ is false when $P$ and $Q$ are both true, because everyday "or" often means a choice ("soup or salad"). In logic, $P \vee Q$ is false only when both parts are false. Check: ask "is at least one part true?" If yes, the disjunction is true.
Parentheses matter. $\neg(P \wedge Q)$ and $\neg P \wedge Q$ are different statements: the first negates the whole "and," the second negates only $P$. By convention $\neg$ applies to the smallest piece right after it.
Practice
Pass with 3 right answers, the last 2 in a row. Each right answer earns 1 XP.