Introduction to Propositional Logic in Discrete Math

A free video tutorial from Grant Hall
Credentialed Actuary and Dedicated Math Tutor
Rating: 4.2 out of 5Instructor rating
3 courses
13,801 students
Introduction to Propositional Logic

Learn more from the full course

Master Discrete Mathematics: Sets, Math Logic, and More

Master Discrete Mathematics: Learn and master all of Discrete Math - Logic, Set Theory, Combinatorics, Graph Theory, Etc

06:49:41 of on-demand video • Updated October 2020

Most Complete Course on Discrete Math offered on Udemy
Fully Understand Mathematical Logic
Grasp the Complex Topic of Counting for Advanced Mathematics
Know When to Use Combinations or Permutations
Solve Real World Problems Using Combinations and Permutations
Discover How to Solve Mathematical Proofs Using a Variety of Methods
Learn Mathematical Notation to be able to Understand Complex Proofs
English [Auto]
Hello and welcome to today's video, we're going to do an introduction to propositional logic before we can really get started. We have to do some English stuff. We got to talk about what a proposition is. This is something I struggled with because I'm much more math oriented, not really English, but a proposition is just a declarative sentence that is either true or false. So it's just some sentence that has an inherent truth value. So it's not something like telling you someone someone to do the laundry. That's a command, but it's it's something that is either true or false. It's got to have some truth value. And some examples here, too, is less than four. That's true, right? Seven is greater than nine. That is obviously false. The world is centered around me. That's false, too. So we have this one true, false and false. These are these are preposition propositions because they have some inherent truth value. But now this one is do your homework. That's a command. And that is obviously not a proposition. So not a proposition. OK, so hopefully now you kind of understand at least what propositions are, because these are what we're going to be forming all of these logical statements with, it's kind of important to be able to tell what is a proposition and what isn't. So propositions in general are denoted with capital letters. So PKU and our common examples. So P might be able to eat McDonald's every night for a month. Q Might be. I will exercise. So that's the capital letters. These are these represent like certain propositions. So one could be two is less than four, something like that. Then lowercase letters P Q and are used for general propositions. They're almost like variables is what we use for proofs. So you're going to have a good mix of using the capitals. That's kind of when we're translating statements into propositions versus lowercase, which is just when we're doing proofs, when we're kind of learning the topics and doing truth tables. You'll hear about that later. That's when we'll be using lowercase. And we have to understand these things called connectives. And that's what we use to make compound propositions, which means basically a proposition that has more than one statement in it. So first one is negation. So if I write not P, it's kind of like the right angle symbol, like upside down. That means that it's just not P. So P whatever P is is not true. Right. Then we have conjunction. That's this symbol right here and that means P and Q So that's how you want to read it. And Q If you see that symbol, if you see the upside down one, so the V basically read that as P or Q And if you remember from our set theory we had we had like said, if we said A and B we would say A right there, and if we said A or B we would say A and then do A, you notice that these are almost the same because now it's P and Q versus P or Q, so I kind of think that if it's kind of opening up, then it's going to be or and if it's opening down then it's going to be. And so notice that these are pretty similar, just a way to remember it a little bit easier. OK, and then now we have this weird thing, it's kind of a circle with a plus sign in the middle and this is either P or Q, but not both. And this is kind of how you really need to think about the P or Q original. So just like sat there when we had A or B, remember that it also included the inside. So if we had two sets, A and B, and if we did A or B, A or B, we included everything. But what is exclusive or this new symbol is saying is that it means A or B, but not both. So it's saying, well, you can be here. This could be true. This could be true, but both can't be true. So that middle part's going to be excluded and that's that new symbol that we kind of showed here. So that's the we call that the exclusive or while the other one is inclusive or. All right. So the next one is the implication. We're going to have a separate video on this one, the arrow, because of how important it is. We'll have that later on. That means just if P, then. Q So that's how you want to read that. So when you see the arrow say then or that implies that Q happens then the bi conditional P if and only if. Q That's kind of like the implication going back and forth. So if P is true. Q Must be true and if Q is true, P must be true. And we'll talk about that later on in a separate video as well. I just want to give a quick introduction here. So now let's do some practice. So what we're going to do is we're going to have that. We have this statement here and we want to translate this into English. So this is a logical statement, but we want to get rid of that and get it into words. So these are our propositions. We have P Es. I will eat McDonald's every night for a month cuz I will exercise hours. I will be obese and acis I will go to the hospital. So obviously these are pretty crazy propositions, but they're interesting nonetheless. And now we want to see what, what the heck is this saying right here. So we need to take it apart step by step. So let's start with this one right here. We have P and not Q, right. Because that's how those are the symbols from these Conexion connectives. That's how we need to read it. P and not. Q And now I want to write that, I want to write P and not Q using my rules right here. So P is I will eat McDonald's for every day, for a month, every night for a month. I'm just putting that instead of p every night for one month. And then and because that's what this part is that's about and. So that's there and then is this whole thing here, so this to this is P and now what's this not the symbol to make this go to the and that's the end. And now the not symbol here. That just means. And I will not. Exercise, right, because not CU is exercise, CU is I exercise if I'm not exercising, I'm saying I'm writing that as I will not exercise. So that's the first part of our statement. So P and not Q It means I will eat McDonald's. I didn't even I didn't write that down. I will eat McDonald's every night for a month. I will eat McDonald's my bad there. I will eat McDonald's every night for a month and I will not exercise. OK, so now that's what the P and not Q part means. Now we were going to this next part, but before we do that, we need to obviously include the connective. I'm going to say I will eat McDonald's every night for a month and I will not exercise. And let's see what it says here. Says If P then. Q So we really want to say if let me write that here. If I, if I will not if I will eat McDonald's every night for a month and I will not exercise now we say then that's that implication there, that's the arrow. We say then now what happens. What's R and S or s then I will be obese or I will go to the hospital. Right. Because it's just a simple statement or. S then I will be obese or I will go to the hospital and notice that the or is not an exclusive or so or I will go to the hospital. Let's kind of take this apart and see what it means, like logically, if I will be obese or I will go to the hospital, note that it's the other symbol instead of this, that plus symbol, which means that I can be I can be obese and go to the hospital, too. So both of those things can happen at the same time. And if this actually happened, it might happen at the same time. So that is what this crazy statement means. Instead of doing the logical terms, that's what it means. And just in real life. So we say, if I will eat McDonald's, I'll just say if I eat McDonald's every night for a month and I don't exercise, don't exercise, then I will be obese or I will go to the hospital. And that's what that statement means in terms of real words. So hopefully that makes sense. And now we're going to do another one here where we're going to translate the sentence into propositional logic. So this one says if Bridgid doesn't study for her test, then she will not get into med school and her family will be sad. And so what we want to do is when I do statements, I like to make each one have kind of a positive connotation. So we have PKU and it looks like we have three statements here and now we need to make them. So what is going to be? Well, the first one I see is Bridgitte doesn't study for a test. I'm going to say British studies for a test. So first statement is Brigitte studies for her test. I don't like to have a negation already inside of my statement because I can easily enough add a negation. Said we're just studies for her test. All right, so what's the next proposition that we see then she will not get into med school, so she will get into med school is going to be my next one again, because I don't like to have negative ones. And Bridget will get into med school. And the last one is a little bit iffy, you could say so, obviously the last one is her family will be sad, but we can make this. We could make it, her family will be happy and we can make it not happy. But I would like to keep with what it says exactly. And I would like to say her family will be sad because that's not necessarily a negation. It's not like it's saying not happy. It's saying sad. So her family will be sad. I'll leave that as kind of even though it's negative, I'm going to leave that there because there's no negation implied her family will be sad. OK, so now what what our job is, is to turn this statement into kind of what we had here with this P and not Q, blah, blah, blah. We have to somehow turn it into that. So first thing I see is if Britain doesn't study for a test, then so that then I know is going to imply the arrow. So I'm going to have the arrow going here. But now then what's before the arrow. OK, so Bridget doesn't study for her test. Well P is Brigitte studies for her tests, so she doesn't study for her test. That's not P so now I'm saying OK, not P implies because that's the then I read that as implies so not P implies that. Now what, what do we have now. She will not get into med school. OK, so that's I'm going to put this in parentheses here. So that's not. Q Right. Because Q is Birgitt does get into med school so not. Q She doesn't get into med school and her family will be sad. It's not the end part is going to be this, that kind of upside down. V because that's our symbol for and we have that up here for our collective. OK, now the last part is and her family will be sad. Well the part that says her family was sad is are so it's and ah and that is our statement here. So we say not P implies not Q and R, and that's what this statement means. And hopefully that kind of makes sense. Hopefully you kind of seen it both ways. How we get from the logical statement to the words and how we get from the words to the logical statement. And these can be tough sometimes. So make sure you take time to practice this on your own. Let me know if you have any questions. And hopefully this is a good introduction to where we'll be going with logic. Have a good one.