View source for Boolean functions, minimization of

A representation of Boolean functions by normal forms (cf. [[Boolean functions, normal forms of|Boolean functions, normal forms of]]) that are most simple relative to some measure of complexity. The usual meaning of the complexity of a normal form is the number of letters in it. A simplest form is then called a minimal form. A measure of complexity sometimes used is the number of elementary conjunctions in a disjunctive normal form or the number of factors in a conjunctive normal form. In this case a simplest form is called a shortest form. In view of the duality of disjunctive and conjunctive normal forms, it is sufficient to consider disjunctive normal forms only.

The construction of shortest and minimal disjunctive normal forms each has its own specific features. The sets of minimal and shortest disjunctive normal forms of one and the same function may be connected by set-theoretical relations: of being contained one in one another, of having an empty intersection or a non-empty symmetric difference. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b0169601.png" /> be the complexity of the minimal disjunctive normal form of a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b0169602.png" />, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b0169603.png" /> be the minimal complexity of its shortest disjunctive normal form and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b0169604.png" /> be the largest of the ratios <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b0169605.png" /> over all functions in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b0169606.png" /> variables. Then the following asymptotic relation holds:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b0169607.png" /></td> </tr></table>

By the problem of minimization of Boolean functions one usually understands that of constructing their minimal disjunctive normal forms. There is a trivial algorithm for constructing all minimal disjunctive normal forms of an arbitrary Boolean function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b0169608.png" />, which operates as follows: All disjunctive normal forms in the variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b0169609.png" /> are reviewed, and those which realize the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696010.png" /> and have minimal complexity are selected. In fact, this algorithm is not applicable even for small <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696011.png" />, since the number of operations required increases rapidly. Many other algorithms have therefore been constructed, which, however, are not effectively applicable to all functions.

The initial specification of a function in the problem of minimization is usually a table, a perfect disjunctive normal form (cf. [[Boolean functions, normal forms of|Boolean functions, normal forms of]]) or an arbitrary disjunctive normal form. The first stage consists in the transition to the so-called abridged disjunctive normal form, which is uniquely determined for each function. Many methods for the realization of this transition are available. The most universal method consists in performing transformations on a disjunctive normal form of the type

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696012.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696013.png" /></td> </tr></table>

A typical property of the abridged disjunctive normal form is that it is possible to obtain any minimal abridged disjunctive normal form from it by removing certain elementary conjunctions. The second, most laborious stage is to extract from the abridged disjunctive normal form all dead-end disjunctive normal forms, among them all the minimal ones. A geometrical representation of Boolean functions is usually employed at this stage. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696014.png" /> denote the set of all vertices of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696015.png" />-dimensional unit cube. Each Boolean function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696016.png" /> is in one-to-one correspondence with the subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696017.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696018.png" />, of vertices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696019.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696020.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696021.png" /> be an elementary conjunction of rank <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696022.png" />. The set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696023.png" /> is then called an interval of rank <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696025.png" /> corresponding to the elementary conjunction <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696026.png" />. One says that a system of intervals <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696027.png" /> forms a covering of a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696028.png" /> if

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696029.png" /></td> </tr></table>

Since the equalities

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696030.png" /></td> </tr></table>

are equivalent, the problem of minimization of Boolean functions is equivalent to the search for coverings with a minimal sum of the ranks of their intervals. Such coverings are called minimal. An interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696031.png" /> is called maximal for a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696032.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696033.png" /> and if there is no interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696034.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696035.png" />. The construction of dead-end disjunctive normal forms of a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696036.png" /> reduces to a search for coverings of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696037.png" /> by maximal intervals such that no proper subset of it is a covering of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696038.png" />. These coverings correspond to dead-end disjunctive normal forms and are called irreducible. They are obtained from coverings corresponding to abridged disjunctive normal forms by removal of certain intervals.

