Normal Forms - Discrete Mathematical Structures Video Lecture - Computer Science Engineering (CSE)

ah-ha-ha-ha hey does speed Allah Allah
Allah Allah
II
it's not
you
you
you
today we shall consider about normal
forms already we consider a little bit
about what is meant by a disjunctive
normal form and conjunctive normal form
and conjunctive normal form we took as
class form and we used it in the
solution principle but again we shall go
through those definitions and also what
is meant by principal disjunctive normal
form and principal conjunctive normal
form and in the first order logic what
is meant by prin ex normal form so let
us recall some definitions which we
learnt earlier a product of the
variables and the negations in a formula
is called an elementary product for
example something like P and Q and not R
something like this is called an
elementary product similarly a sum of
the variables and their negations is
called an elementary sum for example
something like P or not P or Q or not R
something like this is called an
elementary sum
now you can see that a necessary and
sufficient condition for an elementary
product to be identically false is that
it contain at least one fair of factors
in which one is the negation of the
other suppose I have an elementary
product like this and if it some it is
like this say if it contains one pair of
variables or one pair of letters where
one is the negation of the other you
have Q and not Q then this becomes
identically false because you know that
Q and not Q is zero that is false and
something and zero is zero so an
elementary product is identically false
if it contains two literals where one is
the negation of the other and the other
way round
a necessary and sufficient condition for
an elementary sum to be identically true
is it contains at least one pair of
factors in which one is the negation of
the other so suppose I have something
like this P or not P Q or not or
something like that then you have only
trill and the negation of the variable
manager literal so you have one variable
and also the negation of that this we
know that is a Tata GPR RP is 1 so 1 or
something that will be 1
the any formula involving the
connectives using propositional
variables is called the wff or well
formed formula of propositional logic
now any well formed formula of
propositional logic you can bring into
conjunctive normal form on distinctly
normal form first let us define what is
meant by that first let us take
disjunctive normal forms a formula that
is a well-formed formula which is
equivalent to a given formula and which
contains the sum of elementary products
is called a disjunctive normal form of
the given formula so it should be of
this form something like no it should be
the sum of elementary products
okay so a sum of elementary products is
called a disjunctive normal form it will
be something like this or again
something now any well formed formula we
can bring into disjunctive normal form
let us take some examples first let us
take this we want to bring this
well-formed formula into disjunctive
normal form how do you go about doing
that first of all you can convert
implication into naught so this will
become not not of P or not of Q P
implies Q you can write s naught P R Q
so this can be written as not of this R
P is equivalent to naught Q now P is
equivalent to naught Q you can write as
suppose you have P is equivalent to Q
this is equal to saying P and Q are not
P and not Q this we have either both of
them must be true or both of them must
be false
this we know so using this rule here you
will get this portion is as it is this
we can write as P and not Q
P and not Q are not P and not not P and
not of not Q so using demorgan's laws
this will become P and Q because this
will become not of not of P and not of
not of Q maybe I will write that ripples
or not of not of P and not of not of Q
using demorgan's laws and R and this
will be P and not Q and this will be
there should be a bracket here also
not pee and
so this is equivalent to saying P and Q
are P and not Q or not P and Q so this
is an elementary product this is an
elementary product and this is an
elementary product and you have a sum of
elementary products so this is a
disjunctive normal form let us take one
more example let us convert this into
again disjunctive normal form how do you
go about doing this P implies Q and R so
implication you can convert into not P R
Q so this will be not P R Q and R and
this one again you can write like this
not of not of P R not Q and not R
so this again you can write as not P R Q
and R and P are not Q and not R now you
can use distributive laws we can write
this s not P R Q and R and P are not P R
Q and R
and not Q and not
again here you can use distributed loss
and this will be not P and P R Q and R
and P
are here again again use distributive
loss and this will become not P and not
Q and not R
are
Q & R and not Q and not
we can remove unnecessary parentheses
and write it in the proper form so here
it is an elementary product elementary
product here again elementary product
elementary product so if you rewrite
this it will become not P and P R Q and
R and P R this one will be not P and not
Q and not R and this will be Q and R and
not Q and not R so this is the
distinctive form normal form again I
want to mention that distinctly formal
normal form or conjunctive normal form
is not unique for example this you can
you know that Q you have Q and not Q so
this whole term is 0 so it can be
omitted so it is not unique but any
formula you can bring it to the
disjunction of elementary products next
we shall consider conjunctive normal
form or CNF that is the one we used
earlier
what is a conjunctive normal form a
formula which is equivalent to a given
formula and which consists of a product
of elementary some is called a
conductive normal form of the given
formula so it will be like this it will
be something like okay P R Q and
something
R
this is called conjunctive normal form
it is the product of elementary so each
one is an elementary sum and you have
and here product of element sums again
any well formed formula of the
propositional logic you can bring it to
conjunctive normal form let us take one
more example here so this is the formula
and we want to bring it to conjunctive
normal form so this you can write as not
not of P or not of Q using implication
rule for implication P implies Q can be
written as not p RQ so not of this R
this one you can write as P implies not
Q
and not P P P implies Q and Q implies P
so not Q implies
using demorgan's class this will become
P and Q are
not P R naught Q and not of not of Q R P
key here again I am using their rule not
P implies Q is not P R cube and he same
rule here so what will you get you will
get P and Q are not P R naught Q and
this will become not tuffnut of Q is Q
so you will get P R Q you can use
distributive laws now so this will
become P R
not pee
are not Q and P are Q and Q
not P or not Q and P R Q
so if you expand this using the
distributive laws you will get P or not
P or not Q and P R P R Q and this one
will be can become and okay how omitted
there is are here which
q are not P or not Q and Q are T are
so this is an elementary some this is an
elementary some this is an elementary
some this in elementary some and you
have the product of elementary sums this
is a conjunctive normal form now you can
see that because you have PR not P this
will reduce to 1 and because you have Q
or not Q this will reduce to 1 and this
will reduce to P R Q and because P R P
is P and Q R Q is Q so ultimately the
whole thing will reduce to PR Q if you
simplify if you want to simplify this
will reduce to this but we are not at
present interested in that this is the
conjunctive normal form so any well
formed formula of the propositional
logic can be brought into either
disjunctive normal form or conjunctive
normal form now we will consider prints
triple distinctive normal forms let us
take two propositional variables P and Q
now consider the terms P and Q are P and
not Q or not P and Q and R not P and not
Q they are called a min terms there are
four min terms here P and Q cementum P
and not Q cementum not B and Q is a min
term not P and not Q is a min term in a
min term every variable will be present
only once either in the negated form or
in the non negative form so if you have
two variables it is the conjunction of
two literals they can be negated or non
negated now what is a principal
distinctive normal form for a given
formula an equivalent formula consisting
of disjunction of minterms is known as
its principal disjunctive normal form
such a for normal form is also called
the sum of products canonical form so
you should have disjunction of minterms
earlier we had disjunction of elementary
products here we have disjunction of
minterms
so let us see how to convert a given
formula into principle distinctive
normal form let us take some example now
consider this example P R naught P
implies not Q implies R this you can
write as P R not P implies this one by
changing into the form you can write it
as not of not of Q is Q or R so this you
can write as P R again not of not of P P
R Q R R so this will become P R P R Q or
R it is nothing but P R Q R
now this is a this is a sum of
elementary products but each one should
be a midterm this is not a midterm so
you have to convert this into a midterm
for which you have to add the variables
Q and R now you know that P you can
write like this P is P and Q are not Q
because Q are not Q is 1 and P and one
is P so we can write like this
and our R naught R and then if you
expand using distributive laws this will
become P and Q and R are P and Q and not
R R
P and not Q and R R P and not Q and not
so you will see that each is a minterm
this is the minterm this is the minterm
this is the minterm position so P is
equivalent to these form in terms some
of their form in terms similarly you can
write for Q also Q will be equal to P
and Q and R are not P and Q and R R P
and Q and not R are not P and Q and R
time so you have to provide the missing
variables here you have only Q P and R
as missing so you have to provide them
in all possibilities so you have P R
naught P R P naught R naught P naught R
like that you have to provide similarly
R also you can date ultimately the whole
formula will be equivalent to we can
omit repetition P and Q and R is there
here also it is there the whole formula
will become P and Q and R R P and not Q
and R are P and Q and not R R P and not
Q and not R are not P and Q and not R
not P and Q and R are not P and not Q
and
so out of the eight possibilities of
combining them if if you each variable
should be present in the midterm either
in the negated or in the non negated
form so with three variables you can
possibly have eight min terms and in
this formula out of the eight seven are
present so this is the way you convert a
given well-formed formula into principal
disjunctive normal form this is also
called sum of products each is a product
and you have the sum of them now there
is a way of writing this usually you
write not P or not Q or not or not RS 0
0 0 not representing 0 for example P P
and Q and R s 1 1 1 P and not Q and R
I'm sorry this is end this is the end
P not Q and R this you can write s101
like that so the eight possible min
terms you can represent by binary
numbers from zero to seven so in this
case what will this represent this will
represent 1 1 1 that is 7 and this will
represent 1 0 1 that is 5 and this will
represent 1 1 0 that is 6 and this will
represent 1 0 0 that is 4 and this will
represent 0 1 0 it is 2 and this will
represent 0 1 1 that is 3 and this will
represent 0 0 1 that is 1 so if you
allow the minterms
to be represented from 0 to 7 in this
case in general if you have n variables
the min terms you can represent by
integers from 0 to 2 power n minus 1
so if you do that you represent the
principal disjunctive normal form as
Sigma for example this one we can
represent as Sigma 1 2 3 4 5 6 7 with
two variable suppose I have two min
terms P and Q not P and not Q and a
principal disjunctive normal form like
this how will you represent this there
are only two variables they can be
represented from 0 to 3
and this will represent 3 1 1 that is 3
and this will represent 0 0 that is 0 so
this whole expression you can write as
Sigma 0 comma 3
next we shall consider principal
conjunctive normal form we shall first
define what is meant by a max term for a
given number of variables the max term
consists of distinctions in which each
variable or its negation but not both
appears only once so suppose you are
having variables P and Q with P and Q
what will be the max terms P R Q not P R
Q P R naught Q and not P or not Q these
are called max terms they are
disjunction of literals where each
variable is present in the negated or
non negative from form but not in both
forms so any formula you can bring into
principal conjunctive normal form
what is principal principal conjunctive
normal form for a given formula an
equivalent formula consisting of
conjunctions of Max terms only is known
as principal conjunctive normal form and
this is also called product of sum scan
achill form and any formula can be
brought into principal conjunctive
normal form let us see how we can do
that the earlier example which we
considered this one reduced with this
then we added extra variables to make it
the principal disjunctive normal form
now look at this this is a max term with
three variables this is a maximum so the
whole thing reduces to just one maxed in
this example let us consider one more
example Q implies P and not P and Q this
you can write as not Q
and not pee and
you
so this is not Q R P this is a max term
and not P and Q now you have to convert
them into max terms so not P you can
write s not P R
q and nasty this is zero so not P R zero
is not P and this one using distributive
loss will become not P or Q and not P R
naught Q similarly Q can be written as P
and not P R Q you have to provide the
missing variable like this that is equal
to using distributive laws P R Q and not
P so the whole formula reduces to not u
RP that I will write as P R naught Q
using committed a loss not P this term
becomes like this not P P R naught Q and
in stuff not P you have to write these
two terms not P or Q and not P or not Q
and instead of Q you have to write these
two terms P R Q and not P R
now you can see that not PRQ is repeated
twice it is not necessary to write twice
so probably you can remove this this is
repeated so it so you have the
conjunction of max terms each is a max
term and you have the conjunction of Max
term this is the elementary this is the
principal conjunctive normal form now
the notation for that is so a principal
conjecting normal form is a product of
max terms so with two variables i have
the max terms like no P not P or not Q
not P R Q P R naught Q P R Q and this
you can represent in binary like 0 0 0 1
1 0 1 1 representing their numbers from
0 to 3 so if you look at the last one
which we consider all the four terms are
present here all the four max terms are
present so this can be represented as
product 0 comma 1 2 3 so this is the
notation used now with three variables
again you can have the Mac stem
represented by 0 to 7 and if you look at
this one this represents the max term 1
1 1 or 7 so the whole formula can be
represented by PI 0 suppose I have P R Q
or not R with 3 variables and not B
our cue our our and not P are not a not
Q or R suppose a formula consists of
grease these three max terms this will
represent 0 0 sorry 1 1 0 and this will
represent 0 1 1 and this will represent
0 0 1 so the whole thing can be written
as pi of 1 comma 3 comma 6 the formula
you can write as PI 1 comma 3 comma 6 so
this is another notation for writing the
principal conjunctive normal form as we
consider for principal distinctive
normal forms next we have to consider
the next normal form so far we have
considered only propositional logic we
then use quantifier setup now if you use
quantifiers how will you write it in a
normal form what is the normal form for
first order logic
for first-order logic the normal form is
called predicts normal form and the
definition is like this a formula yes in
the first-order logic is said to be in a
predicts normal form if and only if the
formula F is of the form Q 1 X 1 Q 2 xn
m where X 1 X 2 X and are the individual
variables so every Qixi is of the form
for all of X I are there exists X Q 1
represents a quantifier for x1 2 to the
presence our quantifier for x2 and so on
it can be the universal quantifier for
all are the existential quantifier there
exists and the rest of the formula is
given in M and M is a formula containing
no quantifiers now the Q 1 X 1 to 2 X 2
etc this is called the prefix of the
formula and M is called the matrix of
the formula now any well formed formula
of first order logic
you can bring it to the next normal form
let us see how to go about that the
steps you have to go through are given
like this if you want to bring any well
formed formula of the first order logic
how to transform interpret next normal
form this first step will be use the
loss that is if EF is equivalent to G
you have to replace it by F implies G &
G implies F and if you have F implies G
you have to replace it by not frg then
by this you will be eliminating the
logical connective equivalence and
implication the second step will be
repeatedly use not of not of F is equal
to F and de Morgan's laws
not of F or G is not of F and not of D
and not of F and G is not of F or not of
G and also the loss not off or all of of
X by bringing the knot inside for all
will change to there exist these things
we have learnt earlier so this is
equivalent to saying there exists X
naught of f of X so you are ringing a
knot inside similarly here if you have
not there exists X f of X bring the not
inside and you will get for all of X
knot of f of X so this is the second
step is to bring the negation signs
immediately before the a turns the third
step is rename bound variables if
necessary we shall see what it is by
taking some examples and step four will
be make use of the loss now if you have
Q of X f of X or G where G does not
contain X you can write it like this
similarly if you have Q of X f of X and
G where G does not contain X we can
write it like this and for all
distributes over end so this one can be
replaced by taking for all of X out and
writing this way this for all of X f of
X and for all of X H of X you can write
as for all of X f of X and H of X and
there exist six distributes over R so in
a similar manner if you have their exes
X f of X are there exists X H of X you
can take out the there exist X and write
it as there exists X f of X are H of X
but if you have for all and are you
cannot use that and similarly there
exists will not distribute over and this
you have to remember now if you have Q 1
X f of X are Q 2 XH of a
then how can you bring out the
quantifiers q-1 q-2 can be for all are
there exist how can you take them out
now this X R this quantifier is binding
this portion and this quantifier is
binding this portion so the best thing
for us will be to rename one of the
variables so keep X here and instead of
X you write it as Z in that case this
will not have X and this will not have
is it so you can take the quantifiers
out this is renaming of variables so
keep it as it is and this one you
replace by is it rename as Z and then
take out the quantifiers so this you
will get s Q 1 X Q 2 X f of X our H of
easy you are renaming the variable here
similar this is using our this uring and
here again you have the same thing if
you have Q 3 X and Q 4 X this is binding
this and this is binding this so it is
better to rename this variable s is e
and so by taking up the quantifiers you
will get this that is to move the
quantifiers to the left of the entire
formula to obtain the next Armel form
let us consider one our two examples
so let us consider some examples to see
how to convert a well-formed formula of
first order logic into pre next normal
form we have to bring all the
quantifiers to the front and the rest of
the formula should be after the
quantifiers the first one is called
their prefix and the latter one is
called the matrix of the formula now
take this example for all of X P of X
implies there exists X Q of X and we
have seen what are the steps we have to
use in converting a formula of that well
form to form law the first order logic
token examine first we have to replace
equivalence and implication so let us
try to replace this implication this you
can write as not for all of X P of X or
there exists X Q of X so this given
formula is equivalent to this this is we
are using the rule P implies Q is
equivalent to not P or Q now the next
step will be to bring the knot nearer to
the atom P of X and Q of X they are the
atoms so how will you bring the not
inside when you bring for all of X will
become direct this X so you have there
exists X naught of T of X R there exists
X Q of
we know that for all distributes over
end and there exist distributes over our
so we can use distributive law in the
reverse and take the direct this out so
you can take out there exists X and
write it as not of P of X our U of X
this is in print X normal form this is
the prefix and this is the matrix
let us take one more example this has
four variables there this is the
well-formed formula involving four
individual variables X Y Z u for all of
X for all of Y there exists set P of X
is Z and P of Y user implies there
exists u Q of X Y u here P is a
predicate variable with two variables
and Q is a predicate variable with three
variables it is a ternary predicate the
scope of X for all of X and for all of Y
will be the whole thing the scope of
there exists ed is this portion the
scope of there exists you is this
portion so we must be very careful about
the scope of each quantifier now
fortunately in this example the two
quantifiers for all X and for all of Y
are outside the rest of the portion we
need not have to do anything about them
only the remaining thing we have to
change so this can be written in this
form for all of Y and this one again the
first step is to replace implication by
using P implies Q is equivalent to not P
R Q so this can be written in the form
not there exists Z P of X comma Z and P
of Y comma Z are there exists u Q of X Y
now the for all of X for all of ye
remains as it is the second step will be
to bring the not inside so in that case
you will get there exist will become for
all so for all of is egg not of P of X
is a and P of Y is it okay for all is it
is the whole thing this is and there
exists you Q of X Y you
now for all of X for all of Y this you
can write as for all of his head use
debug ins last this will become not of P
of X comma Z are not of P of Y comma and
the scope of Z is this portion are there
exists you Q X Y you
now you can see that the scope of Z is
this portion and easy it is not
occurring in this portion at all and
similarly you there exists you the scope
is this and you is not appearing in this
portion that way this portion is free of
U and this portion is free of Z so using
for all is it here is not going to
affect it in any way because this does
not contain Z and using their exists
here
there exists you here is not going to
affect because this portion does not
contain you at all and for all of X for
all of Y the scope is the whole thing
and they are already outside so we need
not bother about that
so without affecting the formula we can
take out for all our visit and there
exists you outside this is possible
because this does not contain Z and this
does not contain you supposing it
contains something we have to rename the
variables and things like that so in
this particular example there is no
necessity for rename renaming of
variables so what you get is for all of
X for all of Y for all of is Z that
exists you then you get not of P of X
comma Z are not dot B Y comma Z are Q of
X Y you
so we have brought the given formula
into pre next normal form this is the
prefix which contains all the
quantifiers and this is the matrix for
portion which does not contain any
quantifiers like that we can bring any
formula of a starter logic into products
normal form
propositional logic also you can look at
as boolean algebra which has got
application to switching circuits I am
NOT going into detail of this circuits
but you must have heard about an a
target and so on a NAND gate is
represented like this it has got two
inputs and the output is P and Q P and Q
can be 0 or 1 and the output will be 1
when P and Q are both 1 otherwise it
will be 0 this is known as I indicate in
switching circuits and our gate is n an
our gate is represented like this there
will be two inputs P and Q and the
output will be P R Q it will be 0 when
both P and Q are 0
when one of or both of P and Q are 1 it
will be 1 it represents and the
connective in the propositional logic
the not gate in switching circuits is
represented by this there is one only
one input and output represents not P
and this is called the not gate in
switching circuits we also have two more
gates known as the NAND gate and the nor
gate nand which is
actually not and complimentary to end
and the truth table for that will be
like this PQ the Nunda operator is
usually denoted like this pierce-arrow
when this is 0 this is 0 this is 0 1 you
have to consider the 4 possibilities 1 0
1 1 in the case of end and end of P and
Q will be 1 in this case
so not end will be this is 0 in the
other cases it will be 1 so it is
complimentary to the end table P and Q
will be like this P and Q will be so it
is complimentary to that this is
represented by a gate of this form
off
we also have another gate now which
represents not all the truth table for
that will be like this P Q this is
sometimes left represented by this
notation again we have possibilities 0 0
0 1 1 0 1 1
what will be the table for P R Q P R Q
will be 0 in this case in the other 3
cases it will be 1 so it is not of R so
it will be 1 0 0 0 the truth table for
nor gate is given by this it is
represented by a diagram like this with
two inputs P Q P Q
now any boolean function can be
represented by a karnaugh map and you
have it is you can represent it as a
canonical sum of products our
disjunction of minterms for example
involved in two variables P or Q or R if
you represent it I again do not want to
go into the details what is meant by a
karnaugh map and all that those who are
familiar can connect it up with this
these suppose I have three variables P Q
and R this is P this is say Q and R then
0 0 0 is this 0 0 1 is this better use P
Q and R here so 0 0 will be this 0 0 1
will be like this 0 0 1 0 3 4 5 6 7
cells can be represented like this
P will be represented by this Q will be
represented by this and are represented
by this which includes all the seven
cells and this will be written in the
form Sigma of 1 comma 2 comma 3 4 5 6 7
this we have already seen so this is to
show the connection between boolean
algebra our propositional logic and
boolean algebra and switching circuits
we already know what is meant by and are
not two more gates are there in
switching circuits nor and 9 and any
boolean function can be represented like
this as a principal disjunctive normal
form
you
you