Introduction I Introduction to Logic Slides by Christopher M Bourke Instructor Berthe Y Choueiry Propositional calculus or logic is the study of the logical relationship between objects called propositions and forms the basis of all mathematical reasoning and all automated reasoning Definition Fall 2007 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 Computer Science Engineering 235 Introduction to Discrete Mathematics Sections 1 1 1 2 of Rosen cse235 cse unl edu Introduction II Examples I Example Propositions 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 I Today is Monday I The derivative of sin x is cos x I Every even number has at least two factors Example Not Propositions p 0 1 Examples II Example Propositions I C is the best language I When is the pretest I Do your homework Logical Connectives Connectives are used to create a compound proposition from two or more other propositions I Negation denoted or I 2 2 5 I And denoted or Logical Conjunction I Every integer is divisible by 12 I Or denoted or Logical Disjunction I Microsoft is an excellent company I Exclusive Or XOR denoted I Implication denoted I Biconditional if and only if denoted Negation Logical And A proposition can be negated This is also a proposition We usually denote the negation of a proposition p by p 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 Example Negated Propositions I It is raining and it is warm 2 3 5 2 2 I Schro dinger s cat is dead and Schro dinger s cat is not dead I I Today is not Monday I It is not the case that today is Monday I It is not the case that the derivative of sin x is cos x Truth table Truth table p 0 1 p 0 0 1 1 p 1 0 Logical Or q 0 1 0 1 p q 0 0 0 1 Exclusive Or The logical disjunction or logical or is true if one or both of the propositions are true 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 Or Example Logical Connective Exclusive Or I The circuit is either is on or off I It is raining or it is the second day of lecture 2 2 5 2 2 I Let ab 0 then either a 0 or b 0 but not both I You may have cake or ice cream 1 I You may have cake or ice cream but not both I Truth table 1 p 0 0 1 1 q 0 1 0 1 p q 0 0 0 1 p q 0 1 1 1 Truth table p 0 0 1 1 q 0 1 0 1 p q 0 1 1 0 Can I have both Implications I Implications II Definition The implication p q can be equivalently read as Let p and q be propositions The implication I if p then q I p implies q I if p q I p only if q I q if p Here p is called the hypothesis or antecedent or premise and q is called the conclusion or consequence I q when p I q whenever p Truth table I p is a sufficient condition for q p is sufficient for q I q is a necessary condition for p q is necessary for p I q follows from p p q is the proposition that is false when p is true and q is false and true otherwise p 0 0 1 1 q 0 1 0 1 p q 1 1 0 1 Examples Exercise Which of the following implications is true Example I If you buy your air ticket in advance it is cheaper I If x is a real number then x2 0 I If it rains the grass gets wet I If the sprinklers operate the grass gets wet I If 2 2 5 then all unicorns are pink Biconditional I 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 I If 1 is a positive number then 2 2 4 true for the same reason as above I 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 Examples Definition p q can be equivalently read as The biconditional p q is the proposition that is true when p and q have the same truth values It is false otherwise I p if and only if q I p is necessary and sufficient for q I if p then q and conversely I p iff q Note typo in textbook page 9 line 3 Note that it is equivalent to p q q p Example Truth table p 0 0 1 1 q 0 1 0 1 p q 1 1 0 1 q p 1 0 1 1 p q 1 0 0 1 Exercise I x 0 if and only if x2 is positive I The alarm goes off iff a burglar breaks in I You may have pudding if and only if you eat your meat Converse Contrapositive Inverse Which of the following biconditionals is true I I I x2 y 2 0 if and only if x 0 and y 0 true both implications hold 2 2 4 if and only if 2 2 true for the same reason above x2 0 if and only if x 0 false The converse holds That is if x 0 then x2 0 However the implication is false consider x 1 Then the hypothesis is true 1 2 12 0 but the conclusion fails Consider the proposition p q I Its converse is the proposistion q p I Its inverse is the proposistion p q I Its contrapositive is the proposistion q p Truth Tables I Constructing Truth Tables Truth Tables are used to show the relationship between the truth values of individual propositions and the compound propositions based on them Construct the Truth Table for the following compound proposition p q q p 0 0 1 1 q 0 1 0 1 p q 0 0 0 1 p q 0 1 1 1 p q 0 1 1 0 p q 1 1 0 1 p q 1 0 0 1 p 0 0 1 1 Table Truth Table for Logical Conjunction Disjunction Exclusive Or and Implication Precedence of Logical Operators q 0 1 0 1 p q 0 0 0 1 q 1 0 1 …
View Full Document
Unlocking...