Predicate Logic 1

Flash and JavaScript are required for this feature.

Download the video from iTunes U or the Internet Archive.

PROFESSOR: The logic of predicates is a basic concept in mathematical language as well as being a topic on its own. In particular, I'm going to talk now about the idea of the two so-called quantifiers. For all-- that's the upside-down A. And exists-- that's the backward E.

So what's a predicate? Basically, a predicate is a proposition, except it's got variables in it. Here's an example. P of x, y is the predicate that depends on x and y. And let's say it's defined to be x plus 2 equals y.

Now, in order to figure out whether or not a predicate is true, I need to know the values of the variables-- in this case, x and y. So if I tell you that x is 1 and that y is 3, guess what? P of 1 and 3-- P of x and y when x is 1 and y is 3-- is true, because in fact, 1 plus 2 is equal to 3.

If I tell you that x is 1 and y is 4, then since 1 plus 2 is not equal to 4, P of 1 and 4 is false. On the other hand, since P of 1 and 4 is false, that makes not P of 1 and 1 true. That's the easy part.

Now the quantifiers are read as "for all" and "exists." But they control a variable. So I write "for all x," it means-- sorry. I write upside-down Ax and I read it as "for all x." I'm so used to reading it that I forgot that I needed to read symbols literally. And backwards Ey is read as "there exists some y."

So let's see how that would work. The upside-down A, for all, acts like an AND. To understand what it means, let's look at this example. Let's let a variable s range over the staff members in 6.042 at this term, of whom there are about 30 counting the graders. Let's define a predicate that depends on the variable s called P of s that says that s is pumped about 6.2042. They're enthusiastic about being on the staff. OK.

If I tell you for all s, P of s, that's exactly the same as saying that P of Drew is true, and P of Peter is true, and P of Keshav is true, and a whole bunch more ANDs down to P of Michaela. They'll be 29 ANDs if there are 30 staff members.

Similarly, the backwards E-- there exists-- acts like an OR. If I tell you that t is now ranging over the 6.042 staff just as s was, and I write B of t, the predicate of t means the staff member t took 6.042 before, then if I tell you that there exists a t B of t, what I'm telling you is that B of Drew-- either Drew took it before, or Peter took it before, or Deshav took it before, or Michaela took it before.

This statement is true, because in fact, several of the staff members took 6.042 from me before. And I'd like to think that the previous one-- that everybody's pumped up on the staff-- is true, although I can't guarantee that.

So let's do a little practice with existential quantifiers. So let's agree that the variables x and y will range, for this example, over the non-negative integers. And let's consider the following predicates about y that says that there's some x that's less than y. Q of y is there exists an x that x is less than y. Let's see what happens.

Well, what about Q of 3? Q of 3 is saying that there is an x such that x is less than 3. Well, an example of such an x is 1. So that means there is an x that's less than 3, because 1 is. And so that makes this Q true.

All right, what about Q of 1? Well, again, there's an x that's a non-negative integer, namely 0, that's less than 1. And therefore, Q of 1 is true. On the other hand, Q of 0 is false because there is no non-negative integer that's less than 0. And so there's no value that you can assign to x that's a non-negative integer that will make it less than 0. OK, that one's not so bad, I hope.

Let's look at the same example with the universal quantifier. This time, we'll say that R of y means that for every x, x is less than y. Well, R of 1 is false. And the reason is that 5 is a counterexample. 5 is not less than 1. And so it's not true that every x is less than 1.

R of 8 is false because 12 is not less than 8. And therefore, not every x is less than 8. R of a googol, 10 to the 100th, is false. Because if you let x be a googol, it's not less than a googol. And so it's an example of the fact that this doesn't hold for all x's. That part's obvious. OK.

The thing that tends to confuse people in the beginning is what happens when you start mixing up quantifiers. So let's look at an intuitive example first that might help you remember what happens when you have an A followed by an E. And then we'll look at an E followed by an A.

