Conjunctive normal form of a logical function. Normal forms of logical functions

Standard basis. Elementary formulas are literals. Elementary conjunction (disjunction). Disjunctive (conjunctive) normal form and perfect form. Theorem: any Boolean function other than 0 (from 1) can be represented as SDNF (SKNF). Completeness of the standard basis. Examples of complete bases: Zhegalkin basis, Schaeffer's stroke, Peirce's arrow.

Standard basis is a set of three initial operations of Boolean algebra: addition (union), multiplication (intersection), and negation.

Here we will call literal variable x or its negation x and denote xИ. Boolean intersection of multiple literals defined by different variables, i.e. expression of the form X = xИ 1 xИ 2. ... ... xИ л is called elementary conjunction ... The requirement that all variables be different is conditioned by the following. If the conjunction contains several identical literals, then by virtue of the commutativity, associativity and idempotency of the conjunction, it is possible, passing to an equivalent formula, to leave only one literal (for example, x 1 x 1 = x 1). If the conjunction includes a variable and its negation, then the formula is equivalent to the constant 0, since x x = 0 and for any formula Y we have Y x x = 0.

A disjunction of several elementary conjunctions is called disjunctive normal form , or DNF ... For example,

x 1 x 3 + x 2 x 3 x 4 + x 1 x 2 x 3 x 5.

If the composition of the variables in each elementary conjunction of a given DNF is the same, then the DNF is called perfect ... The given example is DNF, which is not perfect. On the contrary, the formula

x 1 x 2 x 3 x 4 + x 1 x 2 x 3 x 4 + x 1 x 2 x 3 x 4

there is a perfect form.

Since in Boolean algebra addition and multiplication are symmetric operations and you can always interpret addition as multiplication, and multiplication as addition, there is also a dual concept - conjunctive normal form (CNF ), which is a conjunction of elementary disjunctions, and perfect conjunctive form (SKNF ). From the duality principle for symmetric semirings it follows that any statement about DNF corresponds to a dual statement about CNF, which is obtained by replacing addition (disjunction) by multiplication, multiplication (conjunction) by addition, constant 0 by constant 1, constant 1 by constant 0, order relation by dual (inverse) order. Therefore, further we will focus on studying only DNF.

Theorem 1.4. Any Boolean function other than the constant 0 can be represented as SDNF.

◀ Let us agree by x σ to mean the formula x if σ = 1, and the formula x if σ = 0. Let the function f (y 1,..., Yn) take the value 1 on the vector (t 1,..., Tn ) (such a vector is called constituent of the unit ). Then the elementary conjunction also takes the value 1 on this set, but vanishes on all other n-dimensional Boolean vectors. Consider the formula

in which the sum (union) extends to all those sets (t 1,..., tn) of values of the arguments for which the given function takes the value 1. Note that the set of such sets is not empty, so that the sum contains at least one term.

It is easy to see that the formula Φ becomes 1 for those and only for those values of the variables for which the considered function becomes 1. Hence, the formula Ψ represents the function f.

Corollary 1.1. The standard basis is complete.

◀ Indeed, if a function is not a constant 0, then it can be represented either in the form of SDNF, which is a formula over a standard basis. The constant 0 can be represented, for example, by the formula f (x 1, x 2,..., X n) = x 1 x 1.

Example 1.2. Consider a function of three variables m (x 1, x 2, x 3) (Table 1.4), called majority function ̆. This function evaluates to 1 if more than half of its arguments are 1. Therefore, it is often called the voting function. Let's build a SDNF for it.

The completeness of the standard basis allows the selection of other complete systems of functions. The completeness of the set F can be established from the following considerations. Suppose each of the three standard busis functions is representable by a formula over F. Then, by Theorem 1.3, the set F is complete.

Example 1.3. The set of operations of addition modulo 2, multiplication, and constant 1 is called the Zhegalkin basis ... Modulo 2 addition and multiplication are basic operations of the ring Z2, the expressions composed with their help are polynomials over the ring Z2. The constant 1 in this case is necessary to write the free member. Since xx = x, all factors in the polynomial have degree 1. Therefore, when writing a polynomial, one can do without the concept of degree. Examples of formulas over the Zhegalkin basis:

