Discrete Structures for Computer Science Presented By: Andrew F. Conn Slides adapted from: Adam J. Lee Lecture #3: Predicates and Quantifiers September 7th, 2016 Todays topics Predicates Quantifiers Logical equivalences in predicate logic Translations using quantifiers Propositional logic is simple, therefore

limited Propositional logic cannot represent some classes of natural language statements Given: Kody is one of my dogs Given: All of my dogs like peanut butter ? Propositional logic gives us no way to draw the (obvious) conclusion that Kody likes peanut Propositional logic also limits the mathematical truths that we can express and reason about

Consider the following: p1 p2 p3 p4 p5 2 has no divisors other than 1 and itself

3 has no divisors other than 1 and itself 5 has no divisors other than 1 and itself 7 has no divisors other than 1 and itself 11 has no divisors other than 1 and itself This is an inefficient way to reason about the properties of prime numbers! General problem: Propositional logic has no way of reasoning about instances of general statements. Historical Context The previous examples are called syllogisms Aristotle used syllogisms in his Prior

Analytics to deductively infer new facts from existing knowledge Major premise All men are mortal Socrates is a man Socrates is mortal Conclusion Minor premise Predicate logic allows us to reason about the properties of individual objects and classes of objects Predicate logic allows us to use propositional

functions during our logical reasoning P(x) x3 > 0 variable predicate Note: A propositional function P(x) has no truth value unless it is evaluated for a given x or set of xs. Examples Assume P(x) x3 > 0. What are the truth values of the following expressions: P(0)

false P(23) true P(-42) false We can express the prime number property using predicate logic: P(x) x is primex is prime D(x) x is primex has no divisors other than 1 and itself P(x) D(x) Predicates can also be defined on more than one variable Let P(x, y) x + y = 42. What are the truth values of the following expressions:

P(45, -3) true P(23, 23) false P(1, 119) false Let S(x, y, z) x + y = z. What are the truth values of the following expressions: true S(1, 1, 2) false S(23, 24, 42) true S(-9, 18, 9)

Predicates play a central role in program control flow and debugging If/then statements: if x > 17 then y = 13 Loops: while y <= 14 do end while Debugging in C/C++: assert(strlen(passwd) > 0); This is a predicate!

Quantifiers allow us to make general statements that turn propositional functions into propositions In English, we use quantifiers on a regular basis: All students can ride the bus for free Many people like chocolate I enjoy some types of tea At least one person will sleep through their final exam Quantifiers require us to define a universe of discourse (also called a domain) in order for the quantification to make sense x is primeMany like chocolate doesnt make sense! What are the universes of discourse for the

above statements? Universal quantification allows us to make statements about the entire universe of discourse Examples: All of my dogs like peanut butter Every even integer is a multiple of two For each integer x, 2x > x Given a propositional function P(x), we express the universal quantification of P(x) as x P(x) What is the truth value of x P(x)? true if P(x) is true for every x in the universe of discourse false if P(x) is false for just one x in the universe of

discourse Examples All rational numbers are greater than 42 Domain: rational numbers Propositional function: Let G(x) x is primex is greater than 42 Statement: x G(x) Truth value: false (counterexample: 1/2) If an natural number is prime, it has no divisors other than 1 and itself Domain: natural numbers Propositional functions: Let P(x) x is primex is prime

Let D(x) x is primex has no divisors other than 1 and itself Statement: x [P(x) D(x)] Truth value: true (by definition) Existential quantifiers allow us to make statements about some objects Examples: Some elephants are scared of mice There exist integers a, b, and c such that the equality a2 + b2 = c2 is true There is at least one person who did better than John on the midterm Given a propositional function P(x), we express the

existential quantification of P(x) as x P(x) What is the truth value of x P(x)? true if P(x) is true for at least one x in the universe of discourse false if P(x) is false for all x in the universe of discourse Examples The inequality x + 1 < x holds for at least one integer Domain: Integers Propositional function: P(x) x + 1 < x Statement: x P(x) Truth value: false For some integers, the equality a2 + b2 = c2 is

true Domain: Integers Propositional function: P(a, b, c) a2 + b2 = c2 Statement: a,b,c P(a,b,c) Truth value: true We can restrict the domain of quantification The square of every natural number less than 4 is no more than 9 Domain: natural numbers Statement: x<4 (x2 9) Truth value: true This is equivalent to writing

x [(x < 4) (x2 9)] Some integers between 0 and 6 are prime Domain: Integers Propositional function: P(x) x is primex is prime Statement: 0x6 P(x) Truth value: true This is equivalent to writing x [(0x6) P(x)] Group work! Problem 1: Assume M(x) x is primex is a Monday and D(x,y) 2x = y. What are the truth values of the

following statements? M(x is primeSeptember 7th, 2016) D(2, 4) Problem 2: Let P(x) x is primex is prime where the domain of x is the integers. Let T(x,y) x is primex = 3y where the domain of x and y is all natural numbers. What are the truth values of the following statements? x P(x) x,y T(x,y) We can extend the notion of logical equivalence to expressions containing predicates or quantifiers

