1、DISCRETE MATHEMATICS,The Course,Totally 64 (class hours) Grading policy: Attendance binary operators take 2 operands (e.g., 3 4). Propositional or Boolean or logical operators operate on propositions (or their truth values) instead of on numbers.,Operators / Connectives,Compound Propositions,In Prop

2、ositional Logic, we assume a collection of atomic (or component) propositions are given: p, q, r, s, t, . Then we form compound propositions by using logical connectives (logical operators) to form propositional “molecules”.,Some Popular Logical Operators,Constructing a truth table,Determine the tru

3、th values of the compound proposition one column for each propositional variable. one for the compound proposition. count in binary n propositional variables = 2n rows.,e.g.,The Negation Operator “”,The unary negation operator transforms a prop. into its logical negation. E.g. If p = “I have brown h

4、air.” then p = “I do not have brown hair.” The truth table for NOT:,T : True; F : False “:” means “is defined as”,Operandcolumn,Resultcolumn,The Conjunction Operator “”,The binary conjunction operator combines two propositions to form their logical conjunction. E.g. p=“I will have salad for lunch.”

5、and q=“I will have steak for dinner.”, then pq=“I will have salad for lunch and I will have steak for dinner.”,Meaning is like “and” in English.,Note that aconjunctionp1 p2 pnof n propositionswill have 2n rowsin its truth table. Also: and operations together are sufficient to express any Boolean tru

6、th table!,Conjunction Truth Table,Operand columns,The Disjunction Operator “”,The binary disjunction operator Combines two propositions to form their logical disjunction. p=“My car has a bad engine.” q=“My car has a bad transmission.” pq=“Either my car has a bad engine, or my car has a bad transmiss

7、ion.”,Meaning is like “or” in English.,Note that pq meansthat p is true, or q istrue, or both are true! So, this operation isalso called inclusive or,because it includes thepossibility that both p and q are true.,Disjunction Truth Table,Notedifferencefrom AND,A Simple Exercise,Let p = “It rained las

8、t night”, q = “The sprinklers came on last night,” r = “The lawn was wet this morning.” Translate each of the following into English: p = r p = r p q =,“It didnt rain last night.”,“The lawn was wet this morning, and it didnt rain last night.”,“Either the lawn wasnt wet this morning, or it rained las

9、t night, or the sprinklers came on last night.”,The Exclusive Or Operator,The binary exclusive-or operator “” (XOR) combines two propositions to form their logical “exclusive or”. p = “I will earn an A in this course,” q = “I will drop this course,” p q = “I will either earn an A in this course, or

10、I will drop it (but not both!)”,Note that pq meansthat p is true, or q istrue, but not both! This operation iscalled exclusive or,because it excludes thepossibility that both p and q are true.,Exclusive-Or Truth Table,Notedifferencefrom OR.,Note that English “or” can be ambiguous regarding the “both

11、” case! “Pat is a singer orPat is a writer.” - “Pat has got an A orPat has got a B.” - Need context to disambiguate the meaning! For this class, assume “or” means inclusive.,Natural Language is Ambiguous,The Implication Operator,The implication p q states that p implies q. e.g., let p = “You study h

12、ard.” q = “You will get a good grade.” p q = “If you study hard, then you will get a good grade.”,Hypothesis,Conclusion,Implication Truth Table,p q is false only whenp is true but q is not true. p q does not requirethat p or q are ever true! p q does not saythat p causes q! E.g. “(1=0) pigs can fly”

13、 is TRUE!,The onlyFalsecase!,Why does this seem wrong?,Consider a sentence like, “If I wear a red shirt tomorrow, then it will snow!” In logic, we consider the sentence True as long as either I dont wear a red shirt, or it snowed. But, in normal English conversation, if I were to make this claim, yo

14、u would think that I was lying.,Examples of Implications,“If this lecture ever ends, then the sun will rise tomorrow.” True or False? “If Tuesday is a day of the week, then I am a penguin.” True or False? “If 1+1=6, then Bush is president.” True or False? “If the moon is made of green cheese, then I

15、 am richer than Bill Gates.” True or False?,English Phrases Meaning p q,“p implies q” “if p, then q” “if p, q” “when p, q” “whenever p, q” “q if p” “q when p” “q whenever p”,“p only if q” “p is sufficient for q” “q is necessary for p” “q follows from p” “q is implied by p” “q unless p”,Converse, Inv

