Discrete Mathematics, Chapter 1.4-1.5: Predicate Logic

1 Discrete Mathematics, Chapter : Predicate LogicRichard MayrUniversity of Edinburgh, UKRichard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapter / 23 Outline1 Predicates2 Quantifiers3 Equivalences4 Nested QuantifiersRichard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapter / 23 Propositional Logic is not enoughSuppose we have: All men are mortal. Socrates is a man .Does it follow that Socrates is mortal ?This cannot be expressed in propositional need a language to talk about objects, their properties and Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapter / 23 Predicate LogicExtend propositional Logic by the following new :x,y,z,.. predicates ( , propositional functions):P(x),Q(x),R(y),M(x,y),..Quant ifiers: , .Propositional functions are a generalization of contain variables and predicates , ,P(x).Variables stand for (and can be replaced by) elements from Mayr (University of Edinburgh, UK) Discrete Mathematics.

2 Chapter / 23 Propositional FunctionsPropositional functions become propositions (and thus have truthvalues) when all their variables are eitherIreplaced by a value from their domain, orIbound by a quantifierP(x)denotes the value of propositional domain is often denoted byU(the universe).Example:LetP(x)denote x>5 andUbe the integers. ThenIP(8)is (5)is Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapter / 23 Examples of Propositional FunctionsLetP(x,y,z)denote thatx+y=zandUbe the integers for allthree ( 4,6,2)is (5,2,10)is (5,x,7)is not a (x,y,z)denote thatx y=zandUbe the (1,2,3) Q(5,4,1)is (1,2,4) Q(5,4,0)is (1,2,3) Q(5,4,0)is (1,2,4) Q(x,4,0)is not a Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapter / 23 QuantifiersWe need quantifiers to formally express the meaning of the words all and some .The two most important quantifiers are:IUniversal quantifier, For all . Symbol: IExistential quantifier, There exists.

3 Symbol: x P(x)asserts thatP(x)is true foreveryxin the domain. x P(x)asserts thatP(x)is true forsomexin the quantifiers are said to bind the variablexin in the scope of some quantifier are called boundvariables. All other variables in the expression are called propositional function that does not contain any free variables isa proposition and has a truth Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapter / 23 Quantifiers: ExampleConsider this formula = y.((P(y) Q(x)) x.(P(x) Q(y) P(z)))How many free variables does this formula contain? Clicker1 One2 Two3 Three4 Four5 NoneRichard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapter / 23 Universal Quantifier x P(x)is read as For allx,P(x) or For everyx,P(x) .The truth value depends not only onP, but also on the :LetP(x)denotex> the integers then x P(x)is the positive integers then x P(x)is Mayr (University of Edinburgh, UK) Discrete Mathematics.

4 Chapter / 23 Existential Quantifier x P(x)is read as For somex,P(x) or There is anxsuch that,P(x) , or For at least onex,P(x) .The truth value depends not only onP, but also on the :LetP(x)denotex< the integers then x P(x)is the positive integers then x P(x)is Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapter / 23 Uniqueness Quantifier !x P(x)means that there exists one and only onexin thedomain such thatP(x)is true. 1x P(x)is an alternative notation for !x P(x).This is read asIThere is one and only onexsuch thatP(x).IThere exists a uniquexsuch thatP(x).Example:LetP(x)denotex+1=0 andUare the !x P(x)is :LetP(x)denotex>0 andUare the integers. Then !x P(x)is uniqueness quantifier can be expressed by standardoperations. !x P(x)is equivalent to x(P(x) y(P(y) y=x)).Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapter / 23 Precedence of QuantifiersQuantifiers and have higher precedence then all logicaloperators.

5 X P(x) Q(x)means( x P(x)) Q(x). In particular, thisexpression contains a free variable. x(P(x) Q(x))means something Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapter / 23 Translating English to LogicTranslate the following sentence into Predicate Logic : Every student inthis class has taken a course in Java. Solution: first decide on the domain 1: IfUis all students in this class, define a propositionalfunctionJ(x)denoting xhas taken a course in Java andtranslate as x J(x).Solution 2: But ifUis all people, also define a propositional functionS(x)denoting xis a student in this class and translateas x(S(x) J(x)).Note: x(S(x) J(x))is not correct. What does it mean?Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapter / 23 Equivalences in Predicate LogicStatements involving predicates and quantifiers are logicallyequivalent if and only if they have the same truth value for everypredicate substituted into these statements and for every domainof discourse used for the variables in the notationS Tindicates thatSandTare logically : x S(x) x S(x).

