Математическая логика. Шапорев С.Д, страница 11

Будем обозначать функции гпзп(х;, хэ ) н пщх(й,х, ) соответственно через (к ох,) и (х, о х,). Функция .т, л х, л ...л х = шзп(з;,х„....х„) называется ловьюлютней лп к-злпчлоуз логике. Тогда элементарная коньюякция будет нмегь вид У. (х,)л/ (х,)л...лу. (з„) Она отлична от пуля лишь па наборе (онпз,...,пя) и равна й-1 на этом наборе. Для функции Т(й,х„...,х,) СДНФ при 1 = 2 имеет вид (1.8 Т1 у(хнхз,...,хя)= о ~(ппп„...,п„)лх,' лхзэ л..л.т„'", где дизь- юикция берет я по всем двоичным наборам. Функции от н переменных й-эначной логики елинствснным образом представляется в виде У(х х,,х )= о Д(онпз,...,п,)г .1. (х,)л.т, (зз)л...л г, (х„)= з.

шах (ш1п(Т(п,,п,,а„) 2„(я~з',У„(х,),, г (х„))) (1 1201 з Эта фоРмУла — аналог СДНФ дла фУнкпни 1(хо.тз.....т„) в / -эна нюн логике. В литературе данное разложение пазы вас гол персов форзюи доказывается формула прямой проверкой Д(~,т,.„,х„) в формуле 11.129) разложена по системе функций (0,02,,к — 1,1с(х) 2~(х),,уя(х) ш~п(лн ьз) знак(энх,)). Поскольку это разложение справедп ива лля любой произвольной функции у(х,, х,,...,.т„). то данная система функпнй полив.

С этой полной системой связано несколько групп тождеств, которые позволяю~ перейти ш любой формулы нал ланиым множеством функций к другой зквивалеьггной ей формуле. бб Ча ь 1. Магамапачасааал пыа 74-значная логика, определяемая полной сисгемой функций )0,1,2,...,й — 1,ас(х)4,(х)...,./„(х) п11п(хпхз)рлкк(хпхз)), цюыеаегса в литературе аигебраб Рогсери -Гьюкеаа . Другими часто встречающимися й-значными логиками являются логики, опрслеляемыс следующими полными системами функций: О алгебра Пакта (0,!,...,й — 1, глад(41,хз), ), гле х = (х+!)щобй; О алгебра Вебба 40,1а..,ф — 1, ), где х, хз — — (птах(хцхз)ь1)тобй, Пример. Пуси, 1(х,у)= ( хч у)о ( уч х).

Представим зту формулу при й = 3 аналогом СДНФ в форме 11.17.9). Метод равносильнык преобразований, конурым мы полюовались в Р, здесь примснюь значительно труднее. Для этого необходимо иметь все пуждесеа в 1», связанные с системой функций (0,1,2,2с(а)2,(х)уз(г)щап(хпхз)птах(хцхз)). Воспользуемся истинностной таблицей для 7"(х у) 1табл. 1 17 12). Тибавна 1.17.11 'Д Н р ЯР «рцзлт-1ЗЯР1 — р а Я ыааатаа Э ы Руфу Ъ 1р 19141 — р аа ааая г ю (даял т.

