Resolvent method

The Resolventenmethode (Engl. Resolvent method , resolution method ) is one of John Alan Robinson described around 1963 method for calculating all Primterme to Boolean functions to be minimized. In contrast to the Quine and McCluskey method , the resolvent method does not require a canonical disjunctive normal form .

The following two laws are required for implementation:

General resolution law: ${\ displaystyle x \ cdot a + {\ bar {x}} \ cdot b = x \ cdot a + {\ bar {x}} \ cdot b + a \ cdot b}$
Law of absorption: ${\ displaystyle a \ cdot b + a = a}$

One possible scheme for performing the resolvent method is the layering algorithm . The given disjunctive normal form is written as layer 0 in the first line. Now each term is compared with each other and it is checked whether the general law of resolution can be applied. If this is the case, the resolvent ( in the above formula) is written to the next line. This line is then named Layer 1. Next, it is checked whether the law of absorption can be applied between the added resolvent and a term of the upper layer. The corresponding term in layer 0 is deleted. ${\ displaystyle a \ cdot b}$

After all the terms in layer 0 have been compared with each other, you proceed in the same way with the terms in layer 1, whereby it should be noted that the terms must also be compared with the terms in the upper layers. Terms deleted due to absorption are not considered further.

This is repeated until no more new terms can be generated. The remaining terms are all prime terms of the function. Now some prime terms have to be selected so that a minimal function arises. The selection is identical to that of the Quine and McCluskey method.

Example:

literature

Friedrich L. Bauer , Martin Wirsing : Elementary propositional logic. Mathematics series for computer scientists, Springer Verlag, 1991, Chapter 15: The resolvent method , ISBN 978-3-540-52974-3 .