xy⊕x⊕y, x⊕1, xyz⊕xz⊕x⊕y⊕1.

Any such formula is called the Zhegalkin polynomial. In fact, the Zhegalkin polynomial is a polynomial over the ring Z2.

It is not difficult to construct formulas over the Zhegalkin basis, representing the operations of addition and negation of the standard basis (the multiplication of the two bases is common):

x + y = x⊕y⊕xy, x = x⊕1.

Therefore, the Zhegalkin basis is a complete set.
It can be shown that for any Boolean function the Zhegalkin polynomial is uniquely determined

(more precisely, up to the order of the terms). The coefficients of the Zhegalkin polynomial for a small number of variables can be found by the method of undefined coefficients.

Example 1.4. Consider a set of a single function, the Schaeffer stroke *. This set is complete, which follows from the following easily verifiable identities:

x = x | x, xy = x | y = (x | y) | (x | y), x + y = x | y = (x | x) | (y | y).

Example 1.5. The basis consisting of a single function, the Pierce arrow, is also complete. The verification of this is similar to the case of the Schaeffer stroke. However, this conclusion can also be made on the basis of the duality principle for symmetric semirings.

* Schaeffer's stroke is a binary, but not associative operation. Therefore, when using the infix form, you should be careful: the result depends on the order in which the operations are performed. In this case, it is recommended to explicitly indicate the order of operations using parentheses, for example, write (x | y) | z, not x | y | z, although both forms are equivalent.

The conjunctive normal form is convenient for automatic theorem proving. Any Boolean formula can be converted to CNF. To do this, you can use: the law of double negation, de Morgan's law, distributivity.

Collegiate YouTube

1 / 5

Formulas in KNF:

¬ A ∧ (B ∨ C), (\ displaystyle \ neg A \ wedge (B \ vee C),) (A ∨ B) ∧ (¬ B ∨ C ∨ ¬ D) ∧ (D ∨ ¬ E), (\ displaystyle (A \ vee B) \ wedge (\ neg B \ vee C \ vee \ neg D) \ wedge ( D \ vee \ neg E),) A ∧ B. (\ displaystyle A \ wedge B.)

Formulas not in the CNF:

¬ (B ∨ C), (\ displaystyle \ neg (B \ vee C),) (A ∧ B) ∨ C, (\ displaystyle (A \ wedge B) \ vee C,) A ∧ (B ∨ (D ∧ E)). (\ displaystyle A \ wedge (B \ vee (D \ wedge E)).)

But these 3 formulas not in CNF are equivalent to the following formulas in CNF:

¬ B ∧ ¬ C, (\ displaystyle \ neg B \ wedge \ neg C,) (A ∨ C) ∧ (B ∨ C), (\ displaystyle (A \ vee C) \ wedge (B \ vee C),) A ∧ (B ∨ D) ∧ (B ∨ E). (\ displaystyle A \ wedge (B \ vee D) \ wedge (B \ vee E).)

Constructing the CNF

Algorithm for constructing CNF

1) Get rid of all logical operations contained in the formula, replacing them with the main ones: conjunction, disjunction, negation. This can be done using equivalent formulas:

A → B = ¬ A ∨ B, (\ displaystyle A \ rightarrow B = \ neg A \ vee B,) A ↔ B = (¬ A ∨ B) ∧ (A ∨ ¬ B). (\ displaystyle A \ leftrightarrow B = (\ neg A \ vee B) \ wedge (A \ vee \ neg B).)

2) Replace the negation sign, referring to the entire expression, with the negation signs, referring to individual variable statements based on the formulas:

¬ (A ∨ B) = ¬ A ∧ ¬ B, (\ displaystyle \ neg (A \ vee B) = \ neg A \ wedge \ neg B,) ¬ (A ∧ B) = ¬ A ∨ ¬ B. (\ displaystyle \ neg (A \ wedge B) = \ neg A \ vee \ neg B.)

