Logical Equivalence (Powerful Techniques of Logic)

Video Series: Logic and Mathematical Proof (In-Depth Tutorials for Beginners)

(D4M) — Here is the video transcript for this video.

00:00
in this video i teach you logical equivalence what you’ll learn here are
powerful techniques of logic in logic and mathematics
statements are logically equivalent if they are provable under a set of axioms
or have the same truth value in every possible way so let’s see why this is so
powerful hi everyone welcome back i’m dave
this video logical equivalence powerful techniques of logic is part of the
series logic and mathematical proof in-depth tutorials for beginners
so let’s get started and see what we got going today
so first off i’m going to explain what is logical equivalence and then
how to verify logical equivalence um and then we’re going to talk about
some useful in uh logical equivalences um and so yeah let’s go ahead and get

00:01
started what is a logical equivalence so the link to the playlist is uh below
the link to the series is below in the description
and so this is uh after some videos that are explained what are logical
connectives what are some tautologies and so here we go in propositional logic
statements are called logical equivalent if they have the same meaning the same
semantic meaning so there and here’s the notation that
we’re going to use and they’re going to be a logical equivalent if they have the
same truth value for every possible choice of truth values
so another way to write this definition out
is using this symbol right here p and q are logically equivalent this means
means that p if and only if q is a tautology

00:02
and we know how to check if if uh if a statement like this is a statology we
can make a truth table for this and so if the
you can you can know these statements are logically equivalent means
p if and only if q is a tautology so we’ll be using this right here
in the following to verify some some logical equivalence is the tautology
but we’ll also talk a different way how showing uh how showing a logical
equivalence using only other logical equivalences so let’s get started
how to verify logical equivalence first and so here we go how to verify logical
equivalence so in this problem right here we have two logical equivalences
this statement is logically equivalent to this statement
and the way to do the way to verify that is to it’s one way is to construct the
truth table so i’m going to look at the truth table

00:03
uh involving p’s and q so we’re gonna have p and q so true false true false
true true false false and then we’re going to have a p implies a q
let’s make that column and then we have a not p
so we can make that not p right here and then we’ll have a not p or q right here
and then the last column will be the statement on the left this one right here
if and only if the statement right here so here we go p implies q
if and only if not p or q and this is a nice uh logical equivalence
uh we’re going to fill it out and verify it but this is a very nice logical
equivalence that we’ll use later on but here we go so p implies cq so true
implies a true this is false and then true and then
true and then not p is false false true true

00:04
and now we have an or between uh these two columns right here this one and this
one so we have an or so we have a true false and then true true
and then now we have a uh equivalence okay so what what columns
are we’re looking at now um we’re looking at this column right here
and this column right here are these columns right here equivalent we can see
down here that they are true and true that’s the same false and false are the
same those are the same and those are the same so this right here is a tautology
and that means that this is an equivalence right here
so this is a tautology so we verified this equivalence right here so
these are logically equivalent statements and we can we can see that
right here in this table right here now we have the negation of p implies that q

00:05
is logical equivalent to p and not q we’re actually going to use both of
these later so let’s quickly verify this one right here also that this is a
logical equivalence right here so we still need the implies column
and now we need the not q column so let’s change this to not q
so here we have false true false true and then now what else do we need we
need the negation of this one here but let’s go ahead and remove those here
let’s so let’s do the negation of the implication here
so this would be false true false false and then we need p
and not q so p and not q and so that will be here um true these two columns here

00:06
with an and so false false and then now we need the [Music]
equivalent column here p and not q all right very good and they don’t match
here and they match everywhere else so what happened here
um we have an implication here and and so this should be false what about
this one p and not q so here’s not oh i didn’t do not q right
here so that should be a false uh this one didn’t have a not q so we
don’t need to go back and change it but this one right here so now we’re looking
at p and not q so that should be a false there
so now these match so now this is true this is the tautology so this is a
logical equivalence right here anywhere you have this right here you can replace
it with this right here this is these are logically equivalent to each other

