Таблица 3. Унифицированные СКТ S1 и S2

S1

S2

Теоретически для исходных СКТ потенциально существуют оптимальные структуры S10 и S20, построенные следующим образом: из S1 и S2 соответственно исключены все строки, не входящие в объединение элементарных СКТ, представляющих СВН в каждой из двух структур. Оптимальные СКТ по построению пусты, если СВН отсутствуют. Концепция потенциально существующих, хотя и недоступных для исследователя до решения задачи, структур, имеющих некоторые очевидные свойства, принципиальна для обоснования и построения излагаемого далее алгоритма классификации формулы.

Примем S1 за базисную структуру и установим для нее исходную нумерацию переменных: x1, x2 , ... , xn (в рассматриваемом примере исходная нумерация переменных: a, b, ... , h). Базисную структуру удобно представить графом (также базисным), вершины которого расположены в соответствии с ярусами СКТ и отмечены наборами троек; ребра отображают сочленения троек в соседних ярусах по двум совпадающим значениям переменных. Каждая вершина по построению соединена одним или двумя ребрами с вершинами предыдущего и последующего ярусов. Выполняющие наборы ассоциируются с маршрутами в базисном графе (БГ), каждый из которых включает одну вершину каждого яруса (однократно) и соединяющие их ребра, - в дальнейшем рассматриваются только такие маршруты. Так, граф G1 = (V, E), изображенный на рис. 1, соответствует структуре S1 , представленной таблицей 3. В нашем иллюстративном примере отыскание СВН для СКТ S1 и S2 будет означать решение задачи 3-ВЫП для подформулы F формулы F. В таблице 1 F представлена подмножеством строк, на основе которых сформированы структуры S1 и S2 до их унификации.

0 0 1

0 1 0

1 0 1

0 1 1

a b c

b c d

1 0 11 1 1c d e

110 def

1 1 01 0 1e fg

1 0 00 1 1fg h

Рис. 1. Базисный граф

Для решения задачи введем новый объект - гиперструктуру (ГС). С этой целью создадим копию G2 базисного графа (с сохранением обозначений вершин и ребер, принятых в графе G1), которая будет играть роль каркаса гиперструктуры. Гиперструктура Г формируется в результате приписывания вершинам и ребрам каркаса определенных подструктур СКТ S2. Каждой вершине Vj в гиперструктуре Г приписана подструктура-вершина TCj c S2 , полученная путем конкретизации в S2 троек переменных в соответствии со значениями, указанными в одноименной вершине графа G1 (будем также говорить, что 7tj помещена в Vj ), каждому ребру (vj , vk) приписана подструктура-ребро 7tj k = 7tj n nk . Таким образом, гиперструктура - это граф, сохраняющий топологию и ярусное строение базисного графа, но содержащий структурированные вершины и ребра. Отметим, что сквозная нумерация вершин и ребер в последующих рассуждениях не потребуется, и подстрочный индекс в обозначениях вершин будет указывать номер яруса.

В результате конкретизации переменных некоторые из названных подструктур могут оказаться пустыми, что влечет удаление одноименных элементов (вершин или ребер) из графов G1 и G2 , причем вершины удаляются вместе со всеми инцидентными им ребрами. Кроме того, согласно ярусному строению, никакая вершина в графах G1 и G2 не может существовать без смежных вершин, расположенных на соседних ярусах. Наконец, если обнаруживается, что хотя бы один ярус в ГС пуст, вся гиперструктура объявляется пустым множеством. Отметим, что пересечения подструктур, расположенных на одном ярусе ГС, по построению являются пустыми.

Введем в рассмотрение несколько важных понятий, которые потребуются для определения эффективной процедуры построения ГС.

0 1 1

1 1 1

Назовем j-пересечением подструктур в ГС пересечение j подструктур, расположенных на каждом из ярусов с номерами 1, 2, ... , j .

Определим операцию проецирования r -го яруса на подструктуру 77 j -го яруса ( j > r ). Операция заключается в вычислении пересечений 77 с каждой подструктурой r -го яруса, с последующим объединением указанных пересечений. Результирующая подструктура замещает 77 .

Продвижением подструктуры-вершины j -го яруса по ребру (vj , Vj+1) с одновременным вычислением подструктуры-ребра nj, j+1 назовем конкретизацию переменной Xj+3 подструктуры TCj согласно значению, указанному для этой переменной в соответствующей вершине Vj+1 базисного графа, с последующим поочередным проецированием (при j > 2 ) ярусов с номерами 1, 2, ... , j - 1 на подструктуру, полученную в результате конкретизации. При этом каждый очередной ярус проецируется на подструктуру, которая является продуктом всех предшествующих операций проецирования. В результате продвижения для ребра (Vj , Vj+1) базисного графа формируется подструктура-ребро 7% Подструктура nj после указанных операций восстанавливается в том виде, в каком она существовала до конкретизации переменной Xj+3 . Если Vj - единственная вершина j -го яруса, смежная с Vj+1, то подструктура-вершина 7 j+1 совпадает с подструктурой-ребром; при наличии двух ребер - (vj , Vj+1) и (vj , Vj+1) - подструктура-вершина 7 j+1 вычисляется как объединение двух подструктур-ребер. Подструктуры-ребра и подструктуры-вершины в ходе вычисления могут оказаться пустыми, что, согласно сформулированным выше правилам, влечет их удаление из гиперструктуры вместе с соответствующими элементами каркаса; при этом из базисного графа удаляются ребра и вершины, не имеющие копий в ГС.

ЗАМЕЧАНИЕ 1. Последовательность операций проецирования ярусов 1, ... , j - 1 на подструктуру 7 j j -го яруса сохраняет j -пересечения, содержащиеся в 7 j (по определению j -пересечений), и предназначена для минимизации числа побочных подструктур, не являющихся j -пересечениями. Назовем указанную последовательность операций процедурой фильтрации подструктуры nj . Отметим, что при отсутствии фильтрации побочные подструктуры могут продвигаться от яруса к ярусу независимо от j -пересечений, что, как будет ясно из дальнейшего анализа, противоречит цели создания ГС.

ЗАМЕЧАНИЕ 2. Последовательность операций проецирования ярусов 1, ... , j - 1 на подструктуру 7 j , в которой предварительно конкретизирована переменная xj+3: nj (xj+3 —» b), b g {0, 1}, выделяет из nj подструктуру nj ( b ) c 77 , которая сохраняет все j -пересечения с Xj+3 = b , содержащиеся в nj . Очевидно, что эквивалентный по результату способ выделения 7 j ( b ) состоит в конкретизации одновременно двух переменных: xj+2 и xj+3 (с тем же значением b для xj+3) при формировании подструктур, приписанных ребрам, подходящим к вершине Vj от вершин (j - 1) -го яруса.

После сделанных уточнений эффективная процедура построения ГС Г сводится к следующим пунктам: