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

we’ve already seen that before just refreshing your memory here

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

and so what was this one supposed to be here

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

so we’ve talked about these logical equivalences already

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

we had up arrow we had up arrow and we had the and and we had up arrow up arrow

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

you think in the comments