Discrete Mathematics and Proof

And and or: conjunction and disjunction

Two claims are joined into one sentence, by “and” or by “or”. When does the whole sentence count as true, and how do you list every case at once so nothing is missed?

Unlocks

Building a truth table for a compound statementDiscrete Mathematics and Proof Modus tollens, ruling out, and a common fallacyDiscrete Mathematics and Proof

Where you are 9 in Logic

Logic, proof and discrete math6

Logic9

And and or: conjunction and disjunction

Statements and negation Conditionals, converse, inverse, contrapositive Quantifiers4 Biconditional ▾ Show all 9 (4 more)

Why this exists

A single statement is true or false on its own: “12 is even” needs no help from anywhere else to be decided. Most of the claims worth making, though, are built out of smaller ones. “The number is even and it is greater than 10” is really two statements riding on one sentence. And a great deal of mathematics does not pin down a single answer at all: solve x^2 = 9 and the honest answer is “x = 3 or x = -3”; divide a whole number by 2 and the remainder is 0 or 1.

English already has the two joining words, “and” and “or”, but it is loose about both. “She opened the door and walked in” quietly means first one, then the other, while “2 is even and 3 is odd” carries no order at all. “You can have cake or ice cream” usually means pick one, while “is anyone here hungry or thirsty?” plainly includes the person who is both. A proof that leans on these words has to know exactly what it is allowed to conclude, so mathematics fixes each of them to one meaning. “And” keeps its demand that both halves hold and loses any sense of order or cause. “Or” means at least one, both included. The joined statements are the conjunction and the disjunction, two of the basic logical connectives, and the clearest way to see everything they do is to list every case in a truth table.

Definition

Conjunction: and

Let P and Q be statements. Their conjunction, written P \land Q and read “P and Q”, is the statement that is true when P and Q are both true, and false in every other case.

Disjunction: or

Their disjunction, written P \lor Q and read “P or Q”, is the statement that is true when at least one of P and Q is true, including when both are. It is false in exactly one case: when P and Q are both false. The two statements it joins are its disjuncts.

This is called inclusive or, because the case where both parts are true is included. The reading “one or the other, but not both” is a different connective, exclusive or, written P \oplus Q: it is true when exactly one part is true. In mathematics “or” always means inclusive or, unless the words “but not both” are said.

Only the truth values matter

What P and Q say plays no part, only whether each is true. “7 is prime and Tuesday comes before Wednesday” has two parts with nothing to do with each other, but both are true, so it is a true statement. “7 is odd or the moon is made of cheese” is true too, because its first part is. This is what it means to call \land and \lor truth-functional: the truth value of the whole is a function of the truth values of the parts alone, worked out the same way whatever the parts say. It is also why letters P, Q, R are used for statements in the first place: once only true or false is in play, the letters could stand for anything.

P and Q do not have to be simple. Either one can itself be a compound statement, built with “not”, with another “and” or “or”, or with if and only if, and the rule does not change: find the truth value each side ends up with, then apply the definition.

Intuition

Picture the statement P as marking out a region, the cases where P holds, and Q as marking out another. P \land Q is the region where both markings land on the same case at once.

Figure 1P \land Q is true exactly in the shaded overlap, where both circles hold at once.

The shaded lens is smaller than either circle alone, and that is the whole personality of “and”: joining a second requirement can only narrow things down, never widen them. Whatever satisfies P \land Q satisfies P by itself and Q by itself; the reverse need not hold.

P \lor Q is the opposite picture. It is true everywhere inside either circle: the whole shaded area in the left panel below, overlap included. It is false only in the corner marked “neither”. The right panel shows the reading mathematics does not use, exclusive or, which leaves the overlap blank. The two panels differ only in the overlap, the one case where P and Q are both true.

Figure 2Inclusive “or” (left) shades the overlap where both are true. “One but not both” (right) leaves it out.

So the two connectives are mirror images. A conjunction is hard to make true, since every part must hold, and easy to make false, since one failure is enough. A disjunction is a modest claim: it promises that at least one part holds and says nothing about which, so it is easy to make true and hard to make false. When the statements are about a number x, the circles become sets of numbers: “and” keeps the intersection of the two solution sets, and “or” keeps their union.

Results

Truth conditions.

P \land Q \text{ is true} \iff P \text{ is true and } Q \text{ is true}

P \lor Q \text{ is false} \iff P \text{ is false and } Q \text{ is false}

To show a conjunction true, every part must be shown true; to show it false, one false part is enough. A disjunction is the other way round: one true part makes it true, and only every part false makes it false.

The truth table for and

Each of P and Q is true (T) or false (F). For each choice for P there are two for Q, so there are 2 \times 2 = 4 combinations and no others, by the counting principle. A truth table gives each combination one row. The usual order puts T before F and lets the first letter change slowest: P is T in the top two rows and F in the bottom two, while Q alternates. Any order would list the same four cases, but a fixed one lets two tables be compared line by line and makes a missing row easy to spot. The last column is then filled row by row with the one question the definition asks: are both entries T?

Row	P	Q	P \land Q
1	T	T	T
2	T	F	F
3	F	T	F
4	F	F	F

Exactly one row is true. A row where P \land Q is true must have T under both letters. That fixes both entries, and the table lists each combination once, so the “and” column always has one T and three F, whatever P and Q say.

Reading it backwards. If P \land Q is true you are in row 1, and both parts are pinned down. If it is false you are in row 2, 3 or 4, and the table shows how little that says: each part is true in some of those rows and false in others.

