Русская логика – индикатор интеллекта (стр. 11 )

Алгоритм «Волга» решения уравнений в двоичной логике.

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(aÅb)+ab, где а, b – складываемые числа, p0 и p1 – входной и выходной переносы. После минимизации получается функция p1 = p0(a+b)+ab. Напрашивается «очевидный» вывод: (aÅb) = (a+b). Но это противоречит здравому смыслу и математике. Поэтому проверим истинность суждения:

[(p0(aÅb)+ab) = [(p0(a+b)+ab)] ® [(aÅb) = (a+b)].

Решение.

Доказывать истинность {(p0(aÅb)+ab) = [(p0(a+b)+ab)]} ® [(aÅb)=(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]’ + (xÅy) [(x=y)+c] =

= (x=y)(xÅy)c’ + (xÅy) [(x=y)+c] = (xÅy)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’ = (axÅbc)+(bxÅac)=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 исходной таблицы строим таблицу истинности для полной системы обратных функций.