С.Н. Селезнёва, А.Б. Дайняк, М.С. Шуплецов - Булевы функции и полиномы (1123636)
Текст из файла
Московский Государственный Университетимени М. В. ЛомоносоваФакультет Вычислительной Математики и КибернетикиБулевы функции и полиномыЛектор — к.ф.-м.н. С. Н. СелезневаCоставители — А. Б. Дайняк, М. С. ШуплецовМосква, 2006Глава 1Введение1.1Основные определенияБудем обозначать через Ek множество {0, 1, 2, .
. . , k − 1} первых k целых неотрицательных чисел.Наборы (векторы) длины n , компонентами которых являются элементы из Ek , будем, как правило,обозначать греческими буквами αen , βen , . . . Набор длины n , состоящий из одних нулей, будем обоneзначать 0 , единичный набор аналогичным образом обозначим e1n . Иногда верхний индекс n будемопускать, если из контекста ясно, какую длину имеет рассматриваемый набор. Компоненты наборовбудем обозначать соответствующими греческими буквами с нижними индексами: например, αi — этоi -ая компонента набора αe.На множестве Ek можно ввести стандартный линейный порядок: 0 < 1 < . .
. < k − 1 . На множествеEkn вводится стандартный частичный порядок:∀eαn ∀βen (eα 6 βe ⇔ ∀i ∈ [1, n](αi 6 βi )).На множестве E2n вводится метрика (расстояние) Хемминга d :e = |{i ∈ [1, n] | αi 6= βi }|.d(eα, β)Для набора αe через |eα| будем обозначать число единичных компонент в αe .
Число |eα| будем называть рангом набора αe . Очевидно, |eα| = d(eα, e0).Индексной характеристикой набора αe называется множество ind(eα) = {i | αei = 1} . При этомind(1) = ∅.Булевой функцией (или функцией алгебры логики) называется отображение f : E2n → E2 .
Множество всех булевых функций от n переменных обозначается P2 (n) . Множество всех булевых функцийобозначается через P2 . Не ограничивая общности, будем полагать, что всякая функция из P2 (n) зависит от переменных из множества {x1 , . . . , xn } .Элементарная конъюнкция (ЭК) ранга r — это выражение вида xσi11 . . .
xσirr , где все xij — различныебулевы переменные. Будем считать тождественными ЭК, в которые входят одни и те же литералы(возможно, в разном порядке).Монотонной ЭК называется ЭК, в которую все переменные входят без отрицаний. Будем считать,что 1 — это монотонная ЭК ранга 0. Ранг ЭК K будем обозначать r(K) . Индексной характеристикоймонотонной ЭК K называется множество ind(K) = {i | xi входит в K}.Пусть K1 , . .
. , Kl — элементарные конъюнкции. Выражение вида K1 ⊕ . . . ⊕ Kl называется (обобщенной) полиномиальной формой, или просто (обобщенным) полиномом.Полином, в который входят только монотонные ЭК, называется полиномом Жегалкина.Полином, в который каждая переменная входит либо только с отрицанием, либо только без отрицания, называется поляризованным полиномом.21.1. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ3Мы будем отождествлять полиномы, в которые входят одни и те же ЭК (возможно, в разномпорядке). Кроме того, будем считать, что пустой полином реализует функцию, тождественно равнуюнулю.Под обозначением Pf будем понимать полином (Жегалкина, поляризованный, обобщенный), реализующий функцию f .Глава 2Полиномы Жегалкина иполяризованные полиномы2.1Простейшие фактыТеорема 2.1 ([9]). Для каждой функции из P2 существует единственный реализующий её полиномЖегалкина.Доказательство.1. Существование. Пусть f ∈ P2 (n). Функцию f можно представить в видеf (x1 , .
. . , xn )= x1 · f (1, x2 , . . . , xn ) ⊕ x1 · f (0, x2 , . . . , xn ) == x1 · f (1, x2 , . . . , xn ) ⊕ x1 · f (0, x2 , . . . , xn ) ⊕ f (0, x2 , . . . , xn ).Функции f (0, x2 , . . . , xn ) и f (1, x2 , . . . , xn ) можно, в свою очередь, разложить по переменной x2 , ит.д. Наконец, мы придем к выражению, представляющему собой сумму конъюнкций переменныхxi и констант. Упростив его, используя тождества 0 ⊕ K = 1 · K = K , 0 · K = 0 и K ⊕ K = 0 ,получим полином Жегалкина, реализующий f .2. Единственность.
Пусть P1 и P2 — различные полиномы Жегалкина, реализующие одну и ту жефункцию. Тогда полином P = P1 ⊕ P2 является непустым полиномом Жегалкина, реализующимтождественный нуль. Пусть K = xi1 · . . . · xir — ЭК минимального ненулевого ранга r в полиномеP . Присвоим значение 0 всем переменным, не входящим в K , и значение 1 — всем переменным изK , кроме xi1 . Получим функцию от единственной переменной xi1 , которая будет существеннозависеть от xi1 , что противоречит предположению о том, что полином P реализует константу 0 .Следствие 2.1.
Для каждой функции из f ∈ P2 (n) и каждого вектора поляризации δen существуетединственный реализующий ее поляризованный по вектору δ̃ n полином.В соответствии с теоремой 2.1 и следствием к ней полиномы Pf и Pfδ для произвольного вектораполяризации δe однозначно определены ( f ∈ P2 (n) ).eУпражнение 1. Дайте другое доказательство единственности в теореме 2.1. Для этого установите равенство числа различных функций и числа различных полиномов Жегалкина от n переменных.Упражнение 2. Докажите следствие к теореме 2.1.Упражнение 3. Постройте по схеме п. 1 доказательства теоремы 2.1 полином Жегалкина дляфункции f (ex3 ) , заданной столбцом значений: (01001011) .42.1.
ПРОСТЕЙШИЕ ФАКТЫ5Итак, для каждой функции можно найти единственный полином Жегалкина. Сразу же возникает вопрос: каким способом можно его построить? Хотя доказательство теоремы 2.1 фактически даетспособ нахождения полинома Жегалкина для произвольной функции, его нельзя считать удовлетворительным из-за его громоздкости. Тем же недостатком обладает и метод неопределенных коэффициентов.
Оказывается, однако, существует простой, быстрый способ преобразования столбца значенийфункции в вектор коэффициентов ее полинома Жегалкина.Каждую монотонную ЭК от переменных x1 , . . . , xn можно закодировать двоичным векторомκe = (κ1 , . . .
, κn ) , где κi = 1 тогда и только тогда, когда переменная xi входит в K . Число, двоичная запись которого определяется ветором κe , назовем номером конъюнкции K . Всякий полиномЖегалкина от переменных x1 , . . . , xn можно закодировать ветором ec длины 2n , в котором ci = 1тогда и только тогда, когда ЭК с номером i входит в этот полином. Через ecf будем обозначать векторeкоэффициентов полинома Жегалкина функции f , а через f — вектор-столбец значений этой функции.nnПусть n > 1 .
Определим по рекурсии преобразование Πn : E22 → E22 :Если n = 1, то Πn (α0 , α1 ) = (α0 , α0 ⊕ α1 ).eγe Πn (β)e ⊕ Πn (eЕсли n > 1 и αe = (β,e), где βe и γe — векторы длины 2n , то Πn+1 (eα) = (Πn (β),γ )),где суммирование векторов ведется покоординатно.Теорема 2.2 ([1]). Пусть f ∈ P2 (n) . Тогда Πn (fe) = ecf .Доказательство. Доказательство проводится индукцией по числу n переменных функции f .Аналогично преобразованию Πn можно построить преобразование Πδn , которое преобразует столбецзначений функции в вектор коэффициентов ее δe–поляризованного полинома.Если n = 1 и δe = (δ0 ), тоeΠδn (α0 , α1 ) =e(α0 , α0 ⊕ α1 ), если δ0 = 0,(α1 , α0 ⊕ α1 ), если δ0 = 1.eγПусть n > 1 . Если δe = (δ0 , δe0 ) — вектор длины (n + 1) , и αe = (β,e) , то(eeγe)Πδn+1 (β,=e0e0 ee0 eγ )), если δ0 = 0,⊕ Πδn (eΠδn (β)(Πδn (β),00eeeδ0δ eδγ )), если δ0 = 1.γ ), Πn (β) ⊕ Πn (e(Πn (eДоказательство ”правильности функционирования” преобразования Πδn может быть легко проведено по индукции.eУпражнение 4.
Для функции из упражнения 3 постройте в соответствии с преобразованием(010)поляризованный по вектору (010) полином.Π3Итак, мы видим, что поляризованные полиномы и полиномы Жегалкина во многом схожи. В чем жетогда мы выигрываем при использовании поляризованных полиномов для задания булевых функций?Преимущество состоит в свободе выбора вектора поляризации. Очевидно, что для всякого фиксированного вектора поляризации можно подобрать функцию f ∈ P2 (n) такую, что длина (число слагаемых)eполинома Pfδ будет равна 2n — то есть будет максимально возможной. Но если нам задана функция f ,eто мы можем подобрать вектор δe так, чтобы максимально сократить размер полинома Pfδ . Подробноэтот вопрос рассматривается в следующем параграфе.Упражнение 5.
Для какой функции от n переменных полином Жегалкина имеет максимальнуюдлину ( 2n )? Как по заданному вектору поляризации δe найти столбец значений функции, для которойдлина δe–поляризованного полинома максимальна?6ГЛАВА 2. ПОЛИНОМЫ ЖЕГАЛКИНА И ПОЛЯРИЗОВАННЫЕ ПОЛИНОМЫ2.2Сложность булевых функций в классе поляризованных полиномовНачнем с определений. Будем через l(P ) обозначать длину, т.е. число слагаемых, полинома P . Пустьf (exn ) ∈ P2 .
Введем функционалelп.п. (f ) = min Pfδ ,neδ∈E2обозначающий минимальную длину поляризованного полинома для функции f . Значение lп.п. (f ) называется сложностью функции f в классе поляризованных полиномов. Также рассмотрим функциюLп.п. (n) = max lп.п. (f ),f ∈P2 (n)характеризующую сложность ”са́мой сложной функции” от n переменных в классе поляризованныхполиномов. Функция Lп.п. (n) называется функцией Шеннона сложности в классе поляризованныхполиномов.В 1995 году Н.А.Перязев установил точное значение функции Lп.п. (n) . Оказывается, класс поляризованных полиномов ”в полтора раза лучше” для представления булевых функций, чем классполиномов Жегалкина.Теорема 2.3 ([5]).2 n·2 .Lп.п.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