3) Get rid of double negation signs.

4) Apply, if necessary, to the operations of conjunction and disjunction the properties of distributivity and the absorption formula.

An example of building a CNF

Let us bring to the CNF the formula

F = (X → Y) ∧ ((¬ Y → Z) → ¬ X). (\ displaystyle F = (X \ rightarrow Y) \ wedge ((\ neg Y \ rightarrow Z) \ rightarrow \ neg X).)

Let's transform the formula F (\ displaystyle F) to a formula that does not contain → (\ displaystyle \ rightarrow):

F = (¬ X ∨ Y) ∧ (¬ (¬ Y → Z) ∨ ¬ X) = (¬ X ∨ Y) ∧ (¬ (¬ ¬ Y ∨ Z) ∨ ¬ X). (\ displaystyle F = (\ neg X \ vee Y) \ wedge (\ neg (\ neg Y \ rightarrow Z) \ vee \ neg X) = (\ neg X \ vee Y) \ wedge (\ neg (\ neg \ neg Y \ vee Z) \ vee \ neg X).)

In the resulting formula, we transfer negation to variables and reduce double negatives:

F = (¬ X ∨ Y) ∧ ((¬ Y ∧ ¬ Z) ∨ ¬ X). (\ displaystyle F = (\ neg X \ vee Y) \ wedge ((\ neg Y \ wedge \ neg Z) \ vee \ neg X).)

For example, the following formula is written in 2-CNF:

(A ∨ B) ∧ (¬ B ∨ C) ∧ (B ∨ ¬ C). (\ displaystyle (A \ lor B) \ land (\ neg B \ lor C) \ land (B \ lor \ neg C).)

Normal form logical formula does not contain signs of implication, equivalence and negation of non-elementary formulas.

The normal form comes in two forms:

conjunctive normal form (CNF)- conjunction of several disjunctions, for example, $ \ left (A \ vee \ overline (B) \ vee C \ right) \ wedge \ left (A \ vee C \ right) $;

disjunctive normal form (DNF)- a disjunction of several conjunctions, for example, $ \ left (A \ wedge \ overline (B) \ wedge C \ right) \ vee \ left (B \ wedge C \ right) $.

SKNF

Perfect conjunctive normal form (SKNF) is a CNF that satisfies three conditions:

does not contain identical elementary disjunctions;

none of the clauses contains the same variables;

each elementary disjunction contains each variable from the given CNF.

Any Boolean formula that is not identically true can be represented in SKNF.

Rules for constructing SKNF according to the truth table

For each set of variables for which the function is 0, the sum is written, and the variables that have the value 1 are taken with negation.

SDNF

Perfect Disjunctive Normal Form (SDNF) is a DNF that satisfies three conditions:

does not contain identical elementary conjunctions;

none of the conjunctions contains the same variables;

each elementary conjunction contains each variable from the given DNFs, moreover, in the same order.

Any Boolean formula that is not identically false can be represented in the SDNF, moreover, in a unique way.

Rules for constructing SDNF according to the truth table

For each set of variables for which the function is equal to 1, the product is written, and the variables that have the value 0 are taken with negation.

Examples of finding SKNF and SDNF

Example 1

Write a logical function according to its truth table:

Picture 1.

Solution:

Let's use the rule for constructing SDNF:

Figure 2.

We get SDNF:

Let's use the rule for constructing SKNF.

Simple disjunction(inclusive disjunction) or disjunct(English disjunct) is a disjunction of one or more variables or their negations, and each variable occurs no more than once.

Simple disjunction

complete if each variable (or its negation) appears in it exactly once;
monotonous if it does not contain variable negatives.

Conjunctive normal form, CNF(eng. conjunctive normal form, CNF) normal form, in which a Boolean function has the form of a conjunction of several simple clauses.

CNF example:$ f (x, y) = (x \ lor y) \ land (y \ lor \ neg (z)) $

SKNF

Perfect conjunctive normal form, SKNF(perfect conjunctive normal form, PCNF) is a CNF that satisfies the following conditions:

