Prove a Set of Connectives Is Functionally Complete

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

00:00
in this video you’ll learn how to prove a set of logical connectives is
functionally complete in the context of propositional logic
functionally complete sets of connectives are called expressively
adequate so how do we define this how do we know that our logical
connectives negation and or implication and equivalence can express what we need
let’s find out hi everyone welcome back i’m dave
this video prove a set of connectives is functionally complete
is part of the series logic and mathematical proof
in-depth tutorials for beginners and so let’s see what we’re going to
cover today so what does functionally complete mean
and then we’re going to talk about these three connectors right here and we’re
going to show that these three connectives are actually functionally complete
and then we’re going to ask the question can only two logical connectives be

00:01
functionally complete so number two will
show that these three are and then we’ll ask this question can can we find only
two of them that are logically complete and then the last question we’ll try to
answer is can only one logical connective be functionally complete
and so let’s go ahead and get started so what does functionally complete mean
let’s see a good uh unjust let’s get a good understanding of this
so here’s our definition of what functionally complete means
a set of logical connectives is called functionally complete if every boolean
expression is equivalent to one involving only these connectives so
if you can have a collection of logical connectives and
you have to be equivalent to only one of these
so we’re going to show right now that these five right here are functionally
complete and these are the five we use in everyday mathematics negation and or

00:02
implication and uh equivalence here so here’s how we can do that
so we need to look at every boolean expression right and so we’re going to
be looking at all these possible uh truth uh values outcomes here
so i’m going to be looking at these um [Music]
logical connectives here and they’re binary right so i need two variables so
i need p and q and here’s all possible possibilities for p and q true false
true false and then we have true true false false
and then i wrote the negations here negation of p and negation of q
okay so this is just the possibilities right here and then we have the same
thing down here for this table also the same same p’s and q’s here now
when you have two variables there’s only four possibilities um
you know four rows are going to be needed but there’s going to be 16
possibilities so four rows 16 possibilities so how do we get all 16

00:03
possibilities so the way i’m going to do this is i’m going to go um
all trues and then all falses in the first row and then i’ll repeat that all
trues and all falses and i’m going to go true false true
false true false true false same thing down here true false true
false true false true false and i’m going to go with two truths two
falses and repeat that pattern and then repeat that pattern down here
and then now i’m going to have all trues all the way across
and all falses all the way across and so what we see here is these eight
columns right here and then eight more columns right here is all the boolean
expressions that we could have here’s one where they’re all true
here’s one we’re all false and because we have uh four possib uh
four rows here and each one has two choices true or false you know there’s

00:04
going to be 16 different possibilities so we have uh all 16 laid out right here
so here’s true false true true and there’s no other
uh column with true false true true this is the only one and we have true true
false true true false false true so there’s 16 possibilities
for bullying expressions here now how do we know that we can get all 16 of these
in fact how do we know we can get true true true true just involving these
logical connectives to one involving only these connectives right so
there’s actually infinitely many ways you could do that and i just chose one
of them right here p if and only if p that gives us the all trues
so for this column right here what could we put right here
um instead of p implies q to get true false true true there’s
actually infinitely many but all you need to do is come up with one so i came

00:05
up with p implies q that gives us the true false true true
how do i get true true false true from these logical connectives again
there’s infinitely many ways but i just chose one you just need to choose one
i chose p or not q and if you look at the p or not q over
here and you calculate that you do get true true false true
so the point is is that we’re able to look at all the boolean expression
possibilities even false true false false we can find an x we can find a
a statement a compound statement that only involves these connectives
right here so we’re going to call these functional these logical connectors
right here is functionally complete because every boolean expression no
matter which combination of trues and falses you have
is going to be equivalent to one statement all you need is one so i found

00:06
one in each of these columns right here and only involving these connectives
here so that’s how we know that it’s functionally complete
so now the question may arise are some of these logical connectives
redundant do we need do we need all of them
and so let’s try to answer that question now
so we’re going to say the connectives here negation or and and
are functionally complete so notice missing from this list right here is the
implication and the equivalence so how do we
show that this is true how do we show that without the implication and the
equivalence that we have functionally complete
so what we need to do is to make sure that we can get all possible 16 boolean
expressions possible but only this time using equivalence or an and and so what
we need to do is to find a way to rewrite the um any expression that has an

