WIXLIB

Chapter 1Propositional LogicThe grand aim of all science is to cover the greatest number of empirical factsby logical deduction from the smallest number of hypotheses or axioms.Albert Einstein (1879–1955), Nobel prize-winning physicistin Life magazineFor our purposes, Logic is the business of deciding whether or not a deduction is valid; thatis, deciding whether or not a particular conclusion is a consequence of particular assumptions.(The assumptions can also be called “hypotheses” or “axioms.”)1.1. Assertions, deductions, and validityWe will begin our discussion of Logic by introducing three basic ingredients: assertions, deductions, and validity.Here is one possible deduction:Hypotheses:(1) It is raining heavily.(2) If you do not take an umbrella, you will get soaked.Conclusion: You should take an umbrella.(The validity of this particular deduction will be analyzed in Example 1.1.10 below.)In Logic, we are only interested in sentences that can be a hypothesis or conclusion of adeduction. These are called “assertions”:DEFINITION 1.1.1. An assertion is a sentence that is either true or false.OTHER TERMINOLOGY. Some textbooks use the term proposition or statement or sentence,instead of assertion.EXAMPLE 1.1.2. Questions The sentence “Are you sleepy yet?” is not an assertion. Although youmight be sleepy or you might be alert, the question itself is neither true nor false. Forthis reason, questions do not count as assertions in Logic. Imperatives Commands are often phrased as imperatives like “Wake up!,” “Sit upstraight,” and so on. Although it might be good for you to sit up straight or it mightnot, the command itself is neither true nor false. Exclamations “Ouch!” is sometimes called an exclamatory sentence, but it is neithertrue nor false. so it is another example of a sentence that is not an assertion.3

41. Propositional LogicRemark 1.1.3. Roughly speaking, an assertion is a statement of fact, such as “The earth isbigger than the moon” or “Edmonton is the capital of Alberta.” However, it is important toremember that an assertion may be false, in which case it is a mistake (or perhaps a deliberatelie), such as “There are less than 1,000 automobiles in all of Canada.” In many cases, the truthor falsity of an assertion depends on the situation. For example, the assertion “It is raining” istrue in certain places at certain times, but is false at others.In this chapter and the next, which are introductory, we will deal mostly with assertionsabout the real world, where facts are not always clear-cut. (For example, if Alice and Bob arealmost the same height, it may be impossible to determine whether it is true that “Alice is tallerthan Bob.”) We are taking a mathematical (or scientific) view toward Logic, not a philosophicalone, so we will ignore the imperfections of these real-world assertions, which provide motivationand illustration, because our goal is to learn to use Logic to understand mathematical objects(not real-world objects), where there are no grey areas.Throughout this text, you will find exercises that review and explore the material that hasjust been covered. There is no substitute for actually working through some problems, becausethis course, like most advanced mathematics, is more about a way of thinking than it is aboutmemorizing facts.EXERCISES 1.1.4. Which of the following are “assertions” in the logical sense?1)3)5)7)England is smaller than China.Is New Jersey east of Wisconsin?The atomic number of helium is π.This is the last question.2)4)6)8)Greenland is south of Jerusalem.The atomic number of helium is 2.Take your time.Rihanna was born in Barbados.DEFINITION 1.1.5. A deduction is a series of hypotheses that is followed by a conclusion.(The conclusion and each of the hypotheses must be an assertion.)If the hypotheses are true and the deduction is a good one, then you have a reason to acceptthe conclusion.EXAMPLE 1.1.6. Here are two deductions.1)Hypotheses:All men are mortal.Socrates is a man.Conclusion: Socrates is mortal.Hypotheses:The Mona Lisa was painted by Leonardo da Vinci.2)Neil Armstrong was the first man on the moon.Conclusion: Justin Trudeau went swimming yesterday.The first of these deductions is very famous (and was discussed by the ancient Greek philosopherAristotle), but the second one is lame. It may seem odd to even call it a deduction, because thetwo hypotheses have nothing at all to do with the conclusion, but, given our definition, it doescount as a deduction. However, it is is a very poor one, so it cannot be relied on as evidencethat the conclusion is true.We are interested in the deductions that do provide solid evidence for their conclusions:

