IntroductionPropositionsConnectivesTruth TablesUsefulness of LogicBitwise OperationsLogic in TCSLogic in ProgrammingPropositional EquivalencesUsing TTUsing L.E.Introductionto LogicCSE235IntroductionUsefulness ofLogicPropositionalEquivalencesIntroduction to LogicSlides by Christopher M. BourkeInstructor: Berthe Y. ChoueiryFall 2007Computer Science & Engineering 235Introduction to Discrete MathematicsSections 1.1-1.2 of [email protected] / 40Introductionto LogicCSE235IntroductionPropositionsConnectivesTruth TablesUsefulness ofLogicPropositionalEquivalencesIntroduction IPropositional calculus (or logic) is the study of the logicalrelationship between objects called propositions and forms thebasis of all mathematical reasoning and all automatedreasoning.DefinitionA proposition is a statement that is either true or false, but notboth (we usually denote a proposition by letters; p, q, r, s, . . .).2 / 40Introductionto LogicCSE235IntroductionPropositionsConnectivesTruth TablesUsefulness ofLogicPropositionalEquivalencesIntroduction 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 / 40Introductionto LogicCSE235IntroductionPropositionsConnectivesTruth TablesUsefulness ofLogicPropositionalEquivalencesExamples 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 / 40Introductionto LogicCSE235IntroductionPropositionsConnectivesTruth TablesUsefulness ofLogicPropositionalEquivalencesExamples IIExample (Propositions?)2 + 2 = 5Every integer is divisible by 12.Microsoft is an excellent company.5 / 40Introductionto LogicCSE235IntroductionPropositionsConnectivesTruth TablesUsefulness ofLogicPropositionalEquivalencesLogical 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 / 40Introductionto LogicCSE235IntroductionPropositionsConnectivesTruth TablesUsefulness ofLogicPropositionalEquivalencesNegationA 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 / 40Introductionto LogicCSE235IntroductionPropositionsConnectivesTruth TablesUsefulness ofLogicPropositionalEquivalencesLogical 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 / 40Introductionto LogicCSE235IntroductionPropositionsConnectivesTruth TablesUsefulness ofLogicPropositionalEquivalencesLogical 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 111 1 11Can I have both?9 / 40Introductionto LogicCSE235IntroductionPropositionsConnectivesTruth TablesUsefulness ofLogicPropositionalEquivalencesExclusive OrThe exclusive or of two propositions is true when exactly one ofits 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 q p ⊕ q0 0 00 1 11 0 111 010 / 40Introductionto LogicCSE235IntroductionPropositionsConnectivesTruth TablesUsefulness ofLogicPropositionalEquivalencesImplications 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 / 40Introductionto LogicCSE235IntroductionPropositionsConnectivesTruth TablesUsefulness ofLogicPropositionalEquivalencesImplications 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 / 40Introductionto LogicCSE235IntroductionPropositionsConnectivesTruth TablesUsefulness ofLogicPropositionalEquivalencesExamplesExampleIf 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 / 40Introductionto LogicCSE235IntroductionPropositionsConnectivesTruth TablesUsefulness ofLogicPropositionalEquivalencesExerciseWhich 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 / 40Introductionto LogicCSE235IntroductionPropositionsConnectivesTruth TablesUsefulness ofLogicPropositionalEquivalencesExerciseWhich 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 / 40Introductionto LogicCSE235IntroductionPropositionsConnectivesTruth TablesUsefulness
View Full Document
Unlocking...