§ 5.5. Булевы уравнения

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

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

и, следовательно, должно быть таким, чтобы выполнялось равенство

откуда

где вместо X можно написать как 0, так и 1.

Таким образом, рассматриваемое уравнение имеет четыре решения, соответствующие изображающим числам

Аналогично можно найти решение уравнения в виде импликации, например

Так как

то

Таким образом, имеется решений уравнения (5.7):

Заметим, что уравнение в форме импликации всегда можно записать как соотношение эквивалентности, например вместо (5.7) можно было бы написать

или после упрощения

Существуют также уравнения, которые вообще не имеют решений, например

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

Когда было много разговоров о существовании «летающих тарелок» в связи с утверждениями некоторых лиц о том, что ночью ими наблюдались странные небесные тела, был произведен опрос населения двух близлежащих к месту предполагаемого появления этих тел населенных пунктов.

Систематизация результатов опроса жителей первого населенного пункта показала следующее:

а) в небе появились сгустки слабо светящейся ионизированной пыли ;

б) среди атмосферных облаков появилось одиночное светлое дискообразное тело радиусом приблизительно и больше не было никаких других тел (У);

в) далеко в небе показалась группа движущихся сигарообразных тел и движение этих тел сопровождалось слабыми мерцающими разрядами атмосферного электричества

Ответы жителей второго населенного пункта можно было объединить в такие группы:

а) не было ни светящейся ионизированной пыли ни большого светлого дискообразного тела (X), ни сигарообразных тел (У);

б) не видели ни атмосферных облаков ни светлого дискообразного тела (X);

в) наблюдались слабые разряды атмосферного электричества

г) среди облаков были видны сгустки слабо светящейся ионизированной пыли

На основании этих данных требовалось определить, следует ли принимать всерьез заявления некоторых лиц о наблюдавшихся ими странных небесных телах или же представления о телах могли быть вызваны комбинированными действиями атмосферных явлений

Используя введенные обозначения, результаты опроса представим в виде следующего булева уравнения:

Решение вопроса о существовании тел сводится к определению возможности разрешить уравнение (5.8) относительно неизвестных и выразить их как функции от элементов Если решение существует и, кроме того,

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

Вычисление и относительно базиса удобно проводить при помощи следующей рабочей таблицы [14]:

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

Рекомендуется следующий порядок работы при вычислении относительно базиса Возьмем первую пару значений при т. е. , которые соответствуют нулевому столбцу базиса Паре значений отвечают колонка о в наборе изображающих чисел элементов и У для левой части уравнения (5.8) и колонка в наборе изображающих чисел для правой части этого уравнения. Колонку умножаем на нулевую колонку в наборе изображающих чисел коэффициентов для левой части уравнения и результат суммируем по правилу логического сложения:

Аналогично поступим с колонкой и нулевой колонкой в наборе для правой части уравнения:

Так как результаты (5.10) и (5.11) не совпадают, то, следовательно, пара значений в разрядах изображающих чисел вычисленных относительно базиса не удовлетворяет (5.8) и потому должна быть отброшена.

Далее проверяется пара при в разрядах с номером по отношению к Как и раньше, необходимо сравнить логическую сумму произведения колонки на колонку т. е.

с аналогичным результатом для колонок

— колонка с номером в наборе колонка с номером в наборе . Аналогично, колонка с номером в наборе а — колонка с номером в наборе

Поскольку количества (5.12) и (5.13) совпадают, можем записать в нулевые разряды и по отношению к значения как показано в таблице результатов:

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

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

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

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

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

Изложенный метод может быть применен и при решении системы уравнений в форме эквивалентности с тем, однако, усложнением, что проверяемая пара значений должна одновременно удовлетворять всем уравнениям системы.

Процедуру отбора пар значений удовлетворяющих, например, уравнению (5.8), можно значительно упростить, если ввести в рассмотрение операции над булевыми матрицами. Прямоугольная матрица называется булевой, если элементы ее — числа 0 и 1. Произведение булевых матриц

обозначаемое знаком определяется по правилам обыкновенного матричного умножения:

с той только разницей, что операция суммирования произведений элементов строк и столбцов (5.15) заменяется логическим сложением, например

Соотношение импликации, обозначаемое справедливо для двух булевых матриц: если нет таких, что например

Транспонированной матрицей по отношению к называется матрица

получаемая из при перемене местами строк и столбцов.

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

Аналогично для правой части уравнения (5.8) находим

Сравнение матриц показывает, что в строках совпадают элементы с индексами т. е. и, следовательно, в разряд таблицы результатов должны быть внесены значения (.

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

Для системы из уравнений в форме эквивалентности, которые будем предполагать перенумерованными при помощи индекса решения находятся из условия совпадения элементов одновременно во всех матрицах вычисленных таким же образом, как и матрицы (5.16) и (5.17). Если при каком-либо не существует таких что

то система уравнений не имеет решения.

Для уравнений в форме импликации не нужно требовать совпадения элементов матриц и Для существования решения достаточно только, чтобы единице слева обязательно соответствовала единица справа.

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

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

Очевидно, что если бы удалось выразить через причем то ответ должен бы быть положительным.

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

Составим рабочую таблицу:

Для уравнения (1)

Для уравнения (2)

Для уравнения (3)

Сравнивая построчно матрицы получаем для нулевой строки:

и, следовательно, только удовлетворяет уравнениям в нулевых разрядах Так как

то только можно записать в первые разряды Далее,

откуда следует, что общее значение для трех уравнений есть и потому при следует взять Аналогично, из того, что

заключаем, что разряды должны быть равны

Таким образом,

Решение показывает, что наблюдавшиеся самолеты типа X могли в действительности быть самолетами типа А, а самолеты типа У могли быть либо типа А, либо типа В, но не

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

Второму варианту данных наблюдения за самолетами отвечают уравнения:

Найдем возможные решения уравнения (2). По отношению к соответственно будем иметь:

и, следовательно,

откуда

Сопоставляя эти результаты с решениями для уравнений (1) и (3), замечаем, что в первые разряды и нельзя вписать ни одну из

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