Дискретная математика

73 К, + Кг +... +К,. (3.21) Покажем, что сумма (3.21) представляет нашу функцию. Пусть f(bi, Ьъ- b,J= 1, тогда на наборе (Ь,, Ь:,.-, Ь^) одна из собственных конституент единицы принимает значение 1, положим, Л). Остальные собственные конституенты единицы на этом наборе равны нулю. Тогда сумма (3.21) обращается в единицу. Если f(b,, b:,..., Ь^=0, то на наборе (hi, 6 2 , . . . , Ь,) все собственные конституенты АГ, (1 < i<s) обрагцаются в нуль, следовательно, и сумма (3.21) тоже равна нулю. Итак, доказано, что f(x,, xJ~K, + K2+...+K,. В конституентах единицы исключим отрицание, используя соотношение: 1х ~1 + X. Появившиеся при этом скобки раскроем, используя дистрибутивность конъюнкции относительно сложения по модулю два. Далее приведем подобные члены, используя соотношения; х + х +...+ х ~ О, когда имеем четное число слагаемых, и х + х +...+ х ~ х, когда имеем нечетное число слагаемых. В результате получим требуемый полином Жегалкина. Теперь докажем единственность. Максимальное возможное число слагаемых в полиноме Жегалкина равно числу подмножеств множества {xj, xJ, следовательно, равно 2". Различные полиномы Жегалкина получаются, если некоторые а, = О, другие a j ~ 1. Таким образом, число •лП ПОЛИНОМОВ Жегалкина равно 2 . Число различных булевых функций от п переменных, кахс известно, тоже равно 2 , причем каждая функция (по доказанному) имеет свой полином. Отсюда и следует единственность полинома Жегалкина для данной функции. § 13. Сокращенные дизъюнктивные нормальные формы Прежде чем ввести сокращенные дизъюнктивные нормальные формы (сокращенные д.н.ф.), проведем вспомогательные рассуждения. Импликантой булевой фунтщи f называется булева функция (р, которая обращается в нуль на всех тех наборах значений аргументов, на которых равна нулю функция f . Обозначение (р с: f применяется для высказывания: «функция (р является импликантой функции у>>, если (р не импликанта для f , т о записываем: с г / Если (р czf, то всюду, где/принимает значение О, функция (р тоже принимает значение О, там же, где f принимает значение 1, ф может быть как О, так и 1. Следовательно, функция (р имеет не меньшее количество значений О, чем функция/!