The truth table for or

Over the same four rows, mark T wherever at least one entry is T:

Row	P	Q	P \lor Q
1	T	T	T
2	T	F	T
3	F	T	T
4	F	F	F

Exactly one row is false: row 4, the only combination with neither part true. So an “or” column is F exactly where both of its input columns read F, which is the fast way to fill one inside a larger table: mark F where both inputs are F, and T everywhere else. The “and” column is the mirror image, T exactly where both inputs read T.

Reading it backwards. If P \lor Q is false, only row 4 fits, so both parts are false. If it is true, three rows fit, and the table alone cannot tell you which part holds. One more fact narrows it: learning that P is false leaves only row 3, so Q is true. That step is the disjunctive syllogism, the ruling out of one case to leave the other.

More than two parts

Three letters give 2^3 = 8 rows. The first letter is T for the top half and F for the bottom half, the next splits each half in two, and the last alternates. Side by side, a chain of “and”s and a chain of “or”s look like this, with the column headed “and” standing for P \land Q \land R and the column headed “or” for P \lor Q \lor R:

Row	P	Q	R	and	or
1	T	T	T	T	T
2	T	T	F	F	T
3	T	F	T	F	T
4	T	F	F	F	T
5	F	T	T	F	T
6	F	T	F	F	T
7	F	F	T	F	T
8	F	F	F	F	F

With n letters there are 2^n rows. A conjunction of all n is true in exactly one row, the one with T in every column. A disjunction of all n is false in exactly one row, the one with F in every column, so it is true in 2^n - 1 rows. Each letter added doubles the rows and leaves that one special row alone.

Exclusive or

P \oplus Q, “P or Q, but not both”, is true when exactly one part is true. Beside the inclusive column:

Row	P	Q	P \lor Q	P \oplus Q
1	T	T	T	F
2	T	F	T	T
3	F	T	T	T
4	F	F	F	F

The columns differ only in row 1, where both parts are true. Exclusive or is inclusive or with row 1 struck out, which is just what “P or Q, and not both” says: (P \lor Q) \land \neg(P \land Q) has the column F, T, T, F, the same as P \oplus Q. (Here \neg, read “not”, flips a truth value.)

Laws of and and or

Order does not matter. P \land Q and Q \land P always have the same truth value, and so do P \lor Q and Q \lor P.

Grouping does not matter. (P \land Q) \land R and P \land (Q \land R) agree in every case, and so do (P \lor Q) \lor R and P \lor (Q \lor R). So chains can be written P \land Q \land R and P \lor Q \lor R with no brackets at all.

Simplification. If P \land Q is true, then P is true, and Q is true, each on its own. Read the other way, this is how a conjunction is proved: show P, then show Q, as two separate pieces of work.

A true part settles an or. If Q is true, then P \lor Q is true, whatever P is. In particular, whenever P \land Q is true, so is P \lor Q.

A false part can be dropped from an or. If Q is false, then P \lor Q has the same truth value as P.

Something always holds, and nothing holds with its opposite. P \lor \neg P is true for every statement P, which is the law of the excluded middle, and P \land \neg P is false for every P.

Why it is true

Every one of these follows from the two truth conditions by checking what they demand, not from any new assumption.

The tables. A row of the “and” column is T only when both entries are T, and exactly one of the four combinations is T, T. A row of the “or” column is F only when both entries are F, and exactly one combination is F, F. With n letters, each letter has 2 values and each choice of values appears once, so there are 2 \times 2 \times \cdots \times 2 = 2^n rows, and the same argument picks out the single all-T row for “and” and the single all-F row for “or”.

Order. P \land Q is true exactly when “P is true and Q is true”; Q \land P exactly when “Q is true and P is true”. These describe the same pair of facts. “At least one of P and Q is true” likewise does not care which is named first. Order was never part of either definition, so swapping it changes nothing.

Grouping. (P \land Q) \land R is true exactly when P \land Q is true and R is true, which happens exactly when P, Q and R are all three true; P \land (Q \land R) comes down to the same requirement. (P \lor Q) \lor R is true when P \lor Q is true or R is, which means when at least one of P, Q, R is true, and P \lor (Q \lor R) has exactly the same condition. The same condition gives the same truth value in all eight rows.

Simplification. Suppose P \land Q is true. The truth condition leaves no way for that to happen except with P true and Q true, so in particular P is true, and Q is too.

A true part, a false part. If Q is true, at least one part of P \lor Q is already true. If Q is false, the only way for at least one part to be true is for P to be true, so P \lor Q is true when P is and false when P is. And if P \land Q is true, both parts are true, so certainly at least one is.

The excluded middle, and its partner. A statement and its negation have opposite truth values, so exactly one of P and \neg P is true. At least one part of P \lor \neg P is true, so it is true; the two parts of P \land \neg P are never true together, so it is false. The excluded middle is what lets a proof split into “either P or not P” and deal with each case in turn.

Exclusive or. (P \lor Q) \land \neg(P \land Q) asks for at least one true part and not both, which is exactly one true part: the definition of P \oplus Q.

Worked examples

Example 1

Deciding the truth value and naming the row

For each statement, decide whether it is true or false, and name the row of the four-row table its two parts fall on.

(a) 12 is even and 12 is a multiple of 5.

(b) 21 is odd and 21 is a multiple of 3.

(d) 4 is odd or 4 > 10.

(e) 5 > 2 or 5 is odd.

