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