Statements and connectives

The words that build mathematical claims, "not", "and", "or", "if ... then", mean something slightly different in conversation every time they are used, and a proof cannot rest on a word whose meaning moves.

The previous lesson unpacked "the sum of two odd integers is even" into a claim with an "if ... then" inside it, and its proofs worked only because it was clear what that claim asserted. This lesson makes that clarity routine. It says which sentences can be true or false, fixes the meaning of each connective with a truth table, and spends a good part of its time on the conditional, the connective every theorem is written in. It then treats logic as algebra: which compound statements always say the same thing, which are true whatever their parts, and how to rewrite one into another by a small set of laws. It ends with two results about the connectives themselves: every truth table can be written with "not", "and" and "or" alone, and in fact with a single connective. It assumes school algebra and the definitions of even and odd: an integer is even when it equals $2k$ for some integer $k$, and odd when it equals $2k+1$.

Statements

A statement, or proposition, is a sentence that is either true or false. "$91$ is prime" is a statement, and a false one, since $91=7\times 13$. "$2^{10}>1000$" is a true one, since $2^{10}=1024$. What matters is that the sentence has a truth value, not that anyone knows it. "Every even integer greater than $2$ is the sum of two primes" is Goldbach's conjecture, proposed in a letter to Euler in 1742 and checked by computer for every even number up to $4\times {10}^{18}$. Nobody knows whether it is true, but it is certainly one or the other, so it is a statement.

Plenty of mathematical sentences are not statements. "Is $91$ prime?" is a question and "Let $n=91$" is an instruction. The subtler case is a sentence with a free variable, such as "$x>3$", which is true when $x=5$, false when $x=1$, and has no truth value until $x$ is pinned down. Such a sentence is an open sentence. Turning open sentences into statements is the job of the next lesson; this one works with statements, or with open sentences read for one value of the variable at a time.

Statements are written with capital letters, $P$, $Q$, $R$, so that the structure of a claim can be seen apart from its content. The rules below depend only on whether each part is true or false, never on what it says. A statement with no connectives inside it, such as "$91$ is prime", is called atomic; one built from others with connectives is compound.

Not, and, or

Each connective is defined by saying, for every combination of truth values of its parts, whether the compound is true. With two parts there are four combinations, and a truth table lists them, one per row.

Negation, written $\neg P$ and read "not $P$", is true exactly when $P$ is false. Conjunction, $P\wedge Q$, read "$P$ and $Q$", is true exactly when both parts are true. Disjunction, $P\vee Q$, read "$P$ or $Q$", is true when at least one part is true, including when both are.

The last column is the one that departs from conversation. "Soup or salad" on a menu usually means one but not both. In mathematics "or" is always inclusive, and the sentences mathematicians write show why. The rule "if $ab=0$ then $a=0$ or $b=0$" must not exclude $a=b=0$, and "$n$ is divisible by $2$ or by $3$" is true of $6$. When the exclusive sense is wanted it is spelt out: "$P$ or $Q$ but not both", which is $(P\vee Q)\wedge \neg (P\wedge Q)$. This is the exclusive or, sometimes written $P\oplus Q$, and it is true in the middle two rows only.

The negation of a statement is whatever is true in exactly the cases where the statement is false, and ordinary language often reaches for an opposite instead. The negation of "$x>3$" is "$x\le 3$", not "$x<3$": at $x=3$ both "$x>3$" and "$x<3$" are false, so the second cannot be the negation of the first. And "$x\le 3$" is itself a disjunction, "$x<3$ or $x=3$". Likewise the negation of "$n$ is even" is "$n$ is not even", which becomes "$n$ is odd" only once it is known that every integer is one or the other, a fact the lesson on direct proof proves.

English uses many words for $\wedge$. "But", "although", "whereas" and "yet" all mean "and" to a logician, whatever contrast they suggest: "$7$ is prime but $9$ is not" is $P\wedge \neg Q$. Mathematical writing also hides conjunctions in chains: "$0<x<1$" is "$0<x$ and $x<1$", and "$a=b=c$" is "$a=b$ and $b=c$".

Compound statements need brackets, just as in arithmetic, since $\neg P\wedge Q$ could mean $(\neg P)\wedge Q$ or $\neg (P\wedge Q)$, and these differ. The convention is that $\neg$ applies to the smallest thing after it, so $\neg P\wedge Q$ means $(\neg P)\wedge Q$. For the other connectives this course uses brackets whenever there could be doubt.