1. Propositional Logic5DEFINITION 1.1.7. A deduction is valid if its conclusion is true whenever all of its hypothesesare true. In other words, it is impossible to have a situation in which all of the hypotheses aretrue, but the conclusion is false.The task of Logic is to distinguish valid deductions from invalid ones.EXAMPLE 1.1.8.Hypotheses:Oranges are either fruits or musical instruments.Oranges are not fruits.Conclusion: Oranges are musical instruments.The conclusion is ridiculous. Nevertheless, the deduction is valid, because its conclusion followsvalidly from its hypotheses; that is, if both hypotheses were true, then the conclusion wouldnecessarily be true. For example, you might be able to imagine that, in some remote rivervalley, there is a variety of orange that is not a fruit, because it is hollow inside, like a gourd.Well, if the other hypothesis is also true in that valley, then the residents must use the orangesto play music.This shows that a logically valid deduction does not need to have true hypotheses or a trueconclusion. Conversely, having true hypotheses and a true conclusion is not enough to make adeduction valid:EXAMPLE 1.1.9.Hypotheses:London is in England.Beijing is in China.Conclusion: Paris is in France.The hypotheses and conclusion of this deduction are, as a matter of fact, all true. This is aterrible deduction, however, because the hypotheses have nothing to do with the conclusion.For example, if Paris declared independence from the rest of France, then the conclusion wouldbe false, even though the hypotheses would both still be true. Thus, it is logically possible tohave a situation in which the hypotheses of this deduction are true and the conclusion is false.Therefore, the deduction is not valid.EXAMPLE 1.1.10. Recall the deduction that you should take an umbrella (on p. 3, above),and suppose for a moment that both of its hypotheses are true. (Thus, you will get wet ifyou do not take an umbrella.) Now is it necessarily true that you should take an umbrella?No—perhaps you enjoy walking in the rain, and you would like to get soaked. In that case,even though the hypotheses were true, the conclusion would be false. Thus, the deduction isnot valid.EXAMPLE 1.1.11.Hypotheses:You are reading this book.This is an undergraduate textbook.Conclusion: You are an undergraduate student.This is not a terrible deduction, because most people who read this book are undergraduatestudents. Yet, it is possible for someone besides an undergraduate to read this book. Forexample, if your mother or father picked up the book and thumbed through it, they would not

