Predicate Logic and QuantifiesLaTexOutlineIntroductionPropositional Functions (1)Propositional Functions (2)Propositional Functions (3)Propositional Functions: ExampleUniverse of DiscourseUniverse of Discourse: Multivariate functionsSlide 11Quantifiers: IntroductionUniversal Quantifier: DefinitionUniversal Quantifier: Example 1Universal Quantifier: Example 2Existential Quantifier: DefinitionExistential Quantifier: Example 1Existential Quantifier: Example 2Quantifiers: Truth valuesMixing quantifiers (1)Mixing quantifiers (2)Mixing Quantifiers: Truth valuesMixing Quantifiers: Example (1)Mixing Quantifiers: Example (2)Mixing Quantifiers: Example (3)Mixing Quantifiers: Example (4) false mathematical statementMixing Quantifiers: Example (5)Slide 28Binding VariablesBinding Variables: ScopeNegationNegation: TruthSlide 33Prolog (1)Prolog (2)English into LogicMore exercises (1)More Exercises (2)Alert…Predicate Logic and QuantifiesSections 1.3 and 1.4 of RosenFall 2008CSCE 235 Introduction to Discrete StructuresCourse web-page: cse.unl.edu/~cse235Questions: [email protected] Logic and QuantifiersCSCE 235, Fall 20082LaTex•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}$Predicate Logic and QuantifiersCSCE 235, Fall 20083Outline•Introduction•Terminology:–Propositional functions; arguments; arity; universe of discourse•Quantifiers–Definition; using, mixing, negating them•Logic Programming (Prolog)•Transcribing English to Logic•More exercisesPredicate Logic and QuantifiersCSCE 235, Fall 20084Introduction•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 predicatePredicate Logic and QuantifiersCSCE 235, Fall 20085Propositional 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 argumentPredicate Logic and QuantifiersCSCE 235, Fall 20086Propositional 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 predicatePredicate Logic and QuantifiersCSCE 235, Fall 20087Propositional 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.Predicate Logic and QuantifiersCSCE 235, Fall 20088Propositional Functions: Example•Let Q(x,y,z) denote the statement ‘x2+y2=z2’–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?Q(3,4,5) is trueThere are infinitely many values that make the proposition true, how many right triangles are there?Q(2,3,3) is falsePredicate Logic and QuantifiersCSCE 235, Fall 20089Universe 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’Predicate Logic and QuantifiersCSCE 235, Fall 200810Universe 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)?Predicate Logic and QuantifiersCSCE 235, Fall 200811Outline•Introduction•Terminology:–Propositional functions; arguments; arity; universe of discourse•Quantifiers–Definition; using, mixing, negating them•Logic Programming (Prolog)•Transcribing English to Logic•More exercisesPredicate Logic and QuantifiersCSCE 235, Fall 200812Quantifiers: 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 discoursePredicate Logic and QuantifiersCSCE 235, Fall 200813Universal 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)Predicate Logic and QuantifiersCSCE 235, Fall 200814Universal 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.”–“Everybody must take a discrete mathematics course or be a CS student.”–“Everybody must take a discrete mathematics course and be a CS student.” x Q(x) P(x) x ( P(x) Q(x) ) x ( P(x) Q(x) )Are these statements true or false?Predicate Logic and
View Full Document
Unlocking...