(f) 0 is positive or 0 is even.

Solution

Settle each part on its own first, then find the row with that pair of values and read the connective’s column.

(a) 12 = 2 \cdot 6 is even, but 12 \div 5 is not a whole number. The pair is T, F, which is row 2, and an “and” with a false part is false. Once one part was false, the other did not need checking at all.

(b) 21 = 2(10) + 1 is odd, and 21 = 3 \cdot 7 is a multiple of 3. The pair is T, T, row 1, the only row where “and” is true. Here both halves genuinely had to be checked: finding one true part is never enough for a conjunction.

(c) 7 is prime, since its only positive divisors are 1 and 7, but it is not even. The pair is T, F, row 2, and one true part makes the “or” true. The false part does not matter.

(d) 4 is not odd, and 4 > 10 is false. The pair is F, F, row 4, the only way an “or” is false.

(e) 5 > 2 is true, and 5 is odd is true. The pair is T, T, row 1, and inclusive “or” is true there. Reading this “or” as “one but not both” would call it false, which is why the reading has to be fixed in advance.

(f) 0 is not positive, but 0 = 2 \cdot 0 is even. The pair is F, T, row 3, and the “or” is true: one true part is enough, whichever of the two it is.

Example 2

Statements named by letters

Let P be “8 is a perfect cube”, Q be “8 is a perfect square” and R be “8 is even”. Write each statement in words and find its truth value: (a) P \lor Q, (b) \neg P \lor Q, (c) P \lor \neg Q, (d) P \land \neg Q \land R.

Solution

First settle the letters. 8 = 2^3, so P is true. The perfect squares either side of 8 are 4 and 9, so 8 is not one, and Q is false. 8 = 2 \cdot 4, so R is true. That makes \neg P false and \neg Q true.

(a) “8 is a perfect cube or 8 is a perfect square.” P is true, so P \lor Q is true.

(b) “8 is not a perfect cube or 8 is a perfect square.” \neg P and Q are both false, so \neg P \lor Q is false.

(d) “8 is a perfect cube and 8 is not a perfect square and 8 is even.” All three parts, P, \neg Q and R, are true, so the conjunction is true. It makes no difference whether it is read as (P \land \neg Q) \land R or as P \land (\neg Q \land R): by the grouping law both ask for the same three facts.

The negation sign in (b) belongs to one letter only. \neg P \lor Q means “(not P) or Q”, not “not (P or Q)”. The second is a different statement, taken up in De Morgan’s laws.

Example 3

Sentences with a variable

(a) The inequality 2 < x < 5 is shorthand for the conjunction “x > 2 and x < 5”. Decide whether it is true for x = 3, for x = 5 and for x = 0.

(b) For which of the values x = -3, -1, 0, 2, 3 is “x^2 = 9 or x < 0” true?

Solution

With a variable in it, a sentence is neither true nor false yet. Each value of x turns it into a statement, so test each value in both parts.

(a) For x = 3: 3 > 2 is true and 3 < 5 is true, so the conjunction is true. For x = 5: 5 > 2 is true, but 5 < 5 is false, since 5 is not strictly less than itself, so the conjunction is false. For x = 0: 0 > 2 is already false, so the conjunction is false without even looking at the second part.

x = 3 \text{ works,} \qquad x = 5 \text{ and } x = 0 \text{ do not.}

Every compound inequality you have ever solved is a conjunction wearing a shorter notation.

(b) One row per value, with a last column, headed “either”, for the whole sentence “x^2 = 9 or x < 0”:

x	x^2 = 9	x < 0	either
-3	T	T	T
-1	F	T	T
0	F	F	F
2	F	F	F
3	T	F	T

The sentence is true for x = -3, x = -1 and x = 3. The value -3 makes both parts true and still counts, because the “or” is inclusive. The value 0 fails the second part, since 0 < 0 is false.

Example 4

All numbers, some numbers, no numbers

Find every real number x for which each sentence is true.

(a) “x < 4 or x > 1”

(b) “x < 1 or x > 4”

Solution

(a) Take any real number. If it is less than 4, the first part is true. If it is not, it is at least 4, so it is certainly greater than 1, and the second part is true. Either way one part holds, so the sentence is true for every real number. A number between 1 and 4, such as 2, makes both parts true, and inclusive “or” counts it.

(b) Use the truth condition: an “or” fails only where both parts fail. A number that is not less than 1 and not greater than 4 satisfies 1 \le x \le 4. So the sentence is true for every real number except those with 1 \le x \le 4.

(c) A number less than 1 is never greater than 4, so no number makes both parts true at once: the sentence is true for no real number. Each part on its own is true for plenty of numbers, but an “and” needs both of them true of the same number.

Swapping the two numbers in (a) and (b) turned a sentence that is always true into one with a gap in the middle, and changing “or” to “and” in (c) shrank it to nothing. Adding a part to an “or” can only widen what it allows; adding a part to an “and” can only narrow it, sometimes all the way to nothing. Solving sentences like these in general is compound inequalities with and and or.

Example 5

Filtering a list with and, and with or

From the integers 1 to 15, list those that satisfy (a) “n is a multiple of 3 and n is even”, and (b) “n is a multiple of 3 or n is even”.

Solution

The multiples of 3 up to 15 are 3, 6, 9, 12, 15, and the even numbers are 2, 4, 6, 8, 10, 12, 14.

(a) “And” keeps only what both lists share:

\text{(a) the integers } 6 \text{ and } 12