it does not have the same simple disjunctions
every simple disjunction is complete

SKNF example:$ f (x, y, z) = (x \ lor \ neg (y) \ lor z) \ land (x \ lor y \ lor \ neg (z)) $

Theorem: For any Boolean function $ f (\ vec (x)) $ that is not equal to the identity unit, there is an SKNF that defines it.

Proof: Since the inverse of the function $ \ neg (f) (\ vec x) $ is equal to one on those tuples on which $ f (\ vec x) $ is equal to zero, then the SDNF for $ \ neg (f) (\ vec x) $ can be write as follows:

$ \ neg (f) (\ vec x) = \ bigvee \ limits_ (f (x ^ (\ sigma_ (1)), x ^ (\ sigma_ (2)), ..., x ^ (\ sigma_ (n ))) = 0) (x_ (1) ^ (\ sigma_ (1)) \ wedge x_ (2) ^ (\ sigma_ (2)) \ wedge ... \ wedge x_ (n) ^ (\ sigma_ (n ))) $, where $ \ sigma_ (i) $ denotes the presence or absence of negation for $ x_ (i) $

Let's find the inverse of the left and right sides of the expression:

$ f (\ vec x) = \ neg ((\ bigvee \ limits_ (f (x ^ (\ sigma_ (1)), x ^ (\ sigma_ (2)), ..., x ^ (\ sigma_ (n ))) = 0) (x_ (1) ^ (\ sigma_ (1)) \ wedge x_ (2) ^ (\ sigma_ (2)) \ wedge ... \ wedge x_ (n) ^ (\ sigma_ (n ))))) $

Applying de Morgan's rule twice to the expression obtained on the right side, we get: $ f (\ vec x) = \ bigwedge \ limits_ (f (x ^ (\ sigma_1), x ^ (\ sigma_2), \ dots, x ^ (\ sigma_n)) = 0) $ $ (\ neg (x_1 ^ (\ sigma_1)) \ vee \ neg (x_2 ^ (\ sigma_2)) \ vee \ dots \ vee \ neg (x_n ^ (\ sigma_n))) $

The last expression is SKNF. Since the SKNF is obtained from the SDNF, which can be constructed for any function that is not identically zero, the theorem is proved.

Algorithm for constructing SKNF according to the truth table

In the truth table we mark those sets of variables on which the value of the function is equal to $ 0 $.
For each marked set, we write the disjunction of all variables according to the following rule: if the value of some variable is $ 0 $, then we include the variable itself in the disjunction, otherwise its negation.
We connect all the resulting disjunctions by conjunction operations.

An example of constructing SKNF for the median

one). In the truth table we mark those sets of variables on which the value of the function is equal to $ 0 $.

x	y	z	$ \ langle x, y, z \ rangle $
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

2). For each marked set, we write the conjunction of all variables according to the following rule: if the value of some variable is $ 0 $, then we include the variable itself in the disjunction, otherwise its negation.

x	y	z	$ \ langle x, y, z \ rangle $
0	0	0	0	$ (x \ lor y \ lor z) $
0	0	1	0	$ (x \ lor y \ lor \ neg (z)) $
0	1	0	0	$ (x \ lor \ neg (y) \ lor z) $
0	1	1	1
1	0	0	0	$ (\ neg (x) \ lor y \ lor z) $
1	0	1	1
1	1	0	1
1	1	1	1

3). We connect all the resulting disjunctions by conjunction operations.

$ \ langle x, y, z \ rangle = (x \ lor y \ lor z) \ land (\ neg (x) \ lor y \ lor z) \ land (x \ lor \ neg (y) \ lor z) \ land (x \ lor y \ lor \ neg (z)) $

SKNF examples for some functions

Pierce's Arrow: $ x \ downarrow y = (\ neg (x) \ lor (y)) \ land ((x) \ lor \ neg (y)) \ land (\ neg (x) \ lor \ neg (y) ) $