61. Propositional Logicimmediately become an undergraduate. So the hypotheses of this deduction, even though theyare true, do not guarantee the truth of the conclusion. Thus, even though some people mightsay that the deduction has some value, it is certainly not valid.Remark 1.1.12. It is important to remember that validity of a deduction is not about the truthor falsity of the deduction’s assertions in the real world. Instead, it is about the form of thededuction, in that the truth of the hypotheses is incompatible with the falsity of the conclusionin every possible world (real or imaginary). Furthermore, a deduction gives you a reason tobelieve its conclusion only in situations where its hypotheses are true.EXERCISES 1.1.13. Which of the following is possible? If it is possible, give an example. Ifit is not possible, explain why.1) A valid deduction that has one false hypothesis and one true hypothesis.2) A valid deduction that has a false conclusion.3) A valid deduction that has at least one false hypothesis, and a true conclusion.4) A valid deduction that has all true hypotheses, and a false conclusion.5) An invalid deduction that has at least one false hypothesis, and a true conclusion.1.2. Logic puzzlesClear thinking (or logic) is important not only in mathematics, but in everyday life, and canalso be fun; many logic puzzles (or brain teasers) can be found on the internet or in bookstores.Here are just a few. Solving problems like these provides good practice for some of the logicskills that will be needed later in this book.EXERCISE 1.2.1 (found online at http://philosophy.hku.hk/think/logic/puzzles.php). There wasa robbery in which a lot of goods were stolen. The robber(s) left in a truck. It is known that:1) No one other than A, B and C was involved in the robbery.2) C never commits a crime without including A as an accomplice.3) B does not know how to drive.So, can you tell whether A is innocent?EXERCISES 1.2.2. On the island of Knights and Knaves, every resident is either a Knight ora Knave (and they all know the status of everyone else). It is important to know that: Knights always tell the truth. Knaves always lie.More precisely, every assertion spoken by a Knight is true, and every assertion spoken by aKnave is false.You will meet some residents of the island, and your job is to figure out whether each ofthem is a Knight or a Knave.1) You meet Alice and Bob on the island. Alice says “Bob and I are Knights.” Bob says,“That’s a lie! She’s a Knave!” What are they?2) You meet Charlie, Diane, and Ed on the island. Charlie says, “Be careful, not all threeof us are Knights.” Diane says, “But not all of us are Knaves, either.” Ed says, “Don’tlisten to them, I’m the only Knight.” What are they? http://en.wikipedia.org/wiki/Knights and knaves

1. Propositional Logic73) You meet Frances and George on the island. Frances mumbles something, but youcan’t understand it. George says, “She said she’s a Knave. And she sure is — don’ttrust her!” What are they?EXERCISE 1.2.3. Complete each of these mini-Sudoku puzzles, by putting a number from 1to 4 in each box, so that no number appears twice in any row or column, or in any of the four2 2 boxes with dark outlines. (Each of the puzzles has a unique solution.)4312a)b)324234 12c)1EXERCISE 1.2.4. In a game similar to Mastermind, one player chooses a secret 4-digit number,using only the digits 1–6, inclusive. (Repeated digits are allowed.) The other player makes aseries of guesses. After each guess, the first player tells the other how many of the digits are inthe guess are perfectly correct, and how many of the other digits are correct, but in the wrongplace. In each of the following games, there is now enough information to determine the secretnumber. Figure out the secret number.guess # correct # in wrong spotguess # correct # in wrong spot123403123402235403451612a) 3642b) 4621111151430365430245121254110340401.3. Using letters to symbolize assertionsIn the remainder of this chapter, we will discuss a logical language called Propositional Logic. Itprovides a convenient way to describe the logical relationship between two (or more) assertions,by using capital letters to represent assertions. Considered only as a symbol of PropositionalLogic, the letter A could mean any assertion. So, when translating from English into Propositional Logic, it is important to provide a symbolization key that specifies what assertion isrepresented by each letter.For example, consider this deduction:Hypotheses:There is an apple on the desk.If there is an apple on the desk, then Jenny made it to class.Conclusion: Jenny made it to class.This is obviously a valid deduction in English.What happens if we replace each assertion with a letter? Our symbolization key would looklike this:A: There is an apple on the desk.B: If there is an apple on the desk, then Jenny made it to class.C: Jenny made it to class.

81. Propositional LogicWe would then symbolize the deduction in this way:Hypotheses:ABConclusion: CUnfortunately, there is no necessary connection between two assertions A and B, which couldbe any assertions, and a third assertion C, which could be any assertion, so this is not a validdeduction. Thus, the validity of the original deduction has been lost in this translation; weneed to do something else in order to preserve the logical structure of the original deductionand obtain a valid translation.The important thing about the original deduction is that the second hypothesis is not merelyany assertion, logically divorced from the other assertions in the deduction. Instead, the secondhypothesis contains the first hypothesis and the conclusion as parts. Our symbolization keyfor the deduction only needs to include meanings for A and C, and we can build the secondhypothesis from those pieces. So we could symbolize the deduction this way:Hypotheses:AIf A, then C.Conclusion: CThis preserves the structure of the deduction that makes it valid, but it still makes use of theEnglish expression “If. . . then. . .” Eventually, we will replace all of the English expressions withmathematical notation, but this is a good start.The assertions that are symbolized with a single letter are called atomic assertions, becausethey are the basic building blocks out of which more complex assertions are built. Whateverlogical structure an assertion might have is lost when it is translated as an atomic assertion.From the point of view of Propositional Logic, the assertion is just a letter. It can be used tobuild more complex assertions, but it cannot be taken apart.NOTATION 1.3.1. The symbol “. . ” means “therefore,” and we will often useA, B, C, . . . , . . Zas an abbreviation for the deductionHypotheses:ABC.Conclusion: Z.1.4. Connectives ( , &, , , )Logical connectives are used to build complex assertions from simpler pieces. There are fivelogical connectives in Propositional Logic. This table summarizes them, and they are explainedbelow.

