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

! 6 1) )с раз при фиксации переменных х„,х,,х, по порядку !порядок фиксации переменных не существенен) ПРаизааднан )с-га ваРлдка от бУлевой фУнкции У (Д,хз,...,~,) по псРемсиным х,,х, „х, называется выражение, равное сумме по модулю числа 2 всех пронзводнык первого порядка, вторых, третьих,..., )с-к смешанных производных при фикщции переменных хч хч,..., хд .' Главе т Акебра л гпкн 1апгебра вн казнпанпй) бб Рассмотрззм пример Пусть 1(х,у)= (ху — у т)~ 4Пз'-~ у). Очевилно, что /(х у) = (гр и т)л ( ту л у~ и (ху а х)л су = — (ха у) л ху и " хху а хту и ху .

— =1 убСО у=у. — =л 1йдс О=.с, д2' ду дх ' ду Тогда — = — ~ — 1=1О0=1, ' = — йг — Ю вЂ” -= у63хш1= д-"Х а уд(~ д'у д( д( д'( дхду ду~ дт) ' д(х,у) дх ду дхду = уйх= ~~ ля)а(ул.с)мху азу,т. к хгду = с т-у ум и (с л у) а (х л у) а х = х 40! ((хнхз,,т„)п 'У',а,п, х, т, х, = рейзену',х, 6 ~,рм 4; т, Э..<3 ( --3 Чна н'г Е ~ (,, хх, ...х, В...Ю (з п«тз хбп, П.1б42 4 злг'з,,ч ! з тле ае — — 1;.

ал = э';, н т л. Уо згь * Х *Лг, а (04 Паслеловатсльно пролифферснпируем полинам Жсгалкина ог функпии У(я,хз,,,,,х'„) по переменным х„х„...,х, и пайпем значения всеь проюволнмк в точке (О, О,, О). При этом поскаяьку полиномы Жсгалкина состоят яз опночлснов, в которые всс переменныс входят не выше, чсч в первой сте- 1( ° пени, то — ь, х, 1 = ,х, Кроме того, па свойству пронзвопной Практичсокое ишюльзованпс введенные паня~на праизволныя ог булевых функпий насолят при проектировании и расчете лаги~вских схем персюноча- тельных устройшв, а именно условия переключения различных каналов та- ких схем зависят от значений производных от булевых функпий.

Выражение 41.14.1) лля мнашчгчмм Жегалкнна Озастный случай (1.14.20 мозкно более подробно раснисать в слелуюглем виде. Часы |. Ыагемллм игал лсглю — = — Ю вЂ”. Тогда после дифференцирования получаем д(7Еб) д7 дб д» дх д» Д2. г —, 2,1'=12,...,л, г Ф 1 на зтом наборе авиле д'( д" 1 дх,дх ' 'дх,дх ...дхл дтУ! «'(хпх„,х„) = 1'(0,0,...,0)гп~ ~~ л х, то ~ л ,ыд:,((к, „',,~,ах,(ф, „ д") Ч 226 ГЗ" Хсыжг д" 7 — ЛХ,Х, ..Х . д ,д ,...дх„ „, „ (1,!6.5) Это разлгокение аналогично разложенмо в ряд Маклорена для функции и переменных. Для получения разложения булевой функции в ряд, аналогичный рялу Тейлора на наборе (п„п,,,.,пл), воспользуемся параллельным переносом начала координат.

г Пусть х, =х,йпы х =х Юпз,..., х„=х„юа„. Тогда точка (онпз,,п„) в системе «сординат щ,х,...,х„будет соответствовать точке (О,О,,О) всистеме Л,х;,...,х. Действительно, после дифференцирования по переменным х,хз,...,х все члены в разложении (1.16.4) до 1,2 х.

обращаются в нуль, а в результате подстановки хсы = хгчз = ., = х„= 0 остальные члены зтого РазложениЯ, кРоме 7,2 з, также будут равны нулю. Тогда из (1.16.4) после несложных преобразований получаем следующую теорему. Теогжма 1.17. Люба» булева фуикнни г (х„х,...,х„) представимо сваны ду значением на наборе (0,0,...,0) н значениями всех производных — , дх,' уплел Г. Длг б л логики (алгебре вы к зыввикл/ разложим булаву функцию /(д,хз,...,х„,) по фармуае (1165) в точке (0,0... О) ы замеынм каждую переменную ~г на х, !но,; получим формулу н теорему о разложении бужаой функции /(й,х„...,х,) на проызвольнам наборе (оооз,...,о„).

Теорема ! /б Любан булев» функции /(~, х„...,х„) пр«дставнма своим значением на наборе (о,,о„...,о„) и значепиизгп вест своих произнод. д/ д'Т д-/ иык — ', —,.-, ', !,/=12,...п. !и,/, иа это» наборе дх, дхдх, дз,дхз дх„ ы виде „Г(хох„...,х) = /(она„...,а„)Ю~ — л (х, Юо )Ю д/~ ,, д;~(.. Й ~ — л(л; Во,)(т, Жо,)Ю... дт г" ,, ддд, о'Т дх,дх, ...дх„( о 2 (1 16.6) рассмотрилг асс этапы получения рапюигспиа по формуле (! 165) лля конкретной булевой фупкнии г"(х,у, )=(лу — !ух) — э((л — э у) — э(э +у)).

упргютим эту формулу: /'(х у х) = лу г ух ч ( хч у ч ч з ) и /(ху л > г/ч ((т л у/ г э г г/ —= и/(аул~о й//гхчу «)/ихуу хухчх туч энхч)' гх. Получим еиачзле прсдстзеление этой функции полиномом Жсгалкина /(ху, ) = хо уча и хлулх =(хЮ1)(у|31) З1= =(худ уюхЫ1)эю(=хух(йуэЮхгОхЮ1. 'Мсгь !. аьяммагичесюя лсгняе Найдем теперь все необходимые производные: аг" — =1ч у чхВОч уч с = !В у ч т = ум я= ус ах То жс самос получается иг дифференцирования самого полинома Жегалкина — = утВОЮхВОВО=усВт=я(уВ1)=ту.Дммсанатогично: ау сх -=- ау ау 'ае — =хч!чсЮхчОчл =1Вхчт =тол=хе, — = хч у ч1Вхч учО= — а'у а!ау'!- =хч уВ1=хч у =ху; — = — — =1 лЮО.я= с; ' ахау ау( а. ) = " а'у а ! ау1 а а а,( а.

! = —,— 1=! уВО у=у; а У г1 (а Г'1 !ВО-! а.а,а, а ~ а.а, ) а у аГау1 — — — =1.хВО х=х; ауа а.~ ау) ' дг"( ' д'у" у'(х,х„кт) — у"(О О 0)В ~ л х В «~ — л хх Ю ,, а,,)й,ф,.м,а,а; !с с,ь) , т, е. ау В ох,х,х, ах,ах,ах, „„ у (х, у, г) = к ч у ч я = 1В ~ух)! л к Ю (хл)! л у Ю (х»)~ л ллВЦ удхуВ(у)( лхгВ(х)( л у!В!(!о„„!лхул= =!ВОВОВ1 !ЮОЮ1 ляВ1 у!В1 хул = = 1 В л Ю хл В у- В дупл Тогда формула !!.16.5) для данной булевой функции от трех персмениьгл бу- дет иметь вид Глав» \ Ллгев а логики ыл едра вы и зиваииа 1.17. Й-значные логики рассмотрешжя в прелылушия разделал лвузиачная логика допускает сбоб. жение на й-зна шый саучви, >!рп эгам лоти в й-зиа шыл логикак сокрацяются многие слойствв л результаты двузначной логики, ысш иабл|оласмые факты и явления обнаруживают принципиазшнос отличие ог рассьзозре~лгой алгебры логики.

Мно~ие решенные задачи двузначной логики ие яме~от тако. го исчерпывающего решения в Г -значной логике, а иные и вовсе не решены, Функция / (т„лы...,л;, ) называется фушлиев Гг-згглчггои лгл гггггг, осли ее аргументы определены на множестве (О,й 2, ., I — 1), сосшяшсм нз /г злелзентов, а сама ф> нкция нринимаез значения гы того зкс мнозксства. Множество всех функцин йг-значиой логики обозначается через Рг О ювидно, что функция /(л, хз,...,к, ) полностью определена, если задана ее нстиинсстная таблица хзабл й >У >>.

Зевелев Гну./ аз ззсь Част Г. Магемлпмесква лялям Так «ак число lг-злачных наборов длины л равно й', то числа функции от л переменныхв lг-значнойлогике Р, равной Из скюанного ясна, что в Р, в значительной степени возрастают трудности по сравнению с Р„даже в возмоагнссти перебора функций. Например, если з' с функцийстдвухпеременныхв Рз всего !б,тоужев Рз их 3 =3 =19683. Число стран в испгнностной таблице, равное й", тоже растет очень быстро. Например, при lг = и = 3 таблица имеет следующий вид (табл. !.

!7.23 тел и !.гг,г В Р,, как и я Р,, вводятся поилки» существенной и несущественной !фиктивной!переменнойй, понятие равенства и суперпозиции функций. тазов 1. Длгвб злоп кн !алгеб вмскззмзюмя) бг рассмотрим примеры некоторых конкретных функций ю Рс, которые мощно считать элементарными. 1. х = (х о 1)гообй — отрицание Носта. Н,173) х в этой функции предсщвляет собой обобщение отрицания з смысле "циклического" сдвигз значений.

Например, ира й = 3 для х=(тз-1)щоб3 будем имщь следующую заблицу истинности (табл 1.17.3). Таблвцв 1,174 Таблице 1.! 7.5 2. х= йгх=)с — 1 — х Н.)7.2) Это другое обобщение отрицания з смысле "зсрказьнога" отобрюкення значений. Эта функння носит название оогроцоггол Л)касезочо . Дл» й = 3 таблица истинности этой функции оривелена з табл. !.174. 3. з, (х ) = !1.17.3) О, х и г, (г = О, 1, 2,..., !. — 1).

Эта функция называется,гараюлкрисгночсщоб фткцоей ошорого родо числа 1 и обобнзает некоторые свойства отрицания Гели 8 = 3, то 2,х= 1, з, (х) =, а таблица истинности нрсдссггвясна в табл. 1.17 5 (О,х кг',(г =0,1,2) гаг,ю го!.17,5 Яндг зб878.!З5ф — к и е з ю зс»к Часть! амтематическаялс ияа 4.

1,(т)= О, к М 1, (1 = 0 1 2,..., )с — 1) (1.17.4) (характеристичсска» функция перваке рода зцачсни» 1). пзсп(х! хз ), (!.17.5) (первое обобщение конъюнкции). 5. (х, хз)тпосУс (1.17.6) Таблсана 1.17.7 Тибллие1Л7б 6, щах(х„х,) (обобщение дизъюнкции) (см. табл. 107.8). 7. (х, +~)лоб)с (сумма по модулюй)(см, табл, 1.!7 Р). 0,0<к<у<8 †, 8. Усеченная разнося~ х -, у = (х — у, О<» 6х<)с — 1. (1.17.7) (1.17.8) (произведение по модулю к и второе обобщенно конъюнкции).

Таблицы истинности дла стих функций приведены в табл. 1.17.6 и 1.!7.7 (!с = 3) Тлела 1. Ал бра лосили 7елтебре выскакиваний! бд 0-1, 0<к<у<1 — 1, р. Импликация х — Ь у = (1 — 1) — к+у, 0< у <к бус — 1 1 = 3 операция нмпликации 2,0<х<у<2, х -ь у = , а ес таблица (2 — э в у, 0 < у < х < 2 а табл. 1.17.10.

При имеет вцд истинности дана Таллина !.178 Тарлицв1.179 Тлелвив 1.17 !б 10 Функция Всбба (так(х, т)е!)юоб1 . х-у,о«у< .01-1, 11. Ратность по модулю уи х — у = (б — (у — х) 0<к < у <1 — !. Чяспс Ыяюмяпю сявялслгяя х-у, 0<у<х<2, При й=3 получим х — у=, Таблица истин- (3 — !у — х) О <х< у< 2. ности этой операции приведена в табл. 1.17.11.

тяялиця 1.!У.П Из этого списка фуккций вилно, что элементарные функции алгебры логики имеют при й и 3 по несколько аняяошв, кюкдый из которых обобщает соответствующее свойство функции. Функции гпш, шах, +, . !или ) обладают свойствами воммутативнасти и ассоциативности: х, хэ = хэ х,; 1. х, +ха =ха+ай 2.

(х, хт).ха =я, (х хэ); (х, я- хэ ) т хэ = х, + (хз + хз ) Кроме того, справедливы следующие соотношения: 1. (х, ьхт) хз — — (х, хэ)+(хт хэ) — дистрибутивность умноягени» относительно слояюния. 2. шах(пнп(х;, хэ) х, ) = пцп(птах(й, х, ) шах(х„х, )) — дистРибУгвв- ность операции шах относи»яльно операции шгп. 3. пцц(шах(х, х,) х,) = шая(гп!п(х„х, !'; пни(х„х )) — диотрибупяв- ность операции гпш относительно операции шах. 4.

шах(х, х) = х, ппп(х, х)= х — идемпстеитность операций тп!п и шах. ппп( х, х,)= шах(~,х,) 5., '... — аналоги правил лс Моргана. шах! х, х,)= ш!п(х„хэ) раааа 1. Длгеб лсгнкн 1влшб я е я энв ьнд1 ~ 0, х = 0, 1й — х, .те 0. ФУнкциа 1(хз,х„...,.т„)н Д назывгмтса сУвпесггзеелногу, если она сУщсстаенна зависит не менее чем от двух переменных и принимает всс 1 значений из множества (О, 1, 2,,к — 1) Сбобщим теперь понятие совершенной дизьюнктивнай пормалгшогз формы иа й-значный случай. Это можно сделать не единственным образом.