Exclusive or: $ x \ oplus y \ oplus z = (\ neg (x) \ lor \ neg (y) \ lor z) \ land (\ neg (x) \ lor y \ lor \ neg (z)) \ land (x \ lor \ neg (y) \ lor \ neg (z)) \ land (x \ lor y \ lor z) $

Example. Find CNF formulas

~ ~

A perfect disjunctive normal form of SDNF can be constructed using the following algorithm:

1. = 1.of the DNF algorithm

2. = 2.of the DNF algorithm

3. = 3.DNF algorithm

4. = 4. of the DNF algorithm

5. Drop the identically false terms, that is, terms of the form

6. Replenish the remaining terms with missing variables

7. Repeat step 4.

Example. Find SDNF formulas.

To construct the SKNF, you can use the following scheme:

Example. Find SDNF formulas.

It is known (Theorems 2.11, 2.12) that SDNF and SKNF are uniquely determined by the formula and, therefore, they can be constructed from the truth table of the formula.

The scheme for constructing SDNF and SKNF according to the truth table is given below, for the formula ~ :

			~
			1 0 1 0 1 1 0 1	SDNF; SKNF.

2.2. The task.

2.2.1 Below are the logical expressions. Simplify the expressions of your variant as much as possible by using Boole's laws of logic. Then use truth tables to compare your simplified expression with the original.

2.2.2. Clarify the question of the equivalence of f 1 and f 2 by reducing them to SDNF (Table 1).

2.2.3. Find the dual function for f 3 according to the generalized and Boolean principle (Table 1). Compare the results obtained.

№	f 1	f 2	f 3

2.3. Test questions.

2.3.1. Give the definition of the statement.

2.3.2. List the basic operations on the utterance.

2.3.3. What is a truth table?

2.3.4. Create truth tables for the following formulas:

~ ~ ~ ;

2.3.5. Taking into account the conventions on the order of operations, omit the "extra" parentheses and the "" sign in the formulas:

;

2.3.6. Using equivalent transformations, prove the identical truth of the formulas:

2.3.7. Find dual formulas:

)

2.3.8. Bring the following formulas to the perfect DNF (SDNF) form:

2.3.9. Bring the following formulas to the perfect CNF (SKNF) form:

Laboratory work No. 3

Topic:“Minimization of Boolean Functions. Logic"

Target: Acquisition of practical skills in working with methods of minimizing Boolean functions.

3.1. Theoretical information.

Minimal forms

As shown in, any Boolean function is representable in perfect normal form (disjunctive or conjunctive). Moreover, such a presentation is the first step in the transition from the table definition of a function to its analytical expression. In what follows, we will proceed from the disjunctive form, and the corresponding results for the conjunctive form are obtained on the basis of the duality principle.

The canonical problem of synthesizing logic circuits in a Boolean basis is reduced to minimizing Boolean functions, i.e. to represent them in disjunctive normal form, which contains the smallest number of letters (variables and their negations). Such forms are called minimal. In canonical synthesis, it is assumed that both signals and their inversions are fed to the inputs of the circuit.

The formula, presented in disjunctive normal form, is simplified by multiple applications of the gluing operation and the absorption operation and (dual identities for the conjunctive normal form have the form: and). Here, by and can be understood as any formula of Boolean algebra. As a result, we arrive at such an analytical expression when further transformations are already impossible, i.e. we get a dead-end shape.

Among the dead-end forms is the minimal disjunctive form, and it may not be unique. To make sure that a given dead-end shape is minimal, it is necessary to find all dead-end shapes and compare them by the number of letters they contain.

For example, let the function be given in perfect normal disjunctive form:

Grouping the members and applying the gluing operation, we have.

With another method of grouping, we get:

Both dead-end forms are not minimal. To get the minimum shape, you need to guess to repeat one term in the original formula (this can always be done, since). In the first case, such a member can be. Then . By adding a member, we get:. After going through all the possible options, you can make sure that the last two forms are minimal.

Working with formulas at this level is like wandering in the dark. The process of finding minimal forms becomes more visual and purposeful if you use some graphical and analytical representations and symbols specially designed for this purpose.

