Разложение логических определителей по блокам

Садовников Н.В., Будимирова Т.С.

Ключевые слова: разложение общего логического определителя по элементам, блочное разложение логического определителя, иерархическая процедура вычисления логического определителя, сложность вычисления логического определителя, дихотомическая процедура, число этапов в оптимальной процедуре.

Аннотация. Рассматривается возможность разложения логических определителей по блокам в отличие от традиционного разложения по элементам. Определяя порядок блок – логических определителей, выбираемых на каждом шаге иерархической процедуры раскрытия логического определителя, а соответственно, и общее число шагов, выбираем эти параметры так, чтобы минимизировать получаемое выражение логического определителя. Выяснили, что минимальной по сложности оказывается та из многоэтапных процедур отыскания выражения бесконечного логического определителя, у которой на каждом этапе в группы объединяются по две строки (общее число строк уменьшается вдвое). Это дихотомическая процедура.

Decomposition of logical determinants into blocks

Sadovnikov N.V., Budimirova T.S.

Keywords: element decomposition of a common logical determinant, block decomposition of a logical determinant, hierarchical procedure for computing a logical determinant, complexity of computing a logical elements, dichotomous procedure, number of steps in the optimal procedure.

Abstract. The possibility of decomposition of logical determinants by blocks is considered, in contrast to the traditional decomposition by elements. Determining the order of block- logical determinants selected at each step of the hierarchical procedure for expanding the logical determinant, and, accordingly, the total number of steps, we choose these parameters in such a way as to minimize the resulting expression of the logical determinant. Found out that the minimum in complexity is that of the multi-stage procedures for finding the expression of an infinite logical determinant, in which at each stage two rows are combined into groups (the total number of rows is halved). It is dichotomous procedure.