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

[Music]
[Music]
[Music]
[Music]
this course is about discrete
mathematical structures it is a
theoretical course intended for we take
our B students in computer science in
the second semester and what are the
things we are going to study in this
subject so first of all what is discrete
mathematics and what are the topics
which are to be covered here discrete
mathematics is study of discrete
structures which are abstract
mathematical models dealing with
discrete objects and the relationship
between them the district's objects
could be likes it's permutations graphs
FSA etc we'll see in a minute what are
the topics which are to be covered here
and why do you want to study discrete
mathematics and why should one study the
subject the reason is in many fields in
computer science basic mathematical
concepts will be used and in any books
on them when such a concept is
introduced
they will not explain it in detail but
briefly mentioned a few lines about it
better for a student to understand the
subject completely that may not be
enough at the same time only not going
to depth in these subjects also one
shouldn't not lenore or need not learn
these subjects as a mathematics student
would learn algebra or analysis you want
to know something about its topic to a
decent depth
and that will help to understand the
other subjects in computer science in a
better way the aim of this course is not
only make people learn about these
topics but also develop the habit of
thinking mathematically the student
should develop to think in a
mathematical manner that is the aim of
this course what are the applications
are the what are the fields in which
this these concepts will be used
they are plenty in fact in each and
every subject in computer science
somewhere or other these concepts will
be used for example when you want to
study programming after writing a
program you would like that it is
correct you want to prove it so proving
programs correct is a topic which will
be studied in this course it will help
you to write correct programs and in
artificial intelligence a lot of ideas
about logic will be used Prolog it's a
logic programming language where there a
solution principle is used and we will
learn about this in this subject and in
computer networks lot of concepts about
graph theory and finite state automata
are used so that will be very useful
that in fact you can find that in any
field you will have a few concepts from
discrete mathematics which will help you
to understand the subject in a better
manner in compilers you learnt the
finest rater automatic concepts will be
used grammar concepts will be used hash
functions will be used and these are
studied in this subject
and now what are the topics which will
be covered in the subject we'll be
studying about logic sets relations then
functions graphs combinatoric s--
recurrence relations algebras and FSA
the level of the subject will be like
this first nine lectures will be devoted
to logic and it's applications then
three lectures will be on sets actually
this subject does not presuppose any
prior knowledge from this road and
accept a reasonable mathematical
maturity expected of a high school
student that is the only thing we assume
and proceed with this subject in fact
after learning this subject the student
should be able to think more
mathematically and also should have
acquired a basic knowledge about these
topics then we go on to relations in
relations first we have lecture 13 then
afterwards we shift two graphs from
lecture 14 to 17 then again come back to
more properties of relations from 18 to
23 then the last lecture will be about
lattices it is also about partially
ordered sets we will learn about certain
basic facts about graphs in lecture 14
to 17 then we learn about the functions
in lecture 24 to 26
then a few lectures on combinatoric
where we will be studying about
pigeonhole principle permutation and
combination and generating functions
the recurrence relation is a another
topic
it is of importance especially in
algorithmic analysis we spent three
lectures on them then algebras we'll
study a little bit there we study about
groups semigroups rings etc and about
financial Tata my time we have two
lectures where we study only the basic
principles of finite state automata we
shall give some reference books for the
subject some of them are new some of
them are old but there have been recent
additions of them elements of discrete
mathematics by CL lu and the second one
is discrete mathematical structures with
applications to computer science by
Tremblay Manohar these are standard
books discrete mathematics in computer
science by Stinnett and Mike Lister is
another book discrete mathematics and
its application by Rosen logic and
discrete mathematics by grassman and
Tremblay this has come some concepts
about Prolog and application of logic to
that introductory combinatorics by bro
Rd for topics on combinatorics
this book can be used modern applied
algebra may be covered with but it's a
world book but it has got some good
concepts about lattices final state
automata mathematical theory of
computation by mana this book will be
useful for proving programs corrected
introduction to combinatorial
mathematics by Leo this is an old book
but still it has got some very good
topics permutation combination
generating functions recurrence
relations etcetera then for automata
theory this book can be used
introduction to automata theory
languages and computation by hop craft
motwani and will
these are only a few books there are so
many other books any student using
studying the subject can use the
prescribed book by the respective
university our College now we shall go
on to the first topic logic logic is a
very useful topic every student in
computer science should learn this topic
because it is applied in proving
programs correct in databases where you
study about relational algebra and
relational calculus and also in
artificial and intelligence about
reasoning and things like that so first
coming to logic there will be nine
lectures on logic
they are divided like this the first two
lectures will be devoted to
propositional logic then we go on to
predicate logic then logical inference
then the solution principle then methods
of proofs normal forms and one topic on
one lecture on proving programs correct
so let us start first with logic and
proposition
what is proportion logic so for that
first we have to start with what is a
proposition in English language we talk
about sentences we talk about assertions
we talk about orders questions and so on
what is a proposition first of all it
should be an assertion an assertion is a
statement it is different from asking a
question or giving an order a
proposition is an assertion which is
either true or false but not both so you
must be able to associate a truth value
with an assertion truth value the truth
value will be false are true usually you
denote it by false by 0 and true by 1 so
any sentence any assertion to which you
can associate a truth value is called a
proposition consider the following
examples the following are propositions
for this is a prime number it is an
assertion but it is a false statement so
the truth value associated with 4 is a
prime number is false then take the next
sentence 3 plus 3 is equal to 6 again it
is an assertion and it is a correct
statement so the truth value associated
with that is true the moon is made of
green cheese or the moon is made of
cheese
this is again an assertion and a wrong
statement so the truth value associated
with that is false
let us see what are not propositions
consider the statement X plus y greater
than 4 is it true or false it depends on
what value you are going to give for X
and value if you give X the value 2y is
the value 2 then 2 plus 2 is greater
than 4 is not correct or if I give the
value X is equal to 3 y is equal to 4
then it takes the value 3 plus 4 is
greater than 4 that is 7 is greater than
4 which is correct so depending on the
value you give for x and y the statement
takes a true or a false value it does
not have a unique value it depends on
the value are going to give for the
variables x and y x and y are called
individual variables so you cannot
associate a unique truth value to this
next take the sentence x is equal to 3
here you find that you cannot associate
a truth value to this if you give the
value 3 to X it will be true
if you give some other value to X it
will not be true so again this is not a
proposition take the next one are you
leaving this is not an assertion a
proposition should be an assertion all
you're leaving is a question and it is
not an assertion so it is not a
proposition take the next one
by 4 books this again is not an
assertion is no order go and buy 3 books
this is an order and not an assertion so
it cannot be a proposition so whenever
something is not an assertion to the
question not an order it cannot be a
proposition but in special cases there
can be assertions which are not
propositions
for example they consider this sentence
this statement is false this is an
assertion is it the proposition it is
not a proposition because you cannot
associate their truth value to this if
it is true it is false if it is false it
is true so you cannot associate a true
or a false value with this statement
this is called a paradox this is called
actually a liar paradox is called the
layer pannel ox and such a statement
even though it is an assertion is not a
proposition because you are not able to
associate the truth value with that this
as you have variables individual
variables x and y 2 which we associated
numbers you can talk about a preposition
variables a propositional variable
denotes an arbitrary proportion with
unspecified truth value P Q R there are
propositional variables and you can
assign a proposition to them P is just a
variable propositional variable just as
we assigned the value 4 to X you can
assign the value of a proposition to
their variable P similarly you can
denote this as propositional variables
and you can assign propositions as
values to them then when you have proper
share variables are actual propositions
also you can connect them with logical
connective there are several connectives
first we shall study 3 of them and our
and not
consider the proposition john is six
feet tall and the proposition
q there are four curves in the model
then the compound statement P and Q is
John is six feet tall and there are four
cows in the bottle when is this true P
and Q will be true when both P is true
and Q is true so we have a truth table
for them so and is denoted by this
symbol and the truth table for that will
be P Q P and Q the possibilities are
both can be false or P can be false and
Q can be true this can be true and this
can be false and both can be these are
the possibilities and both are false the
compound statement will be false
when one is false also the compound
statement will be false but when both
are true the compound statement will be
true usually we denote false by 0 and
true by 1 so the truth table will be
like this P Q P and
zero zero zero one one deal one one and
in these three cases it is zero it is
this one in this case so the compound
statement P and Q will be true only when
both P is true and Q is true in all the
other cases it will be false what about
the connective are PR q If P denotes
this sentence and Q denotes this
sentence PR q will denote the sentence
John is 6 feet tall are there are four
curves in the bomb when can you say that
this is true when one of them is true
the compound statement will be true or
when both of them are true also the
compar segment will be this is called in
to see our inclusive r and the truth
table for that will be like this PQ p RQ
0 0 0 1 1 0 1 1 0 denotes false and 1
denotes true and when both of them are
false this is false when one of them are
both of them are true this will be true
this is the truth table this is called a
truth table for us and for the unary
operator not P and not P when P is false
not P will be true and P is true not P
will be false so what is the statement
not be John is not 6 feet up that will
be the statement for not P so we are
studying the operators and are not there
is one more operator called the
exclusive are an assertion which
contains at least one proposition
variable is called a proportional form
so when you connect to propositional
variables by and R it is a proffesional
form we can also use the exclusive or
operator exclusive R means the truth
table for that will be like this
zero one one zero one one in the
exclusive our case it is true only when
one of them is true and other is false
if both of them are true or both of them
are false it is false so when you say
something like that
John is six feet tall
there are four cows in the barn both can
be both statements can be true and the
compound statement can be true but in
some cases like say Sudha is wearing a
sari and Sudha is wearing a blue
churidhar something
and if I say Sudha is wearing a sari our
Sudha is wearing a blue churidhar both
of them cannot be true at the same time
only one can be true the other will be
false so in such cases you use exclusive
are usually when you say either this our
that that means exclusive or when you
just say our it means inclusive our but
you have to be very careful in sometimes
they are used in a slightly ambiguous
way so when you want to transform an
English sentence into logical notation
or transform some logical formula into
English sentence you have to be very
careful whether you are using inclusive
or exclusive are usually exclude
exclusive or means you must say either
are inclusive are you save just are
without that either and any
propositional form it is connecting
variables it is called a well formed
formula well formed formula of
proportional logic well-formed formula
it is denoted by W PFF usually call s
wff so P and Q is a well-formed formula
p RQ is a well-formed Butler we
exclusive RQ is a well-formed formula so
P exclusive R will be denoted like P
exclusive are
apart from these operators there are two
more operators which are used in logic
one is called the implication and
another is called the equivalence
what is implication let us look at this
P implies Q it is denoted like P implies
Q in some books it may be written like
this and some in some books they rarely
use this sort of an arrow for P implies
Q so when you take a book you must be
clear what sort of a notation they are
using similarly not P is usually denoted
like this sometimes it is also denoted
like this so when you see a book you
must be careful what notation they are
using so in this case B is called the
premise hypothesis our antecedent and Q
is called the conclusion or consequence
and what is the truth table for P
implies Q P implies Q you have 0 0 0 1 1
0 1 1 then when both are false it is
true when P is false and Q is true it is
true when P is true and Q is false it is
false when both of them are true it is
true there is a slight problem here it
is not a problem but you must feel
convinced about this truth table usually
when we say logic or what we study is
Greek logic which was formulated by
Aristotle Socrates and
Greek philosophers in such logic this is
the truth table for implication the
antecedent and the consequent need not
be related at all they may be quite
unrelated statements like if the moon is
made of cheese then earth is not found
it could be something like that there is
no relationship between the antecedent
and the consequence but the compound
statement is true because this is of the
form false implies false and for that in
the truth table the first line of the
truth table tells you if P is 0 and Q is
0 P implies Q will be true
Greek logic allows that usually in
Indian logic you look at Bay Area but
our buskerud exploration inaudible does
work such things are not allowed usually
as antecedent and the consequence will
be related for example something like
this this you can very easily see if I
fall into the lake I will get red
obviously the premise and the conclusion
are the consequence are related and you
can see the correspondence between them
but generally in the truth table you
must also give a valid the compound
statement even though the president
promised and the antecedent are not
related so the implication this you must
remember very well the implication is
true when the premise are the antecedent
is false are the consequence is true it
is false on
in the case when premise is true and the
conclusion is false or the antecedent is
true and the consequences was only only
in that case it will be false either
three cases it is taken to be true this
can be read in several ways you can read
it this if P then Q P only if Q P is a
sufficient condition for Q q is a
necessary condition for P Q Y of P Q
follows from P Q provided P Q is a
logical consequence of P Q whenever
people these are different ways of
saying this and you would have said it
about sufficient conditions and
necessary conditions in high school
level and any many theorems where the
statement will be in the form if then
for example you decided the Pythagoras
theorem if ABC is a triangle right
angled at B then AC square is equal to a
B square plus BC square so the statement
of the theorem is of the form if
something then something and sometimes
you talk about the converse of a theorem
sometimes the theorem will be proved in
a slightly different manner when we
study methods of proof we'll go into
that in depth but generally the converse
of a theorem is denoted as Q implies P P
implies Q is a comp a statement and the
converse is Q implies P is the converse
and not Q implies not P is called the
contrapositive
so you have this P implies Q Q implies P
is the converse not Q implies not P is
the contrapositive so suppose Pythagoras
theorem is if ABC is a triangle right
angle at B then AC square is a B square
plus BC square what would be the
converse of the theorem Conners also you
would have studied in school if in a
triangle the AC square is a B square
plus BC square then the triangle is
right angled at B so there is a Congress
in this case is it so happens that both
the theorem and the converse are true
but several situations may arise where
the theorem may be true but the converse
need not be true because P implies Q it
does not mean Q implies P is two whereas
the contrapositive not Q implies not P
will be true whenever P implies Q is
true let us draw the truth table and see
this
so you have P you have P Q P implies Q
not P not Q not Q implies not P so
consider this table you have the
possibilities 0 0 0 1 1 0 another thing
is you must note before going into that
let us see that if there are variables
say P Q R yes like that in the truth
table there will be one column for each
one of the variables and there will be
one row for each assignment of the
variable each variable can be assigned
the value true or false that is 0 or 1
so if there are four variables they'll
be two into two into two into two 16
possibilities so there will be 16 rows
in the truth table in general when you
deal with in proportion variables and
you want to study the truth table
involving them about foreign expression
involving them there will be n columns
first n columns will be first n columns
will be 4 very this
and their turn there will be more
columns here there are two variables two
columns are for the variables and here
you consider every assignment every
possible assignment for the variables so
there will be two power n possible
assignments possible assignments of
truth values to the variables and so
there will be 2 power n rows and if you
look at them carefully they are
representing binary numbers 0 1 2 3 so
they will represent binary numbers from
0 to 2 power n minus 1 now coming to
this this is not Q implies not P is the
contrapositive P implies Q is true here
it is false here what about not P not P
will be true if P is false it will be
false when P is true what about not you
if Q is false this would be true if Q is
true this will be false and when is the
implication false when the premise is
true and the conclusion is false so in
this case it will be false 1 and 0 in
the if the premise is false the
conclusion will be true I mean the
result implication will be true if the
ant if the consequence is true then also
it is true here both are 1 so it will be
1 or 2 1 represents true so you see that
these two columns are identical and so P
implies Q is the same as saying not Q
implies not P many terms you will make
use of such statements for example if a
prime number is not a perfect number so
you may say it is a if X is a prime is
it is not a perfect number are you may
also say a perfect number is not a prime
it is saying the other way around in the
contrapositive manner okay so next thing
is equivalence you also have a logical
connective equivalence which is denoted
by a double arrow with arrow like this
this is called equivalence this is read
as P is equivalent to Q R P if and only
if Q R P is a necessary and sufficient
condition for Q then the Li you read is
SP is equivalent to R P if and only if Q
this is also correct P is a necessary
and sufficient condition for Q when is
this compound statement true
this compound statement is true when
both P and who have the same values when
both of them are false are when both of
them are true the compound statement
takes a value two if one of them is
false and the other is true then it
takes the value false so this is the
truth table for equivalence those who
have learnt a little bit about boolean
algebra you will see the similarity
between professional logic and boolean
algebra in boolean algebra you also
study about two operators an end and not
that we will not study in logic instead
in logic we study equivalence and
implicit
now let us take some examples constrict
the truth tables for Q and not P implies
P and P and Q or not R is equivalent to
P so I say I mentioned to you earlier
when you have K variables there will be
K columns for each of the variable then
some more columns but there will be 2
power K rows representing the
assignments and they will be
representing binary numbers from 0 to 2
power K minus 1 now let us draw the
truth tables for these two expressions Q
and Q and not P implies P there are two
variables P and Q so there will be two
columns for them and you will give the
value 0 0 1 0 0 0 1 1 0 1 1 for them
then
not P Q and not B then the whole
expression Q and not P in place
now when is not be true when P is false
not P is true and when P is true not P
will be false and the ending of that
when you end when both of them are true
this is true in other cases it will be
false now this is the premise and this
is the consequence when is the
implication true when the premise is
false the implication will be and in
this case the premise is true and the
conclusion or that consequence is false
so in that case you know that it is
what's so this is the truth table but
you can not be in place P now let us
take the other one
P and Q or not R in is equivalent to P
there are three variables P Q R so there
will be three columns for them and there
will be all possible assignments for
them that will be 0 0 0
usually that you write them in this
order so that they are representing
number 0 1 2 3 etcetera
1 0 1 1 1 0 1 1 1
now what is a statement the statement is
this I will write here P and Q or not R
is equivalent to P so next you must have
a column for P and Q you must have a
column for not R so when s P and Q true
when both of them are true when one of
them is false it will be false so you
get this for P and Q when is not of are
true when R is false and it is false
when R is true so you get 1 0 1 0 1 0 1
0 now you have the expression for P and
Q are not apar
you are owning this and this when you
are when one of them is true that the so
it is true so when one of them is true
it is true and both of them are false it
is false when one of them is true it is
true when both of them are false it is
false in these cases in this case it
will be true in this case it will be
false true and true then the last column
is like this P and Q or not R this is
equivalent to P when not true expression
is equivalent when they take the same
value 0 0 or 1 so you have to compare
this and this when they are the same it
is true here 0 0 it is true but here it
is 0 and 1 so it is false 0 & 1 it is
false 0 & 0 it is true
1 and 1 it is true 0 & 1 it is false
1 & 1 1 and 1 so this is the truth table
for P and Q or not R is equivalent to P
so for e given any expression you can
draw the to table and find out when the
whole expression will be true and when
the whole expression will be false and
so on
now a tautology is a propositional form
whose truth value is true for all
possible values of its propositional
variables sometimes an expression may be
such that always it takes the truth
value true for example PR not be
considered this expression PR not P
there are two possibilities we can be
true RP can be false when P is true this
compound expression is true because one
of the component is true when P is false
not P will be true so this compound
expression will be true because one of
the components is true so whether you
give the value of zero or one our faults
are true to P this compound expression
is always true such an expression is
called a tautology a tautology is a
proportional form whose truth value is
true for all possible values of its
propositional variables now the way
around a contradiction or an absurdity
is a propositional form which is always
false take this expression P and not P
there are two possibilities P is true or
P is false if P is true not P is false
so this expression will be fast because
and will be true only when both of them
are true it is not fun possible for P
and not P to be both true either one of
them will be true in any case one of
them will be true the other will be
false the possibility is this is true
this is false or this is false this is
true in any case this compound
expression P and not P will always be
false such an expression is called a
contradiction a proposition form which
is neither a tautology now or a
contradiction is called a contingency
these examples which we consider Q and
not P is equal to the
in place P and Q and P are not R is
equivalent to P these two are examples
of contingencies some cases they are
true some cases they're false so they
are examples of contingency given that
propositional from it is always possible
to find out whether it is a tautology or
not because you can't always draw the
truth table and if the last column is
always 1 1 1 then it is a tautology the
last column is always 0 0 0 it is a
contradiction sometimes it is 0 and
sometimes it is 1 then it is a
contingency then we have lot of logical
identities this logical identities can
be used in simplifying logical
expressions look at this one bow and let
us see one by one P is equivalent to say
PR people when you say PR P it is not
necessary to say it price is enough to
say once this is called the idempotence
of r then if you have P and P it's not
necessary to write like this it is
enough to say like this so P is
equivalent to P and P this is called
idempotence offhand
so whenever is an expression you get
something like P and P can replace it by
P then you have the commutative laws
it's equivalent to saying Q or P is
equivalent to saying PR q you can
interchange the variables doesn't affect
the meaning either this or that ARB is
BRE so PR Q is same as Q or P this is
called commutativity of similarly you
have commutativity for any P and Q is
equivalent to saying Q and P
and you have associative loss p RQ then
R that is first you are PR Q then you
take R and combine that is equivalent to
having P R Q or R and P and Q and R is
equivalent to saying P and Q and R this
is called associativity ah
and in general we are try to whenever
you write an expression you try to use
parentheses there is no priority but
generally not has higher priority then
and then if you use only these three of
them not has higher priority than end
then not because you can write not P and
Q this is not P and Q that is equivalent
to saying not P and Q you can write
without that parenthesis it is not not P
and this is different if you want to
write like this you must put the
parenthesis in a proper way
so we see that but P and Q and R you can
write without parenthesis because of
associated that we group this first R
group this first is immaterial when both
the operators around without any problem
you can write like this that is what is
meant by associated to your tough and
similarly for all whereas you can
realize that P implies Q in place if you
want to write like that P implies Q
implies R this is different from saying
P implies Q implies up you cannot say
something like this P implies Q implies
R because you do not know whether you
mean this R that you can draw the truth
table and verify that this has got a
different value this has got a different
one they are not the same so you cannot
write something like this
you have to put parentheses wherever his
either
you mean this are you mean that
so implication is not associated then
there are de Morgan's laws which are
very common and very useful also not of
PRQ you can bring the not inside and
that will mean not P and not Q you can
again draw the truth table for this and
for this and see that they will be
identical the columns representing them
will be identical so when you bring the
not inside are become centered similarly
not of P and Q will be not of P or not
of Q so even you bring the not inside
and becomes R R becomes and these are
called the Morgan's plus then you have
distributive laws and distributes over R
that is P and Q R R is equivalent to
saying P and Q or P R R so you can
distribute and over R and write like
this sometimes you can use the
distributive laws in the reverse
direction also another thing is are
distributes over and P R PR q and r is
the same as saying P R Q and P R I again
here also the distributive law sometimes
you can apply in the reverse then you
have these rules in playing when one of
the operands is true or false P R 1 is
always 1 so this is a compound statement
but when one of the operands is true the
compound statement is always true
this we know so even when one of them is
true this is true and now we have taken
one operand that's true only so this is
1 P and 1 if P is true this will be true
if P is false this will be false so P
and 1 has the same
us P similarly for our PR 0 if P is true
this will be true if P is false this
will be false so P our zeroes take the
same value as speak and when you end
with a 0 P and 0 because one of the
operands is false the compound statement
will be false so you will have P and 0
is the same as 0 or false PR not P is
always 1 always true this is called a
tautology this is what we have seen
earlier P and not P is called a
contradiction or AB absurdity it always
takes the value 0 and you have double
negation saying P is equivalent to not
of not of P so if you use negative 1
negative in price it is equivalent to
the original statement there are some
more statements like this we shall
briefly look into them we shall look
into them in more detail in the next
lecture but just we have a brief look at
them P implies Q you can write it as not
P R Q this is equivalent to saying P
implies Q and similarly P is equivalent
to Q you can equivalent we say it s P
implies Q and Q implies P this rule is
also true P and Q implies R is
equivalent to saying P implies Q implies
R and P implies Q and P implies not Q is
equal into saying not V this is called
absurdity and this is used in proof by
contradiction this is the most commonly
used this we have seen earlier P implies
Q is equivalent to saying not Q implies
not P which is the contrapositive so on
so to this class we have learnt a few
logical connectives
and how to write the truth table and so
on we shall continue with this concepts
in the next lecture
[Music]