00:07
right so verifying a logical equivalence is the same thing as making out a true
table so we did that twice here we did two examples there
all right so let’s go on to the next example um but before we do that though i
actually wanted to mention here there is something going on here that we
may or may not like so there’s of course an infinite number
of tautologies and logical equivalences however to
verify something’s the logical equivalence we have to check for tautology
now checking for a tautology is difficult because
depending upon the number of variables so if your statement has um two variables
then we have two to the two we have four rows
but if you have eight variables right then we have too many
so you know that’s just too many rows that’s equal to too many rows
and you might say well if you’re if you’re going to use computer then

00:08
it’s not too many rows yeah but it’s going to be easy to come up with
something that’s very interesting if you’re going to be using computers that
may have 80 variables in it and so then you would be using computer
and then you would not even be able to use a computer to check that many rows
so um exponential growth is you know not really great for uh computational
purposes not good at all so we need a practical
way of determining something a given statement is the tautology
whether they’re logical equivalent or not not necessarily by building out a
true table is there a better way that is the main point
so here we’re going we’re going to go with some useful logical equivalences
and so here’s the first one right here um commutative properties
and it’s saying that p and q is logically equivalent to q and p
and p or q is logically equivalent to q or p now you might have guessed these

00:09
are logical equivalences just just just by doing lots of truth
tables lots of examples but the goal here is to come up with
some very basic um logical equivalences and then use these basic logical
equivalences to build larger more complicated uh logical
equivalences without having to use a truth table so that’s one well that’s
one approach like i said at the beginning there’s two
approaches so let’s verify that this is a logical equivalence and i’ll leave
that over there for you to check let’s verify this one right here real quick so
p and q and then we have p and q and then we have q and p
and then we have p and q if and only if q and p and so to verify this logical

00:10
equivalence i just need true false true false true true true false false false
so the end will be true false false false and this end will be true false
false false and you see here they agree and so this is a tautology
so p and q is logically equivalent to q and p
all right and then you have the same result for the or here
so these are called the communicative properties now there are lots of
simple basic tautologies or logical equivalences that you want to know
the next one is the associative properties so if you have two ands right
next to each other right here we can move these parentheses over
and then this these two are logically equivalent to each other and then you
have the corresponding one for the or and we have the distributive property

00:11
also here so we have p and q or r so we can distribute the p
we’re going to keep the and so p and q and then now the symbol right here the
or and then p and r so this is similar to distributive we’re going to
talk about addition and multiplication and then you have the corresponding uh
one here when these symbols are reversed right here so this is a uh
logical equivalence also so to check this logical equivalence we would need
uh you know eight columns are sorry eight rows because we have three
variables here so we could check this as a logical
equivalence here i think i’ll check one more here for you and then leave the
rest for you so let’s just check this one here with eight so here’s go here
with p q and r we’re going to go true false true false true false true false
all right and so then we’re going to have true true false false true true

00:12
false false and then true true true true false for the remainder
and then now what do we need to build up we need a q or r
and then we need a p and that so before we build up the right hand
side here let’s go ahead and do these so q and r so i’m looking at an or right
here so i’m looking at true true true false true true true false
and then now for the and between these two columns here
so the and between the p and the q or the r so i’m looking at the and so i got a
true true true false false false false false
okay so far so good we have this part right here built up we have the p and
the qrr and now let’s work on this right here so we need a p

00:13
and a q right here we don’t have a p and eq yet so let’s do p and q right here
and then we’ll do p and r right here and then we’ll do the or between those two
columns so p p and q or the p and the r all right so good
so now we’re looking at p and q right here and we’re going to do the and so
i’m looking at the and down here so i’m looking at the true true false false
false false false false now the p and the r so true false true false
the rest are false so now i’m looking at the or between these two right here
between these two right here i’m looking at the or so we got true true true

00:14
and then the rest are false all right so very good so now to be a
logical equivalence i need these two columns right here to match
so to be a logical equivalence you need the this one right here what’s called q1
slot is uh if and only if q2 so here’s q1 and here’s q2
and as you can see they all match the first three are true and then the rest
are falses all these are falses here so these are all true down here
one two three four so that’s these are all true down here
you can just see that these are all true here okay so
that means we’ve shown that this distributive property right here this
logical equivalence right here and you can go do the same for the the

