Научный журнал
Научное обозрение. Технические науки
ISSN 2500-0799
ПИ №ФС77-57440

АНАЛИЗ ЛОГИЧЕСКИХ МАТРИЦ И ГРАФОВ ОРТОГОНАЛЬНОСТИ

Попов С.В. 1
1 ООО «Научно-внедренческая фирма БП+»
Актуальность решения комбинаторных задач сегодня определяется перемещением Искусственного Интеллекта из теоретической области в практическую сферу. Известно, что одни и те же интеллектуальные задачи обладают различными способами решения в зависимости от их описания. В связи с этим в статье исследуется соотношение двух типов описания предметных областей: на языке логических матриц, и на языке графов ортогональности. В статье эта проблема исследована полностью. Невыполнимость логической матрицы сводится к исследованию совокупности максимальных пустых подграфов, образующей полное покрытие графа. Это позволяет сформулировать критерий выполнимости матрицы, который сводится к разложению исходной матрицы на две и имеет практическое значение. Граф ортогональности, который однозначно строится по логической матрице, обладает совокупностью узлов, совпадающей со столбцами матрицы, и два узла смежные, если соответствующие столбцы ортогональные. Таким образом, матрица однозначно определяет граф, но одному графу соответствует несколько матриц с разным числом переменных, среди которых могут встречаться как выполнимые, так и невыполнимые. В статье решена проблема, что происходит при варьировании матриц, определяемых одним графом ортогональности, и при расширении графа ортогональности за счет введения новых ребер. Оказывается, что в одном случае наблюдается сохранение свойства невыполнимости матриц, а в другом – выполнимости. Приведена полная система преобразований матриц, которая не нарушает свойство соответствия одному графу ортогональности. Поэтому, хотя логические матрицы позволяют более детально описывать предметные области, нежели графы, имеется возможность исследовать логические функции, сводя их к задачам на графах.
комбинаторика
логические матрицы
графы
предметные области
пустые подграфы
векторы
1. Попов С.В. Синтез предметных областей. Решение одного класса переборных задач. LAP LAMBERT Academic Publishing, 2017. 96 с.
2. Яблонский С.В. Введение в дискретную математику. М: Физматлит, 2013. 312 с.
3. Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений М.: Вильямс, 2012. 528 с.
4. Furedi, Zoltan. The number of maximal independent sets in connected graphs. Journal of Graph Theory. 2014. Vol. 19. no. 4. P. 463–470.
5. Зыков А.А. Основы теории графов. М.: Вузовская книга, 2012. 664 с.

В статье исследуется соотношение между логическими функциями, представленными матрицами, и графами ортогональности, которые строятся по логическим матрицам. Пусть M есть логическая матрица размерности [n, m], представляющая функцию в КНФ. Обратим внимание на следующие свойства матрицы M:

– каждый столбец опровергается в точности на одном интервале n-мерного единичного куба;

– несколько столбцов матрицы опровергаются на одном интервале n-мерного единичного куба, тогда и только тогда, когда все эти столбцы попарно не ортогональные.

Построим по матрице M граф ортогональности GM: его узлами являются столбцы матрицы M, и два узла смежные, если соответствующие столбцы ортогональные хотя бы по одному компоненту. Выделим в матрице M максимальную совокупность H столбцов, которая опровергается на одном интервале IH единичного куба [1, 2]. Вследствие этого все столбцы из H попарно не ортогональные. Справедливо следующее: совокупности H столбцов матрицы M в графе GM соответствует максимальный пустой подграф GH и всякому максимальному пустому подграфу GH соответствует совокупность H столбцов, одновременно опровергаемых на одном интервале единичного n-мерного куба.

Тем самым между максимальными пустыми подграфами и соответствующими опровергающими наборами для матрицы M имеется соответствие: каждый максимальный пустой подграф определяет опровергающий набор для матрицы M. Если матрица M выполнимая, то множество всех опровергающих интервалов не образует полного покрытия единичного n-мерного куба. В противном случае имеется совокупность максимальных пустых подграфов, которые определяют множество опровергающих наборов, покрывающее весь n-мерный единичный куб. Такую совокупность максимальных пустых подграфов графа ортогональности GM назовем полной. Определенные этими подграфами опровержимые интервалы покрывают весь единичный n-мерный куб.

Справедливо утверждение.

Теорема 1. Логическая матрица M опровержима тогда и только тогда, когда в графе ортогональности GM существует полная совокупность пустых подграфов.

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

