CHAPTER 2

1 CHAPTER 2 Logic1. Logic a declarative sentence that is eithertrue (denoted either T or 1) orfalse (denoted either F or 0).Notation: Variables are used to represent propositions. The most common variablesused arep, q, has been studied since the classical Greek period ( 600-300BC). The Greeks,most notably Thales, were the first to formally analyze the reasoning process. Aristo-tle (384-322BC), the father of logic , and many other Greeks searched for universaltruths that were irrefutable. A second great period for logic came with the use of sym-bols to simplify complicated logical arguments. Gottfried Leibniz (1646-1716) beganthis work at age 14, but failed to provide a workable foundation for symbolic Boole (1815-1864) is considered the father of symbolic logic.

2 He developedlogic as an abstract mathematical system consisting of defined terms (propositions),operations (conjunction, disjunction, and negation), and rules for using the opera-tions. It is this system that we will study in the first s basic idea was that if simple propositions could be represented by pre-cise symbols, the relation between the propositions could be read as precisely as analgebraic equation. Boole developed an algebra of logic in which certain types ofreasoning were reduced to manipulations of Drilling for oil caused dinosaurs to become extinct. is a LOGIC Look out! is not a How far is it to the next town? is not a x+ 2 = 2x is not a x+ 2 = 2xwhenx= 2 is a apropositionis a declarative sentence that is either true or false.

3 Here aresome further examples of cows are Earth is further from the sun than is life on 2 = are some sentences that are not Do you want to go to the movies? Since a question is not adeclarative sentence, it fails to be a Clean up your room. Likewise, an imperative is not a declar-ative sentence; hence, fails to be a 2x= 2 +x. This is a declarative sentence, but unlessxisassigned a value or is otherwise prescribed, the sentence neither true nor false, hence,not a This sentence is false. What happens if you assume this state-ment is true? false? This example is called a paradox and is not a proposition , becauseit is neither true nor proposition can be assigned one of twotruth values.

4 We use T or 1 for trueand use F or 0 for Logical Operatornegation: notp , Operators(a)conjunction: pandq ,p q.(b)disjunction: porq ,p q.(c)exclusive or: exactly one ofporq , pxorq ,p q.(d)implication: ifpthenq ,p q.(e)biconditional: pif and only ifq ,p LOGIC DEFINITIONS23 DiscussionA sentence like I can jump and skip can be thought of as a combination of thetwo sentences I can jump and I can skip. When we analyze arguments or logicalexpression it is very helpful to break a sentence down to some composition of can createcompound propositionsusing propositional variables, such asp,q,r,s,.., andconnectivesorlogical operators. A logical operator is either aunaryoperator, meaning it is applied to only a single proposition ; or abinaryoperator,meaning it is applied to two tablesare used to exhibit the rela-tionship between the truth values of a compound proposition and the truth values ofits component Negation.

5 Negation Operator, not , has symbol . : This book is interesting. pcan be read as:(i.) This book is not interesting.(ii.) This book is uninteresting.(iii.) It is not the case that this book is Table:p pTFFTD iscussionThenegationoperator is a unary operator which, when applied to a propositionp, changes the truth value ofp. That is, the negation of a propositionp, denotedby p, is the proposition that is false whenpis true and true whenpis false. Forexample, ifpis the statement I understand this , then its negation would be I donot understand this or It is not the case that I understand this. Another notationcommonly used for the negation ofpis , an appropriately inserted not or removed not is sufficient to negatea simple statement.

6 Negating a compound statement may be a bit more complicatedas we will see later LOGIC Conjunction. Conjunction Operator, and , has symbol . : This book is : I am staying at q: This book is interesting, and I am staying at Table:pqp qTTTTFFFTFFFFD iscussionTheconjunctionoperator is the binary operator which, when applied to two propo-sitionspandq, yields the proposition pandq , denotedp q. The conjunctionp qofpandqis the proposition that is true when bothpandqare true and false Disjunction. Disjunction Operator, inclusive or , has symbol . : This book is : I am staying at q: This book is interesting, or I am staying at Table:pqp qTTTTFTFTTFFFD iscussionThedisjunctionoperator is the binary operator which, when applied to two propo-sitionspandq, yields the proposition porq , denotedp q.

7 The disjunctionp qofpandqis the proposition that is true when eitherpis true,qis true, orbotharetrue, and is false otherwise. Thus, the or intended here is theinclusive or. In fact,the symbol is the abbreviation of the Latin wordvelfor the inclusive or .1. LOGIC Exclusive Or. Exclusive Or Operator, xor , has symbol . : This book is : I am staying at q: Either this book is interesting, or I am staying at home, but not Table:pqp qTTFTFTFTTFFFD iscussionTheexclusive oris the binary operator which, when applied to two propositionspandqyields the proposition pxorq , denotedp q, which is true if exactly oneofporqis true, but not both. It is false if both are true or if both are times in our every day language we use or in the exclusive sense.

8 In logic,however, we always mean the inclusive or when we simply use or as a connectivein a proposition . If we mean the exclusive or it must be specified. For example, in arestaurant a menu may say there is a choice of soup or salad with a meal. In logicthis would mean that a customer may choose both a soup and salad with their logical implication of this statement, however, is probably not what is create a sentence that logically states the intent the menu could say that thereis a choice ofeithersoup or salad (but not both). The phrase either .. or .. isnormally indicates the exclusive Implications. Implication Operator, , has symbol . : This book is : I am staying at q: If this book is interesting, then I am staying at Table:pqp qTTTTFFFTTFFTE quivalent Forms of Ifpthenq :1.

9 LOGIC DEFINITIONS26 pimpliesq Ifp,q ponly ifq pis a sufficient condition forq qifp qwheneverp qis a necessary condition forpDiscussionTheimplicationp qis the proposition that is often read ifpthenq. Ifpthenq is false precisely whenpis true butqis false. There are many ways to saythis connective in English. You should study the various forms as shown way to think of the meaning ofp qis to consider it a contract that saysif the first condition is satisfied, then the second will also be satisfied. If the firstcondition,p, is not satisfied, then the condition of the contract is null and void. Inthis case, it does not matter if the second condition is satisfied or not, the contractis still example, suppose your friend tells you that if you meet her for lunch, shewill give you a book she wants you to read.

10 According to this statement, you wouldexpect her to give you a book if you do go to meet her for lunch. But what if you donot meet her for lunch? She did not say anything about that possible situation, soshe would not be breaking any kind of promise if she dropped the book off at yourhouse that night or if she just decided not to give you the book at all. If either ofthese last two possibilities happens, we would still say the implication stated was truebecause she did not break her of the following statements are equivalent to Ifxis even,thenyis odd ? There may be more than one or none.(1)yis odd only ifxis even.(2)xis even is sufficient foryto be odd.(3)xis even is necessary foryto be odd.