1.1: Propositional Logic
 Page ID
 6708
A proposition is a statement which is either true or false. In propositional logic, we take propositions as basic and see what we can do with them. Since this is mathematics, we need to be able to talk about propositions without saying which particular propositions we are talking about, so we use symbolic names to represent them. We will always use lowercase letters such as \(p, q,\) and \(r\) to represent propositions. A letter used in this way is called a propositional variable. Remember that when I say something like “Let p be a proposition,” I mean “For the rest of this discussion, let the symbol p stand for some particular statement, which is either true or false (although I am not at the moment making any assumption about which it is).” The discussion has mathematical generality in that p can represent any statement, and the discussion will be valid no matter which statement it represents.
What we do with propositions is combine them with logical operators. A logical operator can be applied to one or more propositions to produce a new proposition. The truth value of the new proposition is completely determined by the operator and by the truth values of the propositions to which it is applied.1 In English, logical operators are represented by words such as “and,” “or,” and “not.” For example, the proposition “I wanted to leave and I left” is formed from two simpler propositions joined by the word “and.” Adding the word “not” to the proposition “I left” gives “I did not leave” (after a bit of necessary grammatical adjustment).
But English is a little too rich for mathematical logic. When you read the sentence “I wanted to leave and I left,” you probably see a connotation of causality: I \(left\) because I wanted to leave. This implication does not follow from the logical combination of the truth values of the two propositions “I wanted to leave” and “I left.” Or consider the proposition “I wanted to leave but I did not leave.” Here, the word “but” has the same logical meaning as the word “and,” but the connotation is very different. So, in mathematical logic, we use \(symbol\)s to represent logical operators. These symbols do not carry any connotation beyond their defined logical meaning. The logical operators corresponding to the English words “and,” “or,”and “not” are ∧, ∨, and ¬.
Definition 1.1
Let p and q be propositions. Then \(p∨q\), \(p∧q\), and \(¬p\) are propositions, whose truth values are given by the rules:
• \(p ∧ q\) is true when both \(p\) is true and \(q\) is true, and in no other case.
• \(p ∨ q\) is true when either \(p\) is true, or \(q\) is true,or both \(p\) and \(q\) are true, and in no other case.
• \(¬p\) is true when \(p\) is false, and in no other case.
The operators ∧, ∨, and ¬ are referred to as conjunction, disjunction, and negation, respectively. (Note that \(p ∧ q\) is read as “\(p\) and \(q\),” \(p ∨ q\) is read as “\(p\) or \(q\),” and ¬p is read as “not p.”)
1It is not always true that the truth value of a sentence can be determined from the truth values of its component parts. For example, if p is a proposition, then “Sarah Palin believes p” is also a proposition, so “Sarah Palin believes” is some kind of operator. However, it does not count as a logical operator because just from knowing whether or not p is true, we get no information at all about whether “Sarah Palin believes p” is true.
These operators can be used in more complicated expressions, such as \(p∧(¬q)\) or \((p ∨q)∧(q∨r)\). A proposition made up of simpler propositions and logical operators is called a compound proposition. Parentheses can be used in compound expressions to indicate the order in which the operators are to be evaluated. In the absence of parentheses, the order of evaluation is determined by precedence rules. For the logical operators defined above, the rules are that ¬ has higher precedence that ∧, and ∧ has precedence over ∨. This means that in the absence of parentheses, any ¬operators are evaluated first, followed by any ∧ operators, followed by any ∨ operators.
For example, the expression \(¬p∨q∧r\) is equivalent to the expression \((¬p)∨(q∧r)\), while \(p∨q∧q∨r\) is equivalent to \(p∨(q∧q)∨r\). As a practical matter, when you make up your own expressions, it is usually better to put in parentheses to make your meaning clear. Remember that even if you leave out parentheses, your expression has an unambiguous meaning. If you say “\(¬p∧q\)” when what you meant was “\(¬(p∧q)\),” you’ve got it wrong!
This still leaves open the question of which of the ∧ operators in the expression \(p∧q∧r\) is evaluated first. This is settled by the following rule: When several operators of equal precedence occur in the absence of parentheses, they are evaluated from left to right. Thus, the expression \(p∧q∧r\) is equivalent to \((p∧q)∧r\) rather than to \(p∧(q∧r)\). In this particular case, as a matter of fact, it doesn’t really matter which ∧ operator is evaluated first, since the two compound propositions \((p∧q)∧r\) and \(p∧(q∧r)\) always have the same value, no matter what logical values the component propositions p, q, and r have. We say that ∧ is an associative operation. We’ll see more about associativity and other properties of operations in the next section.
Suppose we want to verify that, in fact, \((p∧q)∧r\) and \(p∧(q∧r)\) do always have the same value. To do so, we have to consider all possible combinations of values of p, q, and r, and check that for all such combinations, the two compound expressions do indeed have the same value. It is convenient to organize this computation into a truth table. A truth table is a table that shows the value of one or more compound propositions for each possible combination of values of the propositional variables that they contain. Figure 1.1 is a truth table that compares the value of \((p∧q)∧r\) to the value of \(p∧(q∧r)\) for all possible values of \(p, q\), and \(r\). There are eight rows in the table because there are exactly eight different ways in which truth values can be assigned to p, q, and r.2 In this table, we see that the last two columns, representing the values of \((p∧q)∧r\) and \(p∧(q∧r)\), are identical.
Figure 1.1: A truth table that demonstrates the logical equivalence of \((p∧q)∧r\) and \(p∧(q∧r)\). The fact that the last two columns of this table are identical shows that these two expressions have the same value for all eight possible combinations of values of \(p, q\), and \(r\).
\(^2\)In general, if there are n variables, then there are \(2^n\) different ways to assign truth values to the variables. This might become clear to you if you try to come up with a scheme for systematically listing all possible sets of values. If not, you’ll find a rigorous proof of the fact later in this chapter.
More generally, we say that two compound propositions are logically equivalent if they always have the same value, no matter what truth values are assigned to the propositional variables that they contain. If the number of propositional variables is small, it is easy to use a truth table to check whether or not two propositions are logically equivalent.
There are other logical operators besides ∧, ∨, and ¬. We will consider the conditional operator, →, the biconditional operator, ↔, and the exclusive or operator, ⊕\(^3\). These operators can be completely defined by a truth table that shows their values for the four possible combinations of truth values of p and q.
\(^3\)Note that the symbols used in this book for the logical operators are not universal. While ∧, ∨, and → are fairly standard, ¬ is often replaced by ∼ and ↔ is sometimes represented by ≡ or ⇔. There is even less standardization of the exclusive or operator, but that operator is generally not so important as the others.
Definition 1.2
For any propositions \(p\) and \(q\), we define the propositions \(p → q, p ↔ q\), and \(p ⊕ q\) according to the truth table:
When these operators are used in expressions, in the absence of parentheses to indicate order of evaluation, we use the following precedence rules: The exclusive or operator, ⊕, has the same precedence as ∨. The conditional operator, →, has lower precedence than ∧, ∨, ¬, and ⊕, and is therefore evaluated after them. Finally, the biconditional operator, ↔, has the lowest precedence and is therefore evaluated last. For example, the expression “\(p→q∧r↔¬p⊕s\)” is evaluated as if it were written “\((p→(q∧r))↔((¬p)⊕s).\)”
In order to work effectively with the logical operators, you need to know more about their meaning and how they relate to ordinary English expressions.
The proposition \(p→q\) is called an implication or a conditional. It is usually read as “\(p\) implies \(q\).” In English, \(p→q\) is often expressed as “if \(p\) then \(q\).” For example, if \(p\) represents the proposition “Bill Gates is poor” and \(q\) represents “the moon is made of green cheese,” then \(p→q\) could be expressed in English as “If Bill Gates is poor, then the moon is made of green cheese.” In this example, p is false and q is also false. Checking the definition of \(p→q\) , we see that \(p→q\) is a true statement. Most people would agree with this. It’s worth looking at a similar example in more detail. Suppose that I assert that “If the Mets are a great team, then I’m the king of France.” This statement has the form \(m→k\) where \(m\) is the proposition “the Mets are a great team” and \(k\) is the proposition “I’m the king of France.” Now, demonstrably I am not the king of France, so \(k\) is false. Since \(k\) is false, the only way for \(m→k\) to be true is for \(m\) to be false as well. (Check the definition of → in the table!) So, by asserting \(m → k\), I am really asserting that the Mets are not a great team.
Or consider the statement, “If the party is on Tuesday, then I’ll be there.” What am I trying to say if I assert this statement? I am asserting that \(p→q\) is true, where p represents “The party is on Tuesday” and q represents “I will be at the party.” Suppose that p is true, that is, the party does in fact take place on Tuesday. Checking the definition of →, we see that in the only case where p is true and \(p→q\) is true,q is also true. So from the truth of “If the party is on Tuesday, then I will be at the party” and “The party is in fact on Tuesday,” you can deduce that “I will be at the party” is also true. But suppose, on the other hand, that the party is actually on Wednesday. Then \(p\) is false. When p is false and \(p → q\) is true, the definition of \(p → q\) allows q to be either true or false. So, in this case, you can’t make any deduction about whether or not I will be at the party. The statement “If the party is on Tuesday, then I’ll be there” doesn’t assert anything about what will happen if the party is on some other day than Tuesday.
The implication \((¬q)→(¬p)\) is called the contrapositive of \(p→q\). An implication is logically equivalent to its contrapositive. The contrapositive of “If this is Tuesday, then we are in Belgium” is “If we aren’t in Belgium, then this isn’t Tuesday.” These two sentences assert exactly the same thing.
Note that \(p→q\) is not logically equivalent to \(q→p\). The implication \(q→p\) is called the converse of \(p → q\). The converse of “If this is Tuesday, then we are in Belgium” is “If we are in Belgium, then this is Tuesday.” Note that it is possible for either one of these statements to be true while the other is false. In English, I might express the fact that both statements are true by saying “If this is Tuesday, then we are in Belgium, and conversely.” In logic, this would be expressed with a proposition of the form \((p→q)∧(q → p)\).
The biconditional operator is closely related to the conditional operator. In fact, \(p↔q\) is logically equivalent to \((p→q)∧(q→p)\). The proposition \(p↔q\) is usually read as “\(p\) if and only if \(q\).” (The “\(p\) if \(q\)” part represents \(q→p\), while “\(p\) only if \(q\)” is another way of asserting that \(p → q\). It could also be expressed as “if \(p\) then \(q\), and conversely.” Occasionally in English, “if. . . then” is used when what is really meant is “if and only if.” For example, if a parent tells a child, “If you are good, Santa will bring you toys,” the parent probably really means to say “Santa will bring you toys if and only if you are good.” (The parent would probably not respond well to the child’s perfectly logical plea “But you never said what would happen if I wasn’t good!”)
Finally, we turn to the exclusive or operator. The English word “or” is actually somewhat ambiguous. The two operators ⊕ and ∨ express the two possible meanings of this word. The proposition \(p∨q\) can be expressed unambiguously as “\(p\) or \(q\), or both,” while \(p\) ⊕ \(q\) stands for “\(p\) or \(q\), but not both.” If a menu says that you can choose soup or salad, it doesn’t mean that you can have both. In this case, “or” is an exclusive or. On the other hand, in “You are at risk of heart disease if you smoke or drink,” the or is inclusive since you certainly don’t get off the hook if you both smoke and drink. In mathematics, the word “or” is always taken in the inclusive sense of \(p∨q\).
Now, any compound proposition that uses any of the operators →, ↔, and ⊕ can be rewritten as a logically equivalent proposition that uses only∧, ∨, and ¬. It is easy to check that \(p→q\) is logically equivalent to \((¬p)∨q\).
(Just make a truth table for \((¬p)∨q.)\) Similarly, \(p↔q\) can be expressed as \(((¬p)∨q)∧((¬q)∨p)\), So, in a strict logical sense, →, ↔, and ⊕ are unnecessary. (Nevertheless, they are useful and important, and we won’t give them up.)
Even more is true: In a strict logical sense, we could do without the conjunction operator ∧. It’s easy to check that \(p∧q\) is logically equivalent to \(¬(¬p∨¬q)\), so any expression that uses ∧ can be rewritten as one that uses only ¬ and ∨. Alternatively, we could do without ∨ and write everything in terms of ¬ and ∧.
Certain types of proposition will play a special role in our further work with logic. In particular, we define tautologies and contradictions as follows:
Definition 1.3
A compound proposition is said to be a tautology if and only if it is true for all possible combinations of truth values of the propositional variables which it contains. A compound proposition is said to be a contradiction if and only if it is false for all possible combinations of truth values of the propositional variables which it contains.
For example, the proposition \(((p∨q)∧¬q) → p\) is a tautology. This can be checked with a truth table:
The fact that all entries in the last column are true tells us that this expression is a tautology. Note that for any compound proposition \(P\), \(P\) is a tautology if and only if \(¬P\) is a contradiction. (Here and in the future, I use uppercase letters to represent compound propositions. \(P\) stands for any formula made up of simple propositions, propositional variables, and logical operators.) Logical equivalence can be defined in terms of tautology:
Definition 1.4
Two compound propositions, \(P\) and \(Q\), are said to be logically equivalent if and only if the proposition \(P↔Q\) is a tautology.
The assertion that P is logically equivalent to Q will be expressed symbolically as “P ≡ Q.” For example, \((p → q) ≡ (¬p∨q)\), and \(p⊕q ≡(p∨q)∧¬(p∧q)\).
Exercises
 Give the three truth tables that define the logical operators ∧, ∨, and ¬.

Insert parentheses into the following compound propositions to show the order in which the operators are evaluated:
a) \(¬p∨q\)
b) \(p∧q∨¬p\)
c) \(p∨q∧r\)
d) \(p∧¬q∨r\) 
List the 16 possible combinations of truth values for the four propositional variables \(s, p, q, r\). Try to find a systematic way to list the values. (Hint: Start with the eight combinations of values for \(p, q,\) and \(r\), as given in the truth table in Figure 1.1. Now, explain why there are 32 possible combinations of values for five variables, and describe how they could be listed systematically.)

