CSE115/ENGR160 Discrete Mathematics 01/19/121.3 Propositional equivalencesTautology and contradictionLogical equivalenceExamplePowerPoint PresentationSlide 7Slide 8De Morgan’s lawsSlide 10De Morgan’s law: general formLogical equivalencesSlide 13Slide 14Constructing new logical equivalencesSlide 16Limitations of proposition logicSlide 181.4 Predicate and quantifiersExample: x > 3Slide 21N-ary PredicateQuantifiersUniversal quantifierSlide 25Slide 26Slide 27Existential quantificationSlide 29Slide 30Uniqueness quantifierQuantifiers with restricted domainsPrecedence of quantifiersBinding variablesSlide 35CSE115/ENGR160 Discrete Mathematics01/19/12Ming-Hsuan YangUC Merced11.3 Propositional equivalences•Replace a statement with another statement with the same truth value•For efficiency (speed-up) or implementation purpose (e.g., circuit design)2Tautology and contradiction3• A compound proposition:• Tautology: always true• Contradiction: always false• Contingency: neither a tautology nor a contradictionLogical equivalence•p ≡ q (p q): the compound propositions p and q are logically equivalent if p ↔ q is a tautology •Can use truth table to determine whether two propositions are equivalent or not4Example5•Show that ┐(p v q) and ┐p ˄ ┐ q are equivalent6qpqp p q p→q ┐p˅qT T T TT F F FF T T TF F T TExample7Example8De Morgan’s laws9Example•Express the negation of “Heather will go to the concert or Steve will go to the concert”•Negation: Heather will not go to the concert AND Steve will not go to the concert.10De Morgan’s law: general form•The first example above is known as the De Morgan’s law11Logical equivalences121314Constructing new logical equivalences•Show ┐ (p → q) ≡ p ˄ ┐ q┐ (p → q) ≡ ┐(┐p ˅ q) ≡ ┐(┐p) ˄ ┐q ≡ p ˄ ┐q 15Constructing new logical equivalences•Show ┐ (p ˅ (┐ p ˄ q) ) ≡ ┐ p ˄ ┐ q┐ (p ˅ (┐ p ˄ q) ) ≡ ┐ p ˄ (┐(┐ p ˄ q)) ≡ ┐ p ˄ (┐(┐ p) ˅ ┐q) ≡ ┐ p ˄ (p ˅ ┐q) ≡ (┐ p ˄ p ) ˅ (┐ p ˄ ┐q) ≡ F ˅ (┐ p ˄ ┐q) ≡ ┐ p ˄ ┐q16Limitations of proposition logic•Proposition logic cannot adequately express the meaning of statements•Suppose we know “Every computer connected to the university network is functioning property”•No rules of propositional logic allow us to conclude“MATH3 is functioning property”where MATH3 is one of the computers connected to the university network17Example•Cannot use the rules of propositional logic to conclude from“CS2 is under attack by an intruder”where CS2 is a computer on the university network to conclude the truth“There is a computer on the university network that is under attack by an intruder”181.4 Predicate and quantifiers•Can be used to express the meaning of a wide range of statements•Allow us to reason and explore relationship between objects•Predicates: statements involving variables, e.g., “x > 3”, “x=y+3”, “x+y=z”, “computer x is under attack by an intruder”, “computer x is functioning property”19Example: x > 3•The variable x is the subject of the statement•Predicate “is greater than 3” refers to a property that the subject of the statement can have•Can denote the statement by p(x) where p denotes the predicate “is greater than 3” and x is the variable•p(x): also called the value of the propositional function p at x•Once a value is assigned to the variable x, p(x) becomes a proposition and has a truth value 20Example•Let p(x) denote the statement “x > 3”–p(4): setting x=4, thus p(4) is true–p(2): setting x=2, thus p(2) is false•Let a(x) denote the statement “computer x is under attack by an intruder”. Suppose that only CS2 and MATH1 are currently under attack–a(CS1)? : false–a(CS2)? : true–a(MATH1)?: true21N-ary Predicate •A statement involving n variables, x1, x2, …, xn, can be denoted by p(x1, x2, …, xn)•p(x1, x2, …, xn) is the value of the propositional function p at the n-tuple (x1, x2, …, xn)•p is also called n-ary predicate22Quantifiers•Express the extent to which a predicate is true•In English, all, some, many, none, few•Focus on two types: –Universal: a predicate is true for every element under consideration–Existential: a predicate is true for there is one or more elements under consideration •Predicate calculus: the area of logic that deals with predicates and quantifiers23Universal quantifier •“p(x) for all values of x in the domain”•Read it as “for all x p(x)” or “for every x p(x)”•A statement is false if and only if p(x) is not always true•An element for which p(x) is false is called a counterexample of •A single counterexample is all we need to establish that is not true 24)(xpx)(xpx)(xpx)(xpxExample•Let p(x) be the statement “x+1>x”. What is the truth value of ?–Implicitly assume the domain of a predicate is not empty–Best to avoid “for any x” as it is ambiguous to whether it means “every” or “some”•Let q(x) be the statement “x<2”. What is the truth value of where the domain consists of all real numbers? 25)(xpx)(xqxExample•Let p(x) be “x2>0”. To show that the statement is false where the domain consists of all integers–Show a counterexample with x=0•When all the elements can be listed, e.g., x1, x2, …, xn, it follows that the universal quantification is the same as the conjunction p(x1) ˄p(x2) ˄…˄ p(xn) 26)(xpx)(xpxExample•What is the truth value of where p(x) is the statement “x2 < 10” and the domain consists of positive integers not exceeding 4? is the same as p(1)˄p(2)˄p(3)˄p(4)27)(xpx)(xpxExistential quantification •“There exists an element x in the domain such that p(x) (is true)”•Denote that as where is the existential quantifier•In English, “for some”, “for at least one”, or “there is”•Read as “There is an x such that p(x)”, “There is at least one x such that p(x)”, or “For some x, p(x)”28)(xpxExample•Let p(x) be the statement “x>3”. Is true for the domain of all real numbers?•Let q(x) be the statement “x=x+1”. Is true for the domain of all real numbers?• When all elements of the domain can be listed, , e.g., x1, x2, …, xn, it follows that the