Multidimensional cube

Each vertex of the -dimensional cube can be associated with the constituent of the unit. Consequently, the subset of marked vertices is a mapping on the -dimensional cube of a Boolean function of variables in perfect disjunctive normal form. In fig. 3.1 shows such a mapping for the function from Section 3.7.

Figure 3.1 Display on a three-dimensional cube of the function presented in SDNF

To display a function of variables presented in any disjunctive normal form, it is necessary to establish a correspondence between its miniterms and elements of the -dimensional cube.

Minitherm (-1) -th rank can be considered as a result of gluing two miniterms of the -th rank (constituent of the unit), i.e. On a -dimensional cube, this corresponds to replacing two vertices that differ only in the values of the coordinate connecting these vertices by an edge (the edge is said to cover the incident vertices). Thus, miniterms of the (-1) th order correspond to the edges of the -dimensional cube. Similarly, the correspondence of miniterms of the (-2) th order is established to the faces of the -dimensional cube, each of which covers four vertices (and four edges).

Elements of an -dimensional cube, characterized by dimensions, are called -cubes. So, vertices are 0-cubes, edges are 1-cubes, faces are 2-cubes, etc. Summarizing the above reasoning, we can assume that the miniterm of the () -th rank in the disjunctive normal form for the function of variables is displayed by a -cube, and each -cube covers all those -cubes of the lowest dimension that are associated with its vertices. As an example, Fig. 3.2 the mapping of the function of three variables is given. Here miniterms and correspond to 1-cube (), and miniterm is displayed by 2-cube ().

Figure 3.2 Function coverage

So, any disjunctive normal form is displayed on the -dimensional cube by a set of -cubes that cover all the vertices corresponding to the constituents of the unit (0-cube). The converse is also true: if some collection of -cubes covers the set of all vertices corresponding to the unit values of the function, then the disjunction of the miniterms corresponding to these -cubes is the expression of this function in disjunctive normal form. It is said that such a set of -cubes (or the corresponding miniterms) forms the coverage of a function.

The striving for the minimal form is intuitively understood as the search for such a coverage, the number of -cubes of which would be smaller, and their dimension would be larger. The coverage corresponding to the minimum shape is called the minimum coverage. For example, for the function coverage in Fig. 3.3 matches minimal shapes and .

Rice. 3.3 Function Covers.

left – ; on right –

Displaying a function on a -dimensional cube is clear and simple for. A four-dimensional cube can be drawn as shown in fig. 3.4, where the function of four variables and its minimum coverage corresponding to the expression ... The use of this method requires such complex constructions that all its advantages are lost.

Rice. 3.4 Function display on a four-dimensional cube

Karnaugh maps

Another method of graphing boolean functions uses Karnot maps which are specially organized look-up tables. The columns and rows of the table correspond to all possible sets of values of no more than two variables, and these sets are arranged in such an order that each subsequent one differs from the previous one by the value of only one of the variables. Due to this, both horizontally and vertically adjacent cells of the table differ in the value of only one variable. Cells located at the edges of the table are also considered adjacent and have this property. In fig. 3.5 shows Karnaugh charts for two, three, four variables.

Rice. 3.5 Karnot maps for two, three and four variables

As in ordinary truth tables, the cells of the sets in which the function takes on the value 1 are filled with ones (zeros usually do not fit, they correspond to empty cells). For example, in Fig. 3.6, but shows the Karnot map for the function, the mapping of which on the four-dimensional cube is given in Fig. 3.4. For simplicity, the rows and columns corresponding to the values of 1 for a variable are enclosed in curly braces with the designation of that variable.

Rice. 3.6 Displaying a function of four variables on a Karnot chart

(a) and its minimum coverage (b)

Between function mappings on n-dimensional cube and on the Karnot map there is a one-to-one correspondence. On the map of Karnot s-cube corresponds to a set of 2 neighboring cells located in a row, column, square or rectangle (taking into account the proximity of the opposite edges of the map). Therefore, all the provisions set out in the above (see p. multidimensional cube) are valid for Karnot maps. So, in fig. 3.6, b the coverage of map units corresponding to the minimal disjunctive form is shown the function under consideration.

