XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 69
Текст из файла (страница 69)
Тогда она представляется некоторым полиномом Жегалкина третьей степени, общий вид которого дает формула (6.19). Наша задача — найти такие значения коэффициентов этого полинома, при которых он представляет функцию 1. Ясно, что значение функции у на наборе 000 равно коэффициенту йв в формуле (6.19). Но, согласно заданному вектору значений, оно равно 1. Следовательно, йв = 1.
Далее, У(0,0,1) =аз9йо =йз91=1, откуда, решая уравнение относительно аз в иоле Ег, получим аз=О; У(0 1 О) = йг 9 1 = О т.е. йг = 1; у(1,0,0) =й191= 1, и й1 = О. Чтобы найти коэффициенты й1г, аьз и йгз, нужно рассмотреть значения функции на наборах 110, 101 и 011 соответственно. Так, для первого набора получим ,~(1, 1, 0) = йггх1 хг 9 й1х1 9 йгхг 9 йв = =агг9йг9йв = йгг9191=агг б.7. Теорема Посте (сумма по модулю 2 любого четного числа равных слагаемых равна 0).
Поскольку в то же время Д1,1,0) = 1, то аш = 1. Аналогично У(1,0,1) =а13 Щао =О, откуда а1з = 1; У(0,1,1) =агз Щаг Щао = О, и, так как аг = ав = 1, агз = О. Наконец, 3 (1~ 1~ 1) = п123 Щ а12 Щ а13 Щ а2 Щ ав = а123 = 1. Итак, 3 = Х1Х2ХЗ Щ Х1Х2 Щ Х1ХЗ Щ Х2 Щ 1.
Как видно из примера 6.18, суть метода неопределенных коэффициентов состоит в следующем. Записывая полипом Жегалкина сначала в общем виде, с неопределенными коэффициентами, мы выражаем значение полинома на фиксированных наборах через коэффициенты и приравниваем его заданному значению функции. Начинаем с нулевого набора и находим коэффициент ав, равный значению заданной функции на нулевом каборе. Зная его, из рассмотрения значений фукнции на наборах, содержащих в точности одну единицу, находим коэффициенты а; при „одиночных" переменных (коэффициенты „линейной части" полинома).
Зная их, из рассмотрения значений функции на наборах, содержащих в точности две единицы, находим коэффициенты при конъюнкциях двух переменных и т д. При этом вьшолюпотся вычисления и решаютсл простейшие линейные уравнения в поле вычетов по модулю 2. Пример 6.19. а. Рассмотрим множество Щ, состоящее вз единственной функции (ппприха Шеффера).
Полнота этого множества следует из легко проверяемых тождеств х р=(х)р))(х~у), х=(х~х). 434 б. БУЛЕВЫ ФУНКЦИИ б. Полнота множества (Ц, единственным элементом которого является стпрелка Пирса, проверяется аналогично. Теперь мы сформулируем и докажем критерий (необходимое и достаточное условие) полноты для произвольного множества булевых функций.
Для этого нам потребуется сначала рассмотреть некоторые специальные множества функций. Определение 6.8. Функцию у называют функцией, сохраняющей констпантпу 0 (соответственно константпу 1), если у (0) = 0 (соответственно: у (1) = 1), где 0 — нулевой, а 1— единичный наборы значений переменных функиии у. Например,махсоритпарная функиил являетсл функцией, сохраняющей и константу О, и константу 1. Отрицание не сохраняет ни О, ни 1, а эквиваленптностпь сохраняет 1, но не сохраняет О. Множество всех функций, сохраняющих константу 0 (константу 1), обозначается То (соответственно Т1).
Наборы а и а из булава куба В" = (О, 11" (для произвольного фиксированного и) будем называть вэаилтно противополоэкными, говоря при этом также, что набор а есть инверсия (или отприцание) набора а (в силу единственности дополнения любого элемента булевой алгебры набор а будет, очевидно, инверсией набора а). Определение 6.9. Функцию д Е Рз,„называют двойстпвенной к утункции,т е Рэ,„, если для всякого а Е (О, Ц (и ) 0) имеет место д(а) = У(Нт). Полагаем также, что константа 0 является двойственной к константе 1 и наоборот.
Пример 6.20. а. Стрелка Пирса есть функция, двойственная к штриху Шеффера, так как х ). у = х Ч у = х у = х~ у. 6.7. Теорема Поста б. Сумма по модулю 2 двойственна к зквивалеишиосеви, так х у=я9у=я®у. Эти две функции являются и отрицанием друг друга, но неверно в общем случае, что функция д, будучи отрицанием функции ~, двойственна к у: штрих Шеффера не есть функция, двойственная к конъюнкции, а стрелка Пирса не есть функция, двойственная к дизъюнкции, но конъюнкция двойственна к днзъюнкции и наоборот, а стрелка Пирса двойственна к штриху Шеффера и наоборот. В общем случае в силу уже упомянутого свойства единственности дополнения в булевой алгебре функция Ь, двойственная к функции д, которая двойственна к у, равна у.
Определение 6.10. Функцию у Е Рз,„называют самодвобстпееиио4, если она двойственна к себе самой, т.е. (Ча Е (О, 11")(у (а) = у (се)), С~ ~10,1ГППа) =Уй)) Таким образом, функция самодвойственна тогда и только тогда, когда на взаимно противоположньпс наборах она принимает взаимно противоположные значения. Следовательно, для того чтобы убедиться в несамодвойственности заданной функции у, достаточно найти хотя бы одну пару взаимно противоположных наборов а и а, таких, что значения функции на них совпадают, т.е.
у(се) = У(а). Так, мажоритарная функция является самодвойственной, а эквивалентность — нет, поскольку приа=(0, 0) 0 0=1и1 1=1. Множество всех самодвойственных функций (при всех и > 1) обозначим Я. Определение 6.11. Функцию у Е Рз„называют момотпокиой, если для любых наборов се,,в Е В", таких, что а ( ~3, имеет место У(ст) ( ПР). 436 б. БУДЕВЫ ФУНКЦИИ Другими словами, функция монотонна тогда и только тогда, когда для любого набора се имеет место следующее свойство: если значение функции на наборе се равно 1, то оно равно 1 и на всех наборах, строго больиеих (по отношению булева порядка на В") набора а. Любой минимальныб (относительно того же порядка) набор се, для которого значение у(се) монотонной функции у равно 1, называют нижней единицей функции у. Очевидно, что вектор эначениб монотонной булевой функции полностью определяется множеством ее нижних единиц'.
Мажоритарнвл функция монотонна, и множество ее нижних единиц есть (011, 101, 110). Штрих Шеффера — не. монотонная функция, так как 00 < 11, но 0~0 = 1, а Ц1 = О. Множество всех монотонных функций принято обозначать через М. Определение 6.12. Функцию у Е Рз,к называют ликебкоб, если она может быть представлена полиномом Жегалкина первой степени от п переменных, т.е. формулой вида (6.20).
Множество всех линейных функций принято обозначать через Ь. Любая булева константа и любая проектирующая функция х являются линейными функциями. Такова, разумеется, сумма по модулю 2. Отрицание также линейно, ибо х = х 9 1. Коньюнкция и дизъюнкция не являются линейными функциями, так как не могут быть представлены полиномом Жегалкина первой степени (см. теорему 6.4). Определение 6.13. Множества функций То, Тм Я, М, Ь называются классами Поста.
Замечание 6.9. Каждый класс Поста состоит из функций с соответствующим свойством для любого числа переменных. 'Нетрудно понять, что множество нижних единиц монотонной функции 7 есть множество всех минимальных элементов множества Су — консеяк- 1 еоуект единицы функции у. 437 6.7. Теорема Поста Можно доказать также, что если функция у принадлежит какому-то классу Поста С, то и любая функция, равная функции ~, принадлежит этому же классу. Другими словами, добавление или удаление фиктивных переменных не выводит за пределы любого из классов Поста. Полезно еще заметить, что любая проектирующая функция х принадлежит одновременно всем пяти классам Поста.
Действительно, если 1 (х) = х, то ~(0) = 0 и Д1) = 1, т.е. )' Е Тв П Ть Отсюда же вытекает и самодвойственность функции х. Монотонность следует из того, что 0 < 1 и у(0) = 0 < ~(1) = 1. Линейность очевидна. В то же время существуют функции, не принадлежащие ни одному из классов Поста.
Таков, например, штрих Шеффера. Все свойства, кроме нелинейности, следуют прямо из таблицы этой функции. Нелинейность же доказывается выводом поли- нома Жегалкина для штриха Шеффера: хну=я у=х ° у91, что не есть полипом Жегалкина первой степени. Фундаментальным свойством каждого класса Поста является его эамкнутаость (в смысле определения 6.3). Это означает для любого из классов Поста С, что всякая суперпозиция над С снова есть элемент С. Теорема 6.5.
Каждый класс Поста замкнут. ~ Нужно для каждого класса Поста С Е 1Тв, Тм Я, М, Ь) доказать, что замыкание [С) мноэхествва булевых функиий С совпадает с С. Пусть |(дм...,д„) — какая-то суперпозиция над С. Обозначим ее через ~р. Без ограничения общности можно считать, что все функции ~, д1, ..., д„Е Рз,„(для некоторого п). Рассуждаем, используя индукцию по определению суперпозиции. Если для каждого 1 = 1, п функция д; = х,, где х;— переменное, то у =,1(хм...,х„) Е С. Предположим, что в суперпоэиции у все функции д; есть элементы класса Поста С 438 6. БУЛЕВЫ ФУНКЦИИ (в частности, зто может быть и соответствующая проектирующая функция, которал ввиду замечания 6.9 принадлежит всем классам Поста). Докажем, что и <р = у(дм...,д„) е С. 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