00:07
implication in it in terms of only these three right here and any expression
involving an equivalence to write it logically equivalent to only a statement
involving these three right here and so we’ve seen in previous videos
so by the way before i start solving this here um let me just mention that
this video is um the link to the series is below and so
we’ve covered uh you know these logical connectives in a previous video as well
as logical equivalence and the substitution rule and and other and other things
so anyways so in order to say uh p implies q
and write a logical equivalence for that
in fact we did this in our last video we found a an equivalence for implication
and we can use not p or q so this is a logical equivalence here

00:08
now the way you go do that is to show that this right here is a tautology
so this equivalence is a tautology so we can make the truth table for that and
what you’ll find out is that that’s a tautology again there was a video also
over uh looking at tautologies so the point is is that
when i see any equivalent when i see any implication i can rewrite that
implication and state logically equivalent to it so we’ll get the same
boolean expression but only using negation and or
and so that’s one of these three down here negation and or so i can rewrite
and replace any equivalence with this or right here not p or q what about the
equivalence p is equivalent to q can we rewrite this and stay logically
equivalent to it but only using these three right here and the answer is yes

00:09
because remember p if and only if q means p implies q and q implies p
and so we have an and down here and this is an and right here so that’s good but
we have an implication and an implication but we’ve already talked
about how to rewrite an implication with negation and or so we can rewrite this
implication right here so this implication can be written as not p or q
so not p or q and and this implication right here this one
is q is the hypothesis so this will be not q or p
and so here we have p is equivalent to q and now we only have negation ors and
ends so anytime we run into an implication whatever p and q are doesn’t
matter anytime we run into an implication we can rewrite it by putting

00:10
whatever p is here put it here and here and whatever q is put it here and here
and then we’ll have a logically equivalent statement but only involving
negation and ors and ands so in this sense this
connective right here is redundant and this connective right here is redundant
and another way of saying that is to say that these three right here are
functionally complete so that’s all we need to do
for this example here to show that these three are a lot are
functionally complete is to show that you can rewrite the other other
connectives in terms of these three only so let’s look at another example
or or the next part here which is a question can only two logical
connectives be functionally complete so this last example that we just did right
here was three one two and three can we can we redo this but only using two
so normally we’d have five one two three four and five so normal mathematical

00:11
discourse takes place with five logical connectives but actually these two are
redundant and we only need three and we can do all of propositional logic with
just three so now the question is can we do can we do classical propositional
logic with just two connectives let’s try to answer this question right here
so what we’re going to do is we’re going to say
can we just use negation and or do we need the and
and let’s see if we can do this here let me get rid of this um
so actually let’s leave this here and let’s just get rid of this one because
we have it right here actually let’s just leave it let’s just
leave all that there so here we can show how to get rid of the implication
in terms of the negation and or and how we can get rid of implication

00:12
and write it with negation and ors but we still have an and so how can we
rewrite an and and get rid of the and and only keep negation and or
so how can we rewrite an end and be logically equivalent to that
so here’s how we can do that we can say negation negation p and q
so this is a double negation so these are logical equivalent
now for this negation i’m going to apply it to the end
and i’m going to leave this negation alone let’s leave that negation alone
but now i’m going to apply de morgan’s law so what’s the negation of an and so
it’s going to be negation of p or negation of q
and now let’s see what we’ve done is we’ve taken any and and we can rewrite

00:13
it with only negations and ors so in fact we don’t need all five one two three
four and five we don’t need all five logical connectives in fact these three
right here you can say they’re redundant or another way of saying that is
these two right here these two logical connectives are functionally complete i
can get all 16 possible boolean expressions just using these two right
here and to do that you just replace implication with these two equivalence
with this and and with this and so all three of these right here only involve
the negation and or this only involves negation and or
only involves negation and or and the same thing there
so actually the ques the question is can we have only two logical connectives
and still and still be functionally complete and the answer is yes

00:14
now what was so special about getting rid of the and if you remember back
there were two de morgan’s laws and so actually we can switch this to an and
and we will still have functionally complete so now if i want to say
negation and and is functionally complete i need to show how to get rid
of ors so now let’s put an or here and now we have an or here
so p or q is equivalent logically equivalent to
the negation of the negation of the or now this negation i’m going to leave
alone right here but this negation i’m going to apply de morgan’s law also to
so if you don’t know what de morgan’s law is then you should look at the last
video over a logical equivalence where we work out de morgan’s laws so when i
apply the negation to an or i’m going to negate the negation here

