Полиномы Жегалкина

Полиномом (многочленом) Жегалкина от п переменных называется функция

P = a₀ + a₁x₁ +a₂x₂ + ...a_nx_n +a_{n +1}x₁x₂ +...+a_{n +C}²_nx_n-1x_n + ...+a_2n-1x₁x₂..xn

Всего здесь 2^п слагаемых. Напомним, что + сейчас означает сложение по модулю 2, коэффициенты a₀, a₁,..., a₂ⁿ_-1 являются константами (равными нулю или единице).

Теорема. Любая функция п переменных может быть представлена полиномом Жегалкина и это представление единственно.

Доказательство. Любая функция f(x₁, x₂, …, x_n) имеет свою таблицу истинности. Запишем сначала данную функцию в виде полинома Жегалкина с неопределенными коэффициентами. Затем по очереди подставляем всевозможные наборы переменных и находим коэффициенты. Легко видеть, что за каждую подстановку находим только один коэффициент. Так как число наборов равно числу коэффициентов (и равно 2^п), отсюда следует утверждение теоремы.

Доказательство этой теоремы показывает, как по таблице истинности построить полином Жегалкина.

Имеется 2-й способ нахождения полинома Жегалкина для функций, заданных в виде ДНФ. Этот способ основан на том, что х+1 = . Если функция задана в виде ДНФ, то сначала убираем дизъюнкцию, используя при этом правило де Моргана, а все отрицания заменяем прибавлением единицы. После этого раскрываем скобки по обычным правилам, при этом учитываем, что четное число одинаковых слагаемых равно нулю (так как х+ х = 0), а нечетное число одинаковых слагаемых равно одному такому слагаемому.

Пример.

( xy + 1)((x + 1)(y + 1) + 1)((y + 1)z + 1) + 1 = (xy + 1)(xy + x + y)(yz + z + 1) + 1 = (x + y)(yz + z + 1) + 1= xyz + yz + xz +yz + x + y + 1 = xyz + xz + x +y + 1.

Последнее выражение и есть полином Жегалкина данной функции.

Функция f (x₁,x₂,…,x_n) называется линейной, если ее полином Жегалкина содержит только первые степени слагаемых. Более точно функция называется линейной, если ее можно представить в виде

f(x₁, x₂, …, x_n) = a₀+ a₁x₁+ a₂ x₂ +…+ a_n x_n.

Класс линейных функций часто обозначают через L.(Заметим, что число линейных функций п переменных равно 2^п+1).

Замечание. Если п³2 то линейная функция в таблице истинности может содержать только четное число единиц.Действительно, если f(x₁,x₂,…, x_n) = x₁+ x₂+…+x_n,то легко видеть что такая функция в таблице истинности содержит одинаковое число нулей и единиц а именно 2^п /2 единиц и нулей, т. е. число это четно при п³2. Столько же нулей и единиц имеет функция .Добавлениежефиктивнойпеременной приводитк увеличению числа единиц (и нулей) в два раза. Разумеется, нелинейная функция может иметь в таблице истинности как четное, так и нечетное число единиц.

7. Суперпозиция функций. Замыкание набора функций.
Замкнутые классы функций. Полные наборы. Базисы

Пусть имеется некоторый набор K, состоящий из конечного числа булевых функций. Суперпозицией функций из этого набора называются новые функции, полученные с помощью конечного числа применения двух операций;

можно переименовать любую переменную, входящую в функцию из K;

вместо любой переменной можно поставить функцию из набора K или уже образованную ранее суперпозицию.

Суперпозицию еще иначе называют сложной функцией.

Пример 7.1. Если дана одна функция х|y (штрих Шеффера), то ее суперпозициями, в частности, будут следующие функции x|x, x|(x|y), x|(y|z)и т. д.

Замыканием набора функций из K называется множество всех суперпозиций. Класс функций K называется замкнутым, если его замыкание совпадает с ним самим.

Набор функций называется полным, если его замыкание совпадает со всеми логическими функциями. Иначе говоря, полный набор – это множество таких функций, через которые можно выразить все остальные булевы функции.

Неизбыточный полный набор функций называется базисом (“неизбыточный” означает, что если какую-то функцию удалить из набора, то этот набор перестанет быть полным).

Пример 7.2. Конъюнкция, дизъюнкция и отрицание являются полным набором (в этом убедились в разд. 5), но не являются базисом, так как это набор избыточен, поскольку с помощью правил де Моргана можно удалить конъюнкцию или дизъюнкцию. Любую функцию можно представить в виде полинома Жегалкина (разд. 6). Ясно, что функции конъюнкция, сложение по модулю 2 и константы 0 и 1 являются полным набором, но эти четыре функции также не являются базисом, поскольку 1+1=0, и поэтому константу 0 можно исключить из полного набора (для построения полиномов Жегалкина константа 0 необходима, поскольку выражение “1+1” не является полиномом Жегалкина).

