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

Уизряма 1.!Ц Каждан функция из Р, может быть вырюкеиа при помогли ввцниома но модулзо 2 (полмгюма Жегалкина), Клаас функций 6 нщывается фу квиоигмыю зам ггулгьгзг если вмесщ с функциями из этого класса он содержит а все их супсрпозиции. Иэункциа- нально замкнутыми классами являются кчасс всех булсвыч функций Р, класс, содержащий только тохгдесгеенные функции вида Г(х)= л, класс фунюзиб от одной перемеиноб, т. к, все суперпозицин над функциями из этих классов не выводит результат из соответствующих классоь. функционально замкнутые классы, отлн тнью от пустого класса и от сова- цупности всех функциИ нлгебры логики, называются ссбсмееильыцг функ- цвоммьяо зликлулгыми классиии.

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

е. функции, щя которых ! (1, 1,..., 1) =! . К этому классу ла Чясп 1. Мягемагишт ялопм приналлежат функции 1, х, х, л х, х, ч хэ, напротив, функции 0 и х нс входят в Р, Докаэательатво замкнутости этого класса анвлогично предыдущему 3. Обозначим через Я класа всех самодвойатаенных функций, т.

е. функций 3 и Р, щя коэорьш 3 = / Докажем, что класс о юмкнуг. Для само- двойственной функции имеет место тождество У*(хэ*хэ - х,)= 13хэ,хэ,-,т„)= 1(х,,х„.,х„). для доказательстве замкнУгости поккксм, что гР= Ф(умУэ,..., Уе)п 5, если б,~„, г" и С Найдем Ф =Ф*Ы *Л - Х,,)=ФЫ Л- Г )=Ф(А Уэ,...,Х„,) Этот жс результат следует и из теоремы 1.5. 4. Функция Р(хг,хэ,...,.г„) называется линейкой, если 3(хпхэ,...,х„)=иеФа,хгш...шаля„, где а, ц 30, 1). Класс линейньш функций обозначается через Е. Он, оч»- видно, содержит константы О н 1, тождественную функцию х, функции х,х, Юхэ. Фу~кики х, лхз Ях, чхэ й 1..

Класс линейных функций Е функционально замкнут. Если 1', =а,Фа х Ю...Юа„х„п Ь и Р =Ь ЮЬх Ю...ЮЬчхч б Е, то Это очевидно, если вспомнить, что хш я=0, х х=х, ОЮх= х. Переименование переменных также не выводит из Е. 5. Поаледний класс наиболес важных замкнупях булевых функций — иона- тонные. Введем отношения чаатичного порядка на наборах переменных х„х„....х.

Для лвух наборов и = (амцэ,...,пе) и 33 = ((3мОэ,...,33„) выполнено отношение предпгсствования ц<(3,если а, <Онпз <Оэ,,п„ВЬе. Например, (О, 1,0,1)<(1,1,0,1). Оценки (0,1,0,1) и (1,1,0,1) нюываются сраелцнылги, а оценки (0,1,0,1) и (1,0,1,1) — яесраелмныма Введенное отношение и или ц есть отношение частичного порядка. Функция э (х„хз,...,х„) называется мономаллой, если для любых двух н»- боров а и 33 таких, чю пб)3, имеет место неравенство э (п)< э (33). Клаш й г з У,ДЛ Вела ястихк(ЕЛ Енса аи Яаа ВВННЛ) лг зотоиных функций обозначается через М. Очевидззо, что ьзонотонными фуи,щиямибулугй,!, х, т, лхэ н т, г т. Функция д -ох, не монотонна. , ю (О,О)н(),О), - ((О,О)= )(),О)= О.