The conditional

The fourth connective is the conditional, $P\Rightarrow Q$, read "if $P$ then $Q$" or "$P$ implies $Q$". $P$ is the hypothesis (or antecedent) and $Q$ the conclusion (or consequent).

The first two rows need no defence. "If $n$ is divisible by $4$, then $n$ is even" is kept by a number divisible by $4$ that is even, and would be broken by one divisible by $4$ that is odd: a true hypothesis with a false conclusion is exactly what it means for an implication to fail.

The last two rows are the ones that surprise. Whenever the hypothesis is false, the conditional is true, whatever the conclusion, so "if $2+2=5$, then $7$ is even" is a true statement. A conditional true because its hypothesis is false is called vacuously true. It looks like a convention, and slightly at odds with sense, but no other choice would let mathematics state its theorems, as the next section shows.

Vacuous truth turns up constantly in mathematics, usually without comment. "Every element of the empty set is even" is true, because it says "for every $x$, if $x$ is in the empty set then $x$ is even", and the hypothesis is false for every $x$. "All the prime factors of $1$ are greater than $100$" is true for the same reason. A definition that says "a set of numbers is bounded below by $5$ if every element is at least $5$" makes the empty set bounded below by $5$, and by every other number too. These are not tricks; they are what the definitions say, and results about empty sets and edge cases come out right only because of them.

Why a false hypothesis gives a true conditional

Take a theorem nobody doubts: for every integer $n$, if $n$ is divisible by $4$, then $n$ is even. It claims something about every integer, so it is true only if each instance, one conditional per integer, is true. At $n=8$ the instance has a true hypothesis and a true conclusion. At $n=6$ the hypothesis is false and the conclusion true. At $n=7$ both are false. If either of the last two instances counted as false, this theorem would be false, and so would nearly every theorem of the form "if ... then", since nearly any hypothesis fails for some values. Those rows have to be true for mathematics to be sayable at all.

Nothing else could go in them either. Making both rows false turns $P\Rightarrow Q$ into $P\wedge Q$, so the theorem would assert that $n$ is divisible by $4$. Making only the false-true row false turns it into the biconditional of the next section, so the theorem would claim every even number is divisible by $4$, which $6$ refutes. Making only the false-false row false gives a column identical to $Q$, and the hypothesis would do nothing.

The conditional asserts no connection between its parts: "if $2+2=5$, then $7$ is even" is true though its halves are unrelated. In mathematics that costs nothing, because the connection is what the proof supplies. The table also tells a proof where to look. A conditional can fail only in the row where $P$ is true, so to prove $P\Rightarrow Q$ it is enough to assume $P$ and show that $Q$ follows, which is what the previous lesson did when it began "let $a$ and $b$ be odd".

That same row gives the negation. Since $P\Rightarrow Q$ is false only when $P$ is true and $Q$ false, its negation is $P\wedge \neg Q$. The negation of an implication is not another implication: it says the hypothesis holds and the conclusion fails, which is what a counterexample exhibits.

Example. Negate "if $n$ is prime, then $n$ is odd", decide whether the conditional is true for $n=2$, $n=9$ and $n=7$, and say what this shows.

The negation is "$n$ is prime and $n$ is not odd", since $\neg (P\Rightarrow Q)$ is $P\wedge \neg Q$. For $n=2$ the hypothesis is true and the conclusion false, so the conditional is false, and its negation is true: $2$ is prime and not odd. For $n=9$ the hypothesis is false, since $9=3\times 3$, so the conditional is vacuously true. For $n=7$ both parts are true and so is the conditional. The claim "every prime is odd" is therefore false, and $n=2$ is the counterexample: an integer at which the negation holds.

Now you. Negate "if $x>2$, then $x^2>4$", and decide whether the conditional is true for $x=3$, $x=-3$ and $x=1$.

The biconditional

The fifth connective is the biconditional, $P⟺Q$, read "$P$ if and only if $Q$" and often abbreviated "$P$ iff $Q$". It is true when $P$ and $Q$ have the same truth value, and false when they differ.

The fifth and sixth columns agree in every row, so a biconditional says exactly that each part implies the other. That is why proving an "if and only if" takes two proofs, one for each direction, and why the lesson on direct proof labels them $(\Rightarrow )$ and $(\Leftarrow )$. The biconditional is also the negation of the exclusive or: $P⟺Q$ is true where $P\oplus Q$ is false, and the reverse.