Легко видеть, что одним из способов проверки полноты какого-то набора К является проверка того, что через функции из этого набора выражаются функции другого полного набора (можно проверить, что через функции из К можно выразить конъюнкцию и отрицание или дизъюнкцию и отрицание.

Существуют такие функции, что одна такая функция сама является базисом (здесь достаточно проверить только полноту, неизбыточность очевидна). Такие функции называются шефферовскими функциями. Это название связано с тем, что штрих Шеффера является базисом. Напомним, что штрих Шеффера определяется следующей таблицей истинности:

Так как очевидно , т. е. отрицание является суперпозицией штриха Шеффера, а дизъюнкция тогда , штрих Шеффера сам является базисом. Аналогично, стрелка Пирса является шефферовской функцией (студенты могут проверить это сами). Для функций 3-х или более переменных шефферовских функций очень много (конечно, выражение других булевых функций через шефферовскую функцию большого числа переменных сложно, поэтому в технике они редко используются).

Заметим, что вычислительное устройство чаще всего базируется на полном наборе функций (часто на базисах). Если в основе устройства лежат конъюнкция, дизъюнкция и отрицание, то для этих устройств важна проблема минимизации ДНФ; если в основе устройства лежат другие функции, то полезно уметь алгоритмически минимизировать выражения через эти функции.

Перейдем теперь к выяснению полноты конкретных наборов функций. Для этого перечислим 5 важнейших классов функций:

• Т₀ – это набор всех тех логических функций, которые на нулевом наборе принимают значение 0 (Т₀ – это класс функций, сохраняющих 0);
• Т₁ – это набор всех логических функций, которые на единичном наборе принимают значение 1 (Т₁ – это класс функций, сохраняющих единицу) (заметим, что число функций от п переменных принадлежащих классам Т₀ и Т₁ равно 2^2n-1);
• L – класс линейных функций т. е. функций, для которых полином Жегалкина содержит только первые степени переменных;
• М – класс монотонных функций. Опишем класс этих функций более подробно. Пусть имеются 2 набора из п переменных: s1 = (x₁, x₂,..., x_n)

s₁= (х₁, х₂,…, х_п)и s ₂= (y₁, y_2,…, y_п).Будем говорить, что набор s ₁ меньше набора s ₂ (s ₁ £ s ₂), если все х_i £ y_i. Очевидно, что не все наборы из п переменных сравнимы между собой (например, при п = 2наборы (0,1) и (1,0) не сравнимы между собой). Функция от п переменных называется монотонной,если на меньшем наборе она принимает меньшее или равное значение. Разумеется, эти неравенства должны проверяться только на сравнимых наборах. Понятно, что несравнимые наборы – это те, в которых есть некоторые координаты типа (0,1) в одном наборе и (1,0) в другом на соответствующих местах (в дискретной математике монотонные функции это только как бы “монотонно возрастающие функции”, “монотонно убывающие” функции здесь не рассматриваются).

Пример. В нижеследующей таблице функции f₁, f₂ являются монотонными функциями, а функции f₃, f₄– нет.

Естественный порядок переменных обеспечивает тот факт, что если какой-то набор меньше другого набора, то он обязательно расположен в таблице истинности выше“большего” набора. Поэтому если в таблице истинности (при естественном порядке набора переменных) вверху стоят нули, а затем единицы, то эта функция точно является монотонной. Однако возможны инверсии, т. е. единица стоит до каких-то нулей, но функция является все равно монотонной (в этом случае наборы, соответствующие “верхней” единице и “нижнему” нулю должны быть несравнимы;можно проверить, что функция, задаваемая таблицей истинности при естественном порядке набора переменных (00010101), является монотонной);

• Класс S – класс самодвойственных функций. Функция п переменных называется самодвойственной, если на противоположных наборах она принимает противоположные значения, т. е. самодвойственная функция f(x₁, x₂,…,x_n)удовлетворяет условию f (x₁,x₂, ..., x_n ) =. Например, функции f_1,f₂-являются самодвойственными, а функции f_3, f₄ – не являются.Нетрудно устанавливается следующий факт.

Теорема. Классы функций Т₀, Т₁, L, M, S замкнуты.

Это утверждение следует непосредственно из определения самих этих классов, а также из определения замкнутости.

В теории булевых функций очень большое значение имеет следующая теорема Поста.

Теорема Поста. Для того чтобы некоторый набор функций K был полным, необходимо и достаточно, чтобы в него входили функции, не принадлежащие каждому из классов T₀, T₁, L, M, S.

Заметим,чтонеобходимостьэтогоутвержденияочевидна,таккакеслибы всефункцииизнабора К входиливодинизперечисленныхклассов,тоивсесуперпозиции,азначит,изамыканиенаборавходилобывэтотклассикласс К немогбытьполным.

Достаточностьэтогоутверждениядоказываетсядовольносложно,поэтомуздесь не приводится.

Из этой теоремы следует довольно простой способ выяснения полноты некоторого набора функций. Для каждой из этих функций выясняется принадлежность к перечисленным выше классам. Результаты заносятся в так называемую таблицу Поста (в нашем примере эта таблица составлена для 4-х функций, причем знаком “+” отмечается принадлежность функции соответствующему классу, знак “–” означает, что функция в него не входит).

В соответствии с теоремой Поста набор функций будет полным тогда и только тогда, когда в каждом столбце таблицы Поста имеется хотя бы один минус. Таким образом, из приведенной таблицы следует, что данные 4 функции образуют полный набор, но эти функции не являются базисом. Из этих функций можно образовать 2 базиса: f₃, f₁и f₃, f₂. Полными наборами будут любые наборы содержащие, какой-либо базис.

Непосредственно из таблицы Поста следует, что число базисных функций не может быть больше 5. Нетрудно доказать, что на самом деле это число меньше или равно 4.

Некоторые приложения теории булевых функций

Материал этого раздела не используется в контрольной работе, но используется в тестах, предлагаемых студентам для сдачи зачета. Примеры такого рода приведены в разд. 17 “Дополнительные задачи”.