00:15
i’m going to negate p here and it’s going to be an and and i’m going to negate q
so this is a way to get rid of ores i can rewrite any or and change it to a
negation and an and there’s nothing but negations and ends in in this statement
here so in fact any statement any any compound statement can be written only
with negation and ends i can get rid of implication
oh that doesn’t have a negation and an and in it so how would we write
implication well that has an or in it though and so
i can rewrite ors so i can rewrite this or right here this is one way to do it
so this is this is an or right here and so how do i rewrite an or so i’m going
to take the negation and put it here and put it here and here
and then i’m going to take the q so i can rewrite this implication as a negation
and i’m going to have negation of the p but i’m going to put a not p

00:16
so i’m going to have not not p which will just be p and and then we have the q
is right here so i’m going to have a not q and that’s actually a
logical equivalence that we talked about earlier in the last video
so i can write any implication now only using ends and negations any
implication with only negations and ands and
we can do the same thing for equivalence so right here it looks like i have some
ores but again we can rewrite this or only using negation and ends and we can
rewrite this or only using negation and ends
and so that will be an end of negations and ends so we can rewrite equivalence
only using negation and ands so there’s the idea behind showing that

00:17
negation and ends are logically uh functionally complete also okay so what about
if we have implication here how can we do this if we have implication here
so let’s look at that real quick okay so now i want to get rid of the ends and
the ores and the equivalents and so the way i’m going to do that is
i’m going to say p and q is logically equivalent to
the negation of p implies a q so it’s going to be the negation of
p implies not q and so this will be how to take any and
and write it only with negation and implication and we can check that this
is logical equivalent just for the sake of of clarity let’s go ahead and do
one logical equivalence so let’s just go ahead and do one table here so we need

00:18
p’s and q’s we need to not queue we need a p implies a not q
and then we need the negation of the p implies and not q
and we also need the p and q and and then yeah so let’s do this real quick
so let’s go here true false true false true true false false
and then negate the q false true false true and then p implies not q
so look at implication so we have false true true true
and then now let’s negate that so true false
false false and now let’s look at an and between these two
so the end would be true false false false and you can see here that these are
equivalent to each other true true false false they all they’re

00:19
all matches the whole way through so this is a logical equivalence here so
just to refresh your memory on how to do that but the point is
that to show that these two are functionally complete
how can i rewrite the other uh ones how do i write the or p or q
if you play around with this you see p or q is going to be p implies q implies p
sorry implies q so again to to show this logical
equivalence you could write out the truth table to show it
but this shows how to write the ands with negation and implication and how to
write the ors with only in fact only an implication here
and then p if and only if q we can write that as logically equivalent to

00:20
the negation of p implies q implies the negation of q implies p
so it’s the negation of all that so p implies q implies the negation of q
implies p and the negation of all that so that will get rid of the uh
equivalence anytime you have an equivalence you can rewrite it with only
negations and implications so the these are logically equivalent to each other
okay so now to see that you might need to make a truth table
and in fact you don’t need to know this exact one here all you need to do is to
come up with equivalence with some compound statement here it doesn’t have
to be this exact one but some compound statement here that only uses these two
right here negation and implication so using negation and implication [Music]
we have the statement here and we can show this logical equivalence again just

00:21
by making a true table so that truth table would go something like this right
p q um we’re going to need the q p implies q q implies the p
negation of q implies a p and then we have this implication here the negation of
or p implies q implies the negation of q implies p let’s do all that
true false true false true true false false
so the implication here is true false true true
the implication going the other way is true false true
and the negation of this implication is false false true false
and now the implication here which is p implies q

00:22
implies this one so i’m looking at implication true implies a false is false
if also implies a false is true and this is true and this is false
and now we need to do the negation of all of this so i’ll just say negation of
all of that well what is the negation it’s true false false true and if you
look at the equivalence here of p and q right what is the equivalence it’s true
false false true which matches that right there
that’s just that whole statement there okay so the point is that that this is a
logical equivalence here so we can take any we can take these two right here

00:23
and that’s all we need we can get rid of the and we can get rid of or and we can
get rid of equivalents and only write them with negations and implications
so there we go so now the question is can we have one logical connective
and get everything get all boolean expressions get all possibilities
can we get rid of all five logical connectives and only have one
um well we can’t get rid of all five but actually there’s some other logical
connectives so if you remember back to our first video here we had
you know what are the seven logical connectives that you need to know
and in that video we talked a little bit about the up arrow and i promised we’d
talk more about it it’s called the nand and here’s the true table for it so