Definition: Two statements involving predicates and quantifiers are logically equivalent iff they take on the same truth value regardless of which predicates are substituted into these statements and which domains of discourse are used. Prove: Given: implies that we can pick the one value of x that the statement is true. Lets call this value . So we have giving us at least one element that makes true, namely the element . This implies . By a similar argument we have . Thus we have .

Prove: Given: implies that we can pick the values of that make the statement true. Lets call these values and . So we know is true. If was the true statement in the original, then we have at least for . If was the true statement in the original, then we have at least for . In either case we have Prove: Given: , Pick an arbitrary element Thus we have: Since the selection of was arbitrary for both and

, we must have For the other direction, just pick both s to be the same. Thus we have: And: We also have DeMorgans laws for quantifiers Negation over universal quantifier: x P(x) x P(x) Intuition: If P(x) is not true for all x, then there is at least one x for which P(x) is false

Intuition: Ifover P(x) is not true forquantifer: at Negation existential x P(x) least one value x, then P(x) is false x P(x) for all x Prove: Given: then we know that it is not that case that is true for all in the domain. Pick the value for that makes false, call it .

Thus we have . Since there exists a value for x which satisfies , we have . Likewise, given , let be the element for which this is true. Then is false when we pick . Thus we have Therefore Translations from English To translate English sentences into logical expressions: 1. 2. 3. 4. 5.

Rewrite the sentence to make it easier to translate Determine the appropriate quantifiers to use Look for words that indicate logical operators Formalize sentence fragments Put it all together Example: At least one person in this classroom is named Adam and has lived in Pittsburgh for 8 years Existential quantifier Rewrite: There exists at least one person who is in this classroom, is named Adam, and has lived in Pittsburgh for 8 years Conjunction

Formalize: C(x) x is primex is in this classroom N(x) x is primex is named Adam P(x) x is primex has lived in Pittsburgh for 8 years Final expression: x [C(x) N(x) P(x)] Example: If a student is taking CS441, then they have taken high school algebra Universal quantifier Rewrite: For all students, if a student is in CS 441, then they have taken high school algebra Formalize:

Implication C(x) x is primex is taking CS441 H(x) x is primex has taken high school algebra Final expression: x [C(x) H(x)] Negate the previous example x [C(x) H(x)] x [C(x) H(x)] x [C(x) H(x)] x [C(x) H(x)] a b a b x [C(x) H(x)] Double negation

law DeMorgans law for negation over the universal quantifier DeMorgans law for negation over disjunction Translate back into English: There is a student taking CS441 that has not taken high school algebra! Example: Jane enjoys drinking some types of

tea Rewrite: There exist some types of tea that Jane enjoys drinking Formalize: T(x) x is primex is a type of tea D(x) x is primeJane enjoys drinking x Final expression: x [T(x) D(x)] Negate the previous example: x [T(x) D(x)] x [T(x) D(x)] x T(x) D(x) x T(x) D(x) x is primeFor all types of drink, if x is a tea, Jane does not enjoy drinking it.

Group work! Problem 3: Translate the following sentences into logical expressions. a) Some cows have black spots b) At least one student likes to watch football or ice hockey c) Any adult citizen of the US can register to vote if he or she is not a convicted felon Problem 4: Negate the translated expressions from problem 3. Translate these back into English. Final Thoughts The simplicity of propositional logic makes it unsuitable

for solving certain types of problems Predicate logic makes use of Propositional functions to describe properties of objects The universal quantifier to assert properties of all objects within a given domain The existential quantifier to assert properties of some objects within a given domain Predicate logic can be used to reason about relationships between objects and classes of objects Next lecture: Applications of predicate logic and nested quantifiers Please read section 1.4 Extra slides

Prove: x [P(x) Q(x)] x P(x) x Q(x) We must prove each x is primedirection of the equivalence. Assume that P and Q have the same domain. First, prove x [P(x) Q(x)] x P(x) x Q(x): If x [P(x) Q(x)] is true, this means that there is some value v in the domain such that either P(v) is true or Q(v) is true If P(v) is true, then x P(x) is true and [x P(x) x Q(x)] is true If Q(v) is true, then x Q(x) is true and [x P(x) x Q(x)] is true Thus x [P(x) Q(x)] x P(x) x Q(x) Prove: x [P(x) Q(x)] x P(x) x Q(x)

Then, prove x P(x) x Q(x) x [P(x) Q(x)]: If x P(x) x Q(x) is true, this means that there is some value v in the domain such that either P(v) is true or Q(v) is true If P(v) is true, then x [P(x) Q(x)] is true If Q(v) is true, then x [P(x) Q(x)] is true Thus x P(x) x Q(x) x [P(x) Q(x)] Since x [P(x) Q(x)] x P(x) x Q(x) and x P(x) x Q(x) x [P(x) Q(x)] then x [P(x) Q(x)] x P(x) x Q(x). Prove: x P(x) x P(x) x P(x) x P(x) x P(x) is true if and only if x P(x) is false

x P(x) is false if and only if there is some v such that P(v) is true If P(v) is true, then x P(x) x P(x) x P(x) x P(x) is true if and only if there is some v such that P(v) is true If P(v) is true, then clearly P(x) does not hold for all possible values in the domain and thus we have x P(x) Therefore x P(x) x P(x).