The selection of the minimal disjunctive normal forms from all dead-end disjunctive normal forms is also a very laborious process, since  "almost-all"  Boolean functions in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696039.png" /> arguments have no fewer than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696040.png" /> different dead-end disjunctive normal forms. The diversity of the complexities of dead-end disjunctive normal forms may be very wide, so that if a random rather than a dead-end minimal disjunctive normal form is selected, a large error may result.

Estimates of the number of dead-end disjunctive normal forms and of the scatter of their complexities show that a more detailed inspection during the elimination of the elementary conjunctions from a disjunctive normal form is a natural way of improving the effectiveness of minimization algorithms. A conjunction should be eliminated (or, on the contrary, retained until the end of the process) only if it can be established by some procedure that it does not occur in any minimal disjunctive normal form for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696041.png" /> (occurs in all minimal disjunctive normal forms for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696042.png" />). The latter fact is usually established by an analysis of the conjunctions that are close to the one in question, i.e. occur in a neighbourhood of it (cf. [[Algorithm, local|Algorithm, local]]). Here one has to accumulate information about elementary conjunctions and use it in the subsequent analysis. Procedures of this kind are known as local simplification algorithms. Some of them are quoted below, and their description involves the concept of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696044.png" />-th order neighbourhood <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696045.png" /> of an elementary conjunction <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696046.png" /> in a disjunctive normal form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696047.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696048.png" />.

The zero-order neighbourhood <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696049.png" /> consists of the single conjunction <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696050.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696051.png" /> is the neighbourhood of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696052.png" />, then the neighbourhood <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696053.png" /> of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696054.png" /> consists of all conjunctions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696055.png" /> of the disjunctive normal form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696056.png" /> that satisfy one of the following conditions: 1) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696057.png" /> has a non-empty intersection with at least one interval corresponding to a conjunction of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696058.png" />; or 2) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696059.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696060.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696061.png" />, satisfies 1).

Quine's algorithm. Here one considers at each step the neighbourhood <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696062.png" /> of one of the conjunctions in the disjunctive normal form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696063.png" />. As the algorithm is executed for each conjunction, one attempts to compute one of the following properties:

<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696064.png" /> —  "A occurs in all minimal disjunctive normal forms" ; and

<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696065.png" /> —  "A does not occur in any minimal disjunctive normal form" .

The algorithm works as follows. 1) The neighbourhood <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696066.png" /> is successively formed for each conjunction <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696067.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696068.png" />. The inclusion <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696069.png" /> is verified. If this is not the case, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696070.png" /> is marked in some way as belonging to all minimal disjunctive normal forms. One says that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696071.png" /> is part of the kernel of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696072.png" /> (is a kernel conjunction). 2) Let the conjunctions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696073.png" /> be marked in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696074.png" /> in the first stage. The remaining conjunctions in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696075.png" /> are ordered, and the inclusion <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696076.png" /> is checked for each such conjunction <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696077.png" />. Conjunctions satisfying this relation do not occur in any minimal disjunctive normal form and are removed from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696078.png" />.

Regular points algorithm. During each step of this algorithm one examines the neighbourhood <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696079.png" /> of a conjunction <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696080.png" /> in the disjunctive normal form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696081.png" />, and the conjunctions not occurring in any dead-end disjunctive normal form, and hence not occurring in any minimal disjunctive normal form either, are eliminated. The description of the algorithm involves the concept of an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696083.png" />-bundle in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696084.png" />, which, for this point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696085.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696086.png" />, is the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696087.png" /> of intervals <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696088.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696089.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696090.png" />. For a conjunction <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696091.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696092.png" /> a point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696093.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696094.png" /> is called regular with respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696095.png" /> if there exists a point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696096.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696097.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696098.png" />. A set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b01696099.png" /> is called regular with respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960100.png" /> if all its points are regular with respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960101.png" />. This algorithm is based on the fact that a conjunction <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960102.png" /> of the abridged disjunctive normal form of a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960103.png" /> does not occur in any dead-end disjunctive normal form of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960104.png" /> if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960105.png" /> is a regular set with respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960106.png" />. The algorithm checks whether in a certain sequence the conjunction intervals occurring in the disjunctive normal form are regular sets and eliminates those that are regular. Whether or not an interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960107.png" /> is regular with respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960108.png" /> is completely determined by the neighbourhood <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960109.png" /> but not, in general, by the neighbourhood <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960110.png" />.

