tailieunhanh - Lecture Discrete mathematics and its applications - Lecture 3

This chapter define the term computer program, describe the use of flowcharts and pseudocode in programming, identify two ways in which a program can work toward a solution, differentiate the two main approaches to computer programming, list and describe three elements of object-oriented programming. | The Foundations: Logic and Proofs Chapter 1, Part II: Predicate Logic With Question/Answer Animations Copyright © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of McGraw-Hill Education. Summary Predicate Logic (First-Order Logic (FOL), Predicate Calculus) The Language of Quantifiers Logical Equivalences Nested Quantifiers Translation from Predicate Logic to English Translation from English to Predicate Logic Predicates and Quantifiers Section Section Summary Predicates Variables Quantifiers Universal Quantifier Existential Quantifier Negating Quantifiers De Morgan’s Laws for Quantifiers Translating English to Logic Logic Programming (optional) Propositional Logic Not Enough If we have: “All men are mortal.” “Socrates is a man.” Does it follow that “Socrates is mortal?” Can’t be represented in propositional logic. Need a language that talks about objects, their properties, and their relations. Later we’ll see how to draw inferences. Introducing Predicate Logic Predicate logic uses the following new features: Variables: x, y, z Predicates: P(x), M(x) Quantifiers (to be covered in a few slides): Propositional functions are a generalization of propositions. They contain variables and a predicate, ., P(x) Variables can be replaced by elements from their domain. Propositional Functions Propositional functions become propositions (and have truth values) when their variables are each replaced by a value from the domain (or bound by a quantifier, as we will see later). The statement P(x) is said to be the value of the propositional function P at x. For example, let P(x) denote “x > 0” and the domain be the integers. Then: P(-3) is false. P(0) is false. P(3) is true. Often the domain is denoted by U. So in this example U is the integers. Examples of Propositional Functions Let “x + y = z” be denoted by R(x, y, z) and U (for all three variables) be the integers. Find these truth values: R(2,-1,5) Solution: | The Foundations: Logic and Proofs Chapter 1, Part II: Predicate Logic With Question/Answer Animations Copyright © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of McGraw-Hill Education. Summary Predicate Logic (First-Order Logic (FOL), Predicate Calculus) The Language of Quantifiers Logical Equivalences Nested Quantifiers Translation from Predicate Logic to English Translation from English to Predicate Logic Predicates and Quantifiers Section Section Summary Predicates Variables Quantifiers Universal Quantifier Existential Quantifier Negating Quantifiers De Morgan’s Laws for Quantifiers Translating English to Logic Logic Programming (optional) Propositional Logic Not Enough If we have: “All men are mortal.” “Socrates is a man.” Does it follow that “Socrates is mortal?” Can’t be represented in propositional logic. Need a language that talks about objects, their properties, and their relations. Later we’ll see how to .