A true biconditional says that two conditions are interchangeable. "An integer $n$ is divisible by $6$ if and only if it is divisible by both $2$ and $3$" means that, for each integer, the two sides are both true or both false, so one may be replaced by the other anywhere. Mathematicians spend a great deal of effort finding such equivalences, because each one gives two ways to think about the same thing.

The biconditional is not the same as equality of statements, but it behaves like it. For every $P$, $P⟺P$ is true; if $P⟺Q$ then $Q⟺P$; and if $P⟺Q$ and $Q⟺R$, then $P⟺R$. The last fact justifies chains such as "$x^2-5x+6=0$ if and only if $(x-2)(x-3)=0$ if and only if $x=2$ or $x=3$", where each link is a separate equivalence and the chain concludes that the first and last are equivalent.

Tautologies, contradictions and valid arguments

A truth table can be built for any compound statement, one column per piece, working outwards from the atomic statements. With two atomic statements there are $4$ rows; with three there are $8$; with $n$ there are $2^n$, since each atomic statement independently takes one of two values. By convention the rows are listed systematically: the first variable is T in the top half and F in the bottom half, the second alternates in blocks half as long, and so on down to the last, which alternates every row.

Some compound statements come out true in every row, whatever their parts say. Such a statement is a tautology. One that is false in every row is a contradiction, and one that is neither is contingent. Three tautologies are basic enough to have names.

• The law of excluded middle, $P\vee \neg P$: every statement is true or its negation is.
• The law of non-contradiction, $\neg (P\wedge \neg P)$: no statement is true together with its negation.
• The law of identity, $P\Rightarrow P$.

Their tables have two rows each and are immediate. A tautology stays a tautology when its atomic statements are replaced by any statements at all, however complicated, since the table never looked at what they said. So $(x>3)\vee \neg (x>3)$ is true for every $x$, and so is $(P\wedge Q)\vee \neg (P\wedge Q)$.

One tautology explains a remark in the previous lesson, that a system of axioms must be free of contradictions. The statement $(P\wedge \neg P)\Rightarrow Q$ is a tautology: its hypothesis is false in every row, so the conditional is vacuously true in every row, whatever $Q$ is. So from a contradiction, every statement follows. This is the principle of explosion, and it means that a single contradiction among the axioms would make every statement a theorem, including every false one. The lesson on contrapositive and contradiction turns the same fact into a method: if an assumption leads to a contradiction, the assumption is false.

Tautologies of the form "if these premises, then this conclusion" are the valid patterns of reasoning. An argument with premises $P_1,\dots ,P_k$ and conclusion $C$ is valid when $(P_1\wedge \cdots \wedge P_k)\Rightarrow C$ is a tautology, which means: in no row are all the premises true and the conclusion false. Validity is about form, not truth. A valid argument with a false premise may have a false conclusion; what it cannot do is lead from true premises to a false conclusion. The patterns used most often in proofs are these.

• Modus ponens: from $P$ and $P\Rightarrow Q$, conclude $Q$. Every application of a theorem is one: the theorem is $P\Rightarrow Q$, and checking its hypothesis gives $P$.
• Modus tollens: from $P\Rightarrow Q$ and $\neg Q$, conclude $\neg P$.
• Hypothetical syllogism: from $P\Rightarrow Q$ and $Q\Rightarrow R$, conclude $P\Rightarrow R$. This is how results chain together.
• Disjunctive syllogism: from $P\vee Q$ and $\neg P$, conclude $Q$.
• Proof by cases: from $P\vee Q$, $P\Rightarrow R$ and $Q\Rightarrow R$, conclude $R$.

Two invalid patterns are common enough to have names too. Affirming the consequent argues from $P\Rightarrow Q$ and $Q$ to $P$: "if $n$ is divisible by $4$ then $n$ is even; $n$ is even; so $n$ is divisible by $4$", which fails at $n=6$. Denying the antecedent argues from $P\Rightarrow Q$ and $\neg P$ to $\neg Q$: "if $n$ is divisible by $4$ then $n$ is even; $n$ is not divisible by $4$; so $n$ is not even", which fails at $n=6$ too.

Example. Show that hypothetical syllogism is valid: $((P\Rightarrow Q)\wedge (Q\Rightarrow R))\Rightarrow (P\Rightarrow R)$ is a tautology.

