БИОНИКА ИНТЕЛЛЕКТА. 2009. № 1 (70). С. 64-67 ХНУРЭ УДК 519.62 Ж РЕШЕНИЕ СИСТЕМ КОНЪКЖТИВНЫХ И СМЕШАНЫХ СИСТЕМ И ИХ ГРАФОВАЯ ИНТЕРПРЕТАЦИЯ Л. Г. Ситник INTELLIGENCE Сумы, Сумской областной институт последипломного педагогического образования В статье рассматриваются алгебраические методы решения систем логических уравнений конъюнктивного и смешанного типа, основанные на теории логических определителей. Получен общий вил решений таких систем и предложена интерпретация решений с помощью языка теории графов. КОНЪЮНКТИВНАЯ СИСТЕМА. ДИЗЪЮНКТИВНО-КОНЪЮНКТИВНАЯ СИСТЕМА. ДЕДИЗЪЮНКПИЯ. ИНТЕРПРЕТИРУЮЩИЙ ГРАФ Введение Данная статья является продолжением работы 111 на случай конъюнктивных и смешанных систем. Для них с использованием аппарата логических определи­ телей построенные частные и общие решения, пока­ зана принципиальная разрешимость таких систем. Используются интерпретации на языке теории графов. 1. Система конъюнктивных уравнений В графовой интерпретации дизъюнктивной систе­ мы (см. формулу (3) из [1]) каждой переменной сопос­ тавлялась вершина, наделенная функцией дизъюнкции от значений верш ин-соседей, связанных с ней единич­ ными заходящими дугами. Пусть теперь каждая верши­ на интерпретирующего графа G будет наделена функ­ цией конъюнкции, то есть будет принимать единичное значение, если все ее соседи уже наделены единичны­ ми значениями. Систему уравнений, сопоставляемую такому графу, будем называть конъюнктивной. Будем пользоваться записью булевой степени х", означающей хй=Р’* = (\ (1) [X,tf = 1 Тогда каждое уравнение конъюнктивной системы можно представить в виде: ху = xfn xj2.. .x"ft , і = 1, я, (2) где знаки конъюнкции опушены [2]. Систему (2) будем условно изображать в матрич­ ной форме как Х = Х'1И. (3) где А — матрица показателей степеней переменных из X. объединяемых в (2) знаками конъюнкции. Решение системы (2), как и дизъюнктивной систе­ мы (см. формулу (3) из [I]), неоднозначно. Поэтому среди прочих будем выделять 0-решения и 1 - решения, имеющие тот же смысл, что и при решении дизъюнк­ тивной системы. Найдем их. Записи (1) соответствует эквивалентная форма (xvfl),a поэтому, перейдя от (2) к двойственной сис­ теме относительно X, , с помощью теоремы 1 из 11 I получим, что справедлива следующая теорема. Теорема 1. Система конъюнктивных уравнений (2) имеет единственное 1-решение Xі: , п |л(»| ___ ‘ (4) /=1 На графе 6'определитель интерпретируется объединением всех путей, исходящих из вершин X. и заканчивающихся вершиной х. Следовательно, значе­ нием переменной х- в 1-решении системы (2) будет конъюнкция всех А, из которых существует хотя бы один путь в вершину хр то есть справедливо следую­ щее соотношение: *’ = П сД/ = 1,л, (5) йуєД- где В. - множество всех истоков, из которых существу­ ют пути в х{ на графе G\ В - множество всех истоков, а х,- = 1 , если Bt■ = 0. Для интерпретации 1 -решения на графе G в терми­ нах его окраски удобно использовать нс конъюнктив­ ный принцип, определяемый (5), а «дизъюнктивный», приняв истоки с нулевой краской за определяющие. Тогда в нулевой цвет должны перекраситься все тс вер­ шины, у которых хотя бы одна соседняя уже окраше­ на в нулевой цвет. Пол однородной конъюнктивной системой (2), В которой В отличие ОТ ДИЗЪЮНКТИВНОЙ bj = 1,у = l,w . Справедлива также следующая теорема. Теорема 2. Любое частное решение системы (2) может быть представлено покомпонентной конъюнк­ цией ее 1-решения и одного из решений, соответству­ ющей ей однородной системы. Любое решение однородной системы (2) может быть найдено С ПОМОЩЬЮ бу тем же путем, что и реше­ ние однородной дизъюнктивной системы (см. теоре­ му 2 из 11 ]), с той лишь разницей, что вершинам с пет­ лями в графе Ge произвольным образом могут присва­ иваться нс единичные, а нулевые значения. Множе­ ство всех частных решений системы (2), найденных указанным путем, и составляет се общее решение. 64 РЕШЕНИЕ СИСТЕМ КОНЪЮКТИВНЫХ И СМЕШАНЫХ СИСТЕМ И ИХ ГРАФОВАЯ ИНТЕРПРЕТАЦИЯ Любое частное решение однородной системы (2) может быть найдено через его базисные решения, по­ рождаемые вектором «автонулей» с компонентами: *;= = (6) Тогда любое частное решение однородной системы (20) суть покомпонентная конъюнкция любых наборов следующих базисных решений х/ с компонентами: 4’-|4’|К>1.'-й Покомпонентная конъюнкция всех базисных ре­ шений является О-решением однородной системы (2). Для однородной системы конъюнктивных уравне­ ний справедлива следующая теорема. Теорема 3. Однородная система конъюнктивных уравнений, соответствующая системе (2), имеет един­ ственное 0-решение Xq : п ( п ___ 4 = П ,'=и /=1\Л=1 ) Если граф G ацикличен, то в нем не могут возни­ кать «автонули», и, следовательно, имеют место: Ciedcmeue 1. Интерпретирующий систему (2) граф (7 ацикличен, если и только если 0-решение, соответ­ ствующее однородной системе, представлено только единичными компонентами. Ciedcmeue 2. Если интерпретирующий систему (2) граф G ацикличен, то она имеет единственное реше­ ние, совпадающее с 1-решением (О-рсшенисм). Ciedcmeue 3. Интерпретирующий систему (2) граф G ацикличен, если и только если все компоненты век­ тора автонулей единичны: |Я°| =!,/ = !, п. 2. Дизъюнктивно-конъюнктивная система уравнений Рассмотрим теперь случай системы, которая может включать в себя как дизъюнктивные уравнения, так и конъюнктивные: х,- = aflxt v ai2x2 v... v ainxn v Д,/ = 1,/, Xj = Х,7 X2J- ...xn)nbfj = / + 1,/r. Назовем такую систему уравнений дизъюнктивно­ конъюнктивной Соответствующий интерпретирующий граф G будет содержать дизъюнктивные вершины х,-,/ = 1,/ и конъ­ юнктивные вершины XjJ = l = 1,/?. Такой граф можно представить как результат объединения нескатьких гра­ фов в которых каждая дизъюнктивная вершина имеет только одну заходящую дуту. Каждый из таких графов можно трактовать как сугубо конъюнктивный, полагая, что дизъюнктивная вершина с одной заходя­ щей дугой эквивалентна такой же конъюнктивной вер­ шине. Будем называть графы = конъюнк­ тивными составляющими графа (7, а процедуру разло­ жения графа G на конъюнктивные составляющие бу­ дем называть его дедизъюнкпией. Соответственное представление исходной системы (7) в виде г систем конъюнктивных уравнений также будем называть ее де­ дизъюнкцией |2]. Эти системы будем называть конъ­ юнктивными составляющими дедизъюнкции системы (7). Имеет место следующая лемма. Лемма. Для всякого решения системы (7) найдется конъюнктивная составляющая ее дедизъюнкпия, до­ пускающая тоже решение. Доказательство этой леммы строится на той же ос­ нове, что в графе G можно у дизъюнктивных вершин, принявших нулевое значение, оставить любую одну за­ ходящую дугу, а у принявших единичное значение ос­ тавить только одну заходящую дугу, связанную с любой из вершин, также принявших единичные значения. Используя дедизъюнкцию системы (7) можно по­ казать, что справедлива следующая теорема. Теорема 4. 0-решение (1-решение) системы (7) есть покомпонентная дизъюнкция 0-решений (1-решений) конъюнктивных составляющих ее дедизъюнкций. Доказательство этой теоремы основывается на том, что ни 0-рсшсния. ни 1-решения конъюнктивных со­ ставляющих не могут иметь больше единичных ком­ понент. чем исходная система, и эти компоненты нс могут быть новыми. А то, что 0-рсшсние и 1-решение исходной системы совпадает с каким-либо из реше­ ний конъюнктивной составляющей, определяется сформулированной выше леммой. Ciedcmeue 4. Если интерпретирующий систему (7) граф С?ацикличен, то он имеет единственное решение, совпадающее с 0-решением (1-решением). При проверке графа G на ацикличность нет необхо­ димости учитывать свойства его вершин (дизъюнктив­ ное ь. конъюнктивы ость). Достаточно лишь исследо­ вать матрицу Л. используя следствие 3 или следствие 4, эквивалентные в силу их двойственности. Пример 1. Для построения графов G^ можно вос­ пользоваться следующей процедурой. Пусть вместо матрицы Л система представлена D- матрицей, отобра­ жающей дизъюнктивные связи, и А”-матрицей, отобра­ жающей конъюнктивные связи в графе G. Например : р = (° і і °U=P 1 ° °) ІД 0 0 1/ [о 0 1 1/ Выполним лексикографическую дизъюнкцию D- матрицы: О 1 1 р) 1 0 (р р) 0 1 0А і о о ij и о о oj и о о ог (0 1 О 0W0 О 1 о V V to 0 О ЩО о 0 1 Тогда исходящий граф представим следующим на­ бором конъюнктивных графов (см. рис.1) с матрица­ ми смежностей: 65 Л. Г. Ситник <0 1 0 (П <0 0 1 0^ G™ = 10 0 0 ,(?<** = 10 0 0 1 110 0 110 0 <0 0 1 1> <0 0 11; '0 1 0 0> 0 0 1 0л ' = 0 0 0 1 ,G'k> = 0 0 0 1 3 110 0 110 0 0 0 1 1 0 0 11 На рис. 2а представлен такой граф, причем точка­ ми изображены дизъюнктивные вершины, а кружоч­ ками - конъюнктивные. После дедизъюнкции этого графа получим две его конъюнктивные компоненты G’}A ) и б’*** (рис. 26 и 2в), потенциально содержащие различные варианты решений задач на СС. Конъюнктивные компоненты преобразуем в интер­ претирующие графы и следующим образом. Рис. 1. Набор конъюнктивных графов Теперь можно убедиться, что соответствующие этим графам системы уравнений имеют только нуле­ вые решения при любых В, и, следовательно. 0-рсше- ние в этом примере при любых В также нулевое. Пример 2. (использование решения как формулы). В системах с искусственным интеллектом предмет­ ная область зачастую представляется семантической сетью в виде И-ИЛ И-графа, в котором вершинам типа ИЛИ сопоставляются понятия, а вершинам типа И - отношения (модули), отображающие одни понятия и другие. Если одно и то же понятие может быть сформу­ лировано различными модулями, то в соответствующую ему вершину типа ИЛИ будут заходить несколько дуг. В СС решаются различные задачи, в том числе : - выводимо (вычислимо) ли требуемое понятие по заданному множеству исходных понятий; - какие из модулей принимают участие в конкрет­ ном выводе. Для этой цели СС сопоставим граф, в котором дизъ­ юнктивные вершины отмечаются именами понятий, а конъюнктивные — именами отношений. Рис.2. Структура семантической сети: а — граф семантической сети; б, в — конъюнктивные компоненты графа Рис.З. Интерпретирующие графы: а — связь m} -> /и4; б — связь m2 -> /??4 Имена отношений приписываются дугам, заходя­ щим в конъюнктивные вершины, дизъюнктивные вер­ шины исключаются, их именами помечаются предше­ ствующие дизъюнктивным вершинам (рис.За и 36). При таком построении некоторые из конъюнктивных вершин будут помечены одними и теми же именами понятий. Поэтому матрицы смежности для получен­ ных графов будем записывать отн(кительно уникаль­ ных индексов, сопоставленных вершинам модулей: < 0 0 0 0^ <0 0 0 0 O' 0 0 0 0 0 0 0 0 0 0 4 = 0 0 0 0 0 ,Л2 — 0 0 0 0 0 . /w4 0 m4 0 0 0 m4 /w4 0 0 < 0 0 0 <0 0 m5 0 0; где дуги представляются приписанными им именам мо­ дулей, причем значение w. = 1,/= 1,5. Пусть названные выше задачи решаются относительно понятий и х4 , или, что то же, относительно т4 и /и5 Ответы на постав­ ленные вопросы можно получить, найдя 0-решения для графов и G2. Но так как G{ содержит цикл, включаю­ щий w4, то он не может быть использован для вывода т4. Остается использовать G,. для которого получим: х3 = (mfy)° (т2^ р4 [m3b3 )'”4 (w5Z>4) = (m2/>2m3£j р , х4 = )° )° f54 (w5/>4 f5 = (m3b3m5b4f54 . Таким образом, х3 вычислимо, если определены Ь2 и Ь3 , а участвуют в вычислениях модули /я2, m3 и m4. Для вычисления х4 достаточно определить Ь3 и Ь4, а в вычислениях участвуют модули ш3 и т5. Решения систем логических уравнений, рассмот­ ренные в данной работе и статье 111, были реапизова- 66 РЕШЕНИЕ СИСТЕМ КОНЪЮКТИВНЫХ И СМЕШАНЫХ СИСТЕМ И ИХ ГРАФОВАЯ ИНТЕРПРЕТАЦИЯ ны программно. Если проанализировать соответству­ ющие формулы решений, то нс сложно заметить, что для их программной реализации необходимо вычис­ лить булев определитель. Решение данной задачи мо­ жет быть реализовано по следующему алгоритму. Шаг 1. Ищется элемент определителя /1(7,/) равный 1 и запоминается номер его строки и столбца. Шаг 2. Осуществляется поиск I в столбце J+1 и во всех строках, кроме /-той. Если единичный элемент отсутствует, то определитель равен нулю, в противном случае шаг 2 повторяется до тех пор, пока не будет най­ дена последовательность из п единиц, каждая из кото­ рых стоит в отдельном столбце и отдельной строке. Это означает, что булев определитель равен 1. Выводы В статье предложен метод решения конъюнктив­ ных и смешанных систем логических уравнений мат­ ричными методами, позволивший применять извест­ ные аналитические методы решения линейной алгеб­ ры (аналог метода Крамера). Разработан общий алго­ ритм нахождения решения систем логических уравне­ ний и его графоаналитическая интерпретация. Для частных случаев решения систем логических уравнений предложены понятия: «0-рсшснис» и «1- ре­ шение» этих систем, позволяющие представить в ком­ пактном виде структуру общего решения. Список литературы: 1. Ситник Л, Г.. Шабанов-Кушнарен­ ко С. Ю. Решение систем дизъюнктивных уравнений мето­ дом логических определителей// Бионика интеллекта: науч.- техн. журнал.-2008.-№1(68). 2. Чистов В. П. Аналитичес­ кие решения логических уравнений // Техническая кибер­ нетика (Изв. АН СССР).-1994.-№ 2.-С. 219-224. Поступила в редколлегию 18.02.2009 УДК 519.62 Розв’язання систем кон'юнктнвних і змішаних систем та їх графова інтерпретація / Сітнік Л. Г. // Біоніка інтелекту: наук.- тсхн. журнал.-2009.-№ 1(70).-С. 64-67. У статті розглядається питання про розв'язання систем логічних рівнянь за допомогою логічних визначників. Знай­ дено вигляд розв’язків даних систем і запропонована інтер­ претація з використанням теорії графів. Іл.: 3. Бібліогр.: 2 найм. UDK 519.62 Decision of the systems of the conjunct and mixed systems and their graphs interpretation / Silnik L. G. // Bionics of Intelligence: Sci. Mag. -2009. -№l(70).-P. 64-67. In the article a question is about the decision of the systems of logical equations through logical determinants. The general view of decisions of these systems is found and interpretation with the use of theory of graphs offered. Fig.3.: Ref.: 2 items. 67