2015-07-14
987
Задача 1
Дано: m = ab + cd = 1---------------------------Найти: d = f(a,b,c)Решение
На основании исходного логического уравнения полной единицы строим таблицу истинности для разрешённых наборов, т.е. тех наборов, на которых исходное уравнение имеет решение. Перенеся столбцы a,b,c из исходной таблицы в качестве значений аргументов, а столбец d - в качестве значений искомой функции, получим таблицу истинности для d = f(a,b,c).
| dcba | _m_ |
В соответствии с п.4 алгоритма "Селигер" построим диаграммы.
a =====================------=====----- b =====================-----------===== c ----=====------====================== d ---------============================| cba | _d_ |
По полученной таблице заполним карту Карно, откуда после минимизации выведем соотношения для d = f(a,b,c). Если на некотором наборе функция принимает значение как 0, так и 1, то в соответствующую клетку карты Карно вписываем символ i. Если на каком либо наборе функция не определена, то в соответствующую клетку карты Карно вносим значение j. Здесь и далее апостроф означает отрицание аргумента или функции. Применение карты Карно не имеет принципиального значения: просто автор считает карты Карно наиболее эффективным инструментом для минимизации булевых функций.
| c \ ba | ||||
| j | j | i | j | |
| i |
Клетки карты Карно с координатами 011 и 111 заполнены значением i, т.к. на этих наборах(индивидах,конституентах) d принимает значения как 0, так и 1. Наборы 000, 001 и 010 в таблице отсутствуют, поскольку при таких значениях аргументов исходное уравнение не имеет решения, поэтому соответствующие карты Карно заполнены символом j.
Для трёхзначной логики в этих клетках помещается прочерк, т.е. символ недоопределённости. Доопределение минимизируемой функции единицами позволяет получить компактную формулу.
Для комплементарной логики имеем:
d = cb' + ca' + iba + j(c'b' + c'a')Для трёхзначной логики это уравнение выгдядит проще:
d = b' + a' + ibaЗадача 2
Рассмотрим 1-ю задачу Порецкого[27]. Между птицами данного зоосада существует 5 отношений:
- Птицы певчие - крупные или обладающие качеством Y.
- Птицы, не имеющие качества Y - или не крупные, или не имеют качества Х.
- Птицы певчие в соединении с крупными объединяют всех птиц с качеством Х.
- Каждая не-крупная птица есть или певчая, или обладающая качеством Х.
- Между птиц с качеством Х совсем нет таких птиц с качеством Y, которые не будучи певчими, были бы крупные.
Определить, были ли птицы качества Х певчие или нет. Узнать то же в отношении птиц качества Y.Найти, были ли среди качества Х птицы качества Y и наоборот.
Решение
Пусть
Х - птицы качества Х.Y - птицы качества Y.S - певчие птицы.G - крупные птицы.Тогда условие задачи будет представлено следующими рекурсивными уравнениями [27]:
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=15. x'+у'+s+g'=1Нетрудно заметить, что система уравнений Порецкого представляет из себя сорит, содержащий посылки общего характера(см. раздел 4). По соответствующим формулам из базиса Васильева преобразуем уравнения Порецкого:
1. g+у+s'=As(g+y).2. g'+x'+у=Ay'(g'+x'). 3. s+g+x'=Ax(s+g).4. s+g+x=Ag'(s+x).5. x'+у'+s+g'=E(xy)(s'g).Ктати, эта функторная мнемоника напрямую описывает текстовые посылки Порецкого. Порецким впервые в мире применены здесь многоаргументные функторы, о которых мечтал Л.Кэрролл. Порецкий также впервые в мире отыскал методы решения многоаргументных полисиллогизмов общего характера. Посылки частно-утвердительного характера метод Порецкого обрабатывать не может. У Кэрролла нет решения даже для многоаргументных соритов, не говоря уже о полисиллогизмах.
Полная логическая единица M всей задачи определится как конъюнкция всех левых частей системы логических уравнений. Эту рутинную операцию можно заменить на менее утомительную процедуру построения дизъюнкции нулей. Получим систему:
1. g'у's=02. gxу'=03. g's'x=04. g's'x'=05. gs'xу=0Полный логический нуль системы равен дизъюнкции всех левых частей системы логических уравнений. Проведём решение задачи Порецкого с использованием карты Карно, а потом сопоставим результаты. Заполним карту Карно нулями в соответствии с нулевыми термами системы, а в оставшиеся клетки впишем единицы. Тогда полная логическая единица всей задачи после минимизации примет вид:
m=sу+gx'| gs\xy | ||||
Выпишем из карты Карно все единичные наборы в виде таблицы истинности. По полученной таблице построим таблицы для х=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 = xsу = gу + g'sу = у + xИз диаграмм и сокращённой таблицы истинности можно получить и более прозрачные результаты:
F1(x,s) = x'+s = Axs.F2(g,s,y) = sy+g = Ag'(sy) = A9s'+y')g.F3(x,y) = y+x' = Axy.Задача 3
Рассмотрим 2-ю задачу Порецкого.
Относительно белья в комоде известны 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, что совпадает с результатом Порецкого.
По алгоритму "Селигер" получим b = i, а по алгоритму "ТВАТ"
f(b,d) = 1 = Ibd(8).Эти выражения эквивалентны.
Задача 4
Дано: 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.
| xy | z | v |
| xy | y=z/x |
| i | |
| j | |
| xy | y=v-x |
| j | |
| i |
В соответствии с п.3 алгоритма "Селигер-С проведём минимизацию искомых функций в трёхзначной и комплементарной логиках.
Для комплементарной логики получим:
у = z/x = xz + ix'z' + jx'z у = u-x = x'v + ixv + ixv'Для трёхзначной логики уравнения имеют вид:
у = z/x = xz + ix' у = v-x = x'v + ixОднозначным и более строгим решением являются уравнения комплементарной логики.
Задача 5
Дана система логических уравнений (В. С. Левченков "Булевы уравнения" - М.:1999):
ax = bcbx = ac--------------Найти х.Решение
Напрашивается простой и "очевидный" метод решения: сложить левые и правые части уравнений и сократить на общий множитель. В результате получим (a+b)x = (a+b)c. Откуда x = c, a = b. Ответ настораживает, тем более, что что решение противоречит принципу отыскания парных индивидов, поэтому проверим его на основе разработанных алгоритмов.
Действительно, сложить левые и правые части уравнений мы имеем право на основании правила (9П) Порецкого. Кстати, заодно и проверим это правило:
(9П)(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.Оказывается, что алгебра логики не разрешает нам этакие вольности, т.е. мы доказали, что уравнения (cx=cy) и (x=y) не равносильны.
По алгоритму "Селигер":
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).a = bcx+ic'x'+jb(cx'+c'x).Заданная система уравнений может быть представлена графически при помощи скалярных диаграмм. Скалярные диаграммы построены по рабочим наборам таблицы истинности для М.
a -------------======----============== b -------------==========-------======= c --------===========------------------ x ---=====----=======------------------Скалярные диаграммы дают полное представление о системе уравнений. Подтвердим корректность метода на решении более прозрачной задачи.
Задача 6
Дана система логических уравнений:
x = yu = v-------------------------Найти решение системы.Решение
M = (x = y)(u = v) = (xy + x'y')(uv + u'v') = = u'v'(x'y' + xy)+uv(x'y' + xy).Для обеспечения наглядности решения уравнения представим полную единицу системы М в виде скалярных диаграмм.
| uvxy | _m_ |
По алгоритму "Селигер" получим
y(x,u,v) = x(u = v)+j(u Å v)Для перехода к y(x) достаточно в таблице истинности для полной единицы М вынести столбец значений y в графу функций и произвести синтез y(x) по вышеизложенным алгоритмам. Второй способ заключается в том, что в полученной формуле для y(x,u,v) мы заменим лишние аргументы u,v на 1. В результате мы подтвердим исходное уравнение системы y(x) = x. Аналогично можно показать,что u(v) = v.
Задача 7
Используя алгоритм "Селигер", получить полную систему обратных функций для двоичной логики. В таблице приведена полная система функций двоичной логики.
| xy | z0 | z1 | z2 | z3 | z4 | z5 | z6 | z7 | z8 | z9 | z10 | z11 | z12 | z13 | z14 | z15 |
Решение
Перестановкой столбцов у и z исходной таблицы строим таблицу истинности для полной системы обратных функций.
| xz | y0 | y1 | y2 | y3 | y4 | y5 | y6 | y7 | y8 | y9 | y10 | z11 | z12 | z13 | z14 | z15 |
| I | i | i | i | j | j | j | j | |||||||||
| J | j | j | j | i | i | i | i | |||||||||
| I | j | i | j | i | j | i | j | |||||||||
| J | i | j | i | j | i | j | 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.
