Глава десятая. Логические уравнения и обратные функции. 10.1. Решение уравнений и 4-значная комплементарная логика.
Под решением логического уравнения понимается преобразование исходного уравнения к явному виду относительно одной из переменных. Такую формулировку предложил Вороничев Пётр Петрович, научный сотрудник Института Проблем Управления, когда рецензировал первую статью автора по решению логических уравнений. Сам автор до такого чёткого определения поставленной задачи не додумался бы. Даже когда эта формулировка прозвучала, автор не сразу её осознал.
Наиболее полно проблема решения логических уравнений рассмотрена в работах П.С.Порецкого [45] и Н.П.Брусенцова [3].
Предлагается более простой и эффективный метод решения логических уравнений[17, 29], основанный на применении таблиц истинности и четырёхзначной логики.
Автором для решения логических уравнений впервые предлагается четырехзначная комплементарная логика. Она полностью соответствует общеразговорной, или бытовой логике. Вышеназванная логика представлена базисными функциями. Значения этой логики имеют следующий смысл: 0 - нет, j - не может быть никогда, i- может быть, 1 - да.
Следует обратить внимание на комплементарность (взаимодополняемость, взаимоинверсность) значений переменных : 0+1=1, i+j=1, 01=0, ij=0. В связи с этим вполне естественно было назвать такую логику комплементарной. Для приведённых базисных функций комплементарной логики как и для 3-значной логики также справедлив закон Де Моргана.
При решении системы логических уравнений вначале определяется так называемая полная единица задачи (системы)[44], а потом отыскивается решение уравнения относительно одной из переменных. Под решением здесь и далее понимается преобразование исходного уравнения к явному виду относительно одной из переменных. Поскольку построение полной единицы системы не вызывает затруднений, рассмотрим решение логического уравнения с помощью таблиц истинности, считая полную единицу (m) известной.
В качестве примера рассмотрим именно ту задачку, с которой автор начинал освоение классической логики. Тогда, в 1995г.,только что получив в подарок от Н.П.Брусенцова его книжку «Начала информатики»[3], я заявил, что в логике нет и не может быть проблем, поскольку там всё понятно даже четверокласснику. В ответ Учитель предложил решить любое логическое уравнение. Я ответил, что справлюсь с этим за 5 минут. При всём при том я даже не знал, что такое «решение логического уравнения». Я взял в качестве уравнения первое, что пришло в голову: M = ab+cd. Брусенцов Н.П. заявил, что это сложное уравнение, но мне оно таким не казалось – я справился с ним за обещанные 5 минут. Надеюсь, что Читатель тоже уложится в этот интервал.
Пример 1.
Дано : m = ab + cd = 1
Найти : d = f(a,b,c)
Решение.
На основании исходного логического уравнения полной единицы строим таблицу истинности для разрешённых наборов, т.е. тех наборов, на которых исходное уравнение имеет решение, т.е. разворачиваем ДНФ в СДНФ. Перенеся столбцы a,b,c из исходной таблицы в качестве значений аргументов, а столбец d - в качестве значений искомой функции, получим таблицу истинности для d = f(a,b,c).
По полученной таблице заполним карту Карно, откуда после минимизации выведем соотношения для d = f(a,b,c). Если на некотором наборе функция принимает значение как 0, так и 1, то в соответствующую клетку карты Карно вписываем символ i. Если на каком либо наборе функция не определена, то в соответствующую клетку карты Карно вносим значение j. Здесь и далее апостроф означает отрицание аргумента или функции. Применение карты Карно не имеет принципиального значения: просто автор считает карты Карно наиболее эффективным инструментом для минимизации логических функций.
Клетки карты Карно с координатами 011 и 111 заполнены значением i, т.к. на этих наборах(индивидах, конституентах) d принимает значения как 0, так и 1. Наборы 000, 001 и 010 в таблице отсутствуют, поскольку при таких значениях аргументов исходное уравнение не имеет решения, поэтому соответствующие карты Карно заполнены символом j.
Для трёхзначной логики в этих клетках помещается прочерк [17], т.е. символ недоопределённости. Доопределение минимизируемой функции единицами позволяет получить компактную формулу.
Для комплементарной логики имеем:
d = cb’ + ca’ + iba + j(c’b’ + c’a’)
Для трёхзначной логики это уравнение выгдядит проще:
d = b’ + a’ + iba
Но просто ещё не значит истинно. Поэтому произведём проверку полученных результатов. Кстати, эту проверку я ввёл далеко не сразу. Как её сделать? Очень просто. Если из M = ab+a’b’ мы получили решение a=b, то и из a=b мы должны на основе формулы эквивалентности вернуться к M = ab+a’b’.
Работать с эквивалентностью в 4-значной комплементарной логике достаточно сложно, поэтому я предлагаю Читателю более простой метод обычной булевой алгебры. Дело в том, что для выражения y = f1+if2+jf3 удалось установить соответствие y = f1+yf2+y’f3. Запомните это рекурсивное соотношение:
Я предлагаю Читателю поломать голову над выводом вышеприведённого соответствия. Кстати, заодно и над модификацией разработанной мною алгебры четырёхзначной комплементарной логики: не всё мне там нравится. Да, есть ещё интересная проблема: один студент ТВАТ на моих лекциях по Русской логике заявил, что общеразговорная логика 5-значна: 5-е значение – «не знаю». Надеюсь, что кто-нибудь из русских мыслителей создаст алгебру 5-значной логики. К стыду своему, фамилию этого талантливого русского студента я не запомнил. Приношу ему свои самые искренние извинения. За 15 прошедших лет это был единственный студент (надеюсь, будущий выдающийся учёный), который открыл 5-значную логику здравого смысла.
А теперь приступим непосредственно к проверке полученных результатов. Начнём с 4-значной комплементарной логики.
Приведём выражение d = cb’ + ca’ + iba + j(c’b’ + c’a’) к рекурсивному виду. Получим d = c(a’+b’)+abd+c’d’(a’+b’). Теперь найдём полную единицу системы, т.е. M. Поиск будем вести по формуле эквивалентности M = (x=y) = xy+x’y’, т.е. проверим равносильность преобразований в прямом и обратном направлении.
Тогда получим следующее выражение для М:
M = [d=c(a’+b’)+abd+c’d’(a’+b’)] = d[c(a’+b’)+abd+c’d’(a’+b’)]+d’[c(a’+b’)+abd+ +c’d’(a’+b’)]’ = cd(a’+b’)+abd+d’(a’c’d+abd’+b’c’d) = cd(a’+b’)+abd+abd’ = ab+cd, что и требовалось доказать.
То, что [c(a’+b’)+abd+c’d’(a’+b’)]’ = (a’c’d+abd’+b’c’d), удалось выяснить с помощью карты Карно: очень скучен процесс аналитического инвертирования.
Итак, проверка решения уравнения в 4-значной комплементарной логике закончилась благополучно.
Проведём проверку решения уравнения в 3-значной логике. Приведём выражение d = b’ + a’ + iba к рекурсивному виду. Получим d = b’+a’+dba=b’+a’+d. Откуда M = (d = b’+a’+d) = d(b’+a’+d)+d’(b’+a’+d)’ = d+abd’ = d+ab, что не сответствует исходному значению М. Мы доказали, что решение логических уравнений возможно только в 4-значной комплементарной логике, чего не знал и не мог знать П.С.Порецкий. Внимательно анализируя метод решения логических уравнений великого русского логика П.С.Порецкого[45], приходишь к выводу, что кое в чём гениальный математик ошибался. Но и на солнце бывают пятна, поэтому великим грехом эту оплошность назвать нельзя. Можно утверждать, что метод Порецкого даёт правильный результат только в том случае, если искомая функция является полностью определённой (ПОЛФ).
В связи с тем, что при решении логических уравнений приходится зачастую проводить минимизацию булевых функций от большого числа переменных, полезно ознакомиться с соответствующими алгоритмами, изложенными в [13,14] и в диссертации автора[15].
Пример 2.
Рассмотрим 1-ю задачу Порецкого[45]. Между птицами данного зоосада существует 5 отношений:
1. Птицы певчие - крупные или обладающие качеством Y.
2. Птицы, не имеющие качества Y - или не крупные, или не имеют качества Х.
3. Птицы певчие в соединении с крупными объединяют всех птиц с качеством Х.
4. Каждая не-крупная птица есть или певчая, или обладающая качеством Х.
5. Между птиц с качеством Х совсем нет таких птиц с качеством Y, которые, не будучи певчими, были бы крупные.
Определить, были ли птицы качества Х певчие или нет, крупные или нет. Узнать то же в отношении птиц качества Y. Найти, были ли среди птиц качества Х птицы качества Y и наоборот.
Решение.
Пусть Х - птицы качества Х.
Y - птицы качества Y.
S - певчие птицы.
G - крупные птицы.
Тогда условие задачи будет представлено следующими рекурсивными уравнениями [45]:
1. s= (g+ у)s;
2. у’= (g’+x’)у’;
3. s+g+x’=1;
4. g’=(s+x)g’;
5. xуs’g=0.
Эти уравнения Порецкий через эквивалентность приводит к единичной форме:
g+у+s’=1
g’+x’+у=1
s+g+x’=1
s+g+x=1
x’+у’+s+g’=1
Нетрудно заметить, что система уравнений Порецкого представляет собой сорит, содержащий посылки общего характера. Посылки частно-утвердительного характера метод Порецкого обрабатывать не может.
Кстати, используя силлогистические функторы Аху и Еху, можно получить эти соотношения сразу, не прибегая к рекурсии и эквивалентности. Исходя из вышесказанного можно утверждать, что аналитическое представление силлогистических функторов Axy, Exy было впервые в мире дано русским логиком Порецким П.С. Правда, мировая логика не заметила этого научного достижения, как не увидела и того, что позже к аналогичному выводу пришел и Л.Кэрролл[11]. Логика до сих пор прозябает в невежестве. На основе соотношений Axy = x’+y и Exy = x’+y’, выведенных нами в разделе «Базисы силлогистики»(см. рис. «Переход от диаграмм Венна к диаграммам Лобанова»), получим:
1.As(g+y) = s’+g+y = 1
2. Ay’(g’+x’) = y+g’+x’ = 1
3. Ax(s+g) = x’+s+g = 1
4. Ag’(s+x) = g+s+x = 1
5. Ex(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’
xy gs
|
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, то в соответствующую клетку карты Карно вписываем i. Если какой-нибудь набор отсутствует, то для этого набора в карту Карно вносим значение j комплементарной логики.
После минимизации получим для комплементарной логики системы уравнений:
x = is + jg’s’
у = g’s + ig + jg’s’
у = x + ix’ = (x + ix) + ix’ = x + i
x = iy
После приведения к рекурсивной форме имеем:
x = xs + x’g’s’
у = g’s + yg + y’g’s’
у = x + y
x = xy
Результаты, полученные Порецким:
x = xs
у = gу + g’s
у = у + x
x = xy
Сравнивая системы уравнений, можно заметить расхождение в результатах. Проверим себя и Порецкого. Полная единица системы M(g,s,x) = s+gx’. Это следует из основной формулы M(g,s,x,y) = sy+gx’. Для комплементарной логики имеем M(g,s,x) = (x=xs+x’g’s’) = xs+x’(xs+x’g’s’)’ = xs+x’(x’s+gs’+xs’) = xs+x’s+x’g = s+gx’, что и требовалось доказать. Проверка остальных результатов комплементарной логики также завершилась успешно.
Для Порецкого проверка не увенчалась успехом. Здесь великий логик допустил ошибку: он нашёл лишь частное решение. Привожу проверку равносильности преобразований для x=xs:
M(g,s,x) = (x=xs) = xs+x’(xs)’ = xs+x’ = s+x’, что не соответствует заданному M(g,s,x).
Строгим решением является лишь результат, полученный на основе четырёхзначной комплементарной логики.
Комплементарная логика в электронике повышает надёжность любого устройства. Электронная система, построенная на такой логике, фиксирует те ситуации, которые не могут быть никогда. Например, в сложной системе управления своевременное обнаружение таких состояний может предотвратить аварию или отказ. Поэтому можно надеяться, что вычислительная техника (да и не только она, но и юриспруденция тоже) будет строиться на комплементарной логике.
Кстати, первая в мире троичная ЭВМ «Сетунь-70» была создана в России Брусенцовым Н.П. (МГУ). Что касается 4-значной ЭВМ, то аппаратная реализация комплементарной логики на современной двоичной элементной базе весьма несложна.
Основываясь на примерах 1 и 2, составим алгоритм решения системы логических уравнений.
|