Ллгеб логики (ллгеб змс азмзаьнй) вг СДНФУ(хтг')= ч ((проз)лУ, (т)лУ, (г)=(У(00)луо(х)л,! (у))о г г (У(ОД) л Уа (х) л У, (у)) о (У (02) л .(с (х) л У, (у)) о (! (10) л У, (х) л л у ! у)) о (У (11) л У, (х) л У, (у)) о (У (1 2) л У, (х) л У, (у)) о (Р(2 0) л У, (ь) л л Уо( у)) о (У(21) л У г (л) л У, (у)) у (! (2 2) л У, (х) л У г (у)) = (2 л У„(т) г, луо(у))о(1 лус(х)л.!ь(у))о(Олус(х)луг(у))~ (2лУ,(х)луьь(у))о у(1луь(т)луь(у))о(1 г У,(х)лУ,(у))ч (2 луг(я)лУ„()))'г(2 луг(х)г ь .1, (у)) о (2 л .1, (т) л У, (у)) Проверим, например, значение функции ьж наборе (1, 2): У(1 2) = 1 = (2 л Уь (1 ) л Усф)о (1 л .! (1) л У (2)) о (О л У (1) л У (2)) о о(2л.! (1)л.(,(2))о(1, .!(1)л.((2))о(!г .! (1)л.(г(2))о(2л Уг(1)г л ! (2))о (2 л ! (1)л ! (2)) г (2 г .! (1) .! (2)) = (2 л Ол 0) (1 лО л0)о о (О л 0 л 2) о (2 л 2 л 0) о (1 л 2 л 0) о (1 л 2 л 2) о (2 л 0 л 0) о (2 л 0 л 0) о о (2 л 0 л 2) = 0 о 0 о 0 о 0 о 0 о 1 о 0 о 0 = 1 Прн использовании формулы (1.)йо) особо отмстнм нсобходнмосьь присутствия констант 0,1,2,...,( — 1, чьжо нс было в Рг, т к, там мозьно бьыо в СДНФ оную нть козффицнсньы, псрсйдя к дижьоньгцььы по наборам, на которых У(пь,пг,,п ) ..1.

Если а разложснии У(з„,х„...,т„) использовать ларактсристичсскнс функции парного рада, то для любон функции „((й,х, ,т„) из Р, иьысз мссзо прсдстаалеиис. называемое яжорон форьюй: ! (хь,х„,...,х, ) = з (У, (т, )У, (х, ) .. !. (х„ )у (а,,о„ ,и„ ))пюой (1.17 10) Эта формула цо сгруктуре аналогична формула (1.9.1).

П й-злачной логике можно рассмотрсть вопрос о представимости функций полиномами (аналог н полицомоа Жегалкина). При этом оказывасгся, что та. «ос прсдстаалснис возможно только для простых (г. угорело ! !9 Система поднпомов по пгоб!с полив в Р, зсгдв н только тогда, когда й = Р, где Р— просюе чнсдо. Чяец 1 Магемегичеслая логвла Н теории В-значиых логик в последнее время получены значительные результаты. Они показывают существенное отличие В-значных логик от лвузначиого случа», кроме того, многие результаты зависят от значения числа К.

1.18. Практическое занятие йа 3. Минимизация в классе дизь)онктивных нормальных форм. Замкнутые классы и полнота систем функций алгебры логики. 18-значные логики 1.!8.!. Найти сокращенную, все тупиковые и минимавьные ДНФ булевой функиии г (х,у,т) двумя способами: а) методом Квайна и б) с помощью карт Карно Каким классам Поста приивллежит зта функция? !) 1(000)=.~(001)=-2(1,01)=1(1,1,!)= 1; 2) у (0,0,0) = У(1Д,1) = ~''(1,1,0) = 0: 3) Г(!00) = Г(0!))-) (О!О) = 0; 4) 1 (О 1 1) = 2' (0,1 О) = г (! 0,1 ) = Г (! 1 1) = 1; 5) У(0!1)=У(!00)ф,т(101)=1 1.18 2. Представить х Ю у в виде СДИФ и СКНФ, найти (х ю у) .

1.!8.3. Представить полиномаии Жегалкина: !) Основные логические операции. 2) хм унт. 3) хуч уяо хл. 4) х) чхутт ху" ч хух. !.!8.4. Доказать, что функция, представленная полиномом Жегалкин*, существенно зависит ог всех входящих в него переменныя. 1.18.5. Представив функцию г' полииомом, выяснить, является ли она линейной. 1) у = (х ~ у) Ю ху; 2) У = ху«хуо я; рлаш г. Алгебра лагмги !алгебра анака ы лийг 3) / = ху(х»-г у), 4) ) = (л г уд) 6 хуя, !.18.6 1.18.7 1.18.8 1. 18.9 !.! 8.10 Перечишгить все чоноташгые функции от двух цсремснны» Моя«но ли из фуикцин,г = худ г г(ху — ь т) получгпь: 1) функцию .т отогкдествлснием переменных: 2) функцию к подстановкой констмн О, 1, 3) функцию = отождестюмнием переменныьг Доказать полноту следугащи«систем функций: !)ху,х, 1.18.11.

