Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Топ:
Генеалогическое древо Султанов Османской империи: Османские правители, вначале, будучи еще бейлербеями Анатолии, женились на дочерях византийских императоров...
Эволюция кровеносной системы позвоночных животных: Биологическая эволюция – необратимый процесс исторического развития живой природы...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Интересное:
Берегоукрепление оползневых склонов: На прибрежных склонах основной причиной развития оползневых процессов является подмыв водами рек естественных склонов...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Национальное богатство страны и его составляющие: для оценки элементов национального богатства используются...
Дисциплины:
2023-01-16 | 33 |
5.00
из
|
Заказать работу |
|
|
На основе метода, заложенного в алгоритме "Селигер", можно вывести соотношения для операций, обратных конъюнкции и дизъюнкции. Поскольку эти операции часто называются соответственно логическими умножением и сложением, то логично обратным операциям присвоить имена логического деления и логического вычитания. Впервые формулы для логического частного и логической разности для троичной логики получены Н.П.Брусенцовым[5].
Если логическое уравнение вида 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) и провести её минимизацию.
Пример 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.
xy z v00 0 001 0 110 0 111 1 1 xz y=z/x00 i01 j10 011 1 xv y=v-x00 001 110 j11 iВ соответствии с п.3 алгоритма "Селигер-С" проведём минимизацию искомых функций в трёхзначной и комплементарной логиках.
Для комплементарной логики получим:
|
Для трёхзначной логики уравнения имеют вид:
у = 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П) Порецкого[35,стр,376]. Кстати, заодно и проверим это правило:
(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.Оказывается, что алгебра логики не разрешает нам этакие вольности
По алгоритму "Селигер":
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 --==---- a ---==--=b ---===--c --==----d -===---- d -===----Подтвердим корректность метода на решении более прозрачной задачи.
Пример 6
Дана система логических уравнений:x = yu = 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.
Отыскание обратных функций.
Используя алгоритм "Селигер" или "Селигер-С", можно получить полную систему обратных функций для двоичной логики. В таблице приведена полная система функций двоичной логики.
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 101 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 110 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 111 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 y10 y11 y12 y13 y14 y1500 I i i i 0 0 0 0 1 1 1 1 j j j j01 J j j j 1 1 1 1 0 0 0 0 i i i i10 I 0 1 j i 0 1 j i 0 1 j i 0 1 j11 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' - импликация. Из этого выражения легко просматривается физический смысл импликации: из истинности x следует истинность y.
Решая 1-ю задачу Порецкого, мы заметили аналогию между рекурсивным вхождением функции и комплементарным значением i. Резонно предположить, что такая аналогия существует между комплементарным j и рекурсивным значением инверсии функции. Проверим это предположение на полученных одноаргументных функциях и убедимся в их обратимости с помощью формулы эквивалентности.
|
После обращения были получены все 16 прямых функций от двух аргументов без какого-либо искажения. Это подтверждает правильность всех алгоритмов решения логических уравнений и корректность комплементарной логики.
Заключение
1. Простота метода, заложенного в алгоритме "Селигер", позволяет решать логические уравнения от большого числа переменных.
2. Минимизация функций в 3-значной и комплементарной логиках для двоичных аргументов несущественно отличается от традиционных методов двузначной логики.
3. Парные термы для равносильных преобразований определяются набором термов, полученных на основе применения формулы эквивалентности к исходному логическому уравнению.
4. Применение метода при выводе обратных логических функций показало, что однозначное решение для двоичных аргументов может быть получено лишь в комплементарной логике.
5. Впервые получены все 16 обратных логических функций для двух аргументов.
6. Комплементарная логика при аппаратной реализации позволяет значительно упростить решение проблемы самодиагностирования вычислительной техники: например появление j на любом выходе может свидетельствовать о сбое или отказе.
|
|
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!