Rules of Inference for Propositional Logic | Discrete Math

[00:00:01]in this video we are going to take a look at rules of inference for propositional logic so before we start talking about the different rules of inference first let's talk about what our purpose is our purpose is to create an argument or actually a valid argument where logic will hold so an argument is just a sequence of propositions oo propositions like P1 P2 Etc such that if P1 and P2 and P3 and all the way up to p n whatever that happens to be implies or if then Q so we call P1 P2 Etc the premises and we call Q the conclusion and if it's a valid argument a valid argument would mean that the premises imply oops the conclusion essentially we're saying if this is a taty it is a valid argument so if it is always true then it is a valid argument so let's take a look at our statement if it is raining I will need an umbrella then we say it is raining and let's talk about how we might write this using propositions so let's let is riging be represented by P therefore this is p and let's let I will need an umbrella be represented by q and here we have an if then statement even though I didn't write the N so let's talk about how we would write this my first statement says if p then Q my second statement says it is raining so that's P so we know in our first statement if P then Q would mean that if p is true therefore Q is true and then I tell you in the second line that P is true therefore what is my conclusion and again remember the three dots mean therefore so therefore we can say Q is true I will need an umbrella over the next several slides we're going to take a look at some different uh rules of inference that we're going to be using and I'm just going to introduce a lot of them to you and hopefully help them make sense to you so that when we use them you're just ready to go so we're just sort of building that toolkit for down the road the first um rule of inference is modus components and this should look familiar because we just did an example with the rain and the umbrella on the last slide so modus ponin says this if we have if P then q and then I tell you p is true the result is q and again this means therefore so those three dots mean therefore now again this is exactly what we just did if it rains then I'll need my umbrella it rains therefore I need my umbrella great so how am I going to write this in another way because on each of these we're going to look at how to write them as a tautology um and basically what we're going to do is we're going to say if this is true then that's my conclusion so how would I write all of that stuff on the top I would say if P then q and P so so I'm saying if this is true then Q is true so that's how I would write it as a tautology now let's take a look at modus tolins very similar the first statement is the same the second statement is not q and the result or conclusion is not P so again here are the premises and then of course our conclusion and then a lot of people struggle with this one just kind of making it make sense in their head but what I would encourage you to do is think about if P then q and know that I can write if P then Q as an equivalent statement as if not Q then not p and to me that makes a lot more sense because if not Q then not P looks exactly like modus ponents we're saying if something then something else then the first thing is true then the second thing is the result and that's exactly what modus tolin tells us now how would I write it as a tautology I would write just as I did before the premises as the If part of the implication [Music] so if p and Q I'm sorry if P then q and not Q if all of that then not p let's take a look at a few more rules of inference the first is the hypothetical syllogism and this should look pretty familiar to you because this is very similar to the transitive property the transitive property says if a implies B and B implies C then a implies C and that's exactly what this is saying it's saying if P implies Q so if it rains then I'll need an umbrella and then if Q implies something else so if I need an umbrella then maybe I should wear gashes then the conclusion is if P then r or if it rains then I should wear gashes so that's all it's telling us is that one implication essentially leads to another so how would I write that as a tautology again I'm writing my premises as if P then q and if Q then R then I'm saying if that's true then the result is if P then R hypothetical syllogism then we have the disjunctive syllogism again because this is a disjunction and we're saying P or q and then not P so we're saying P or Q occurred but it wasn't P therefore it was Q so again this one makes a heck of a lot of sense to me because if we're saying that P or Q must have occurred but P didn't occur it makes sense Q must have occurred so how would I write that then I would say P or q and not P implies Q the next two rules of inference are kind of of silly actually um but again we will use these quite often but the logic is very easy to follow on these the first one is addition and the uh rule for addition says P so p is true is what this is saying that's the premise is that P is true the conclusion is that P or Q is true well now this should make sense we know that when we're dealing with this disjunction with this or statement that that tells us that one or the other must be true or both and therefore it makes perfect sense that if P then P or Q which is how I would write that as a corresponding tipology so if P then P or Q is true which makes perfect sense simplification is the same thing but kind of backwards and notice here we're dealing with a conjunction we're dealing with and so the premise is that P and Q is true so let's remember that this tells us that both p and Q are true so the conclusion that tells us that Q is true is sort of a du and again I could have instead of using Q I could use P instead and it's the exact same rule so again how would I write that as a tautology p and Q so if p and and Q then P or if p and Q then Q both of those would be the same let's take a look at our last two rules the conjunction and the resolution now the conjunction is super straightforward and kind of silly um but really it's just a reminder conjunction which is of course what this is says the premises are that P is true and Q is true and because p is q and true is Q is true then p and Q is also true which again we kind of already knew but that's okay p and Q so if those are both true then p and Q the conjunction is true so pretty straightforward and kind of silly but it gives us a name to use when we're working with proofs and then of course the resolution now this one's probably the hardest one to get your mind around resolution is saying that not P or R is true and P or Q is true and if that's the case then either Q or R is true or both so let's think of it this way let's pretend not p is true so if not p is true then p is false now for both of statements to be true which is what the premise says that would mean q would have to be true and R could be true or false and we don't really care but because Q is true that would make this conclusion true because Q is true so let's now take a look at if I changed things up and I said P was true so not P was false so if not p is false that means R would have to be true for this to be true and then if R is true we don't really care if Q is true because down here I've got a true and therefore no matter what again using these premises and the conclusion we can see that resolution is a valid um a valid way of thinking so how would I write that as a topology I would say not P or r and P or Q so if that then Q or R so let's take a look at why we're learning about these what are these rules of inference for and they are so that we can build a valid argument and a valid argument says that we're going to be given some information we're going to be given the premise and it might be more than one premise and we need to use those laws to show that some conclusion is true based on the premise and based on the law so before we look at this one specifically let's look at just the general the general case we start with some reason here and anything that goes here is going to be a true statement and then anything that goes here is going to be a reason so it's going to be like a two column proof and this typically the first one is a premise and then from then on these are going to be your rules of inference that we just learned and so I'm going to continue with steps and steps and steps until I get to whatever my final step is and my final step is going to be my conclusion statement and the reason again will be some rule of inference and that's how we're going to build a valid argument is we're going to say okay this is true because they told me it was true and then all of these other things are true because of the rules of inference and therefore this last thing is true and that's what I wanted to prove was true so let's put that into action then if I were doing this particular question I would first write p and if P then Q because I always started out with a premise because how else am I going to start I'm going to start with something that I know is true so again p and if P then Q is true because they told me it was true from there I'm going to look at my rules of inference and think about the fact that I'm trying to get to the fact that Q is true well based on my premise I can say that P is true and how can I say that P is true we have a rule or a um rule of inference called simplification and that simplification rule says that if you have if P then Q is I'm sorry if p and Q then p and it also says if p and Q then Q basically saying if you've got p and Q are true then p is true and P and and Q are true then Q is true so I can say simplification on one so I'm saying here's my first statement I'm simplifying that to say p is true and I'm going to simplify that to say if P then Q is true so same reason simplification on one now that seems silly because I didn't really do anything I just said two separate statements but that's exactly what this whole process is about I'm saying hey guess what this is true because I can simplify my first statement this is true because I can simplify my first statement my final conclusion is that therefore Q is true and you might be saying hold up you didn't really do anything how did you show that Q is true well we have a rule called modus ponin and if you'll recall and I'm going to say on 2 and three before I forget and if you'll recall modus ponents tells us that if we have if P then q and P therefore q and that's exactly what I have here I have if P then q and I have p and therefore Q is true so this is how a valid argument works I started with a premise that I knew was true because they told me it was I used my rules of reference and I got down to my conclusion so again here is a premise here's my conclusion I've shown that that is a valid conclusion let's try another example and this one is going to be harder because we don't know what the propositions are um in the last one it was sort of defined for us and now we have to Define them ourselves which is fine it's just one extra step so here's how I would get started it says we're using the rules of inference to show that the premise says John works hard okay so as I'm reading it I'm just going to get started for assigning so I'm going to say that P represents John Works heart uh another premise is if Jon works hard then he isn't having any fun so I'm going to let Q represent John is having fun because I can always negate that when I'm writing the actual proposition and then if JN isn't having any fun then he won't make any friends so R is going to be John is making friends so this is something you would definitely want to do before you get started on any sort of logical argument we need to know what PQ andr represent the other thing I would do before I get started is to write down the premises oops p r e m i s e s premises so the premises are those first three statements the premises are one John works hard so how could I write that John I'm not going to number them or it might get confusing when we do our actual proof so John works hard is just P two if JN works hard then he isn't having any fun so isn't having fun so if JN works hard which is p if then that's an implication then he isn't having any fun Jon is having fun is Q so it's not q and then three if Jon isn't having any fun so not Q Jon is not having fun then he won't make any friends so that would be not R so these are all premises I can use in my argument and you'll notice I'm maybe not just going to frontload them so a lot of people like to frontload them and by that I mean they're just going to write all of those things at the beginning I don't do that because I'm going to write them as I need them now the last thing I'm going to do before I get started is I'm going to go ahead and take a look at the conclusion Jon will not make any friends so my conclusion should be not R now it's good to know all of that that before I get started because then I know what I what I know I know what I know and I know what I'm trying to get to so let's get started now that we are ready so we had to do a lot of steps to get ready but now we're ready so let's go step number one again my first step is really always going to be a premise so here I'm going to say p because it's a premise I'm also going to say if P then not Q which is a premise from here I'm going to use a law so notice I've used this guy and I've used this guy I haven't used the last one yet and that's okay because what I'm doing is I'm saying here's two things that I know to be true and then here's some conclusion so if I know if P then not Q and P is true then not Q is true and that's our good old modus ponents and again whenever I'm doing a law like that a rule of inference I'm going to give the numbers of the statements that I used so I used the first and the second statement to say that the third statement was true not Q from there I'm now going to say say hey guess what if not Q then not R and this was a premise so now I've used that last premise but notice I didn't put it at the beginning I didn't use it until I was ready to because now what I can say is if I have if not Q then not R and I know not Q is true yep that's right I can say not R is true and the reason I can say not R is true is modus ponents on three and four and again that's exactly where I was trying to get to is that not R was true all right I hope you are ready for this one because this one is going to be a bit of a doozy here we are going to show that the argument with the premises P if p and t then r or S if Q then U and T U implies P not s q these are all premises that those will lead to the conclusion that if Q then R is valid so I know when I start a question like this it's a little bit overwhelming what do I know what do I not know what do I what am I trying to get to so of course of course what I'm trying to get to is my conclusion here's where I'm trying to get and I've got one 2 3 4 five premises so right away we know we're going to have quite a few steps in this logical argument so let's get started together and see how it goes I'm going to start with one and one I'm just going to say Q so Q is true because it's a so what else can I say well I'm going to say if Q then U and T again a premise I'm going to move these over a little bit just because I haven't given myself a ton of room so premise and premise so that's this premise and this present premise I've used both now why would I use both of those well because I know that if Q then U and T is true then and Q is true therefore U and T is true so how do I know that yeah that's right modus ponin on one and two so how does that help me well let's let's think about what I can do next if I know that U and T are true then I should be able to say that U is true and I should be able to say that t is true and I can do that by simplification on three same here so now what well I'm probably going to take a look at another premise now because I've sort of gotten to the end of what I can say so far and I have one that says if you then P so let's do that next if you then p and that's a premise now why would I need to know that well if I have if you then p and U is true then my next step should be that P is true and why is that true that's modus ponents on five I'm sorry four and six so p is true now think about what I haven't used yet in my premises I've got p and t well I just showed that P is true over here on step five I showed T was true so step eight is going to be p and t uh I don't really need the parentheses but you can have them if you want either way so p and t and how am I able to show that that's a conjunction of five and seven so now that I've shown p and t then I can say this premise so I'm just going to recopy that premise if p and t then r or S and that's a premise and then for 10 I'm going to say hey guess what r or S is true how do I know r or S is true modus ponents on uh n eight and nine my pen stopped working for a second eight and nine all right so I'm getting close I'm trying to say if Q then R and remember I started with q and my very last step should then be R so 11 is again the last premise that I haven't used not s which is a premise then 12 would be remember this one is saying r or S is true and then it says guess what s isn't true so what does that tell me that tells me R must be true and that is the disjunctive syllogism on 10 and 11 now it's okay for me to stop right here because I have shown that if Q based on all of the steps here then are if you'll notice none of the examples that we went through in this video dealt with statements that involved quantifiers so that's what we're going to look at next is simp similar to what we just learned but we're going to deal with Quantified statements