Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров, страница 14

в. Система Хз — — (Ь, Я, Ц функционально полна, так как х=х(+)! и, следовательно, Хз сводится к Хь На свойствах этой системы остановимся более подробно. Алгебра Жегалкина и линейные функции. Алгебра над множеством логических функций с двумя бинарными операциями Ь и Я называется алгеброй Жегалхина. В алгебре Жегалкина выполняются следующие соотношения: х; у — у;Ох, (3. 25) х(у;1,'г) = ху,,'; хг; (3, 26) хЯх О; (3.27) хД+О=х, (3.28) а также соотношения булевой алгебры, относящиеся к конь- 71 юнкции и константам (3.7а), (3.8а), (3,!1а), (3.13,а,б). Отрицание и дизыонкция выражаются так: х=хЯ1; (3.29) х ~,~ у = х у = (х Я 1)(у Д+ 1) (+~ 1 =ху (+) х ( Н у. (3. 30) Если в произвольной формуле алгебры Жегалкина раскрыть скобки и произвести все возможные упрощения по соотношениям (3.27), (3.28), (3.11а), (3.13, а, б), то получится формула, имеющая вид суммы произведений, т.

е. полинома по и!од 2. Такая формула называется лолиномогг ,л(егалнина для данной функции. От булевой формулы всегда можно перейти к формуле алгебры Жегалкина и, следовательно, полиному Жегалкииа, используя равенства (3.29) и (3.30), а также равенство, вытекающее из (3.30): если !з1г —— О, то ~!Юг=1!(+гг.

Оно, в частности, позволяет заменять знак дизыонкции знаком~+) в случае, когда исходная формула — СДНФ, Пример 3 6. а. (хз~(хг) (хг~/х!хз) = (х хг (т~~хЯхг)Ь Ь(хгхгхз(+х!хз®хг) = хз(хг;81)хз®х!хгхз®хгхз(рх!ХгхзД+ О+х! (хЯ1) =хзх,хз гох!хг®х!, б хзхг~„/хзхз — хзхг!т.хзхз х! (хг(+)1) ~~+!(х!Я1) !йхз =х!хг(+~х!хз®х! (+~хз; в. хзхг~/х!хг=хзхгЯ(хз(+)1) (хг(+)1) =х!Д+хг(тг1. Теорема 3.6. Для всякой логической функции существует полинам Жегалкина, и притом единственный.

Существование полинома уже доказано. Для доказательства единственности покажем, что между множеством всех функций от и переменных и множеством всех полиномов Жегалкина от и переменных существует взаимно однозначное соответствие, Число различных членов (т. е. конъюнкций переменных) полнномов от л переменных равно числу всех подмножеств из и элементов, т. е. 2" (пустому подмножеству соответствует член 1). Число различных полиномов, которые можно образовать из этих конъюнкций, равно числу всех подмножеств множества копъюнкгз ций, т. е.

2' (пустому подмножеству коныопкций соответствует полином О), Таким образом, число всех полиномов Жегалкнна от и переменных равно числу всех функций от и переменных. Так как разным функциям соответствуют разные полииомы (одна н та же формула не может представлять две разные функции), то тем самым между множествами функций и полиномов от и переменных устаиов- 72 Важным примером замкнутого класса является класс монотонных функций, к рассмот. рению которого мы сейчас переходим. В гл. 1 (пример 1.14, б) рассматривалось отношение частичного порядка ( на множестве векторов одинаковой длины.

Напомним, что для двух векторов о=(о~, ..., о„) и т= 1~ !э Х! Х2 Хз о о о о о о ! о о о о о о ! 1 1 о о о о ! 1 о о о ! ! = (ть ..., т;) о(т, если и только если о;(т, для всех !=1, ..., и. Здесь воспользуемся этим отношением для двоичных векторов. Функция 1 (хь ..., х,) называется монотонной, если для любых двоичных наборов о и т длины и из того, что а(т, следует, что ! (о) (~ (т) . Пример 3.8. а. Константы О, 1 и функция х монотонны. Отрицание х немонотонно. б. Дизъюнкция и конъюнкция любого числа переменных являются монотонными функциями. Рассмотрим две функции от трех переменных, заданные лено взаимно однозначное соответствие, что и доказывает единственность полинома для каждой функции, П Функция, у которой полином Жегалкина имеет вид Ха;х,'+у, где иь т равны 0 или 1, называется линейной. Все функции от одной переменной линейны. Линейными функциями от двух переменных являются сумма по гпоб 2 и эквивалентность.

Замкнутые классы. Монотонные функции, Множество М логических функций называется замкнутым классом, если любая суперпозиция функций из М снова принадлежит М. Всякая система Х логических функций порождает некоторый замкнутый класс, а именно класс, состоящий из всех функций, которые можно получить суперпозициями из Х. Такой класс называется замыканием Х и обозначается [Е], Очевидно, что если М вЂ” замкнутый класс, то [М)=М, а если М вЂ” функционально полная система, то [М)=Рм Пример 3.7. а.

Множество всех дизъюнкций, т. е. функций вида х!'!ух,'~/...!/х,, является замкнутым классом. б. Множество всех линейных функций является замкнутым классом, так как подстановка формул вида Ха;х,(-[ду в формулу такого же вида снова дает формулу того же вида. Таблица 8,6 табл. З.б. ФУнкциЯ (г немонотоннаЯ, так как 001(101, а (001) ) (1О1), ФУнкциЯ )з монотонна (пРовеРкУ пРедставляем читателю).

Проверка монотонности функции непосредственно по определению требует анализа таблицы функции и может оказаться довольно громоздким делом. Поэтому весьма полезной для опознавания монотонности является следующая теорема, Теорема 3,7. Всякая булеза формула, ие содержащая отрицаний, представляет монотонную функцию, отличную от О и !; и наоборот, для любой монотонной функции, отличной от О и 1, найдется представляющая ее булеза формула без отрицаний.

Доказательство, 1. Пусть дана булеза формула беэ отрицаний. Применим к ней процедуру пряведення к ДНФ. Так как соотношения (3.15) и (ЗЛ6), приводящие к константам, в формулах без отрицаний неприменимы, то получим невырождепную (отличную от О' и 1) ДНФ Р, также не содержащую отрицаний. Пусть на наборе и =(аь,,п ) х(п)=1, Тогда г" содержит конъюнкцию (без отрицаний!) х! ...х! =1, равную 1 иа этом наборе. Следовательно, и! —— ...=ог„=1.

Рассмотрим любой набор т, больший, чем о. В нем обязательно т! —— „. тгь — — 1, поэтому хг, ..., хг„обратится в 1 и Р(т) =1. Таким образом, условие монотонности для с" выполнено и функция 1, представляемая ДНФ Г (а значит, и исходной формулой), монотонна. При этом (ФО, так как в невыражденной ДНФ для любой конъюнкции найдется набор, обращающий ее в 1; 1Ф1, так как на нулевом наборе (О, О, ..., 0) Р О.

2, Пусть функция 1 монотонна и отлична от 1 и О. Тогда она имеет невырожденную ДНФ и, следовательно, иевырожденные импликанты. Предположим, что какой-либо импликант 1 содержит отрицание над переменной и имеет вид хгй (е — элементарная конъюнкция). На любом наборе о, в котором а,-о н который обращаетйв!,1(а) 1. Рассмотрим набор о', полученный из о заменой пг на !. Так как и')и, то по условию монотонности 1(а') =1, Кроме того, о' обращает в 1 коньюикцию х~А, которая, следовательно, является импликантом 1. Но если хф и х,й — импликанты 1, то й — также нмпликант 1 (это следует из определения импликанта и закона склеивания (3.18)) и, следовательно, х;й не янляется простым импликавтом, Таким образом, простым импликантом монотонной функции 1 может быть только конъюнкция, не со.

держащая отрицаний. Дизъюнкцня всех простых импликантов 1 (сокращенная ДНФ) н дает исномую булеву формулу без отрицаний для 1. П Более подробное изучение импликантов монотонной функции дает о следующую картину их строения, Выделим нз Мг множество М! всех минимальных наборов 1а минимален в Мг, если из т<о следует, что тбеМг). Каждому минимальному набору и соответствует простой импликант, являющийся коньюнкцией всех тех переменных, которым в а соответствуют единицы; и наоборот, каждому простому нмпликаиту 1 соответствует 1аналогичным образом) минимальный набор в'Мг. Например, для функции )з на табл. З.б Мо=(010, 10Ц, поэтому сокращенная ДНФ )х имеет внд хзХ/х,хь Следствие.

Сокращеьщая ДНФ монотонной функции является ее минимальной ДНФ. Действительно, поскольку в сокращенной ДНФ нет отрицаний, для любых двух нмпликантов й~ и йз найдется переменная, содержащаяся в йь но не в йь и переменная, содержащаяся в йь но ие в йь Если положить переменные из Ц равными 1, а остальные переменные — О, то получим набор о, который все импликанты, кроме йь обращает в О.

Поэтому о покрывается только импликантом йь который не может быть удален нз сокращенной ДНФ. Следовательно, сокращенная ДНФ— единственная тупиковая, а значит, и минимальная ДНФ монотонной функции. 13 Теорема 3.8. Множество всех монотонных функций является замкнутым классом. Эта теорема непосредственно следует из теоремы 3,7 и того очевидного обстоятельства, что подстановка формул без отрицаний в формулу без отрицаний снова дает формулу без отрицаний. Следствие. Класс монотонных функций является замыканием системы функций (а, 'ьг, О, 1). Это утверждение вытекает из того, что всякая булева формула без отрицаний является суперпозицией дизъюнкций и конъюнкций. П Две теоремы о фукциональной полноте.

Теперь можно перейти к основной проблеме этого параграфа: каковы необходимые и достаточные условия функциональной полноты для произвольной системы функций ХР Как отмечалось в начале параграфа, система Х полна, если дизъюнкция, конъюнкция и отрицание являются суперпозициями функций из Х. Поэтому будем искать свойства функций, позволяющие выразить через них булевы операции. Лемма 1 10 немоиотониых функциях). Если функция ~(хь ..., х„) немонотониа, то подстановкой констант из нее можно получить отрицание. Точнее: существует такая подстановка и — 1 константы, что функция оставшейся одной переменной является отрицанием.