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, OR, 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, P or Q is true only when either
P is true or Q is true or both of them are
true. It is false only when both P and Q are
false considering NOT P. NOT P is true only
when P is false and NOT P is false when P
is true.
We consider the Exclusive OR operator 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. We have seen how to express P implies
Q in 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 or Q is true. That
is in three cases it will be true when 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 if P and Q both takes
the same value, that is if P is falser Q is
false this will take the value 1, if P is
true and Q is true also this will take the
value 2, 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 tables
for propositional forms or well formed formulae
of propositional logic.
First we will have columns for each one of
the variable 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 8 equal
to 2 power cube possible assignments and there
will be 8 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 propositional form whose
truth value is true for all possible values
of its propositional variables example P OR
NOT P. A contradiction or absurdity is a propositional
form which is always false example P AND NOT
P. A propositional form which is neither a
tautology nor a contradiction is called contingency.
Now, in some cases it may not be necessary
to have all the 2 power k rows for a truth
table. For example, if you want to show that
a propositional form is a contingency it is
enough if you show one row were the resultant
expression takes the value 1 and another row
were the resultant expression takes the value
0, this shows that for some assignments it
will 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 the 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 1 row for this. When P and Q will be
true? When P is true and Q is true. So it
is enough if we consider this row alone. So
in this 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 true. So we find that it is not always
necessary to write all the rows. In some cases
it is enough if we write 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. Some
of them are very clear. As I told you AND
is associative, OR is associative. So you
can write something P AND Q AND R without
any ambiguity. Similarly you can also write
P OR Q OR R 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 because this is ambiguous.
Do you mean P implies Q implies R or 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 8 rows giving different
values for P, Q and R. We know that 1 stands
for truth and 0 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 will
it 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 or 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 or when R is true this will
be true.
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 it will take the
value false. Here both the antecedent and
the consequence are true in these three rows
so this implication will be true.
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 or this is true. So whenever
R is true the compound expression will be
true. So looking at this, it will be true
here, it will be true here and it will be
true here. Look at this: P implies Q is true
but R is false so this will be false, here
P implies Q is true and also R is 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 and 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
your 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 OR and AND
are all tautologies, then commutativity of
OR and commutativity of AND, associativity
of OR and Demorgan’s laws, distributive
laws, then laws involving one of the operands
as true or false, one stands for true and
other false, double negatation, NOT of NOT
of P is P and implication. Let us see what
this means. P implies Q is equivalent to NOT
P OR Q. Let us construct the truth table for
this and see what it is.
P Q, P implies Q, NOT P, NOT P OR (Q), 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. So the last column is
the orring of this two.
When is the orring of this false? When both
of them are false and 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 fifth column. You find
that they are identical. So P implies Q is
equivalent to saying NOT P OR Q. So we can
use these equivalences for simplifying propositional
forms or if you look at it as Boolean algebra
or Boolean expressions and replace one expression
by an equivalent 1.
So you want to simplify something and if you
have P implies Q, you can replace it by NOT
P OR 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 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 saying P implies
Q implies R and this is called Exportation.
We can draw the truth table for this also
having 8 rows.
If you draw the truth table 
some expressions or identities you are considering.
The exportation 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
or 8 possible assignments. Then P AND Q is
true only when P is true and Q is true so
this is the value for P AND Q. And P AND Q
implies R 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 2 rows alone it
will be false rest of them will be true. And
taking the last one P implies Q implies R
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 or 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
and equivalent to NOT P.
This is the one which we will use for proving
something by contradiction and this is called
proof by contradiction and this is the law
which 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 and
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 Q that will be false only
when Q is true and NOT P is false. That is
in this case NOT Q is true 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 say
saying NOT Q implies NOT P. Just for English
sentence we consider “if I fall into the
lake I get wet” if I am not wet 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 or well
formed formulae of propositional 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 implies D implies B OR
D, this is the expression. Here A B D are
propositional variables.
Now let us see how to simplify this. First
we shall change the implication into OR. We
know that A implies B is equivalent to saying
NOT A OR B and similarly A implies D is equivalent
to saying NOT A OR D. So you can reduce this
expression to this. Now NOT A is common in
both these cases, so you can take it out and
write it as NOT A OR B OR 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 write this as
NOT of NOT A OR B OR D OR B OR D.
Now when you have a NOT out and you want to
bring it inside we have to use what are called
Demorgan’s laws which we have already seen.
These are called Demorgan’s laws. So this
will become A AND NOT B OR D, this OR 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 OR B OR D AND NOT B
OR D OR B OR D.
Now we know that if you have NOT P or P that
reduces to 1 and it is always true and it
is a tautology. So this will become A OR B
OR D AND 1 that is true and that is nothing
but A OR B OR D. Now because of the associative
property of OR you can write it as A OR B
OR D without ambiguity. We can remove the
parenthesis here which is not necessary because
of the associativity of OR. Like that by using
these identities we can simplify logical expressions.
Let us consider some sentences in English
and try to convert them into logical notations
and also try to write down English sentences
from the logical notations. 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 town, R stands for I have
time. Now using logical connectives write
a proposition which symbolizes the following.
First we have, if it is not snowing and I
have time then I will go to town. How can
you write this in logical notation “if it
is not snowing?” For if it is snowing, the
logical notation is P, so it is not snowing
means NOT P. And the logical notation for
I have time is AND R. If this is so, then
the logical notation for I will go to town
is implies Q. So this sentence can be written
logically in this form as NOT P AND R implies
Q. The next one is I will go to town only
if I have time. So for this P implies Q can
also be read as P only if Q. So the logical
notation for I will go to town only if I have
time will be Q implies R.
The third sentence is a very simple sentence:
it is not snowing, here P stands for it is
snowing, so NOT P will stand for it is not
snowing. Next you have, it is snowing and
I will not go to town. What is the logical
expression for this? For snowing it is P and
for I will not go to town is NOT Q.
Q is I will go to town, so NOT Q is I will
not go to town. Like that these English sentences
can be written in logical notation. And if
you have a proposition how will you write
it in English? How will you interpret properly
and write it in English? Now write a sentence
in English corresponding to each of the following
propositions: Q is equivalent to R AND NOT
P.
How can we write this in English? This can
be read as if and only if. And what does Q
stands 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 R AND NOT P? What is R? R is 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 R AND NOT P. If you want
to write in 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? How will you write a sentence
which 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.
Then 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 can be written
in the form I will go to town only if I have
time then R implies Q must be written as,
if I have time I will go to town or equivalently
Q implies R AND R implies Q is equivalent
saying Q is equivalent to R. So this can also
be written in the form I will go to town if
and only if I have time. The last is NOT R
OR Q, again R stands for I have time and Q
stands for I will go to town, can be written
in the form it is not true that 
I have time or I will go to town. So like
this you can transform English sentences into
logical notations and if you have logical
notations you can write down the corresponding
English sentences.
You have to be careful when you use inclusive
OR or exclusive OR but usually either or would
refer to exclusive OR and other wise it will
be inclusive OR but you have to be careful
about this. Let us consider some more logical
identities; they are all tautologies 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. In addition P implies P OR
Q, see when you have P by adding something
the value is not altered so from P you can
conclude P OR Q. If you look at it as a pool
of inference from P you will be able to conclude
P OR 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 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 you have four rows and we have
written down the four possible values. For
P implies Q this is the truth value and we
also know this. Now P AND Q, P AND P implies
Q will be true only when P is true and P implies
Q is also true. So you find that the truth
value for this is, in these three cases it
takes the value 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
compound 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 1, it is a tautology. This is called
Modus ponens and when you write it as a rule
of inference you write like this, P implies
Q and from this you conclude Q.
This is what is meant by Modus 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
it means if you have P and Q that is P implies
Q and NOT Q, from this you can conclude NOT
P, this rule therefore NOT P is called Modus
tollens whereas this is called Modus ponnens.
And we have some more rules NOT P AND P OR
Q implies Q, this is called Disjunctive syllogism.
And P implies Q AND Q implies R implies P
implies R 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
is anding of two things and this is equivalence.
P implies Q and R implies S implies P AND
R implies Q AND S and this should be equivalence.
P is equivalent to Q AND Q is equivalent to
R would imply P is equivalent 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 may be I shall
give you the solution 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 or 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 a no answer.
A tourist comes to a fork in the road so this
is the situation. You have a fork, the tourist
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 Mr.Z standing at
the fork. What single yes or 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 tells 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 Z the inhabitant there may
be a truth teller or may be a liar. This person
does not know, the tourist does not know whether
he is a truth teller or a liar and he will
respond only with an yes or no answer, he
will not say anything more.
In that situation this tourist should ask
only one question, a single question for which
the answer will be a yes or no and by listening
to that answer like this. If it is yes he
will take the left road which is the correct
road, if it is no he will take the right road
which is the correct road. So what is the
single yes or no question he should ask? So
you must look at the four possibilities.
The person may be truth teller and the left
road may lead to capital, the person may be
a liar and the left road 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 right road may lead to capital.
So there are four possibilities and the single
yes or no question should take care of all
these things. Let us consider some more similar
problems.
Five persons A, B, C, D, E are in a compartment
in a train. A, C, 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 an enquiry is held.
And A, B, C, D makes 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,
D says I am innocent and 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 eight statements are true
and four of them are false. Assuming only
one person committed the murder. 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 true and four are false.
Now from these arguments or from these statements
how will you find out who has committed the
murder? Look at the first four statements
each one makes: A says I am innocent and B
says I am innocent and C says I am innocent
and D also says that I am innocent. Now only
one person committed the murder, so out of
A, B, C, D three of them must be saying the
truth and one is lying.
So there are eight statements: A is making
statement one and two, B is making statement
one and two and C is making statement one
and two and D is making statement one and
two. Out of these all four statements are
I am innocent out of which three of them are
true one is false. So out of the four, three
are true and one is false. So, in the remaining
four, three of them must be false and one
must be true 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 A says is true
then what B says is not true and if what B
says is true then 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 amounts to 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 and that is false. So D did not
commit the murder. What does C say, the second
statement of D 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 murder? B committed the murder.
In that case the first statement of A is true,
the first statement 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 and 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 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 tells the truth,
another is Mr.Y who always lies and the third
is Mr.Z who sometimes tells the truth and
sometimes lies, that is Mr.Z 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 are Mr.X, Mr. Y and
Mr. Z, they will buy you a drink. What yes
or no questions should the thirsty tourist
ask? The problem is like this: A person is
sitting here, the tourist is sitting here,
the waiter comes and he points out to three
people standing out there: 1, 2, 3 they are
standing in a row and the waiter tells the
tourist, 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 says yes who always lies, third person
is Z 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 and point out who should answer
the question and then depending upon the answer
he can ask the second question. So again he
can ask the second question and point out
whom should answer the question and similarly
again he can ask the third question. After
getting the answer for all the three questions
the answer should be only in the form of yes
or no.
So if it is correct X will say the correct
answer, for Y if it is yes he will say no,
if it is no he will say yes, for Z without
looking into that he will randomly say yes
or randomly say no. So what are the three
questions he should ask so that at the end
he is able to find out who is Mr. X , Mr.
Y and who is Mr. Z. Actually this is not a
very easy problem, this is slightly difficult.
But the first question is important. The first
question should be asked in such a way that
you eliminate Z.
Actually it is easier to deal with a person
who always tells the truth or who always lies.
It is difficult to deal with the person like
Z who sometimes lies and sometimes tells the
truth. So here we have to find out who is
Z and eliminate him. And after eliminating
Z the second and the third question can be
conveniently asked. Think about the answer
for this problem and shall lead you to another
similar problem.
Brown Jones and Smith are suspected of income
tax evasion. They testify under oath as follows:
Brown says Jones is guilty and Smith is innocent,
Jones 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 or who are all innocent
and who are all guilty?
Assuming the innocent told the truth and the
guilty lied who is and who is innocent? Look
at the statements they make, we have to transfer
all of them into logical notations. 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 is
Smith.
So the contrapositive of that will be if Smith
is not guilty Brown is not guilty and so Brown
is innocent. So the answer to the first portion
is Brown is innocent, Jones 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
such as existential quantifiers and inversal
quantifiers and further concepts in logic.
