е. набор вида [ ] (…)), то исходная ДНФ общезначима.

Рассмотрим теперь работу блока обратного метода. Сначала мы формируем базу наборов для обратного метода. Для каждой переменной p проделываются следующие действия. Пусть дизъюнкт i содержит переменную p на k-м месте, а дизъюнкт j — ~p на l-ом месте. Тогда в базу наборов добавляется набор [i/k, j/l] ( ) — замкнутый набор, или набор с пустой зависимостью.

Продолжение Примера 2.
На вход обратного метода поступает D 2.1:
(~a&d) Ъ (b&a) Ъ (~a&~d ) Ъ (~b&~d) Ъ (~b&d)

По контрарным парам литер строятся все возможные замкнутые наборы:
#1 [2/1 4/1] ( ) — наборы, соответствующие переменной b

#2 [2/1 5/1] ( )

#3 [1/1 2/2] ( ) — наборы, соответствующие переменной a

#4 [2/2 3/1] ( )

#5 [1/2 3/2] ( ) — наборы, соответствующие переменной d

#6 [1/2 5/2] ( )

#7 [3/2 4/2] ( )

#8 [4/2 5/2] ( )

Здесь #n означает, что данный набор записан под номером n; все номера наборов уникальны.

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

· Если в одном из наборов в зависимости есть число s, то в других наборах не должно быть членов вида s/r;

· Если в каком-нибудь наборе есть член вида s/r, то ни в одном из других наборов не должно быть членов s/t;

· Ни один из наборов не должен иметь в зависимости число i;

Если все эти требования выполнены, то создается новый набор по указанному выше правилу; он добавляется в базу наборов. Так продолжается до тех пор, пока мы не получим пустой набор или пока не будут построены все возможные наборы. В первом случае исходная формула общезначима, во втором – нет.

Для упрощения поиска в базе наборов в программе создается списочная таблица: для каждых i, j она предоставляет список наборов, которые содержат член i/j. Для рассматриваемого примера 2 таблица имеет следующий вид:

№ дизъ.
Индекс
№ набора

1
1
3

1
2
5,6

2
1
1,2

2
2
3,4

3
1
4

3
2
5,7

4
1
1

4
2
7,8

5
1
2

5
2
6,8


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

Для ускорения работы программы необходимо на каждом шаге, по возможности, уменьшить число наборов, могущих участвовать в выводе. Это связано с тем, что предложенный алгоритм «механически» строит все возможные «склейки» существующих наборов (об этом смотри выше). Для уменьшения числа участвующих в выводе наборов предусмотрено несколько режимов работы алгоритма:

· Наиболее существенный выигрыш дает лемма о поднаборности [20]. Она говорит, что если мы получили набор, являющийся наднабором некоторого имеющегося набора, то вновь полученный набор можно исключить из дальнейшего рассмотрения. Использование этой леммы позволяет сократить перебор. Например, если в базе наборов имеется набор [3/1, 4/2] (...) (набор a), а построенный набор имеет вид [3/1, 4/2, 6/4] (...), то новый набор, являющийся наднабором набора a, не дает ничего нового: он «слабее» того «поднабора» a, который уже имеется в базе наборов. Поэтому его можно не рассматривать в дальнейшем. Наоборот, если построен набор [4/2] (…), который является поднабором набора a, то он переносится в базу наборов, а набор [3/1, 4/2] (…) (набор a), соответственно, удаляется из базы наборов.

· Другой способ сокращения числа наборов (и соответственно, времени поиска) основывается на том, что правило склейки является «локальным» правилом, позволяющим за одно свое применение удалить не более одного члена из состава исходных наборов. Поэтому можно предложить следующую тактику работы алгоритма. Для получения пустого набора нам необходимо иметь совокупность однолитерных наборов [i/1] (…), …, [i/n] (…) для некоторого i. Тогда вместо того, чтобы искать пустой набор, зафиксируем число i и будем последовательно искать наборы [i/1] (…) ,…, [i/n](…). При этом, пытаясь вывести набор [i/1] (…), мы можем не рассматривать наборы, содержащие члены i/2, … , i/n, что существенно сокращает число наборов, участвующих в выводе на этом этапе. Если мы найдем все такие наборы, то ДНФ выводима; иначе (если мы не смогли построить какой-нибудь из этих наборов) мы удаляем из базы все наборы, содержащие элемент i/j, и повторяем поиск. Эта тактика, первоначально предложенная в [20], является аналогом метода расщепления.

Продолжение Примера 2.
Теперь, по имеющейся базе наборов реализуем обратный метод для нашего примера. Мы рассмотрим вариант, когда он работает, используя тактику расщепления с расщеплением и лемму о поднаборности, поскольку это наиболее сложный случай работы алгоритма. Итак, мы имеем восемь исходных наборов:

#1 [2/1 4/1] ( )

#2 [2/1 5/1] ( )

#3 [1/1 2/2] ( )

#4 [2/2 3/1] ( )

#5 [1/2 3/2] ( )

#6 [1/2 5/2] ( )

#7 [3/2 4/2] ( )

#8 [4/2 5/2] ( )

Допустим, что наш алгоритм начал свою работу с «расщепления» последнего дизъюнкта и алгоритм пытается построить набор, содержащий в теле только элемент 5/2.