2 Logically Speaking 19 Here are some examples for you to try. Exercise 2.10.Negate the following.It's interesting to note that you can negate a statement even if you don't understand what it says.It is easier to get it right,though, if you understand the statement. (a)If I go to the party,then he is there. (b)If x is even,then x is divisible by 2. (c)If a function is differentiable,then it is continuous. (d)If x is a natural number,then x is even or x is odd. O Exercise 2.11.Which of the following are equivalent to each other?All the answers have appeared in this chapter. P→Q,(PVQ),(PAQ),PAQ,(P→Q), PV-Q,-PV-0,-PA-O,-PVO. 0 So let's apply what we have learned in this chapter to Mr.French,who eats only pickles on Wednesday and only chocolate on Monday.One statement is that"if it is Wednesday,then Mr.French eats only pickles."We let W represent the statement"it is Wednesday,"and P the statement"Mr.French eats only pickles."Thus,we know that W-P is true.(If you thought we should have said WA P is true,note that we do not know that the statement W is true,so we must use the implication here.)The second is"if it is Monday,then Mr.French eats only chocolate."Letting M denote "it is Monday"and C the statement that "Mr.French eats only chocolate"we may write what we are given as M-C.Finally we are told that"Mr.French is eating chocolate."From this we can conclude thatP is true.Let's put this together. 1.W→P, 2.M→C,and 3.P Now,it's fairly clear that the second statement is irrelevant.So let us look at the truth tables for the first and third statements(for convenience,we combine the two tables): NPW→P|-P TT T 公 E 个 FT T F FF T T We know that both W-P and-P are true,and from our truth table we see that there is only one time that this happens:when both W and P are false.So there you have it.All we can conclude is that it is not Wednesday. People differ in their approaches to problems.In the example above,you might have found it easier not to rewrite the problem.That's fine.On the other hand,when
2 Logically Speaking 19 Here are some examples for you to try. Exercise 2.10. Negate the following. It’s interesting to note that you can negate a statement even if you don’t understand what it says. It is easier to get it right, though, if you understand the statement. (a) If I go to the party, then he is there. (b) If x is even, then x is divisible by 2. (c) If a function is differentiable, then it is continuous. (d) If x is a natural number, then x is even or x is odd. Exercise 2.11. Which of the following are equivalent to each other? All the answers have appeared in this chapter. P → Q,¬(P∨Q),¬(P∧Q),P∧ ¬Q,¬(P → Q) , P∨ ¬Q,¬P∨ ¬Q,¬P∧ ¬Q,¬P∨Q. So let’s apply what we have learned in this chapter to Mr. French, who eats only pickles on Wednesday and only chocolate on Monday. One statement is that “if it is Wednesday, then Mr. French eats only pickles.” We let W represent the statement “it is Wednesday,” and P the statement “Mr. French eats only pickles.” Thus, we know that W → P is true. (If you thought we should have said W ∧P is true, note that we do not know that the statement W is true, so we must use the implication here.) The second is “if it is Monday, then Mr. French eats only chocolate.” Letting M denote “it is Monday” and C the statement that “Mr. French eats only chocolate” we may write what we are given as M → C. Finally we are told that “Mr. French is eating chocolate.” From this we can conclude that ¬P is true. Let’s put this together. 1. W → P, 2. M → C, and 3. ¬P. Now, it’s fairly clear that the second statement is irrelevant. So let us look at the truth tables for the first and third statements (for convenience, we combine the two tables): W P W → P ¬P T T T F T F F T F T T F F F T T We know that both W → P and ¬P are true, and from our truth table we see that there is only one time that this happens: when both W and P are false. So there you have it. All we can conclude is that it is not Wednesday. People differ in their approaches to problems. In the example above, you might have found it easier not to rewrite the problem. That’s fine. On the other hand, when
20 2 Logically Speaking a problem starts to confuse you,looking at it as we have here will often help you figure out how to attack a problem. Solutions to Exercises Solution (2.1).All sentences are statements except (d)and (g). Part(d)is not a statement because its truth depends on X,and X is a variable.So the sentence is sometimes true and sometimes false. Part(g)is tricky.Suppose it were a statement.Then it would have to be true or false,but not both.Suppose"This sentence is false"were true.Then it would have to be false,but it cannot be both true and false.From this we conclude that the sentence has to be false.But reading the sentence tells us that if it is false,it must again be true as well.We conclude that it cannot be a statement,because we cannot assign a unique truth value to it. Solution (2.2).The truth table for PVO is PQPVQ TF T FT T FF E Solution (2.3).The truth table for PAO is PQPAQ TF 内 FT F FF F Solution (2.4).The truth table for P-o is PQP一→Q TT T B T T FF T This is the same as the truth table for-PVO. Solution (2.5).We will break the problem into parts in such a way that at each step we apply only one additional connective (except for the negation,which is handled easily in general)
20 2 Logically Speaking a problem starts to confuse you, looking at it as we have here will often help you figure out how to attack a problem. Solutions to Exercises Solution (2.1). All sentences are statements except (d) and (g). Part (d) is not a statement because its truth depends on X, and X is a variable. So the sentence is sometimes true and sometimes false. Part (g) is tricky. Suppose it were a statement. Then it would have to be true or false, but not both. Suppose “This sentence is false” were true. Then it would have to be false, but it cannot be both true and false. From this we conclude that the sentence has to be false. But reading the sentence tells us that if it is false, it must again be true as well. We conclude that it cannot be a statement, because we cannot assign a unique truth value to it. Solution (2.2). The truth table for P∨Q is P Q P∨Q T T T T F T F T T F F F Solution (2.3). The truth table for P∧Q is P Q P∧Q T T T T F F F T F F F F Solution (2.4). The truth table for P → Q is P Q P → Q T T T T F F F T T F F T This is the same as the truth table for ¬P∨Q. Solution (2.5). We will break the problem into parts in such a way that at each step we apply only one additional connective (except for the negation, which is handled easily in general)
2 Logically Speaking 21 PQR-QVRP-(-QVR)RVQ (P-(-QVR))A(RVQ) TTT T T T T TTF F 小 T F TFT T T T 7 TFF T T F F FTT T T T T FTF F T T T FFT T T T FFF T 2 F F Solution (2.6).We note that the last statement form is always true.(Note that the first and second statement forms have the same truth table.) Solution (2.8).In the solution to Exercise 2.4,we noted that P-O and-PVO are equivalent.Thus (P-O)is equivalent to(PVO),which is,as we have seen in Exercise 2.6,equivalent to PAO.In words,the negation of "If P,then o"is “P and not O.” Solution (2.10).More than one answer is possible but they must be equivalent,of course. (a)I go to the party and he is not there. (b)One answer is:x is even and x is not divisible by 2. (c)A function is differentiable and it is not continuous. (d)One answer is:x is a natural number and x is not even and x is not odd. Equivalently,we could say:x is a natural number,and x is neither even nor odd. Problems Problem 2.1.In the following implications,identify the antecedent and the conclu- sion.(Don't worry about whether the implication is true or false.) (a)If it is raining,I will stay home. (b)I wake up if the baby cries. (c)I wake up only if the fire alarm goes off. (d)Ifx is odd,then x is prime. (e)The number x is prime only ifx is odd. (f)You can come to the party only if you have an invitation. (g)Whenever the bell rings,I leave the house. Problem 2.2.Construct a truth table for(P).Is this what you expect?Why? Problem#2.3.Write out the truth tables for(PAO)and-PV-O.What can you conclude?
2 Logically Speaking 21 P Q R ¬Q∨R P → (¬Q∨R) R∨Q (P → (¬Q∨R))∧(R∨Q) T T T T T T T T T F F F T F T F T T T T T T F F T T F F F T T T T T T F T F F T T T F F T T T T T F F F T T F F Solution (2.6). We note that the last statement form is always true. (Note that the first and second statement forms have the same truth table.) Solution (2.8). In the solution to Exercise 2.4, we noted that P → Q and ¬P∨Q are equivalent. Thus ¬(P → Q) is equivalent to ¬(¬P∨ Q), which is, as we have seen in Exercise 2.6, equivalent to P ∧ ¬Q. In words, the negation of “If P, then Q” is “P and not Q.” Solution (2.10). More than one answer is possible but they must be equivalent, of course. (a) I go to the party and he is not there. (b) One answer is: x is even and x is not divisible by 2. (c) A function is differentiable and it is not continuous. (d) One answer is: x is a natural number and x is not even and x is not odd. Equivalently, we could say: x is a natural number, and x is neither even nor odd. Problems Problem 2.1. In the following implications, identify the antecedent and the conclusion. (Don’t worry about whether the implication is true or false.) (a) If it is raining, I will stay home. (b) I wake up if the baby cries. (c) I wake up only if the fire alarm goes off. (d) If x is odd, then x is prime. (e) The number x is prime only if x is odd. (f) You can come to the party only if you have an invitation. (g) Whenever the bell rings, I leave the house. Problem# 2.2. Construct a truth table for ¬(¬P). Is this what you expect? Why? Problem# 2.3. Write out the truth tables for ¬(P∧Q) and ¬P∨ ¬Q. What can you conclude?
22 2 Logically Speaking Problem#2.4.Find a statement form,S,equivalent to(PVO)and show that it is logically equivalent by constructing the truth table for"S if and only if(PVO)" and showing that this statement form is a tautology. Problem 2.5.Write out the truth table for the statement form P(OA-P).Is this statement form a tautology,a contradiction,or neither? Problem 2.6.Write out the truth table for the statement form (P(RVO))A R. Is this statement form a tautology,a contradiction,or neither? Problem 2.7.Negate the sentences below and express the answer in a sentence that is as simple as possible. (a)I will do my homework and I will pass this class. (b)Seven is an integer and seven is even. (c)If T is continuous,then T is bounded. (d)I can eat dinner or go to the show. (e)If x is odd,then x is prime. (f)The number x is prime only ifx is odd. Problem 2.8.Negate the following. (a)If I am not home,then Sam will answer the phone and he will tell you how to reach me. (b)If the stars are green or the white horse is shining,then the world is eleven feet wide. (c)If we go swimming or bowling,then dinner will be late or Bob will bring veggie burgers. Problem 2.9.Consider the statement form (PAO)-R. (a)Find the truth table for this statement form. (b)Construct a different statement form using P.O,and R such that if you call your construction S,then ((PA-O)-R)+S is a tautology. Problem 2.10.Consider the statement form(PVO)(RAO) (a)Write out the truth table for this form. (b)Give a statement in English that is in this form. (c)Write the negation of your English statement,and simplify the sentence as much as possible. Problem 2.11.For each of the cases below,write a tautology using the given state- ment form. For example,if you are given PV-O,you might write(PV-O)(O-P). (a)(P): (b)-(PVO); (c)-(PAO);
22 2 Logically Speaking Problem# 2.4. Find a statement form, S, equivalent to ¬(P∨ Q) and show that it is logically equivalent by constructing the truth table for “S if and only if ¬(P∨ Q)” and showing that this statement form is a tautology. Problem 2.5. Write out the truth table for the statement form P → ¬(Q ∧ ¬P). Is this statement form a tautology, a contradiction, or neither? Problem 2.6. Write out the truth table for the statement form (P → (¬R∨ Q))∧R. Is this statement form a tautology, a contradiction, or neither? Problem 2.7. Negate the sentences below and express the answer in a sentence that is as simple as possible. (a) I will do my homework and I will pass this class. (b) Seven is an integer and seven is even. (c) If T is continuous, then T is bounded. (d) I can eat dinner or go to the show. (e) If x is odd, then x is prime. (f) The number x is prime only if x is odd. Problem 2.8. Negate the following. (a) If I am not home, then Sam will answer the phone and he will tell you how to reach me. (b) If the stars are green or the white horse is shining, then the world is eleven feet wide. (c) If we go swimming or bowling, then dinner will be late or Bob will bring veggie burgers. Problem 2.9. Consider the statement form (P∧ ¬Q) → R. (a) Find the truth table for this statement form. (b) Construct a different statement form using P, Q, and R such that if you call your construction S, then ((P∧ ¬Q) → R) ↔ S is a tautology. Problem 2.10. Consider the statement form (P∨ ¬Q) → (R∧Q). (a) Write out the truth table for this form. (b) Give a statement in English that is in this form. (c) Write the negation of your English statement, and simplify the sentence as much as possible. Problem 2.11. For each of the cases below, write a tautology using the given statement form. For example, if you are given P∨ ¬Q, you might write (P∨ ¬Q) ↔ (Q → P). (a) ¬(¬P); (b) ¬(P∨Q); (c) ¬(P∧Q);
2 Logically Speaking 23 (d)P-Q. Problem 2.12.When we write,we should make certain that we say what we mean. If we write PAOVR,you may be confused.since we haven't said what to do when you are given a conjunction followed by a disjunction.Put parentheses in to create a statement form with the given truth table. PQRPAQVR TTT T TTF T TFT T TFF F FTT T FTF F FFT T FFF F Problem 2.13.For each of the cases below,write a contradiction using the given statement form. For example,if you are given(P),you might write(P)-P. (a)P→Q: (b)-(PVO); (c)-PV-Q; (d)P+0. Problem 2.14.Consider the following statement:If f is not continuous at 1 and-1, then the group of invariants is an infinite cyclic group,a cyclic group of order 2,or the trivial group. You probably do not know what the words in italics mean,but you don't need to know in order to work this problem.Just think of them as describing different objects.This is an exercise in restating things you don't understand-something that might be useful in the future! (a)Write the form of this statement using P,O,R,S,and T.(It's possible to use fewer variables and still have a correct solution.)Say precisely what each of your letters represent. (b)Write the negation of this statement in words.Use a phrase that is as simple and direct as possible. Problem 2.15.Consider the statement "It snows or it is not sunny." (a)Find a different statement that is equivalent to the given one. (b)Find a different statement that is equivalent to the negation of the given one. Problem 2.16.The following problem is well known.Many different versions of this problem appear in [101]. On a certain island,each inhabitant is a truth-teller or a liar (and not both,of course).A truth-teller always tells the truth and a liar always lies.Arnie and Barnie live on the island
2 Logically Speaking 23 (d) P → Q. Problem 2.12. When we write, we should make certain that we say what we mean. If we write P∧Q∨R, you may be confused, since we haven’t said what to do when you are given a conjunction followed by a disjunction. Put parentheses in to create a statement form with the given truth table. P Q R P∧Q∨R T T T T T T F T T F T T T F F F F T T T F T F F F F T T F F F F Problem 2.13. For each of the cases below, write a contradiction using the given statement form. For example, if you are given ¬(¬P), you might write ¬(¬P) ↔ ¬P. (a) P → Q; (b) ¬(P∨Q); (c) ¬P∨ ¬Q; (d) P ↔ Q. Problem 2.14. Consider the following statement: If f is not continuous at 1 and −1, then the group of invariants is an infinite cyclic group, a cyclic group of order 2, or the trivial group. You probably do not know what the words in italics mean, but you don’t need to know in order to work this problem. Just think of them as describing different objects. This is an exercise in restating things you don’t understand—something that might be useful in the future! (a) Write the form of this statement using P, Q, R, S, and T. (It’s possible to use fewer variables and still have a correct solution.) Say precisely what each of your letters represent. (b) Write the negation of this statement in words. Use a phrase that is as simple and direct as possible. Problem 2.15. Consider the statement “It snows or it is not sunny.” (a) Find a different statement that is equivalent to the given one. (b) Find a different statement that is equivalent to the negation of the given one. Problem 2.16. The following problem is well known. Many different versions of this problem appear in [101]. On a certain island, each inhabitant is a truth-teller or a liar (and not both, of course). A truth-teller always tells the truth and a liar always lies. Arnie and Barnie live on the island