Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
Теорема 6. Каждая функция из Р2 может быть вылзажена при помощи полинома по mod 2 {полинома Жегалкина).
Подсчитаем число полиномов Жегалкина от переменных жь ..., хп, т. е. число выражений вида
(ix М
Число членов равно количеству подмножеств
(ii, . . ., is) из п чисел (1, п), т. е. 2”. Поскольку
аН — равно 0 или 1, искомое число полиномов равно 22П, т. е. числу всех булевых функций от тех же переменных. Отсюда, как следствие, получаем единственность представления функций посредством полиномов Жегалкина.
Пример 12. Выразить Xi V хг в виде полинома Жегалкина.
Ищем выражение для xt V х2 в виде полинома с неопределенными коэффициентами:
V хг = aXiXz + Ъх 1 4* схг + d.
При Xi = х2 — 0 имеем 0 = d,
ири Xi = 0, x2= i имеем 1 ~ с,
при Xi — 1, хг “ 0 имеем 1 = Ь,
при х{ ~ хг = 1 имеем 1 = а 4- Ь + с, т. е. а — 1.
Мы получаем ж, V хг = х^хг + ад 4- хг.
Из приведенных примеров видно, что существует целый ряд полных систем. Каждая из них может быть принята за множество элементарных функций. Таким образом, для задания булевых функций можно использовать различные языки формул. Какой именно из языков является более, удобным, зависит от характера рассматриваемой задачи,
ГЛ. і. АЛГЕБРА ЛОГИКИ
33
С понятием полноты тесно связано понятие замыкания и замкнутого класса.
Определение. Пусть — некоторое подмножество функций из Р2. Замыкаииеи называется множество всех булевых функций, представимых в виде формул через функции множества 501. Замыкание множества ЭД обозначается через [9Й]. Легко видеть, что замыкание инвариантно относительно операции введения и удаления фиктивных переменных.
Пример 13.
1) Ш= Р2. Очевидно, что [9Л] = Р2.
2) ЗЕЛ = {1, х1 + х2). Замыканием этого множества будет класс Ь всех линейных функций, т. е. функций, имеющих вид
где С* = О, 1 (1 = 0, ..., и); существенные переменные входят с коэффициентом 1, фиктивные — с коэффициентом 0.
Отметим некоторые свойства замыкания:
Определение. Класс (множество) 2ГС называется (функционально) замкнутым, если М = да.
Пример 14.
1) Класс. является замкнутым классом.
1!) Класс. 901 (1, ;г, Н- л,} не замкнут.
3) Класс !> замкнут, так как линейное выражение, составленное из линейных выражений, является линейным.
Легко видеть, что всякий класс [2Я] будет замкнутым. Ото дает возможность получать многочисленные примеры замкнутых классов.
Н терминах замыкания и замкнутого класса можно дать Другое определение полноты (эквивалентное исходному) : ЗЕЛ — полная система, если [2Л] = Р2.
§ 6. Важнейшие замкнутые классы.
Теорема о полноте
Этот параграф мы начинаем с рассмотрения некоторых важнейших замкнутых классов в Р2.
1. Обозначим через Т„ класс всех булевых функций /(.г,, ..., хп), сохраняющих константу 0, т. е. функций,
3 с. В. Яблонский
/(^її * ? •» *^п) Со с&у 4”... Ч- СпХп^
84 Ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТ1ШЫ и шлзклцинми
для которых выполнено равенство
/(О,..., 0)= 0.
Заметим, что если /^Гс, а /' — функция, равная /, то и У ^ Та (это достаточно проверить для функций / и /', отличающихся одной переменной).
Легко видеть, ЧТО функции 0, X, Х!&Х2, Я1 V ж2, хл 4-+ хг принадлежат классу Т0, а функции 1, х не входят В Го.
Поскольку таблица для функции / пз класса Го в первой строке содержит значение 0, то в Г0 содержится ровно (1/2) 22>х булевых функций, зависящих от переменных хи ..хп.
Покажем, что Г0 — замкнутый класс. Так как Г0 содержит тождественную функцию, то для обоснования замкнутости Г0 достаточно показать, что функция
принадлежит Г„, если /, /,, ..принадлежат классу Г0. Последнее шлокает из цепочки равенств
Ф(0,0)—/слсо, 0) мо,..ч 0)Н
-/(0,ОНО.
2. Обозначим через Тх класс всех булевых функций /(^1, ..хп), сохраняющих константу 1, т. е. функций, для которых выполнено равенство
/{1,.... 1)=1.
Очевидно, что класс Т1 вместе с любой функцией содержит и любую равную ей функцию.
Легко видеть, что функции 1, х, Х\ & хг, ж, V хг принадлежат классу Ти а функции 0, х пе входят в Тг.
В силу того, что класс Тк состоит из функций, двойственных функциям нз класса Г0 (или, как мы будем говорить, что класс Т1 двойствен классу Г0), нетрудно перенести результаты о классе Го на класс Г4. Класс Т1 содержит (1/2) 2271 функций, зависящих от переменных хи ..хп, и является замкнутым классом.
3. Обозначим через 5 класс всех самодвойственных функций, т. е. функций / из Р& таких, что /* ~ /.
Как и выше, нетрудно проверить, что добавление равных функций не выводит за пределы класса 5.
Очевидно, что самодвойственными функциями будут х, х. Менее тривиальным примером самодвойственной
ГЛ. 1. АЛГЕБРА ЛОГИКИ 35
функции является функция к(х1, Л’2, х3)=х1х2УадУ V хгх3.
к* (хи хг, ;г3) = {х\ V х2) (^! V х3) (х2 V .г3) =*
*= ХхХг V Х&ь V ХгХ3 = к (*!, х2, х3). Для самодвойственной функции имеет место тождество
J (^1) • ? ?} Хг^) / [Х{1 . ,дг„),
иначе говоря, па наборах (о^, ..а„) и (а(, ..а„), которые мы будем пазывать противоположными, самодвойственная функция принимает противоположные значения. Отсюда следует, что самодвойственная функция полностью определяется своими значениями на первой половине строк (см. табл. 1). Поэтому число самодвойственных функций, зависящих от переменных хи ...
