Русская вероятностная логика (стр. 36 )

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. Например, понятно, что «Всё дорогое бельё – новое» и «Всё дорогое бельё – крупное».

11.3. Равносильные преобразования.

При решении логических уравнений иногда возникает необходимость в равносильных преобразованиях. Эта проблема рассмотрена в [3] и решена путём введения понятий парного и непарного индивидов. Однако, чёткое определение этих понятий отсутствует.

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

( х = у ) = ху + х’у’

Требуется найти парный индивид z, т. е. такую функцию, добавление (удаление) которой к обеим частям равенства х=у не нарушало бы его равносильности. Это требование записывается в виде уравнения.

x + z = у + z

Но полученное выражение через формулу эквивалентности приводится к виду:

(x+z=у+z) = (x+z)(у+z)+(x+z)’(у+z)’ =

= xу+x’у’+z = (х=у)+z

Откуда следует, что z должен принадлежать исходному равенству, и парным индивидом для исходного уравнения х=у может быть любой терм уравнения или их комбинация, т. е. в данном случае парными индивидами являются термы ху, х’у’, xу+х’у’.

х = у

х +ху = у + ху

х + х’у’ = у + x’у’

x + ху + x’у’ = у + xу + х’у’

Пример 4.

Пусть х+а = у+b. Найти парные термы (индивиды).

Решение.

Развернём исходное уравнение на основе формулы эквивалентности :

(x+a=у+b)=(х+а)(у+b)+(х+а)’(у+b)’ = xу+ау+bx+ab+a’b’x’у’

Парными термами в этом случае являются ху, ау, bx, ab, a’b’x’у’ и все их комбинации, которые более наглядно можно представить на карте Карно.

Любой набор термов из единичных фигур покрытия [3] карты Карно может быть парным индивидом. Определим общее количество парных индивидов 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

11.4. Отыскание обратных функций.

На основе метода, заложенного в алгоритме «Селигер», можно вывести соотношения для операций, обратных конъюнкции и дизъюнкции. Поскольку эти операции часто называются соответственно логическими умножением и сложением, то логично обратным операциям присвоить имена логического деления и логического вычитания. Впервые формулы для логического частного и логической разности для троичной логики получены [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П) Порецкого[34,стр,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.

Оказывается, что алгебра логики не разрешает нам этакие вольности

По алгоритму “Селигер” :

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 = х, что и требовалось доказать.