Introduction to LogicSlides by Christopher M. BourkeInstructor: Berthe Y. ChoueiryFall 2007Computer Science & Engineering 235Introduction to Discrete MathematicsSections 1.1-1.2 of [email protected] IPropositional calculus (or logic) is the study of the logicalrelationship between objects called propositions and forms thebasis of all mathematical reasoning and all automated reasoning.DefinitionA proposition is a statement that is either true or false, but notboth (we usually denote a proposition by letters; p, q, r, s, . . .).Introduction IIDefinitionThe value of a proposition is called its truth value; denoted by T or1 if it is true and F or 0 if it is false.Opinions, interrogative and imperative sentences are notpropositions.Truth table:p01Examples IExample (Propositions)IToday is Monday.IThe derivative of sin x is cos x.IEvery even number has at least two factors.Example (Not Propositions)IC++ is the best language.IWhen is the pretest?IDo your homework.Examples IIExample (Propositions?)I2 + 2 = 5IEvery integer is divisible by 12.IMicrosoft is an excellent company.Logical ConnectivesConnectives are use d to c reate a com pound proposition from twoor more other propositions.INegation (denoted ¬ or !)IAnd (denoted ∧) or Logical ConjunctionIOr (denoted ∨) or Logical DisjunctionIExclusive Or (XOR, denoted ⊕)IImplication (denoted →)IBiconditional; “if and only if” (denoted ↔)NegationA proposition can be negated. This is also a proposition. Weusually denote the negation of a proposition p by ¬p.Example (Negated Propositions)IToday is not Monday.IIt is not the case that today is Monday.IIt is not the case that the derivative of sin x is cos x.Truth table:p ¬p0 11 0Logical AndThe logical connective And is true only if bot h of the propositionsare true. It is also referred to as a conjunction.Example (Logical Connective: And)IIt is raining and it is warm.I(2 + 3 = 5) ∧ (√2 < 2)ISchr¨odinger’s cat is dead and Schr¨odinger’s cat is not dead.Truth table:p q p ∧ q0 0 00 1 01 0 01 1 1Logical OrThe logical disjunction (or logical or) is true if one or both of thepropositions are true.Example (Logical Connective: Or)IIt is raining or it is the second day of lecture.I(2 + 2 = 5) ∨ (√2 < 2)IYou 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?Exclusive OrThe exclusive or of two prop ositions is true when exactly one of itspropositions is true and the other one is false.Example (Logical Connective: Exclusive Or)IThe circuit is either is on or off .ILet ab < 0, then either a < 0 or b < 0 but not both.IYou may have cake or ice cream, but not both.Truth table:p q p ⊕ q0 0 00 1 11 0 11 1 0Implications IDefinitionLet p and q be propositions. 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 1Implications IIThe implication p → q can be equivalently read asIif p then qIp implies qIif p, qIp only if qIq if pIq when pIq whenever pIp is a sufficient condition for q (p is sufficient for q)Iq is a necessary condition for p (q is necessary for p)Iq follows from pExamplesExampleIIf you buy your air ticket in advance, it is che aper.IIf x is a real number, then x2≥ 0.IIf it rains, the grass gets wet.IIf the sprinklers operate, the grass gets wet.IIf 2 + 2 = 5 then all unicorns are pink.ExerciseWhich of the following implications is true?IIf −1 is a positive number, then 2 + 2 = 5.true: the hypothesis is obviously false, thus no matter whatthe conclusion, the implication holds.IIf −1 is a positive number, then 2 + 2 = 4.true: for the same reason as aboveIIf sin x = 0 then x = 0.false: x can be any multiple of π; i.e. if we let x = 2π thenclearly sin x = 0, but x 6= 0. The implication “if sin x = 0then x = kπ for some intege r k” is true.BiconditionalDefinitionThe biconditionalp ↔ qis the proposition that is true when p and q have the same truthvalues. 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 010 0 1 01 1 1 1 1Examplesp ↔ q can be equivalently read asIp if and only if qIp is necessary and s ufficient for qIif p then q, and converselyIp iff q (Note typo in textbook, page 9, line 3.)ExampleIx > 0 if and only if x2is positive.IThe alarm goes off iff a burglar breaks in.IYou may have pudding if and only if you eat your meat.ExerciseWhich of the following biconditionals is true?Ix2+ y2= 0 if and only if x = 0 and y = 0true: both implications hold.I2 + 2 = 4 if and only if√2 < 2true: for the same reason above.Ix2≥ 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 thehypothesis is true, (−1)2= 12≥ 0 but the conclusion fails.Converse, Contrapositive, InverseConsider the proposition p → q:IIts converse is the proposistion q → p.IIts inverse is the proposistion ¬p → ¬q.IIts contrapositive is the proposistion ¬q → ¬p.Truth Tables ITruth Tables are used to show the relationship between the truthvalues of individual propositions and the compound propositionsbased on them.p q p ∧ q p ∨ q p ⊕ q p → q p ↔ q0 0 0 0 0 1 10 1 0 1 1 1 01 0 0 1 1 0 01 1 1 1 0 1 1Table: Truth Table for Logical Conjunction, Disjunction, Exclusive Or,and ImplicationConstructing Truth TablesConstruct the Truth Table for the following compound proposition.((p ∧ q) ∨ ¬q)p q p ∧ q ¬q ((p ∧ q) ∨ ¬q)0 0 0 1 10 1 0 0 01 0 0 1 11 1 1 0 1Precedence of Logical OperatorsJust as in arithmetic, an ordering must be imposed on the use oflogical operators in compound propositions.Of course, parentheses can be used to make operatorsdisambiguous:¬p ∨ q ∧ ¬r ≡ (¬p) ∨q ∧ (¬r)But to avoid using unnecessary parentheses, we define thefollowing precedences:1. (¬) Negation2. (∧) Conjunction3. (∨) Disjunction4. (→) Implication5. (↔) BiconditionalUsefulness of LogicLogic is more precise than natural language:IYou may have cake or ice cream.Can I have both?IIf you buy your air ticket in advance, it is che aper.Are there or not cheap last-minute tickets?For this reason, logic is used for hardware and softwarespecification.Given a set of logic statements, one can decide
View Full Document
Unlocking...