The reading of miniterms from the Karnot card is carried out according to a simple rule. Cells that form s-cube, give miniter (n – s)-th rank, which includes those (n – s) variables that store the same values on this s-cube, where the value 1 corresponds to the variables themselves, and the values 0 correspond to their negations. Variables that do not store their values for s-cube, in the miniterm are absent. Different ways of reading lead to different representations of the function in disjunctive normal form (the rightmost one is minimal) (Fig. 3.7).

The use of Karnaugh maps requires simpler constructions than mapping on n-dimensional cube, especially in the case of four variables. To display functions of five variables, two Karnot maps for four variables are used, and for a function of six variables, four such maps are used. With a further increase in the number of variables, Karnot maps become practically unusable.

Known in literature Weich maps differ only in a different order of the sets of values of variables and have the same properties as Karnot maps.

Complex of cubes

The inconsistency of graphical methods with a large number of variables is compensated by various analytical methods for representing Boolean functions. One of such representations is complex of cubes using the terminology of multidimensional logical space in combination with specially designed symbology.

). 0-cubes corresponding to the constituents of one are represented by sets of values of variables on which the function is equal to one. Obviously in the record

Rice. 3.8 Complex of cubes of a function of three variables ( but) and its symbolic representation ( b)

The complex of cubes forms maximum function coverage... Excluding from it all those s-cubes, which are covered by cubes of the highest dimension, we obtain coverings corresponding to dead-end forms. So, for the example under consideration (Fig. 3.8) we have a dead-end cover

which corresponds to the function ... In this case, this coverage is also minimal.

For two Boolean functions, the disjunction operation corresponds to the union of their complexes of cubes, and the conjunction operation corresponds to the intersection of complexes of cubes. The negation of a function corresponds to the complement of a complex of cubes, that is, is determined by all vertices at which the function takes the value 0. Thus, there is a one-to-one correspondence (isomorphism) between the algebra of Boolean functions and Boolean sets representing complexes of cubes.

The representation of a function in the form of complexes of cubes is less clear, but its most important advantages are that it removes restrictions on the number of variables and makes it easier to encode information when using computers.

Minimizing Boolean Functions

Formulation of the problem. Minimizing a circuit in a Boolean basis is reduced to finding the minimum disjunctive form that corresponds to the minimum coverage. The total number of letters included in the normal form is expressed by the price of the cover , where is the number of - cubes forming a cover of the given function in n variables. The minimum coverage is characterized by the lowest value of its price.

Usually the minimization problem is solved in two steps. First, look for a reduced coverage that includes all -cubes of maximum dimension, but does not contain any cube covered by any cube of this coverage. The corresponding disjunctive normal form is called abbreviated, and its miniterms are called simple implicants. For this function, cut coverage is the only one, but it may be redundant due to the fact that some of the cubes are covered by collections of other cubes.

At the second step, the transition from reduced to dead-end disjunctive normal forms is carried out, from which the minimal forms are selected. Dead-end forms are formed by excluding all redundant cubes from the abbreviated coverage, without which the remaining set of cubes still forms a coverage of the given function, but upon further exclusion of any of the cubes, it no longer covers the sets of all vertices corresponding to unit values of the function, i.e., it ceases to be a coverage ...

A reduced coverage cube that covers the vertices of a given function that are not covered by any other cubes cannot be redundant and will always be included in the minimum coverage. Such a cube, like the corresponding implicant, is called an extremal (essential implicant), and the vertices it covers are called canceled vertices. The set of extremals forms the core of the coverage, it is clear that when going from reduced coverage to the minimum one, first of all, all extremals should be singled out. If the set of extremals does not form a cover, then it is supplemented to be covered with cubes from the reduced cover.

These definitions are illustrated in Fig. 3.9, where the reduced coverage (see Fig.3.9a, ) and the minimum coverage (Fig. 3.9b) and (see Fig. 3.9, b) are expressed as follows.