With three atomic statements there are eight rows. Write $H$ for the hypothesis $(P\Rightarrow Q)\wedge (Q\Rightarrow R)$.

The last column is T in every row, so the statement is a tautology.

There is a faster way, and it scales better. A conditional is false only when its hypothesis is true and its conclusion false, so look for such a row and see whether one can exist. For the conclusion $P\Rightarrow R$ to be false, $P$ must be T and $R$ must be F. For the hypothesis to be true, both $P\Rightarrow Q$ and $Q\Rightarrow R$ must be T. With $P$ true, $P\Rightarrow Q$ forces $Q$ true; with $R$ false, $Q\Rightarrow R$ forces $Q$ false. $Q$ cannot be both, so no falsifying row exists, and the statement is a tautology. This is the same search as in the table, organised by working backwards from the one row that could do damage.

Now you. Show that modus tollens is valid, that is, $((P\Rightarrow Q)\wedge \neg Q)\Rightarrow \neg P$ is a tautology, and that affirming the consequent is not, by finding a row in which $((P\Rightarrow Q)\wedge Q)\Rightarrow P$ is false. Give an instance of the second with real numbers.

Logical equivalence and its laws

Two compound statements are logically equivalent when they have the same truth value in every row of their truth table. Equivalently, $A$ and $B$ are equivalent when $A⟺B$ is a tautology. Since the table lists every case, checking the rows is a complete proof. Equivalent statements say the same thing in different words, and a proof may replace either by the other at any point. Note that $\neg (P\wedge Q)$, which denies the whole conjunction, is a different thing from $\neg P\wedge Q$, where $\neg$ applies only to $P$.

The most useful equivalences say how to negate an "and" or an "or". To deny that two things both hold is to say that at least one fails, and to deny that at least one holds is to say that both fail. These are De Morgan's laws, after Augustus De Morgan, who stated them in 1847, and they are what a proof needs whenever it must say what the failure of a condition looks like.

Example. Show that $\neg (P\wedge Q)$ and $\neg P\vee \neg Q$ are equivalent, and use this to negate "$x>0$ and $x<5$".

Compute both columns in each of the four rows.

The fourth and seventh columns agree in every row, so the two statements are equivalent. Now let $P$ be "$x>0$" and $Q$ be "$x<5$". The negation of $P\wedge Q$ is $\neg P\vee \neg Q$, and the negations of the parts are "$x\le 0$" and "$x\ge 5$". So the negation of "$x>0$ and $x<5$" is "$x\le 0$ or $x\ge 5$".

Now you. Show that $\neg (P\vee Q)$ and $\neg P\wedge \neg Q$ are equivalent, and use this to negate "$x<0$ or $x>1$".

The common error is to negate the parts and leave the connective alone. "Not ($x>0$ and $x<5$)" is not "$x\le 0$ and $x\ge 5$", which no number satisfies. Negating a compound always turns "and" into "or" or the reverse.

De Morgan's laws are two entries in a short list of standard equivalences, each checked by a truth table of at most eight rows. In the list, $\mathrm{T}$ stands for any tautology and $\mathrm{F}$ for any contradiction.

Two of these deserve comment. Material implication says that "if $P$ then $Q$" is the same as "not $P$, or $Q$": the conditional is false only when $P$ is true and $Q$ false, which is exactly when $\neg P\vee Q$ is false. It is the bridge that lets conditionals be handled with the laws for $\wedge$, $\vee$ and $\neg$. The distributive laws come in two forms, and the second, with $\vee$ distributing over $\wedge$, has no counterpart in arithmetic, where $a+bc$ is not $(a+b)(a+c)$. Logic is more symmetric than arithmetic: every law in the list stays a law when $\wedge$ and $\vee$ are exchanged and $\mathrm{T}$ and $\mathrm{F}$ are exchanged, a fact called duality.

The laws turn logic into algebra. Because the truth value of a compound depends only on the truth values of its parts, replacing any part by an equivalent part gives an equivalent whole. So an equivalence can be proved by a chain of rewritings, each justified by a law, in place of a truth table. For three or four atomic statements the chain is usually shorter than the table, and it often shows why the equivalence holds. It gives, for instance, a two-line derivation of the negation of a conditional: $\neg (P\Rightarrow Q)$ is equivalent to $\neg (\neg P\vee Q)$ by material implication, which is equivalent to $\neg \neg P\wedge \neg Q$ by De Morgan, and so to $P\wedge \neg Q$ by double negation.

