离散数学英文讲义：1-1 Logic

1、L o g oL o g o1Discrete MathematicsL o g oL o g o2Section 1.1Chapter 1. Logic and Proof, Sets, and FunctionL o g oL o g oContentsPropositions1Implications2 Precedence of Logical Operators3Translation4Application Examples5L o g oL o g ovPropositionsL o g oL o g oPropositional Logic (1.1)Propositional

2、 Logic is the logic of compound statements built from simpler statements using so-called Boolean connectives.Some applications in computer science:vDesign of digital electronic circuits.vExpressing conditions in programs.vQueries to databases & search engines.George Boole(1815-1864)L o g oL o g

3、oPropositions in natural languageIn propositional logic, a proposition is simply:va statement (i.e., a declarative sentence) with some definite meaningvhaving a truth value thats either true (T) or false (F) Never both, or somewhere “in between”. However, you might not know the truth valueL o g oL o

4、 g oExamples of NL Propositionsv“It is raining.” (In a given situation.)v“Beijing is the capital of China, and 1 + 2 = 2”But, the following are NOT propositions:v“Whos there?” (interrogative: no truth value)v“x := x+1” (imperative: no truth value)v“1 + 2” (term: no truth value)L o g oL o g oSome Pop

5、ular Boolean OperatorsFormal NameNicknameAritySymbolNegation operatorNOTUnaryConjunction operatorANDBinaryDisjunction operatorORBinaryExclusive-OR operatorXORBinaryImplication operatorIMPLIESBinaryBiconditional operatorIFFBinaryL o g oL o g oThe Negation OperatorThe unary negation operator “” (NOT)

6、transforms a prop. into its negation.E.g. If p = “I have brown hair.” then p = “I do not have brown hair.”The truth table for NOT:T : True; F : False“:” means “is defined as”OperandcolumnResultcolumnL o g oL o g oThe Conjunction OperatorThe binary conjunction operator “” (AND) combines two propositi

7、ons to form their logical conjunction.E.g. If p=“I will have salad for lunch.” and q=“I will have steak for dinner.”, then pq=“I will have salad for lunch and I will have steak for dinner.”L o g oL o g ovNote that aconjunctionp1 p2 pnof n propositionswill have 2n rowsin its truth table.vAlso: and op

8、erations together are sufficient to express any Boolean truth table!Conjunction Truth TablepqpqFFFFTFTFFTTTOperand columnsL o g oL o g oThe Disjunction OperatorThe binary disjunction operator “” (OR) combines two propositions to form their logical disjunction.p=“My car has a bad engine.”q=“My car ha

9、s a bad carburetor.”pq=“Either my car has a bad engine, or my car has a bad carburetor.”Meaning is like “and/or” in English.L o g oL o g ovNote that pq meansthat p is true, or q istrue, or both are true!vSo, this operation isalso called inclusive or,because it includes thepossibility that both p and

10、 q are true.v“” and “” together are also universal.Disjunction Truth TablepqpqFFFFT TTFTTT TNotedifferencefrom ANDL o g oL o g oThe Exclusive Or OperatorThe binary exclusive-or operator “” (XOR) combines two propositions to form their logical “exclusive or”.p = “I will earn an A in this course,”q =

11、“I will drop this course,”p q = “I will either earn an A in this course, or I will drop it (but not both!)”L o g oL o g ovNote that pq meansthat p is true, or q istrue, but not both!vThis operation iscalled exclusive or,because it excludes thepossibility that both p and q are true.v“” and “” togethe

12、r are not universal.Exclusive-Or Truth Tablepq pqFFFFTTTFTTTFNotedifferencefrom OR.L o g oL o g oTest your understanding of the two types of disjunction1. Suppose p q is true.Does it follow that pq is true?2. Suppose pq is true.Does it follow that p q is true?L o g oL o g oTest your understanding of

13、 the two types of disjunction1.Suppose p q is true.Does it follow that pq is true?No: consider p TRUE, q TRUE2.Suppose pq is true. Does it follow that p q is true? Yes. Check each of the two assignments that make pq true: a) p TRUE, q FALSE (makes p q true) b) p FALSE, q TRUE (makes p q true) L o g

