It is finally time to introduce proofs in our language, propositional logic, using a Fitch-style system. So I wasn't going to use Fitch at first because personally I think it's a little unnecessary, but it's a good way to sort of introduce the idea of sub-proofs and proofs. So what is a proof, first of all? A proof is a set of premises, like let's say we have P and Q.
not Q, P arrow R, and we can prove R from this. And this is a proof, and our whole point of doing this and the motivation is to give you rules to get from these set of conclusions to your premise mathematically and systematically, such that every single step you take is also going to be true as well. So we can't prove it if everything isn't true and everything doesn't flow nicely. So we have a couple rules for our proofs and we're going to go through them. So we have an assumption rule.
So if we have on a Fitch system we always have a line to our left. If we have say a letter a and this is an assumption then we can rewrite a anywhere we want. So say if we have an a at line 1, we can rewrite it again at line n.
This just means from anywhere. And we write 1 reit, because we have to remind ourselves what we did on each line, so that way it's true. And we have justification of what we did. So what this means is that from line 1, we reiterated it.
So this is one of our basic rules. Another one here. we have a thing called modus opponents, and you might remember this. If we start off with, say, on line i, we have a.
On some other line, we have a arrow b. Then we can conclude b from, well, let's call these assumptions. So this is an assumption, this is an assumption, then b we say is from line i and line j and this is mp for modus ponens. Now when I say line i and line j, I just mean any line.
If it's a 2 and a 4 there, you just put 2, 4, mp. So this is also called conditional elimination sometimes, which you might see as that. This is a really weird term for this because it's modus ponens and It is a commonly used term everywhere in philosophy. So I kind of question books that use arrow elimination or they call it conditional elimination. It's kind of weird.
It bothers me in ways that it shouldn't. And elimination. Okay, here's another good one. We also abbreviate this like this.
If you have A and B on some line, then later you can get and. just A. You can get any one of the disjuncts you want. So you can get A or you can get B from it. Well, you get both, but you have to write them down separately.
So we'd say this is I for and elimination, and this also comes from line I for and elimination. So this is an acceptable rule. And introduction states that if you have three lines, I, J, and K, if you have A on one line, and B on another line, you can put them together to get A and B. So we have I and J, and this is an introduction. So every elimination rule has an introduction rule, so this is the opposite.
So if you have A and B, then you can get A and B. And finally, some last rules we're going to do today. is or introduction. If you have on line i some statement p, then on line j you can write p or anything. And this comes from i, and this is or introduction.
Or elimination is very difficult, so we're not going to do it in this video. But if you take a look at this, this line says that p is true. So we know that disjunctions are true if at least one of its disjuncts are true. So P is going to be true, so this sentence is also going to be true, no matter what you put there. So it's totally acceptable.
Biconditional elimination is sort of a tricky one. If we have A biconditional B, then what we really get is A arrow B and B arrow A. And biconditional introduction is really just the opposite way. So you can call them like this. elimination and introduction.
These aren't rules you commonly use. In fact, one given in the logic book that I like is that if you have a arrow double arrow b and you have a, then you get b. And I like this because both the truth values have to be exactly the same.
So this is also going to be acceptable for us. Similarly, if you have a biconditional b and you have not a, then you're going to get not b because the sign must be the same for both of these. And this is fine for me. You can call this biconditional elimination. Depending on your class, you might have to use specifically one of these, but for this video series I'm just going to be using both interchangeably.
They're both proven from each other, so it's not really necessary that I pick one or the other because both of them are valid. It's just depending on your professor, you might have to prove one or the other. Alright, let's do some examples.
We're given F and F or G arrow H, and we have to prove H, so let's set this up Fitch style. So we put a line on the left side, we number our lines, and we have to label each of our lines as justification of why it's there, because if we can't write why it's there, then why are we writing it? Okay, so What's the first thing we can do?
We're trying to get to H, so we take a look at what can possibly get us to H. And we see this line here, F or G arrow H. So we know we need to get an F or G in there. So what are we going to do?
Well, we use a rule we have with F, so we take F from the first line, and we just add OR. So on 1, we use OR introduction, which... is going to be this rule right here.
If we have P on one line, then on another line we can put P or Q. And those can be any letters you want. So, that is the first step. And on line 4, well, we know we have a rule called modus ponens, that if we have F or G, then we get H. We have F or G, therefore, we get H.
So, this would be lines 2 and 3, modus ponens. And this is the end of the proof, so we have proved H from it. Alright, let's try another one, a little bit harder.
So with these two, we want to prove not A and B or C. So this is a little bit crazy. I'm just going to write ASM on the top. I'd shorten it further, but I think for a YouTube tutorial, I'm going to refrain from that.
You might be able to guess why. So here's what we have. We have b biconditional, d biconditional, not a, and we have b and d.
So let's use and elimination first to get b and d on their own, because it's usually good to separate everything you can, so you can see what you can do with it. So this is going to be and elimination on 2, and this is going to be and elimination on 2. Now we have b biconditional, d biconditional, a. So with 1 and 3, we know that if b is true, then d biconditional not a has to be true as well.
So we're going to call this biconditional elimination. And we also have d true, which means that not a has to be true, using 4 and 5, biconditional elimination. So now we have...
not A, but we have to prove not A and B or C. So we have our not A, now we just need to get our B or C. How do we do that?
Well, we'll take a look at line number 3 where we have B, and we can use or introduction to get B or C, because that is a rule, and we are allowed to do that. And now, on line 8, we can conjoin the two. using AND introduction.
So we get NOT A AND B OR C. So this is lines six and seven with and introduction. So I know this might have been really fast if this was the first time you've ever seen this stuff because the rules came fast and furious. And I definitely beg of you to do a bunch of practice because practice is going to be the best thing you can do to learn these rules.
So... I'm going to give you a bunch of practice questions that you need to do. I'm not giving answers. I'm not going to do answers for these, because they do take a little bit.
But by doing this, you should be fine to do the next things, and you should get it. If you have any questions about the proofs I'm going to give you, they might be difficult. Okay, they might be difficult.
If you have any questions about them, please leave them in the comments. I will answer the questions about these proofs. When you practice them and you get to know them, these become very simple, but at first I know they're incredibly daunting.
So I need to let you loose on your own to try these, okay? So I know you don't want to, but you have to do it. So here we're given A arrow, B and not C.
We are given A and B, and I want you to prove not C. This one should be a little bit simpler. For number two, we are going to do not B arrow D and E. We're also going to give you A and not B and C. And we want you to prove E and D and not B and C.
Let's give you a few more because I do believe that practice is amazing. So here's a nice hard one. Okay, for number three, we're going to do a and not b, and a or not c, arrow d, and we are going to prove, what are we going to prove from this?
Let's do this real quick. We can get d, and we can get not b. That should be provable. And finally, let's give you a three-liner for what can we do here with this one.
Okay, we'll get not F and not G. Not G arrow H. H and not F is biconditionally equivalent to not I.
And... from this should be very easy to get H and not I. In fact, I'm pretty sure if you know the rules, then you should see pretty much as I was writing it what the logical conclusion was going to be from those.
So here's four practice questions. I encourage you to definitely take some time to do these. Write it out Fitch style with your numbers, your justifications, and...
In the next video, when we introduce some more challenging rules, it should not be a problem. So, I'll see you in that video.