Predicate Logic and Quantifies Sections 1 3 and 1 4 of Rosen Fall 2008 CSCE 235 Introduction to Discrete Structures Course web page cse unl edu cse235 Questions cse235 cse unl edu LaTex Using the package usepackage amssymb Set of natural numbers mathbb N Set of integer numbers mathbb Z Set of rational numbers mathbb Q Set of real numbers mathbb R Set of complex numbers mathbb C CSCE 235 Fall 2008 Predicate Logic and Quantifiers 2 Outline Introduction Terminology Propositional functions arguments arity universe of discourse Quantifiers Definition using mixing negating them Logic Programming Prolog Transcribing English to Logic More exercises CSCE 235 Fall 2008 Predicate Logic and Quantifiers 3 Introduction Consider the statements x 3 x y 3 x y z The symbols denote relations between x and 3 x y and 4 and x y and z respectively These relations may hold or not hold depending on the values that x y and z may take A predicate is a property that is affirmed or denied about the subject in logic we say variable or argument of a statement Consider the statement x is greater than 3 x is the subject is greater than 3 is the predicate CSCE 235 Fall 2008 Predicate Logic and Quantifiers 4 Propositional Functions 1 To write in Predicate Logic x is greater than 3 We introduce a functional symbol for the predicate and Put the subject as an argument to the functional symbol P x Terminology P x is a statement P is a predicate or propositional function x as an argument CSCE 235 Fall 2008 Predicate Logic and Quantifiers 5 Propositional Functions 2 Examples Father x unary predicate Brother x y binary predicate Sum x y z ternary predicate P x y z t n ary predicate CSCE 235 Fall 2008 Predicate Logic and Quantifiers 6 Propositional Functions 3 Definition A statement of the form P x1 x2 xn is the value of the propositional symbol P Here x1 x2 xn is an n tuple and P is a predicate We 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 CSCE 235 Fall 2008 Predicate Logic and Quantifiers 7 Propositional Functions Example Let Q x y z denote the statement x2 y2 z2 What is the truth value of Q 3 4 5 Q 3 4 5 is true What is the truth value of Q 2 2 3 Q 2 3 3 is false How many values of x y z make the predicate true There are infinitely many values that make the proposition true how many right triangles are there CSCE 235 Fall 2008 Predicate Logic and Quantifiers 8 Universe of Discourse Consider the statement x 3 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 below be EnrolledinCSE235 x x is enrolled in CSE235 CSCE 235 Fall 2008 Predicate Logic and Quantifiers 9 Universe of Discourse Multivariate functions Each variable in an n tuple i e each argument may have a different universe of discourse Consider an n ary predicate P P r g b c The rgb values of the color c is r g b Example what is the truth value of P 255 0 0 red P 0 0 255 green What are the universes of discourse of r g b c CSCE 235 Fall 2008 Predicate Logic and Quantifiers 10 Outline Introduction Terminology Propositional functions arguments arity universe of discourse Quantifiers Definition using mixing negating them Logic Programming Prolog Transcribing English to Logic More exercises CSCE 235 Fall 2008 Predicate Logic and Quantifiers 11 Quantifiers Introduction The statement x 3 is not a proposition It becomes a proposition When we assign values to the argument 4 3 is false 2 3 is true or When we quantify the statement Two quantifiers Universal quantifier forall the proposition is true for all possible values in the universe of discourse Existential quantifier exists the proposition is true for some value s in the universe of discourse CSCE 235 Fall 2008 Predicate Logic and Quantifiers 12 Universal Quantifier Definition 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 x P x which is read for all x If the universe of discourse is finite say n1 n2 nk then the universal quantifier is simply the conjunction of the propositions over all the elements x P x P n1 P n2 P nk CSCE 235 Fall 2008 Predicate Logic and Quantifiers 13 Universal Quantifier Example 1 Let P x x must take a discrete mathematics course and Q x x is a CS student The universe of discourse for both P x and Q x is all UNL students Express the statements Every CS student must take a discrete mathematics course x Q x P x Everybody must take a discrete mathematics course or be a CS student x P x Q x Everybody must take a discrete mathematics course and be a CS student x P x Q x Are these statements true or false CSCE 235 Fall 2008 Predicate Logic and Quantifiers 14 Universal Quantifier Example 2 Express the statement for every x and every y x y 10 Answer Let P x y be the statement x y 10 Where the universe of discourse for x y is the set of integers The statement is x y P x y Shorthand x y P x y CSCE 235 Fall 2008 Predicate Logic and Quantifiers 15 Existential Quantifier Definition Definition The existential quantification of a predicate P x is the proposition There exists a value x in the universe of discourse such that P x is true We use the notation x P x which is read there exists x If the universe of discourse is finite say n1 n2 nk then the existential quantifier is simply the disjunction of the propositions over all the elements x P x P n1 P n2 P nk CSCE 235 Fall 2008 Predicate Logic and Quantifiers 16 Existential Quantifier Example 1 Let P x y denote the statement x y 5 What does the expression x y P x y mean Which universe s of discourse make it true CSCE 235 Fall 2008 Predicate Logic and Quantifiers 17 Existential Quantifier Example 2 Express the statement there exists a real solution to ax2 bx c 0 Answer Let P x be the statement x b b2 4ac 2a Where the universe of discourse for x is the set of real numbers Note here that a b c are fixed constants The statement can be expressed as x P x What is the truth value of x P x It is false When b2 …
View Full Document
Unlocking...