Notes Introduction to Logic Slides by Christopher M Bourke Instructor Berthe Y Choueiry Fall 2007 Computer Science Engineering 235 Introduction to Discrete Mathematics Sections 1 1 1 2 of Rosen cse235 cse unl edu Introduction I Notes 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 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 Introduction II Notes 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 Examples I Notes Example Propositions 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 I C is the best language I When is the pretest I Do your homework Examples II Notes Example Propositions I 2 2 5 I Every integer is divisible by 12 I Microsoft is an excellent company Logical Connectives Connectives are used to create a compound proposition from two or more other propositions I Negation denoted or I And denoted or Logical Conjunction I Or denoted or Logical Disjunction I Exclusive Or XOR denoted I Implication denoted I Biconditional if and only if denoted Notes Negation Notes A proposition can be negated This is also a proposition We usually denote the negation of a proposition p by p Example Negated Propositions 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 p 0 1 p 1 0 Logical And Notes 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 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 Truth table p 0 0 1 1 q 0 1 0 1 p q 0 0 0 1 Logical Or Notes The logical disjunction or logical or is true if one or both of the propositions are true Example Logical Connective Or I It is raining or it is the second day of lecture 2 2 5 2 2 I You may have cake or ice cream 1 I Truth table 1 Can I have both p 0 0 1 1 q 0 1 0 1 p q 0 0 0 1 p q 0 1 1 1 Exclusive Or Notes 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 I The circuit is either is on or off I Let ab 0 then either a 0 or b 0 but not both I You may have cake or ice cream but not both Truth table p 0 0 1 1 q 0 1 0 1 p q 0 1 1 0 Implications I Notes 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 p 0 0 1 1 q 0 1 0 1 p q 1 1 0 1 Implications II The implication p q can be equivalently read as I if p then q I p implies q I if p q I p only if q I q if p I q when p I q whenever p 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 Notes Examples Notes 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 Exercise Notes Which of the following implications is true 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 Biconditional Notes 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 q 0 1 0 1 p q 1 1 0 1 q p 1 0 1 1 p q 1 0 0 1 Examples Notes p q can be equivalently read as 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 Example 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 Exercise Notes 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 Converse Contrapositive Inverse 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 Notes Truth Tables I Notes Truth Tables are used to show the relationship between the truth values of individual propositions and the compound propositions based on them p 0 0 1 1 p q 0 0 0 1 q 0 1 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 Table Truth Table for Logical Conjunction Disjunction Exclusive Or and Implication Constructing Truth Tables Notes Construct the Truth Table for the following compound proposition p q q p 0 0 1 …
View Full Document
Unlocking...