Propositional Logic (Contd.) - Discrete Mathematical Structures Video Lecture - Computer Science Engineering (CSE)

oh ha ha ha jung-woo day does speed all
of us Pawar official I don't eat meat
you
let us continue with what we learnt in
propositional logic in the last lecture
first we shall review what we learnt in
the last lecture we saw what is meant by
a proposition and taking propositional
variables P and Q PQ we consider logical
operators and our unary operator not and
exclusive or operator implication and
equivalence
to recall what we studied earlier P and
Q is true only when P is true and Q is
true PR q is true when either P is true
our Q is true or when both of them are
true it is false only when both P and Q
are false considering not B not B is
true when P is false and not P is false
when P is true the exclusive or operator
we consider like this P exclusive or Q
this compound expression is true if one
of P and Q is true and the other is
false it will be false when both of them
are true or when both of them are false
P implies Q we have seen how to express
this in a different ways we can also say
if P then Q Q if P P only if Q and so on
this is true if P is false our Q is true
that is in three cases it will be true P
false Q true P false Q false P true Q
true it is false only when P is true and
Q is false P is equivalent to Q this is
true if P and Q both take the same value
that is if P is false and Q is false
this will take the value 1 if P is true
and Q is true also this will take the
value true but if one of them is true
and the other is false this will take
the value false or 0 we have also seen
what is meant by a contrapositive for P
implies Q the contrapositive is not Q
implies not P this is
called the contrapositive
and Q implies P is called the converse
of P implies Q we also saw how to draw
two trebles for propositional forms are
well formed formulae of propositional
logic first we will have columns for
each one of the variables and there will
be a row corresponding to each
assignment of values for the variables
suppose there are three variables each
can be true or false so there are
totally eight equal to two power cube
possible assignments and there will be a
truth eight rows in the table for any
propositional form involving P Q and R
in general if you have K variables there
will be first K columns for each one of
the variables and there will be 2 power
K rows each one standing for one
assignment of the truth values for the
variables we have also seen what is
meant by a tautology a tautology is a
proportional form whose truth value is
true for all possible values of its
propositional variables example is PR
not P contradiction or absurdity is a
professional form which is always false
examples P and not be a proposition form
which is neither a tautology nor a
contradiction is called a contingency
now in some cases it may not be
necessary to have all the 2 power K
rose for a truth table for example if
you want to show that a professional
form is a contingency it is enough if
you show one row where the resultant
expression takes the value 1 and another
row where the resultant expression takes
the value 0 this shows that for some
assignment you take the value 1 and for
some other assignment it will take the
value 0 and so it is a contingency we
need not have to write all that 2 power
K rows and similarly in some cases you
may have a simplified truth table for
example I want to show that P and Q
implies P this is a tautology so
actually I should write 4 rows to show
that this is a tautology and in the last
column I should show that everything is
1 1 1 1 but it is not necessary to write
all the 4 rows because when will this
implication be false this implication
will be false when this is true and this
is false so when will this be true when
both P and Q are true so it is enough if
I write only one row for this pen will P
and Q be true when P is true and Q is
true so it is enough if we consider this
row alone so in this case P and Q is
true and obviously P and Q implies P
because both the antecedent and the
consequence are true this implication
will be 2 so we find that it is not
always necessary to write all the rows
some cases it is enough if you write a
few rows which are necessary to show
what we want
we have also seen some logical
identities let us recall what we have
seen this we have seen in the last
lecture since some of them are very
clear as I told you and this associative
or is associative so you can write
something like p and q and r without any
ambiguity similarly p r q or r also you
can write without any ambiguity but
whenever you are in doubt you must use
parenthesis so that the expression is
unambiguous but if you take P implies Q
implies R you cannot write like this
this is ambiguous do you mean P implies
Q implies R R do you mean P implies Q
implies R implication operator is not
associative and we have to use proper
parenthesis to represent what we mean
see the tables for these two expressions
P Q R P implies Q Q implies R P implies
Q implies R P implies Q implies R let us
draw the truth table for this and see
what happens
so there will be a truce giving
different values for P Q and R we know
that one stands for truth and zero
stands for false when is P implies Q
true in these cases it will be true and
in these two cases it will be false when
will Q implies R be true or when it will
be false when Q is true and R is false
it will be false
in other cases it will be true so
writing down the expression R the truth
value in this column you find that when
Q is true and R is false this is false
but when Q is false r when R is true
this will be
now look at this column and this column
let us fill the truth value for these
two columns when can this be true it
will be true when P is false or Q
implies R is true it will be false when
P is true and Q implies R is false so
taking that you see that whenever P is
false this will be true and what about Q
implies R Q implies R is false here and
P is true so at this point we'll take
the value false here both the antecedent
and the consequence are true in these
three rows so this implication will be
now let us go to the last column P
implies Q implies R that will be false
if this is true and this is false it
will be true if this is false R this is
2 so whenever R is true the compound
expression will be true so looking at
this here it will be true it will be
true here it will be true here it will
be true here if look at this P implies Q
is true but R is false so this will be
false here P implies Q is true and R is
also true so that is 1 here again P
implies Q is true but R is false so this
will be false and here
P implies Q is false r is also false so
this will be true and here P implies Q
is true and R is false so this will be
false so you can see that the last two
columns are not the same so it very much
depends upon how you interpret this
value that is whether you are going to
put the parenthesis here or parenthesis
here the meaning becomes entirely
different so implication is not
associative and you have to be careful
when you write an expression of the form
P implies Q implies R you have to put
parenthesis in a proper manner we have
seen some logical identities in the last
lecture the idempotence of r and and
they are all tautologies then
commutativity of r and commutativity of
and associativity of r and de Morgan's
laws distributive laws then loss
involving one of the operands as true or
false 1 stands for true and other false
double negation not of not of V is P
implication let us see what this means P
implies Q is equivalent to not P R Q let
us construct the truth table for this
and see what it is P Q P implies Q not P
not V R
so giving all four possible values for P
and Q
let us fill this column P implies Q is
false in this case and in the other
three cases it is true we know this now
what about not P not P is true when P is
false and it is false when P is true the
last column is the awning of this - when
is this the airing of this false when
both of them are false in this case both
of them are false so it will be false in
the other three cases at least one of
them is true so this will be true now
look at the third column and the 5th
column you find that they are identical
so P implies Q is equivalent to saying
not P our Q so we can use this
equivalence as' for simplifying
professional forms or if you look at it
as boolean algebra boolean expressions
and replace one expression by an
equivalent one so if you want to
simplify something and if you have P
implies Q you can replace it by not PR Q
and the next one is
P is equivalent to Q is equivalent to P
implies Q and Q implies P for this also
we can draw the truth table and see that
they are equivalent similarly for every
one of these things we can draw the
truth table and see that they always
whatever you have on the left side this
is equivalent to this if you draw the
truth table the two columns will be
identical similarly P and Q implies R is
equivalent to say P implies Q implies R
this is called exportation we can draw
the truth table for this also having
eight rows
if you draw the truth table some
expressions our identities we are
considering the expectation rule says
that P and Q implies R is equivalent to
P implies Q implies R let us draw the
truth table and see you can see that the
truth table for this is like this there
are 3 variables so there will be 8 rows
having all the 8 possible values are 8
possible assignments then P and Q is
true only when P is Q and Q is true so
this is the value for P and Q and P and
Q implies R this will be false only when
this is true and R is false in this case
so only in this case it will be false
otherwise it will be true let us
consider the value for Q implies R again
it will be false when Q is true and R is
false that is in these two rows alone it
will be false list of them it will be
true and taking the last one P implies Q
implies R that will be false only when P
is true and Q implies R is true so
comparing this and this you will realize
that this is false only when this is
true and this is false that is in this
case so if you look at this column are
this column you see that they are
identical and that is what this logical
identity says P and Q implies R is
equivalent to P implies Q implies R then
we have rule for absurdity that is P and
Q and P implies Q and P implies not Q is
equivalent to not P this is the one
which
we will use for proving something by
contradiction this is called proof by
contradiction and this is the law which
we will use for proving such theorems
this we have to see contrapositive P
implies Q is equivalent to not Q implies
not P if you look at the table giving
all the four possible assignments to P
and Q you will get four rows when P is
true Q will be false and so on this is
the column for not P and this is the
column for not Q this is the truth value
for P implies Q this we already know for
not Q implies not P that will be false
only when not Q is true and not P is
false that is in this case not Q is true
and not P is false only in this case it
will be false otherwise it will be true
and so if you look at the last two
columns you see that they are identical
so whenever an expression involving
implication P implies is true it is
equivalent to saying not u implies not P
just for English sentence de we consider
if I fall into the lake I will get wet
and if I am not right means I have not
fallen into the lake that is the
contrapositive of it so like this we
consider these rules and these rules can
be made use of to simplify logical
expressions are well formed formulae of
Corruption logic
let us take an example of an expression
and see how to simplify it let us
consider this expression we will make
use of these identities which we
considered earlier and simplify this
expression this is a implies B or a M
plus D implies B R T this is the
expression here a B D our propositional
variables now let us see how to simplify
this first we shall change the
implication into R we know that a
implies B is equal to saying not a or B
and similarly a implies D is equivalent
to saying not a our D
so you can reduce this expression to
this
now not a is common in both this so you
can take it out and write it as not ta r
BR d
now there is a implication involved here
so again we can make use of the result
that P implies Q is equivalent to not P
or Q and right this is not of not a our
BRD our
now when you have a not out and if you
want to bring it inside we have to use
what are called de Morgan's laws which
we have already seen these are called de
Morgan's laws so this will become a and
not B or D this R becomes and when you
bring the not inside and not of not of a
will become a now using the distributive
law this will become a of BRD a r BR d
and not v rd r
now we know that if you have not PRP
that reduces to one it is always true it
is a tautology so this will become a r
BR d and one that is true and that is
nothing but a r BR d now because of the
associative property of our you can
write it as a r BR d without ambiguity
we can remove the parenthesis here it is
not necessary because of the associative
associativity of our like that using
these identities we can simplify logical
expressions let us consider some
sentences in English and try to convert
them into logical notation and also try
to write down English sentences from the
logical notation let us take an example
now let us consider this P stands for
the sentence it is snowing and Q stands
for I will go to top R stands for I have
time now using logical connectives write
a proposition which symbolizes the
following first we have if it is not
strong and I have time then I will go to
top how can you write this in logical
notation if it is not snowing it is
snowing is P so it is not snowing means
not P and I have done and
are if this is so then I will go to town
this implies Q so this centers can be
written logically in this song not P and
R implies Q the next one is I will go to
town only if I have time P implies Q can
also be read write as P only if Q so I
will go to town only if I have time in
logical notation this will be Q implies
R
the third Center is a very simple
centers it is not snowing P stands for
it is no snowing so not P will stand for
it is not snowing next you have it is
knowing and I will not go to town what
is the logical expression for this it is
knowing is P and I will not go to town
that is not Q Q is I will go to town so
not Q is I will not go to Tom like that
these English sentences can be written
in logical notation and we have a
proposition how will you write it in
English
how will you interpret properly and
write it in English
write the sentence in English
corresponding to each of the following
propositions q is equivalent to R and
not P how can you write this in English
we know that this can be read as if and
only if and what does Q stand for q
stands for I will go to town so this can
be written in the form I will go to town
if and only if
what is the condition other side RN not
P what is RR s I have time and P is it
is snowing so if I have time and it is
not snowing
so this proposition Q is equivalent to
our and not B if you want to write it
English
it takes this form I will go to town if
and only if I have time and it is not
snowing now how will you transcribe this
proposition into English that is how
will you write in certain switch is
equivalent to this R and Q R stands for
I have time and Q stands for I will go
to town so this can be written in the
form I have time and I will go to town
the next one is Q implies R and R
implies Q how will you transcribe this
in English q stands for I will go to
town and R stands for I have time so Q
implies R means this can be written in
the form I will go to turn only if I
have time this can be written in the
form I will go to town only if I have
time
then our implies Q you must rate if I
have time I will go to time if I have
time I will go to
or equivalent Li QM plus R & R implies Q
is equal to saying Q is equal to R so
this can be also written the form I will
go to town if and only if I have time
the last is not rrq again our stands for
I have time and Q stands for I will go
to town so this can be written the form
it is not true that
I have time our I will go proof down it
is not true that I will have time or I
will go to town so like this you can
transform English sentences into logical
notation and logical notation if you
have you can write down the
corresponding English sentences you have
to be careful when you use inclusive or
exclusive are usually either are would
refer to exclusive are and otherwise it
will be inclusive are but you have to be
careful about this let us consider some
more logical identities
they are topologies involving
implications and later on we shall see
that they are also called rules of
inference so these are the logical
implications which are tautologies
addition P implies PR q see when you
have P by adding something the value is
not altered so from P you can conclude
PR Q if you look at it as a rule of
inference from P you will be able to
conclude PR Q and simplification is the
second rule P and Q implies P if you
have P and Q then from that you can
conclude P because P and Q will be true
only when P is true and Q is true and so
you can conclude P from that so if you
look at it as a rule of inference then
you have this P and P implies Q implies
Q this is called modus ponens let us
draw the truth table and see how it
looks
considering the truth table for modus
ponens we have four possible assignments
for P and Q so we have four rows and we
have written down the four possible
values P implies Q this is a truth value
this we also know now P and Q P and P
implies Q this will be true only when P
is true and P implies Q true is also
true so you find that the truth value
for this is in these three cases is take
the value of 0 and in this case it is 1
the last column stands for the entire
statement
P implies P implies Q P and P implies Q
implies Q this will be true if the
antecedent is false or the consequence
is true so in these three rows the
antecedent is false so the compote
statement will be true in the last case
when the antecedent is true the
consequence is also true so this
compound statement is again true so if
you look at the last column you always
have one it is a tautology this is
called modus ponens and when you write
it as a rule of inference you write like
this P P implies Q and from this you
conclude Q this is what is meant by
Modest ponens similarly the next
implication is modus tollens P and Q and
not Q implies not P we can draw the
truth table for this also in a similar
manner but when we write it as a rule of
inference this means if you have P and Q
that is P implies Q and not Q from this
you can conclude not P this is called
this rule therefore not P this is called
modus tollens
whereas this is called modus ponens
and we have some more rules not P and P
R Q implies Q this is called disjunctive
syllogism and P implies Q and Q implies
R implies P implies R this rule is
called hypothetical syllogism we will
come across this again when we study
rules of inference this rule states that
if you have P implies Q implies Q
implies R implies P implies R and this
is the ending of two things and this is
equivalence
P implies Q and R in places in place P
and R implies Q and s and this has this
should be equivalence P is equivalent to
Q and Q is equivalent to R would imply P
is equal to R that last rule is if P is
equivalent to Q and Q is equivalent to R
this would imply P is equivalent to R we
will make use of this in logical
inference when you come to that now
before that I will leave you with a
problem and maybe the solution I shall
give in the next lecture but let us see
what the problem is a certain country is
inhabited only by people who either
always tell the truth are always tell
lies that is either the person will be a
truth teller or a liar and who will
respond to questions only with a yes or
no answer a tourist comes to a folk in
the road so this is a situation you have
a fork
the Taurus is approaching this place
a 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
mister is that standing at the fork what
single SR no question should the tourist
ask him to determine which branch to
take so this tourist is approaching this
fork he sees a person sitting here this
person may be a truth teller or he may
be a liar a truth teller always says the
truth a liar always lies and either the
left road leads to the capital or right
road leads to the capital this tourist
wants to find out there is no board here
so he wants to ask this question but
this person said the inhabitant that may
be a truth teller or maybe a liar this
person does not know the tourist does
not know whether he is a truth teller
Aradia and he will respond only with sr
no answer he will not say anything more
now in that situation this story should
ask only one question a single question
for which the answer will be yes or no
and by listening to that answer like
this if it is yes he will take the left
road the correct road if it is no he
will take the right Road which is the
correct road okay so what is the single
sr no question he should ask so you must
look at the four possibilities the
person may be a truth teller and the
left road may lead to capital the person
may be a liar
and the left load may lead to capital
the person may be a truth teller and the
right road may lead to capital the
person may be a liar and the right load
may lead to capital so there are four
possibilities and the single S or no
question should take care of all these
things let us consider some more similar
problems five persons ABCDE are in a
compartment in a train AC e are men and
B D are women the train passes through a
tunnel and when it emerges it is found
that E is murdered and then inquiry is
held and ABCD make the following
statements a says I am innocent B was
talking to e
when the train was passing through the
tunnel and B says I am innocent I was
not talking to e when the train was
passing through the tunnel C says I am
innocent D committed the murder these is
I am innocent one of the men committed
the murder
you must remember that a and C are men
and B and D are women and each one is
making two statements four of these
eight statements are true and four are
false you have to assume that four of
these statements are true and four of
them are false assuming only one person
committed the murder
who did it from these statements you
must find out who committed the murder
and each one is making two statements
and therefore there are eight statements
out of which four are two and four are
false
now from these arguments are from these
statements how we
you found out how will you find out who
is who has committed the murder look at
the first four statement it each one
makes a says I am innocent B says I am
innocent C says I am innocent and D also
says that now only one person committed
the murder so out of ABCD three of them
must be saying the truth and one is
lying so there are eight statements a is
making statement one and statement to be
is making statement one and statement to
C is making statement one to D is making
one and two out of these these all these
four statements are I am innocent so out
of it three of them are true one is
false so after the four three are true
one is false so in the remaining four
three of them must be false and one must
be because it is given that four of them
are true and four of them are false and
look at the second statement of a and B
what is that B was talking to e when the
train was passing through the tunnel and
B says I was not talking to e when the
train was passing through the tunnel one
is the negation of the other if what s s
is true what B says is not true
if what B says is true a what a says is
not true so out of these two one is
false and the other is true either of
them may be false the other may be true
so it emerged saying that this statement
is false and this also is false so the
second statement of C and D are false
what is the second statement of C D
committed the murder that is false so D
did not commit the
that what the CC second statement of the
is one of the men committed the murder
so that is also false that means a and C
did not commit the murder
so who committed the Mulder be committed
the in that case this first statement of
a is to this first statement of C is
true this is true this is false this is
true this is false this is true this is
true and these two are false one of them
is true and other is false so four
statements are true and four statements
are false so this satisfies the
condition and so we should come to the
conclusion that B has committed the
murder we can look at similar problems
like this as an extension of the example
which I mentioned just a few minutes
back let us consider one more problem
this is much more difficult than that
problem a tourist is enjoying an
afternoon refreshment in a local pub in
England when the bartender says to him
do you see those three men over there
one is mr. X who always tell the truth
and another is mr. Y who always lies and
the third is mr. Ezard who sometimes
tells the truth and sometimes lies that
is mr. Ezard answers yes or no at random
without regard to the question you may
ask them three yes or no questions
always indicating which man should
answer if after asking these three
questions you correctly identify who is
mr. X mr. Y and mr. is that they will
buy you a drink
what s no questions
should the thirsty tourists ask the
problem is like this a person is sitting
here the tool is sitting here the writer
comes and he points out to three people
standing out there
one two three they are standing in a row
and the waitress tells the tourists look
at those three people one is mr. X who
is a truth-teller he always tells the
truth
another is mr. y who is a liar who
always say says who always lies third
person is said sometimes he lies and
sometimes he tells the truth now this
tourist can ask these three people three
questions each time he can ask the first
question point out who should answer the
question and then depending upon the
answer he can ask the second constraint
so second question again he can ask and
point out who should answer the question
again you can ask a similar third
question after getting the answer all
these three questions should be only S
or no question the answer should be only
in the form of s or no so if it is
correct X will say say the correct
answer Y if it is says he will say no if
it is no he will say yes Z without
looking into that he will era and then
we say s randomly say no so what three
questions he should also that at the end
he is able to find out that who is mr. X
who is mr. Y and who is mr. Z actually
this is a not a very easy problem it is
slightly difficult but the first
question is important the first question
should be asked in a such a way that you
eliminate is it actually it is easier to
deal with the person who always tells
the truth or who always lies it is
difficult to deal with the person like
you said who sometimes lies and
sometimes tells the truth so here you
have to find out who is it and eliminate
him and after the eliminating is e the
second and the third question can be
conveniently us think about the answer
for this
problem I shall lead you to another
problem a similar problem
Brown Jones and Smith are suspected of
income tax evasion they testify under
oath as follows Brown says John is
guilty and since Smith is innocent they
own says if Brown is guilty then so is
Smith Smith says I am innocent but at
least one of the others is guilty
assuming everybody told the truth who is
are who are all innocent who are all
guilty assuming the innocent told the
truth and the guilty lied who is guilty
and who is innocent look at the
statements they make we have to transfer
transfer them into logical notation and
solve but the first portion is easy
assuming everybody tells the truth from
the first statement you can infer that
Jones is guilty and Smith is innocent
and if Brown is guilty then so it Smith
so the contrapositive of that will be if
Smith is not guilty Brown is not guilty
so Brown is innocent so the answer to
the first portion is Brown is innocent
donor is guilty and Smith is innocent
the second portion is slightly more
involved you can try the second portion
also so in the next lecture we shall
consider predicate calculus and use of
quantifiers exist until quantifier and
Universal quantifier and further
concepts in logic