Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 15
Текст из файла (страница 15)
Доказательство. Пусть 1 немонотонна. Тогда су- ществуют наборы о и т, такие, что п<т, 1(п) =1, )'(т) =О. Если о и т отличаются й компонентами, то в этих компонентах в о стоят нули, а в т единицы. Беря набор о и заменяя эти компоненты по одному единицами, получаем це. почку п(ээ'(ээ'(...<эээ-'(т, в которой любые два набора, стоящие рядом, отличаются только в одной компоненте (такие наборы называются соседними). Ясно, что в такой' цепочке найдутся два соседних набора го~, ы~+', таких, что 1(а~) =1, 1(ы'"') =О. Пусть они отличаются в 1-й компоненте; тогда в( =О, вг+' =1, остальные их компоненты одинаковь).
Подставим эти значения остальных компонент в 1. Получим функцию )(гэ(, ..., <о( ь хь ь',~ы ..., ы,') от хп обозначим ее п(х,). Но д(0) =д(ээ';) =1(а1) =1; д(1) = =й(зэке ) =1(ы~+~) =0; следовательно, д(х,) =хь П Лемма 2 (о нелинейных функциях). Если функция 1(хь ..., х,) нелинейна, то с помощью подстановки констант и использования отрицаний из нее можно получить дизьюнкцию и конъюнкцию. Точнее, существует представление дизъюнкции и конъюнкции в виде суперпозиции констант, отрицаний и функции ).
До к а за тельство. Пусть ? нелннейна. Тогда ее полипом Жегалкипа содержит конъюнкции переменных. Выберем самую короткую из них К=х; х; ...х,„. Положим х~ —— =...=х, =1, а для всех хь не входящих в К, х;=О. Подстановка этих констант в полипом обратит К в хпхп, а остальные конъюнкции в О, и 1 примет вид хьхп~®ахи(+) Яйхп®у, где а, б, у — коэффициенты, равные 0 или 1 и зависящие от' конкретной функции 1. Функции, получающиеся при всех восьми возможных комбинациях значений а, 9, у, приведены в табл. 3.?, в которой для наглядности обозначено хп — — х, х;,=у, а отрицание в последнем столбце обозначено через М, Поскольку каждая из функций ?;(х, у) (1=0, 1, ..., 7) — результат подстановки констант в 1, то последний столбец табл. 3.7 содержит искомое представление дизъюнкции или конъюнкции в виде суперпозицин отрицаний, констант и исходной функции ?, Для перехода от полученного представления к представлению двойственной функции (от конъюнкции к дизъюнкцин и наоборот) дополнительно потребуются только отрицания (по закону де Моргана).
П ПРимеР 3.9. ((х„хм хм х4) =-х~хэх4Д+ х~хэхэх4(Н хк'-.,хэ. Полагаем х4=1, хэ=О. Тогда 1(хь О, хм 1) =х~хэ(+дг+'1, 76 Табанил 3.7 Эквивалентная булева формула Искомая суперпозиция Вид полинома ху ху ху ху=хт/у Ку ху=х /у х~/у х'/У что соответствует строке (з в табл. 3.7, Отсюда получаем х!'т/хз=/(х!, О, хз, 1); х1хз=х!1/хз=((хь О, хзв 1), Замечание. При традиционных обозначениях переменных в выражениях вида 1(хь хв, х,, х,), где перелвенные расположены в естественном порядке индексов, индексы играют двоякую роль: оии именуют переменные и нумеруют места в функции.
Эти роли следует различать. В примере 3,9 существенны именно места в функпии (первое и третье); с помощью той же функции можно получить дизъюнкцию не только хв их„но и любых другах переменных. Например, хвт/хв=)(хв, О, х„1)', ут/х 1(!70,з,!). Укаэанное различие хорошо видно при схемной реализации функций; функция от и аргументов реализуется схемой с и входами; номера мест — зто номера (или имена) входов схемы, а имена переменных — это имена внешних сигналов (датчиков, выходов других схем и т.
д,), подаваемых на входы схемы. Две доказанные леммы позволяют получить все булевы операции с помощью немонотонных функций, нелинейных функций н констант. Это еще не функциональная полнота в обычном смысле, так как константы с самого начала предполагались данными. Однако такое предположение часто бывает оправданным в 'различных приложениях и прежде всего в синтезе логических схем (см, гл, 8), где системе логических функций соответствует набор (серия) типовых логических элементов, а полнота системы означает возможность реализовать с помощью элементов данной схемы любые логические функции.
При схемной реали- 77 гв /т /х (з /в /в 1в (т 0 0 0 0 0 1 0 1 0 О 1 ! 1 0 0 1 0 1 1 1 0 1 1 ! ° ху хуе! хуеу хуеуе! ху Е х ху е х е 1 ху е х е у ху Ех ЕУЕ1 ху=/в(х, У) ху=йг ((т (х, у)) ху=/ (Ф (х), у) хт/у=:)в [х, Ж (у)) ху=/в (х, !У [у)) х~/У=/в (йг (х), У) х'/У==(в (х, У) у М (/7 (т у)) зации констаыты О и 1 специальных элементов не требуют. Поэтому имеет смысл ввести ослабленное понятие функциональной полноты: система функций Х называется функционально полной в слабом слнысле, если любая логическая функция может быть представлена формулой над системой Х() (О, !), т, е.
является суперпозицией констант и функций из Х. Очевидно, что из обычной полноты системы следует ее слабая полнота. Теорема 3.9 (первая теорема о функциональной полноте). Для того чтобы система функций Х была функционально полной в слабом смысле, необходимо и достаточно, чтобы она содержала хотя бы одну немонотонную и хотя бы одну нелинейную функцию. Н е о б х о д и м о с т ь. Классы монотонных и линейных функций замкнуты и содержат О и 1. Поэтому если Х не содержит ыемоыотонных или нелинейных функций, то их нельзя получить с помощью суперпозиций функций из Х и констант. Достаточыость. Пусть Х содержит немонотонную и нелинейную функцию. Тогда по лемме 1 подстановкой констант из моыотонной функции получаем отрицание, а затем по лемме 2 из нелинейной функции с помощью отрицаний и констант получаем дизъюнкцию и конъюнкцию.
П Пример 3.10. а. Система Ха=(а, Я)) функционально полна в слабом смысле, так как конъюнкция нелинейна, а сумма по гпод2 немонотонна, Константа О получается из соотношения (3.27), однако константу 1 с помощью коньюнкции и суммы по гпод2 получить нельзя, поэтому Ха не ' является функционально полной системой в обычном (сильном) смысле. Использование константы 1, которое разрешается определением слабой полноты, сводит Ха к полной в сильном смысле системе Ха (см. пример 3.5, в).
б. В функционально полной системе Ха единственная функция — штрих Шеффера — одновременно нелинейна и немонотонна. в. Проверим на слабую функциональную полноту систему Х,, состоящую из одной функции )ь заданной табл. 3.6. Немонотонность (~ уже установлена. Получим ее полипом Жегалкина: х1 хз ха ~у х1 хз ха ~/ х1 хз ха ~/ х1 х ха — — (х я !)(х я !)х (+) Ь(х~Ж !) хэхзО+х1(хз(Э !Нхат !)9 Зх1х,х. = х,х,О+х,С+ха. Следовательно, )! нелинейна и Ет — функционально полная в слабом смысле система. Для формулировки необходимых и достаточных условий сильной полноты рассмотрим еще три замкнутых класса. Функция !(х„..., х ) называется сохраияюи(ей О, если ! (О, О, ..., 0) =О.
Функция 1(х„..., х„) называется сохраняюп(ей 1, если 1(1, 1, ..., 1) =1. Оба класса функций, сохраняющих 0 и сохраняющих 1, являются замкнутыми, что проверяется подстановкой констант в суперпозиции. Напомним, что функция является самодвойственной, если )(Х1,, х.) =((Х1, ..., х„). Класс самодвойственных функций замкнут. Его замкнутость доказывается прямой выкладкой. (Чтобы избежать громоздких обозначений, далее она проводится не в самом общем виде; обобщение очевидно.) Пусть 11 (х,, ..., х„), )2(х„, х,+ь ..., х„иь) — самодвойственные функции.
Подставим 12 в 1! вместо х,. Получим й!(Х1, ..., х„, хи+1, ..., хи+2) !2! (х1,, хл 1, )2(хи, ..., Хи+2)) ° Тогда в силу самодвойственности 1! и )2 3(х1, ..., х„, х 21, ... Хи+И) =!1(Х1, ..., Хи-!, !2(Хл, -., Хи+2)) =!1(Х1, „., Хл-1л ! !2(Хи, „и Хи+2)) =!1(Х1, -., Хл — 1, !2(хи, ..., Хи+2)) ~й!(Х1, ..., Хии-и), т. е, и является самодвойственной. Теорема 3.10 (вторая — основная теорема о функциональной полноте). Для того чтобы система функций Х была функционально полной (в сильном смысле), необходимо и достаточно, чтобы она содержала: 1) нелинейную функцию; 2) немонотонную функцию; 3) несамодвойственную функцию; 4) функцию, не сохраняющую 0; 5) функцию, не сохраняющую 1, Необходимость следует из замкнутости пяти классов, упомянутых в условии теоремы.
При доказательстве достаточности отметим следующее. Леммы 1 и 2 используют константы. Поэтому сначала нужно получить константы (из условий 3.5 теоремы) и только потом можно воспользоваться теоремой 3.9. Прежде всего отметим, что если г(х1, ..., хл) несамодвойственна, то подстановкой в нее х и х можно получить константу. Действительно, ввиду,несамодвойственности 1 найдется набор (а1,..., о,), такой, что )(о1,..., о ) =1(о1,..., о„). но тогда функция 1,(х) =г(х'1, ..., х' ) является константой, так как (л(0) )(0~1, ..., 0"') =)(о1, ..., а„) =)(а1, „.
... о ) =((1~~, ..., 1 ") =),(1). Пусть теперь 12 не сохраняет О, )! не сохраняет 1, 12 не- самодвойственна ()ь, )ь (з не обязаны быть различными). Если ~ь(1, ..., 1) =1, то функция ф(х) =гь(х, ..., х) есть константа 1, так как ~р(0) =1 по определению гь и ~р(1) = =1о(1, ..., 1) =1, а функция ф(х) =1,(~р(х), ..., ~р(х)) = =11(1, ..., 1)=0, т. е. Ч (х) есть константа О. Если же )о(1, ..., 1) =О, то <р(х) =х, так как р(0) =1 по определению Го и ф(1) =1ь(1, .", 1) =О. Но тогда из 16 подстановкой х и х получим функцию ),(х), являющуюся константой, а используя еще раз х, получим вторую константу. Итак, в любом случае выполнения условий (3.5) достаточно для получения констант О, 1.
Используя этот факт и теорему 3.9, получаем теорему 3.10. гз ал. язык лОГики прндикдтОВ Предикаты. Предикатом Р(х,, х„) называется функция Р: М -ь.В, где М вЂ” произвольное множество, а В— двоичное множество, определенное в начале $ 3.1. Иначе говоря, и-местный предикат, определенный на М, — это двузначная функция от и аргументов, принимающих значения в произвольном множестве Л1. М называется предметной областью предиката, а хь ..., х„— предметными переменными, В принципе ничто не мешает определить предикат в более общем виде как функцию Р: МХМтХ...Х̄— В, т.
е, разрешить разным аргументам принимать значения из разных мнолсеств. Иногда это оказывается удобным; однако, как правило, в логике предикатов исходят из первого определения. Для любых М и и существует взаимно однозначное соответствие между и-местными отношениями и а-местными предикатами на Л(: а) каждому и-местному отношению )с соответствует предикат Р, такой, что Р(аь . а„) =1, если и только если (а„..., а„)~В; б) всякий предикат Р(хь ... ..., х„) определяет отношение )г', такое, что (ап ..., а„) ейВ, если и только если.
Р(аь ..., а,) =1. При этом Р задает область истинности предиката Р, Всякой функции 1: М" — ~М молсно поставить в соответствие (а+1)-местный предикат Р, такой, что Р(аь л а„, а„„,) =1, если и только если ((аь „., а,) =а„+,.
Поскольку функция должна быть однозначной, то это соответствие требует, чтобы для любого а„ч, Фа„+, Р(аь ..., а„, а„+~) =О. Поэтому обратное соответствие 1от (и+1)-местного предиката к а.местной функции1 возможно не всегда, а только при выполнении указанного условия. 80 Отступление 3.1. С логической точки зрения двоичные объекты, которые рассматривались в предыдущих параграфах,— это высказыванвя, которые могут быть истинными илн ложными. формулы — зто составные высказывания, истинность которых определяется истинностью входящих з них элементарных высказываний (обозначаемых буквами) и логическими операциями над элементарными высказываниями, причем сами операции (такие, как отрицание, ковъюнкция, импликацня и т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
