PROFESSOR: So now we're going to talk about the concepts of validity and satisfiability, which take on some extra interest in the context of predicate calculus. So let's remember for propositional validity, if you have a propositional formula with variables taking the truth values ranging over true and false, then a formula is valid when it's true for all possible truth values.
So here's an example that P implies Q or Q implies P. And you can check that for the four possible environments of P and Q-- true/false values of P and Q, this OR will come out to be true. Well, for predicate formulas there's a bunch of things that I need to give value to that are more complicated than just truth values.
In particular, I will say that a predicate calculus formula is valid when it's true for all possible domains of discourse that the variables range over. There's a technicality that it has to be non-empty, but aside from that all possible domains. And whenever you have a predicate mentioned in the formula, in order to know whether the formula is true or not, I need to know what that predicate means. So a formula is valid if it comes out true no matter what the predicate means.
Let's look at a concrete example to get a grip on this. Here is a valid formula of predicate calculus. It's mentioning predicates P and Q. It's of the form of a proposition because it's saying something about every possible z in the domain and every possible x and every possible y. The only thing that we need to know to make sense out of this formula, to figure out whether or not it's true, is what's the domain that x, y, and z range over and what exactly do P and Q mean?
Well, I want to argue informally. Let's just look at what this is saying together. What this is saying is suppose that for everything in the domain, both property P of z and P of Q. In other words, everything in the domain have property P and property Q. Well, that certainly implies that everything in the domain has property P because they have both properties. And also, everything in the domain has property Q because everything has both properties.
So when you say it that way, the sense that this is a fundamental logical fact that doesn't depend on what P and Q mean or what the domain is. It's just a fact about the nature of the meaning of the for all universal quantifier and the connectives [? AND then ?] implies. That's how we figure out that this is valid.
Well, let me go one level in more detail to say again what I just said informally and try to be a little bit more precise and clear about a reason why this formula is valid. So suppose I wanted to prove that the formula is valid.
Well, it's an implication. So the proof strategy-- there it is written again-- the proof strategy is I'm going to assume that the if part, the left-hand side of the implies or hypothesis, is true. That is, that for every z, P of z holds and Q of z holds. And then I'm going to try to prove, based on that, that the consequent holds, namely that the right-hand side for all x P of x and for all y Q of y holds.
OK. How am I going to do that? Well, so here's the formula written just to fit on the line with the concise mathematical symbols. The upside down V means AND, and the arrow means implies. And we want to try to prove that this is valid a little bit more carefully.
Well, the strategy, as I said, is to assume that the left-hand side holds. Well, what's the left-hand side say? It says that for every z, Q of z holds and P of z holds. That means that for every possible environment that assigns a value to z, Q of z and P of z both come out to be true.
Well, suppose that the environment assigns the value c to z, where c is some element of the domain. Then what this means is that in that environment, Q of z and P of z is true, which means that Q of c and P of c holds. But Q of c holds and P of c holds, so Q of c certainly holds all by itself. All right.
So now we're in an interesting situation because we just proved that Q of c holds. And we know nothing and have assumed nothing about c except that it's an element of the domain. c could have been any element of the domain, and we've managed to prove that Q of c holds. So it follows that, in fact, we have really proved that for every x Q of x holds.
Now, that step of saying I proved it for Q of a given element without making any assumptions about the given element except that it's in the domain and therefore I can conclude that it holds for all domain elements, [? it's a ?] very natural and plausible and understandable rule. And it's a basic axiom of logic called UG-- Universal Generalization. We'll come back to it in a minute.
Anyway, I've just proved that for all x Q of x holds. And by a completely symmetric argument, for all y P of y holds. And having proved both for all x Q of x and for all y P of y, clearly the AND holds. And I've just proved that the right-hand side of this implication is true given that the left-hand side is true.
Now, having called this proving validity, let me immediately clarify that this is not fair to call a proof because the rules of the game are really murky here. This theorem, you could read it as saying that universal quantification distributes over AND is one of these basic valid formulas that is so fundamental and intelligible that it's hard to see what more basic things you are allowed to assume when you're proving it.
And this proof really isn't anything more than translating upside down A and the AND symbol into English and using ordinary intuitive rules about for all and AND and using that in the proof. So this is a good way to think about the formula to get an understanding of it. But it's not right to say that it's a proof because we haven't been exactly clear about what the proof rules are.
And with this kind of really fundamental valid fact, it becomes a quite technical problem to decide what a proof is going to be. What's fair to assume and what's fair not to assume? It would actually be perfectly plausible to take this as an axiom and then prove other things as a consequent of it.
Anyway, going on, let's look at this just for cultural reasons. We're never going to actually ask you to do anything with it. But the universal generalization rule UG would be stated this way as a deduction rule in logic. The stuff over the bar means if you've proved this, then you can conclude you've proved the stuff below the bar. So what this is saying is if you've proved P of c for a constant c, then you can deduce that for every x P of x holds.
And this is providing that c does not occur in any other part of the predicate P except where you're talking explicitly about it. It's hard to be more precise about that for now. Don't worry about it. But the idea is you're not supposed to assume anything about c other than it's in the domain and that it has property P, and you can then conclude that everything has property P.
So let's look at a similar example where it is possible to prove something. Namely, I can prove that something's not valid. So here's a similar-looking formula. This one says that for every z if P of z holds OR Q of z holds, then for every x P of x holds OR for every y Q of y holds. And this one we're going to show is not valid.
Let's think about it for a minute. What it's saying is if everything has either property P or property Q, that implies that everything has property P or everything has property Q. Well, when you say it that way, it's clearly not the case. But let's go one level more precise and lay that out.
What I'm going to do is convince you that it's not valid by giving you a counter-model where I choose an interpretation. I choose a domain of discourse and predicates that P and Q are going to mean over that domain and that make the left-hand side of this implication true. And then I'm going to show you that the right-hand side is not true. And that means that in that domain with those interpretations of P and Q, this implication fails so it's not valid.
So I need to make the left-hand side true and the right-hand side false. Well, I'm going to choose the domain of discourse to be the simplest one that will make this false, namely let's let the domain of discourse just be the numbers 1 and 2. And let Q of z be the predicate that says z is 1 and P of z be the predicate that says z is 2.
Well, is the left-hand side true? Yeah, because the only things there are in the domain are 1 and 2, and so clearly everything in the domain is either 1 or 2. So the antecedent is true. On the other hand, is everything in the domain, does it satisfy P? Is everything in the domain equal to 2? No, 1's not equal to 2.
What about, is everything in the domain equal to 1? Is it true that for all y Q of y holds? No, 2 is in the domain, and it's not equal to 1. And so we have found exactly what we wanted, a counter-model which makes the left-hand side of the implies true and the right-hand side of the implies false.
Let me close with just one more example of a valid formula that we can talk through. This is the version of De Morgan's law that works for quantifiers. Remember De Morgan's law was the thing that said that the negation of P or Q was the same as not P and not Q. And remembering that the connection between universal quantification, [? an ?] AND, and existential quantification, [? an ?] OR, it turns out that by the same kind of reasoning, De Morgan's law comes out this way.
It says that if it's not true that everything has property P, that's possible if and only if there's something that doesn't have property P. And so that's what De Morgan's law is. It's another thing you could take as an axiom, or you could try one of these hand-waving proofs about. But I think I've said enough to give you that example of another interesting valid formula, and we'll stop with that.