10.2. Алгоритм «Селигер» решения уравнений в 4-значной логике.
1. Привести систему уравнений к нулевому виду (исходная система).
2. Заполнить карту Карно нулями в соответствии с термами левых частей исходной системы уравнений, а в оставшиеся клетки вписать единицы. Эти единичные термы представляют собой СДНФ полной единицы системы.
3. Произвести минимизацию совокупности единичных термов. Полученное соотношение представляет МДНФ уравнения полной единицы системы.
4. Построить сокращённую (только для единичных термов) таблицу истинности уравнения полной единицы и выписать из неё все значения входных и выходной переменных в виде частной таблицы истинности для искомой функции.
5. Произвести минимизацию полученного выражения..
6. Привести полученное выражение к рекурсивной форме, заменив i на прямое значение искомой переменной, а j – на инверсное значение этой переменной.
7. Произвести проверку рекурсивного выражения на соответствие его полной единице системы для задействованных аргументов, т.е. выполнить проверку равносильности произведённых преобразований.
Если система уравнений простая и позволяет легко найти СДНФ для М, то решение можно начинать сразу с п.3 алгоритма "Селигер". Алгоритм предполагает не только графическую, но и аналитическую минимизацию методом обобщённых кодов [13, 26]. Для систем уравнений с числом аргументов не более 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
Нулевые термы системы уравнений занесём в карту Карно, откуда получим функцию полной единицы.
M = ac’+bd.
По полученному соотношению строим сокращённую таблицу истинности и выписываем из неё значения b и d в виде таблицы, из которой получаем логическую функцию. Из этой функции следует, что d не зависит от b, что совпадает с результатом Порецкого.
Если построить диаграммы Лобанова, то сразу становятся очевидными все зависимости между аргументами a, b, c, d. Например, понятно, что «Всё дорогое бельё – новое» и «Всё дорогое бельё – крупное».
Пример 4
Дано: M = xy+x’y’ = 1.
Найти: x = f(y).
Решение.
Применяя метод Порецкого, домножим левую и правую части исходного равенства на х. Получим (xy+x’y’)x = x или после минимизации x = xy. Но для этого равенства полная единица M = x’+y = Axy, что не соответствует заданной формуле равнозначности M = xy+x’y’. Кроме того, по алгоритму «Селигер» истинное решение уравнения выглядит так: x = y. К тому же это общеизвестный факт. Но ещё первичнее то обстоятельство, что 2-й закон Лобановой С.В. не позволяет этого делать.
Таким образом, мы видим, что метод Порецкого может давать противоречащие математике и здравому смыслу решения логических уравнений.
10.3. Алгоритм «Волга» решения уравнений в двоичной логике.
Под решением логического уравнения мы понимаем преобразование исходного уравнения к явному виду относительно одной из переменных. Впервые в мире эту проблему сумел разрешить гениальный русский учёный Платон Сергеевич Порецкий в своей работе о логических равенствах [45].
Однако Порецкий П.С. допустил ряд ошибок, для уcтранения которых пришлось разработать алгебру 4-значной комплементарной логики и алгоритм «Селигер».
А нельзя ли найти решение поставленной задачи, не прибегая к 4-значной логике? Оказывается, можно. Автором разработан алгоритм «Волга», опирающийся только на булеву алгебру.
Алгоритм «Волга» решения уравнений в двоичной логике.
1. Привести систему уравнений к нулевому виду.
2. Заполнить карту Карно нулями в соответствии с термами левых частей исходной системы уравнений, а в оставшиеся клетки вписать единицы. Эти единичные термы представляют собой СДНФ полной единицы системы.
3. Произвести минимизацию совокупности единичных термов. Полученное соотношение представляет минимальную дизъюнктивную нормальную форму (МДНФ) уравнения полной единицы системы.
4. Построить сокращённую (только для единичных термов) таблицу истинности уравнения полной единицы и выписать из неё все значения входных и выходных переменных в виде частной таблицы истинности для искомой функции.
5. Если на каком-либо наборе функция Y принимает как 0, так и 1, то присвоить ей значение Y. Если существуют наборы, на которых функция Y не определена, то на этих наборах искомой функции присвоить её инверсное значение, т.е. Y’.
6. Произвести минимизацию полученного выражения.
7. Произвести проверку рекурсивного выражения на соответствие его полной единице системы для задействованных аргументов, т.е. выполнить проверку равносильности произведённых преобразований.
Рассмотрим вновь 1-ю задачу Порецкого[45]. Между птицами данного зоосада существует 5 отношений:
1. Птицы певчие - крупные или обладающие качеством Y.
2. Птицы, не имеющие качества Y - или не крупные, или не имеют качества Х.
3. Птицы певчие в соединении с крупными объединяют всех птиц с качеством Х.
4. Каждая не-крупная птица есть или певчая, или обладающая качеством Х.
5. Между птиц с качеством Х совсем нет таких птиц с качеством Y, которые, не будучи певчими, были бы крупные.
Определить, были ли птицы качества Х певчие или нет, крупные или нет. Узнать то же в отношении птиц качества Y. Найти, были ли среди птиц качества Х птицы качества Y и наоборот.
Решение.
Пусть Х - птицы качества Х, Y - птицы качества Y,
S - певчие птицы, G - крупные птицы.
На основе соотношений 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
Полный логический нуль системы равен дизъюнкции всех левых частей системы логических уравнений. Заполним карту Карно нулями в соответствии с нулевыми термами системы, а в оставшиеся клетки впишем единицы. Тогда полная логическая единица всей задачи после минимизации примет такой же вид, как и в [44, с.113]:
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, то в соответствующую клетку карты Карно вписываем символическое обозначение искомой функции. Если какой-нибудь набор отсутствует, то для этого набора в карту Карно вносим символическое обозначение инверсии искомой функции.
После минимизации получим следующие системы уравнений:
x = xs + x’g’s’, у = g’s + gy + g’y’, у = x + y.
Проверим корректность решения задачи на более простом первом результате. Полная единица системы M(g,s,x) = s+gx’. Это следует из основной формулы M(g,s,x,y) = sy+gx’.
Аналогично: M(g,s,y) = g+sy, M(x,y) = x’+y.
Проверка равносильности преобразований выглядит так: 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’, что и требовалось доказать. Проверка остальных уравнений также завершилась успешно: M(g,s,y)=( у=g’s + gy + g’y’) = g+sy, M(x,y) = (y=x+y) = y(x+y)+y’(x+y)’ = y+y’(x’y’) = y+x’y’ = x’+y.
10.4. Равносильные преобразованиялогических уравнений.
При решении логических уравнений иногда возникает необходимость в равносильных преобразованиях. Эта проблема рассмотрена в [3] и решена путём введения понятий парного и непарного индивидов. Однако, чёткое определение этих понятий отсутствует. Рассмотрим проблему на примере решения задачи.
Задача 10.4.1.
Это задача Лобановой С.В. При синтезе функции переноса в одноразрядном сумматоре получается выражение:
p1 = p0(ab)+ab, где а,b – складываемые числа, p0 и p1 – входной и выходной переносы. После минимизации получается функция p1 = p0(a+b)+ab. Напрашивается «очевидный» вывод: (ab) = (a+b). Но это противоречит здравому смыслу и математике. Поэтому проверим истинность суждения:
[(p0(ab)+ab) = [(p0(a+b)+ab)] [(ab) = (a+b)].
Решение.
Доказывать истинность {(p0(ab)+ab) = [(p0(a+b)+ab)]} [(ab)=(a+b)]=1 достаточно муторно, поэтому рассмотрим общий случай, на его основе выведем общий закон, а на основе закона решим задачу Лобановой С.В.
Исходя из равенств y = ax+b, y = az+b проверить суждение
[(ax+b) = (az+b)] (x=z), т.е. можно ли удалять из правой и левой части равенства одинаковые логические слагаемые и сомножители.
На основе алгоритма «Импульс» получаем
[(ax+b)=(az+b)](x=z) = (ax+b)(az+b)+(x=z) = (ax+b)(az+b) + b’(a’+x’)+ (x=z) = b+axz+a’b’+b’x’+xz+x’z’ = x’+z+a’+b 1.
Из этого закона ясно видно, что исходное суждение ложно. Это было видно и без закона, на основании здравого смысла, однако его всегда нужно поддерживать строгими математическими доказательствами. Поскольку закон инициирован задачей Лобановой С.В., то он носит её имя. Поставить вопрос оказалось сложнее, чем ответить на него.
Мы доказали, что нельзя в общем случае сокращать обе части равенства на общие логические сомножители или удалять общие логические слагаемые.
Отсюда возник вопрос: что же можно "безболезненно" добавлять и удалять из логического равенства. Вопрос этот опять-таки навеян задачей Лобановой.
Докажем равносильность преобразований с помощью традиционных методов. Пусть х, у - логические функции, для которых справедливо уравнение х = у, приведённое через эквивалентность к виду.
( х = у ) = ху + х’у’
Требуется найти парный индивид z , т.е. такую функцию, добавление (удаление) которой к обеим частям равенства х=у не нарушало бы его равносильности. Это требование записывается в виде уравнения.
x + z = у + z
Но полученное выражение через формулу эквивалентности приводится к виду:
(x+z=у+z) = (x+z)(у+z)+(x+z)’(у+z)’ =
= xу+x’у’+z = (х=у)+z
Откуда следует, что z должен принадлежать исходному равенству, и парным индивидом для исходного уравнения х=у может быть любой терм уравнения или их комбинация, т.е. в данном случае парными индивидами являются только три терма: ху, х’у’,xу+х’у’.
х = у
(х +ху = у + ху) = (x = y)
(х + х’у’ = у + x’у’) = (x+y’ = x’+y) = [(x+y’)(x’+y) + (x+y’)’(x’+y)’] =
=x’y’+xy+x’y & xy’ = x’y’+xy = (x=y)
(x + ху + x’у’ = у + xу + х’у’) = [(x+y’) = (y+x’)] = (x = y)
Все эти 4 логических равенства равносильны.
Задача 10.4.2
Пусть х+а = у+b . Найти парные термы (индивиды).
Решение.
Развернём исходное уравнение на основе формулы эквивалентности:
(x+a=у+b)=(х+а)(у+b)+(х+а)’(у+b)’ = xу+ау+bx+ab+a’b’x’у’
Парными термами в этом случае являются ху, ау, bx, ab, a’b’x’у’ и все их комбинации, которые более наглядно можно представить на карте Карно.
Любой набор термов из единичных фигур покрытия [3] карты Карно может быть парным индивидом. Самым неочевидным является парный терм a’b’x’у’. Вот его и проверим.
[(x+a+ a’b’x’у’=у+b+ a’b’x’у’)] = (х+а+b’y’)(у+b+a’x’) = xy+ay+bx+ab+a’b’x’y’+
+(a’bx’+a’x’y)(ab’y’+b’xy’) = xy+ay+bx+ab+a’b’x’y’+0 = (x+a=у+b).
Проверка подтвердила правильность наших утверждений.
Определим общее количество парных индивидов n. Пусть u - количество переменных, входящих в уравнение f1=f2. Тогда количество конституент единицы k определится следующими соотношениями.
Для чётного u: k = 1 + [2^(u/2) - 1]^2
Для нечётного u: k = 1+(2^[(u+1)/2]-1)
Эти соотношения легко(?) выводятся из анализа карты Карно для уравнения х+а = у+b .Общее количество парных индивидов равно сумме биноминальных коэффициентов для бинома степени k без единицы:
n = 2^k – 1.
Более надёжно определяется минимальное количество парных индивидов: оно равно количеству логических слагаемых в СДНФ анализируемой функции.
А теперь рассмотрим равносильное преобразование при умножении обеих частей уравнения на один и тот же логический сомножитель.Имеем исходное уравнение x = y. Домножим обе части уравнения на логический сомножитель с. Получим:
(cx = cy) = cxy+(cx)’(cy)’ = cxy+c’+x'y' = (x=y)+c’.
Полученное выражение будет эквивалентно исходному уравнению только при c’ = x’y’, c' = xy или c' = xy+x'y'. Отсюда получим c1 = x+y, c2=x'+y', c3 = (xy'+x'y) .
Проверим полученные результаты.
[(x+y)x = (x+y)y] = (x=y).
[(x'+y')x = (x'+y')y] = (xy'=x'y) = [0+(x'+y)(x+y')] = (xy+x'y') = (x=y).
[(xy'+x'y)x = (xy'+x'y)y] = (xy'=x'y) = (x'+y)(x+y') = (xy+x'y') = (x=y).
Следовательно, домножать обе части уравнения можно только на логическую сумму этих частей или их инверсий.
Законы Лобановой С.В.
Сокращение на общий множитель или отбрасывание общих частей в левой и правой половинах логического уравнения в общем случае недопустимо.
Можно домножать левую и правую части логического уравнения только на сомножитель, являющийся парным индивидом исходного уравнения. Соответственно удалять можно только такой сомножитель, который является парным индивидом остающегося уравнения.
Можно добавлять к обеим частям логического уравнения одно и то же логическое слагаемое, являющееся парным индивидом уравнения. Соответственно удалять можно только такое логическое слагаемое, которое является парным индивидом остающегося уравнения.»
Из законов Лобановой известно, что в общем случае [(x=y)=(x+c=y+c)] ≠ 1, т.е. [(x=y) ≠ (x+c=y+c)]. Однако также известно, что операции «равно» и «не равно» взаимноинверсны: (а=в) = ( а в )’ , а в = (а=в)’.
Проверим тождественность операций и ≠, заменив знак ≠ на знак в уравнении [(x=y) ≠ (x+c=y+c)] .
[(x=y) (x+c=y+c)] = {(x=y) [(x=y)+c]} = (x=y)[(x=y)+c]’ + (xy) [(x=y)+c] =
= (x=y)(xy)c’ + (xy) [(x=y)+c] = (xy)c = cxy’+cx’y ≠ 1, т.е. операции и ≠ не эквивалентны.
10.5. Отыскание обратных функций.
На основе метода, заложенного в алгоритме «Селигер», можно вывести соотношения для операций, обратных конъюнкции и дизъюнкции. Поскольку эти операции часто называются соответственно логическими умножением и сложением, то логично обратным операциям присвоить имена логического деления и логического вычитания. Впервые формулы для логического частного и логической разности для троичной логики получены Н.П.Брусенцовым[3, с.37]. Поскольку в троичной логике не может быть получено корректное решение, то требуется проверка уравнений Брусенцова.
Если логическое уравнение вида z=f(x1, x2, x3 .....xi .....xn) решается относительно одной из своих переменных, например, отыскивается обратная функция x1=fi(z, x2, x3 .....xi ..... xn), то можно воспользоваться более простым алгоритмом «Селигер-С» решения задачи.
Алгоритм «Селигер-С» синтеза обратных функций.
1. Построить таблицу истинности для уравнения z=f(x1, x2 ..... xn).
2. По исходной таблице истиннсти построить таблицу истинности для обратной функции вида x1=fi(z, x2 ......xn) простой перестановкой столбцов z и х1.
3. По полученной таблице истинности построить обратную функцию x1=fi(z, x2, ..... xn) и провести её минимизацию.
4. Проверить полученное решение, вычислив полную единицу системы М по обратной функции.
Пример 5.
Дано: z = xу , v = x + у.
Найти: у = z/x , у = v-x .
Решение.
На основе формулы эквивалентности преобразуем исходную формулу z=xу. Тогда получим (z=xу) = zxу + z’(x’+у’). В соответствии с пп.4, 5 алгоритма «Селигер» получим у = xz+ix’z’+jx’z.
Решим ту же задачу посредством алгоритма «Селигер-С». Исходные уравнения представим в виде таблицы истинности. Тогда в соответствии с п.2 алгоритма «Селигер-С» построим частные таблицы истинности для у= z/x и у=v-x.
В соответствии с п.3 алгоритма «Селигер-С проведём минимизацию искомых функций в комплементарной логике.
Для комплементарной логики получим:
у = z/x = xz + ix’z’ + jx’z = xz+x’yz+x’y’z - уравнение логического деления.
у = u-x = x’v + iv + jxv’ = x’v+yv+xy’v’ - уравнение логического вычитания.
Проверим оба полученных результата(проверка всех 16 обратных логических функций от двух аргументов будет проведена ниже). Пусть вначале это будет операция логического деления. В рекурсивной форме она выглядит так:
у = xz + yx’z’ + y’x’z
Найдём полную единицу системы М для полученной функции.
M = (у = xz + yx’z’ + y’x’z ) = y(xz + yx’z’ + y’x’z )+y’(xz + yx’z’ + y’x’z )’ =
= xyz+x’yz’+y’(y’z’+xz’+x’yz) = xyz+x’yz’+y’z’ = xyz+z’(x’+y’).
Она должна совпадать с исходной
M = (z=xy) = xyz+z’(xy)’ = xyz+z’(x’+y’). Налицо совпадение результатов.
Проверим формулу, полученную для логической разности. Исходная полная единица M = (v = x+y) = v(x+y) + v’(x+y)’ = xv+yv+x’y’v’.
Полная единица системы на основе логической разности
M = (y = x’v+yv+xy’v’) = x’yv+yv+y’(x’v+yv+xy’v’)’ = yv+y’(x’v’+yv’+xy’v) =
= yv+x’y’v’+xy’v = xv+yv+x’y’v’, ч.т.д.
Проверка подтвердила правильность полученных результатов.
Теперь проверим формулы, полученные Брусенцовым Н.П. [3, с.37]. Для логического деления была получена формула: y = xz+ix’.
Приведём её к рекурсивному виду – получим y = xz+yx’. Найдём полную единицу системы: M = (y = xz+yx’) = xyz+x’y+y’(xz+yx’)’ = xyz+x’y+y’(xz’+y’x’)’ = xyz+x’+xy’z’ = x’+x(y=z) = x’+(y=z), что не соответствует исходной М.
Для логического вычитания Брусенцовым Н.П. построена частичная функция [3, с.37] : y = x’z+ix. В рекурсивном виде y = x’z+yx. Найдём полную единицу системы M = (y = x’z+yx) = x’yz+xy+y’(x’z+yx)’ = x’yz+xy+y’(x’z’ + y’x) = x’yz + xy + xy’ = x’yz + x, что не соответствует исходной М.
Как мы убедились, однозначными и строгими решениями являются лишь уравнения комплементарной логики. Следовательно, в принципе не может быть правильным решение логического уравнения в троичной логике.
Пример 5.
Дана система логических уравнений (В. С. Левченков «Булевы уравнения» – М.:1999 ):
ax = bc
bx = ac
Найти х.
Решение .
Напрашивается простой и “очевидный” метод решения: сложить левые и правые части уравнений и сократить на общий множитель. В результате получим (a+b)x = (a+b)c. Откуда x = c, a = b. Ответ настораживает, тем более, что решение противоречит принципу отыскания парных индивидов, поэтому проверим его на основе разработанных алгоритмов.
. Действительно, сложить левые и правые части уравнений мы имеем право на основании правила (9П) Порецкого[48,стр,376]. Кстати, заодно и проверим это правило:
(e=c) (e+b=c+b) = ec’+e’c+(e+b)(c+b)+(e+b)’(c+b)’ = ec’+e’c+ec+b+e’b’c’ = 1;
Да, Порецкий не ошибся. Однако относительно сокращения на общий множитель великий русский логик нам ничего не сообщил. А так хочется это сделать, тем более что всё очевидно, и обычная алгебра нам не запрещает подобные операции. Проверим допустимость сокращения на общий множитель с помощью алгоритма “Импульс”:
(cx=cy) (x=y) = cx(cy)’+(cx)’cy+xy+x’y’ = cxy’+cx’y+xy+x’y’ 1.
Оказывается, что алгебра логики, а точнее 1-й закон Лобановой, не разрешает нам этакие вольности
По алгоритму “Селигер” :
M = (ax = bc)( bx = ac)
M’ = (axbc)+(bxac)=ab’x+ac’x+a’bc+bcx’+a’bx+bc’x+acx’+ab’c.
После занесения M’в карту Карно получим
M = a’b’+abcx+c’x’.
Откуда решение системы логических уравнений в соответствии с алгоритмом «Селигер» примет вид:
x = abc+ia’b’+jc(ab’+a’b) = abc+xa’b’+x’c(ab’+a’b).
a = bcx+ic’x’+jb(cx’+c’x) = bcx+ac’x’+a’b(cx’+c’x).
Проверка этих рекурсивных уравнений по полной единице системы М дала положительные результаты.
Заданная система уравнений может быть представлена графически при помощи скалярных диаграмм . Скалярные диаграммы построены по рабочим наборам таблицы истинности для М.
Скалярные диаграммы дают полное представление о системе уравнений. Подтвердим корректность метода на решении более прозрачной задачи.
Пример 6.
Дана система логических уравнений:
x = y
u = v
Найти решение системы.
Решение.
M = (x = y)(u = v) = (xy + x’y’)(uv + u’v’) = u’v’(x’y’ + xy)+uv(x’y’ + xy)
По алгоритму «Селигер» получим
y(x,u,v) = x(u = v)+j(u v)
Для перехода к y(x) достаточно в таблице истинности для полной единицы М вынести столбец значений y в графу функций и произвести синтез y(x) по вышеизложенным алгоритмам. В результате мы подтвердим исходное уравнение системы y(x) = x. Аналогично можно показать,что u(v) = v.
Кстати, в данном случае есть более простой способ поверки решения системы: в уравнении y(x,u,v) = x(u = v)+j(u v) убрать «лишние» переменные, т.е. подставить u = v = 1. Получим y(x) = x(1 = 1)+j(1 1) = х+ j0 = х, что и требовалось доказать.
Используя алгоритм «Селигер» или «Селигер-С», можно получить полную систему обратных функций для двоичной логики. В таблице приведена полная система прямых функций двоичной логики.
xy
|
z0
|
z1
|
z2
|
z3
|
z4
|
z5
|
z6
|
z7
|
z8
|
z9
|
z10
|
z11
|
z12
|
z13
|
z14
|
z15
|
00
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
01
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
10
|
0
|
0
|
1
|
1
|
0
|
0
|
1
|
1
|
0
|
0
|
1
|
1
|
0
|
0
|
1
|
1
|
11
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
Перестановкой столбцов у и z исходной таблицы строим таблицу истинности для полной системы обратных функций.
xz
|
y0
|
y1
|
y2
|
y3
|
y4
|
y5
|
y6
|
y7
|
y8
|
y9
|
y
10
|
y
11
|
y
12
|
y
13
|
y
14
|
y
15
|
00
|
i
|
i
|
i
|
i
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
j
|
j
|
j
|
j
|
01
|
j
|
j
|
j
|
j
|
1
|
1
|
1
|
1
|
0
|
0
|
0
|
0
|
i
|
i
|
i
|
i
|
10
|
i
|
0
|
1
|
j
|
i
|
0
|
1
|
j
|
i
|
0
|
1
|
j
|
i
|
0
|
1
|
j
|
11
|
j
|
1
|
0
|
i
|
j
|
1
|
0
|
i
|
j
|
1
|
0
|
i
|
j
|
1
|
0
|
i
|
Из таблицы обратных функций впервые получим полную симметричную систему обратных функций y = f1(x,z),а по алгоритму «Селигер» – y = f2(x):
у0 = iz’+jz y0 = j
у1 = xz+ix’z’+jx’z y1 = x+jx’
у2 = xz’+ix’z’+jx’z y2 = jx’
у3 = i(xz+x’z’)+j(xz’+x’z) y3 = ix+jx’
у4 = x’z+ixz’+jxz y4 = x’+jx
у5 = z y5 = 1
у6 = xz’+x’z y6 = x’
у7 = x’z+ixz+jxz’ y7 = x’+ix
у8 = x’z’+ixz’+jxz y8 = jx
у9 = xz+x’z’ y9 = x
у10= z’ y10 = 0
у11= x’z’+ixz+jxz’ y11 = ix
у12= i(xz’+x’z)+j(xz+x’z’) y12 = ix’+jx
у13= xz+ix’z+jx’z’ y13 = x+ix’ - импликация
у14= xz’+ix’z+jx’z’ y14 = ix’
у15= iz+jz’ y15 = i
Кстати, переход от левой системы уравнений к правой легко выполняется простой заменой z на 1 и z’ на 0. Аналогичные результаты мы получим, если таблицу прямых функций заменим скалярными диаграммами, а из них по алгоритму ТВАТ выведем соотношения y = f(x). Самой примечательной из полученных функций является y13 = x+ix’ – импликация. Из этого выражения легко просматривается физический смысл импликации: y обязательно истинно, если истинно x, но иногда y истинно даже при ложном х.
Решая 1-ю задачу Порецкого, мы заметили аналогию между рекурсивным вхождением функции и комплементарным значением i. Резонно предположить, что такая аналогия существует между комплементарным j и рекурсивным значением инверсии функции. Проверим это предположение на полученных одноаргументных функциях и убедимся в их обратимости с помощью формулы эквивалентности.
0) (y = j) (y = y')
M = (y=y') = yy'+y'y = 0
1) (y = x+jx') (y = x+x'y') = (y = x+y')
M = (y=x+y') = y(x+y')+y'(x+y')' = xy+y'x'y = xy
2) y = jx' x'y'
M = (y=x'y') = yx'y'+y'(x'y')' = y'(x+y) = xy'
3) y = ix+jx' xy+x'y'
M = (y=xy+x'y') = y(xy+x'y')+y'(xy'+x'y) = xy+xy' = x
4) y = x'+jx x'+xy' = x'+y'
M = (y=x'+y') = y(x'+y')+y'(x'+y')' = x'y
5) y = 1
M = (y=1) = y&1+y'&0 = y
6) y = x'
M = (y=x') = xy'+x'y
7) y = x'+ix x'+xy = x'+y
M = (y=x'+y) = y(x'+y)+y'(x'+y)' = y+xy' = x+y
8) y = jx xy'
M = (y=xy') = yxy'+y'(xy')' = x'y'
9) y = x
M = (y=x) = x'y'+xy
10)y = 0
M = (y=0) = y&0+y'&1 = y'
11)y = ix xy
M = (y=xy) = yxy+y'(xy)' = xy+y' = x+y'
12)y = ix'+jx x'y+xy'
M = (y=x'y+xy')=y(x'y+xy')+y'(x'y'+xy)=x'y+x'y' = x'
13)y = x+ix' x+x'y = x+y
M = (y=x+y) = y(x+y)+y'(x+y)' = y+x'y' = x'+y
14)y = ix' x'y
M = (y=x'y) = yx'y+y'(x'y)' = x'y+y' = x'+y'
15)y=i y
M = (y=y) = y&y+y'&y' = y+y' = 1
После обращения были получены все 16 прямых функций от двух аргументов без какого-либо искажения. Это подтверждает правильность всех алгоритмов решения логических уравнений и корректность комплементарной логики.
10.6. Разложение логических функций на множители.
В своей работе[44, с.130-134] П.С.Порецкий много внимания уделяет разложению логических функций на множители. На самом деле это чрезвычайно простая задача: достаточно перейти от дизъюнктивной нормальной формы(ДНФ) представления функции к конъюнктивной(КНФ).
Алгоритм «ОМТ» аналитического нахождения посылок сорита.
Найти инверсию функции М и представить её в виде ДНФ, т.е. в виде логической суммы.
Проинвертировать полученную M’ и представить М в виде КНФ, т.е. в виде произведения логических сомножителей.
Например, нужно разложить функцию М полной единицы системы на множители, т.е. на элементарные посылки.
Пусть M = ab+cd. Тогда, проведя первое инвертирование, получим:
M’ = (ab+cd)’ = (a’+b’)(c’+d’) = a’c’+b’c’+a’d’+b’d’.
Проведя второе инвертирование, получим:
M = (a’c’+b’c’+a’d’+b’d’)’ = (a+c)(b+c)(a+d)(b+d).
В полученном результате легко просматривается более простой алгоритм механического разложения логической функции на множители.
Пусть M = ab+cd+ef. Тогда после разложения на множители получим следующий результат:
M = (a+c+e)(b+c+e)(a+d+e)(b+d+e)(a+c+f)(b+c+f)(a+d+f)(b+d+f).
10.7. Алгебра 6-значной комплементарной логики.
Когда автор в 1996г. заявил, что общеразговорная логика, т.е. логика здравого смысла (ЛЗС), четырёхзначна, то в это поверили не сразу. Однако один из моих студентов в ТВАТ, к стыду своему я не запомнил фамилии этого талантливого русского юноши, заявил, что ЛЗС пятизначна: пятое значение – «не знаю» (k). Я согласился, но создание 5-значной алгебры переложил на инициатора.
Прошло десять лет, и я вернулся к этой проблеме. Мне пришла в голову мысль, что ЛЗС шестизначна и комплементарна. Шестое значение – «знаю, но не скажу»(s). Так может ответить, например, патриот на вопрос оккупанта.
Если принять шестизначность за аксиому, то алгебра такой логики может выглядеть так.
Следует обратить внимание на комплементарность (взаимодополняемость, взаимоинверсность) значений переменных : 0+1=1, i+j=1, k+s=1, 01=0, ij=0, k&s=0. В связи с этим вполне естественно назвать такую логику комплементарной. Для приведённых базисных функций 6-значной логики как и для 2-, 3- и 4-значной логики также справедлив закон Де Моргана.
10.8. Парадоксы Русской логики.
Прошло уже 128 лет, как вышла в свет работа выдающегося русского логика Порецкого П.С. о решении логических равенств [45]. По сути дела это основополагающий труд, ознаменовавший создание истинно математической логики, о которой мечтал Лейбниц и всё человечество. До сих пор никто в мире не понял достижений русского учёного. Пришлось перевести работу Порецкого П.С. на язык четвероклассника, устранить принципиальные ошибки великого логика и создать корректные методы решения логических уравнений, а также методы анализа и синтеза силлогизмов и соритов [16-41]. В итоге родилась Русская вероятностная логика (РВЛ). Поскольку и её никто не понял, пришлось написать конспект по РВЛ[42]. Фундаментом РЛ явились скалярные диаграммы Лобанова. На их основе были выведены все аналитические соотношения для общеутвердительных, общеотрицательных и частноутвердительных кванторов, а также разработаны методы анализа и синтеза силлогизмов и соритов.
В настоящее время Русская логика стала индикатором интеллекта: если освоил РЛИ [41], то интеллект на «3», не понял РЛИ – бестолочь. Если разобрался с Порецким [45] и устранил его принципиальные ошибки, то интеллект на «4». Если нашёл ошибки («парадоксы») в РЛ и сумел их нейтрализовать, то интеллект на «5».
За прошедшие 14 лет никто не сумел обнаружить эти парадоксы. Боюсь, что математики будут ещё 128 лет разбираться в РЛ. Поэтому раскрываю парадоксы для толковых математиков-патриотов. Надеюсь, что русским матлогикам удастся решить те задачи, с которыми не справился автор.
Из диаграмм Лобанова были получены соотношения: Axy = x’+y, Exy=x’+y’, Ixy=1. Однако суждение Exy→Ixy=(x’+y’)’+1 = 1 парадоксально: мы доказали истинность шокирующей импликации, что противоречит здравому смыслу.
Следующие парадоксы можно усмотреть в алгебрах комплементарных 4- и 6-значных логик. Парадокс 4-значной логики автор нейтрализовал за счёт перехода к двоичной логике при решении логических уравнений. Результаты такого метода абсолютно корректны, но хотелось бы научиться решать логические равенства, используя комплементарные 4-значную и 6-значную логики. Это умение пригодится при создании ИИ.
Успеха вам в доработке РЛ, Русские математики!
Выводы.
1. Простота методов, заложенных в алгоритмах «Селигер» и «Волга», позволяет решать логические уравнения от большого числа переменных.
2. Минимизация функций в 3-значной и комплементарной логиках для двоичных аргументов несущественно отличается от традиционных методов двузначной логики.
3. Парные термы для равносильных преобразований определяются набором термов, полученных на основе применения формулы эквивалентности к исходному логическому уравнению.
4. Применение метода при выводе обратных логических функций показало, что корректное решение для двоичных аргументов может быть получено лишь в четырёхзначной комплементарной логике.
5.Впервые получены все 16 обратных логических функций для двух аргументов.
6. Комплементарная логика при аппаратной реализации позволяет значительно упростить решение проблемы самодиагностирования вычислительной техники: например появление j на любом выходе может свидетельствовать о сбое или отказе.
|
