Propositional Logic: Equivalence and Simplification Examples
Dive into the world of propositional logic with discussions on logical equivalence, distributive property, De Morgan's Law, and truth table simplification. Explore statements, converse, contrapositive, and inverse forms. Learn to express complex statements using quantifiers and logical connectives.
Uploaded on | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Week 3 CSE 20 Fall 2020 Propositional Logic Logical Operators
Propositional Logic Propositional Logic Question: Are the following propositions equivalent? ? ? (? ?) and ? (? ?) Yes, they are equivalent. ? ? ? ? ? ? ? ? ? ? ? ? (? ?) *this is distributive property
Propositional Propositional Logic Logic Question: Are the following propositions equivalent? ? ? (? ?) and ? ? ? No, they are not equivalent. Too see this, consider the assignment ? = ?,? = ?,? = ? then ? ? ? ? = ? ? ? ? = ? ? = ? ? ? ? = ? ? ? = ? ? = ? However, ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? *distributive property *de Morgan s Law
Propositional Logic Propositional Logic Question: Are the following propositions equivalent? ? (? ?) and ? (? ?) Yes, they are equivalent. ? ? ? ? ? ? ? ? ? ? ( ? ?) ? ? ? ? ? ? ? ? ? ? (? ?) *associative property *commutative
Propositional Logic Propositional Logic Simplify the following truth table: ? ? ? ? ? ? ? ? ? ( ? ? ?) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (? ?)
Propositional Logic Propositional Logic Converse of ? ?: Contrapositive of ? ?: Inverse of ? ?: p: Maria learns discrete mathematics q: Maria will find a good job. Express the statement p q as a statement in English. If Maria learns discrete mathematics, she will find a good job
Propositional Logic Propositional Logic Write the following statement as a proposition: The home team wins whenever it is raining. p: It is raining. q: The home team wins. ? ?: If it is raining, the home team wins. ? ?: If the home team wins, then it is raining. Converse: Contrapositive: ? ?: If the home team does not win, then it is not raining. ? ?: If it is not raining, then the home team does not win. Inverse: Observe: The contrapositive is the same as the original
Quantifiers Quantifiers Let ?(?)be the statement ?can speak Klingon and let ?(?)be the statement ?knows C++. Express each of these sentences in terms of ?(?),?(?), quantifiers, and logical connectives. The domain for quantifiers consists of all students in our class. ?(? ? ?(?)) a) There is a student in our class who can speak Klingon and knows C++. ?(? ? ?(?)) b) There is a student in our class who can speak Klingon but doesn t know C++. ? ? ? ? ? ?( ? ? ?(?)) c) No student in our class can speak Klingon or knows C++.
Quantifiers Quantifiers What is the truth value of ? ?(?2< ?) ? m ? < ?2 The domain is the set of integers. ? ?(?2< ?) is true. To see this, pick an arbitrary integer ?. We need to show that there exists an integer ? such that ?2< ?. Indeed, when ? = ?2+ 1, we have ?2< ?2+ 1 = ?. Hence, for each integer n, there exists an integer m such that ?2< ?. ? m ? < ?2 is true. Let ? = 1 then for all integer ?, we have ? = 1 < 0 ?2. Thus, there exists an integer ? such that for all integers ?,? < ?2.