00:24
how do you get this truth table here let’s refresh our memory on that so we
have p and q and p and q and we have the negation of p and q so true false
true false true true false false we have the and so true false false false
and then now if we negate that we’re going to get false true true true
so this is just the negation of the and or for short the nand
and we’re just going to use a symbol for that the up arrow as you can see it’s
one of the 16 boolean expressions that’s possible false true true true
so that’s called up arrow for short and that way we don’t have to use all these
logical connectives but we already showed that negation and and is
logically complete so you would probably guess that the up arrow the nand is
functionally complete also like this says here but let’s just you know do

00:25
better than say guessing let’s show how to get rid of all the um
other logical connectives so how would we do that
so first off we need the let’s remember the implication here p implies q is
logically equivalent to not p and not q so that allows us to take implications
to negations and ends and then we can do p is logically equivalent to q
which will allow us to do uh implication in ands remember this is p and q
and q and p q implies p right p implies q and q implies p
so this allows us to go from um implication to
uh sorry equivalence to implication and ends and then we also showed p or q

00:26
can be written with negation and ands it’s the negation of the negation of
p and in the negation of q we did we used de morgan’s law to get that
so the point is we can write any ors with negation and ends
and we can write implication with ends in implication
and we can write implication with ends in implication
so if you trace everything back through here
there’s only we only need negation and ands
right so if you have negation and ands you have the or and if you have the
negation and ands you can rewrite implication so i can rewrite this
implication with negation and ends and i can rewrite this implication with
negation and ends so the point is is that we only need negation and ends and
now how do we get rid of negation and ands so that’s the key

00:27
so the first thing is to notice that p up arrow p is logically equivalent to
not p and this will be a way to get rid of negations
now before we go on let’s just check this is a logical equivalence here so
let’s make a true table true false thus the possibilities for p
and then we have negation of p which is false and true
and then now what is p up arrow p so those are the columns that we need
so p up arrow p so what’s a true what’s a true up arrow true
so true up arrow true is a false so this would be false
and now if p is false what’s a false up arrow false so that’s true
and so you can see these are equivalent to each other so not p
is logically equivalent to p and up arrow p so these match so true and these

00:28
match so are true so this is the tautology which means
they’re logically equivalent to each other
so the point is is that every time i see a negation i can write this using an up
arrow in fact let’s just flip sides just for the fun of it
negation of p is logically equivalent to p up arrow p
so i like to think about them in terms of left to right
if i want to rewrite an implication here’s where i go i take any implication
and i rewrite it i can rewrite an equivalence rewrite it and i can rewrite
an or and i can rewrite it now whenever i have negation i can rewrite it so
here’s the negation not p i can rewrite that using up arrow i can rewrite this
using up arrow and i can rewrite this negation of all
of this using up arrow two but how do we rewrite the ands so let’s do that now

00:29
so how do we do p and q in terms of only up arrows here so p and q
um this will be p up arrow q up arrow p of arrow q or nand
so here’s how we’ll be able to rewrite the ends it’ll be the uh nand
sorry how to rewrite the ends it’ll be the nand of these two which are both
nands so let’s make sure we understand this let’s prove this logical equivalence
real quick so we have p and q and we don’t need anything else
no no negations i mean now we have p up arrow q and then we have p up arrow q
nand p nand q so that’s all the columns we need here so let’s go true false

00:30
true false true true false false okay now what’s the up arrow to get this part
right here what’s up era well we have it right here it’s false true true true
and now i’m going to do the nand with itself with this column with
itself so i’m going to do i’m going to do the false that’s a false
right there so false up arrow false nand false which is true
and now i’m going to get the true so what’s a true nand true
that’s right here and that gives us the false
and then i have the same thing again the true
so i have a true here up arrow true so that will be false
and then last but not least i have the false false so i have a true here so
what is the end let’s remember the end the end here so true and true is true

00:31
and then i have a false um so it looks like they all match except for right here
false and false is certainly false so what happened right here um
this is false true true oh that was supposed to be a true right there
just copying that down there that was supposed to be a true
so the up arrow was with the true so true true
and then false so this should be a false there
all right there we go so these match right here so we have an equivalence
is that is a tautology right so all of this uh if and only if this
so that’s true true true true so the equivalence is a tautology so pnq

