Introduction Predicate Logic and Quantifiers Predicate Logic and Quantifiers CSE235 Predicate Logic and Quantifiers Consider the following statements x 3 CSE235 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 Fall 2007 z x is greater than 3 z Computer Science Engineering 235 Introduction to Discrete Mathematics subject Sections 1 3 1 4 of Rosen cse235 cse unl edu 2 1 Propositional Functions Predicate Logic and Quantifiers predicate Terminology affirmed holds is true denied does not hold is not true Propositional Functions Predicate Logic and Quantifiers To write in predicate logic CSE235 CSE235 z x is greater than 3 z subject x y z The truth value of these statements has no meaning without specifying the values of x y z Slides by Christopher M Bourke Instructor Berthe Y Choueiry 1 1 x y 3 predicate We introduce a functional symbol for the predicate and put the subject as an argument to the functional symbol P x 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 Examples Takes one or more arguments Father x unary predicate Expresses a predicate involving the argument s Brother x y binary predicate Becomes a proposition when values are assigned to the arguments Sum x y z ternary predicate P x y z t n ary predicate 3 1 Predicate Logic and Quantifiers CSE235 4 1 Propositional Functions Propositional Functions Example Example Example Predicate Logic and Quantifiers CSE235 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 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 5 1 5 1 Universe of Discourse Universe of Discourse Multivariate Functions Predicate Logic and Quantifiers Predicate Logic and Quantifiers CSE235 CSE235 Consider the previous example Does it make sense to assign to x the value blue Moreover each variable in an n tuple may have a different universe of discourse 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 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 would be the universe of discourse for the propositional function P x The test will be on x the 23rd be 6 1 What are the universes of discourse for r g b c 7 1 Quantifiers Universal Quantifier Introduction Definition Predicate Logic and Quantifiers Predicate Logic and Quantifiers CSE235 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 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 Such quantification can be done with two quantifiers the universal quantifier and the existential quantifier 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 9 1 8 1 Predicate Logic and Quantifiers CSE235 Universal Quantifier Universal Quantifier Example I Example I 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 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 10 1 Express the statement Everybody must take a discrete mathematics course or be a computer science student 10 1 Predicate Logic and Quantifiers CSE235 Universal Quantifier Universal Quantifier Example I Example I 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 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 x Q x P x Express the statement Everybody must take a discrete mathematics course or be a computer science student Express the statement Everybody must take a discrete mathematics course or be a computer science student x Q x P x 10 1 Predicate Logic and Quantifiers CSE235 x Q x P x 10 1 Are hetse statements true or false Universal Quantifier Universal Quantifier Example II Example II Express the statement for every x and for every y x y 10 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 11 1 Predicate Logic and Quantifiers CSE235 11 1 Universal Quantifier Universal Quantifier Example II Example II Express the statement for every x and for every y x y 10 Predicate Logic and Quantifiers CSE235 Express the statement …
View Full Document
Unlocking...