Introduction to Logic CSE235 Introduction to Logic Introduction Usefulness of Logic Propositional Equivalences 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 1 40 Introduction I Introduction to Logic CSE235 Introduction Propositions Connectives Truth Tables Usefulness of Logic Propositional Equivalences 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 2 40 Introduction II Introduction to Logic CSE235 Introduction Propositions Connectives Truth Tables Usefulness of Logic Propositional Equivalences 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 40 Examples I Introduction to Logic CSE235 Introduction Propositions Connectives Truth Tables Usefulness of Logic Example Propositions Today is Monday The derivative of sin x is cos x Every even number has at least two factors Propositional Equivalences Example Not Propositions C is the best language When is the pretest Do your homework 4 40 Examples II Introduction to Logic CSE235 Introduction Propositions Connectives Truth Tables Usefulness of Logic Propositional Equivalences Example Propositions 2 2 5 Every integer is divisible by 12 Microsoft is an excellent company 5 40 Logical Connectives Introduction to Logic CSE235 Introduction Propositions Connectives Truth Tables Usefulness of Logic Propositional Equivalences 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 40 Negation Introduction to Logic CSE235 Introduction Propositions Connectives Truth Tables Usefulness of Logic Propositional Equivalences 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 40 p 1 0 Logical And Introduction to Logic CSE235 Introduction Propositions Connectives Truth Tables Usefulness of Logic Propositional Equivalences 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 40 p 0 0 1 1 q 0 1 0 1 p q 0 0 0 1 Logical Or Introduction to Logic CSE235 Introduction Propositions Connectives Truth Tables 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 Usefulness of Logic You may have cake or ice cream 1 Propositional Equivalences Truth table 9 40 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 Introduction to Logic CSE235 Introduction Propositions Connectives Truth Tables Usefulness of Logic Propositional Equivalences 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 40 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 Introduction Propositions Connectives Truth Tables Usefulness of Logic p q is the proposition that is false when p is true and q is false and true otherwise Propositional Equivalences Here p is called the hypothesis or antecedent or premise and q is called the conclusion or consequence Truth table 11 40 p 0 0 1 1 q 0 1 0 1 p q 1 1 0 1 Implications II Introduction to Logic The implication p q can be equivalently read as CSE235 if p then q Introduction Propositions Connectives Truth Tables Usefulness of Logic Propositional Equivalences 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 40 Examples Introduction to Logic CSE235 Introduction Propositions Connectives Truth Tables Usefulness of Logic Propositional Equivalences Example If you buy your air ticket in advance it is cheaper If x is a real number then x2 0 If it rains the grass gets wet If the sprinklers operate the grass gets wet If 2 2 5 then all unicorns are pink 13 40 Exercise Introduction to Logic CSE235 Which of the following implications is true Introduction Propositions Connectives Truth Tables If 1 is a positive number then 2 2 5 Usefulness of Logic Propositional Equivalences If 1 is a positive number then 2 2 4 If sin x 0 then x 0 14 40 Exercise Introduction to Logic CSE235 Which of the following implications is true Introduction Propositions Connectives Truth Tables Usefulness of Logic 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 Propositional Equivalences If 1 is a positive number then 2 2 4 If sin x 0 then x 0 14 40 Exercise Introduction to Logic CSE235 Which of the following implications is true Introduction Propositions Connectives Truth Tables Usefulness of Logic Propositional Equivalences 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 14 40 Exercise Introduction to Logic CSE235 Which of the following implications is true Introduction Propositions Connectives Truth Tables Usefulness of Logic Propositional Equivalences 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
View Full Document
Unlocking...