00:32
i guess we could sneak it in here pnq if and only if p up arrow q
up arrow p up arrow q [Music] so that statement right there is a tautology
all right so what have we done let’s look at a um let’s remove this table here
and just make sure that we’re clear on everything really quick
um the alternative negation is functionally complete and the way that
we show that this is functionally complete right here is by rewriting
being able to rewrite all five logical connectives in terms of up arrows only
anytime i see a not i can rewrite it using up arrow anytime i see an and i
can rewrite it into all of this so i can rewrite this whole expression here so i
can rewrite an or so what will p or q be just for an example here

00:33
well p or q it’ll be negation of a negation with an and here so let’s
write this um let’s write this part out right here
real quick what’s the negation of p so that’ll be p up arrow p
and then we have an and here and then we have a q up arrow q
we have an and between these two just to work on this part right here we have an
and between these two so to do an and i need to do all of this right here and
then i have a negation in front of all that and i’ll do that negation last but
how do we do this and here when this is the not p right here and this is the not
q so the and is going to be the p and q here and then the p and q here and then
a nand between them so this will be our not p

00:34
so we needed not p so i’m going to use p up arrow p and then up arrow
and then the um q up arrow q so [Music] this right here will be the not p and
not q and so to do the end here of these two i’ll need to do the
p yeah the p up arrow key p sorry and then the um
to do the and i need a p and a q here’s my p and q so i need uh up arrow
q up arrow q and then i have up arrow and then all of that again so p up arrow p
up arrow q up arrow q and then parenthesis there

00:35
and then i still have negation in front of all that i still have that negation
so all that rights right there is for the and of the negations of p and q
here’s a negation of p negation of q negation of p negation of q
but to do the and right here to do that and i need the same thing
up arrow the same thing to do the end right here
and so we still have to do the negation and the negation is the same thing
but with an up arrow between them so uh for for p or q
one way to write it and this isn’t necessarily the only way or even the best way
but it would be p up arrow p and then um an up arrow q up arrow q so all of that
and then up arrow to get the and p n p up p up arrow p q up arrow q all that

00:36
and then to get the negation i need up arrow all that again
so up arrow and then all that again and so then the same thing here so
this is certainly possible to do all this is it the best way well perhaps if
you’re using computer or computer science or something related to that using
computational software maybe this would be better maybe not but it’s not very
intuitive to say an or by using all of that right there so
that’s the nand it is functionally complete now the question is what about the
nor the down arrow so let’s look at that
so it’s going to be very similar to what we did so we’re going to take an

00:37
implication here p implies q and we we can rewrite it with the
negation and the or and we can write rewrite the and
using a logical equivalence negation of p or negation of q using de morgan’s law
we can do p if and only if q is logically equivalent to not p or q and
not q or p so again we’ve talked about these three logical equivalences already
now what does that do it allows us to rewrite these three
in terms of negations and ors and so what’s left is to figure out
how to rewrite negations and ors only using the norse now is that even possible

00:38
well let’s look at a clue as to why it would be possible
so let’s remember what the what the nor is so p or q true false true true
false false and what is the or and then what’s the negation of the or
so the or is true true true false and so the negation is false false false true
and so this is the nor right here and so we’re just going to be using down arrow
as a substitution for this for these two logical connectives now remember we
already showed that negation and or is functionally complete so it would
make perfect sense that this is functionally complete but let’s go ahead
and figure out how to actually do it how to actually carry it out
so we would need to know how to write in negation of a p and that would be p

00:39
down arrow or p nor p and how do we rewrite an and
or sorry we already took care of the n p or q and so this will be p nor q nor
p nor q so you see that this is very symmetrical to what we had a minute ago
up arrow so there isn’t any like major surprise
here that nor is also functionally complete and the
logical equivalences are very similar to it and you know we could go make a true
table to verify all that but it will be very similar to what we just did and so
that’s the exciting part is the answer is yes there is actually one logical

00:40
connective you can use to to get all possible boolean expressions and
that’s it for this video so i want to say uh thank you for watching now if you
have any questions or ideas i hope that you use the comment section below don’t
forget that this is part of the series logic and mathematical proof in-depth
tutorials for beginners and i want to say thank you for watching again 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