Example. Prove, using the laws, that $(P\Rightarrow Q)\wedge (P\Rightarrow R)$ is equivalent to $P\Rightarrow (Q\wedge R)$, and say what the equivalence means for proofs.

Each line is equivalent to the one before, so the first is equivalent to the last. For proofs, it says that to prove "if $P$ then both $Q$ and $R$" it is enough to prove "if $P$ then $Q$" and "if $P$ then $R$" separately, and conversely. The proof that $6\mid n$ gives both $2\mid n$ and $3\mid n$ in the lesson on direct proof is of this shape.

Now you. Prove, using the laws, that $(P\Rightarrow R)\wedge (Q\Rightarrow R)$ is equivalent to $(P\vee Q)\Rightarrow R$, and say what it means for proofs.

Converse, inverse and contrapositive

Swapping and negating the parts of $P\Rightarrow Q$ gives three new conditionals: the converse $Q\Rightarrow P$, the inverse $\neg P\Rightarrow \neg Q$, and the contrapositive $\neg Q\Rightarrow \neg P$. Their tables settle which say the same thing as the original.

The contrapositive agrees with the original in every row, so the two are equivalent. The converse and inverse agree with each other (the inverse is the contrapositive of the converse) and differ from the original in the middle two rows. So a proof of $\neg Q\Rightarrow \neg P$ is a proof of $P\Rightarrow Q$, which the lesson on contrapositive and contradiction turns into a method, while a proof of $P\Rightarrow Q$ says nothing about $Q\Rightarrow P$. Treating it as if it did is the commonest logical error in student proofs.

The equivalence with the contrapositive also follows from the laws, without a table: $P\Rightarrow Q$ is equivalent to $\neg P\vee Q$ by material implication, to $Q\vee \neg P$ by commutativity, to $\neg \neg Q\vee \neg P$ by double negation, and so to $\neg Q\Rightarrow \neg P$ by material implication again.

Example. Write the converse, inverse and contrapositive of "if $n$ is divisible by $6$, then $n$ is divisible by $3$", and decide which are true for every integer $n$.

The statement is true: if $n=6k$ for an integer $k$, then $n=3(2k)$, and $2k$ is an integer. The converse is "if $n$ is divisible by $3$, then $n$ is divisible by $6$", which is false, since $n=3$ is divisible by $3$ and not by $6$. The inverse is "if $n$ is not divisible by $6$, then $n$ is not divisible by $3$", and $n=3$ refutes it too, as it must, being equivalent to the converse. The contrapositive is "if $n$ is not divisible by $3$, then $n$ is not divisible by $6$", which is true because it is equivalent to the original.

Now you. For real numbers $x$, write the converse, inverse and contrapositive of "if $x>3$, then $x^2>9$", and decide which are true.

A conditional and its converse are independent: all four combinations of truth values occur. Both can be true ("if $n$ is even then $n+1$ is odd" and its converse), the statement can be true and its converse false (the Example), the reverse can happen (swap the parts of the Example), and both can be false ("if $n$ is prime then $n$ is odd", refuted by $2$, and its converse, refuted by $9$). When both are true, the statement and its converse together make a biconditional.

Necessary, sufficient, only if, unless

When $P\Rightarrow Q$ holds, $P$ is a sufficient condition for $Q$: having $P$ guarantees $Q$. And $Q$ is a necessary condition for $P$: without $Q$ there is no $P$, which is the contrapositive read aloud. Divisibility by $6$ is sufficient for divisibility by $3$, and divisibility by $3$ is necessary for divisibility by $6$. These are one fact seen from its two ends. A condition that is necessary and sufficient for $Q$ is one equivalent to it: "a necessary and sufficient condition for $n$ to be divisible by $6$ is that it be divisible by $2$ and by $3$."

"$P$ only if $Q$" also means $P\Rightarrow Q$. "Only" marks the necessary condition, which is the conclusion: "$n$ is divisible by $4$ only if $n$ is even" says divisibility by $4$ cannot happen without evenness. By contrast "$P$ if $Q$" means $Q\Rightarrow P$. The two are opposite, so together they make "if and only if": $P⟺Q$ is the same as $(P\Rightarrow Q)\wedge (Q\Rightarrow P)$, a condition both necessary and sufficient. That is why proving an "if and only if" takes two proofs, one per direction.