В другую сторону. Пусть матрица M не выполнимая и GM – определяемый ею граф ортогональности. Покажем, что для нее существует полная система пустых подграфов. Строим не избыточную совокупность E1, …, Eq максимальных пустых подграфов, которые покрывают все узлы графа ортогональности. Каждый подграф Ej определяет множество Hj столбцов, опровержимых на интервале Ij, j = 1, 2, …, q. Допустим, что объединение ∪j=1,q Ij интервалов не покрывает всего единичного n-мерного куба, и интервал I не принадлежит объединению ∪j=1,q Ij. По построению, интервал I ортогонален каждому из интервалов Ij, j = 1, 2, …, q. Но тогда на этом интервале все столбцы матрицы M истинные, т.е. она выполнимая. Противоречие.

Теорема доказана.

Дополнение ортогональности. Рассмотрим преобразование матрицы, когда в результирующем графе ортогональности не появляются новые ребра. То есть в результате преобразования не расширяется отношение ортогональности ее столбцов.

Пусть в матрице M столбцы h1 и h2 ортогональные и в один или оба из них вводится один или два компонента, которые определяют отношение ортогональности. Рассмотрим вначале случай одного компонента (пусть это будет 1), который вводится в i-ю строку столбца h1. Следовательно, в столбце h2 в той же строке располагается 0. Допустим, что узел h1 принадлежит максимальному пустому подграфу E1 с узлами H1, определяющему опровергающий интервал I1, а h2 – максимальному пустому подграфу E2 с узлами H2, определяющему опровергающий интервал I2. Из того, что в графе ортогональности GM не появляются новые ребра, следует, что в H1 в i-й строке нет компонентов 0. Поэтому добавление 1 в столбец h1 не приводит к расширению интервала I1, т.к. в нем i-й компонент есть _ (и тогда интервал I1 сужается) или 1 (и тогда интервал I1 не меняется). Следовательно, преобразование либо превращает невыполнимую исходную матрицу в выполнимую, либо выполнимая матрица остается выполнимой.

Рассмотрим случай, когда в матрице M столбцы h1 и h2 ортогональные и в оба вводятся компоненты, которые также определяют отношение ортогональности. Пусть компонент 1 вводится в i-ю строку столбца h1, и 0 – в i-ю строку столбца h2. Допустим, что узел h1 входит в максимальный пустой подграф E1, содержащий узлы H1, и определяющий опровергающий интервал I1, а h2 – в E2, содержащий узлы H2 и определяющий опровергающий интервал I2. Из того, что новых ребер в графе ортогональности не появляется, следует, что в H1 в i-й строке нет компонентов 0, а в H2 в i-й строке нет компонентов 1. Тогда добавление 1 в столбец h1 не приводит к расширению интервала I1, т.к. в нем i-й компонент есть _ или 1, а добавление 0 в столбец h2 не приводит к расширению интервала I2, т.к. в нем i-й компонент есть _ или 0. В первом случае происходит сужение интервалов, во втором – интервалы не меняются. Следовательно, преобразование либо превращает исходную невыполнимую матрицу в выполнимую, либо выполнимая матрица остается выполнимой.

Тем самым верно утверждение.

Теорема 2. Преобразование, не расширяющее отношение ортогональности столбцов матриц, может лишь ослабить свойство невыполнимости, т.е. невыполнимая матрица может превратиться в выполнимую, но не наоборот.

Введение новой ортогональности. Рассмотрим преобразования графов ортогональности и матриц, которые влекут появление новых ребер. Вначале рассмотрим, как расширение ортогональности в матрице M отражается на соответствующем графе GM [3, 4]. Пусть максимальный пустой подграф E1 строится по множеству H1 столбцов матрицы, для которых I1 есть опровергающий интервал. (Отметим, что H1 суть метки подграфа E1). Введение новой ортогональности в матрице влечет добавление одного или нескольких ребер в граф ортогональности. Возможны несколько случаев.

Пусть в исходной матрице M в i-й строке столбцов множества H1 располагаются лишь не значащие символы, и в этой строке вводится ортогональность на пересечении со столбцами h1 и h2. В этом случае граф E1 разбивается на два пустых подграфа E11 и E12, такие, что в первый входит узел h1, а во второй – h2. Граф E11 определяет опровергающий интервал I11, а E12 – I12, ортогональные в i-м компоненте, а во всех остальных компонентах совпадающие с интервалом I1. Эти интервалы находятся на расстоянии 1 друг от друга, и их объединение равно I1. Поэтому результирующая матрица останется выполнимой (не выполнимой) в зависимости от того, была ли выполнимой (невыполнимой) исходная матрица.

