Introductionto LogicCSE235Introduction to LogicSlides by Christopher M. BourkeInstructor: Berthe Y. ChoueirySpring 2006Computer Science & Engineering 235Introduction to Discrete MathematicsSections 1.1-1.2 of [email protected] / 1Introductionto LogicCSE235Introduction IPropositional calculus (or logic) is the study of the logicalrelationship between objects called propositions and forms thebasis of all mathematical reasoning.DefinitionA prop osition is a statement that is either true or false, but notboth (we usually denote a proposition by letters; p, q, r, s, . . .).2 / 1Introductionto LogicCSE235Introduction IIDefinitionThe value of a proposition is called its truth value; denoted byT or 1 if it is true and F or 0 if it is false.Opinions, interrogative and imperative sentences are notpropositions.Truth table:p013 / 1Introductionto LogicCSE235Examples IExample (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 / 1Introductionto LogicCSE235Examples IIExample (Propositions?)2 + 2 = 5Every integer is divisible by 12.Microsoft is an excellent company.5 / 1Introductionto LogicCSE235Logical ConnectivesConnectives are used to create a compound proposition fromtwo or more other propositions.Negation (denoted ¬ or !)And (denoted ∧) or Logical ConjunctionOr (denoted ∨) or Logical DisjunctionExclusive Or (XOR, denoted ⊕)Implication (denoted →)Biconditional; “if and only if” (denoted ↔)6 / 1Introductionto LogicCSE235NegationA proposition can be negated. This is also a proposition. Weusually 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 ¬p0 11 07 / 1Introductionto LogicCSE235Logical AndThe logical connective And is true only if both of thepropositions 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)Schr¨odinger’s cat is dead and Schr¨odinger’s cat is notdead.Truth table:p q p ∧ q0 0 00 1 01 0 01 1 18 / 1Introductionto LogicCSE235Logical OrThe logical disjunction (or logical or) is true if one or both ofthe 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.1Truth table:p q p ∧ q p ∨ q0 0 0 00 1 0 11 0 0 11 1 1 11Can I have both?9 / 1Introductionto LogicCSE235Exclusive OrThe exclusive or of two propositions is true when exactly one ofits propositions is true and the other one is false.Example (Logical Connective: Exclusi ve 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 q p ⊕ q0 0 00 1 11 0 11 1 010 / 1Introductionto LogicCSE235Implications IDefinitionLet p and q be propos itions. The implicationp → qis the proposition that is false when p is true and q is false andtrue otherwise.Here, p is called the “hypothesis” (or “antecedent” or“premise”) and q is called the “conclusion” or “consequence”.Truth table:p q p → q0 0 10 1 11 0 01 1 111 / 1Introductionto LogicCSE235Implications IIThe implication p → q can be e quivalently read asif p then qp implies qif p, qp only if qq if pq when pq whenever pp 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 p12 / 1Introductionto LogicCSE235ExamplesExampleIf 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 / 1Introductionto LogicCSE235ExerciseWhich of the following implications is true?If −1 is a positive number, then 2 + 2 = 5.true: the hypothesis is obviously false, thus no matterwhat the conclusion, the implication holds.If −1 is a positive number, then 2 + 2 = 4.true: for the same reason as aboveIf 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 “ifsin x = 0 then x = kπ for some integer k” is true.14 / 1Introductionto LogicCSE235ExerciseWhich of the following implications is true?If −1 is a positive number, then 2 + 2 = 5.true: the hypothesis is obviously false, thus no matterwhat the conclusion, the implication holds.If −1 is a positive number, then 2 + 2 = 4.true: for the same reason as aboveIf 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 “ifsin x = 0 then x = kπ for some integer k” is true.15 / 1Introductionto LogicCSE235ExerciseWhich of the following implications is true?If −1 is a positive number, then 2 + 2 = 5.true: the hypothesis is obviously false, thus no matterwhat the conclusion, the implication holds.If −1 is a positive number, then 2 + 2 = 4.true: for the same reason as aboveIf 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 “ifsin x = 0 then x = kπ for some integer k” is true.16 / 1Introductionto LogicCSE235ExerciseWhich of the following implications is true?If −1 is a positive number, then 2 + 2 = 5.true: the hypothesis is obviously false, thus no matterwhat the conclusion, the implication holds.If −1 is a positive number, then 2 + 2 = 4.true: for the same reason as aboveIf 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 “ifsin x = 0 then x = kπ for some integer k” is true.17 / 1Introductionto LogicCSE235BiconditionalDefinitionThe biconditionalp ↔ qis the proposition that is true when p and q have the sametruth values. It is false otherwise.Note that it is equivalent to (p → q) ∧ (q → p)Truth table:p q p → q q → p p ↔ q0 0 1 1 10 1 1 0 01 0 0 1 01 1 1 1 118 / 1Introductionto LogicCSE235Examplesp ↔ q can be e quivalently read asp if and only if qp is necessary and sufficient for qif p then q, and converselyp iff q (Note typo in textbook, page 9, line 3.)Examplex > 0 if and only if x2is positive.The alarm goes off iff a burglar breaks in.You may have pudding if and only
View Full Document
Unlocking...