The <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960112.png" />-algorithm. The concept employed here is that of a disjunctive normal form that is minimal with respect to a disjunctive normal form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960113.png" />, i.e. one that is minimal among all disjunctive normal forms that are equivalent to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960114.png" /> and are obtained from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960115.png" /> by omission of certain elementary conjunctions. Two properties of an elementary conjunction in a disjunctive normal form are considered:

<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960116.png" /> —  "A occurs in all disjunctive normal forms that are minimal with respect to N" ; and

<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960117.png" /> —  "A occurs in no disjunctive normal form that is minimal with respect to N" .

It is assumed that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960118.png" /> if the property <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960119.png" /> holds, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960120.png" /> otherwise. It is also assumed that disjunctive normal forms are formed from conjunctions with informative marks <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960121.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960122.png" />. The equality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960123.png" /> means that the property <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960124.png" /> has not been calculated <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960125.png" />, while the equalities <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960126.png" /> mean that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960127.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960128.png" />. A conjunction <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960129.png" /> with informative marks (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960130.png" />) is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960131.png" />. The <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960132.png" />-algorithm computes the values of the properties <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960133.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960134.png" /> for the conjunctions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960135.png" /> in the disjunctive normal form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960136.png" />, using for this purpose only the conjunctions of the neighbourhood <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960137.png" /> and their informative marks. For a conjunction <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960138.png" /> of rank <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960139.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960140.png" /> a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960141.png" /> is called a set of the first type relative to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960142.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960143.png" /> contains conjunctions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960144.png" /> of ranks <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960145.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960146.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960147.png" />.

The difference <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960148.png" /> of two disjunctive normal forms <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960149.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960150.png" /> is the disjunctive normal form consisting of the elementary conjunctions occurring in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960151.png" /> but not in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960152.png" />.

Before the application of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960153.png" />-algorithm all conjunctions of the disjunctive normal form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960154.png" /> have the mark <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960155.png" />. After <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960156.png" /> steps have been performed and the conjunctions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960157.png" /> have received the mark <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960158.png" />, and the conjunctions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960159.png" /> have received the mark <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960160.png" />, the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960161.png" />-th step consists of the following. The conjunctions in the disjunctive normal form are ordered in some way. If the disjunctive normal form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960162.png" /> is empty, the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960163.png" />-algorithm is terminated. If it is not, the conjunctions of this disjunctive normal form are ordered in some way; the first conjunction <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960164.png" /> in the sequence and its neighbourhoods <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960165.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960166.png" /> in the disjunctive normal form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960167.png" /> are singled out, and the relation

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960168.png" /></td> </tr></table>

is checked. If it is satisfied, the mark <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960169.png" /> over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960170.png" /> is replaced by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960171.png" /> and the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960172.png" />-th step of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960173.png" />-algorithm is terminated. If not, then a check is made whether or not <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960174.png" /> can be represented in the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960175.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960176.png" /> is a regular set relative to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960177.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960178.png" /> is a set of the first type relative to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960179.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960180.png" /> can be represented in this form, the mark <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960181.png" /> over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960182.png" /> is replaced by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960183.png" /> and the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960184.png" />-th step of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960185.png" />-algorithm is terminated; if this is not possible, the procedure is applied to the second conjunction in the sequence, etc. If the mark does not change in any one of these conjunctions, then after all the conjunctions have been examined, the operation of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960186.png" />-algorithm is terminated.

If the abridged disjunctive normal form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960187.png" /> of a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960188.png" /> is taken for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960189.png" />, then no conjunctions that obtained in the algorithm the mark <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960190.png" /> occur in any minimal disjunctive normal form of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960191.png" />; they are eliminated from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960192.png" />. Conjunctions that obtained the mark <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960193.png" /> occur in all minimal disjunctive normal forms of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960194.png" />. Various special cases of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960195.png" />-algorithm have also been considered.

The ring algorithm places over the conjunctions informative marks <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960196.png" />, with the same meaning as in the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960197.png" />-algorithm. At each step of the ring algorithm use is made of the conjunctions contained in the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960198.png" />-th order neighbourhood of some conjunction and of their informative marks. A simplified version of this algorithm is outlined below. The ring algorithm in its complete form is the best local algorithm with a special memory relative to the neighbourhoods <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960199.png" />. The algorithms described above are special cases of the general ring algorithm. If

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960200.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960201.png" /></td> </tr></table>

and

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960202.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960203.png" /></td> </tr></table>

then to each subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960204.png" /> a Boolean function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960205.png" /> that is not everywhere defined is assigned, such that the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960206.png" /> of its ones is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960207.png" /> and the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960208.png" /> of its zeros is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960209.png" />; the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960210.png" /> is not defined on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960211.png" />. The set of such functions is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960212.png" />. Prior to the beginning of the algorithm the conjunctions of the disjunctive normal form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960213.png" /> in question have the mark <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960214.png" />. If, after <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960215.png" /> steps have been completed, conjunctions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960216.png" /> with the mark <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960217.png" /> and conjunctions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960218.png" /> with the mark <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960219.png" /> are obtained, then the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960220.png" />-th step is performed as follows. The conjunctions of the disjunctive normal forms are ordered in some way. If the disjunctive normal form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960221.png" /> is empty, the algorithm is terminated. If not, then all conjunctions of this disjunctive normal form are ordered in some way. For the conjunction <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960222.png" /> which is the first in the sequence and for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960223.png" /> from the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960224.png" />, all disjunctive normal forms which realize <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960225.png" /> on its domain of definition, which consist of conjunctions in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960226.png" /> and which contain the least number of variable symbols as compared with other such disjunctive normal forms, are found. Among them one selects all disjunctive normal forms which, first, do not contain the conjunctions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960227.png" /> and, secondly, contain all the conjunctions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960228.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960229.png" />, for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960230.png" />. If for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960231.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960232.png" /> the conjunction <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960233.png" /> occurs in all disjunctive normal forms selected, then the mark <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960234.png" /> over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960235.png" /> is replaced by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960236.png" /> and the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960237.png" />-th step of the algorithm is terminated. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960238.png" /> does not occur in any disjunctive normal form selected, then the mark <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960239.png" /> is changed into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960240.png" /> and the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960241.png" />-th step of the algorithm is terminated. Otherwise, the procedure just described is applied to the conjunction that is next in sequence, etc. If the mark cannot be changed for any conjunction, the algorithm terminates at the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960242.png" />-th step. All conjunctions obtained in the ring algorithm over the abridged disjunctive normal form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960243.png" /> of a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960244.png" /> with mark <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960245.png" /> (or, respectively, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960246.png" />) occur in all minimal disjunctive normal forms (or, do not occur in any minimal disjunctive normal form) of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960247.png" />. The algorithms just described yield identical results, whatever the manner of ordering of the conjunctions in the disjunctive normal form.

The task of selecting all conjunctions occurring in at least one or not occurring in any minimal disjunctive normal form cannot be solved by algorithms working with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960248.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960249.png" /> is bounded or increases too slowly as the number of variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960250.png" /> increases. This situation does not change if to the properties <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960251.png" /> stored in the algorithm a bounded set of properties or one that increases too slowly as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960252.png" /> increases is added.

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  S.V. Yablonskii,   "Functional constructions in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016960/b016960253.png" />-placed logic"  ''Trudy Mat. Inst. Steklov.'' , '''51'''  (1958)  pp. 5–142  (In Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  Yu.I. Zhuravlev,   "Set-theoretical methods in the algebra of logic"  ''Problemy Kibernet.'' , '''8'''  (1962)  pp. 5–44  (In Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  W.V. Quine,   "On cores and prime implicants of truth functions"  ''Amer. Math. Monthly'' , '''66'''  (1959)  pp. 755–760</TD></TR></table>