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.