Практикум по решению логических уравнений

Краткая справка

Логические уравнения

Теоретический материал в полном объёме можно найти в работах [18,24,26].

Таблица базисных функций 4-значной комплементарной логики

XY	X'	X&Y	X+Y	XY	X'	X&Y	X+Y
				i0	j
0j			j	ij	j
0i			i	ii	j	i	i
				i1	j	i
j0	i		j
jj	i	j	j	1j		j
ji	i			1i		i
j1	i	j

Алгоритм "Селигер" решения логических уравнений

1. Привести систему уравнений к нулевому виду (исходная система).
2. Заполнить карту Карно нулями в соответствии с термами левых частей исходной системы уравнений, а в оставшиеся клетки вписать единицы. Эти единичные термы представляют собой СДНФ полной единицы системы.
3. Произвести минимизацию совокупности единичных термов. Полученное соотношение представляет МДНФ уравнения полной единицы системы.
4. Построить сокращённую (только для единичных термов) таблицу истинности уравнения полной единицы и выписать из неё все значения входных и выходных переменных в виде частных таблиц истинности для искомых функций. Для получения наглядого решения желательно построить диаграммы Лобанова по сокращённой таблице истинности.
5. Произвести минимизацию искомых функций.

Задача 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 отношений:

1. Птицы певчие - крупные или обладающие качеством Y.
2. Птицы, не имеющие качества Y - или не крупные, или не имеют качества Х.
3. Птицы певчие в соединении с крупными объединяют всех птиц с качеством Х.
4. Каждая не-крупная птица есть или певчая, или обладающая качеством Х.
5. Между птиц с качеством Х совсем нет таких птиц с качеством 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.

g -----------========================== s ======================----------===== x ----=======-----======--------------- y ======================-----=====----- 0101 0111 1101 1111 1000 1001 1100

После минимизации получим для комплементарной логики системы уравнений:

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 положения:

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

Нулевые термы системы уравнений занесём в карту Карно, откуда получим функцию полной единицы. По полученному соотношению строим сокращённую таблицу истинности и выписываем из неё значения b и d в виде таблицы, из которой получаем логическую функцию. Из этой функции следует, что d не зависит от b, что совпадает с результатом Порецкого.

a -----------========================== b ======================----------===== c ----=======-----======--------------- d ======================-----=====----- 0101 0111 1101 1111 1000 1001 1100

По алгоритму "Селигер" получим 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_

u ----------------===================== v ----------------===================== x ------==========-----------========== y ------==========-----------==========

По алгоритму "Селигер" получим

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.

Дата добавления: 2015-05-08