So suppose I look at this statement. This time, I'm going to tell you that v ranges over the possible computer viruses, not biological viruses. d ranges over antivirus software, defenses against viruses. And I want to look at the predicate that says for every virus, there is a defense such that d protects against v. This defense is good against that virus.

All right, so each virus, I have a defense for. So an example would be-- these are, by the way, dated viruses, but that's when the slides were made. So against the Mydoom virus, you could use Defender, Microsoft Defender. Against the ILOVEYOU virus, you could use Norton. Against the Bablas virus, you could use ZoneAlarm.

Well, is that what we want? It's expensive. It means that for every different virus, I need a different defense. I have to spend a fortune on software. This is not what we want. So that's when for every virus, there's a defense, but the quantifiers are in the wrong order.

Let's reverse them. Suppose I tell you that there's one defense that's good for all viruses. There is a defense such that for every virus, d protects against v. For example, if d is MITviruscan, then it would be wonderful if it was true that d protects against all viruses, there's one defense good against every attack. That's what we want because it's a lot cheaper.

All right, let's start looking at a concrete mathematical example. And I hope that that prelude with the viruses will help you decipher how the quantifiers behave. So let's look at this predicate now. Sorry, this is a proposition. It really doesn't depend on the values of x and y. It's asking about all possible x's and all possible y's, whether there is one.

In order to figure out whether a proposition like G is true, actually, I do need to know what x and y are ranging over. Because as you'll see, whether or not G comes out to be true will depend on that. So I'm going to look at the domain of discourse that x and y range over. And we'll suppose that the domain is the non-negative integers.

So now, what G is saying is that if you give me a non-negative integer x, there is a y that's greater than x. In other words, I can find another non-negative integer that's bigger than x. Well, that's certainly true.

There's a simple recipe for finding y. Give me an x. Let's choose y to be x plus 1, or x plus 2. But I don't necessarily need a recipe as long as somewhere out there, there's a y that's bigger than x. This is true. So G is true when the domain of discourse is the non-negative integers.

On the other hand, when I change the domain of discourse, different things can happen. So let's look at the negative integers, the integers less than 0, and ask, is it true that for every x, there's a y that's greater than x? Well, for a lot of them, there is. If x is minus 3, then minus 2 is bigger than x. If x is minus 2, then minus 1 is bigger than x.

But then I'm in trouble. If x is minus 1, there's no negative integer that's bigger than x. And so G is false when the domain of discourse is the negative integers.

Well, let's shift again, the point being here both we're looking at alternate quantifiers, and we're understanding that the truth of a proposition with quantifies depends crucially on the domain of discourse. If we let the domain of discourse be the negative reals, then what this is saying is that for every negative real, there's a bigger negative real.

And that, of course, is true. Because if you give me a negative real r, then r over 2, because it's negative, is actually bigger than r. And it will not be positive if r isn't positive. So sure enough, G in this case is true.

All right, let's reverse the qualifiers and see what happens. It's worth thinking about. So let's call H the assertion that for every y-- sorry, that there exists a y such that for every x, x is less than y. So intuitively, what this is saying is there's a biggest element. Y is bigger than everything.

Well, if the domain is the non-negative integers, then H is false because there's no biggest non-negative integer. If it's the negative integers, it's false because there's no biggest negative integer. If it's the negative reals, it's false because there's no biggest negative real.

But the truth is that this thing is going to be false in any domain of discourse in which less than is behaving as it should because all any y is not going to be bigger than itself. So you can't possibly find a biggest y. It would have to be bigger than itself. This is going to be false in all of the sensible domains where less than behaves as we would expect.

So let's make this slightly more interesting and make that less than or equal to. So now, it's actually possible that there could be a biggest element that is greater than or equal to everything including itself. And if you look at these domains, well, there this isn't any greatest non-negative integer, because for any x, plus 1 is bigger. There isn't any biggest negative real-- same reasoning. For any r, r/2 is going to be bigger.

But for the negative integers, there is a biggest y, namely minus 1. It's greater than or equal to every other negative integer.

Free Downloads

Video


Caption

  • English-US (SRT)