Theorems
of MORGAN |
Return
on functions NAND and NOR |
|
|
Return
to the synopsis |
To
contact the author |
Low
of page |
Created it, 06/09/09
Update it, 06/09/14
N° Visitors
2. - NEGATIVE LOGIC
Up to now, we adopted a convention called positive logical convention ; it is used and we think that it is for the current uses to better stick to this convention.
2. 1. - RECALL OF POSITIVE LOGICAL CONVENTION
One makes correspond to a closed contact (physical state), the logical state 1 and with an open contact (physical state) the logical state 0 (figure 33).
2. 2. - NEGATIVE LOGIC
Only by convention, one decided to make correspond at the physical state open contact the logical level 1 and to a contact closed the logical level 0 (figure 34), i.e. the opposite of usual convention.
Let us analyze which are the consequences of this change of convention.
PRINCIPLE OF DUALITY
Let us consider the table of operation of a door AND such as it is given by the manufacturer (figure 35) in the case of a door AND electronics :
Now let us write the truth table of this assembly by adopting positive logical convention L = 0, H = 1 ; we obtain the truth table of figure 36.
This truth table is the well-known truth table such as we saw it in theory 2.
Again let us write the truth table of the assembly but this time by using negative logical convention (figure 37).
Now let us give this truth table in order so that the variables of entry grow according to a binary order (figure 38).
.gif)
We obtain the truth table of one OR inclusive.
One can thus affirm that :
“An operator AND in positive logic behaves like an operator OR in negative logic”.
If the truth tables of all the logical circuits in one and the other type of logic are drawn up, one can write the following table (figure 39).
These correspondences were very much used to save cases in the digital circuits, but the fall in the prices of the circuits practically made give up this system which causes error.
On the catalogs of integrated circuits, the function indicated is that which this one would have in positive logic. A circuit AND trade thus function like one AND in positive logic and like one OR in negative logic.
Subsequently of this theory, it will not be any more question but of positive logical convention, i.e. the convention which we always used. Chapter 2 of this theory can thus be regarded as a bracket. You will refer to this paragraph only with the not very probable case where you would meet an old system using negative logical convention.
3. - THEOREMS OF MORGAN
3. 1. - 1st
THEOREM OF MORGAN 
Demonstration by the circles of Euler figure 40.
That is to say a unit A and
its complement 
(green hatchings) and a unit B and its complement 
(red hatchings).
Meeting A È B of A and B will be the surface included in blue contour.
The complement of A
È B
compared to  will be doubly
hatched surface either 
.
This surface being doubly hatched, it goes from either that it is well the
intersection of the complements of A and B
or 
.
One can thus say well that :
We can thus say in Boolean algebra that:
=
.
The reverse of a logical sum of two variables is equal to the logical product of the opposite of these two variables.
3. 2. - 2nd
THEOREM OF MORGAN 
Demonstration by the circles of Euler (figure 41).
That is to say a unit A and
its complement
(green hatchings) and a unit B and its complement
(red hatchings).
The intersection of A and b : A Ç B will be the surface included in blue contour.
The complement of A
Ç B is 
will be the part hatched in black.
We in addition see that this same
surface hatched in black is the union of
and
is 
,
indeed this black shaded zone covers all the green hatchings
and all the red hatchings .
In Boolean algebra, we can thus write :
=
+
The reverse of the logical product of two variables is equal to the sum of the opposite of the two variables.
3. 3. - RETURN
ON FUNCTIONS NAND AND NOR
3. 3. 1. - OPERATOR NAND
In
the preceding chapter, we saw for the operator NAND,
whose equation was S =,
the following electric circuit (figure 42).
We can now thanks to the theorem of
Morgan simplify this circuit, indeed S =
=
+
. It is thus enough to put two contacts at rest in parallel to obtain the
same result as previously what is very interesting (figure 43).
Let us check the operation of this circuit (figure 44) by studying the four possibilities of combinations of a and b.
Let us defer the results obtained in a table of Karnaugh (figure 45).
We find well the table of Karnaugh of a circuit NAND (figure 43).
We see in the passing that the table
of Karnaugh gives him also S =
+
and that thanks to him, one obtains the simplest solution well.
3. 3. 2. - NOR OPERATOR
In
the preceding chapter, we saw the NOR
operator whose equation was S =
taking into account the theorem of Morgan we can write :
S =
=.
From where the diagram of figure 46 :
You will be able yourself to carry out the checks of the good conformity of the truth table of this NOR-circuit with that which we know.
3. 4. - ASSOCIATION
OF CIRCUITS, TRANSFORMATION OF DIAGRAM
We studied various fundamental functions which are available in the form of integrated circuits.
In each case, there are several functions of the same type. Thus one meets integrated circuits containing four NAND into two entries.
The originator of numerical systems will thus have when it uses a NAND knowledge that in the same case three other NAND at two entries are available and still unutilised.
It will be thus sometimes interesting to be able to transform a circuit AND into two circuits NAND, for example if there is a surplus of doors NAND available whereas it would be necessary to put an additional case containing of AND.
The problem becomes complicated when one wants to do for example one OR with NAND. There is then recourse has a simplification by means of the theorem of Morgan.
The theorem of Morgan gives us the
following relation:
=
+
which makes it possible to develop equivalences between circuits.
If the first term of the equality is
observed, i.e.,
it is noticed that it is the result obtained at exit of a NAND
starting from two variables a and b
present on the entries.
The second term of the equality
+
represents a logical sum, i.e. the result obtained at the exit of one OR
which one complémenté the entries.
The diagrammatic representation of this equality is made on figure 47.
This means that NAND equivalent to one OR is preceded by reversers.
To check in practice that the two preceding assemblies are quite equivalent, it is enough to apply logical levels in a and b to the second assembly to see whether one can write a truth table similar to that of a circuit NAND. In this case, the two assemblies will be quite equivalent.
We know that there are 4 combinations different from two variables a and b ; if you wish it can carry out the checking for these four combinations. We will not study for our part that the combination a = 0 and b = 0.
Figure 48 shows the result for a = b = 0. Knowing the truth tables of the reversers, that of AND and that of OR, it was easy to us to find this result.
The level of the exit east then to 1 for the two assemblies.
While proceeding in the same way, we can check that equivalence is valid when a = 0 and b = 0, a = 1 and b = 0 and finally when a = b = 1. We thus find the truth table of a NAND.
The circuit OR at complémentées entries can be represented as indicated figure 49.
Example :
Let us apply this principle to the diagram of figure 50.
To see how it functions, one transforms it into an equivalent circuit by applying the theorem of MORGAN to circuit NAND of exit.
We obtain figure 51.
We see now that each circuit NAND
is followed of a reverser, which amounts replacing the NAND
and the reverser by one AND.
Indeed, one can say that 
= y (two successive inversions are cancelled).
One thus obtains the logical circuit of figure 52.
The circuit is not other than that of one OR exclusive already presented figure 25.
The theorem of MORGAN enabled us to find a circuit equivalent. We will see thereafter how to benefit from this one in other examples.
As of now we can see that any logical circuit can be carried out with only circuits of the same type, NAND for example.
The originator of circuit always has the possibility of choosing with his suitability the type of case which it wishes to use.
Until now, we applied the theorem of MORGAN to circuits NAND but it can be applied generally to any logical equation and in particular to the NOR function.
In this last case, the relation is
=.
We can materialize this equality by the diagram of figure 53.
If you wish it, you can easily by taking again the same principle as for the demonstration of equivalence schematized figure 47 (case of the NAND) to draw up the truth table of each assembly figure 53 to show the equivalence of those.
End of this lesson and we will learn the Method of QUINE-MAC CLUSKEY.
|
Click
here for the following lesson or in the synopsis envisaged to this end. |
High
of page |
 Preceding
page |
Following
page |