Пусть в исходной матрице i-я строка столбцов множества H1 (с точностью до перестановки) имеет вид 00…0_ _ … _, и на пересечении с h-м столбцом компонент _ заменяется на 1. Допустим, что нулевых компонентов в этой строке k. В этом случае в графе ортогональности в пустом подграфе E1 появляется k ребер, инцидентных узлу h. С точностью до перестановки строка превращается в такую 00…01 _ … _. В результате граф E1 превращается в два максимальных пустых подграфа E11 и E12, в первом из них i-я строка имеет вид 00…0_..._, в другом 1_..._. Для первого подграфа E11 опровергающий интервал I11 включает интервал I1, в то время как второй E12 определяет новый опровергающий интервал, т.к. у него в i-м компоненте стоит 1. Таким образом, введение новых ортогональностей в этом случае превращает исходную матрицу в новую M1, для которой справедливо следующее: если M – не выполнимая, то M1 также не выполнимая, с другой стороны, выполнимая матрица M может превратиться в невыполнимую.

Аналогично рассматривается случай, когда в исходной матрице i-я строка столбцов множества H1 (с точностью до перестановки) имеет вид 11…1_ _ … _, и на пересечении с h-м столбцом компонент _ заменяется на 0.

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

Теперь рассмотрим, как отражается на выполнимости результирующей матрицы по сравнению с исходной добавление одного нового ребра в граф ортогональности GM. При добавлении нового ребра исходная матрица может преобразовываться как во всех трех описанных случаях. При этом в случаях 2 и 3 значение k = 1. В любом случае максимальный пустой подграф, в который это ребро вводится, раскладывается на два максимальных пустых подграфа.

Теорема 3. Преобразование матриц, которое расширяет отношение ортогональности, может лишь ослабить свойство выполнимости, т.к. матрица из выполнимой может превратиться в невыполнимую, но не наоборот.

Соотношение логических матриц и графов ортогональности. В одну сторону соотношение между графами ортогональности и логическими матрицами понятно: если M есть логическая матрица размерности [n, m], то по ней однозначно строится граф ортогональности GM c m узлами, смежность которых задается отношением ортогональности столбцов матрицы. В обратную сторону ситуация выглядит несколько иначе, т.к. одному графу может соответствовать несколько логических матриц, которые в общем случае задают не эквивалентные логические функции.

Определим преобразования матриц, которые по одному графу порождают множество логических матриц. Мы исходим из того, что всякая строка v логической матрицы, построенной по графу, определяет полный двудольный подграф Gv. Представим строку v матрицы в виде трех компонентов v0, v1 и v_, состоящих соответственно из 0, 1 и _, что будем обозначать так: v = v0 + v1 + v_. Тогда справедливы следующие преобразования, которые не меняют вида графа ортогональности, построенного по матрице.

1. Пусть v0 = v10 + v20, т.е. нулевые компоненты представляются в виде двух частей. Тогда v10 + v20 + v1 + v_ = {v10 + v2_ + v1 + v_ ∪ ∪ v1_ + v20 + v1 + v_}. Здесь v1_ (v2_) получается из v10 (v20) заменой всех нулевых компонентов на _. Преобразование слева направо соответствует преобразованию одного полного двудольного графа в два за счет разделения нулевой доли на два подмножества. Оно соответствует преобразованию одной строки матрицы в две, или, что то же самое, – введению новой переменной в логическую формулу. Преобразование справа налево, наоборот, соответствует слиянию двух полных двудольных графов в один за счет объединения нулевых долей, т.е. превращению двух строк матрицы в одну.

2. Аналогично рассматривается случай, когда v1 = v11 + v21, т.е. единичные компоненты представляются в виде объединения двух частей.

Применение этих преобразований слева направо назовем разложением матрицы, а справа налево – сворачиванием.

Очевидно такое утверждение.

Теорема 4. Пусть по графу ортогональности G с m узлами построена матрица M размерности [n, m], в которой все столбцы суть векторы, приписанные узлам графа G. Тогда эту матрицу можно превратить в матрицу M*, в которой в каждой строке в точности один нулевой и один единичный компоненты. Причем матрица M* единственная с точностью до перестановки строк и столбцов независимо от порядка применения преобразований и М* невыполнима тогда и только тогда, когда невыполнима M.