1. Propositional Logic9symbol nicknamewhat it means not“It is not the case that”&and“Bothand” or“Eitheror” implies“Ifthen” iff“if and only if”Remark 1.4.1. As we learn to write proofs, it will be important to be able to produce a deductionin Propositional Logic from a sequence of assertions in English. It will also be important to beable to retrieve the English meaning from a sequence of assertions in Propositional Logic, givena symbolization key. The above table should prove useful in both of these tasks.1.4A. Not ( ). As an example, consider how we might symbolize these assertions:1. Mary is in Barcelona.2. Mary is not in Barcelona.3. Mary is somewhere other than Barcelona.In order to symbolize Assertion 1, we will need one letter. We can provide a symbolizationkey:B: Mary is in Barcelona.Note that here we are giving B a different interpretation than we did in the previous section.The symbolization key only specifies what B means in a specific context. It is vital that wecontinue to use this meaning of B so long as we are talking about Mary and Barcelona. Later,when we are symbolizing different assertions, we can write a new symbolization key and use Bto mean something else.Now, Assertion 1 is simply B.Since Assertion 2 is obviously related to Assertion 1, we do not want to introduce a differentletter to represent it. To put it partly in English, the assertion means “It is not true that B.”For short, logicians say “Not B.” This is called the logical negation of B. In order to convert itentirely to symbols, we will use “ ” to denote logical negation. Then we can symbolize “Not B”as B.Assertion 3 is about whether or not Mary is in Barcelona, but it does not contain the word“not.” Nevertheless, they both mean “It is not the case that Mary is in Barcelona.” As such, wecan translate both Assertion 2 and Assertion 3 as B.An assertion can be symbolized as A ifit can be paraphrased in English as “It is not the case that A .”Consider these further examples:4. The widget can be replaced if it breaks.5. The widget is irreplaceable.6. The widget is not irreplaceable.If we let R mean “The widget is replaceable,” then Assertion 4 can be translated as R.What about Assertion 5? Saying the widget is irreplaceable means that it is not the casethat the widget is replaceable. So even though Assertion 5 is not negative in English, wesymbolize it using negation as R.Assertion 6 can be paraphrased as “It is not the case that the widget is irreplaceable.”Now, as we have already discussed, “The widget is irreplaceable” can be symbolized as “ R.”Therefore, Assertion 6 can be formulated as “it is not the case that R.” Hence, it is the negationof R, so it can be symbolized as R. This is a double negation. (However, if you think about

101. Propositional Logicthe assertion in English, it is another way of saying the same thing as Assertion 4. In general,we will see that if A is any assertion, then A and A are “logically equivalent.”)More examples:7. Elliott is short.8. Elliott is tall.If we let S mean “Elliot is short,” then we can symbolize Assertion 7 as S.However, it would be a mistake to symbolize Assertion 8 as S. If Elliott is tall, then he isnot short—but Assertion 8 does not mean the same thing as “It is not the case that Elliott isshort.” It could be that he is not tall but that he is not short either: perhaps he is somewherebetween the two (average height). In order to symbolize Assertion 8, we would need a newassertion letter.For any assertion A : If A is true, then A is false. If A is true, then A is false.Using “T” for true and “F” for false, we can summarize this in a truth table for negation:ATF AFTEXERCISES 1.4.2. Using the given symbolization key, translate each English-

the fundamentals of abstract mathematics by Dave Witte Morris and Joy Morris University of Lethbridge incorporating material by P.D. Magnus University at Albany, State University of New York Preliminary Version 0.92 of December 2016 This book is ff under a Creative Co