Introduction to LogicIntroduction: Logic?Introduction: PL?OutlineIntroduction: PropositionPropositions: ExamplesAre these propositions?Logical connectivesLogical Connective: NegationLogical Connective: Logical AndLogical Connective: Logical OrLogical Connective: Exclusive OrLogical Connective: Implication (1)Logical Connective: Implication (2)Logical Connective: Implication (3)Exercise: Which of the following implications is true?Logical Connective: Biconditional (1)Logical Connective: Biconditional (2)Exercise: Which of the following biconditionals is true?Converse, Inverse, ContrapositiveTruth TablesConstructing Truth TablesSlide 23Precedence of Logical OperatorsUsefulness of LogicBitwise OperationsLogic in TCSLogic in TCS: A Sentence in PLLogic in Programming: Example 1Logic in Programming: Example 2Propositional Equivalences: IntroductionTerminology: Tautology, Contradictions, ContingenciesLogical Equivalences: DefinitionLogical Equivalences: Example 1Slide 35Logical Equivalences: Cheat SheetUsing Logical Equivalences: Example 1Using Logical Equivalences: Example 2Using Logical Equivalences: Example 3Logic in Programming: Example 2 (revisited)Programming Pitfall NoteIntroduction to LogicSections 1.1 and 1.2 of RosenSpring 2010CSCE 235 Introduction to Discrete StructuresURL: cse.unl.edu/~cse235Questions: [email protected] 235, Spring 20102Introduction: 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 reasoningLogicCSCE 235, Spring 20103Introduction: 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, …LogicCSCE 235, Spring 20104Outline•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 rulesLogicCSCE 235, Spring 20105Introduction: 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 tablep01LogicCSCE 235, Spring 20106Propositions: Examples•The following are propositions–Today is Monday M–The grass is wet W–It is raining R•The following are not propositions–C++ is the best language Opinion–When is the pretest? Interrogative–Do your homework ImperativeLogicCSCE 235, Spring 20107Are these propositions?•2+2=5•Every integer is divisible by 12•Microsoft is an excellent companyLogicCSCE 235, Spring 20108Logical 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 tablesLogicCSCE 235, Spring 20109Logical 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 tablepp0 11 0LogicCSCE 235, Spring 201010Logical 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 tablep qpq 0 00 11 01 1LogicCSCE 235, Spring 201011Logical 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 tablep qpq pq0 0 00 1 01 0 01 1 1LogicCSCE 235, Spring 201012Logical 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 tablep qpq pq pq0 0 0 00 1 0 11 0 0 11 1 1 1LogicCSCE 235, Spring 201013Logical Connective: Implication (1)•Definition: Let p and q be two propositions. The implication pq 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 tablep qpq pq pq pq0 0 0 0 00 1 0 1 11 0 0 1 11 1 1 1 0LogicCSCE 235, Spring 201014Logical Connective: Implication (2)•The implication of pq 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)LogicCSCE 235, Spring 201015Logical 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.LogicCSCE 235, Spring 201016Exercise: Which of the following implications is true?•If -1 is a positive number, then 2+2=5•If -1 is a positive number, then 2+2=4•If sin x = 0, then x = 0True. The premise is obviously false, thus no matter what the conclusion is, the implication holds.True. Same as above.False. x can be a multiple of . If we let x=2, then sin x=0 but x0.The implication “if sin x = 0, then x = k, for some k” is true.LogicCSCE 235, Spring 201017Logical Connective: Biconditional (1)•Definition: The biconditional pq 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 (pq)(q p)•Truth tablep qpq pq pq
View Full Document
Unlocking...