Some of the following compound propositions are tautologies, some are contradictions, and some are neither. In each case, use a truth table to decide to which of these categories the proposition belongs:
a) \((p∧(p→q))→q\)
b) \(((p→q)∧(q→r))→(p→r)\)
c) \(p∧(¬p)\)
d) \((p∨q) → (p∧q)\)
e) \(p∨(¬p)\)
f) \((p∧q) → (p∨q)\)

Use truth tables to show that each of the following propositions is logically equivalent to p ↔ q.
a) \((p→q)∧(q→p)\)
b) \((¬p)↔(¬q)\)
c) \((p → q)∧((¬p) → (¬q))\)
d) \(¬(p⊕q)\) 
Is → an associative operation? This is, is \((p → q) → r\) logically equivalent to \(p → (q → r)\)? Is ↔ associative?

Let \(p\) represent the proposition “You leave” and let \(q\) represent the proposition “I leave.” Express the following sentences as compound propositions using \(p\) and \(q\), and show that they are logically equivalent:
a) Either you leave or I do. (Or both!). b) If you don’t leave, I will.

Suppose that m represents the proposition “The Earth moves,” c represents “The Earth is the center of the universe,” and g represents “Galileo was rail roaded.” Translate each of the following compound propositions into English:
a)\(¬g∧c\) b)\(m→¬c\) c) \(m↔¬c\) d)\((m→g)∧(c→¬g)\)

Give the converse and the contrapositive of each of the following English sentences:
a) If you are good, Santa brings you toys.
b) If the package weighs more than one ounce, then you need extra postage.
c) If I have a choice, I don’t eat eggplant. 
In an ordinary deck of fiftytwo playing cards, for how many cards is it true
a) that “This card is a ten and this card is a heart”?
b) that “This card is a ten or this card is a heart”?
c) that “If this card is a ten, then this card is a heart”?
d) that “This card is a ten if and only if this card is a heart”?
11. Define a logical operator ↓ so that \(p ↓ q\) is logically equivalent to \(¬(p ∨ q)\). (This operator is usually referred to as “nor,” short for “not or”). Show that each of the propositions \(¬p, p∧q, p∨q, p → q, p ↔ q,\) and \(p⊕q\) can be rewritten as a logically equivalent proposition that uses ↓ as its only operator.