5: Minimize incompletely defined functions.

Annotation: The lecture presents the minimization of incompletely defined functions, provides a synthesis of functions in Sheffer bar and Pierce arrow bases, gives approaches to the minimization of conjunctive forms.

Very often, if not in most cases, the operation of a particular device is described using an incompletely defined function, since some combinations of input signals are not given or are prohibited.

Definition An incompletely defined function is such a switching function, the values ​​of which on some sets of arguments can be arbitrary (that is, equal to "0" or "1").

Definition Let the function f (x ₁ , x ₂ , ... x _n ) not be defined on the "p" sets of arguments. Then a fully qualified function We will be considered equivalent to f (x ₁ , x ₂ , ... x _n ), if its values ​​on those sets on which f (x ₁ , x ₂ , ... x _n ) is defined coincide.

Obviously, there are 2 ^p different functions equivalent to f (x ₁ , x ₂ , ... x _n ).

The minimization problem f (x ₁ , x ₂ , ... x _n ) is to choose such an equivalent which has the simplest form.

We introduce two auxiliary equivalent functions. , which take on forbidden argument sets the values ​​0 and 1, respectively.

THEOREM . PDNF incompletely defined f (x ₁ , x ₂ , ... x _n ) coincides with the disjunction of the shortest implicant that co-cover all the constituents of the unit and none of which is superfluous.

Example :

Let f (x ₁ , x ₂ , ... x _n ) be given in the following table:

Then

,

but

Find simple implicants

Constituent units one	Gluing marks	Implicants	Gluing marks	Implicants
0000	*	000- 00-0 -000	*	00- - 00- - -0-0
0001 0010 1000	*		*
	*		*
	*	00-1 0-01 001- -010 1-00	*
0011 0101 1010 1100	*		-
	*		*	ten
	*		*
	*		*
1101 1110	*	-101 1-10 110- 11-0	-
			*
	*		-	eleven- -
			-
1111	*	111-	*

Simple implicants

Construct an implicant matrix.

Constituent units	0000	0101	1000	1100	1111
Simple implicants
0-01		+
-101		+
110-				+
11-0				+
00--	+
-0-0	+		+
1--0			+	+
eleven--				+	+

Perform optimal coverage of the constituent unit simple implicants and we get the minimal form of the function f (x ₁ x ₂ x ₃ x ₄ )

Minimization of incompletely defined functions with the help of Veitch diagrams in a visual and convenient form allows finding minimal forms.

Example :

Consider the function f (x ₁ x ₂ x ₃ x ₄ ) and find its minimal form. Fill in the Veitch diagram according to the following rules: put in the cells of the diagram units that correspond to the constituents of the unit, zeros for the absent constituents and the symbol of uncertainty - “*” (asterisk) - to the others.

It can be seen that the cells for the constituents: x ₁ x ₂ x ₃ x ₄ , x ₁ x ₂ x ₃ x ₄ , x ₁ x ₂ x ₃ x ₄ it is advisable to “put” units instead of symbols of uncertainty, since in this case the correct rank 2 configuration, which is covered by the product x ₂ x ₃ .

Similarly, in the cell x ₁ x ₂ x ₃ x ₄ you need to "put" one.

So, .

Remark Everything that has been said about minimizing the function represented in the PDNF or DNF is valid for the function specified in the CNF or CNF.

In this case, you need to find the correct configuration formed by zeros.

Synthesis of switching functions in a one-element basis

Operation (arrow) Pierce

  f 

  (x 

  , x 

  ) 

This function can be represented by writing down the "units":

or

Based on the principle of superposition:

Applying the de Morgan rule:

or:

those.

Consider some relationships for Pierce's operation:

,

those. Pierce operation does not have the property of associativity

In this case, the order of operations in the formulas, where there is a Pierce operation is as follows:

1. brackets are revealed
2. inversion operations are performed
3. Pierce operations are performed

Synthesis of logical functions in the Pierce basis is convenient to produce, having a function entry in the CNF.

Suppose that the FAL is given in conjunction form

f = Q ₁ Q ₂ Q ₃ . . . Q _n

Substitute the term Q _i in the form:

Take double negation from both sides of this equality, applying the de Morgan rule

Applying a ratio derived from the superposition principle:

Or, applying this transformation to the original form, we get:

So: to move from the CNF to the Pierce basis and inversion, you need:

1. replace disjunction operations with Pierce operations
2. replace conjunction operations with Pierce operations
3. put in brackets all those groups of letters that correspond to conjunctive members.

Example :

Remark Since in these works the number of letters does not increase, and if the initial form of the function was minimal, then the newly obtained will also be minimal (in fact, the situation is more complicated, since we are not considering a basis " "and the other, that is" "and" - "- Pierce operation and inversion).

Fundamentally, you can get rid of the negatives by applying the ratio: , but then it will not be possible to say that the form obtained will be minimal!

Scheffer's stroke operation

Note that this function is dual with respect to f ₈ , therefore all properties are essentially dual duality of the considered ones.

(write functions by zeros)

based on the principle of superposition:

x ₁ | x ₂ | . . . | x _n = x ₁ x ₂ ... x _n

Consider some equivalences:

x ₁ | x ₂ | x ₃ = (x ₁ x ₂ ) | x ₃ = x ₁ | (x ₂ x ₃ )

x ₁ | x ₂ | x ₃ | x ₄ = (x ₁ x ₂ ) | (x ₃ x ₄ )

We formulate the rules for the transition from a DNF function to an expression using the operation "Sheffer Stroke".

1. replace all disjunction operations with Schaeffer operations
2. replace all conjunction operations with Schaeffer operations
3. groups of letters that correspond to disjunctive members, enclose in brackets.

Example :

The same can be said about the minimal form.

In conclusion, it should be noted that at present the issues of the synthesis of functions in the singleton basis are of great importance, since the corresponding elements use the operation of Pierce and Schaeffer. However, the theoretical methods of synthesis are not fully developed in such detail as they were made in the basis of the “and”, “or”, or “inversion”.

Minimal conjunctive normal forms

As noted, in order to obtain the minimum form of the function, both MDNF and MISP should be constructed.

Consider the construction of the MCF.

Basically, the methods of obtaining MCPF are similar to the methods of obtaining MDNF and therefore we formulate only the rules for obtaining MCPF:

1. Submit FAL to SKNF. If it is specified by the table, then write the function by zeros, as it was formulated earlier. If the PDNF is given, then it is easy to get SKNF from it:

   ,

   those. the function must be represented in the form of a conjunction of the missing number of disjunctive members with corresponding negatives.
2. When specifying a function in an arbitrary conjugative form, applying

   deployment formulas:

   

   . . . . . . . . . . . .

   get SKNF.
3. Perform all partial gluing operations:

   

   and absorption: , get abbreviated CNF.
4. Apply any of the minimization methods: test members, Veitch diagrams, implicative matrix method.
   • When performing the method of testing members, it is necessary to equate each conjunctive member to zero. Find the values ​​of the arguments that vanish it, remove it from the function expression, and find the function value with the found values ​​of the arguments. If the function vanishes, then the conjunctive term is redundant.

     If possible, discard several members at once, act as if minimizing the function of the DNF.
   • When using the Vache diagrams, the correct configurations formed by zeros are searched.
   • When using the method of implicant matrices, they act as in the case of DNF, only the columns are assigned the names of the constituents "0" of the function recorded in the SKNF, and the horizontal rows - the simple implicant. Next, look for the best coverage.