Практикум по решению логических уравнений. Наиболее полно эта проблема рассмотрена в работах П.С.Порецкого [34] и Н.П.Брусенцова [4]

Наиболее полно эта проблема рассмотрена в работах П.С.Порецкого [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 10j 1 0 j ij j 0 10i 1 0 i ii j i i01 1 0 1 i1 j i 1j0 i 0 j 10 0 0 1jj i j j 1j 0 j 1ji i 0 1 1i 0 i 1j1 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 m0011 10111 11011 11111 11100 11101 11110 1 cba d011 011 0011 1111 1100 1101 1110 1

По полученной таблице заполним карту Карно, откуда после минимизации выведем соотношения для d = f(a,b,c). Если на некотором наборе функция принимает значение как 0, так и 1, то в соответствующую клетку карты Карно вписываем символ i. Если на каком либо наборе функция не определена, то в соответствующую клетку карты Карно вносим значение j. Здесь и далее апостроф означает отрицание аргумента или функции. Применение карты Карно не имеет принципиального значения: просто автор считает карты Карно наиболее эффективным инструментом для минимизации булевых функций.

bac \ 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 отношений:

1. Птицы певчие - крупные или обладающие качеством Y.
2. Птицы, не имеющие качества Y - или не крупные, или не имеют качества Х.
3. Птицы певчие в соединении с крупными объединяют всех птиц с качеством Х.
4. Каждая не-крупная птица есть или певчая, или обладающая качеством Х.
5. Между птиц с качеством Х совсем нет таких птиц с качеством Y, которые не будучи певчими, были бы крупные.

Определить, были ли птицы качества Х певчие или нет. Узнать то же в отношении птиц качества 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'=12. g'+x'+у=13. s+g+x'=14. s+g+x=11. x'+у'+s+g'=1

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

Кстати, используя силлогистические функторы Аху и Еху (см. главу 3), можно получить эти соотношения сразу, не прибегая к рекурсии и эквивалентности. Исходя из вышесказанного можно утверждать, что аналитическое представление силлогистических функторов Axy, Exy было впервые в мире дано русским логиком Порецким П.С. Правда, ни Порецкий, ни мировая логика не заметили этого научного достижения, как не увидели и того,что позже к аналогичному выводу пришел и Л.Кэрролл[12]. Логика до сих пор прозябает в невежестве.

1. As(g+y) = (s(g+y)')' = s'+g+y = 12. Ay'(g'+x') = (y'(g'+x')')' = y+g'+x' = 13. Ax(s+g) = (x(s+g)')' = x'+s+g = 14. Ag'(s+x) = (g'(s+x)')' = g+s+x = 15. Ex(ys'g) = (x(ys'g))' = x'+y'+s+g' = 1

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

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

1. g'у's=02. gxу'=03. g's'x=04. g's'x'=05. gs'xу=0

Полный логический нуль системы равен дизъюнкции всех левых частей системы логических уравнений. Проведём решение задачи Порецкого с использованием карты Карно, а потом сопоставим результаты. Заполним карту Карно нулями в соответствии с нулевыми термами системы, а в оставшиеся клетки впишем единицы. Тогда полная логическая единица всей задачи после минимизации примет вид:

m=sу+gx' gs\xy 00 01 11 1000 0 0 0 001 0 1 1 011 1 1 1 010 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. Алгоритм "Селигер"

1. Привести систему уравнений к нулевому виду (исходная система).
2. Заполнить карту Карно нулями в соответствии с термами левых частей исходной системы уравнений, а в оставшиеся клетки вписать единицы. Эти единичные термы представляют собой СДНФ полной единицы системы.
3. Произвести минимизацию совокупности единичных термов. Полученное соотношение представляет МДНФ уравнения полной единицы системы.
4. Построить сокращённую (только для единичных термов) таблицу истинности уравнения полной единицы и выписать из неё все значения входных и выходных переменных в виде частных таблиц истинности для искомых функций.
5. Произвести минимизацию искомых функций.

Алгоритм "Селигер" предполагает не только графическую, но и аналитическую минимизацию методом обобщённых кодов [4]. Для систем уравнений с числом аргументов не более 10 графический метод эффективнее. Минимизация в трёхзначной и комплементарной логиках для двоичных аргументов несущественно отличается от минимизации в двузначной: нужно лишь проводить раздельное склеивание по i, j, 1 или 0.

Пример 3

Рассмотрим 2-ю задачу Порецкого.

Относительно белья в комоде известны 2 положения:

1. часть его состояла из крупных предметов, всё же остальное было тонким, причём часть этого последнего была поношена, прочая часть дёшево стоила;
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, что совпадает с результатом Порецкого.

Заключение

1. Простота метода, заложенного в алгоритме "Селигер", позволяет решать логические уравнения от большого числа переменных.
2. Минимизация функций в 3-значной и комплементарной логиках для двоичных аргументов несущественно отличается от традиционных методов двузначной логики.
3. Парные термы для равносильных преобразований определяются набором термов, полученных на основе применения формулы эквивалентности к исходному логическому уравнению.
4. Применение метода при выводе обратных логических функций показало, что однозначное решение для двоичных аргументов может быть получено лишь в комплементарной логике.
5. Впервые получены все 16 обратных логических функций для двух аргументов.
6. Комплементарная логика при аппаратной реализации позволяет значительно упростить решение проблемы самодиагностирования вычислительной техники: например появление j на любом выходе может свидетельствовать о сбое или отказе.

Дата добавления: 2015-05-08