Back to the on-screen lesson ·
The five connectives, the one combination an implication forbids, and the table that settles any formula in two statements.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to name the atoms of an English sentence, write it in symbols with the right connective, and complete the truth table column for any formula in two or three statements. You will also be able to say why an implication is counted true whenever its hypothesis fails, and why that is forced rather than chosen — which is the single fact that makes the rest of this course's theorems sayable in one line each.
You have written if ... then and and and or all through school, and you have read a theorem that says 'if $f$ is differentiable then $f$ is continuous'. None of that is being replaced. What is added is that these words get definitions, so that whether a compound statement holds stops being a matter of how it sounds and becomes something a finite table decides.
A statement is a sentence that is true or false — not a question, not an instruction, and not something that depends on an unfixed $x$. A connective joins statements into a longer one. An atom is a statement with no connective in it, written as a capital letter. A truth table lists every combination of truth values the atoms can take, one row each, and gives the compound statement's value in every row.
Logic starts by fixing what the joining words mean, because English does not.
| Symbol | Read | True when |
|---|---|---|
| $\neg P$ | not $P$ | $P$ is false |
| $P \wedge Q$ | $P$ and $Q$ | both hold |
| $P \vee Q$ | $P$ or $Q$ | at least one holds — both is allowed |
| $P \Rightarrow Q$ | if $P$ then $Q$ | except where $P$ holds and $Q$ fails |
| $P \Leftrightarrow Q$ | $P$ if and only if $Q$ | the two agree |
Two of these rows are where the trouble is. The mathematical or is inclusive: 'the number is prime or odd' is true of $3$. And the implication is defined by the single combination it forbids — hypothesis true, conclusion false — so it is true whenever the hypothesis fails. 'If $2 > 3$ then the moon is cheese' is a true statement, which sounds absurd until you notice what the alternative would cost: a theorem of the form 'for every $n$, if $n$ is prime and $n > 2$ then $n$ is odd' has to stay true at $n = 4$, where the hypothesis simply does not apply.
With the meanings fixed, a compound statement in $k$ atoms is settled by a table of $2^k$ rows. That is a decision procedure: finite, mechanical, and the reason propositional logic is the one part of this course where an argument can be replaced by a calculation.
Another way: steps
To settle a compound statement:
Another way: example
'The graph is connected but it has no cycle' has atoms $P$ (connected) and $Q$ (has a cycle), and is $P \wedge \neg Q$ — true in exactly one row of four. That one row is the definition of a tree, which is how a definition in unit 5 turns out to be a line of propositional logic.
Suppose you want 'every multiple of $4$ is even' to be one statement about every integer rather than a list. Write it $\forall n\, (P(n) \Rightarrow Q(n))$. At $n = 6$ the hypothesis fails, and the claim is not wrong at $6$ — it said nothing about $6$. So the implication has to come out true there, and the same reasoning covers $n = 7$.
That forces three of the four rows. The remaining row is the one where the claim is actually tested and fails, and it is false. There is no freedom left: the table is not a convention someone chose, it is what is needed for a universal claim to be a single statement.
The practical consequence is the one to carry: to break an implication you must produce the one forbidden combination. Anything else is not a counterexample.
*Reading or as exclusive.* In ordinary speech 'tea or coffee' means one of them. In mathematics $P \vee Q$ is true when both hold, every time, without being said.
*Reading but as a new connective. 'Connected but acyclic' is $P \wedge \neg Q$. But, however, although and yet* are all conjunction with a change of tone, and tone is not logic.
Confusing a false hypothesis with a false statement. An implication whose hypothesis fails is true and uninformative. Those are different things, and only the first is what the table records.
$P \Rightarrow Q$ being true does not mean $P$ has anything to do with $Q$. The table knows only the truth values, so it will happily call 'if $2 > 3$ then $7$ is prime' true. Propositional logic is deliberately blind to relevance; what it buys with that blindness is decidability. When you want a connection rather than a truth value you want a proof, which is unit 2, and a proof is what supplies the relevance the table cannot see.
'The matrix is invertible if and only if its determinant is non-zero.' Let $P$ be 'the matrix is invertible' and $Q$ be 'the determinant is non-zero'.
Name the atoms first, always.
If and only if asserts both directions, so the sentence is $P \Leftrightarrow Q$.
The joining phrase chooses the connective.
That is two claims in one symbol, which is why proving a biconditional is two proofs.
One symbol, two obligations.
Is $(P \Rightarrow Q) \wedge P$ true in more than one row? Atoms $P$, $Q$; four rows.
Count the rows before working.
Row 1 ($P$, $Q$ both true): the implication holds and $P$ holds, so T.
Work outwards from the bracket.
Rows 2 to 4: row 2 fails the implication, rows 3 and 4 fail $P$. So the formula is true in exactly one row, and that row has $Q$ true — which is modus ponens, seen as a table.
One row survives, and it is the one that matters.
Take $\neg P \vee Q$ with atoms $P$ and $Q$. Start by asking when a disjunction fails: only when both halves fail.
Ask what makes it false, not what makes it true.
Both halves fail when $\neg P$ is false and $Q$ is false — that is, when $P$ is true and $Q$ is false. One row.
Name the single failing row.
So it is true in three rows of four, and they are exactly the three rows of $P \Rightarrow Q$. The two formulas are the same statement wearing different symbols, which is the subject of lesson 3.
Complete the column for $P \vee Q$ — the connective read 'or (inclusive)'. The rows are in the usual order: both true, then $P$ true and $Q$ false, then $Q$ only, then neither.
| P | Q | P | Q |
|---|---|---|
Let P stand for “the number is divisible by four” and Q for “the number is even”. Write this in symbols: “if the number is divisible by four then it is even.”
Answer:
Match each connective to what it demands of the two halves.
| Both halves hold | At least one half holds, and both is allowed | The first half never holds while the second fails | The two halves agree, either both holding or both failing | |
|---|---|---|---|---|
| $P \wedge Q$ | ||||
| $P \vee Q$ | ||||
| $P \Rightarrow Q$ | ||||
| $P \Leftrightarrow Q$ |
A truth table for $P$ and $Q$ has four rows. In how many of them is $P \wedge Q$ true?
Answer:
A theorem says $6$ conditions are all equivalent. Proving each implies the next, and the last implies the first, is enough. How many implications is that?
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Complete the column for $P \wedge Q$ — the connective read 'and'. The rows are in the usual order: both true, then $P$ true and $Q$ false, then $Q$ only, then neither.
| P | Q | P & Q |
|---|---|---|
You can write a sentence in symbols and settle a formula with a table. Say in your own words which single combination an implication forbids, and why the other three rows have to come out true. Next: what the converse and the contrapositive of an implication are, and which of them you are allowed to prove instead.
10. Your turn: how many rows make the statement true?, step 3