Section 2.3 Or and And
So the two simplest ways of combining two logical statements are using “or” and “and” . The words “or” and “and” have precise mathematical meanings which sometimes differ from their use in day-to-day language. To avoid conflating these mathematical means with the colloquial meanings we can refer to “or” and “and” by the nicely latin-flavoured words “disjunction” and “conjunction”; hopefully we won’t need those for very long and we’ll get used to being more precise about when we want mathematical “and” and “or” and when we are just being colloquial.
Definition 2.3.1.
Let \(P\) and \(Q\) be statements.
The disjunction of \(P\) and \(Q\) is the statement “\(P\) or \(Q\)” and is denoted \(P \lor Q\text{.}\) The disjunction is true if at least one of \(P\) and \(Q\) are true. The disjunction is only false if both \(P\) and \(Q\) are false.
The conjunction of \(P\) and \(Q\) is the statement “\(P\) and \(Q\)” and is denoted \(P \land Q\text{.}\) The conjunction is true when both \(P\) and \(Q\) are true. It is false if at least one of \(P\) and \(Q\) are false.
The truth tables of the disjunction and conjunction are
| \(P\) |
\(Q\) |
\(P \lor Q\) |
\(P \land Q\) |
| T |
T |
T |
T |
| T |
F |
T |
F |
| F |
T |
T |
F |
| F |
F |
F |
F |
Be careful to use the correct notation. The symbols \(\lor\) and \(\land\) should not be confused or interchanged with the symbols for unions and intersections, \(\cup\) and \(\cap\text{.}\) We’ll come back to unions and intersections later in the text.
Notice that this use of “or” defined above is different from how we often use “or” in spoken English. When you are on a flight and the attendant offers you a meal (assuming you are on a long flight that still offers such luxuries) you might be asked
“Would you like chicken or beef”?
You are not being offered both; you get at most one. This is an example of “exclusive or” — one or the other, but not both. The mathematical “or” we have just described above is “inclusive or” — at least one of the two options. You should assume that when we write “or” in a mathematical context we will mean inclusive or. To refer to exclusive or we will typically write “either … or … but not both”. If in doubt use more words to clarify things rather then save yourself a few symbols at the expense of your reader’s understanding.
The use of “and” in English can also have subtle differences from the mathematical conjunction \(\land\text{.}\) For example, “and” can sometimes imply an order: “He lived and he died” is more natural than “He died and he lived”. The mathematical and, by contrast, doesn’t care about order: \(P \land Q\) has the same truth table as \(Q \land P\text{.}\)
For example, take the statements “7 is prime” and “18 is odd”. We can now construct a new statement
7 is prime and 18 is odd
Since the first statement is true and the second is false, the conjunction of the two (our new statement) is false. On the other hand
7 is prime and 18 is even
is a true statement. Similarly the statement
7 is prime or 18 is odd
is true.
“Not”, “and” and “or” are three logical connectives — or logical operators. They take one or two statements and combine them to make new statements — called “compound statements”. Using “not”, “and” and “or” you can construct any truth table of two statements you might want (there are \(2^4 = 16\) of them). If you have done some computer science you have perhaps heard of NAND (not and), NOR (not or), XOR (exclusive or) and XNOR (exclusive not or). We’ll shortly see how to construct such things using the three connectives we have just defined. But first we’ll introduce the logical operator that lies at the heart of most of the mathematical proofs that are coming.