"$P$ unless $Q$" means that if $Q$ fails, then $P$ holds: $\neg Q\Rightarrow P$, which by material implication and double negation is $Q\vee P$. So "unless" is, for a logician, just "or". "The equation has a real solution unless its discriminant is negative" says: if the discriminant is not negative, there is a real solution. It makes no claim about what happens when the discriminant is negative; in conversation "unless" often suggests the converse too, and in mathematics it does not.

Several other phrases are common, and each has a fixed translation.

One convention catches every newcomer. Definitions are written with "if", as in "an integer $n$ is even if $n=2k$ for some integer $k$", but a definition is always read as "if and only if". The previous lesson used its definitions in both directions, producing a $k$ from an even number and concluding evenness from a $k$, and was right to. Theorems get no such licence: in a theorem, "if" means only "if".

Normal forms

Every compound statement, however tangled, can be rewritten in one of two standard shapes, and the rewriting can be read straight off the truth table.

A literal is an atomic statement or the negation of one, such as $P$ or $\neg Q$. A statement is in disjunctive normal form (DNF) if it is a disjunction of terms, each of which is a conjunction of literals, as in $(P\wedge \neg Q)\vee (\neg P\wedge Q\wedge R)$. It is in conjunctive normal form (CNF) if it is a conjunction of clauses, each of which is a disjunction of literals, as in $(P\vee Q)\wedge (\neg P\vee R)$. The names say which connective is on the outside: DNF is an "or" of "and"s, CNF an "and" of "or"s. A single literal, or a single term, counts as a (short) disjunction or conjunction.

The key observation is that each row of a truth table can be described by a conjunction of literals that is true in that row and in no other. For the row in which $P$ is T, $Q$ is F and $R$ is T, the conjunction is $P\wedge \neg Q\wedge R$: it is true exactly when $P$ is true, $Q$ is false and $R$ is true. Now take any truth table. Write down the conjunction for each row in which the statement is T, and join them with $\vee$. The result is true in a row exactly when one of its terms is true there, which happens exactly when that row is one of the T rows. So it has the given truth table, and it is in disjunctive normal form.

Conjunctive normal form comes from the F rows in the same way. For each row in which the statement is F, write the disjunction of literals that is false in that row and in no other: for the row $P$ T, $Q$ F, $R$ T it is $\neg P\vee Q\vee \neg R$, which fails only when every literal fails. Join these clauses with $\wedge$. The result is false in a row exactly when one of its clauses is false there, that is, exactly in the F rows.

Example. The majority statement $M$ of $P$, $Q$ and $R$ is true exactly when at least two of the three are true. Find a DNF and a CNF for $M$, and simplify them.

The DNF is the disjunction of the four row conjunctions of the T rows:

and the CNF is the conjunction of the four row disjunctions of the F rows:

Both are correct and both are clumsy. The laws shorten them. The first two terms of the DNF share $P\wedge Q$, and by the distributive law their disjunction is $(P\wedge Q)\wedge (R\vee \neg R)$, which is $P\wedge Q$ by the complement and identity laws. More directly, $(P\wedge Q)\vee (P\wedge R)\vee (Q\wedge R)$ is true exactly when some two of the three are true, which is exactly when at least two are true, so it is a shorter DNF for $M$. The same reasoning applied to the CNF gives $(P\vee Q)\wedge (P\vee R)\wedge (Q\vee R)$: this is true exactly when every pair contains a true statement, that is, when at most one of the three is false. The two short forms are duals of each other, as the duality principle predicts.

Now you. Find a CNF and a DNF for $(P\Rightarrow Q)\Rightarrow R$ from its truth table, and check them against a short form obtained with the laws.

Normal forms give every statement a standard shape. Two statements in the same atomic statements are equivalent exactly when their full DNFs (one term per T row) have the same terms, and SAT solvers take their input in CNF. The Logic course's lesson on normal forms treats them from a logician's side. The construction also proves something stronger, which is the subject of the next section.

Functional completeness

A truth function of $n$ variables is any rule that assigns T or F to each of the $2^n$ rows of a truth table. Each connective is one: $\wedge$ is the truth function of two variables with a T in the first row only. Since each of the $2^n$ rows may independently get T or F, there are $2^{2^n}$ truth functions of $n$ variables. For two variables that is $2^4=16$, and the five connectives of this lesson are just the most useful of the sixteen. The question is whether they, or fewer, are enough to express the others. A set of connectives is functionally complete if every truth function, of any number of variables, is the truth table of some statement built from atomic statements using only those connectives.

