Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 27
Текст из файла (страница 27)
Теория трасс Выше было рассмотрено применение математической логики в экспертных системах при геологоразведке полезных ископаемых. Рассмотрим ее использование при оценке переходных процессов в электронных системах, реализующих субмнкронную технологию, т. е. в системах, рабочая частота которых — сотни мегагерц и выше. В этом случае ложная информация порождаетсн неодновременными переключенинми входных каналов из-за задержек сигналов в каналах связи. Рассмотрим интегральную схему (ИС) (рис.
2.17,а), реапизуюшую булеву функцию (рис. 2.17, б) Дхг, хю хз, хз)~1 — — Ч(0, 1, 2, 5, 12, 15), 12.10. Теория аярасс 147 Гл. 2. Матаемаояическал логика 146 и интервал У = [О, 15), который соответствует переключениям входных каналов Х(11) -+ Х(12) для 0 — ) 15 (рис. 2.18). Последовательность переключений входных каналов (хз, хз, хе, х1) обеспечивает смену входных векторов 0 -+ 4 -+ 6 -+ 7 -+ 15; е хя «я) 1О ° у(х) 1 а С)У(я) -о Рис, 2.17 значения выходного канала У(х) при этом следующие: У(0) = = У(15) = 1, У(4) = у(6) = У(7) = О. Следовательно, в интервале [11, 12) имеем ложный О, Определим, в общем случае все условия возникновения ложной информации в ИС, используя теорию трасс [16] и логику предикатов. Трассой Т(х„хя) булевой функции У(Х) называется цепь интервала,У(Х, Хе).
Если е(Х,) — минимальный элемент, соответствующий вектору Х, интервала,7, е(хе) — максимальный элемент, соответствующий вектору Хе интервала,У: (Че(х() 6' У) ((е(Х ) < е(Х;)) зс (е(Х;) < е(хь))), У(Х,) = У(хь), У(х;) = У(Х,), 4 ф а, Ь. В рассмотренном примере цель (О, 4, 6, 7, 15) является трассой т (о, 15). Выбор цепи переключения носит статистический характер. Очевидно, что количество трасс Т((Х, Хь) удовлетворяет неравенству ~(т((х., х,)Ц < н(х., х,)., где Н(Х, Хе) — расстояние ло Хеммингу между точками Х„Х). Интервал [О, 15) рассматриваемой функции содержит шесть трасс: Т1(0, 15) (-) е(0) < е(4) < < е(6) < е(7) < е(15), Тт(0, 15) ++ е(0) < е(4) < < е(6) < е(14) < е(15), з т (О, 15) (0) < (8) < < е(9) < е(11) < е(15), 'Т4(0, 15) ++ е(0) < е(8) < < е(9) < е(13) < е(15), у Та(0, 15) ++ е(0) < е(8) < < е(10) < е(11) < е(15), Та(0, 15) ++ е(0) < е(8) < О б 15 < е(10) < е(14) < е(15), 4 т из 24 цепей, соединяющих точки Рис.
2.1З 0 и 15. Максимальная длина трассы в пространстве размерности я равна диаметру соответствующего гиперкуба, т. е. числу я. Минимальная длина трассы в пространстве той же размерности равна 2. В рассматриваемом случае трассами длины 2 являются: т(0, 5) ++ е(0) < е(4) < е(5); 12.10. Теория трасс 149 Гл. 2. Математическая логика 148 к о(0) < и(4) < о(12), Т(0, 12) "" и(0) < и(8) < и(12); Т(4, 13) яя и(4) < и(5) < о(13), и о(4) < о(12) < о(13); Т(8, 13) ьь и(8) < о(12) < о(13); Т(8, 14) 4~ и(8) < и(12) < о(14); Т(5, 15) е и(5) < и(7) < и(15), и и(5) < и(13) < о(15); Т(12, 15) к.
и(12) < и(13) < и(15), ~' и(12) < и(14) < и(15). Распределение трасс в булевом пространстве определяет качество переходного процесса: чем больше трасс, тем больше возможность порождения ложной информации (количественная оценка будет рассмотрена в гл. 5); чем больше расстояние по Хеммингу между концами трассы, тем больше длитепьность сигнала ложной ин- формации. Введем функцию В(х„, х „..., х„) риска сбоя (т. е.
ложной информации): 1, если возможна ложная информация хотя бы на одной (хя» хяя» . Хая) = из К! цепей са(хь>, хь,..., хь,), 0 в противном случае, где х„, х„, .. и х„— переменные интервала (Х„, Хд1, изменяю- щие свое значение на противоположное: Х„3сХд =Хт, х>м ф Х.„, 1 =1, 2,..., к. Условие порождения трассы определяет формула д1>~ В(хя» Хяя> .", Хяя) = ,3с д(Ха» Хая» ..
Хая) 3с Уса(хь» хья, ..., хь,) Е с;(х;» х>г» ... х;я)/ / ду дзу (11, 42, ..., ьь) = репо (а„а2, ..., аь), ~ —,, ес,, Й '(1д(хь1) д(хь„ хь ) дь-1яе д(хь„хь„хь,) ' ' ' д(хь„хь„, хья > )>> ) / где: дьу/д(х„, х„, ..., х„) — производная от булевой функции у" по переменным х „ х„, ..., х,„ единичное значение которой указывает на изменейие значения функции у при одновременном изменении значений переменных хап х„, ..., х я,.
репи (а1, а2, ..., аь) — результат перестановки (реппиФа11оп) индексов а1, а2,..., аь, переменные хь„хь„..., хь„попарно не равны друг другу (8(хь„ хь„..., хь,)) и являются злементами множества переменных (х,пх„,...,х „). Вычислим функцию риска сбоя при переключении каналов Х1, Х2 для ИС (см. рнс. 2.17, а): д2У дУ д У дУ = — >и 9— д(хп Х2) дх дх дх дх2' ,1 (х1 х2> хз> х4) х1,хзх4 Ч хьхзх4 Ч х1хтхзхе Ч х1хтхзх4> — = у(х1 — — 1) >24 у (х1 = 0), дУ дх1 ДХ1 = 1) = Х2ХзХ4 Ч Х2Хзхе, 24(Х1 = 0) = Х2Х4 Ч ХзХ4. После тождественных преобразований получаем ду дУ вЂ” = Хтхе Ч хтх4 Ч хз> — — — ~(х2 = 1) 9 ~(х2 — 0), Х1 дх2 у(Х2 = 1) = Хьхзх4Ч хгхзх4Ч хгхзх4> ДХ2 = 0) =Хьхе Ч хгхзх4.
Имеем ду х1х4 Ч хзх4 Ч хгхзх4 > дх2 дту дг у дг1 = (хзх4 Ч хзх4) >х> хь = хз. дхьдх2 дх1 ~,дх2,/ Отсюда д2 = (хтх4 Ч хтх4 Ч хз) й> хз >2> (хгх4 Ч хзх4 Ч хгхзх4). д(х1, х2) В результате тождественных преобразований получаем дтпл = Ч(1, 2, 3, 5, 9, 13, 14, 15), д(х1, х2) ~ дт,у = Ч(0, 4, 6, 7, 8, 10, 11, 12). (Х1, Х2) 1 Гл.
2. Машематичсскал логика 12.11, Задачи и унралснениэ 150 151 Согласно формуле (2.24) дгэг — й д(хг, хг) хгхгхЗхе Ч хгхгхЗхе Ч хгхгхйхзЧ дхг Ч хгхгхзхе Ч хгхгхзхе Ч хгхгхзхе, (2.25) дгу' дУ ос — хгхгхЗхе Ч хгхгхЗхе Ч хгхгхЗхеЧ д(хг, хг) дхг Ч хгхгхзхз Ч хгхгхзхз Ч хгхгхзх4. (2.26) При переключении входных каналов хг, хг в ИС (см. рис. 2.17) согласно (2.25) и (2.26) имеем 6 трасс (рис.
2.19): 4, Рнс, 2.19 В 2.11. Задачи и унралгиеиия 3" 3.1. Доказать, что число всех булевых функций от и аргументов равно 2 й й. Записать в совершенных ДНФ и КНФ булеву функцию р = у (хи хз, хз), приннмаюшую анапские 1 на наборах с номерами 3, 4, 7. 3.3. Записать в ДНФ и КНФ булеву функцию р = у(хм хз, хз, хе), принимаюшую аначение 0 иа наборах с номерамн 2, 6, 7, 8, 11, 12.
ЗА. Проверить справеллнвосгь равенства х = ххь Ф 1. 3.5. Проверить справедливость слепуюших равенств: ХГИЗ аз ХГ ЧХЗ, Х1 -З ХЗ = Х1 ЧХЗ, Х1~ХЗ = ХГЗСИЗ. если раньше переключается канал хг, то трассы о(0) < и(8) < е(12), о(4) < о(12) < 0(8), и(7) < о(15) < о(11); если раньше переключается канал хг, то трассы о(0) < о(4) < о(12), о(4) < е(0) < (8), о(6) < 0(2) < о(10). Теория трасс позволяет вычислить распределение трасс в булевом пространстве, определяющее объективные причины порождения ложной информации в ИС, З.б.
Показать, что числа булевых функций, существенно эавнсяших от и аргументов, опрелеляется рекурреитным соотношением А„=2 — ) (;) ° А,, ~ э гле А, — число булевых функций, эааисяших от з аргументов. 3.7. Булеза функция у, зввисяшзя от трех аргументов, называется махсора- заарноб, если имеет место равенство у = хзхе Ч х1хз Ч хзхз. Бувем обозначать зту оперению анаком зк н зэюгсыаать хгурхзурхз. Доказать, что имеви место следующие соотношения: 1) Х1?рхгурхз = хг; 2) хзурнгурхз = хз; 3) х1урхзурхз = И!Яхзурхз. 3.8. Найти минимальную ДНФ фунвпии р = У(хм хз, хз, хэ), принимаю- игей значение 1 на наборах О, 1, 2, 5, 6, 7, 8, 12, 13.
3.9. Найти миннмальную ДНФ функции у = у(хз, хз, хз, хе, хз), при- ишэаюшей значение 1 иа наборах с номерами от 0 ло 7, от 11 ло 21 н от 26 ло 31. 3.10. Функция р ю у (хи хз, хз) равна 1 нв наборах 1, 3, 4 и не опрелеленз нв наборе с номером 5. Найти ее минимальную ДНФ. 3.11. Рааработать тест расаоэиэваная противоречивого запаяна неопреле- лвиной булевой функции у(хм хз,..., хэ) (функция задана ароазиеоречиео, если (ВХ)(у(Х) = О, 1)). 3.13. Йвйти минимальную ДНФ булевой функции Г 1 нэ 01-0-, 001-0, -010-, у (хг хэ~ ~ хз) '1 О иа 110 1 000 1 1001 3.13.
Опрелелить скобочную форму булевой функции Г 1 иа -0-100, 100 — 01, -01- — — 1, у(хм хз' '''хе) 1 0 на 110-0-, 011 — -О, 00 — 1 — 1. 3,14. Найти мошность елниичной области неопределенной булевой функции у(хг, хз, ..., Хэ) после ее лоапрелеления; Г 1 нв 001-1, 01-01 -1011-, г(хг *" ' ") = (О ООО1-,' НЮ-1,'11-011.' 3.15. Проверить линейность булевой функции Г(хи хз, хэ)!г = Ч(0, 1, 5, 6). 3.16. Установить, является ли самоввойствениой функция эквивалентности.
3.17. Проверить монотонность конъюнкции от и аргументов. 3.13. Привести пример монотонной функции, которая олиовременно была бы лннейной. 3.13. Привести пример самалвойственной функции, которая олновременио была бы линейной. 3.30. Привести пример линейной и монотонной функций. 3.31. Убелиться, что функции Шеффера и Вебба ие являются нн линейными, ни монотонными, ни самодвойстаеннымн. 3.33. Установить, образует ли булеза фуиэиия у(хг, хз, хэ, хе)П = Ч(0, 3, 7, 11, 13) базис в Рз.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
