Transcription
Page 1 of 6Discrete MathematicsPredicates and QuantifiersPredica esPropositional logic is not enough to express the meaning of all statements in mathematicsand natural language.Examples:Is1 True or FalseIsis a great tennis player True or False?Predicate LogicVariables: , , , etc.Predicates: π , π , etc.Quantifiers: Universal and Existential.Connectives from propositional logic carry over to predicate logic.A predicate πvariables.is a declarative sentence whose truth value depends on one or moreπis also said to be the value of the propositional function π at .πbecomes a proposition when a value ofis assigned from the domain π.Examples (Propositional Functions):1. Let πbe1. Determine the truth value ofa. π 22. Let π b. π, ,bea. π 2, 1, 52 π 1Find these truth valuesb. π , 3, 2020, I. Perepelitsa
Page 2 of 6QuantifiersWe need quantifiers to e press the meaning of English ords including all and someAll students in this class are computer science majorsThere is a math major student in this classThe two most important quantifiers are:Universal Quantifier, For all s mbol Existential Quantifier There e ists s mbol We write as in πand π . πasserts πis true for every in the domain.If,asserts π πIf, ,,, ,, then ππis true for some, then π π. πin the domain.π π. πExamples:1. Let πwith the domain of all positive real numbers.Find the truth value of π .2. Let πith the domain of all real numbersFind the truth value of π .The truth value of πand ππand on the domain π.depends BOTH on the propositional functionQuantifiersStatement π πWhen True?πis true for every .There is an x for which πis true.When False?There is an x for whichπis false.πis false for every . 2020, I. Perepelitsa
Page 3 of 6Example: Suppose the domain of the propositional function π :consists of1, 2, 3 . Write out each of the following propositions using conjunction or disjunction anddetermine its truth value.1. π2. πAn element for which πis false is called a counterexample of πPrecedence of QuantifiersThe quantifiers and have higher precedence than all the logical operatorsE ample πdifferent πmeans π π π πmeans somethingNegating QuantifiersDe Morgan laws for quantifiers (the rules for negating quantifiers) are: π π π πExample: Express each of these statements using quantifiers. Then form a negation of thestatement, so that no negation is left of a quantifier. Next, express the negation in simpleEnglish.1.Some old dogs can learn new tricks. 2020, I. Perepelitsa
Page 4 of 62.Every bird can fly.3. 2020, I. Perepelitsa
Page 5 of 6Translating from English into Logical ExpressionsExamples: Translate the statements into the logical symbols. Let be in set of all studentsin this class.1. Someone in your class can speak Hindi.2. Everyone in your class is friendly.3. There is a student in your class who was not born in California.π»βπππ π»π ππβ, πΉβπ π ππ ππ , β πΆβπ ππ πΆππππππ. βExample: Translate the follo ing sentence into predicate logic and give its negationEver student in this class has taken a course in JavaSol ionFirst decide on the domain USol ion If U is all students in this class define a propositional function J xdenoting has taken a course in Java and translate asSol ion But if U is all people also define a propositional function Sis a student in this class and translate asdenoting 2020, I. Perepelitsa
Page 6 of 6E ample Translate the follo ing sentence into predicate logicSome student in this class has taken a course in JavaSol ionFirst decide on the domain USol ionIf U is all students in this class translate asSol ionBut if U is all people then translate as 2020, I. Perepelitsa
Discrete Mathematics Predicates and Quantifiers Predica es Propositional logic is not enough to express the meaning of all statements in mathematics and natural language. Examples: Is Γ² T P1 Γ³ True or False . Γ²Ever student in this class has taken a course in Java Γ³ So