16、erse, Contrapositive,Some terminology, for an implication p q: Its converse is: q p. Its inverse is: p q. Its contrapositive: q p. One of these three has the same meaning (same truth table) as p q. Can you figure out which?,Contrapositive,How do we know for sure?,Proving the equivalence of p q and i

17、ts contrapositive using truth tables:,Example of the Converse, Inverse, Contrapositive,Raining tomorrow is a sufficient condition for my not going to town. Step 1: Assign propositional variables to component propositions p: It will rain tomorrow q: I will not go to town Step 2: Symbolize the asserti

18、on: p q Step 3: Symbolize the converse: q p Step 4: Convert the symbols back into words If I dont go to town then it will rain tomorrow,The biconditional operator,The biconditional p q states that p is true if and only if (IFF) q is true. p = “Bush wins the 2004 election.” q = “Bush will be presiden

19、t for all of 2005.” p q = “If, and only if, Bush wins the 2004 election, Bush will be president for all of 2005.”,2004,Im staying,2005,Biconditional Truth Table,p q means that p and qhave the same truth value. Note this truth table is theexact opposite of s! Thus, p q means (p q) p q does not implyt

20、hat p and q are true. p q is equivalent to (p q) / (q p).,Precedence of operators,We can have compound statements r p q What is the order of applying logical operators? We use parenthesis to specify the order If no parenthesis, we still have a precedence list. p q means (p ) q,Translating English Se

21、ntences,To remove the ambiguity “ You can access the Internet from campus only if you are a computer science major or you are not a freshman” Solution: Let a=“You can access the Internet from campus” c=“You are a computer science major” f=“You are a freshman” The sentence can be represented by a c f

22、,Implies,Translating English Sentences,Unless you are older than 16 years old, you cannot ride the roller coaster if you are under 4 feet tall Solution: Let q: you can ride the roller coaster r: you are under 4 feet tall s: you are older than 16 The sentence can be represented by: s (r q) or (s r q)

23、,System Specifications,Whether following specifications are consistent: “ The message is stored in the buffer or is retransmitted” “The message is not stored in the buffer” “If the message is stored in the buffer, then it is retransmitted” Solution: Let p denote “The message is stored in the buffer”

24、 q denote “The message is retransmitted”,p q, p,p q,They are consistent when p is false and q is true.,What are logic puzzles?,A puzzle deriving from the mathematicsfield of deduction Produced by Charles Lutwidge Dodgson A puzzle that can be solved using logicalreasoning It helps work with rules of

25、logic (and, or, xor, etc.) Programs that carry out logical reasoninguse these puzzles to illustrate capabilities,Logic Puzzles,Two kinds of inhabitants: Knights: always tell the truth; Knaves: always lie. You encounter 2 people A and B. A says:”B is a knight”, B says: “I and A are of opposite types”

26、. What are A and B? Solution: Let p denote “A is a knight” ; q denote “B is a knight” : consistent; X : inconsistent,Knight, Knave and Spy Problem,Added rule: Spy can lie or tell the truth. There is one spy, one knight, and one knave. A says that C is a knave. B says that A is a knight. C says “I am

27、 the spy.” What are A, B and C? From Cs statement, C cant be a knight because a knight never lie about his identity. Therefore, C is either a knave or a spy.,Knight, Knave and Spy Problem,There is one spy, one knight, and one knave. A says that C is a knave. B says that A is a knight. C says “I am t

28、he spy.” What are A, B and C? Solution: Suppose C is a spy. Then C is not a knave. Then What A says is false, so A is knave. Then B must be a knight, and what B says must be true. Then A is a knight. Contradiction!,Answer: C is a knave. A is telling the truth, so A is a knight. B is a spy.,Boolean O

29、perations Summary,We have seen 1 unary operator and 5 binary operators. Their truth tables are below.,Some Alternative Notations,Logic and Bit Operations,A bit is a binary (base 2) digit: 0 or 1. Bits may be used to represent truth values. By convention: 0 represents “false”; 1 represents “true”. Bo

30、olean algebra is like ordinary algebra except that variables stand for bits, + means “or”, and multiplication means “and”. See chapter 11 for more details.,Bit Strings,A Bit string of length n is an ordered sequence (series, tuple) of n0 bits. By convention, bit strings are (sometimes) written left to right: e.g. the “first” bit of the bi