These are exactly the multiples of 6: a number divisible by both 2 and 3 is divisible by 6, and every multiple of 6 is both.

(b) “Or” keeps everything in either list, with 6 and 12, which are in both, written once:

\text{(b) } 2, 3, 4, 6, 8, 9, 10, 12, 14, 15

That is 10 integers, 5 + 7 - 2, since the two shared numbers would otherwise be counted twice. Filtering a list by two conditions joined with “and” is intersection in action, and joining them with “or” is union.

Example 6

Where or comes from when you solve an equation

Solve (x - 3)(2x + 1) = 0.

Solution

A product of two numbers is zero when at least one factor is zero, and in no other case. That is the zero product property behind solving by factoring, and “at least one” is exactly inclusive “or”. So the equation holds exactly when

x - 3 = 0 \ \lor\ 2x + 1 = 0

Solve each part on its own. The first gives x = 3; the second gives 2x = -1, so \displaystyle x = -\frac{1}{2}.

The solutions are x = 3 or \displaystyle x = -\frac{1}{2}. The “or” is not loose phrasing. The solution set is every number that makes the first factor zero together with every number that makes the second zero, and each value really does solve the equation: x = 3 makes the first factor 0, and \displaystyle x = -\frac{1}{2} makes the second factor \displaystyle 2\left(-\frac{1}{2}\right) + 1 = 0.

The inclusive reading is the right one. In (x - 3)(x - 3) = 0 both factors are zero at once when x = 3, and that case must count as a solution.

Example 7

Switches in a row, and many switches

(a) A lamp is wired to a battery through two switches, A and B, one after the other, so current reaches the lamp only by passing through both. Let P be “switch A is closed” and Q be “switch B is closed”. Make a table showing, for each setting, whether the lamp is lit.

(b) In another room 5 switches are wired so that the lamp is on when at least one switch is up. Write the condition with one letter per switch, and count the settings of the switches that turn the lamp on.

Solution

(a) Current passes a closed switch and is stopped by an open one. It must pass both, so the lamp is lit exactly when A is closed and B is closed: “the lamp is lit” has the same truth value as P \land Q in every setting. List the settings in the usual order and apply the rule:

Row	P	Q	lamp lit
1	T	T	T
2	T	F	F
3	F	T	F
4	F	F	F

Of the four settings, only one lights the lamp. Switches in a row, in series, are “and” built out of wire. An AND gate in a computer chip does the same job with voltages: read a high voltage as T and a low one as F, and its output is high only when both inputs are high, so once its signals have settled it follows this table.

(b) Let S_1 be “switch 1 is up”, and so on up to S_5. The lamp is on exactly when S_1 \lor S_2 \lor S_3 \lor S_4 \lor S_5 is true. Each switch is up or down, so the table has 2^5 = 32 rows, one per setting, and none need writing out: a disjunction is false only on the row where every part is false, all five switches down. So the lamp is on in 32 - 1 = 31 settings.

Check. With two switches the count is 2^2 - 1 = 3, which is rows 1, 2 and 3 of the table for P \lor Q.

Example 8

A negated part

Make the truth table for P \land \neg Q, where \neg Q is true exactly when Q is false. In which row is the statement true?

Solution

The second part is \neg Q, not Q, so first give \neg Q its own column by flipping each entry of the Q column. Then apply the “and” rule to the P column and the \neg Q column, ignoring Q itself:

Row	P	Q	\neg Q	P \land \neg Q
1	T	T	F	F
2	T	F	T	T
3	F	T	F	F
4	F	F	T	F

It is true only in row 2, where P is true and Q is false. The “and” column still has exactly one T; it has moved to the row where both of the columns it reads are T. A column made only to feed a later one, like the \neg Q column here, is called a helper column.

Example 9

An or column inside a larger table

Fill in the table for (P \land Q) \lor (\neg P \land \neg Q).

Solution

The statement is an “or” of two pieces, so first give each piece a helper column of its own. P \land Q is true only in row 1. \neg P \land \neg Q says both letters are false, which happens only in row 4. Calling the pieces A = P \land Q and B = \neg P \land \neg Q keeps the headings short.

The last column joins these two with \lor, so it is F exactly where both piece columns read F. That is rows 2 and 3; rows 1 and 4 each have a T in one piece.

Row	P	Q	A	B	A \lor B
1	T	T	T	F	T
2	T	F	F	F	F
3	F	T	F	F	F
4	F	F	F	T	T

The final column is true exactly when P and Q have the same value. That is the column of if and only if, so this statement says the same as P \leftrightarrow Q. Helper columns in general are the business of building a truth table for a compound statement.

Example 10

Working back from the value

(a) You are told that P \land Q is false, and separately that P is true. What can you conclude about Q?

(b) The sentence “x > 5 or x < -5” is false. What can you say about x?

(c) For a whole number n, the statement “n is even or n is a multiple of 5” is true, and n is odd. What can you say about n?

Solution

(a) A false “and” sits on row 2, 3 or 4. P is true, which rules out rows 3 and 4, so only row 2 is left, and there Q is F:

Q \text{ is false.}

This is the mirror image of simplification: a true conjunction hands you both parts for free, and a false conjunction together with one true part hands you the other part’s falsity for free.

(b) A false “or” sits on row 4, so both parts are false. x > 5 being false means x \le 5, and x < -5 being false means x \ge -5. So -5 \le x \le 5.

