Maths for Programmers Tutorial - Full Course on Sets and Logic

Key Takeaways

hello world shawn grooms here with free codecamp and in this video i will be giving you three tips on how to learn discrete mathematics the first tip is to stay calm people often hear the word mathematics and panic and when you panic you stop listening and if you stop listening you can't learn the material so if you simply stay calm then you will be able to learn the material better you aren't being graded on the subject so there's no need to panic the second is to rewind you can rewind the videos at any time and when i learned discrete mathematics i didn't have this opportunity so in theory you should be able to learn the material much faster than i was ever able to so i strongly encourage rewinding videos finally explain once you think you understand the material of the videos you can try to explain the material out loud either to yourself or to a friend if no one's around or you feel weird talking to yourself then you can try to explain it to robert ducky there is a concept in programming called rubber duct debugging which is where programmers go through their code line by line trying to identify bugs in their code by explaining it to a rubber ducky so similarly if you go through the material of the videos subject by subject you will soon be able to identify any gaps in your understanding of the material in this video i'll be explaining what discrete mathematics is and why it's important for the field of computer science and programming discrete mathematics is a branch of mathematics that deals with discrete or finite sets of elements rather than continuous or infinite sets of elements imagine trying to run a program that requires an infinite number of executions to complete a task it's obvious to say that the program would run forever and the task would never be completed because there are an infinite number of executions in order to avoid this problem we approximate the continuous sets with discrete sets now you may be thinking i never use math that involves infinite sets but i promise that you do the simplest example is with a circle a circle by definition is an infinite number of points equidistant from a fixed point and the problem with this is that if we try to write a program that prints out all of these points it will run forever because they're an infinite number of points and therefore an infinite number of executions so this is physically impossible that's why if we zoom in here you can see that the when you come down to here there are all these points but in reality we should have even more points between these points and then if we zoom in on those we'll have more points between those points and we can never complete the task now we've all seen circles on computers so what's going on how is this possible we just established that it's impossible well the answer is that they're approximations for example consider regular polygons regular polygons like a triangle or a square or a pentagon those don't really look like circles but if you keep increasing the number of vertices eventually you'll start getting hexagons octagons dodecagons hexadecagons icosagons you can see that these regular polygons the more and more you keep increasing the number of vertices which the vertices are equidistant from a fixed point they will eventually approximate a circle eventually they will be indistinguishable to the naked eye and will look identical to a circle and in this video i'll be explaining what sets are a set is a collection of distinct objects called elements or members an element is essentially anything you want it to be and for example elements could be numbers letters variables more sets or nothing at all sets are usually denoted by capital letters such as capital a capital b c e or f and we say that the set contains elements for example we could say that the set a equals the set containing the element 5. or we can say that 5 is an element of a now i will be introducing a lot of symbols like this this just means is an element of and it'll save us a lot of time in future videos and i don't have to write out is an element of each time so that'll come in handy so what does the set actually look like well there are two common types of notation for sets and the one i'm introducing in this video is roster notation and it looks like this it's just curly braces with elements inside separated by commas which is very similar to javascript the only difference being that in math we use curly braces and in javascript we use a square bracket so now let's just walk through these so the uh the set a equals the set containing the element five that's how you would read this the set b equals the set containing elements two three and four the set c equals the set containing elements d f and g now d f and g they're not they don't have to be variables they're they're either variables or they could be characters it just depends on the context the set e it contains no elements in this case which has an impact that you'll see in future videos and finally the set f equals the set containing elements a b and c in this case our elements are sets so we would read this as f equals the set containing the set containing the element five the set containing elements two three and four and the set containing d f and g so in the next video i'll be going over a different form of set notation in addition to introducing you to some common sense and this will set us up eventually my goal is to bring us up to being able to define and understand algorithms and this is where we have to begin in this video i'll be introducing interval notation and talk about some common sets this will lay the foundation for the next video on set builder notation the beauty of interval notation is that it allows us to efficiently describe all numbers between two values suppose we wanted to say that the variable x is between 0 and 1 well we could do just that we could say that x is an element of 0 the interval 0 to 1 or which is really saying x is greater than 0 and x is less than 1. likewise if we wanted to say that x is greater than or equal to zero and x is less than one then we have to switch this to a square bracket all we're doing is we're now including the number zero in the interval also we can include zero and we can also include one in the interval by using square brackets on both sides so it's greater than or equal to and less than or equal to and now i'll talk about some common sets the first one being the null set which is the same thing as the empty set which is just there are no elements contained within the set and this will come in handy uh in the future the funny end here is the natural numbers which is the set containing elements one two three and then these three dots here are called an ellipsis which tells us that the pattern continues so n is the set containing 1 2 3 4 5 6 7 all the way up to infinity this funny n with a zero is the natural numbers however it includes the value zero within the set so it's zero one two and then the ellipsis tells us all the way to infinity in an integer fashion zero one two three four 5 6 and finally we have all of the integers positive and negative and non-negative which is 0 negative 1 negative 2 all the way down to negative infinity and 0 1 2 3 4 all the way up to infinity in this video i'll be introducing the rational numbers and set builder notation the rational numbers are defined as a ratio of two integers and examples include the integers themselves uh terminating decimals and repeating decimals so let's start with uh repeating decimals if we let 10x equal 9.999 repeating then if we divide by both sides by 10 then x equals 0.999 repeating and if we subtract x from 10x we have 9x equals 9. and then divide both sides by 9 we have x equals 1. and then if we multiply by 10 both sides by 10 we have 10x equals 10. so now we have 10x equals 10 but 10x also equals 9.99 and repeating so we have now and these are in fact true 9.99 repeating equals 10. so we we can now express 10x as an integer which is a a rational number we can put 10 divided by 1 which is a ratio so another problem we have is terminating decimals if we have 2.78 equal to y then we can just easily say 278 divided by 100 equals y as well these are two integers and it's a it's another rational number so a convenient way to define these or is denoted with a q and this is called set builder notation we have the q equals the set containing elements a divided by b such that a and b are elements of the integers with the only condition that b cannot equal zero if you divide by zero uh it's it's undefined it doesn't mean anything so um if you're interested in that i recommend googling it i think it's interesting in this video i'll be giving an example of a non-rational number if the square root of 2 were a rational number then by definition it must be expressed as the ratio of two integers if we then square both sides we have two equals a squared divided by b squared if we multiply both sides by b squared we have 2b squared equals a squared and from this we know that a squared is even a squared is even because we have two times some integer which is b squared since a squared is even we know that a is even because a squared equals two times some integer the integer i chose was 2k squared that means that a times a can be expressed as 2k times 2k which is to say that a equals 2k i can now substitute 2 times 2k squared for a squared and that leaves us with b squared equals 2k squared once these twos cancel out now this also means that b squared is even because b squared equals 2 times some integer which is to say that b is also even following this same logic now if we go back to our original premise uh the square root of 2 equals a divided by b where a divided by b is an irreducible fraction but since a is an even number and b is also an even number we can express these numbers as 2k and 2l but these twos here will reduce meaning that we'll have the square root of 2 equals k divided by l but since this reduced since this is no longer explicitly represented as a divided by b and it reduced to k divided by l we know that we do not have a rational number now there's a more specific way to define these numbers or classify these numbers but we need set operators in the next video in this video i'll be defining four binary operators for sets i've defined two sets a and b to help give some examples so the first is a union b which equals a set containing elements p such that p is an element of a or p is an element of b the next is the intersection a intersection b equals the set containing elements p such that p is an element of a and p is an element of b the next is the set difference of a and b which equals the set containing p or elements p such that p is an element of a and p is not an element of b and finally we have the symmetric difference which is going to be very helpful when you actually complete the symmetric difference algorithm challenge so the symmetric difference of a and b equals the set difference of a and b union with the set difference of b and a and finally i will define the irrational numbers which i hinted to at the end of last video so the irrational numbers are simply the real number real numbers minus the rational numbers and that equals the irrational numbers in this video i will be using vent diagrams to give a graphical representation of the set operators we learned in the previous video so if you recall the definition of a union b you know that a union b equals the set containing elements x such that x is an element of a or x is an element of b so if we let this circle represent the set a and we let this circle represent the set b then that means that x can land anywhere in any of these circles which is why this right the entire region is shaded red we're saying that this red region represents all possible values of x and if we recall the definition of a of a intersection b that equals the set containing elements x such that x is an element of a and x is an element of b which is why the overlap where a and b overlap is is shaded red we're saying all possible values of x are this red region now the set difference of a and b equals the set containing elements x such that x is an element of a and x is also not an element of b which is why it's just this region here none of the elements are within b the set difference of b and a is the set containing elements x such that x is an element of b and x is not an element of a and finally the symmetric difference of a and b i defined as the union of a minus b and b minus a so we take uh this region in this region and we take the union of it which is why this is the resulting region there's no overlap between the two now this is a really good way to familiarize yourself with the concept of set operators however don't rely on it you should really focus on the definitions as it will help you out in the long term in this video i'll be introducing the concept of subsets and supersets the dots on the board here represent elements of a set the lines represent the sets themselves these lines have been labeled b a and u we can say that b is a subset of a because b contains because all elements of b are elements of a we can also say that b is a proper subset of a because all elements of b are elements of a and there are elements of a that are not within the set b we can also say that the set a is a superset of the set b because a contains all of the elements of b and being even more specific we can say that a is a proper superset of b because a contains all elements of b and there are elements of a that are not elements of b what we cannot say is that u is a proper subset of a although the circle here is bigger than a like it just takes up more space it doesn't contain any more elements so all the elements so u contains all elements of a however u does not contain any extra elements so u is a subset of a and a is actually a subset of u u is a superset of a and a is also a superset of u so the sets a and u in this case are actually equal in this video i'll be introducing the concept of the universal set and complements so i want to begin by talking about the universal set which is commonly referred to as the universe now the reason i use this fancy look in you here is that i was defining the universe which is to say the maximum boundaries of my set my biggest set everything outside of this blue circle here doesn't exist i mean it in terms of the sets nothing exists i don't even exist computer doesn't exist you don't exist but everything within it does so that's a very important key now if i don't define this if if i don't define my universal set then we just assume it to be the real numbers so if i just erase this then you know this will just be the real numbers which is we've talked about in previous videos so the other thing i want to talk about is complements so if i say if i'm looking for the complement of b and i'll i'll put a more formal definition of if i'm looking for the complement of b then it is everything that is not within b so all the elements not within b are going to be part of the c complement so in this case it would look like this if i just highlighted everything it would be everything within the universe still and then so that is the complement of b it's all the elements that are not in b so that's that's quite a bit of quite a bit i mean you've got one two three four five six seven so since this is the real numbers these little dots here would represent all the numbers all every single value rational irrational that are not within b so if this is one and two or better how about this this is the rational numbers and these are the integers so these would be everything outside of this would be the irrational numbers and the non-integer values in this video i'll be giving examples for subsets and supersets so if you look at this blue line here this represents our universal set uh we've defined it to be the integers from 1 to 11. that's 1 2 3 4 all the way up to 11. don't let it concern you that there are elements outside of our universe um that just means that they are i mean that just means they're not in the universe that we have in question right now so it's no different than having stars outside of your galaxy you're not concerned by that it's just a matter of fact so if you look at this green line uh what what set would that be well it can say it's elements three beta and gamma so does b b contains three beta and gamma so this would be the set b likewise this set here it contains elements three one and x well a contains three one and x so this is the set a and finally this set uh contains elements one and three this set contains elements one and three so this is the set c now what can be said about these sets well we have uh we can say that c is a subset of the universe because all elements of c are elements of the universe furthermore we can say that uh the set b is not a subset of the universe because there are elements of b that are not within the universe also we can say that the universe is not a subset a superset of a because there's elements of a that are not within or not contained by the universe and finally we can say that the universe is a proper superset of c because the universe contains all elements of c except and there are elements within the universe that are not within the set c so if we wanted to be more specific we could actually say that c is a proper subset of the universe in this video i'll be going over examples of complements so in this video i've defined the universe to be the integers one through five and it's denoted graphically by this blue line and if we recall the definition of uh the complements with or with regards to a we have a complement equals the set containing elements x such that x is an element of the universe and x is not an element of a so in that case we can look at uh all the integers one through five and if it contains any element from a we throw it out so in this case if we look at the integer 1 we know that that's not going to be there because that's an a if we look at the integer 2 that'll be in our set if we look at the integer 3 that won't be in our set because that's also an a and then 4 and 5 are within the universe and they're not with an a next we have b complement well we know that one two four and five are within the universe and they're not within uh b and lastly we have c complement two four and five are within the universe and they're not within c because we had to exclude one and three i want to begin this video by reviewing our definitions of the union and intersection after that i'll be introducing two algebraic laws for sets so the definition of a union b equals set containing elements x such that x is an element of a or x is an element of b also a intersection b is defined as the set containing elements x such that x is an element of a and x is an element of b so when i introduce the importance law it should be clear that a union a equals a because a union a is defined as the set containing elements x such that x is an element of a or x is an element of a which should yield or you should see why that equals the set a also a intersection a equals the set containing elements x such that x is an element of a and x is an element of a which it should also be clear why that is the set a next we have our identity laws so identity laws are laws where we have a given set and we're performing an operation on that set with a given element uh these elements are the identity elements so for this case we have the null set and the universal center are identity elements so a union null set equals a and by definition that means that a union null set equals the set containing elements x such that x is an element of a or x is an element of the null set but since we know that the null set is empty we can't possibly have any elements in there so it's really saying that a union the null set is equal to the set containing elements x such that x is an element of a or more simply it equals a i want to begin this video by reviewing the definition of complements so the definition of a complement of a set for for instance the complement of a equals the set containing elements x such that x is not an element of a i will now be going over two new algebraic laws for sets the first are the law of complements the law of complements states that if we take the union of a set and its complement it equals the universe or if you take the complement of the null set it equals the universe furthermore uh the intersection of a set and its complement is the null set and that should be clear because if you have uh the set a and you are intersecting it with everything that is not inside a there's clearly not going to be any overlap so you're going to have an empty set the next one is the law of involution so involution states that if we have a uh state here let's call it state zero and we feed that state to a function in this case we're going to feed it to the complement function then when it gets to state one if we again feed it through the exact same function the complement function it will result in state 0 again in this case if we fed state if we fed set a through this cyclical function here then we would have a feed it through a complement we get a complement feed it back through the function we get a complement complement which equals a and then we can have a complement complement complement which would be a complement and then you get the idea it's cyclical in this video i'm introducing two more algebraic laws for sets associativity and commutativity associativity is uh essentially just saying that we can regroup uh the sets that we are talking about so um a intersection b intersection c that is a intersecting with the set b intersection c is equal to the set a intersection b intersection c and if you look at the definitions of uh intersection you can actually go through and figure out why this is and i'm pretty sure you'll be able to do that based on the videos that uh you've already watched and the same is true for the union uh commutativity is essentially just saying that we can um switch which side our sets are relative to the the operation so a intersection b is the same thing as b intersection a and the same thing is a union b is equal to b union a so if we look at the actual definition we have a intersection b is defined as the set containing elements x such that x is an element of a and x is an element of b and that's going to equal the set containing elements x such that x is an element of b and x is an element of a so if you just look at these uh the conditions for these for the set builder notation here it's essentially just a uh argument of grammar at this point so uh basic english will tell you that you can just switch which side that you have these on in this video i'll be introducing another algebraic law of sets the distributive law the distributive law is simply saying that the set and operation will be distributed over another set in operation for instance a intersection b union c equals a intersection b union a intersection c so i thought it might be helpful to use uh venn diagrams for the conceptual idea of this and then i'll do a separate video on the actual definition so if we look at a here and we separate a and then we decide to separate b union c then when we actually go to find the union or the intersection of these two regions it's easy to see that it is this region so hopefully for the purposes of equality this region here will match this region here so let's get right to it we have a intersection b so we have the set a and the set b so that means that a intersection b is going to be this region here and we have to also find a intersection c so that's this region and if we take the union of those two regions then we're left with all this jazz so it looks like they are in fact equal but to be more rigorous we'll revisit the actual definition of the intersection in the unions in the next video in my previous video on subsets and supersets i stated that to show equality you have to prove that each side of an equation are are subsets of each other so to prove the distributive law we're going to have this video we're going to have the next video in this video i'm going to be showing that a is a a intersection b union c is a subset of a intersection b union a intersection c so let's start the proof suppose that x is an element of a intersection b union c then x is an element of a and x is an element of b union c by definition of the intersection so we still know that x is an element of a and by definition we know that x is an element of b or x is an element of c from this we can deduce that x is x is an element of a and x is an element of b or x is an element of a and x is an element of c now by definition we can put this or rewrite this as x as an element of a intersection b or x is an element of a intersection c and finally we can deduce that x is an element of a intersection b union a intersection c so there you have it we've shown that since x is an element of a intersection b union c and x is an element of a intersection b union a intersection c x is in both of these and therefore a intersection b union c is in fact a subset of a intersection b union a intersection c in this video i have the proof of the second case for the distributive law in this case we're showing that a intersection b union a intersection c is a subset of a intersection b union c so let's start by saying that suppose that x is an element of a intersection b union a intersection c then we know that x is an element of a intersection b or x is an element of a intersection c and we know this because of the definition of the union from here we can then state that x is an element of a and x is an element of b or x is an element of a and x is an element of c from that we can deduce that x is an element of a and x is an element of b or x is an element of c and here we um we sort of factored out the x as an element of a and and then regrouped x is element of b or x is an element of c and from here we can by definition right x is element of a and x is an element of b union c which finally we can state x's and elements of a intersection b union c which is what we wanted to show so there you have it we've proved that uh x is an element of both of these and therefore this is a subset of this and we've shown that both sides of the equation are subsets of each other and therefore the distributive law is in fact true it's proven this video i'll be going over an example of the distributive law so if you look at a intersection b unc that is supposed to equal a intersection b union a intersection c so if we can if we decompose this equation and look at uh let's start with a intersection b then that equals singleton 3 based off from these predetermined sets and then if we look at a intersection c that equals the set 1 3. so the union of these two is going to be the set containing elements 1 and 3. now if we look at b union c that equals the set containing elements 1 3 beta and gamma and if we take the intersection of that set with a we're left with a set containing elements one and three which is good because now we've shown that this is equal to that now if we look at a union b intersection c that's supposed to equal a union b intersection a union c so if we analyze b intersection c that equals singleton 3 and then a union b right here equals 1 3 x beta gamma and a union c equals the set containing elements 1 3 and x so when we take the intersection of these two sets we're left with the set containing elements 1 3 and x and when we take the union of b intersection c with a we're left with the second containing elements 1 3 and x which is exactly what we wanted so yeah we've shown that these are in fact true in this video i'll be introducing the very last algebraic law of sets known as de morgan's law de morgan's law was founded by augustus de morgan and it states that the complement of a union is the intersection of the complements or it says that the complement of the intersection is the union of the complements so we're going to prove that the uh complement of the union of a and b is is in fact equal to the uh complement of a intersected with the complement of b so to do this we have to show that the complement of a union b is a subset of a complement intersection b complement and vice versa so let's get started suppose that x is an element of a union b complement if that's the case then by definition x is not an element of a union b and if x is not an element of a union b that is if x is not an element of the region a union b which is the red here then surely x is not an element of a and x is not an element of b and if that's the case then by definition x is not an element of a complement and x is not an element of b complement therefore x is not an element of a complement intersection b complement so if we go to the other side here we start by saying let's let's suppose that x is an element of a complement intersection b complement then by definition x is an element of a complement and x is element of b complement by definition of the complements x is not an element of a and x is not an element of b and with the same logic x is not an element of a union b because x is not an element of this region and x is not an element of this region so surely it's not an element of the two regions combined and by definition of complements x is an element of a union b complement in this video in this video i'll be giving examples of de morgan's law de morgan's law states that the complement of the intersection equals the union of the complements and that the complement of the union equals the intersection of the complements so if we check out these new uh this new universal set here it is equal to the set containing integers such that x is greater than or equal to zero and x is less than or equal to five or more simply the universe equals the set containing integers from 0 to 5. so if we decompose our first equation a intersection b equals singleton 3 the complement of a intersection b is going to be integers from 0 to 5 excluding a intersection b so 0 1 2 4 and 5. now the complement of a is equal to 2 four and five because a contains the integers one and three so those are excluded and b complement is going to be equal to zero one two four five because b contains three so it's excluded so the intersection or the union rather of a complement in b complement equals 0 1 2 4 and 5 which is in fact equal to the complement of a intersection b which is what we wanted so the next equation we have a union b and that's equal to 1 3 x beta gamma now the complement of that is equal to 0 2 4 5 because we've excluded everything from uh a union b and now if we look at a complement intersection b complement we also have the set containing elements zero two four and five so which is exactly what we wanted so now we know that these two are equal so there you have it both of our equations worked out and we can happily use de morgan's law in this video i'll be explaining what logic is and why we need it i want to begin with an excerpt from the book of proof by richard hammack this is a free textbook and it's excellent you can find it online and it covers all foundational mathematics to include uh discrete mathematics and i i cannot recommend it enough so the excerpt is logic is a systematic way of thinking that allows us to deduce new information from old information and to parse the meaning of sentences so what this is saying is that essentially with without logic we wouldn't be able to deduce or move from point a to point b and or make claims from point a to point b in a hundred percent affirmative uh no questions asked way and uh so that so that's very important for mathematics if you couldn't do that in mathematics then um it would all fall apart you there there would be no certainty there would be no foundation no argument for us to stand on and we would just be a bunch of people throwing numbers about and making guesses essentially so it's very very important uh the parsing the other part of the quote to parse the meaning of sentences won't make sense until later videos when we actually um do that so just bear with me on that one so why should you care about programmers so well programmers use algorithms or well programmers write code first of all code uses algorithms algorithms is essentially just math and mathematics requires logic so it's that simple in this video i'll be introducing the notion of a proposition a proposition is simply a declarative statement with a verifiable truth value they are usually denoted by lowercase letters so if we have this lowercase p equals rain falls from the sky now that's a true statement rain does fall from this guy but it could have been a false statement like q q equals ghana is a country in asia ghana is not a country in asia ghana is a country in africa so this is a false proposition or a false statement are what are you doing there's no truth value that can be assigned to that it's just it's just a question it's considered an open statement s equals wash the laundry again this is an open statement it has no truth value to it it's a command five equals four plus eighty nine uh that again that that that does actually have a uh truth value to it uh but it's again it's a false state because 5 does not equal 4 plus 89. 7 equals alpha i i don't know if it does i mean i've no i don't know what alpha is so this is an open statement um we can't verify the truth of this 3 equals 5 divided by 0. this is a proposition this is how this has a truth value because 3 does not equal 5 divided by 0. that's 5 divided by 0 is undefined and then 99 times one-third equals 33. so this does have a verify verifiable truth value and it's true in this video i'll be introducing the concept of composite propositions just like regular propositions composite propositions are declarative statements with a verifiable truth value composite propositions are made up of subpropositions and in this video we're going to talk about the conjunction and the disjunction so the first one i want to introduce is the conjunction that is p and q that's how you would read this p and q and so this composite proposition here is rain falls from the sky and ghana is a country in asia so the two subpropositions in this would be p p and q um and this has a verifiable truth value because rain falls from the sky because that is a true statement but the statement q ghana is a country in asia is false we have p and q we have true and false which means that it's false one of them is false and we'll talk about this more when we get into truth tables the next is the disjunction p or q that's read as or rain falls from the sky or ghana is a country in asia so again we have true or false this time so only one of these need to be true in order for everything to be true and therefore p or q is a true statement in this video i'll be introducing truth tables truth tables are the easiest way to visualize why something is true or false and they're really convenient when we start getting up into uh conjunctions and disjunctions so if you remember p and q p is defined as rain falls from the sky and q is ghana is a country in asia then p or q or both p and q have two possible values true or false they're primitive propositions so we just put them in a table true and false and then true or false but i i circled these because i know that p is true and i know that q is false but when i analyze a conjunction or disjunction i have to add two more rows to the truth table and that's because if you like if you imagine this as starting on a path here you can choose to go either true or false when it say i took true when i get to the end of that path i can then choose true or false again so i'm stuck with four different possibilities here the first one being true true true false and then false true and then false false so when i actually go to my table here i have true true true false and yada yada and then uh when i stick in my conjunction i have true and true equals true uh true and false equals false true false and true equals false and then false and false equals false p or q true or true equals true true or false equals true false or true equals true and false or false equals false and these are by the definitions of the conjunction and the disjunction that's why that's why these values take on true or false in this video i'll introduce our first two algebraic laws of logic in importance and identities these are the same laws we saw in set theory if you recall it impotence is when you can take a proposition and apply a binary operator to that proposition over and over and will never change the value of the original proposition for instance p is the logical equivalent that's what these mean the logical equivalent of p or p which is the logical equivalent of p and p and if you recall the definition of uh the disjunction and the conjunction you should be able to figure out why this occurs now the i identity law states that if we take a proposition and we have a conjunction with true a truth value a true value then it will always yield that original proposition likewise if we have a disjunction with a proposition and false it will always yield the original proposition that's why we have p is the logical equivalent of p or false which is the logical equivalent of p and true and uh finally we have uh true and false the identities of true and false so if you have the disjunction of true with any proposition then you will always yield a true value and if you have a conjunction with any proposition in false it will always yield the false value in this video i'll be introducing two more algebraic laws of logic the law of complements in the law of involution we start by examining our primitive proposition p we know that p either is true or false if we look at the negation of p which is read as not p then we know that p is false and true because not p is defined as when p is true not p is false and when p is false not p is true so the law of involution tells us that if we have a proposition and we feed it through a function twice we'll end up in the same spot so if we have proposition p starting at state zero feed it through a function the negation function it'll bring us to state one as not p if we feed not p through the function it'll bring us back to state zero which is p or known as not not p so uh p is logically equivalent to not not p that's what involution tells us we then analyze the law of complements which tells us that the uh disjunction of p and its negation not p will be the logical equivalent of the true value so it is a it is known as a tautology it is always true uh and that's the corresponding truth table here it also tells us that uh a proposition and the conjunction of its negation is always false which is known as a fallacy so you can go through this truth table and you'll see that we have a tautology fallacy tautology tautology fallacy and fallacy in this video i'll be introducing another algebraic law of logic commutative law so we start by looking at all possible cases of p and q we know that based on the path problem that we did when i first introduced truth tables we know that there's four possible cases for both the disjunction and the conjunction of p and q so if we analyze this we know that true and true for the disjunction of p and q is going to yield true and also this is going to be true and false yields true false and true yields true and false and falsies it's true so all we're doing for the commutative law is switching the order of q and p on the operation so instead of having p or q we have q or p so in fact we do have true true true faults so we've shown that both p or q and q or p are logically equivalent for the conjunction of p and q by definition we know that true and true is going to yield true true and false yields false false and true yields false and false and false yields false so when we commute p and q and we have q and p it's not surprising that we get the exact same answer which is good because now we've shown that p and q is logically equivalent to q and p in this video i'll be introducing the associative law and the distributive law for logic now previously we've only dealt with two primitive propositions so that's why we've only ever had four possible outcomes in our true or false path now we're going to take this a step further and we're going to have eight propositions or eight possible outcomes for our true or false path because we're dealing with three propositions p q and r so there's not much to be said about the uh associative law or the distributive law and unfortunately i can't fit the truth table to prove these on my white board it's it and it gets really messy so i'm gonna have them at the end of the video and go through them make sure you understand them and if you don't go back and review the concepts of truth tables in this video i'll be introducing our last algebraic law of logic de morgan's law de morgan's law states that the negation of the conjunction is the logical equivalent of the disjunction of the negations and also that the negation of the disjunction is the logical equivalent of the conjunction of the negations so if we look at our truth table i've decomposed our propositions here so that we have p not p q not q and i have it all out on the board so that i can just simply look at uh not p and q which is our first law and see that it is in fact equivalent to not p or not q so these two columns are equal so we can uh definitively say that these are logical equivalents also not p or q is the is in fact not p and not q based on our truth table it's 100 certain it's this is logic and there's uh no argument against it in this video i'll be introducing the notion of conditional statements a conditional statement contains a hypothesis and a conclusion these are more formally known as an antecedent and a consequent so all this is saying is that when we look at these the actual conditional this is the hypothesis and this is a conclusion so p implies this is read as p implies q and also as if p then q so p implies q is only false when a hypothesis leads to a a false conclusion or a uh antecedent leads to leads to a false consequence so that's why we have uh if we have true implies true that leads to a true statement and if we have true uh implies false that leads to a false statement these other three the converse inverse and contra contrapositive are uh essentially they're just common implications that we run into or common uh conditional statements that we run into and the converse is simply q implies p uh inverse is not p implies not q and not q implies not p is log which is contrapositive is logically equivalent to the original conditional statement in this video i'll be introducing the universal and existential quantifiers but first i have to introduce the propositional function the propositional function denoted p of x takes on a value of true or false but it takes on a value of true or false for everything that you feed to it so in this case with the universal quantifier this is read as for every you would say for every x that is an element of the universe p of x is either true or false for every x uh the shorthand for this is for every x p of x you could also say uh there exists that's the existential quantifier there exists is just stating that there is at least one so if we say there exists an uh there exists an x that is an element of the universe we're saying there is at least one x at least one x that is an element of the universe such that p of x is true or false and you can again use the shorthand uh there exists an x p of x so we look at these examples for every x that is an element of the naturals x plus 3 is greater than 4. so that is a that is a false statement because the first value of the natural numbers is 1 so x plus 3 is 4 which is not greater than 4. also for every x is an element of the real numbers x plus 3 is greater than 4. that is also false i can think of well there are infinitely many numbers that are not true for this and then in this case i said there does not exist an x that is now under the naturals such that x plus 3 is greater than 4. and that is also a false statement because if i let x equal 2 that 2 is a natural number and 2 plus 3 is greater than 4 so this is a false statement there exists an element of the real numbers such that x plus 3 is greater than 4. that is a true statement because any number greater than one is going to yield a true statement in this case in this video i'm going to be going over some examples of tautologies tautologies are simply propositions that are always true this first one is the law of excluded middle which is p or not p so for here we have p or not p so true or false true or false false or true or false are true which yields nothing but a true column next we have the law of contradiction so if you ignore this negation here in this column of trues here we have p and not p so true and false sealed false true and false yields false false and true false and true all yield false now when we actually apply this negation to the uh false column here that yields a column of truths so the law of contradiction is a tautology finally we have modus tollens modus tollens is p implies q and not q implies not p so let's break this down p implies q p implies q is only ever negative when the hypothesis predicts true and the conclusion is false so if we have uh true implies true here is going to be true true implies false that's false false implies true is going to be true false implies false that's also false i mean that's also true we then take this column and uh take a conjunction with not q so true and not false is going to yield false false and true is going to yield false again false and true is going to yield false and true and true is going to yield true so finally we take this column here and that is our we imply not p so this column implies not p so false implying not p is going to be true false implying false is going to be true false implying true is also true and true implying true is also true so there you have it we have this whole column here for modus tollens and that is therefore a tautology there's nothing special about these tautologies these are just examples of tautologies