Reduting the rank of the conjunction, representing the root of the logical equation.pdf Логические уравнения используются в различных приложениях [1]. Они широко применяются в электротехнике, комбинаторике, логике высказываний, целочисленном программировании и др. Принято представлять корни таких уравнений конъюнкциями. Требования к качеству корня в общем случае зависят от контекста задачи. Например, построение тестовых наборов для неисправности сводится к решению соответствующего логического уравнения с представлением решения в виде конъюнкции. Проверяющий тест для класса неисправностей задается совокупностью таких конъюнкций. Чем меньше ранги конъюнкций, тем больше возможностей для сокращения длины проверяющего теста [2]. В данной работе предлагается модификация алгоритма Закревского [3] поиска одного корня логического уравнения. Целью модификации является построение конъюнкции по возможности меньшего ранга. В общем случае поиск корня сводится к сокращенному обходу дерева. С целью сокращенного обхода на каждом шаге выбирается переменная разложения, способствующая ускорению поиска корня уравнения. В работе [3] предлагаются правила выбора переменной разложения, причем предпочтение отдается однородным переменным, которые способствуют быстрому поиску, но не сокращению ранга. В предлагаемой модификации выбирается такая переменная в очередной вершине дерева разложения, которая способствует сокращению ранга конъюнкции. Выбор переменной осуществляется среди конъюнкций минимального ранга, сопоставляемых вершине, причем выбирается не обязательно однородная переменная. 1. Постановка задачи Рассмотрим ДНФ D = K V, ..., V Ks, зависящую от множества переменных X = {хь ..., xn}. Представим D в виде троичной матрицы M (множеством троичных векторов), сопоставив каждой конъюнкции троичный вектор. Компоненты троичного вектора принимают значения из множества {0, 1, x}. Здесь символ x означает неопределенную компоненту, которая может принимать значение либо 0, либо 1. Значения {0, 1} переменной троичного вектора будем называть определенными, значение x будем называть неопределенным. Троичный вектор, в котором определенные компоненты принимают только значение 1, будем называть положительно однородным вектором и отрицательно однородным, если определённые компоненты принимают только значение 0. Векторы, содержащие среди определенных компонент как 0, так и 1, будем называть неоднородными. Однородным столбцом, соответствующим переменной xu в матрице троичных векторов M будем называть столбец, состоящий либо из значений {0, x}, либо {1, x}. Матрицу М будем называть совместимой, если в ней все столбцы однородны. Максимально определенным столбцом будем называть столбец, состоящий из максимального числа определенных компонент. В качестве примера рассмотрим ДНФ D = x-lV x4v х2хзх4х5 v x1x4.xsx6vx1x3x4.xsx6 , матрица M в этом случае будет иметь следующий вид. Здесь столбцы, соответствующие переменным x1, x2, x3, являются однородными, а столбец, соответствующий переменной x4, является максимально определенным. Очевидно, что некоторая конъюнкция r, представляет корень уравнения D = 0, если она ортогональна каждой конъюнкции, представляемой строкой матрицы M. Ранг конъюнкции обозначим rang,. При анализе матрицы M будем придерживаться следующих правил. Правило 1. Если в троичной матрице M присутствует троичный вектор, в котором определена всего одна компонента, то соответствующая ей переменная в конъюнкции r, содержится с противоположным знаком инверсии. В этой ситуации из матрицы М могут быть удалены все троичные векторы, ортогональные троичному вектору, представляющему конъюнкцию rУ оставшихся троичных векторов соответствующая компонента может быть заменена значением x. Например, в рассматриваемом примере (табл. 1) два троичных вектора веса 1, тогда в конъюнкции r, могут присутствовать две переменные c противоположным знаком инверсии, т.е. х2, х4. Таблица 1 M = Xi X2 Хз Х4 Х5 Хб Ki X 1 X X X X Кг X X X 0 X X Кз X 1 0 1 1 X К4 0 X X 1 0 0 К 0 X 0 1 0 1 После упрощения матрица M будет иметь вид, представленный в табл. 2. Таблица 2 M = Xi Х2 Хз Х4 Х5 Хб К4 0 X X X 0 0 К 0 X 0 X 0 1 Если в результате упрощения в оставшейся матрице будет получен вектор, состоящий только из значений X, то рассматриваемое уравнение не имеет решения. Правило 2. Если в матрице присутствует однородный полностью определенный монотонный столбец, то соответствующая переменная включается в решение конъюнкцию r, с противоположным знаком инверсии. Троичный вектор, представляющий конъюнкцию, будет ортогонален всем векторам матрицы M, следовательно, является корнем. Например, в матрице M (табл. 2), полученной после упрощения, переменной x1 соответствует однородный столбец, следовательно, эту переменную можно включить в r, тогда r, = х1х2х4. Эти правила будут использоваться при отыскании корня уравнения D = 0, где D - произвольная ДНФ. 2. Поиск корня логического уравнения D = 0 Рассмотрим общую процедуру построения дерева разложения относительно некоторой переменной x, троичной матрицы M [4]. Из вершины дерева, отмеченной переменной x, исходят три дуги, помеченные значениями {0,1,X}. Каждой дуге сопоставляется соответствующее подмножество троичных векторов, полученное путем разбиения исходного множества M относительно переменной x, на три .. Д"1м0 Л"1;+1.. Л'ш X,!.. .Л-!;.! 1 Л"1;+1.. ,ХШ Рис. 1. Дерево разложения по переменной xt Среди множеств M\xi =1), M0(xi =0) выбирается множество большей мощности, и переменная x, включается в конъюнкцию r, со знаком инверсии, обеспечивающим ортогональность всем элементам выбранного множества. Во втором из рассматриваемых множеств переменной x, присваивается значение X, и полученное в результате множество троичных векторов объединяется с Mx(xt = x). Новое множество М сопоставляется со следующим шагом разложения. При этом дерево корректируется, так что из вершины, помеченной x, исходят две дуги, одна из которых помечена определенным значением, а другая значением x. Если на очередном шаге разложения выясняется, что конъюнкция r, не может быть достроена до корня уравнения, т.е. в множестве, сопоставляемом дуге, отмеченной переменной x, присутствует вектор из одних неопределенных компонент, то возвращаемся в ближайшую вершину дерева разложения, для которой оба множества M1(xi =1), M°(X( =0) не пусты. 2.1. Достаточные условия существования корня логического уравнения Ведем следующие обозначения: M+ - подмножество положительно однородных векторов; М~ - подмножество отрицательно однородных векторов; M* - подмножество неоднородных векторов. Утверждение 1. Если множество M = M , то корень уравнения существует. Доказательство. Пусть множество M состоит только из неоднородных троичных векторов. Значения определенных компонент в неоднородном троичном векторе принимают 0 и 1, следовательно, найдется такой троичный вектор, представляющий корень уравнения, который будет ортогонален всем векторам из M либо только по компонентам 1, либо только по компонентам 0. Утверждение доказано. Рассмотрим множество M (табл. 3), вектор 1x11xx, ортогональный всем троичным векторам по определенному значению 0, а троичный вектор x0x0xx ортогонален всем троичным векторам по значению 1. Таблица 3 M = *1 *2 *3 Х4 *5 x6 Ki 0 1 x x 0 x K2 1 1 x 0 x x Кз x 1 0 1 1 x К4 0 x x 1 0 0 Утверждение 2. Если множество M = М* М~ либо M = М* U М+, то корень уравнения существует. Доказательство. Рассмотрим случай, когда M = М* U М~, т.е. наряду с неоднородными векторами присутствуют однородно отрицательные векторы, следовательно, в каждом векторе присутствуют определенные компоненты со значением 0, тогда найдется такой троичный вектор, представляющий корень уравнения, который будет ортогонален всем векторам из M по компонентам со значением 0. В случае M = М* U М+ найдется такой троичный вектор, представляющий корень уравнения, который будет ортогонален всем векторам из M по компонентам со значением 1. Утверждение доказано. подмножества, обозначим их следующим образом: M1(x; = 1), M(xi =0), Mx(xi = x) по значениям {0,1,х}(рис. 1). Например, во множестве M (табл. 4) вектор 1x1xx ортогонален всем троичным векторам по определенным компонентам со значением 0. Таблица 4 M = Xl X2 Хз Х4 Х5 Хб Kl 0 X X X 0 X K2 0 0 X 0 X X Кз X 1 0 1 1 X К 0 X X 1 0 0 В множестве троичных векторов M выполним упрощения по правилам 1, 2. Пусть M** = М+ U М~. Утверждение 3. Если множество M представляется в виде M = М* U М+ U М~ и M** совместимо, то корень уравнения существует. Доказательство. Пусть подмножество M * совместимо, тогда найдем пересечение между этими троичными векторами. Результатом пересечения является неоднородный вектор V. Получим вектор V* путем инвертирования всех значений вектора V, таким образом, V* ортогонален всем векторам из M*. Так как M*состоит из неоднородных векторов, то найдется вектор V**, совместимый с вектором V*, ортогональный всем элементам из M* . Утверждение доказано. Например, в множестве M (табл. 5) выделим множество M**, которое состоит из двух троичных векторов, 11XXXX и XXX000. Результатом их пересечения будет вектор V = 11x000, получим вектор V* = 00x111. По утверждению 3 найдется вектор, совместимый с V* и ортогональный всем векторам из M*. В нашем случае V** = x0xx1x. Таблица 5 М= Xl Х2 Хз Х4 Х5 Хб Ki 1 1 X X X X К2 X X X 0 0 0 Кз X 1 0 1 1 X К4 0 X X 1 0 0 Ks 0 X 0 1 0 1 Например, полученный вектор V** поглощает вектор V*, тогда результирующий вектор R = V**, он содержит меньшее количество компонент и ортогонален всем элементам матрицы M (табл. 5). 2.2. Выбор переменой разложения Предлагаются следующие правила выбора переменной разложения. Рассмотрим множество векторов, представляемое матрицей M. Исключим из матрицы все поглощаемые векторы, далее упорядочим векторы по возрастанию их рангов. Выделим группу векторов, содержащую троичные векторы минимального ранга. В этой группе выделяем множество монотонных векторов М+(М~) и среди последних векторов выполняем поиск максимально определенных столбцов, среди выбранных столбцов предпочтение отдается тому, который имеет максимальное число определенных компонент в множестве М. Сопоставляемая этому столбцу переменная выбирается в качестве переменной разложения. В случае отсутствия однородных векторов в группе предпочтение отдается столбцу, который имеет максимальное число определенных компонент в множестве М. Если существует несколько неоднородных столбцов с максимальным числом определенных компонент, то для каждого столбца подсчитываем число единичных и нулевых компонент. Предпочтение отдаем столбцу с максимальным числом либо значений 0, либо значений 1. Иначе выбираем любой столбец с максимальным числом определенных компонент. Сопоставляемая ему переменная выбирается в качестве переменной разложения. Рассмотрим пример (табл. 6). Здесь K1, K2, K3, K4 образуют подмножество троичных векторов минимального ранга, в котором присутствуют однородно отрицательные троичные векторы K1, K2. 1 х 0 х х х х х х 1 0 х 1 1 х 0 х х х10 х Ох 1 1 х х 0 х Xi X2 Хз Х4 Х5 Хб К1 1 X X X X 0 Кг 1 X 1 X 1 X Кз 1 X X X 0 1 К4 1 0 X X 1 1 К 1 1 0 X X 1 Кб 0 0 X X 1 X К7 0 1 X X X 1 Таблица 6 М= Xi X2 Хз X4 X5 X6 Ki x x x x 0 0 Кг x x x 0 x 0 Кз 1 x 0 x x x К4 x x x 1 0 x К 1 X 1 0 X X К6 1 1 X 0 X X К7 X 1 0 X 0 X К8 1 1 X X 0 X К9 X 1 1 X X 0 По утверждению 2 корень уравнения существует. В качестве переменной разложения выбираем максимально определенную компоненту из множества однородно отрицательных векторов, а именно компоненту, отмеченную переменной х6. Из вершины, помеченной х6, исходят две дуги: одна дуга, помеченная значением 0, вторая дуга, помеченная значением X. Для множества, сопоставляемого дуге со значением X, разложение продолжается, как показано на (рис. 2). Корень уравнения найден, если на очередном шаге разложения множество, сопоставляемое дуге со значением X, оказывается пустым. Построенная конъюнкция представляет корень уравнения. Для рассматриваемого примера r = x1x5x6. 1 х 0 х х х 1x10 х х 1 1 х 0 х х 1 1 х х 0 х М=0 Рис. 2. Дерево разложения по переменной xt Рассмотрим множество М, представленное в табл. 7 и 8, для которого корня не существует. Дерево разложения представлено на рис 3. Таблица 7 Таблица 8 Xi Хг Хз Х4 Х5 Хб К8 0 X X X 0 1 К9 0 X X 0 1 0 К10 0 1 X 1 0 0 К11 0 1 X 1 1 0 К12 0 X 1 X 0 0 К13 0 0 0 X 0 0 X 1 X X X X ххОххх х X X X X X Неткорня Рис. 3. Дерево разложения множества M в случае отсутствия корня 3. Экспериментальные результаты Предложенная модификация программно реализована и испытана на случайно сгенерированных примерах, полученных с помощью программы [5]. Генерировались примеры разной размерности и разной разреженности по неопределённым компонентам. Результаты сравнивались с алгоритмом Закрев-ского. Как показали экспериментальные результаты (см. табл. 9, 10), предложенная модификация сокращает ранг конъюнкции. Таблица 9 Таблица 10 № i t %dc rZ rDR 8 350 2000 25 150 148 9 350 3000 30 120 116 10 350 3000 35 220 213 11 400 3000 45 223 219 12 400 3000 65 131 126 13 500 3000 70 157 150 14 500 3000 85 194 186 Здесь i - длина вектора, t - число векторов матрицы M, %dc - процент неопределенных компонент, rZ - ранг корня, полученного с помощью алгоритма Закревского, rDR - ранг корня, полученного с помощью предложенного алгоритма. Заключение В работе предложена модификация алгоритма Закревского поиска одного корня логического уравнения. Целью модификации является построение корня по возможности меньшего ранга. Корень уравнения строится с помощью дерева разложения. Предложены эвристики выбора переменной разложения, ориентированные на сокращение ранга конъюнкции, представляющей корень уравнения. Эффективность предложенной модификации подтверждается экспериментально. Сформулированы достаточные условия существования корня уравнения D = 0. № i t %dc rZ rDR 1 100 500 15 39 37 2 100 500 25 22 19 3 100 1000 50 37 34 4 200 1000 60 40 37 5 200 1300 70 57 51 б 300 1500 75 35 30 7 300 1500 85 92 63

Скачать электронную версию публикации