(c) A true “or” could be on row 1, 2 or 3. The first part, “n is even”, is false, which rules out rows 1 and 2, since both have the first part true. Only row 3 is left, so the second part is true: n is an odd multiple of 5, such as 5, 15 or 25.

Example 11

Not both, or neither?

Someone claims that “not both P and Q”, written \neg(P \land Q), says the same as “neither P nor Q”, written \neg P \land \neg Q. Test the claim with a truth table.

Solution

Two statements say the same thing exactly when their columns agree in every row, so build both over the same four rows. For \neg(P \land Q), flip the P \land Q column:

Row	P	Q	P \land Q	\neg(P \land Q)
1	T	T	T	F
2	T	F	F	T
3	F	T	F	T
4	F	F	F	T

For \neg P \land \neg Q, call it N for “neither”, make columns for \neg P and \neg Q, and apply the “and” rule to those:

Row	P	Q	\neg P	\neg Q	N
1	T	T	F	F	F
2	T	F	F	T	F
3	F	T	T	F	F
4	F	F	T	T	T

The last columns of the two tables disagree in rows 2 and 3, so the claim is false. In row 2, P is true and Q is false: “not both” is true, but “neither” is false, since P holds. The shapes of the columns show why it had to fail. \neg P \land \neg Q is a conjunction, so it has exactly one T, while \neg(P \land Q) is a flipped conjunction with exactly one F.

The difference is where the \neg sits. In \neg P \land \neg Q it belongs to each letter alone, as in Example 2; in \neg(P \land Q) it covers the whole conjunction. The statement that does match \neg(P \land Q) comes from De Morgan’s laws.

Example 12

From a column back to a statement

Two statements S_1 and S_2 about P and Q have the columns below.

Row	P	Q	S_1	S_2
1	T	T	F	T
2	T	F	F	T
3	F	T	T	F
4	F	F	F	T

(a) Write a statement with the same column as S_1 using only P, Q, \neg and \land.

(b) Write a statement with the same column as S_2 using only P, Q, \neg and \lor.

Solution

(a) S_1 is true in exactly one row, which is the mark of a conjunction. In that row, row 3, P is false and Q is true. A conjunction true there and nowhere else must demand both facts: “P is false”, which is \neg P, and “Q is true”, which is Q. Now \neg P \land Q is true when P is F and Q is T, which is row 3 and no other row. So

S_1 \text{ has the same column as } \neg P \land Q.

(b) S_2 is false in exactly one row, which is the mark of a disjunction, false exactly where both its parts are false. So choose two parts that are both F on row 3, where P is false and Q is true, and never both F elsewhere. P is F on row 3, and \neg Q is F wherever Q is true, which includes row 3. On any other row, either P is true (rows 1 and 2) or Q is false, so \neg Q is true (row 4):

Row	P	Q	\neg Q	P \lor \neg Q
1	T	T	F	T
2	T	F	T	T
3	F	T	F	F
4	F	F	T	T

S_2 \text{ has the same column as } P \lor \neg Q.

The same moves work for any single row of any table. For a lone T, take each letter if the row has T there and its negation if it has F, and join them with \land. For a lone F, take each letter if the row has F there and its negation if it has T, and join them with \lor.

Example 13

Proving an or statement by cases

Show that for every integer n, the remainder when n^2 is divided by 4 is 0 or 1.

Solution

Two disjunctions are at work. The conclusion is one: “remainder 0 or remainder 1”. The proof starts from another, which holds for every integer: n is even or n is odd. Because that “or” is true for every n, handling each part separately covers every integer.

If n is even, write n = 2k for an integer k. Then

n^2 = (2k)^2 = 4k^2

which is a multiple of 4, so the remainder is 0.

If n is odd, write n = 2k + 1. Then

\begin{aligned} n^2 &= (2k + 1)^2 \\ &= 4k^2 + 4k + 1 \\ &= 4(k^2 + k) + 1 \end{aligned}

which is one more than a multiple of 4, so the remainder is 1.

In each case one part of the conclusion is true, so the disjunction is true for every integer. Check. 6^2 = 36 = 4 \cdot 9, remainder 0, and 7^2 = 49 = 4 \cdot 12 + 1, remainder 1. Splitting an argument on an “or” you already know is proof by cases, and parity is its commonest split.

Boundaries

Each part must already be a statement. \land and \lor combine things that are each true or false on their own. “x > 2” has no truth value while x is unresolved, and joining it to another open sentence does not fix that, nor can it fill a column of a truth table. It becomes usable once x is given a value, as in the examples above, or once it is quantified, which is its own topic.

Logical “and” has no order. P \land Q and Q \land P are the same statement. Ordinary language often smuggles a “then” into “and” (“she fell and broke her arm”), and that extra meaning is simply not part of \land; if order matters, it has to be said separately.

Mathematical “or” is inclusive unless it says otherwise. A meal that “comes with soup or salad” does not offer both. In mathematics that reading has to be written out, as “P or Q, but not both”, and it is the different connective P \oplus Q, which agrees with P \lor Q in three rows of four.

A disjunction says at least one, not which one. Knowing P \lor Q is true tells you nothing about P alone or about Q alone. Only more information, such as learning that one part is false, settles the other.

More parts still means all of them, or at least one of them. A conjunction with one false part among a hundred true ones is still false, and a disjunction with one true part among a hundred false ones is still true.

\le and \ge are disjunctions in disguise. a \le b means a < b or a = b. That is why 5 \le 5 is true: its second part holds.