1 18. Кй 2) х а у, х, 3) тч у. 4) л О». у, л ч у, 1; 5) » — ь у, 0 Найти числа всех линейных функций от гг псрсмснныь. Найти число линейных функций ! (холы,х„) таких, па Г(0,0г..,О)= г(1,1,...,1)=1. Выяснить, принадлюкит ли функция Г множеству Р, 1 РН !) у' = (х — ь х,)(х, -ь хз)(х, -ь х, ), з) г =»и(й,хг, »,); 3) Г= ххг», ах ха ч хг г 4) г =(Н г.т, Г»,» ел, а лгы Какие из указмшых функций являю«ел моцотаннымиу 1) х)'~ .ттч т'; 2) х — ь (х-ь у); 3) ««т»-г «'«у 4) .»ч>»-г ху; 5) лу 'г х ч .«2 гр Чвсг ! Мег магвчеслаллсп на !.!8.!3 1.18. 14 1.18.!5 1.18.10 1.

! 8.17 1 !8.18. Доказать справедливость следующик равенств: 1) -(х)= х; 2) (хч-у)=( х)ч( у); 3) пып~х, у).ь Уе (ум х) — у„, (х). у = ш!п(х у). Для заданного )г представить функцша г в первой и второй фор- мах !получения»а вырюкения упростить): 1) у =х, lг=3; 2) г'= х, )г=й; 1.18.19. 3) ~ = хо уз, й = 3. 1.18.20. Разложить в полипом по модул»о )г функцию )' из Р: 1) г'=х х, )г=5; 2) ) = шах(2х-» у, х у), й = 3.

Показать, что полные системы нз задачи ! ! 8,12 являются базисами. Доказать, что бюис не может содержат~: 1. Более пати функций. 2) Более четырех функций. Из поеной в Рз системы функций 6 выделить всевозможные базисьс 1) 6 = (О, х ю у, х — » у, ху я-» хз)1 2) 6 = (х Ю у, хуш г, хб) у Ю г Ю 1, хуЮ уз 0) хг); 3) 6=(луч хл,х,х — » у,О,хапуг~. дла фУнкпии ! (Хнх„хз)= з;х, ох,х найти все ее пРоизводные Ов том числе смешанные) да третьего порядка еключ»ггелыю Представить слелуюшие булевы функции значениями в тачке (0,0,, О) и значением всея производныя в этой же точке: !) 7(х,у,г)= хм у — » з; 2) У(х, у) = хм у — » (х я.+ у) 3) г(х,у,х)= (х -» л)(у †» з) †»(х †» у) Слава 1 Ал ебралогияи 1 гебра виска нваний) 1.19.

Схемы иэ функциональных элементов. Релейно-контактные схемы, оценка сложности схем Схемой иэ фно:чоояпмнмэ ыгнгляюв гСФО) называется орнсптнрпвачпая бсско~пззктная с ть с помеченными всрншнамн. Пусть нмееэся нскоторос устройство с и упорядоченными входами и одниьз взлхолоьз )рнс.

14). На кажный нэ вколов можсз подаваться два сипзала, «спорые можно обозначить симнолами б н 1 Очевидна. по набор сигналов на входах однозначно определяет сигнал па выходе ) акое устройство наэыиаетсн фуякпноигпьямм щемеюиоч Ясно, па каждому функлпапаяьиому элементу отав мст функция алгебры логики /(хьх„...,х„) Схема иэ фытт~онлмызы элементов полу- чается пугсм проведения следующих операций. 1. Один иэ вкопав какого-га функционального элемента сосдинясзся с аы- хо.эом другого фупкциоюиьного элемента 2. Нскоторью входы функционального элемента отождссталжатся, т с на эти входы подастся один и тот жс сигнал.

На рис 1.5 изображена допустимая схема нэ функционал ных элементов. 2 3 Р .14 Рмс. 1.5 Ясно, что фу«ьпия, которая рсэяиэусэся э.гай схемой, явллетс» супсрпозицией функций, реализусмых теми функциональнычи элементами, иэ «оэорь х эта схема построена. Схемы, полученные с помощью операций 1 — 2, ивзыаа- Ются до гусала ымн Ч сгьг.ЬЭа~ магнческаялыню Вход к функционыьггого элемента у называется фнялшеным, если при любом наборе сигначов на остальнык входах сигнал на выходе не зависит от сигнала на входе х. Функцнонаяьные элементы называются экеняаленлгнымн, если они отличаются лишь нумерацией входов и фиктивными входами.