Theorem. The set $\{\neg ,\wedge ,\vee \}$ is functionally complete.

Proof. Let a truth function of $n$ variables $P_1,\dots ,P_n$ be given. If it is F in every row, it is the truth table of $P_1\wedge \neg P_1$, which uses only $\neg$ and $\wedge$. Otherwise it has at least one T row, and the construction of the previous section produces a statement in disjunctive normal form, built from $\neg$, $\wedge$ and $\vee$ alone, that is true in exactly the T rows. Its truth table is therefore the given one. $\square$

Fewer connectives suffice. By De Morgan's law and double negation, $P\vee Q$ is equivalent to $\neg (\neg P\wedge \neg Q)$, so every $\vee$ in a statement can be replaced by $\neg$ and $\wedge$ without changing its truth table.

Corollary. The sets $\{\neg ,\wedge \}$, $\{\neg ,\vee \}$ and $\{\neg ,\Rightarrow \}$ are functionally complete.

Proof. The first was just shown. For the second, $P\wedge Q$ is equivalent to $\neg (\neg P\vee \neg Q)$, so $\wedge$ can be removed in favour of $\neg$ and $\vee$. For the third, $P\vee Q$ is equivalent to $\neg P\Rightarrow Q$ by material implication (and double negation), so $\vee$ can be removed from $\{\neg ,\vee \}$ in favour of $\neg$ and $\Rightarrow$. In each case every statement in the complete set $\{\neg ,\wedge ,\vee \}$ can be rewritten, one connective at a time, into an equivalent statement using only the smaller set. $\square$

Remarkably, a single connective is enough. The NAND ("not and") connective, $P\uparrow Q$, is defined to be equivalent to $\neg (P\wedge Q)$: it is false only when both parts are true.

Theorem. The set $\{\uparrow \}$ is functionally complete.

Proof. Since $\{\neg ,\wedge \}$ is complete, it is enough to express $\neg$ and $\wedge$ using $\uparrow$ alone. First, $P\uparrow P$ is equivalent to $\neg (P\wedge P)$, which is $\neg P$ by the idempotent law. Second, $P\wedge Q$ is equivalent to $\neg \neg (P\wedge Q)$, which is $\neg (P\uparrow Q)$, and by the first part that is $(P\uparrow Q)\uparrow (P\uparrow Q)$. So every statement built with $\neg$ and $\wedge$ can be rewritten with $\uparrow$ alone. $\square$

Henry Sheffer published this in 1913, and NAND is often called the Sheffer stroke; Charles Sanders Peirce had noticed it around 1880 but did not publish. The same is true of NOR, $P\downarrow Q$, equivalent to $\neg (P\vee Q)$, which Problem 11 asks you to prove.

Not every set of connectives is complete, and proving that one is not needs a different kind of argument: some property that all the statements built from the set share, and some truth function that lacks it.

Theorem. The set $\{\wedge ,\vee \}$ is not functionally complete. In particular, $\neg P$ cannot be expressed using $\wedge$ and $\vee$ alone.

Proof. Consider the row in which every atomic statement is true. Every atomic statement is true in that row. If two statements $A$ and $B$ are both true in that row, then so are $A\wedge B$ and $A\vee B$. Every statement built from atomic statements with $\wedge$ and $\vee$ is made by finitely many such steps, starting from atomic statements, and each step keeps the property, so every such statement is true in the all-true row. But $\neg P$ is false in the row where $P$ is true. So no statement built with $\wedge$ and $\vee$ has the truth table of $\neg P$. $\square$

The argument, "the building blocks have the property, and each way of combining them preserves it", is an instance of structural induction, which the lesson on induction makes precise. It proves more than the theorem states: adding $\Rightarrow$ and $⟺$ to the set does not help, since $A\Rightarrow B$ and $A⟺B$ are also true whenever $A$ and $B$ are. Every complete set must contain some connective that can turn truth into falsehood.

What connectives cannot say