Negating swaps the connective. “Not (P and Q)” is true when at least one part fails, and “not (P or Q)” only when both fail, so negating an “and” produces an “or” of negations and negating an “or” produces an “and”. The exact rules are De Morgan’s laws.

A table lists every row, including rows that cannot happen. It treats the letters as free to take any values. If P is “n is a multiple of 4” and Q is “n is even”, then row 2, with P true and Q false, describes no actual number, yet it stays in the table. The table answers a question about form, what the connective does with any pair of truth values; which rows the world allows is knowledge the table does not contain.

Tables double with every letter, and know only two values. 10 letters need 1024 rows, and 30 letters more than a billion. A plain chain of “and”s or “or”s never needs writing out, since its one special row is known in advance, but larger mixed statements do, which is one reason logicians look for methods that avoid tables. And every entry is T or F: a logic with a third value such as “unknown” has nine combinations for two parts, and more than one reasonable way to fill them in.

Where this goes next

The tables for “and” and “or” are two of the small tables every larger one is assembled from. With the table for “not” in Statements and negation, the table for the conditional and the table for if and only if, they are the pieces of a truth table for a compound statement, put together one helper column at a time. A column of all T, such as the one for P \lor \neg P, marks a tautology, and a column of all F, such as the one for P \land \neg P, marks a contradiction. Columns that agree in every row mark logically equivalent statements, and the same row-by-row scan tests whether an argument is valid.

Turning “and” and “or” upside down, working out what their negations look like, is De Morgan’s laws, and it depends on nothing beyond the truth conditions given here. The column of \neg P \lor Q turns out to match “if P then Q”, which is why a conditional can be said without if-then. And the example that turned a column back into a statement points further: any column with at least one T is matched by taking the conjunction for each of its T rows and joining those with “or”. That is how a table is turned back into a formula, and how a circuit designer turns a required table into wiring.

In algebra, “and” is every compound inequality such as 2 < x < 5, and “or” is how solution sets are joined: each time a factored equation splits into pieces, or an absolute value equation such as |x| = 5 becomes x = 5 or x = -5 (absolute value equations), the answer is a disjunction, and its solution set is the union of the pieces. In proof, a conjunction is proved in two separate parts, a known “or” lets you split into cases, and an “or” you want to prove can be reached by supposing one part false and showing the other must then be true.

Exercises

Deciding the truth value

Decide whether each statement is true or false, and name the row of the four-row table its two parts fall on.

15 is odd and 15 is prime.
6 is even or 6 is prime.
\pi is rational and \pi > 3.
9 is prime or 9 < 5.
10 is even and 10 is a multiple of 5.
5 \le 5, read as “5 < 5 or 5 = 5”.
2 is prime or 2 is even.

Statements named by letters

Let P be “15 is divisible by 3”, Q be “15 is divisible by 2” and R be “15 > 20”. Find the truth value of each statement.

\neg P \lor R
Q \lor \neg R
P \land \neg Q \land \neg R
(P \land Q) \lor R

Sentences with a variable

The sentence is “x > 2 or x < 0”. For which of x = -2, 0, 1, 3 is it true?
The sentence is “x > 1 and x < 6”. For which of x = 1, 4, 6, 7 is it true?
List every integer from 1 to 30 that is a multiple of 4 and a multiple of 6.
For which whole numbers n from 1 to 10 is “n is even or n is a multiple of 3” true? How many are there?
Find every real number x for which “x \ge 3 or x < 5” is true.
Find every real number x for which “x^2 < 0 or x + 1 = 4” is true.
Solve (x - 7)(x + 2) = 0, and write the solution as an or statement.
Solve x^2 = 5x, and write the solution as an or statement.

Reading the table, and working back from the value

In row 3 of the four-row table, P is false and Q is true. What are the values of P \land Q, of P \lor Q and of P \oplus Q there?
(a) P \land Q is known to be true. What are the truth values of P and of Q? (b) P \lor Q is known to be false. What are they now?
The sentence “x \ge 2 or x \le -3” is false. What can you say about x?
P \land Q is known to be false, and P is known to be false. Which rows of the table are still possible, and what can you say about Q?
P \land Q is false and Q is true. Which row of the table are you in, and what is P?
P \lor Q is true and P is true. What can you say about Q?
For a whole number n from 1 to 20, “n is a multiple of 3 or n is a multiple of 7” is true, and n is not a multiple of 3. List the possible values of n.
P \lor Q and P \lor \neg Q are both true. What can you say about P, and about Q?

Building tables

Two columns of a table read, top to bottom, A: T, F, T, F and B: F, F, T, T. Fill in the columns for A \lor B and for A \land B.
Make the truth tables for P \land P and for P \lor P. How many rows does each need, and which simpler statement has the same column?
Make the truth table for (P \land Q) \land \neg R. In which row is it true?
In the eight-row table in the usual order, which row is the only one in which \neg P \land Q \land \neg R is true?
Fill in the eight-row column for P \lor (Q \land R), with P, Q, R in the usual order.
Fill in the column for (P \land Q) \lor (P \land \neg Q). Which letter’s column does it match?
For which whole numbers n from 1 to 12 is “n is even \oplus n is a multiple of 3” true? How many are there?
Fill in the column for \neg(P \oplus Q). Which connective has this column?
Show that (P \oplus Q) \oplus Q has the same column as P.

Counting rows and finding statements