00:15
or the and here all right so now let’s look at uh some more
and so what’s the next one we got here so we have some ident potent properties
p or p is a logical equivalent to just p p and p is also logically equivalent to
p so these are called the idempotent properties
we have de morgan’s law we use these on a previous video and we showed these are
logical equivalent on their previous video so these are very important uh
properties right here and then we have the law of excluded middle
p or not p is a tautology and in fact we showed that one in the last video
and p and not p is a contradiction all right and so here’s some more and we
covered the contrapositive um in a previous video so if you haven’t
seen that i just want to refresh your memory and

00:16
an implication and the contrapositive um are logically equivalent um
that’s not the contrapositive though so this should say not q uh implies not p
and so let’s go verify this right here so we have p implies q
well actually we have p’s and q’s so true false true false true true false false
and then we need the negation so let’s say not p and not q so false false true
true false true false true and now we can build this implication
and let’s build this implication so p or q is true false true true
and then not q implies the not p so now i’m looking at this column right

00:17
here and not p so i’m looking at the implication this way so that’s true false
true and you can see these agree right here so this right here is a tautology
that’s a q not q so that one right there is agree here all the way across
they agree with equivalence so this is the tautology so this is an
equivalence right here and this equivalence right here is called the
contrapositive and you might want to check out that video
uh that’s part of the series a previous video in this series uh over the
contrapositive converse and inverse so that was just a typo there in any
case there’s the contrapositive and let’s see what’s next

00:18
so the converse and inverse here are logical equivalent
and so yeah so what i did was i mixed these up here um by accident so
definitely want to check out that video um on the contrapositive converse and
inverse so what should this right here be this so um actually this is the
converse and the inverse is the should be here the contrapositive of this not p
implies not q and so these are logically equivalent to
each other and we showed this in the that video there that you should check
out so i just want to refresh your memory that that video is there and

00:19
these statements right here that was not q implies not p for the contrapositive
all right so we also have these tautologies here and uh f is a
contradiction so if you have p or a tautology is a tautology if you have p
and a tautology it’s just p if you have p or a contradiction it’s just p
if you have p and a contradiction well that’s a contradiction
all right so we have all of these simple statements the ones on the previous
screen and the ones on the screen right here
and now we’re ready for a different kind of approach
so let’s see about this right here so here we’re going to go with
showing this logical equivalence equivalence right here two different
ways remember i promised you there was two different ways so one way is the

00:20
is the tautology way and we can do that really quick
um let’s see here we have p and q um let’s move these down here p and q and
then we have the if and only if and then we have the negation of the if
and only if and that’s the left hand side here and now we have the not q
and now we have the not q even if and only if p
so these will be the columns here true false true false true true false false
if and only if for the p and the q so this is true false false true
and then now let’s negate that so false true true false
and now let’s negate the q so false true false true now let’s negate or

00:21
do the negation between not q and p oh sorry not q and p
so let’s do the equivalence between not q and p and so now we’re looking here at
uh those don’t match so false these match true and these don’t match so false
and so what we can see is this column right here which is right here
is has the same truth values as this last column right here
so they’re both false they’re both true they’re both true they’re both false
so this is a logical equivalence right here
we could go make that last column if we wish so if and only if
not q if and only if p and these would be all truths true these match
true these match true these match true and so this

00:22
if and only if right here is a tautology meaning this statement right here is a
logical equivalence so that’s showing or verifying a logical
equivalence using a truth table just verifying the definition of logical
equivalence but there’s a better way there’s another way
now for this problem here because there’s only four variables this is
actually a very fast efficient way and we really don’t need another way if
if everything only had two variables in it so the way i’m about to show you is
very powerful when you have a large number of variables um
but but for this problem right here you know the truth table is actually very
short and quick but anyways what is the other method the other
method is to only use logical equivalences and to derive this so you
might want to think about it as like a trigonometric identity where you start
with one side and you keep manipulating it and then you end up with the other

00:23
side and the manipulations that you do will preserve the
logical equivalence so let’s see how that would work so i’m going to start
over here with this i’m going to start with not p if and only if q
and that’s going to be logically equivalent to not
now we know a logical equivalence for p if and only if q it’s p implies a q and
q implies a p so that’s a logical equivalent so the
logical equivalence that i’m using is i’ll just write it briefly over here
we’re using this logical equivalence right here that we already knew this is
p implies a q and q implies a p so we already knew
this uh logical equivalence here and if you don’t know that one you can
do a truth table on that but the idea is to derive this logical
equivalence using previously established logical equivalences we’ve already