Действительно, последовательное разложение матрицы приводит к матрице, в которой каждая строка определяет ребро. Тем самым предельная матрица M* не подлежит дальнейшему разложению и определена единственным образом. Матрица M имеет полную систему пустых подграфов тогда и только тогда, когда ею обладает матрица M*.

Можно привести примеры матриц, определяемых одним графом, которые обладают разными предельными матрицами разложения. Действительно, рассмотрим граф K4, узлы которого помечены векторами: a: 00, b: 01, c: 10, d: 11. Предельное разложение соответствующей матрицы выглядит, как на рис. 1, а.

pop1.wmf

Рис. 1, а Рис. 2, а Рис. 2, б

Матрицы

Тот же граф K4 порождает матрицу как на рис. 2, а. Ее предельное разложение приведено на рис. 2, б. Из сравнения рис. 1, а, и рис. 2, б, видно, что в матрице на рис. 1, а, число строк на единицу превосходит число ребер графа K4, в то время, как в матрице на рис. 2, б, число строк совпадает с числом ребер графа K4. Это происходит потому, что в матрице на рис. 1, а, имеются две строки _ 0 1 _ и _ 1 0 _, определяющие ортогональность узлов b и c, а в матрице на рис. 2, б, имеется только одна такая строка.

Описанное разложение матрицы не меняет граф ортогональности, но добавляет одну новую переменную. Справедлива такая теорема.

Теорема 5. Пусть матрица M1 получена разложением матрицы M. Тогда из выполнимости матрицы M следует выполнимость матрицы M1, и из невыполнимости M1 следует невыполнимость M.

Доказательство вытекает из того, что выполнимость функции (x∨A)(x∨B)(`x∨C) влечет выполнимость функции (x∨A)(y∨B)(`x∨`y∨C). И наоборот, невыполнимость функции (x∨A)(y∨B)(`x∨`y∨C) влечет невыполнимость (x∨A)(x∨B)(`x∨C).

Горизонтальное разложение матриц. Разделим M на две непересекающиеся подматрицы M1 и M2 размерности соответственно [n1, m] и [n2, m], n1 + n2 = n. Если хотя бы одна из матриц M1 или M2 выполнимая, то матрица M выполнимая. Рассмотрим случаи, когда невыполнимы обе матрицы M1 и M2.

Пусть матрица M1 определяет граф ортогональности G1, а матрицы M1 – граф G2, и Emp1⊆G1 и Emp2⊆G1 суть два полных множества максимальных пустых подграфов. Тем самым получаем, что обе матрицы M1 и M2 невыполнимые. Однако невыполнимость этих подматриц не влечет невыполнимости матрицы M. Она может быть выполнимой.

Справедлива следующая теорема.

Теорема 6. 1. Матрица M выполнима тогда и только тогда, когда $E1∈Emp1$E2∈Emp2(E1∩E2 = ∅).

2. Матрица M невыполнима тогда и только тогда, когда ∀E1∈Emp1∀E2∈ ∈Emp2(E1 ∩E2 ≠ ∅).

Доказательство. 1. Пусть для двух максимальных пустых подграфов E1 и E2 выполняется соотношение E1∩E2 = ∅. Пусть опровергающие интервалы, определяемые подграфом E1 и E2, суть соответственно I1 и I2. Следовательно, все столбцы матрицы M1, которые определяются дополнением подграфа E1, выполнимые на интервале I1. А все столбцы матрицы M2, которые определяются дополнением подграфа E2, выполнимые на интервале I2. Но тогда множество столбцов матрицы M2, определяемых подграфом E1, выполнимо на интервале I2. Следовательно, вся подматрица матрицы M, выделяемая подграфом E1, выполнима на интервале I1I2. Но тогда на этом интервале выполнима и вся матрица M. Первое утверждение доказано.

2. Следует из 1 по закону контрапозиции.

Теорема доказана.

Таким образом, проблема исследования выполнимости и невыполнимости логической матрицы сводится к исследованию отношений между базисами, определяемыми частями, получаемыми в результате горизонтального расщепления матрицы [5].

Выводы

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


Библиографическая ссылка

Попов С.В. АНАЛИЗ ЛОГИЧЕСКИХ МАТРИЦ И ГРАФОВ ОРТОГОНАЛЬНОСТИ // Научное обозрение. Технические науки. – 2019. – № 3. – С. 5-9;
URL: https://science-engineering.ru/ru/article/view?id=1242 (дата обращения: 29.03.2024).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1,674