How many rows does the table for P_1 \land P_2 \land \cdots \land P_6 have? In how many of them is it true, and in how many is P_1 \lor P_2 \lor \cdots \lor P_6 true?
On how many rows of the eight-row table is P \lor Q \lor R true while P \land Q \land R is false?
A door has four bolts, each either drawn or not, and it opens only when all four are drawn. Of all the possible settings of the bolts, how many keep the door shut?
A conjunction of different letters is false in 127 rows of its table. How many letters does it have?
A statement about P, Q and R is true only in row 7 of the usual eight-row order. Write a statement with that table using only the letters, \neg and \land.
Find a statement made from P and Q whose table is F on row 1 only.

Reasoning

A statement “P \land Q” is announced to be false. Can you conclude that P is false? Explain, and give an example of P and Q that shows your answer.
Explain why the table for P \land Q needs exactly four rows, no more and no fewer.
Using only the truth condition for \land, explain why P \land Q and Q \land P always agree. Then use the four-row table to explain why P \lor Q and Q \lor P always agree.
Suppose P \land Q \land R is true. Show that Q must be true.
Explain why 2 < x < 5 could not mean the same thing if the “and” in “x > 2 and x < 5” were replaced with “or”.
A meal “comes with soup or salad”. Explain how that “or” differs from the one in “n is even or n is prime”, and give a value of n that shows the difference.
P is a true statement. Explain why P \lor Q is true whatever Q says.
Explain why “n is even or n is odd” is true for every integer n, but “n is even or n is prime” is not. Give an integer that makes the second statement false.
Explain why P \lor Q is true whenever P \land Q is true. Then give two statements P and Q for which P \lor Q is true but P \land Q is false.
Use truth tables to show that P \land \neg P is false in every row and P \lor \neg P is true in every row.
Explain why, for any n, a conjunction of n different letters is true in exactly one row of its table, and a disjunction of n different letters is false in exactly one row.
A statement about P and Q is true in exactly two rows of its table. Explain why it cannot have the same table as L \land M, where L is P or \neg P and M is Q or \neg Q.
Explain why every column with exactly one F, over the letters P and Q, is the column of some statement “A \lor B”, where each of A and B is a letter or the negation of one.
Prove that for every integer n, the remainder when n^2 is divided by 3 is 0 or 1.

Answers

