In this video we're going to learn direct derivation,
a new way of setting up proofs.
We'll also learn two rules, &O and &I.
First I want to introduce direct derivation.
Direct derivation is an alternate way of writing ...
proofs. Up till now we've used simple ...
derivation, in which we start with the ...
premises and go on until you get to the conclusion,
at the end of the proof.
For direct derivation, you start by writing the ...
conclusion on a SHOW line, after the premises and before ...
you do any more steps.
Then you make a box and use the rules to prove the ...
conclusion in the box.
Once you've proved the conclusion inside the box
you close the box
and cancel out the original SHOW:
line by crossing out the word SHOW:.
Here's an example of how that works.
We write down our premises
and after that we write down the conclusion on a separate ...
SHOW line. (The conclusion will be given ...
along with the premises as part of the problem.)
Then we make a box to show Q in.
Now we do rules to the premises.
We can get P by vO from 2 and 3.
Since ~R is the negation of one side of the wedge in line ...
2, we apply vO and we get the ...
other side of the wedge, which is P.
Then we get Q by MP from 1 and 5.
P is what's before the arrow in line 1,
so we get what's after the arrow, which is Q.
Now since we've shown Q in the box,
we cancel out the line where we show
and write DD next to it, to show that we showed Q ...
using direct derivation.
Some things to note about direct derivation.
First, when you write something on ...
a SHOW: line,
you can't use it as an input to other rules if you haven't ...
cancelled out the SHOW: line.
The thing on the SHOW: line is something that needs ...
to be shown. It's not shown until you close ...
the box and cancel the show line,
so you can't use it as an input to rules inside the box.
Also, right now Direct Derivation ...
doesn't let us prove anything we can't prove using simple ...
derivation. It's just another way of writing ...
proofs, with the conclusion explicitly ...
stated just after the premises.
However, later we'll learn some new ...
rules that won't work unless you've written the conclusion ...
on a SHOW: line.
These rules are going to have to be used with Direct ...
Derivation. So we might as well learn ...
direct derivation now.
Also, you don't have to draw the ...
whole box. You can just draw the leftmost ...
line. That's much more convenient ...
if you're typing a proof out.
Now let's learn some new rules.
The first one we'll learn is the rule of &O.
This rule only needs one input,
whose major operator is &. If you have A&B,
then you know A is true.
You also know B is true. So you could get either one of ...
those by using &O.
The upshot is that you can break an &
statement up into its two sides,
as long as & is the major operator.
No input is needed besides the &
statement. This is the first rule we've ...
learned that only requires one input;
once you have the & statement,
it doesn't require anything else to unlock it.
This means that when we do a proof with an &
statement in it, it's a good idea to start by doing the &O.
Let's look at this proof. The second premise is an & statement.
So we start by breaking it up, because that's something we ...
can do. First we get P.
Note that I'm just drawing a line down the left instead of ...
making the whole box.
And we also get the right half, ~R.
Since P is what's before the arrow in 1,
we can do MP and get what's after the arrow, Q->R.
Now the ~R from line 5 is what's after the arrow in ...
Q->R, so we can do MT and get the ...
negation of what's before the arrow, ~Q.
That's what we were trying to show,
so we can cancel the SHOW line and label it as DD.
Now let's look at the &I rule. This is our first introduction ...
rule, which lets us make a more ...
complex sentence out of simpler components by ...
putting a new connective into the statement.
The idea is that we have two inputs and we join them ...
together with an &. Since we know they're true ...
separately, the &
statement must be true.
The inputs can be anything. This lets us put any two things ...
together with &.
Here's one common use for this.
We have an & before an arrow,
as in line 3. And we manage to get each ...
side of the & separately.
We'd like to be able to do MP to line 3,
but in order to do that, we need to exactly match ...
what's in front of the arrow.
We can use &I to put lines 1 and 2 together to get P&Q.
That exactly matches what's in front of the arrow.
So then we can do MP.
So if you have an & in front of an arrow
often you can try to get both sides of the &
then use &I to put them together
and you'll be ready to use MP.
Let's look at how we can put these rules together to do a longer proof.
Here's all the premises and the conclusion.
It may be a bit intimidating to see so many premises.
But we can get a handle on it by starting with the &
statement and then taking the smallest statements we have ...
and seeing if we can combine them with anything.
So we have an & statement in 5,
and we can use &O on it to break it up. We get
and R. Now the P is what's before ...
the arrow in line
so we can get ~Q by MP. That's the negation of one ...
side of the wedge in line
so we get the other side, T,
by vO. We can go back and see that ...
R, in line 8,
is what's before the arrow in line
so we apply MP and get S. Now we have both halves of ...
the & that's before the arrow in line
so we put them together with &I to get S&T
which lets us do MP to get U.
Finally, what we need to show is ...
~Q&U. We have each half of that,
so we can use &I to put that together.
Now we've shown what we needed to show,
so we cancel out the SHOW line and mark it as done using ...
DD. And we're done!
The argument has been proved valid.