Практикум по решению логических уравнений
Наиболее полно эта проблема рассмотрена в работах П.С.Порецкого [34] и Н.П.Брусенцова [4].
Предлагается более простой и эффективный метод решения логических уравнений[17], основанный на применении таблиц истинности и трёхзначной или четырёхзначной логики. Трёхзначную логику представим следующими базисными операциями : инверсией, конъюнкцией и дизъюнкцией [4].
Таблица базисных функций 3-значной логики
Аргументы | Функции --------------------- XY | X' | X&Y | X+Y ----|-----|-----|---- 00 | 1 | 0 | 0 0i | 1 | 0 | i 01 | 1 | 0 | 1 i0 | i | 0 | i ii | i | i | i i1 | i | i | 1 10 | 0 | 0 | 1 1i | 0 | i | 1 11 | 0 | 1 | 1
Базисные функции определяются следующии соотношениями :
X Y = min(X,Y) X+Y = max(X,Y)
Автором впервые предлагается четырехзначная логика.Она полностью соответствует общеразговорной,или бытовой логике.Вышеназванная логика представлена базисными функциями. Значения этой логики имеют следующий смысл : 0 - нет, j - не может быть никогда, i- может быть, 1 - да.
Таблица базисных функций 4-значной комплементарной логики
XY X' X&Y X+Y XY X' X&Y X+Y ----------------------------------------------------------- 00 1 0 0 i0 j 0 1 0j 1 0 j ij j 0 1 0i 1 0 i ii j i i 01 1 0 1 i1 j i 1 j0 i 0 j 10 0 0 1 jj i j j 1j 0 j 1 ji i 0 1 1i 0 i 1 j1 i j 1 11 0 1 1
Следует обратить внимание на комплементарность(взаимодополняемость,взаимоинверсность) значений переменных : 0+1=1, i+j=1, 0 1=0, i j=0. В связи с этим вполне естественно назвать такую логику комплементарной. Для приведённых базисных функций комплементарной логики как и для 3-значной логики также справедлив закон Де Моргана.
При решении системы логических уравнений вначале определяется так называемая полная единица задачи (системы), а потом отыскивается решение уравнения относительно одной из переменных. Под решением здесь и далее понимается преобразование исходного уранения к явному виду относительно одной из переменных. Поскольку построение полной единицы системы не вызывает затруднений, рассмотрим решение логического уравнения с помощью таблиц истинности, считая полную единицу (m) известной.
Пример 1
Дано : m = ab + cd = 1 Найти : d = f(a,b,c)
Решение
На основании исходного логического уравнения полной единицы строим таблицу истинности для разрешённых наборов, т.е. тех наборов, на которых исходное уравнение имеет решение. Перенеся столбцы a,b,c из исходной таблицы в качестве значений аргументов, а столбец d - в качестве значений искомой функции, получим таблицу истинности для d = f(a,b,c).
dcba m 0011 1 0111 1 1011 1 1111 1 1100 1 1101 1 1110 1 cba d 011 0 11 0 011 1 111 1 100 1 101 1 110 1
По полученной таблице заполним карту Карно, откуда после минимизации выведем соотношения для d = f(a,b,c). Если на некотором наборе функция принимает значение как 0, так и 1, то в соответствующую клетку карты Карно вписываем символ i. Если на каком либо наборе функция не определена, то в соответствующую клетку карты Карно вносим значение j. Здесь и далее апостроф означает отрицание аргумента или функции. Применение карты Карно не имеет принципиального значения : просто автор считает карты Карно наиболее эффективным инструментом для минимизации булевых функций.
ba
c \ 00 01 11 10
j j i j
1 1 i 1
Клетки карты Карно с координатами 011 и 111 заполнены значением i, т.к. на этих наборах(индивидах,конституентах) d принимает значения как 0, так и 1. Наборы 000, 001 и 010 в таблице отсутствуют, поскольку при таких значениях аргументов исходное уравнение не имеет решения, поэтому соответствующие карты Карно заполнены символом j.
Для трёхзначной логики в этих клетках помещается прочерк [13], т.е. символ недоопределённости. Доопределение минимизируемой функции единицами позволяет получить компактную формулу.
Для комплементарной логики имеем:
d = cb' + ca' + iba + j(c'b' + c'a')
Для трёхзначной логики это уравнение выгдядит проще:
d = b' + a' + iba
В связи с тем, что при решении логических уравнений приходится зачастую проводить минимизацию булевых функций от большого числа переменных, полезно ознакомиться с соответствующими алгоритмами, изложенными в [13,14] и в диссертации автора[15].
Пример 2
Рассмотрим 1-ю задачу Порецкого[34]. Между птицами данного зоосада существует 5 отношений:
Определить, были ли птицы качества Х певчие или нет. Узнать то же в отношении птиц качества Y.Найти, были ли среди качества Х птицы качества Y и наоборот.
Решение
Пусть Х - птицы качества Х.
Y - птицы качества Y.
S - певчие птицы.
G - крупные птицы.
Тогда условие задачи будет представлено следующими рекурсивными уравнениями [32] :
1. s= (g+ у)s; 2. у'= (g'+x')у'; 3. s+g+x'=1; 4. g'=(s+x)g'; 5. xуs'g=0.
Эти уравнения Порецкий через эквивалентность приводит к единичной форме:
1. g+у+s'=1 2. g'+x'+у=1 3. s+g+x'=1 4. s+g+x=1 1. x'+у'+s+g'=1
Нетрудно заметить, что система уравнений Порецкого представляет из себя сорит, содержащий посылки общего характера. Посылки частно-утвердительного характера метод Порецкого обрабатывать не может.
Кстати, используя силлогистические функторы Аху и Еху (см. главу 3), можно получить эти соотношения сразу, не прибегая к рекурсии и эквивалентности. Исходя из вышесказанного можно утверждать, что аналитическое представление силлогистических функторов Axy, Exy было впервые в мире дано русским логиком Порецким П.С. Правда, ни Порецкий, ни мировая логика не заметили этого научного достижения, как не увидели и того,что позже к аналогичному выводу пришел и Л.Кэрролл[12]. Логика до сих пор прозябает в невежестве.
1. As(g+y) = (s(g+y)')' = s'+g+y = 1 2. Ay'(g'+x') = (y'(g'+x')')' = y+g'+x' = 1 3. Ax(s+g) = (x(s+g)')' = x'+s+g = 1 4. Ag'(s+x) = (g'(s+x)')' = g+s+x = 1 5. Ex(ys'g) = (x(ys'g))' = x'+y'+s+g' = 1
Поэтому, видимо, целесообразно изучать решение логических уравнений после освоения силлогистики.
Полная логическая единица всей задачи определится как конъюнкция всех левых частей системы логических уравнений. Эту рутинную операцию можно заменить на менее утомительную процедуру построения дизъюнкции нулей. Получим систему:
1. g'у's=0 2. gxу'=0 3. g's'x=0 4. g's'x'=0 5. gs'xу=0
Полный логический нуль системы равен дизъюнкции всех левых частей системы логических уравнений. Проведём решение задачи Порецкого с использованием карты Карно, а потом сопоставим результаты. Заполним карту Карно нулями в соответствии с нулевыми термами системы, а в оставшиеся клетки впишем единицы. Тогда полная логическая единица всей задачи после минимизации примет вид:
m=sу+gx' gs\xy 00 01 11 10 00 0 0 0 0 01 0 1 1 0 11 1 1 1 0 10 1 1 0 0
Выпишем из карты Карно все единичные термы в виде таблицы истинности. По полученной таблице построим таблицы для х=f1(g, s),y=f2(g,s) и у=f3(х). Если на каком-либо наборе функция принимает значение как 0, так и 1, то в соответствующую клетку карты Карно вписываем 1. Если какой-нибудь набор отсутствует, то для этого набора в карту Карно вносим значение j при комплементарной логике или произвольное ( по аналогии с двузначной логикой)- при трёхзначной.
После минимизации получим для комплементарной логики системы уравнений:
x = is + jg's' у = g's + ig + jg's' у = x + ix' = (x + ix) + ix' = x + i
Трёхзначной логике соответствует система уравнений:
x = is у = g' + ig + g' + i у = x + ix' = x + 1
Результаты, полученные Порецким:
x = xs у = gу + g's у = у + x
Сравнивая системы уравнений, можно предположить, что Порецкий фактически использовал трёхзначную логику для решения логических задач: рекурсивное вхождение функции соответствует комплементарному значению i . Причём он сделал это впервые в мире. Незначительные расхождения результатов связаны с тем, что Порецкий непроизвольно доопределил у=f(g,s)нулём на наборе g's', что менее логично с точки зрения минимизации. Результаты Порецкого имеют право на существование, однако более строгим решением является система на основе комплементарной логики, поскольку она фиксирует и те ситуации, которые не могут быть никогда. Например, в сложной системе управления своевременное обнаружение таких состояний может предотвратить аварию или отказ. Поэтому можно надеяться, что вычислительная техника (да и не только она, но и юриспруденция тоже) будет строиться на трёхзначной [6] или комплементарной логике. Кстати, первая в мире троичная ЭВМ "Сетунь-70" была создана в России Брусенцовым Н.П. (МГУ). Что касается 4-значной ЭВМ, то аппаратная реализация комплементарной логики на современной двоичной элементной базе весьма несложна.
Основываясь на примерах 1 и 2, составим алгоритм решения системы логических уравнений.
1.2. Алгоритм "Селигер"
Алгоритм "Селигер" предполагает не только графическую, но и аналитическую минимизацию методом обобщённых кодов [4]. Для систем уравнений с числом аргументов не более 10 графический метод эффективнее. Минимизация в трёхзначной и комплементарной логиках для двоичных аргументов несущественно отличается от минимизации в двузначной : нужно лишь проводить раздельное склеивание по i, j, 1 или 0.
Пример 3
Рассмотрим 2-ю задачу Порецкого.
Относительно белья в комоде известны 2 положения:
Узнать, какое бельё было поношено: крупное или мелкое.
Решение
Пусть а - тонкое, b - крупное, с - дорогое, d - новое бельё. Тогда имеем следующую систему уравнний:
1. b + a(d' + c') = 1 2. (a' + d'c) = ab'c' + b(d + ac')
В соответствии с алгоритмом "Селигер" получим:
1. a'b' + b'cd = 0 2. a'b' + a'd' + cd' + 0
Нулевые термы системы уравнений занесём в карту Карно, откуда получим функцию полной единицы. По полученному соотношению строим сокращённую таблицу истинности и выписываем из неё значения b и d в виде таблицы, из которой получаем логическую функцию. Из этой функции следует, что d не зависит от b, что совпадает с результатом Порецкого.
Заключение