00:24
previously established this one right here so we don’t need to do it we don’t
need to do a truth table again all right so now we’re going to do
the negation of an and and so we’ve already talked about the de
morgan’s law on the previous uh previous page here on this video i’m
going to got negate the first one so uh p implies the q negation or
and then negate the second one here q implies the p
so this is using the demorg de morgan’s law
in other words if you want to negate an and if i negate an and
that’s logically equivalent to [Music] this one right here
so that’s that’s the one i’m using right here this logical equivalence so i’m
writing the negation of an and so i’m going to negate this one or and then i’m
going to indicate this one right here all right so good

00:25
all right so next one we’re going to how do we negate an implication
so we talked about that in the previous slide to negated implication we can
change it to an and and now i’m going to negate this implication
and so that’s going to be not the q implies a p so that’ll be q and not p
okay so that’s using a previously established logical equivalence on how
to negate an implication now i have nothing but uh ors and ands
and well i have some negations but i have some ores and ands here so i’m
going to use the distributive property here so i’m going to think about this as
like a q or r and a t so we can use the distributive property
here i’m using all this as a q or and then an r and a t

00:26
and so what did the distributive property say it says q or r
and then the and and then the q or t q or t
so this was a distributive property here so i’m going to use the distributive
property here now so we have all of this p and dot q or q
and then i have this end here now i’m going to distribute all this with the
or not p so p and not q or not p all right very good
so we kind of made it longer but now what can we do now we can use
distributive property again so now i’m going to do this or here

00:27
this or here i’m going to distribute on this side now so now i’m going to go to
p or q and then the and and then the not q for p and we still have the and
now i’m going to do the same thing on this side i’m going to do the not p and
distribute that so i’m going to get a p or not q or sorry p or not p
and then an and and then get a not q or not p okay so so far so good
but it’s turned out to be really long but some nice things happen here
what is the not q or p that’s the tautology right there

00:28
so we can write that out we had that on a previous slide also p or q
and a tautology and so that gets absorbed and so now we just have p or q
and then now we have and and then we have p or not p which is the
same thing that’s tautology and autology
gets absorbed so then we have an and and then just this part right here so not q
or not p and then now i’m going to um distribute this out again
uh actually no we’re going to change this to [Music] implications so p p or not
p or q sorry p or q we can change that to q or p
and we can change that to an implication so not q implies p

00:29
and we can change this to an implication also so this would be p and not q
so and so then we have not q implies p and p implies not q
and so that can be written right there as a uh by implication so not q implies p
and so that takes care of the whole statement there
the negation of the equivalence we used to use tautologies and we so we
started with the left-hand side and we get the right-hand side there not q if
and only if p and so we only use logical equivalences previously established
logical equivalences so this is one way this is another way
to generate a logical equivalence is starting on one side and then just
deriving using previously established logical equivalence you can get another

00:30
logical equivalence there so that’s pretty sweet i like that a lot
all right so if you have any uh questions or comments or ideas
let me know in the comments below this series a logic and mathematical
proof in-depth tutorials for beginners link below in the description and i want
to say thank you for watching and i’ll see you next time
if you like this video please press this
button and subscribe to my channel now i want to turn it over to you math can be
difficult because it requires time and energy to become skills i want you to
tell everyone what you do to succeed in your studies either way let us know what
you think in the comments

About The Author
Dave White Background Blue Shirt Squiggles Smile

David A. Smith (Dave)

Mathematics Educator

David A. Smith is the CEO and founder of Dave4Math. His background is in mathematics (B.S. & M.S. in Mathematics), computer science, and undergraduate teaching (15+ years). With extensive experience in higher education and a passion for learning, his professional and academic careers revolve around advancing knowledge for himself and others. His work helps others learn about subjects that can help them in their personal and professional lives.

Let's do some math together, today!

Contact us today.

Account

Affiliates

About Us

Blog

© 2022 DAVE4MATH.com

Privacy Policy | Terms of Service