Introduction to Logic Sections 1 1 and 1 2 of Rosen Fall 2008 CSCE 235 Introduction to Discrete Structures cse235 cse unl edu Introduction Logic We will study Propositional Logic PL First Order Logic FOL Logic is the study of the logic relationships between objects and forms the basis of all mathematical reasoning and all automated reasoning CSCE 235 Fall 2008 Logic 2 Introduction PL In Propositional Logic a k a Propositional Calculus or Sentential Logic the objects are called propositions Definition A proposition is a statement that is either true or false but not both We usually denote a proposition by a letter p q r s CSCE 235 Fall 2008 Logic 3 Outline Defining Propositional Logic Propositions Connectives Truth tables Precedence of Logical Operators Usefulness of Logic Bitwise operations Logic in Theoretical Computer Science SAT Logic in Programming Logical Equivalences Terminology Truth tables Equivalence rules CSCE 235 Fall 2008 Logic 4 Introduction Proposition Definition The value of a proposition is called its truth value denoted by T or 1 if it is true or F or 0 if it is false Opinions interrogative and imperative are not propositions Truth table p 0 1 CSCE 235 Fall 2008 Logic 5 Propositions Examples The following are propositions Today is Monday The grass is wet It is raining R M W The following are not propositions C is the best language Opinion When is the pretest Interrogative Do your homework Imperative CSCE 235 Fall 2008 Logic 6 Are these propositions 2 2 5 Every integer is divisible by 12 Microsoft is an excellent company CSCE 235 Fall 2008 Logic 7 Logical connectives Connectives are used to create a compound proposition from two or more propositions Negation denote or neg And or logical conjunction denoted wedge Or or logical disjunction denoted vee XOR or exclusive or denoted xor Implication denoted or Rightarrow rightarrow Biconditional denoted or LeftRightarrow leftrightarrow We define the meaning semantics of the logical connectives using truth tables CSCE 235 Fall 2008 Logic 8 Logical Connective Negation p the negation of a proposition p is also a proposition Examples Today is not Monday It is not the case that today is Monday etc Truth table CSCE 235 Fall 2008 p p 0 1 1 0 Logic 9 Logical Connective Logical And The logical connective And is true only when both of the propositions are true It is also called a conjunction Examples It is raining and it is warm 2 3 5 and 1 2 Schroedinger s cat is dead and Schroedinger s is not dead Truth table CSCE 235 Fall 2008 p q 0 0 0 1 1 0 1 1 p q Logic 10 Logical Connective Logical Or The logical disjunction or logical Or is true if one or both of the propositions are true Examples It is raining or it is the second lecture 2 2 5 1 2 You may have cake or ice cream Truth table CSCE 235 Fall 2008 p q 0 0 p q 0 0 1 0 1 0 0 1 1 1 Logic p q 11 Logical Connective Exclusive Or The exclusive Or or XOR of two propositions is true when exactly one of the propositions is true and the other one is false Example The circuit is either ON or OFF but not both 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 CSCE 235 Fall 2008 p q 0 0 p q 0 p q 0 0 1 0 1 1 0 0 1 1 1 1 1 Logic p q 12 Logical Connective Implication 1 Definition Let p and q be two propositions The implication p q is the proposition that is false when p is true and q is false and true otherwise p is called the hypothesis antecedent premise q is called the conclusion consequence Truth table CSCE 235 Fall 2008 p q 0 0 p q 0 p q 0 p q 0 0 1 0 1 1 1 0 0 1 1 1 1 1 1 0 Logic p q 13 Logical Connective Implication 2 The implication of p q can be also read as If p then q p implies q If p q p only if q q if p q when p q whenever p q follows from 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 CSCE 235 Fall 2008 Logic 14 Logical Connective Implication 3 Examples If you buy you air ticket in advance it is cheaper If x is an integer 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 CSCE 235 Fall 2008 Logic 15 Exercise Which of the following implications is true If 1 is a positive number then 2 2 5 True The premise is obviously false thus no matter what the conclusion is the implication holds If 1 is a positive number then 2 2 4 True Same as above If sin x 0 then x 0 False x can be a multiple of If we let x 2 then sin x 0 but x 0 The implication if sin x 0 then x k for some k is true CSCE 235 Fall 2008 Logic 16 Logical Connective Biconditional 1 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 q p q p q p q p q p q CSCE 235 Fall 2008 0 0 0 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 Logic 17 Logical Connective Biconditional 2 The biconditional p q can be equivalently read as p if and only if q p is a necessary and sufficient condition for q if p then q and conversely p iff q Note typo in textbook page 9 line 3 Examples x 0 if and only if x2 is positive The alarm goes off iff a burglar breaks in You may have pudding iff you eat your meat CSCE 235 Fall 2008 Logic 18 Exercise Which of the following biconditionals is true x2 y2 0 if and only if x 0 and y 0 True Both implications hold 2 2 4 if and only if 2 2 True Both implications hold x2 0 if and only if x 0 False The implication if x 0 then x2 0 holds However the implication if x2 0 then x 0 is false Consider x 1 The hypothesis 1 2 1 0 but the conclusion fails CSCE 235 Fall 2008 Logic 19 Converse Inverse Contrapositive Consider the proposition p q Its converse is the proposition q p Its inverse is the proposition p q Its contrapositive is the proposition q p CSCE 235 Fall 2008 Logic 20 Truth Tables Truth tables are used to …
View Full Document
Unlocking...