Introduction to Logic CSE235 Introduction to Logic Slides by Christopher M Bourke Instructor Berthe Y Choueiry Spring 2006 Computer Science Engineering 235 Introduction to Discrete Mathematics 1 1 Sections 1 1 1 2 of Rosen Introduction I Introduction to Logic CSE235 Propositional calculus or logic is the study of the logical relationship between objects called propositions and forms the basis of all mathematical reasoning Definition A proposition is a statement that is either true or false but not both we usually denote a proposition by letters p q r s 2 1 Introduction II Introduction to Logic CSE235 Definition The value of a proposition is called its truth value denoted by T or 1 if it is true and F or 0 if it is false Opinions interrogative and imperative sentences are not propositions Truth table p 0 1 3 1 Examples I Introduction to Logic CSE235 Example Propositions Today is Monday The derivative of sin x is cos x Every even number has at least two factors Example Not Propositions C is the best language When is the pretest Do your homework 4 1 Examples II Introduction to Logic CSE235 Example Propositions 2 2 5 Every integer is divisible by 12 Microsoft is an excellent company 5 1 Logical Connectives Introduction to Logic CSE235 Connectives are used to create a compound proposition from two or more other propositions Negation denoted or And denoted or Logical Conjunction Or denoted or Logical Disjunction Exclusive Or XOR denoted Implication denoted Biconditional if and only if denoted 6 1 Negation Introduction to Logic CSE235 A proposition can be negated This is also a proposition We usually denote the negation of a proposition p by p Example Negated Propositions Today is not Monday It is not the case that today is Monday It is not the case that the derivative of sin x is cos x Truth table p 0 1 7 1 p 1 0 Logical And Introduction to Logic CSE235 The logical connective And is true only if both of the propositions are true It is also referred to as a conjunction Example Logical Connective And It is raining and it is warm 2 3 5 2 2 Schro dinger s cat is dead and Schro dinger s cat is not dead Truth table 8 1 p 0 0 1 1 q 0 1 0 1 p q 0 0 0 1 Logical Or Introduction to Logic CSE235 The logical disjunction or logical or is true if one or both of the propositions are true Example Logical Connective Or It is raining or it is the second day of lecture 2 2 5 2 2 You may have cake or ice cream 1 Truth table p 0 0 1 1 9 1 q 0 1 0 1 p q 0 0 0 1 p q 0 1 1 1 Exclusive Or Introduction to Logic CSE235 The exclusive or of two propositions is true when exactly one of its propositions is true and the other one is false Example Logical Connective Exclusive Or The circuit is either is on or off Let ab 0 then either a 0 or b 0 but not both You may have cake or ice cream but not both Truth table p 0 0 1 1 10 1 q 0 1 0 1 p q 0 1 1 0 Implications I Introduction to Logic CSE235 Definition Let p and q be propositions The implication p q is the proposition that is false when p is true and q is false and true otherwise Here p is called the hypothesis or antecedent or premise and q is called the conclusion or consequence Truth table 11 1 p 0 0 1 q 0 1 0 p q 1 1 0 Implications II Introduction to Logic The implication p q can be equivalently read as CSE235 if p then q p implies q if p q p only if q q if p q when p q whenever p p is a sufficient condition for q p is sufficient for q q is a necessary condition for p q is necessary for p q follows from p 12 1 Examples Introduction to Logic CSE235 Example If you buy your air ticket in advance it is cheaper If 2 2 5 then all unicorns are pink If x is a real number then x2 0 If it rains the grass gets wet If the sprinklers operate the grass gets wet 13 1 Exercise Introduction to Logic CSE235 Which of the following implications is true If 1 is a positive number then 2 2 5 If 1 is a positive number then 2 2 4 If sin x 0 then x 0 14 1 Exercise Introduction to Logic CSE235 Which of the following implications is true If 1 is a positive number then 2 2 5 true the hypothesis is obviously false thus no matter what the conclusion the implication holds If 1 is a positive number then 2 2 4 If sin x 0 then x 0 15 1 Exercise Introduction to Logic CSE235 Which of the following implications is true If 1 is a positive number then 2 2 5 true the hypothesis is obviously false thus no matter what the conclusion the implication holds If 1 is a positive number then 2 2 4 true for the same reason as above If sin x 0 then x 0 16 1 Exercise Introduction to Logic CSE235 Which of the following implications is true If 1 is a positive number then 2 2 5 true the hypothesis is obviously false thus no matter what the conclusion the implication holds If 1 is a positive number then 2 2 4 true for the same reason as above If sin x 0 then x 0 false x can be any multiple of i e if we let x 2 then clearly sin x 0 but x 6 0 The implication if sin x 0 then x k for some integer k is true 17 1 Biconditional Introduction to Logic CSE235 Definition The biconditional p q is the proposition that is true when p and q have the same truth values It is false otherwise Note that it is equivalent to p q q p Truth table p 0 0 1 1 18 1 q 0 1 0 1 p q 1 1 0 1 q p 1 0 1 1 p q 1 0 0 1 Examples Introduction to Logic CSE235 p q can be equivalently read as p if and only if q p is necessary and sufficient for q if p then q and conversely p iff q Note typo in textbook page 9 line 3 Example x 0 if and only if x2 is positive The alarm goes off iff a burglar breaks in You may have pudding if and only if you eat your meat 1 19 1 1 How can you have any pudding if you don t eat your meat Exercise Introduction to Logic CSE235 Which of the following biconditionals is true x2 y 2 0 if and only if x 0 and y 0 2 2 4 …
View Full Document
Unlocking...