Identify and evaluate predicates

- [Voiceover] Let's talk about predicates, a key to writing formal logic proofs. A logical statement whose truth value is a function of one or more variables is called a predicate. A predicate is read P of x. If P of x represented this statement, that x is an even number, it is not a proposition since we don't have any bounds for the value of x. The truth of the statement depends on the value of x. If the value of x is four, such as P of four, then it would be true. But if the value of x is three, P of three would be false. A proposition that takes two variables, x and y, might say that the square root of x is equal to y. Then the proposition P of 36 comma six would be true because the square root of 36 is six. The domain of the function is the set of all possible values for the variables. This is what determines if it is true or false, and it can be finite or infinite. A predicate can also be defined as a proposition by adding a quantifier. There are two types of quantifiers. The universal quantifier, which is read as for all. And an existential quantifier, which represents there exists. Notice the symbols. A universal quantifier looks like an upside down capital A. The existential quantifier looks like a backwards capital E. An example of a universal quantifier might be all students completed their homework. Let me show you what it would look like if we were going to assign variables to the values. We would say students is represented with the letter s. And completed their homework could be h. This statement would now look like, all students, s, comma, h, completed their homework. Every student has a driver's license. Every student would be represented by the universal quantifier and the variable s, comma, has a drivers license, we could represent that as d. Existential quantifiers might be there is a student who completed their homework. We'll use the s again to represent the student. And h for completed their homework. This time our logical statement would look like this. There exists a student, s, comma, which means such that, h, they completed their homework. There is a student that has their driver's license. Same thing, we'll do an s for student, and a d for driver's license, and I'll write my backwards E, which means there esxists, a student s, comma, such that that student has their driver's license. Now let's talk about how to apply De Morgan's Law to both the universal and existential quantifiers. De Morgan's Law says, in this case, not all x P of x. Well that would be logically equivalent to there exists an x such that not P of x. When you're looking at De Morgan's Law, it almost looks to me like you distribute the not sign into each part of the equation. Okay, let's do the same thing for the existential. This time I'll distribute the not to the existential, and then I'll distribute the not to the P of x. So this is logically equivalent to all x comma not P of x. It's important to note that when you apply De Morgan's Law, which is the not operator, that you apply it to both the quantifier and the proposition. Let's continue with talking about how to negate propositions. To negate a universal statement, it changes to an existential statement. In our example we say, not every student has a driver's license. So logically this would look like, there exists a student such that, which is a comma, not d. There exists a student, s, such that they do not have their driver's license. Let's do the same thing, this time I want to negate an existential statement, and turn it into a universal statement. There is a student who completed their homework. And I'm going to apply the not operator. This will become, all students, s, comma, did not complete their homework. When a predicate has a quantifier, if the domain is small, it is often easy to prove whether or not this is true using the method of exhaustion. In this example, I have a universal set equal to the numbers one, three, five, seven, and nine. So the question is, is this true or false that for all x, x is an odd number? Well, the method of exhaustion says just to go through each number. It looks like one is odd, that's good. Three is odd, five, seven, and nine. It looks like everything works, so this is a true statement. How about this one? For all x, x plus three is greater than or equal to seven. So we'll start with one, we'll do one plus three is four. Hmmm, well that's not greater than or equal to seven. So right here I have already found a counter example. And when you're dealing with the universal quantifier, that means the entire statement is false. I only have to find one counter example. Finally, all x, x is prime. Okay, we'll go through our numbers again. One is good, three is prime, five is prime, seven is prime, but nine is equal to three times three, therefore it's not prime, so this statement is also false. We can use the same method dealing with the existential operator. I have a universal set with the values one, two, five, eight, and nine. The difference here is I just have to find one value that matches the criteria. So there exists an x such that x is odd. Well, we got three odd numbers, one, five, and nine. So we are good to go. There exists an x such that x plus three is greater than or equal to 13. Well, I want to get to 13, so I'll take the largest number in my set, which is nine, and do nine plus three. But nine plus three is only 12. So it looks like none of the numbers are going to work, so this one is false. As you can see, predicates can be defined as propositions when we add quantifiers or functions with well defined domains.