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
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