Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 25
Текст из файла (страница 25)
Заключение: в зоне с ваимутам пвденяя 271-360' имеются результаты мннералиаапии рудного тела. 3) Й /, — 1000100010101010, 1-2,Э,Ь 05 /1 = Ч(0, 4, 8, 10, 12, 14) зз хгХ2ХЭха ЧУ1ХзУэУа Ч а зл,в Ч хгхзхвха Ч хгУзхэУа = хахзУэха Ч хгхзхэха = хгхра ЧУвйа 3 чение 1: э зоне с азимутом падения 0-270' имеется рудное тела. Заключение 2: в зоне с азимутам паденяя 0-270 имеются крутопада щи валю а ю е залегания. 4) Й /; — 001000100000 ОООО, а 2,2,7 Й /г = Ч(2, 6) = УгйзхэУа'Ч Угхзхэха = УтхэУа.
а з,э,т Заключение: пологие залегания иерудгюга тела имеются в ване с ааимутом палевия 0-270'. Граф логического вывода имеет виц, представленный яа рис. 2.9. 1ЗЗ Гл,2. Математическая логика 132 12.8. Конечнозначныв логики Кандое заключекне чч представляет собой коньюнкцню сукцедента. Из совместного аналнва пятя заключенна имеем обпнаь лотнческнй вывод: в воне с аанмутом паденнн 0-270' имеется крутопадаюитее залегание рудното тела. $2.8.
Конечиазиачиые логики Обобщением двузначных логик являются конечноэначные логики. Функция у(х1, х2, ..., х„), отображающая и-мерный Й-значный кортеж (о1, <ут, ..., о„), о; Е (О, 1, ..., Й вЂ” Ц, 1' = 1, 2, ..., и, во множество (О, 1, ..., Й вЂ” Ц, называется функцией Й-значной логики. Будем задавать функцию й-значной логики у(х1, х2, ... ..., х„) с помощью таблицы истинности (одномерной таблицы), число строк которой равно ЙЯ, илн двумерной таблицы, число клеток которой равно Й". Рассмотрим трехзначную функцию — функцию Вебба, заданную табл.
2.33, 2.34. .Таблица 2.33 Таблнца 2.34 функция Вебба у = х, о хь = птах(х„хь) + Цтобы й) является полной в конечнозначной логике. Таким образом, конечнозначная алгебра Вебба Ав=(М,о,), М=(1,2,,й — Ц, определяет соответствующую логику. Другими часто встречающимися й-эначными логиками являются логики, определяемые: алгеброй Поста Ап=(М,Ч, ), М=(0 1,2,,Й вЂ” Ц, где х, Ч хь = шах(х„хь) — дизьюнкция, х = х + Цапай й)— цикл; алгеброй Рассера — Тьюкетта АРт=(М,Ч,Зб,Л,1), М=(0,1,2,...,Й вЂ” Ц, где х, ьс хь = ппп (х„хь) — конъюнкция, уй — 1, х=1, У'(*) = (О, .
М;, — характеристические функции 1 = О, 1, ..., й — 1. Сигнатура любой алгебры должна быть полной, независимой и непротиворечивой. Сигнатура является полной, если любая другая формула может быть представлена в виде пропозициональной формы с помощью ее элементов. Сигнатура называется независимой, если в ней не найдется элемента, выводимого с помощью правил вывода из других элементов сигнатуры. Сигнатура непротпиворечива, если не найдется формулы Р, которая справедлива вместе с формулой У.
Конечноэначные логики являются обобщением двузначных логик. Например, логика Поста (М, Ч, ) обобщает логику Буля (М,Ч, ). При минимизации логических функций коиечнозначных логик можно использовать результаты двузначной логики — теорию ДНФ булевых функций. Для этого введем булеву переменную х', равную 1 при х = з и 0 в противном случае, х„~ 1. Будем назйвать х' б-й фазой переменной х, х = (О, 1,..., Й вЂ” Ц: (2.23) Отрицание 1-й фазы равно дпэъюнкции остальных фаз этой переменной: Ь-1 х'„= ~/ 1=О Упь Очевидно, что х Чх Ч...Чх =1. Действительно, хач (х'чх' Ч...Чх" ') =х'„чуо =1. Используя введенное высказывание х', рассмотрим минимизацию трехзначной функции Вебба, заданной табл. 2.33, 2.34: у=х охь, У =х,хьчх,хь Чх,хьч* хь Чх хь.
О О 2 1 2 2 О 2 1 Согласно законам коммутативности, идемпотентностп, ассоциативности и дистрибутивности имеем у = (х, Чх, Ч х„)хь Чхт(хоьЧхь1 Чхьт) = 1 х~~чх2 1 = х2 Чхь. 135 134 Гл.2. Матлемотвическал логика 8 2.8. Конечноэночные логики Этот же результат можно получить, сравнивая тройки коньюнкций для определения истинности выражения (2.23) после применения закона дистрибутивности (рис. 2.10), Каждая конъюнкция соатвет- ЯЯ ствует максимальному интервалу — ребру. Ответ на вопрос о том, можно ли минимизировать полученную сложность функции, получаем, строя и покрывая таблицу Квайна (табл.
2,35). Таблица 2.33 Рис. 2.10 Имеем адно покрытие л = (2 —, -2), которому соответствует минимальная ДНФ нулевой фазы трехзначной функции Вебба у =х,Чхе. Аналогично получаем минимальные формы для 1-й и 2-й фаз ФУНКЦИИ У = Х, о Хб у) = хохово, У2 = хохб) Ч х)ха) Ч х)х). Таким образом, минимизация функции тс-значной логики сводится к минимизации системы, состоящей из Й булевых функций, каждая из которых определяет соответствующую фазу этой функции. При минимизации логических функций (Я уменьшается коэффициент связности соответствующего мографа С~((Я).
Коэффициентом свлэностпи графа Я(С) называется отношение мощности сигнатуры к мощности носителя этого графа. Коэффициент связности маграфа определяется как коэффициент связности графа, полученного в результате снятия его моделизации. Неминимизнрованная функция Вебба определяется моделью вида 1 2 3 1 О 2 1 1 2 1 2 О (Хот хе~ У тт (хот хю У )т (хот Хю У 4 $ а Мограф Отм, определяемый этой моделью, изображен на рис. 2.11, а. Его коэффициент связности Я(С~~~) равен 21: де 2+6+6+4+5+5+6+4+4 1 1 Эта функция после минимизации соответствует модели )Р2 вида Ф2 —— (Мт Ятт Яз)т М ко (Х„, Х„т Х„, Хат Хат Хат У, У, У 1т Я2((х~„уо1, (х~б, У~Ц,- Мограф тк)2)У, определяемый моделью %2, изображен на рис.
2.11, б. у)(1) у'(3) ,3) кк (1,4,7) кт ка г , 4) кт(7, 8, 9 ае(3, б) уо(3, б, 7, 8, , 4, 5) у 4, 5. б) кт(3, б, 7, 8, 9) кот(2, 5, 8) кт (5, б) кат(4, 5) б Рнс. 2.11 После минимизации коэффициент связности уменьшится почти в два раза: м 2+4+4+4+3+3+2+1+1 1 (1 2 ° 9 '3. Примечание.
Па рис. 2.11 вершины, соответствующие фааам функции, ааштрихованы; вершины, соответствующие фааам аргументов, не ааштриховатшт. Хоаффидиеит свяаности графа накодится вав сумма величеств ребер, нишитентиых вершинам графа, деленная иа удвоенное число его вершин.
Рассмотрим алгоритм минимизации трехзначной функции, который естественно применим и для общего случая значения числа Й (тс — значность' логики). Пусть задана функция Дх), хт, хз) вида (О на 6,7,9,15,16,16,24, у(х), хт, хз) = ~1 на 4,3,13, 2 на 11, 20, 26; 137 2 2.8. Конечногночнме логики Гл. 2. Мотемотическол логика 136 Таблице 2.3б 22 21 х, О О (~~)) О Рис.
2.12 Твбцццв 2.37 -1- ++ хв в в остальных точках пространства (рис. 2.12) О, 1, 2, 3, 5, 10, 12, 14, 17, 19, 21, 22, 23, 25 функция не определена: 7'(х1, хз, хз) = 1. Мажорируем заданную функцию У(х1, х2, хз) с помощью вводимой таблицы отличий. Таблицей отличий называется двумерная таблица, каждой строке которой взаимно однозначно соответствует первичный терм рассматриваемой точки К-злачного пространства, в которой определена функция, принимавшая значения св = О, 1, 2, ..., К вЂ” 1, а каждому столбцу соответствует точка, в которой исследуемая функ- ция принимает значение, отличное от св, и на пересечении 1-й строки с у'-м столбцам ставится 1, если рассматриваемая точка отличается от у-й точки 1-м первичным термам.
Каждое покрытие столбцов строками порождает максимальный интервал, включающий точки а-'й фазы рассматриваемой функции и точки, в которых зта функция не определена. Этот максимальный интервал соответствует простой импликанте (Р1), мажорирующей функции У (у Э ~). В точках, где определена функция у, мажорирующая функция у принимает те же значения, что и у, Очевидно, чта таблица отличий является обобщением таблицы различий (1-й таблицы Квайна). Построим таблицы отличий (табл. 2.36) для семи точек О-й фазы заданной функции. Их покрытия порождают сокращенную ДНФ функции 1о(хг, хз, хз). Сокращенная ДНФ функции уо(х1, хз, хз), уо 1 уа, мажорируюшей О-ю фазу функции Дхд, хз, хз), имеет вид Ус (Х1, Х2~ Хз) = Хз Ч Х2 хз Ч Х1 .
хз. О О 2 1 1 2 Аналогично находим сокращенные ДНФ функций у1(х1, х2, хз) ~~(~м х2, хз) (табл 2 37, 2 38). 139 $2.8, Конечнозначные логики Гл.2. Маозезоаозичеекал логика 138 Таблица 2.38 2-2 оо хзхз -02 зз хзхз о з 2-2 оз х~гз О, 26) хо 1 , 18, 11, 20) Уо(6 7 9 15 16 1В 2 1Ы, 13) У1(4, 8, 13 Уз(11, 20, , 7, 15, 1б, 24, 8, 26) , 26) хо(б, 9, хз(7 Рис. 2.13 Т а блиц а 2.41 Таблица 240 Сокращенная ДНФ функции 71(х1, хг, хз), мажорнруюшей 1-ю фазу заданной функции 71(х), хг, хз) (у) э У1), имеет внд Ус (Х11 Хг~ ХЗ) Х2 Ч Х1 ' ХЗ' 1 1 О 2 Сокращенная ДНФ функции уг(х1, хг, хз) (уг ) уз) имеет внд (х)~ хг! Х3) — х) ' Х3 Ч хг ' Х3 Ч х) ' х3 2 1 2 О 2 2, 2 2. Покрывая нмплнкантную таблицу для мажорнрующей функцнн фазы заданной функции, получаем тупиковые ДНФ для каждой фазы (табл.
2.39-2.41 соответственно для фаз уо, у), 72). Таблица 2.39 Тупиковая ДНФ 0-й фазы функции у имеет внд Р- О 2 т ХЗЧХ2 ХЗ' Тупиковая ДНФ 1-й фазы функции У нмеет внд р =х)Чхо хг. о= г 1' З. Тупиковые ДНФ 2-й фазы заданной функции у имеют внд ,~ч) = Х) 'Х3Ч Х1 Хз = Х1 Х31 ~чг = Хг 'ХВЧХ1 Хз( 2 1. 2 2. 2 -О. 2 2 О.
г 2. 2. в табл. 2.39-2.41 К н (Р1)( — у-я констнтуента соответствующей фазы н 1-я простая нмплнканта мажорнруюшей ее функцнн соответственно. В точках неопределенной области фазы мажорнруюшей функцнн у (5 Э у) могут пересекаться, так как онн соответствуют нереализуемым ситуациям. В нашем прнмере 0-я н 1-я фазы (уо н у)) пересекаются в точках 010, 110, 210; 1-я н 2-я фазы — в точках 112 н 212. Минимизированная функция у(х), хг, хз) определяется одной нз двух систем: Д1 — — хз Ч хгхз1 Уч1 — — хг Ч Х1хз, гч1 = х1хз Ч х1хз о 21 1 1 ог 1 )г 22 нлн ~тг = хз Ч Х2Х31 )тг = Х2Ч Х)Х31 )тг = Х2Х3 Ч Х)Х3.
О О 2 1 1 1 О г 1 О 2 2 2 Рассмотрим уменьшенне коэффнцнента связности К„мографов, оцределяюшнх совершенную, сокращенную н тупиковые ДНФ заданной функцнн у(х), хг, хз). х1 1(9, 15, 16, 13, 11) Мограф (зм,(у'), определяюшнй совершенную ДНФ функции у(х), хг, хз), представлен на рнс.
2.13. Роль ндентнфнкаторов на рисунке выполняют зквнваленты соответствуюшнх трончных наборов. Коэффнцнент связности К„((зм,) равен 3, 26: м 7+9+6+6+4+9+7+6+6+6+6+7 оа ооа 2 ° 12 141 3 2.8. Конечноэначные логики Гл. 2. Маиеемаиеическал логика 140 х'(е) х1(с) Рис. 2.13 х)(ее) 1(с) фс, а) 'е( Д(а, 6 Ркс. 2.1б Рис. 2.14 Сокращенная ДНФ функции у(х1, хз, хз) определяется системой вида Д'=хоЧх2 х)Чх' х2, У1 =х'Чхо х2, с 3 2 ' 3 1 2~ с 2 1 ' 31 Уг х1 хтЧхо хзЧх2 хз — З 2'З 1'З. Произведем логическое умножение каждого выражения на ее левую часть и логически сложим эти три выражения; в результате получим мажорирующую функцию е (Х1~ Х2~ ХЗ) = ее ХЗ Ч /~ ХЗХЗ Ч тс Х)ХЭ Ч Эе Х2 Ч еэ О Ж 2 1 Л) 1 2 Ъ 1 е Ь е Ы Ч ~, х,х, 'Ч ~.х,'х,'Ч ~.х,'х,'Ч ~."х,зх,з, е 6 ее Р оцределяюшую мограф (х~ (рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
