Notes Predicate Logic and Quantifiers Predicate Logic and Quantifiers CSE235 Slides by Christopher M Bourke Instructor Berthe Y Choueiry Spring 2006 Computer Science Engineering 235 Introduction to Discrete Mathematics Sections 1 3 1 4 of Rosen cse235 cse unl edu 1 1 Notes Introduction Predicate Logic and Quantifiers Consider the following statements x 3 CSE235 x y 3 x y z The truth value of these statements has no meaning without specifying the values of x y z However we can make propositions out of such statements A predicate is a property that is affirmed or denied about the subject in logic we say variable or argument of a statement z x is greater than 3 z subject 2 1 predicate Terminology affirmed holds is true denied does not hold is not true Notes Propositional Functions Predicate Logic and Quantifiers To write in predicate logic CSE235 z x is greater than 3 z subject predicate We introduce a functional symbol for the predicate and put the subject as an argument to the functional symbol P x Examples Father x unary predicate Brother x y binary predicate Sum x y z ternary predicate P x y z t n ary predicate 3 1 Propositional Functions Predicate Logic and Quantifiers CSE235 Notes Definition A statement of the form P x1 x2 xn is the value of the propositional function P Here x1 x2 xn is an n tuple and P is a predicate You can think of a propositional function as a function that Evaluates to true or false Takes one or more arguments Expresses a predicate involving the argument s Becomes a proposition when values are assigned to the arguments 4 1 Propositional Functions Notes Example Predicate Logic and Quantifiers CSE235 Example Let Q x y z denote the statement x2 y 2 z 2 What is the truth value of Q 3 4 5 What is the truth value of Q 2 2 3 How many values of x y z make the predicate true 5 1 Propositional Functions Example Predicate Logic and Quantifiers CSE235 Example Let Q x y z denote the statement x2 y 2 z 2 What is the truth value of Q 3 4 5 What is the truth value of Q 2 2 3 How many values of x y z make the predicate true Since 32 42 25 52 Q 3 4 5 is true Since 22 22 8 6 32 9 Q 2 2 3 is false There are infinitely many values for x y z that make this propositional function true how many right triangles are there 6 1 Notes Universe of Discourse Notes Predicate Logic and Quantifiers CSE235 Consider the previous example Does it make sense to assign to x the value blue Intuitively the universe of discourse is the set of all things we wish to talk about that is the set of all objects that we can sensibly assign to a variable in a propositional function What would be the universe of discourse for the propositional function P x The test will be on x the 23rd be 7 1 Universe of Discourse Notes Multivariate Functions Predicate Logic and Quantifiers CSE235 Moreover each variable in an n tuple may have a different universe of discourse Let P r g b c The rgb value of the color c is r g b For example P 255 0 0 red is true while P 0 0 255 green is false What are the universes of discourse for r g b c 8 1 Quantifiers Introduction Predicate Logic and Quantifiers CSE235 A predicate becomes a proposition when we assign it fixed values However another way to make a predicate into a proposition is to quantify it That is the predicate is true or false for all possible values in the universe of discourse or for some value s in the universe of discourse Such quantification can be done with two quantifiers the universal quantifier and the existential quantifier 9 1 Notes Notes Universal Quantifier Definition Predicate Logic and Quantifiers CSE235 Definition The universal quantification of a predicate P x is the proposition P x is true for all values of x in the universe of discourse We use the notation xP x which can be read for all x If the universe of discourse is finite say n1 n2 nk then the universal quantifier is simply the conjunction of all elements xP x P n1 P n2 P nk 10 1 Notes Universal Quantifier Example I Predicate Logic and Quantifiers CSE235 Let P x be the predicate x must take a discrete mathematics course and let Q x be the predicate x is a computer science student The universe of discourse for both P x and Q x is all UNL students Express the statement Every computer science student must take a discrete mathematics course Express the statement Everybody must take a discrete mathematics course or be a computer science student 11 1 Notes Universal Quantifier Example I Predicate Logic and Quantifiers CSE235 Let P x be the predicate x must take a discrete mathematics course and let Q x be the predicate x is a computer science student The universe of discourse for both P x and Q x is all UNL students Express the statement Every computer science student must take a discrete mathematics course x Q x P x Express the statement Everybody must take a discrete mathematics course or be a computer science student 12 1 Notes Universal Quantifier Example I Predicate Logic and Quantifiers CSE235 Let P x be the predicate x must take a discrete mathematics course and let Q x be the predicate x is a computer science student The universe of discourse for both P x and Q x is all UNL students Express the statement Every computer science student must take a discrete mathematics course x Q x P x Express the statement Everybody must take a discrete mathematics course or be a computer science student x Q x P x 13 1 Notes Universal Quantifier Example I Predicate Logic and Quantifiers CSE235 Let P x be the predicate x must take a discrete mathematics course and let Q x be the predicate x is a computer science student The universe of discourse for both P x and Q x is all UNL students Express the statement Every computer science student must take a discrete mathematics course x Q x P x Express the statement Everybody must take a discrete mathematics course or be a computer science student x Q x P x 14 1 Are these statements true or false Universal Quantifier Example II Predicate Logic and Quantifiers CSE235 15 1 Express the statement for every x and for every y x y 10 Notes Notes Universal Quantifier Example II Predicate Logic and Quantifiers CSE235 Express the statement for every x and for every y x y 10 Let P x y be the statement x y 10 where the universe of discourse for x y is the set of integers 16 1 Notes Universal Quantifier Example II Predicate Logic and Quantifiers CSE235 Express the statement for every x and for …
View Full Document
Unlocking...