Handout Week 01 - Propositional Logic PDF

Week 1 Introduction to Propositional Logic Shirley Chu De La Salle University update January 20, 2020 Introduction to Logic Rules of logic gives precise meaning to statements. These rules are used to determine val...

Week 1 Introduction to Propositional Logic Shirley Chu De La Salle University update January 20, 2020 Introduction to Logic Rules of logic gives precise meaning to statements. These rules are used to determine validity of mathematical arguments. Definition The area of logic that deals with propositions is called propositional logic or propositional calculus, developed by the Greek philosopher Aristotle. Propositions Definition A proposition is a declarative sentence that is either true or false, but not both. Which of the following are propositions? 1 De La Salle University is located in Manila. 2 Who are you? 3 Cebu City is the capital of the Philippines. 4 Be careful. 5 x + y = 25 Compound Propositions Definition Compound propositions are formed by combining one or more existing propositions using logical operators. Representations Propositional variables or statement variables are letters used to represent propositions. Convention: Lowercase letters are used as propositional variables. Example: Let m denote the statement “Manila is the capital of the Philippines.”. Let p denote the statement “I will pass CCDSTRU.”. Truth values are denoted by T for true and F for false. Truth table displays the relationships between the truth values of propositions. Logical Connectives Definition Logical connectives or logical operators or boolean operators are used to form compound propositions. Negation Definition The negation of the proposition p, denoted by ¬p and read as not p, is the statement: It is not the case of p. The truth value of ¬p is the opposite of the truth value of p. Example: The negation of I will sleep early tonight. In English: I will not sleep early tonight. Using Expressions: Let s be I will sleep early tonight. Translation: ¬s The negation of It is raining. In English: It is not raining. Using Expressions: Let r be It is raining. Translation: ¬r Truth Table for ¬p Table: Truth Table for ¬p p ¬p T F F T Conjunction Definition The conjunction of the propositions p and q is denoted by p ∧ q. The truth value of p ∧ q is true iff both p and q are true. Example: I will sleep early tonight and I will eat breakfast tomorrow morning. Let s be I will sleep early tonight. Let b be I will eat breakfast tomorrow morning. Translation: s ∧ b I woke up early, but I am late for class. Let w be I woke up early. Let c be I am late for class. Translation: w ∧ c Truth Table for p ∧ q Table: Truth Table for p ∧ q p q p∧q T T T T F F F T F F F F Disjunction a.k.a. Inclusive-Or Definition The disjunction of the propositions p and q is denoted by p ∨ q. The truth value of p ∨ q is true when either p or q is true. Example: Either I wake up early, or I am late for class. Let w be I wake up early. Let c be I am late for class. Translation: w ∨ c I will sleep early tonight or I will not eat breakfast tomorrow morning. Let s be I will sleep early tonight. Let b be I will eat breakfast tomorrow morning. Translation: s ∨ ¬b Truth Table for p ∨ q Table: Truth Table for p ∨ q p q p∨q T T T T F T F T T F F F Exclusive-Or Definition The exclusive-or of the propositions p and q is denoted by p ⊕ q. The truth value of p ⊕ q is true when either p or q is true, but not both. Example: The steak comes with soup or dessert. Let s be The steak comes with soup. Let d be The steak comes with dessert. Translation: s ⊕ d I will sleep early tonight or I will not eat breakfast tomorrow morning, but not both. Let s be I will sleep early tonight. Let b be I will eat breakfast tomorrow morning. Translation: s ⊕ ¬b Truth Table for p ⊕ q Table: Truth Table for p ⊕ q p q p⊕q T T F T F T F T T F F F Implication Definition The conditional statement p → q is read as if p then q. The truth value of p → q is false when p is true and q is false. p is the hypothesis, antecedent or premise. q is the conclusion or consequence. Example: If I wake up early, I will eat breakfast. Let w be I wake up early. Let b be I will eat breakfast. Translation: w → b I pass the exam whenever I study. Let p be I pass the exam. Let s be I study. Translation: s → p Truth Table for p → q p → q may be translated as: p is sufficient for q Table: Truth Table for p → q q is necessary for p p q p→q q when p T T T q whenever p T F F F T T p only if q F F T q unless ¬p q follows from p Converse, Contrapositive and Inverse Given a implication statement p → q: Converse Inverse Contrapositive q→p ¬p → ¬q ¬q → ¬p Biconditional Definition The biconditional statement p ↔ q is read as p if and only if q. The truth value of p ↔ q is true when both p and q have the same truth value, false otherwise. Example: I pass the exam if and only if I study. Let p be I pass the exam. Let s be I study. Translation: p ↔ s Truth Table for p ↔ q Table: Truth Table for p ↔ q p ↔ q may be translated as: p q p↔q p is necessary and sufficient for q T T T p if and only if q T F F If p then q and conversely. F T F F F T Summary Summary Not And Or Xor Implies Iff p q ¬p p∧q p∨q p⊕q p→q p↔q T T T T F T T F T F F T T F F F T F T T T F T F F F F F T T Exercise 1 Translate the following English statements to propositions. 1 It is sunny. 2 I answered the assignment, but I did not submit it. 3 I will remember to send you my address only if you send me an email message. 4 Either I go to school or I go to the mall. 5 I will eat breakfast or I will walk to school, or both. Exercise 2 Answer the following. 1 Determine how many rows will appear in the truth tables of these propositions? 1 p ∧ ¬q 2 p ∨ ¬p 3 p ∧ q ∨ (r ∧ p) 2 Construct the truth tables for the following propositions. 1 p ∧ ¬p 2 p ⊕ (p ∨ q) 3 (p ∨ ¬q) → q 4 (q → ¬p) ↔ (¬q → ¬p) Reference Discrete Mathematics and Its Applications, 7th edition by Kenneth Rosen