Row 2, false. 15 is odd, but 15 = 3 \times 5 is not prime, and one false part makes an “and” false.
Row 2, true. 6 is even, and one true part is enough, even though 6 = 2 \cdot 3 is not prime.
Row 3, false. \pi is rational is false (it is irrational), even though \pi > 3 is true.
Row 4, false. 9 = 3 \cdot 3 is not prime, and 9 < 5 is false. Both parts fail.
Row 1, true. 10 = 2 \cdot 5 is even and a multiple of 5, so both parts hold.
Row 3, true. 5 < 5 is false, but 5 = 5 is true, and one true part is enough.
Row 1, true. 2 is prime and 2 is even, so both parts hold, and inclusive “or” counts that case.
False. 15 = 3 \cdot 5, so P is true and \neg P is false; R is false too. Both parts fail.
True. R is false, so \neg R is true, and one true part is enough.
True. P is true; 15 is odd, so Q is false and \neg Q is true; 15 > 20 is false, so \neg R is true. All three parts hold.
False. Q is false, so P \land Q is false, and R is false. Both parts of the “or” fail.
x = -2 and x = 3, since -2 < 0 and 3 > 2. The values 0 and 1 fail both parts (0 < 0 is false).
x = 4 only. For x = 1, 1 > 1 is false, since 1 is not strictly greater than itself; for x = 6, 6 < 6 is false; for x = 7, 7 < 6 is false. Only x = 4 makes both parts true.
12, 24. A number that is a multiple of both 4 and 6 is a multiple of their smallest common multiple, 12.
2, 3, 4, 6, 8, 9, 10: seven numbers. The even ones are 2, 4, 6, 8, 10 and the multiples of 3 are 3, 6, 9; the number 6 is in both lists and is counted once.
Every real number. A number that is not less than 5 is at least 5, so it is at least 3. Every number satisfies one part or the other.
x = 3 only. x^2 < 0 is false for every real number, so that false part can be dropped, and the sentence is true exactly when x + 1 = 4.
x = 7 or x = -2. The product is zero exactly when x - 7 = 0 or x + 2 = 0.
x = 0 or x = 5. Rewrite as x^2 - 5x = 0, so x(x - 5) = 0, and x = 0 or x - 5 = 0. Dividing both sides by x would lose the solution x = 0.
P \land Q is F, P \lor Q is T and P \oplus Q is T. The row has an F, which is enough to make the “and” false; it has a T, which is enough for the “or”; and exactly one part is true, which is what exclusive or asks.
(a) Both are true: P \land Q is true only in row 1, which has T under both letters. (b) Both are false: P \lor Q is false only in row 4, which has F under both letters.
-3 < x < 2. A false “or” has both parts false: x \ge 2 false gives x < 2, and x \le -3 false gives x > -3.
Rows 3 and 4. Both have P false, so P \land Q is false in each. Q is T in row 3 and F in row 4, so nothing can be said about Q.
Row 3, so P is false. Q is true in rows 1 and 3, and row 1 is ruled out because P \land Q is true there.
Nothing. Rows 1 and 2 both have P true and P \lor Q true, and Q is true on one and false on the other. One true part already settles an “or”, so the “or” carries no news about the other part.
7 and 14. The first part is false, so the second must be true: n is a multiple of 7, and neither 7 nor 14 is a multiple of 3.
P is true; Q could be either. P \lor Q is true on rows 1, 2, 3 and P \lor \neg Q on rows 1, 2, 4. Both hold only on rows 1 and 2, where P is true and Q takes both values.
A \lor B is T, F, T, T and A \land B is F, F, T, F. Only row 2 has F in both columns, so only there is the “or” false; only row 3 has T in both, so only there is the “and” true.
Two rows each, since only one letter appears. Both columns are T, F, the same as the column for P: in each row both parts are the same entry, so both are T, and at least one is T, exactly when P is T.
True only in row 2, where P is T, Q is T and R is F. The P \land Q column is T, T, F, F, F, F, F, F, the \neg R column is F, T, F, T, F, T, F, T, and the final column is F, T, F, F, F, F, F, F.
Row 6. The statement needs P false, Q true and R false. The rows with P false are 5 to 8, and F, T, F is the second of them.
T, T, T, T, T, F, F, F. Q \land R is T, F, F, F, T, F, F, F; the “or” is F only where P is F and Q \land R is F, which is rows 6, 7 and 8.
T, T, F, F, the same as the column for P. P \land Q is T, F, F, F and P \land \neg Q is F, T, F, F, so the “or” is T on rows 1 and 2, exactly the rows where P is T.
2, 3, 4, 8, 9, 10: six numbers. The evens are 2, 4, 6, 8, 10, 12 and the multiples of 3 are 3, 6, 9, 12; 6 and 12 are in both lists and so are left out.
T, F, F, T. P \oplus Q is F, T, T, F, and negating flips each entry. This is the column of the biconditional, if and only if: true exactly when P and Q agree.
The column is T, T, F, F, the column of P. P \oplus Q is F, T, T, F; combining it with Q (T, F, T, F) by “exactly one true” gives T, T, F, F.
2^6 = 64 rows. The conjunction is true in exactly 1, the row with every letter true; the disjunction is true in 63, every row but the one with every letter false.
6 rows. P \lor Q \lor R is true on 8 - 1 = 7 rows, and P \land Q \land R is true only on row 1, which is one of those seven.
15. There are 2^4 = 16 settings, and only the one with all four bolts drawn opens the door.
7 letters. With n letters a conjunction is false in 2^n - 1 rows, and 2^n - 1 = 127 gives 2^n = 128, so n = 7.
\neg P \land \neg Q \land R. Row 7 is F, F, T, so take \neg P, \neg Q and R.
\neg P \lor \neg Q. Row 1 has P and Q both true, so \neg P and \neg Q are both F there; on every other row at least one letter is false and its negation is T.
No. If P \land Q is false, at least one of P, Q must be false, but nothing says which one. For example, take P to be “2 is even” (true) and Q to be “2 is odd” (false); then P \land Q is false while P itself is true.
P has two possible values, and for each of them Q has two, giving 2 \times 2 = 4 combinations. Fewer rows would leave a combination out; more would repeat one.
P \land Q is true exactly when “P is true and Q is true”, and Q \land P exactly when “Q is true and P is true”: the same pair of requirements in either order, so the two are true in exactly the same cases. For “or”, swapping the letters swaps rows 2 and 3 of the table and leaves rows 1 and 4 alone. Rows 2 and 3 of the “or” column both read T, so every row keeps its value.
Read P \land Q \land R as (P \land Q) \land R, which the grouping law allows. Simplification makes P \land Q true, and simplification again makes Q true.
“x > 2 or x < 5” would be true for every real number: any x either exceeds 2, or is less than 5, or (for numbers between them) both. “And” is what forces x to satisfy both bounds at once, which is what pins the true values down to the interval between 2 and 5.
The menu’s “or” is exclusive: you get one, not both. The mathematical “or” is inclusive. For n = 2 both parts are true, since 2 is even and prime, and “2 is even or 2 is prime” is true.
A disjunction is true when at least one part is true, and P already is. Nothing about Q can change that.
Every integer is even or odd, so one part is always true. But 9 is odd and 9 = 3 \cdot 3 is not prime, so for n = 9 both parts of the second statement are false.
If P \land Q is true, both parts are true, so at least one is, and P \lor Q is true. The reverse fails: with P “2 is even” and Q “2 is odd”, P is true and Q is false, so P \lor Q is true while P \land Q is false.
The \neg P column is F, T. In row 1, P is T and \neg P is F; in row 2, P is F and \neg P is T. Each row has an F, so the P \land \neg P column is F, F, false in every row. Each row also has a T, so the P \lor \neg P column is T, T, true in every row.
A conjunction is true in a row only if every one of its letters is T there, and a disjunction is false in a row only if every one of its letters is F there. The table lists each combination of values exactly once, and exactly one combination has T for every letter, and exactly one has F for every letter. So each has exactly one special row.
L fixes the value of P and M fixes the value of Q, so L \land M is true only in the one row that has both of those values. Its column has exactly one T, and a column with two T’s is different.
Pick the row where the F sits. For each letter take the letter if it is false on that row and its negation if it is true. Both parts are then F on that row, and on every other row at least one letter takes the other value, which makes its part T. So A \lor B is F on that row only.
Every integer is 3k, 3k + 1 or 3k + 2 for some integer k. Then (3k)^2 = 3(3k^2) leaves remainder 0, (3k + 1)^2 = 3(3k^2 + 2k) + 1 leaves remainder 1, and (3k + 2)^2 = 3(3k^2 + 4k + 1) + 1 leaves remainder 1. In every case the remainder is 0 or 1.