Predicates & Quantifiers - Discrete Mathematical Structures Video Lecture

to speed all of us to love each other
in the last two lectures we saw about
propositional logic we saw what we're
propositions and what are the logical
connectives the logical connectives
which we consider there and are not
implication in the equivalence and we
also saw some identities about logical
connectives and logical expressions and
we saw how to simplify logical
expressions we also saw what is meant by
a tautology a contradiction in the
contingency yeah
towards the end of the last lecture I
left you with a problem we shall
consider the problem this will tell you
how you can use make use of logic and
get some problem Salter here is the
problem which we considered earlier a
certain country is inhabited only by
people who either always tell the truth
are always tell lies and who will
respond to questions only with ASR and
no answer
the tourist comes to a fork in the road
where one branch leads to the capital
and the other does not there is no sign
indicating which branch to take but
there is an inhabitant mr eazi standing
at the folk watch single asad no
question should the tourists ask him to
determine which branch to take the
situation is like this there is a fork
but there is no sign board but mr. Ezard
is sitting over here and the tourist
comes like this now he has to ask her
single yes-or-no question so that if the
answer is yes he must take the left road
this is the left road and this is the
right Road and if the answer is no he
must take the right road and there is a
persons said sitting over that but the
store is does not know whether he said
truth teller are a liar so there are
four possibilities arrays like this the
left road may lead to capital R the
right road may lead to capital and the
person may be a truth teller or a liar
now if the answer is yes he has to take
the left road and if the answer is no he
has to take director for all these
possibilities this should happen but the
liar always lies and the dancer is says
he will say no and if the answer is no
he will say yes so the correct answer to
the question the tourist has to ask is
this left right
because the lair always inverts the
answer the correct answer should be like
this so the question will be something
like this is it true that you are a
truth teller and the left road loads to
capital
ah you are a liar and the right road
leads to capital the this is a
combination of these two using a R
because either of these cases he will
take the left road so you can read it
like this is it true that you are a
truth teller and the left road leads to
capital R you are a liar and the right
road leads to capital so look at this
very carefully if that he feels the
tutela and the left road leads to
capital he will say yes and so the
person can take the left road and if he
is a liar and the right road leads to
capital the correct answer is yes but
the lair will say no and so if there if
it is a combination of liar and write
the answer will be no and he will take
that I'd wrote so like that you can look
into the all the fourth possibilities
and you will see that this is the
question he has to ask this is a single
SR no question by getting the answer is
he will take the left road and by
getting the answer no you will take the
right Road it's not that this is the
unique answer the question can be
something like this also is it true that
if I ask you whether the left road leads
to capital you will say yes won't you so
again you look at their four
possibilities if he is the truth teller
and the left road loads leads to capital
he will say yes and so in the next case
also it will be yes it's a combination
of s and s so you will say yes and then
you take the left road but if he is a
liar and the right road leads to capital
the question will you say yes he has to
say no but BRC says a layer you will say
yes and yes again negative if I ask you
whether the left road leads through
capital you will say yes he will say no
but because a second time negative he
has to use he will say yes
so whenever the answer is says the left
road will be taken so it's a sort of a
double negation makes a positive some
sort of an idea is there here another
question which is equal into RA which
you'll serve the same purpose is this if
I ask the other kind of person whether
the right road leads to capital he will
say yes won't he won't he again here
again you look into the four
possibilities think carefully and look
into the four possibilities you will
realize this is also a proper question
by getting the answer is he will take
the left road and no he'll take that I
took so this is what we study about a
proposition there are many interesting
such puzzles where you make use of logic
to solve a question like this let us
consider this problem this also I
mentioned in the last lecture
Brown Jones and Smith are suspected of
income tax evasion they testify under
oath as follows
Brown Jones is guilty and Smith is
innocent don't says if Brown is guilty
then so is Smith then Smith says I am
innocent but at least one of the others
is guilty the question is assuming
everybody told the truth who is innocent
and who is guilty assuming the innocent
told the truth and the guilty light who
is innocent and guilty the first part is
easier as it told in the last lecture
now let us write these sentences in
logical notation and try to get the
answer
suppose B stands for browning is
innocent
Brown is innocent then not be will stand
for Brown is guilty
Brown is similarly J stands for Jones is
innocent and not J stands for Jones is
similarly yes n not is yes will stand
for yes
Smith is innocent and not this will
stand for Smith is guilty now what are
the statements they are making Brown is
making the following statement
Jones is innocent and don't just guilty
what is the first statement Jones is
guilty and Smith is innocent
so he says Jones is guilty and Smith is
innocent
Jones says if Brown is guilty then so is
Smith so this should be written like
this Brown says not J and this that is
Jones is guilty and Smith is innocent
the on says if Brown is guilty that is
not be then Smith is also guilty that is
not be in place not this then Smith says
I am innocent that is yes and at least
one of the others is guilty that is not
be are not one of the others is guilty
so the statements they make can be
transcribed in this manner
now suppose everybody tells the truth
all these three test statements should
be true in that case what is the answer
you get Brown Jones Smith Brown says all
three statements are true Brown says not
J&S so not a miss get this guilty guilty
and don't is guilty and Smith this
innocent and you take the second
sentence that is true not be in place
not is what is the contrapositive of
this the contrapositive of that will be
yes in place be P implies Q means the
contrapositive is not you impress not be
so the contrapositive of this is this
that is true that is if Swift is
innocent then B is innocent brown is
also innocent you know that Smith is
innocent so Smith is innocent so from
this we get Brown is
in the same so if all of them are
telling the truth this is the answer you
get them but the second portion of the
question is if the innocent tell the
truth and the guilty lied who is
innocent and who is guilty now first let
us take brown there are two
possibilities
Brown may be innocent are brown may be
guilty consider this possibility Brown
is innocent then he must be telling the
truth
so in that case he must be telling the
truth
so the possibility is brown is innocent
Jones is guilty and Smith this innocent
because he says that Jones is guilty and
Smith is innocent but in this case what
is the statement of Jones if Brown is
guilty then so Smith are the
contrapositive is you Smith is innocent
then Brown is innocent that is also true
so actually did Jones is making a
correct statement if he is guilty he
must be making a wrong statement so this
possibility goes so Brown cannot be
innocent this possibility is ruled out
now what are the other possibilities
Brown is guilty so Brown is guilty but
Jones and Smith they can be innocent
both can be innocent are one can be
innocent other can be guilty one can be
guilty the other can be these are the
possibilities other four possibilities
will be like this now let us take this
sentence this possibility
Jones is innocent so he is telling the
truth what is he saying it Brown is
guilty then Smith is guilty but Smith is
innocent so he is making a wrong
statement so this possibility is ruled
out now looking at this possibility the
ONS is saying a correct statement if
Bill Brown is guilty then so is Smith
and Smith is saying I am innocent and so
on he is making
wrong statement so this also works out
correct so this looks a possible answer
now look at this again in these cases
what is the statement of Jones Don says
if Brown is guilty then so yes Smith he
is lying but Smith this innocent
so you must be telling the truth Smith
says I am innocent but at least one of
the others is true this looks ok look at
this first statement Brown is guilty so
he must be saying a wrong statement what
is the statement of Brown what is the
statement of browns it is Smith this
guilty
George is guilty and Smith this innocent
now he is guilty so you must be selling
the wrong statement so you have to take
the negative that that will be J Ark not
this that is you have to roll out this
possibility because here both of them
are not correct so this is now what does
this correspond to this is again not a
possible possibility because in this
case Smith is guilty so he must be lying
and Jones is guilty he must be lying so
the treatment that if Brown is guilty
then so is Smith it's a true statement
which is making but he has to like
because he is guilty he has to lie but
he is making a true statement so this
possibility is also rolled out so the
correct answer in this case is Brown
guilty
don't innocent and Smith
so next we study about predicates and
quantifiers
now we already consider that a statement
something like X greater than 3x plus y
is equal to 7
they are not propositions they are
assertions but they are not propositions
because the truth value you give them
will depend upon what value are going to
the going to give for the individual
variables x and y in the English
language you may have statements like
this she is tall and fair X was born in
City Y in the year Isaiah he was born in
the city Y in the year is a dearth
something that you can use pronouns
pronouns will stand for variables
individual variables here we do not know
whether it is character true or false it
depends upon who the cheese and here who
is this who is what is the city Y and
which here is is it depending upon that
the sentence will get a truth value or
false so they are called predicates and
the value you give to the individual
variables will depend upon will give you
the proper truth value to that now you
usually note the predicates like P X Y Z
for example X plus y is equal to Z this
you can represent as some XYZ this
stands for the predicate X plus y is
equal to Z if you have
MXY this may stand for exes married to
again we do not have a unique value the
value will depend upon what well you are
going to give for individual basics and
buy-in programs you frequently come
across statements like if X greater than
three then say someone is equal to five
yes oh you see fourth to seventh
so you assign the value Y to Y if X is
greater than three and otherwise you
give the value of seven now this is a
predicate here and when the control
comes to this statement you evaluate at
that particular instance X may be having
a particular value and you give that
value to X and find out whether that
treatment becomes true or false and if
it is true you execute to the end
portion and if it is false you execute
the else portion now in general you have
a predicate of the form P of x RQ Y of X
Y etc this is a unary predicate it has a
single individual variables this is a
binary predicate in general you may have
something like P of X 1 X 2 xn you may
have n individual variables in the
predicate this is called a unary
predicate are in place predicates
now depending upon the value you have to
choose the value you give for x and y in
this case x and y are to be taken from
the set of human beings and in this case
x and y can be real numbers is it can be
a real number or x and y can be integers
non-negative integers or integers and so
on they are chosen from a particular
domain of values and that is called a
universe our universe of discourse
universe our universe of discourse
now look at this X was born in the city
why in the year is it X takes value from
the set of human beings Y takes value
from the set of cities Z takes values
from the set of yes so that is called
the underlying universe and in this case
some of X Y Z it represents a predicate
X plus y is equal to Z so X Y is it may
be taken from the set of integers are
non-negative integers now in such cases
you may have to specify what is the
underlying universe because a statement
it may be true for integers may not be
true for real numbers or a statement it
is true for real numbers may not be true
for integers and so on so underlying
universe has to be specified but
sometimes like this you need not have to
specify the underlying universe
explicitly look at this sentence X was
born in the city Y in the year he said
obviously X has to be a human being Y
has to be a city right and Z must be a
year you cannot have Y an integer and
you cannot have Z a color and so on so
something like you know if you have the
predicate X greater than 3 I cannot say
X is a color green
Green is greater than 3 it doesn't make
any sense
so X has to be from the set of integers
or real numbers whatever it is so in
some cases you need to specify the
underlying universe explicitly and
sometimes you need not have to spell it
out explicitly implicitly it will be
understood
now let us take a predicate x1 x2 again
we can have predicate constants and
predicate variables predicate constants
and predicate variables
like you know sum of XY is is that it's
a predicate constant it represents X
plus y is equal to Z now if you
generally say P x1 x2 X is a variable
you can assign any in place predicate to
that and you also have expressions
involving predicate variables and so on
now when you assign a value but click
Euler value for x1 see one particular
value c2 and a particular value CN for X
n this predicate becomes a proposition
for example take this X plus y is equal
to Z if I assign the value X is equal to
two Y is equal to 3 and Z is equal to 5
it becomes 2 plus 3 is equal to 5 which
is a proposition so if you assign
particular values c1 c2 CN to X 1 X 2 X
n then the predicate becomes a
proposition and it takes a truth value
true or false of course it has to take
values from the underlying universe now
a predicate x1 x2 xn if this is true for
all values c1 c2 CN from the universe
you can say call it as you universe you
then you say that this predicate is
valid in the universe you then you say P
of x1 x2 xn is valid in you
if it is not true for all values of c1
c2 CN but for some particular value it
is true then you say it is satisfiable
in you if P is true for some c1 c2 CN
from you it may not be true for all but
for at least one it is true then you say
that P is satisfiable in now it may so
happen that P of x1 x2 xn is not true
for any of the values you give for c1 x1
x2 xn if P is not true for any value any
set of I'll say any set of values c1 c2
CN then P is said to be unsatisfiable
unsatisfiable
so we talked about valid predicates
satisfiable predicates unsatisfiable
predicates and also we specify the
universe now you have a predicate say X
Y P of X Y then you can make it a
proposition by giving values for x and y
so give values for x and y this becomes
a proposition
this becomes a proposition
now in this case you say that you are
binding the variable you are binding
variables x and y by giving values there
is another way you can bind the
variables that is by making use of a
quantitative quantifiers binding using
quantifiers
for example you have a predicate P of X
this is a predicate unary predicate
involving one single variable X now you
can bind it you see this quantifier for
all of X this is Redis for all X are
generally you read it as for all X we
can also read it as for every X for any
X for each X for arbitrary arbitrary X
now when you use a quantifier the
predicate is bound let us consider some
examples making use of this it becomes a
proposition menu you say quantifier the
underlying universe with a set of
integers
look at this ready gates X is less than
X plus 1 you look at this predicate and
X is equal to 3 X is equal to X plus 1
now to make it a proposition I can use a
quantifier like this look at this for
all of X X is less than X plus 1 this is
a property is it true this is always
true isn't it
but you Nev al uu 4 X from the set of
integers X will always be less than X
plus 1 and so this is all this true it
is a proposition and it is always true
and if you use for all of X here for all
of X X is equal to 3 it is not correct
isn't it if you give value for 2 X 4
equal to 3 is not correct so it is true
only when you give the value 3 to X and
for other values it is false so saying
that for all of X X is equal to 3 where
the underlying universe is a set of
integers it's not correct this is a
false statement this is again a
proposition it becomes a proposition and
takes the value false now look at this 1
X is equal to X plus 1 for all of X X is
equal to X plus 1 again then for none of
the values from the set of integers X
can be equal to X plus 1 so this is in
fact not true for any value so saying
that for all of X X is equal to X plus 1
is not correct it is a false statement
so this takes the value false
so we see that using the quantifier for
all of X you can make a predicate a
proposition and it takes a particular
value true or false depending upon what
universe you're specifying now the other
universe other quantifier as a
quantifier is there exists X P of X you
can use the quantifier there exists X P
of X this is read like this that exists
X such that P of X is true you can also
read it as for some max P of X
okay now let us again take the same
three predicates and see what happens
when you apply that quantifier there
exists this directness six is called a
gift seneschal quantifier exists tension
quantifier the earlier one which we
consider for all of X that is called a
universal quantifier now again let us
take these three predicates and take the
underlying universe as a set of integers
this is a predicate if you use there
exists X X less than X plus 1 is it true
or false obviously but every value of x
X will be less than X plus 1 so for some
value also it is true so this is a
proposition this takes the value use
there exists for this predicate there
exists X X is equal to 3 again if you
assign one value X is equal to 3 from
the universe this will be true so saying
that for some X X is equal to 3 is
correct so this takes the value true and
if you say there exists X X X is equal
to X plus 1 it will not be true for any
X isn't it X cannot be equal to X plus 1
for any integer so there exists X X is
equal to X plus 1 is a false statement
so the point to remember is when we use
a quantifier we are binding a variable
and when you bind a variable a unary
predicate becomes a prop
when it is a binary predicate involving
two quantifiers x and y you have to bind
both of them to make it a proposition so
a predicate can be made into your
proposition by binding the variables
there are two very ways of doing that
one is by assigning values to individual
variables or by using quantifiers and
mainly we use two quantifiers one is for
all X and another is there exists X
there is one more quantifier which is
denoted like this there exists a unique
X such that V of X is true this is read
as there exists a unique X such that P
of X is true
are there is one and only one X such
that P of X when we use only for all and
that exists this is rarely used but
anyway we'll learn about this also the
reason is you can express there exists a
unique X in terms of for all and there
exists that we shall see now now again
let us take the same three statements
and use this quantifier there exists a
unique X says there exists a unique X X
is less than X plus 1 is it true or
false underlying set is the set of
integers if you take any value for X X
will be less than 1 it's not correct to
say that there is a unique value of x
for it exists there is an X plus 1 okay
so this becomes a proposition which
takes the value false and there is a
unique X X is equal to 3 for only 1
value of the variable X from the set of
integers the assertion X is equal to 3
will be 2 that's correct
only when you give the value 3 tricks
this will be true if you give any other
value it will be false so there is a
unique value for which this is true so
this takes the value true and then that
X are unique X X is equal to X plus 1
again but none of the values this is
true so saying that that eggs are unique
X for which this is true is not correct
so this takes the value false
now I told you that this is not
frequently used because you can express
this in terms of for all of X and there
exists X so instead of writing directly
60 of X you can write it this way there
exists 6p of X and for all of Y P of Y
implies X is equal to this is equivalent
to saying there is a unique X that's
letter G of X that is why we don't use
this frequently but sometimes you also
use it for convenience E this is a
lengthy expression instead of that you
can use that unique X in a convenient
manner
similarly there exists at most one X
there exists at most one X this you can
represent like this there is this X for
all Y P of Y implies X is equal to
so if you have say something like P of
XY is it then XY is it this is a
predicate involving three individual
variables x and y is it if you say some
quantifier like this for all of X P of X
Y is it then X is bound X is bound here
and yn is a dark free X is bound Y and
is it are there called free variables
again you can bind them by say giving
values are again using some other
quantitative so you can say Y is equal
to 2 and so you will get for all of x PF
for all of X P of X comma 2 comma X now
it is a unary predicate because this is
bound a Lisette is free and you have
burned away by giving a value if you say
something something like there existed
for all of X P of X comma 2 comma Z both
X and Ezard are bound and so this
becomes a proposition and it will take a
value true or false if you specify the
underlying universe it is considered one
more example like this see now we have
taken this x + y is that is equal to z
some
okay so some XYZ denotes this now if I
say there exists Y some XYZ is born
right Y is bound and X and Assad are
free if you specify the underlying
universe as a set of non-negative
integers n denotes non-negative integers
non-negative so x and y and desert take
values from the set of non-negative
integers then what do you mean by saying
there exists a sum of X Y is that that
is there exists Y such that X plus y is
equal to Z if all of them are
non-negative that means X has to be less
than or equal to Z so this really stands
for some predicate X Z it is it's less
than horrible that if the underlying
inverse is the set of non-negative
integers okay like that we had to
analyze the statements now how do you
expand this or look into this for
example if the underlying universe I say
is 1 2 3 it consists of only three
elements say 1 2 3 then for all of X P
of X will represent should be true for
every value here so it represents P R 1
and P of 2 and P after
there exists X P of X this represents a
compound statement P R 1 R P of - ah
there exists a unique X P of X how will
we represent this if it is true for one
it should be false for two and three if
it is true for two it should be false
for one and three if it is true for
three it should be false for one and two
so you represent it as P of one and not
of P of 2 and not of bf3 ah not of P of
1 and P of 2 and not of P of 3 oh not of
P of 1 and not of P of 2 and P of 3 we
can express like this if the universe is
finite in this case it consists of only
three elements 1 2 & 3 if it is infinite
what shall we do for example let the
universe be set up non-negative integers
which is just 0 1 2 etc then for all of
X P of X will be denoted by the infinite
conjunction P of 0 and P of 1 and P of 2
and like that it is an infinite
conjunction like this directly 6 V of X
it is denoted by P of 0 RP of 1 RP of 2
R and so
infinite disjunction now if you have a
predicate involving individual variables
P of X 1 X 2 X n and there is one more
variable Y say and you say there exists
Y P of X 1 X 2 X n where Y is different
from X 1 X 2 X n then binding like this
is not going to affect this this portion
this is just not involve Y at all if
this is just not involve Y by whether
you bind it with there exists Y R for
all it is not going to offer if you say
this is these these are all equivalent
for all of Y P of X 1 X 2 xn and without
any bindings of quantifiers also they
are all equivalent if this just not
involve Y so we have to be careful about
the scope of the quantifiers and which
one it is going to bind and so on
now look at these statements for all of
X for all of Y P of its value P is a
binary predicate and you are having two
variables x and y look at this statement
for all of X for all of Y P of X Y
how will you read this you will read
this is for all values of X and for all
values of Y P of X Y is now look at this
there exists like for all of Y P of X Y
and for all of Y there exists X P of X s
bound by the existent shield quantifier
and Y is bound by the universal
quantifier are these two statements
equivalent you are using the quantifiers
in different orders the order is
exchanged do they mean the same sentence
or are they different can you
interchange the order of painting in
this case you cannot change they
represent different statements here if
you have to read it like this there
exists X such that for all values of Y P
of X Y is now the value of X is fixed
independently of the value of y here and
look at this it says for any Y there
execs such that P of X Y is true
now here you take the value of y and the
value of X depends on the value of money
okay so the meaning is different you
cannot interchange in this case the
meaning will change let us look at some
examples now but you can always change
for all of X for all of Y into for all
of Y for all of X and that exists X
there exists Y you can change the order
this will not affect but here it will
affect
ha ha the order will affect the
statement now let us consider the
examples now let us consider some
example that they're changing the order
of the quantifiers affects the meaning
let the universe of disgust be the set
of married persons then when you say for
all of X there exists X is married to Y
that means for any X for any X there is
a person Y to whom X is married this is
correct so this is true whereas if you
say there exists Y for all of X X is
married to Y that means there is a
person Y to whom everybody else
including himself will be married so
there is a wrong statement so changing
the order affects the meaning completely
so you have to be careful about the
order in which you bind the variables
and when use the quantifiers now let us
take the set of integers as the
underlying universe then look at this
statement for all of X there is a Y such
that X plus y is equal to 0
that is for all of X there exists Y such
that X plus y is equal to 0 this is true
because any value of x there is a value
of y by taking Y to be equal to minus X
which makes the assertion true ok now
look at this there exists Y for all of X
X plus y is equal to 0 this asserts that
the value of y can be chosen
independently of the value of x since no
voi exists which is 0 when added to an
arbitrary integer this is a false
statement
so by interchanging the quantifiers use
once you get a true statement another
you get a false statement look at this
one for all of X for all of Y there is a
unique is that such that X plus y is
equal to Z this is a true statement you
have to choose Z
be the sum of x and y but if you look at
this statement for all of X there is a
unique ez such that for all of I X plus
y is is equal to Z this is not a correct
statement and so it is not it's a false
statement so here the value of Z is
chosen first and then you say whatever
will be the value of y you choose X plus
y will be equal to is it that is not
correct look at some more statements
there is a unique X such that X into 6
is equal to 0 this is true because only
if you give the value X is equal to 0
this will be true if you give me any
other value this will be false and look
at this one there is a unique X for all
of Y X into y is equal to 0 this is true
because only when you take X is equal to
0 for all Y X into y will be equal to 0
but if you interchange the order you say
for all Y there is a unique X such that
X into y is equal to 0 is false because
if Y you take to be 0 any value of x
will satisfy that and so you cannot say
that there is a unique X so there is a
false statement
the last one look at this
for all why there is a unique X such
that X plus y is less than zero is false
because you have a several race of to
sing x given a value of y so that the
sum is less than zero for the any value
of y there are many values of x for
which the sum of x and y is negative
this is a false statement so you have to
be very careful when you quantify a
variable or when you bind the variable
using a quantifier and the order in
which you end the variable matters it
gives the meaning to the sentence so in
the next lecture we shall see how to
convert English sentences into logical
notation using quantifiers and
vice-versa