14、oL o g ovImplicationsL o g oL o g oThe Implication OperatorThe implication p q states that p implies q.I.e., If p is true, then q is true; but if p is not true, then q could be either true or false.E.g., let p = “You study hard.” q = “You will get a good grade.”p q = “If you study hard, then you wil

15、l get a good grade.”antecedentconsequentL o g oL o g oImplication Truth Tablevp q is false only when(p is true but q is not true)vp q does not saythat p causes q!vp q does not requirethat p or q are true!vE.g. “(1=0) pigs can fly” is TRUE!The onlyFalsecase!L o g oL o g oImplication Truth TablevSuppo

16、se you know that q is T. What do you know aboutpq ?L o g oL o g oImplication Truth TablevSuppose you know that q is T. What do you know aboutpq ?vThe conditional must be TL o g oL o g oImplication Truth TablevSuppose you knowthat p is F. Whatdo you know aboutpq ?vThe conditionalmust be TL o g oL o g

17、 oImplications between real sentencsv“If this lecture ever ends, then the sun has risen this morning.” True or False?v“If Tuesday is a day of the week, then I am Andy Lau.” True or False?v“If 1+1=6, then Bush is president.” True or False?v“If the moon is made of green cheese, then I am richer than B

18、ill Gates.” True or False?L o g oL o g oEnglish Phrases Meaning p qv“p implies q”v“if p, then q”v“if p, q”v“when p, q”v“whenever p, q”v“q if p”v“q when p”v“q whenever p”v“p only if q”v“p is sufficient for q”v“q is necessary for p”v“q follows from p”v“q is implied by p”L o g oL o g oContrapositiveSom

19、e terminology, for an implication p q:vIts converse is: q p.vIts contrapositive: q p.vIts Inverse: p q.vWhich of these two has/have the same meaning (express same truth function) as p q? Prove it.L o g oL o g oProving the equivalence of p q and its contrapositive, using truth tables:L o g oL o g oBu

20、t were not studying English .vProbably no two of these expressions have exactly the same meaning in EnglishvFor example, Ill go to the party if Mary goescan be interpreted as implyingIll only go to the party if Mary goesturning the sentence into a biconditional:I go IFF Mary goesL o g oL o g oBicond

21、itional Truth Tablevp q means that p and qhave the same truth value.vNote this truth table is theexact opposite of s!Thus, p q means (p q)vp q does not implythat p and q are true, or that either of them causes the other.p q p qF FTF TFT FFT TTL o g oL o g oConsider .The truth of p q, where1. p= Guan

22、gzhou is in Chinaq= 2+2 =42. p= Japan is not in Asia q= 2+2 =53. p= Scotland is in the UKq= Wales is not in the UKL o g oL o g oConsider .The truth of p q, where1. p= Guangzhou is in China q= 2+2 =4 TRUE2. p= Japan is not in Asia q= 2+2 =5 TRUE3. p= Scotland is in the UKq= Wales is not in the UK FAL

23、SEL o g oL o g ovPrecedence of Logical OperatorsL o g oL o g oBoolean Operations SummaryvWe have seen 1 unary operator (out of the 4 possible ones) and 5 binary operators:L o g oL o g oSome Alternative NotationsName:not and orxor impliesiffPropositional logic:Boolean algebra:ppq+C/C+/Java (wordwise)

24、:!& | !=C/C+/Java (bitwise):&|Logic gates:L o g oL o g oPrecedence of Logical Operators L o g oL o g ovTranslationsL o g oL o g oExample 1v“I just saw my old friend, and either hes grown or Ive shrunk.”vSolution: Let f represent “I just saw my old friend”. Let g represent “hes grown ”. Let s

25、 represent “Ive shrunk”. The sentence can be represented as f (g s).(f g) s would mean something different.f g s would be ambiguous.L o g oL o g oExample 2Solution:Let r =“The lawn was wet this morning”, p =“It rained last night”, q =“The sprinklers came on last night”. Thus, p = “It didnt rain last

26、 night.” r p = “The lawn was wet this morning, andit didnt rain last night.” The sentence can be represented as r p q “Either the lawn wasnt wet this morning, or it rained last night, or the sprinklers came on last night.”L o g oL o g oExample 3v“You cannot ride the roller coaster if you are under 4 feet tall unless you are older than 16 years old.”vSolution: Let q = “You can ride the roller coaster ”, r = “you are under 4 feet tall ”, s = “you