6 Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapter / 23 Quantifiers as Conjunctions/DisjunctionsIf the domain is finite then universal/existential quantifiers can beexpressed by of the integers 1,2, and 3, thenI x P(x) P(1) P(2) P(3)I x P(x) P(1) P(2) P(3)Even if the domains are infinite, you can still think of thequantifiers in this fashion, but the equivalent expressions withoutquantifiers will be infinitely Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapter / 23De Morgan s Law for QuantifiersThe rules for negating quantifiers are: x P(x) x P(x) x P(x) x P(x)Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapter / 23 Predicate CalculusAn assertion in Predicate calculus is valid iff it is trueIfor all domainsIfor every propositional functions substituted for the predicates in assertion in Predicate calculus is satisfiable iff it is trueIfor some domainIfor some propositional functions that can be substituted for thepredicates in the : x(F(x) G(x))is not valid, but : x(F(x) F(x))is Mayr (University of Edinburgh, UK) Discrete Mathematics.

7 Chapter / 23 Nested QuantifiersComplex meanings require nested quantifiers. Every real number has an inverse addition. Let the domainUbe the real numbers. Then the property isexpressed by x y(x+y=0) Every real number except zero has a multiplicative inverse. Let the domainUbe the real numbers. Then the property isexpressed by x(x6=0 y(x y=1))Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapter / 23 Thinking of Nested QuantificationNested LoopsITo see if x y P(x,y)is true, loop through the values ofx:IAt each step, loop through the values for some pair ofxandy,P(x,y)is false, then x y P(x,y)isfalse and both the outer and inner loop terminate. x y P(x,y)is true if the outer loop ends after stepping see if x y P(x,y)is true, loop through the values ofx:IAt each step, loop through the values inner loop ends when a pairxandyis found such thatP(x,y)is noyis found such thatP(x,y)is true the outer loop terminatesas x y P(x,y)has been shown to be false.

8 X y P(x,y)is true if the outer loop ends after stepping the domains of the variables are infinite, then this process cannot actually be carried Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapter / 23 Order of QuantifiersQuantifiers can be grouped into blocks x z a c u can be swapped inside a block, but not between (x,y)denotex+y=y+xandUbe the real x y P(x,y)is equivalent to y x P(x,y).LetQ(x,y)denotex+y=0 andUbe the real numbers. Then x y P(x,y)is true, but y x P(x,y)is Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapter / 23 Quantifications of Two VariablesStatementWhen True?When FalseP(x,y) is true for every pair x, is a pair x, y for which P(x,y) is every x there is a y for which P(x,y) is is an x such that P(x,y) is false for every is an x for which P(x,y) is true for every every x there is a y for which P(x,y) is is a pair x, y for which P(x,y) is (x,y) is false for every pair x,yRichard Mayr (University of Edinburgh, UK) Discrete Mathematics.

9 Chapter / 23 Negating Nested QuantifiersLetP(x,f)denote that personxhas taken (f,a)denote that flightfis operated by : There is no person who has taken a flight on every airlinein the world. x a f(P(x,f) Q(f,a))Now use De Morgan s Laws to move the negation as far inwards aspossible. x a f(P(x,f) Q(f,a)) x a f(P(x,f) Q(f,a))by De Morgan s for x a f(P(x,f) Q(f,a))by De Morgan s for x a f (P(x,f) Q(f,a))by De Morgan s for x a f( P(x,f) Q(f,a))by De Morgan s for Can you translate the result back into English? For every person there is an airline such that for all flights, this personhas not taken that flight or that flight is not operated by this airline. Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapter / 23An Example from CalculusExpress that the limit of a real-valued functionfat af(x) =LIn Predicate Logic x(|x a|< |f(x) L|< )where the domain of and are the positive real numbers and thedomain ofxare all real express its negation, , that limx af(x)6=L.

10 X(|x a|< |f(x) L| )Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapter / 23