The five connectives are now fixed, the negation of each compound can be written down mechanically, and every truth table can be expressed with them. Yet the argument for the conditional's table used something no connective contains. "For every integer $n$, if $n$ is divisible by $4$, then $n$ is even" is not a conditional between two statements, since "$n$ is divisible by $4$" is an open sentence; the phrase "for every integer $n$" is what made the whole a true statement. Refuting "every prime is odd" needed the opposite phrase: there is a prime that is not odd. Nearly every theorem is about all numbers or some number, and neither "all" nor "some" can be built from the five connectives. The next lesson adds them, with rules for negating them that turn "not every" into "some fails".

Problems

Work each problem on paper before opening anything; for Core and Challenge problems, try the hint before the solution.

Warm-up

1. Which of these are statements? For each statement, give its truth value. (a) $7$ is a factor of $91$. (b) $x^2\ge 0$. (c) Factorise $x^2-1$. (d) Every prime greater than $2$ is odd. (e) $2^{100}+1$ is prime.

2. Write out the truth tables of $\neg P\vee (P\wedge Q)$ and of $P\Rightarrow Q$, and decide whether they are equivalent. Then show the same thing using the laws.

3. A triangle is isosceles if at least two of its sides are equal, and equilateral if all three are. For the statement "if a triangle is equilateral, then it is isosceles", write the converse, the inverse, the contrapositive and the negation, and say which are true for every triangle.

4. Let $P$ be "$n$ is prime", $Q$ be "$n$ is odd" and $R$ be "$n>2$", for a positive integer $n$. Translate each sentence into symbols. (a) $n$ is prime only if $n$ is odd. (b) $n>2$ is sufficient for $n$ to be odd. (c) Being odd is necessary for $n$ to be prime, provided $n>2$. (d) $n$ is not prime unless it is odd. (e) $n$ is odd if it is prime and greater than $2$.

Core

5. Prove the distributive law "$P\wedge (Q\vee R)$ is equivalent to $(P\wedge Q)\vee (P\wedge R)$" by a truth table. Then deduce the other distributive law, "$P\vee (Q\wedge R)$ is equivalent to $(P\vee Q)\wedge (P\vee R)$", without a table.

6. Prove or disprove each claim. (a) $(P\Rightarrow Q)\Rightarrow R$ is equivalent to $P\Rightarrow (Q\Rightarrow R)$. (b) $P\Rightarrow (Q\Rightarrow R)$ is equivalent to $(P\wedge Q)\Rightarrow R$. (c) $(P\Rightarrow Q)\vee (Q\Rightarrow P)$ is a tautology. (d) $(P⟺Q)⟺R$ is equivalent to $P⟺(Q⟺R)$.

7. Find the flaw. A student writes: "To negate a conditional, negate both of its parts. So the negation of $P\Rightarrow Q$ is $\neg P\Rightarrow \neg Q$, and the negation of 'if $n$ is divisible by $4$, then $n$ is even' is 'if $n$ is not divisible by $4$, then $n$ is not even'."

8. On an island, every inhabitant is either a knight, who always tells the truth, or a knave, who always lies. (a) Inhabitant A says: "At least one of us two is a knave." What are A and B? (b) On another occasion, C says "D is a knight", and D says "C and I are of opposite types". What are C and D? In each part, write the information as statements with connectives and solve.

9. Using the laws of the section on logical equivalence, and no truth tables, prove: (a) $\neg (P\vee (\neg P\wedge Q))$ is equivalent to $\neg P\wedge \neg Q$; (b) $(P\wedge Q)\vee (P\wedge \neg Q)$ is equivalent to $P$; (c) $P\Rightarrow (Q\Rightarrow P)$ is a tautology.

10. Let $E$ be the statement "exactly one of $P$, $Q$, $R$ is true". Write $E$ in disjunctive normal form. Then prove that

is a conjunctive normal form for $E$, that is, that it has the same truth table.

11. The NOR connective $P\downarrow Q$ is defined to be equivalent to $\neg (P\vee Q)$. Prove that $\{\downarrow \}$ is functionally complete, and write $P\wedge Q$ and $P\Rightarrow Q$ using $\downarrow$ alone.

12. Prove that $\{\Rightarrow \}$ is not functionally complete, but that $\{\Rightarrow ,\mathrm{F}\}$ is, where $\mathrm{F}$ is a constant statement that is false in every row.

Challenge

13. A binary connective $\circ$ is Sheffer if $\{\circ \}$ is functionally complete by itself. Prove that NAND and NOR are the only Sheffer connectives among the sixteen binary connectives.