П зщлгем, что класс монотонныь функций замкнут. 1ьчя установления звмк. щсщ класса М достаточно показать, что функция фмф(б,Д„...,У",„)б М, если ф,Я, (ы.,,, (;„н М . Пусть =(х„,,ха з,, тат ) — наборы цсременньщ функций гр Ун гт,, У„, соответственна, причем множество переменных функнии ф состоит из тех и щщько тех псреиенных, которые встречаююя у функций Д, )э,..., у„, Пусть н ц р — два набора переменных .т.

причем он(3. Эггз два набора апредс-о) -о) — (э) -(2) — ( ) — ( ) -р) — (2) лают наборы п,О,а,б,...,п,О переменных х,х,,х -(О -О) — (3) -(з) — ( ) причемтакис,что ц ч0, п «О,,п бО ФУнкции г(ь~„Уз.....й'„йм,тс Д~п )< г(О '("")"('"'1 '("")й'(" Ъ вЂ”. ~х( "ИР1-4а'"'М=ИР"'1У.(р"'1-4Р'"Ъ сзщу монотонности (по условию) функции ф получим: Ч(У(н ) уэ((п ~...,У„,~а ~) <б~ Д(О ~, ф3 ~,..., «,„(О ))), т с. Ф=о((),ую.... (;„)н М )йгщсы Рь, Ры 5. Е и М неполные и попарно раж нчные, т. к мохгно привести примеры булевых функции, нс прннадлщкащнх ни одному нз этих клвс«яза и примеры функций, принадлежащих олному из любых двух классов. но нс згринщлежа~ззих другому Но оказывается, что для проверки полноты систсньз ны булевых функций можно ограничиться рассмотренными пятью функщщнально замкнутыми классаьпз.

т'ео аоммл! (5 (меореа а ууослга* о фщнзощочщьлон иолнонге) дл» тщо чтобы система бУлевы* фУикцнй (У;,Уз,..., (;„) бьщ» полной, необходимо Часть». Маюмагичеемм лопни и достаточно, чтобы оив целиком ие содержалась нл в одном нз пати замкиутыл классов Рь,Р»,Я,Т. н М. Для проверки, выполняются ли дпя некоторой системы функций ( т», 2»,..., ул) условия теоремы Посте, можно составлять таблицы, которые назывмотся юоблвцами Псе»вл. Рассмотрим следующий пример: доказать полноту системы функций «ЮуЮПлу,0,1.

Таблица Поста будет иметь следующий вид !табл. 1.15.П. теЬлне Д РД! В клетка« втой таблицы пишется знак 'Ч" илн "-" в зависимости от того, принадлежит рассматриваемая функция заданному функционально юмкнутому классу или нет. Дпя полноты системы функций необходимо и достаточно, чтобы в каждом столбце был котя бы олин минус. 1. У,(х у х)= хЮ уЮ«. У» — функция, сохранвющая нуль, ибо ОЮОЮО = О, аналогично она сохраняет единицу 1Ю1Ю!=1.

Найдем двойственную ей функцию г" = у» (х, у т) = (х Ю 1) Ю (у Ю 1) Ю ( Ю 1) Ю 1 = = х Ю у Ю «Ю 1 Ю 1Ю 1 Ю 1 = х Ю у Ю т, т. е. У» ц Я. Очевидна, что у',— лииейная функция. Осталось проверить ее иа монотонность. Выберем два набора значений переменныл (0,1, 0) и (О, 1,1), т' (0,1,0)=1> Д(0,1,1)=0. Итак, у» й М. 2. г' (х,у)= ху. Проверим цри»»ад«емкость,у» к каждому из пяти классов функций. 0 0 = О, Л ц Ро, 1 1 = 1, У» и Р,, /» = У» !х у) = хо у — х т у, т. е.

у» — несамодвойственная функция 1 не линейна, т. к. содержит произведение перемеины«ху. Наконец, т»е М, потому что имеется семь сравнимы« наборов значений переменных: (0,0)Ч(0,0), Тлене г. Алгебра ломки !алгебра вн к зияли л) (О,О)л(),О), (О,О)к(ОО), (),О)к(1,!), (О,))к(1,!), (О,О) (1,1) „ (1, 1)н (1, !). Очевидно, чта лля любого из них 1з (ц) < Тт йз). 3. )з = О и у, = 1 проверяются злсментарл. Собственный функционально замкнутый класс называется лреалалиын, если ан не содермгится ли в наком функционэлыю замкнутом классе, отличгзоьз от аамого себ» и ат класса всех функпий алгебры логики. Итак,~юной-то класс функций К называется ггредэоэггьоч 1нли макьтагольггым), если К вЂ” непал. ный,адла любой Тб Рз и Тй К, клаас Кы()") — полный. Из опРеде.гения следует, по прелполный «ласс является замкнутым. В алгебре логики существуют галька пять предполньж клэссов, а именно Ро,рп5,1.

и 11 Система функций 0 = ( Ти Тт,..., 1«) называетс» иезаеисниаб, если никекаа функция Т системы С не представима суперпозициэми функций из 01(Р,) Независимая система функций С называюс» базисои замки)того класса К, если яснкая функция из К вать суперпозиция функций из С Таким образам. система функций 0 из замкнутою класса К называется его базнсоы, соли она полна в К, а всяка» ее ссбственна» подсиюема ие аыяеюн полной в К. Теареиа 1 1б. Каждый замкнутый класс из Рт имеет конечный базис.

1.16. Производные от булевых функций В дискретной математике и математической логике атс)тствует понятие предела, однако используется термин «роизэоджм Это связано с разложением бУлевой функции в рял, аныюгнчный ряду Маклорена э тачке 1на наборе) (О,оо,.,о) или ряд Тейлора в произвольной тачкерна произвольном наборе). Т)роиыодиог) первого порядки — от булевой функции у(т, т„,х)) по ау а', переменной К называется — = Р(хр хт,..., х , 1, ха„.

, хл ) Ю ,Г(л, х,. .. х,, О, х,,,.,., хе), 11.!б.1) ат Ча и 1. Ывгсмапс мс вя ломив не где с (хах„.,х, п),хч,...,х„) — единичнав остаточная функция, у 1д, хз,...,хи,О, хи, . „х„) — нулевая остаточная функция, 9 — операция суммирования по молулю два. ду' Производнав первого порядка — от булевой функции /(~,х„...,х„) опд, ределяет условгщ, при которых эта функция изменяет значение при переклю- чении переменной х..

дг Пмсщаннай ирошссдгсай от булевой функции „С )л), х„...,х„) назсявасюя вырюксние вида Эс). д Э'чХ (1.1б 2) Эхе Эхч ...Эхч дхч Эха дхб ...Эхч, д'у Эу ~ ~ Э'.Р ЭУ гт, гьэгг д'~ д,д;...Эх, ' (!.!б.З) гле суммирование под знаком суммы а этой и последующих формулах, посвященных производным аг булевых функиий, производиюв также по модулю два. Производная (с-го порядка опредсллст уо.ювия, при которых функция Д)х,,хз,...,т„) изменЯет значение пРи одновРеменном изменении значений переменных хч,х,,...,хс Эту производную вычисляют, применяя соотношение (1.