Propositional Logic PDF

Logic: Propositional Logic Computer Science Department, Umm Al-Qura University Acknowledgment: All course slides are either referenced to Rosen Book online presentations (with certain amendments) or are personall...

Logic: Propositional Logic Computer Science Department, Umm Al-Qura University Acknowledgment: All course slides are either referenced to Rosen Book online presentations (with certain amendments) or are personally developed by the instructor.  Agenda Propositions Connectives – Negation – Conjunction – Disjunction Truth Tables 2 2 Discrete Structures (1) First Semester - 1444  Propositions A proposition is a statement that is either true or false. Examples of propositions: a) The Moon is made of green cheese. [ TRUE ] b) Makkah is the Holy City of Islam. [ TRUE ] c) Madina is the capital of Saudi Arabia. [ FALSE ] d) 1+0=1 [ TRUE ] e) 0+0=2 [ FALSE ] Examples that are not propositions. a) Sit down! b) What time is it? c) x+1=2 d) x+y=z 3 3 Discrete Structures (1) First Semester - 1438/1439  Compound Propositions A compound proposition is constructed from other propositions using logical connectives. Example: o Proposition p : it is raining outside o Proposition q : we are having dinner at home o A new proposition: If it is raining outside, then we are having dinner at home We call p and q propositional variables 4 4 Discrete Structures (1) First Semester - 1438/1439  Propositional Logic Logical connectives: – Negation ¬ NOT – Conjunction ∧ AND – Disjunction ∨ OR – Implication → IMPLIES – Biconditional ↔ IFF 5 5 Discrete Structures (1) First Semester - 1438/1439  Truth Tables 6 6 Discrete Structures (1) First Semester - 1438/1439  Compound Propositions: Negation The negation of a proposition p is denoted by ¬p and it is read as “not p” p p¬ It has the following truth table: T F F T Example: p : The earth is round. ¬p : It is not the case that the earth is round or The earth is not round.” 7 7 Discrete Structures (1) First Semester - 1438/1439  Compound Propositions: Negation Negate the following propositions: – It is raining today. o It is not raining today. – 2 is a prime number. o 2 is not a prime number – There are other life forms on other planets in the universe. o It is not the case that there are other life forms on other planets in the universe. 8 8 Discrete Structures (1) First Semester - 1438/1439  Conjunction The conjunction of propositions p and q is denoted by p ∧ q and it is read as p and q. p q p∧q T T T It has this truth table: T F F F T F F F F Example: If p denotes “I am at home.” and q denotes “It is raining.” then p ∧q denotes “I am at home and it is raining.” 9 9 Discrete Structures (1) First Semester - 1438/1439  Disjunction The disjunction of propositions p and q is denoted by p ∨q and it is read as p or q. p q p ∨q T T T It has this truth table: T F T F T T F F F Example: If p denotes “I am at home.” and q denotes “It is raining.” then p ∨q denotes “I am at home or it is raining.” 10 10 Discrete Structures (1) First Semester - 1438/1439  The Connective Or in English In English “or” has two distinct meanings. – “Inclusive Or”: o Example: “Students who have taken CS202 or Math120 may take this class,” o We assume that students need to have taken one of the prerequisites, but may have taken both. This is the meaning of disjunction. For p ∨q to be true, either one or both of p and q must be true. – “Exclusive Or” o Example: “Soup or salad comes with this meal” o We do not expect to be able to get both soup and salad. 11 11 Discrete Structures (1) First Semester - 1438/1439  Exclusive OR (XOR) The exclusive OR of propositions p and q is denoted by p ⊕q and it is read as p xor q. p q p⊕q It has this truth table: T T F T F T F T T F F F One of p and q must be true, but not both. 12 12 Discrete Structures (1) First Semester - 1438/1439  Implication If p and q are propositions, then p →q is a conditional statement or implication which is read as “if p, then q ”. p q p→q T T T It has this truth table: T F F F T T F F T Example: If p denotes “I am at home.” and q denotes “It is raining.” then p →q denotes “If I am at home then it is raining.” In p →q , p is the hypothesis and q is the conclusion. 13 13 Discrete Structures (1) First Semester - 1438/1439  Understanding Implication In p →q there does not need to be any connection between the hypothesis or the conclusion. The “meaning” of p →q depends only on the truth values of p and q. These implications are perfectly fine, but would not be used in ordinary English. – If the clouds are made of cotton candy, then I have more money than Bill Gates. – if UQU is opened every Friday then 2 is a prime. 14 14 Discrete Structures (1) First Semester - 1438/1439  Understanding Implication (cont) One way to view the logical conditional is to think of an obligation or contract. – “If I am elected, then I will lower taxes.” – “If you get 100% on the final, then you will get an A.” If the politician is elected and does not lower taxes, then the voters can say that he or she has broken the campaign pledge. Something similar holds for the professor. This corresponds to the case where p is true and q is false. 15 15 Discrete Structures (1) First Semester - 1438/1439  Different Ways of Expressing p →q if p, then q p implies q if p, q p only if q q unless ¬p q when p q if p q whenever p p is sufficient for q q follows from p q is necessary for p a necessary condition for p is q a sufficient condition for q is p 16 16 Discrete Structures (1) First Semester - 1438/1439