14 2 Logically Speaking (g)This sentence is false. O Because English usage and mathematical usage may differ slightly,we must be certain that we understand our statements before we construct arguments.We now carefully study the truth or falsity of statements.Our treatment is brief.(See [69]for a more detailed study of mathematical logic.) The rules of logic that we present in this chapter should work for all statements, and not just particular ones.For this reason,we introduce letters such as P,O,R,or S to represent statements.Thus P will have two possible truth values:true,denoted T.or false,denoted F.We can negate P or combine it with o by saying things like: Not P. P and Por Q. If P,then Q. P if and only if Q. Such symbolic sentences will be called statement forms.A precise definition of statement form will be given once we have precise definitions of the connectives “not,”“and,”“or,”if.,then..”and“if and only if..” In the English language we might say It is raining. It is not raining. If it is raining,the sky is gray. It is raining or it is snowing. It is cold and it is snowing. It is snowing if and only if it is cold. Let's start with the simplest case.Suppose your teacher says,"This book has a blue cover."Taking a quick glance at the cover,you can decide on the truth value of that statement;namely,that it is false.In order to have a true statement,you could say,"This book does not have a blue cover."If we have a statement form P,the negation of P is the statement form"not P."Under what circumstances should the negation of P be true or false?We will always use the notationP for "not P."If P is true,then-P should be false.If P is false,then -P should be true.We can summarize all the possibilities in a truth table as follows: FT What about combining two statement forms,P and O,into one statement form as "P or O"?In this sentence,it is particularly important to distinguish between mathematical usage of the word"or"and everyday speech.For example,if we say, "You can have cake or ice cream,"it could be that you can have both.If we say,"The door is open or closed,"it cannot be that the door is both open and closed.English
14 2 Logically Speaking (g) This sentence is false. Because English usage and mathematical usage may differ slightly, we must be certain that we understand our statements before we construct arguments. We now carefully study the truth or falsity of statements. Our treatment is brief. (See [69] for a more detailed study of mathematical logic.) The rules of logic that we present in this chapter should work for all statements, and not just particular ones. For this reason, we introduce letters such as P,Q,R, or S to represent statements. Thus P will have two possible truth values: true, denoted T, or false, denoted F. We can negate P or combine it with Q by saying things like: Not P. P and Q . P or Q. If P, then Q. P if and only if Q. Such symbolic sentences will be called statement forms. A precise definition of statement form will be given once we have precise definitions of the connectives “not,” “and,” “or,” “if ..., then ...,” and “if and only if.” In the English language we might say It is raining. It is not raining. If it is raining, the sky is gray. It is raining or it is snowing. It is cold and it is snowing. It is snowing if and only if it is cold. Let’s start with the simplest case. Suppose your teacher says, “This book has a blue cover.” Taking a quick glance at the cover, you can decide on the truth value of that statement; namely, that it is false. In order to have a true statement, you could say, “This book does not have a blue cover.” If we have a statement form P, the negation of P is the statement form “not P.” Under what circumstances should the negation of P be true or false? We will always use the notation ¬P for “not P.” If P is true, then ¬P should be false. If P is false, then ¬P should be true. We can summarize all the possibilities in a truth table as follows: P ¬P T F F T What about combining two statement forms, P and Q, into one statement form as “P or Q”? In this sentence, it is particularly important to distinguish between mathematical usage of the word “or” and everyday speech. For example, if we say, “You can have cake or ice cream,” it could be that you can have both. If we say, “The door is open or closed,” it cannot be that the door is both open and closed. English
2 Logically Speaking 15 statements involving the word "or"are often ambiguous;in mathematics,ambiguity is generally frowned upon.The statement form"P or O"is called a disjunction and is denoted PVO.In mathematics,a disjunction is true when P alone is true,O alone is true,or both P and O are true.So in mathematics,you can always have your cake and ice cream. Exercise 2.2.Complete the truth table for PVO PQPVQ TT TF FT FF O The statement form"P and o"is called a conjunction and is denoted PAO.We will have you fill in the truth table for"P and O"below.It should be clear that this will be true when both P and O are true,and false otherwise. Exercise 2.3.Complete this truth table PQPAQ TT TF FT FF 0 Now consider the statement form "If P,then O."This statement form is called an implication and is often stated as"P implies O"and written P-O.(Note that though English usage of the word "implies"may suggest a relationship between P and O,our analysis of truth values has assumed no connection at all between P and O.)There are equivalent ways of stating an implication,and some will require careful thinking on the reader's part.Remember as you read on that"If P,then O" may also be stated as Qif P. P is sufficient for O(meaning P is enough to make O happen). O is necessary for P(if P happened,then O must have happened). P only if O(same as above;if P happened,then O must have happened) O whenever P. The statement form P in each of these formulations is called the antecedent,and O is called the conclusion.Under what conditions is an implication true?false?Let's begin with an example you are all familiar with.Suppose we say to our son, "If you clean your room,then you can go to Henry's house
2 Logically Speaking 15 statements involving the word “or” are often ambiguous; in mathematics, ambiguity is generally frowned upon. The statement form “P or Q” is called a disjunction and is denoted P∨Q. In mathematics, a disjunction is true when P alone is true, Q alone is true, or both P and Q are true. So in mathematics, you can always have your cake and ice cream. Exercise 2.2. Complete the truth table for P∨Q. P Q P∨Q T T T F F T F F The statement form “P and Q” is called a conjunction and is denoted P∧ Q. We will have you fill in the truth table for “P and Q” below. It should be clear that this will be true when both P and Q are true, and false otherwise. Exercise 2.3. Complete this truth table. P Q P∧Q T T T F F T F F Now consider the statement form “If P, then Q.” This statement form is called an implication and is often stated as “P implies Q” and written P → Q. (Note that though English usage of the word “implies” may suggest a relationship between P and Q, our analysis of truth values has assumed no connection at all between P and Q.) There are equivalent ways of stating an implication, and some will require careful thinking on the reader’s part. Remember as you read on that “If P, then Q” may also be stated as Q if P. P is sufficient for Q (meaning P is enough to make Q happen). Q is necessary for P (if P happened, then Q must have happened). P only if Q (same as above; if P happened, then Q must have happened). Q whenever P. The statement form P in each of these formulations is called the antecedent, and Q is called the conclusion. Under what conditions is an implication true? false? Let’s begin with an example you are all familiar with. Suppose we say to our son, “If you clean your room, then you can go to Henry’s house
16 2 Logically Speaking Under what conditions would he feel that we had lied?In the example,the an- tecedent,P,is"you clean your room."The conclusion,O,is"you can go to Henry's house."Well,if our son cleans his room and we let him go to Henry's,everybody is happy.That implication should be true.So,if P is true and O is true,the whole statement should be true.Also,it should be as clear to you as it will be to our son, that if he cleans his room and we do not let him go to Henry's,we lied.So,if P is true,and O is false,the implication should be false.Now what if he doesn't clean his room?We never discussed this possibility.So,no matter what we decide here, we have not lied.In this situation,the statement is not false;hence we consider it to be true.So,if P is false,no matter what the truth value is of the conclusion,we will consider the implication to be true. Summarizing this discussion,the only way that the implication"If P,then O" can be false is if P is true and O is false.In the exercise below you will sum up this discussion in the form of a truth table. Exercise 2.4.Complete this truth table. PQP→Q TT TF 2 FF O It is often helpful to rephrase a statement,making sure that you maintain the same true and false values.The statement form"P if and only if o"is called an equivalence,and we will write this as PO.This is the same statement form as "(P only if o)and(P ifo)."In view of the discussion above,we see that this is also (P)A(-P).Thus the truth table for the equivalence is PQP→QQ→PP+Q T T T TF T F FT T F FF T T T Look down the final column and you'll see that the equivalence is true precisely when P and O are both true or both false. The statement form"If P,then o"is also written as P=,and "P if and only if Q”might be written as P台Qor“Piff o." Having studied the connectives,we are ready for our definition of a statement form.A statement form is a letter representing an unspecified statement or an ex- pression built from such letters using connectives.Statement forms can be quite complicated.Assigning truth values to them can be done in a step-by-step fashion. The exercise below illustrates this. Exercise 2.5.Find the truth table for the statement form
16 2 Logically Speaking Under what conditions would he feel that we had lied? In the example, the antecedent, P, is “you clean your room.” The conclusion, Q, is “you can go to Henry’s house.” Well, if our son cleans his room and we let him go to Henry’s, everybody is happy. That implication should be true. So, if P is true and Q is true, the whole statement should be true. Also, it should be as clear to you as it will be to our son, that if he cleans his room and we do not let him go to Henry’s, we lied. So, if P is true, and Q is false, the implication should be false. Now what if he doesn’t clean his room? We never discussed this possibility. So, no matter what we decide here, we have not lied. In this situation, the statement is not false; hence we consider it to be true. So, if P is false, no matter what the truth value is of the conclusion, we will consider the implication to be true. Summarizing this discussion, the only way that the implication “If P, then Q” can be false is if P is true and Q is false. In the exercise below you will sum up this discussion in the form of a truth table. Exercise 2.4. Complete this truth table. P Q P → Q T T T F F T F F It is often helpful to rephrase a statement, making sure that you maintain the same true and false values. The statement form “P if and only if Q” is called an equivalence, and we will write this as P ↔ Q. This is the same statement form as “(P only if Q) and (P if Q).” In view of the discussion above, we see that this is also (P → Q)∧(Q → P). Thus the truth table for the equivalence is P Q P → Q Q → P P ↔ Q T T T T T T F F T F F T T F F F F T T T Look down the final column and you’ll see that the equivalence is true precisely when P and Q are both true or both false. The statement form “If P, then Q” is also written as P ⇒ Q, and “P if and only if Q” might be written as P ⇔ Q or “P iff Q.” Having studied the connectives, we are ready for our definition of a statement form. A statement form is a letter representing an unspecified statement or an expression built from such letters using connectives. Statement forms can be quite complicated. Assigning truth values to them can be done in a step-by-step fashion. The exercise below illustrates this. Exercise 2.5. Find the truth table for the statement form
2 Logically Speaking 17 (P→(QVR)A(RVQ). To solve this you must break the complicated form (P-(OVR))A(RVO)into simpler parts.Once you have done this,you should find the truth value of each of the parts using the truth values of P,O,and R. O Now consider the two statement forms(PVO)and-PA-O.In the next exer- cise,you will find the truth table for each of these expressions and compare them. Exercise 2.6.Write out the truth tables for(PVO),PA-0,and ((PVO)) (PA-O).What can you conclude? O A statement form for which the final column in the truth table consists of all T's is called a tautology.A statement form for which the final column is all F's is called a contradiction.Two statement forms,P and O,are said to be (logically)equivalent if PO is a tautology,and two statements are equivalent if they can be obtained from two equivalent statement forms by consistently replacing the letters by English statements. In view of Exercise 2.6,we see that(PVO)and-PA-O are equivalent state- ment forms.Thus the statement"It is not the case that Rachel or Leah won the race" is equivalent to"Rachel did not win the race and Leah did not win the race."(Why?) In Exercise 2.6 you noticed that the two statement forms(PVO)and-PA-O have the same truth table,and ((PVO))(PAO)is a tautology.This isn't something that happens in this one particular example.Whenever we notice that a statement is always true,we can state that fact as a theorem.Of course,we will need to give a conclusive argument for the statement's truth,and this is called a proof of the theorem.We'll present a theorem and a proof below,but remember: The statement forms,P and O,might very well be complicated constructions with many connectives.For instance,P could be R(SV(TAR)).In fact,the theorem we present below is most interesting when P is complicated! Theorem 2.7.Two statement forms P and O are equivalent if and only if they have the same truth table. Proof.Consider the truth table for the equivalence P+O: PQP-Q TT TF F T F FF We know that Po is a tautology if and only if PO has the truth value T (in the table above,this is row 1 and row 4).Finally,P+O has the truth value T if and only if P and O have the same truth value.Since P and O are equivalent if and only if Po is a tautology,this establishes the theorem. ◇
2 Logically Speaking 17 (P → (¬Q∨R))∧(R∨Q) . To solve this you must break the complicated form (P → (¬Q ∨R))∧(R∨ Q) into simpler parts. Once you have done this, you should find the truth value of each of the parts using the truth values of P,Q, and R. Now consider the two statement forms ¬(P∨Q) and ¬P∧ ¬Q. In the next exercise, you will find the truth table for each of these expressions and compare them. Exercise 2.6. Write out the truth tables for ¬(P∨ Q), ¬P∧ ¬Q, and (¬(P∨ Q)) ↔ (¬P∧ ¬Q). What can you conclude? A statement form for which the final column in the truth table consists of all T’s is called a tautology. A statement form for which the final column is all F’s is called a contradiction. Two statement forms, P and Q, are said to be (logically) equivalent if P ↔ Q is a tautology, and two statements are equivalent if they can be obtained from two equivalent statement forms by consistently replacing the letters by English statements. In view of Exercise 2.6, we see that ¬(P∨Q) and ¬P∧ ¬Q are equivalent statement forms. Thus the statement “It is not the case that Rachel or Leah won the race” is equivalent to “Rachel did not win the race and Leah did not win the race.” (Why?) In Exercise 2.6 you noticed that the two statement forms ¬(P∨Q) and ¬P∧ ¬Q have the same truth table, and (¬(P∨ Q)) ↔ (¬P∧ ¬Q) is a tautology. This isn’t something that happens in this one particular example. Whenever we notice that a statement is always true, we can state that fact as a theorem. Of course, we will need to give a conclusive argument for the statement’s truth, and this is called a proof of the theorem. We’ll present a theorem and a proof below, but remember: The statement forms, P and Q, might very well be complicated constructions with many connectives. For instance, P could be R → (S∨(¬T ∧R)). In fact, the theorem we present below is most interesting when P is complicated! Theorem 2.7. Two statement forms P and Q are equivalent if and only if they have the same truth table. Proof. Consider the truth table for the equivalence P ↔ Q: P Q P ↔ Q T T T T F F F T F F F T We know that P ↔ Q is a tautology if and only if P ↔ Q has the truth value T (in the table above, this is row 1 and row 4). Finally, P ↔ Q has the truth value T if and only if P and Q have the same truth value. Since P and Q are equivalent if and only if P ↔ Q is a tautology, this establishes the theorem. ut
18 2 Logically Speaking While it is very important to be able to restate something in an equivalent form, it is equally important that you be able to negate a statement.Some useful negations appear in the exercises and problems.The negation of an implication is particularly important in mathematics.If you think about integers and the sentence"Ifx is prime, then x is odd or x=2,"you can see that even a relatively simple implication might be difficult to negate.Let's begin with something simpler. Exercise 2.8.Construct the truth table for P-O,and the truth table for-PVO. What do you notice?Now construct a truth table for(P-O)(PVO).What conclusion can you make?Finally,find an equivalent way to write-(P-O).O If all went well,you noticed that P-O is equivalent to -PVO,and therefore the negation of"If P,then o"is"P and not O."Let's return to "If x is prime,then x is odd orx=2. Negating this leads to "x is prime and it is not the case that x is odd orx=2" Q While this is the negation,it isn't really as helpful as it might be.So we now negate the disjunction"x is odd orx=2"and combine it with our previous work to obtain “x is prime and x is not odd andx≠2.” Refining this further,we would probably say something like"x is prime,even,and not equal to two.” The negation of an implication is something you should learn well now because it arises frequently.In the theorem below,we summarize the five most important equivalences that we have covered so far.The first two are often referred to as De- Morgan's laws. Theorem 2.9.Let P and O denote statement forms.The following are tautologies: (DeMorgan's laws)(PVO)(PA-O); (PAQ)→(PVQ): (Implication and(P→Q)→(-PVQ): its negation) (P→Q)+(P∧Q): (Double negation)(-P)+P. Proof.In Exercise 2.6 we showed that the first tautology holds.You will establish the second in Problem 2.3.The third and fourth tautologies were the content of Ex- ercise 2.8.Finally,you will establish the last tautology when you work Problem 2.2. ▣
18 2 Logically Speaking While it is very important to be able to restate something in an equivalent form, it is equally important that you be able to negate a statement. Some useful negations appear in the exercises and problems. The negation of an implication is particularly important in mathematics. If you think about integers and the sentence “If x is prime, then x is odd or x = 2,” you can see that even a relatively simple implication might be difficult to negate. Let’s begin with something simpler. Exercise 2.8. Construct the truth table for P → Q, and the truth table for ¬P∨ Q. What do you notice? Now construct a truth table for (P → Q) ↔ (¬P∨ Q). What conclusion can you make? Finally, find an equivalent way to write ¬(P → Q). If all went well, you noticed that P → Q is equivalent to ¬P∨ Q, and therefore the negation of “If P, then Q” is “P and not Q.” Let’s return to “If x is prime | {z } P , then x is odd or x = 2 | {z } Q .” Negating this leads to “ x is prime | {z } P and it is not the case that x is odd or x = 2 | {z } ¬Q .” While this is the negation, it isn’t really as helpful as it might be. So we now negate the disjunction “x is odd or x = 2” and combine it with our previous work to obtain “x is prime and x is not odd and x 6= 2.” Refining this further, we would probably say something like “x is prime, even, and not equal to two.” The negation of an implication is something you should learn well now because it arises frequently. In the theorem below, we summarize the five most important equivalences that we have covered so far. The first two are often referred to as DeMorgan’s laws. Theorem 2.9. Let P and Q denote statement forms. The following are tautologies: (DeMorgan’s laws) ¬(P∨Q) ↔ (¬P∧ ¬Q); ¬(P∧Q) ↔ (¬P∨ ¬Q); (Implication and (P → Q) ↔ (¬P∨Q); its negation) ¬(P → Q) ↔ (P∧ ¬Q); (Double negation) ¬(¬P) ↔ P. Proof. In Exercise 2.6 we showed that the first tautology holds. You will establish the second in Problem 2.3. The third and fourth tautologies were the content of Exercise 2.8. Finally, you will establish the last tautology when you work Problem 2.2. ut