Булевы функции и основные их классы. Полином Жегалкина.

Целью данного параграфа является знакомство с основными объектами пособия - булевыми функциями. Напомним понятие функции.

Согласно определения (см. часть I), отношение fÍA´B называется функцией (или отображением) из множества A в множество B, если d_f=A, r_fÍB и из (х, y₁)Îf, (х, y₂)Îf следует y₁=y₂. Функция f из A в B обозначается через f: A®B или A B. Если (х, y)Îf, то пишут y=f(x) или f: x®y. При этом y называется значением функцииf при значении аргументаx, а также говорят, что функция fставит в соответствие элементу x элемент y.

Другими словами, функцией называется такое правило f, которое каждому элементу одного множества A ставит в соответствие однозначно определённый элемент другого множества B.

5.1. Понятие булевой функции и способы её задания.

Определение 1. Булевой функцией называется любая функция f, область определения которой совпадает с декартовой n-й степенью множества {0, 1}, а область значений - с {0, 1}.

Другими словами, f - булева функция, если d_f={0, 1}^п, r_f={0, 1}.

Для булевой функции дадим ещё одно

Определение 1¢. Булевой функцией называется любая функция f, которая произвольному набору (s₁, s₂, …, s_n) из нулей и единиц ставит в соответствие значение f(s₁, s₂, …, s_n)Î{0, 1}.

Булевы функции также называют переключательными функциями.

Мы видели, что любая формула алгебры логики ставит в соответствие произвольному набору (s₁, s₂, …, s_n) из нулей и единиц некоторое однозначно определённое значение из множества {0, 1}. Поэтому, любую формулу алгебры логики можно рассматривать как некоторую функция. Но мы также видели, что существуют эквивалентные между собой формулы, которые имеют одинаковые таблицы истинности, и, тем самым, представляют одинаковые отображения из {0, 1}^п на {0, 1}. Следовательно, эквивалентные между собой формулы можно рассматривать как одну и ту же булеву функцию.

С другой стороны, если задана булева функция, то, естественно, нам известно, какому набору из нулей и единиц она ставит в соответствие 0 или 1, то есть нам известна таблица значений этой функции, которая, очевидно, имеет структуру таблицы истинности некоторой формулы. Так как для любой таблицы истинности мы можем построить некоторую формулу, то и для любой булевой функции мы можем построить её определяющую формулу.

Тем самым, мы приходим к следующему определению.

Определение 2. ФормулаFпредставляет функциюf, если их таблицы истинности совпадают.

Таким образом, функцию можно задать с помощью формулы, представляющей её. Такой способ задания называется также аналитическим.

Итак, любую булеву функцию можно рассматривать как некоторую формулу. Поэтому, все понятия и факты, связанные с формулами алгебры логики, рассмотренные нами выше, распространяются и на булевы функции.

В частности, над булевыми функциями производятся логические операции (Ø), &, Ú, ®, «, |, ¯, Å. Но в отличие от формул алгебры логики эквивалентность трансформируется в равенство. Поэтому во всех свойствах логических операций знак «~» меняется на знак «=», и получаем соответствующие свойства логических операций над функциями: f&g=g&f, и т.д.

В частности, на множестве Ф_п булевых функций от п переменных рассматривается булева алгебра áФ_п; &, Ú; Ø; 0, 1ñ. Она изоморфна фактор-алгебре F_n/~ булевой алгебры по конгруэнции ~ - отношения эквиваленции между формулами.

Наконец, áФ_п; Å, &ñ - кольцо. Оно изоморфно фактор-кольцу булева кольца по той же конгруэнции.

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

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

Определение 3. Вектором значений булевой функции f называется упорядоченный набор всех её значений, соответствующих лексикографическому порядку множества аргументов.

Таким образом, функцию можно задать с помощью её вектора значений.

Наконец, для задания функции достаточно указать, при каких наборах значений переменных функция принимает значение 1 либо, наоборот, 0. Другими словами, функцию можно задать с помощью системы равенств вида f(s₁, s₂, …, s_n)=1 или системы равенств вида f(s₁, s₂, …, s_n)=0.

Пример 5.1. Функцию, заданную формулой (х®у)&(у®z)&(z®x), можно задать с помощью вектора значений (10101111), а также систем равенств f(0, 0, 0)=f(0, 1, 0)=f(1, 0, 0)=f(1, 0, 1)=f(1, 1, 0)=f(1, 1, 1)=1 либо f(0, 0, 1)=f(0, 1, 1)=0.

Упражнение 5.1. Функция f(x, y, z) задана системой своих значений. Найти ДНФ и КНФ функции:

а) f(0, 0, 1)=f(0, 1, 0)=f(1, 0, 1)=1;

б) f(0, 0, 1)=f(0, 1, 1)=f(1, 1, 0)=f(1, 1, 1)=0;

в) f(0, 0, 0)=f(0, 1, 0)=f(0, 1, 1)=f(1, 0, 1)=1.

Решение. а) Нам даны те наборы значений переменных, при которых функция принимает значение 1: (0, 0, 1), (0, 1, 0), (1, 0, 1). Составим соответствующие им конъюнкты: z, y , x z. Составим из них ДНФ: zÚ y Úx z.

На остальных наборах (0, 0, 0), (0, 1, 1), (1, 0, 0), (1, 1, 0), (1, 1, 1) функция принимает значение 0. Составим соответствующие им дизъюнкты: xÚyÚz, xÚ Ú , ÚyÚz, Ú Úz, Ú Ú . Составим из них КНФ: (xÚyÚz)&(xÚ Ú )&( ÚyÚz)&( Ú Úz)& &( Ú Ú ).

f(0, 0, 0, 0)=f(0, 0, 0, 1)=f(0, 0, 1, 1)=f(0, 1, 0, 1)=f(0, 1, 1, 1)=f(1, 0, 1, 1)=f(1, 1, 0, 0)=f(1, 1, 1, 1)=0

и f(0, 0, 1, 0)=f(0, 1, 0, 0)=f(0, 1, 1, 0)=f(1, 0, 0, 0)=f(1, 0, 0, 1)=f(1, 0, 1, 0)=f(1, 1, 0, 1)=f(1, 1, 1, 0)=1.

Остальное аналогично решению предыдущего упражнения.

Определение 4. Функция f(х₁, х₂, …, х_n) называется суперпозицией функции g(y₁, y₂, …, y_m), h₁(х₁, х₂, …, х_n), h₂(х₁, х₂, …, х_n), …, h_m(х₁, х₂, …, х_n) если

f(х₁, х₂, …, х_n)=g(h₁(х₁, х₂, …, х_n), h₂(х₁, х₂, …, х_n), …, h_m(х₁, х₂, …, х_n)).

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

1. Говорят, что булева функция fсохраняет нуль, если f(0, 0, …, 0)=0. Класс Р₀ - класс булевых функций, сохраняющих нуль: Р₀={f | f(0, 0, …, 0)=0}.

2. Говорят, что булева функция fсохраняет единицу, если f(1, 1, …, 1)=1. Класс Р₁ - класс булевых функций, сохраняющих единицу: Р₁={f | f(1, 1, …, 1)=1}.

3. Говорят, что булева функция f является самодвойственной, если она совпадает со своей двойственной. Класс S - класс самодвойственных функций: S={f | f*=f}.

4. Булева функция называется монотонной, если для любых наборов нулей и единиц (a₁, a₂, …, a_n) и (b₁, b₂, …, b_n) из условий a₁£b₁, a₂£b₂, …, a_n£b_n следует f(a₁, a₂, …, a_n)£f(b₁, b₂, …, b_n). Класс М - класс монотонных функций: М={f |(a₁£b₁, a₂£b₂, …, a_n£b_n) Þ f(a₁, a₂, …, a_n)£f(b₁, b₂, …, b_n)}.

5. Булева функция называется линейной, если она представима в виде линейного многочлена: f(x₁, x₂, …, x_n)=c₀Åc₁x₁Åc₂x₂Å…Åc_nx_n. Класс L - класс линейных функций: L={f | f(x₁, x₂, …, x_n)=c₀Åc₁x₁Åc₂x₂Å…Åc_nx_n}.

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

Принадлежность функции к классам Р₀ и Р₁ проверяется очевидным образом.

Принадлежность функции к классу S проверяется так же, как и самодвойственность формулы алгебры логики: по таблице истинности проверяется, что на всех противоположных наборах значений переменных функция принимает противоположные значения (см. ).

Проверка принадлежности функции к классу М на первый взгляд также очевидна: достаточно по таблице истинности убедиться, что из a₁£b₁, a₂£b₂, …, a_n£b_n следует f(a₁, a₂, …, a_n)£f(b₁, b₂, …, b_n). Но с ростом числа переменных эта процедура становится достаточно громоздкой. Основная проблема возникает при выделении пар наборов (a₁, a₂, …, a_n) и (b₁, b₂, …, b_n) таких, чтобы можно было произвести их сравнение a₁£b₁, a₂£b₂, …, a_n£b_n. Тем не менее, при небольшом числе переменных существуют достаточно эффективные процедуры. Опишем одну из процедур для случаев п=3 и п=4. Она заключается в следующем.

Строится помеченный (гипер)куб, в вершинах которого проставляются значения функции. Построив всевозможные маршруты от вершины (0…0) до вершины (1…1), убеждаемся, что на каждом из этих маршрутов при переходе от произвольной вершины (a₁, a₂, …, a_n) к смежной вершине (b₁, b₂, …, b_n) будет выполнено условие f(a₁, a₂, …, a_n)£f(b₁, b₂, …, b_n). Если для какого-либо маршрута это условие нарушено, то функция монотонной не является.

Рассмотрим процедуру проверки на монотонность для функции f(x, y, z)= =x&(yÚz). Построим помеченный куб, в вершинах которого проставлены значения функции f(x, y, z) (рис. 1). Замечаем, что при переходе от вершины к вершине по любому маршруту от (000) до (111), значения функции на вершинах не убывают. Это означает, что функция монотонна.

Для функции f(x₁, x₂, x₃, x₄)=(x₁&x₂)®(x₃Úx₄) от четырёх переменных строим гиперкуб четвёртого порядка (рис.2). Как видим, существует маршрут от вершины (0000) к вершине (1111), для которого при переходе от одной вершины к другой значение функции меняется от 1 к 0. Например, это маршрут ((0000, 1000), (1000, 1100), (1100, 1110), (1110, 1111)). По этому маршруту имеем, что f(1, 0, 0, 0)<f(1, 1, 0, 0).

Проверка принадлежности функции к классу L заключается в том, что сначала находятся значения коэффициентов c₀, c₁, c₂, …, c_n в предположении, что функция f линейная. После этого сравниваются таблицы истинности функции f и полученной формулы c₀Åc₁x₁Åc₂x₂Å…Åc_nx_n. Коэффициенты находятся из соотношений:

c₀=f(0, 0, …, 0),

c₁=c₀Åf(1, 0, …, 0),

c₂=c₀Åf(0, 1, …, 0), (5.1)

…………………..

c_n=c₀Åf(0, 0, …, 1).

Пример 5.2. Проверим на линейность функции (х&у)Ú( & ) и х . Обе функции - от двух переменных. Значит, функции будем искать в виде c₀Åc₁xÅc₂у, где коэффициенты c₀, c₁, c₂ ищем из соотношений (5.1), которые принимают вид: c₀=f(0, 0), c₁=c₀Åf(1, 0), c₂=c₀Åf(0, 1).

Для функции (х&у)Ú( & ) имеем

c₀=f(0, 0)=(0&0)Ú( & )=1,

c₁=c₀Åf(1, 0)=1Å(1&0)Ú( & )=1Å0=1,

c₂=c₀Åf(0, 1)=1Å(0&1)Ú( & )=1Å0=1,

то есть c₀Åc₁xÅc₂у=1ÅxÅу. Сравним таблицы истинности полученной формулы и функции f(х, у)=(х&у)Ú( & ):

Таблицы истинности совпали. Следовательно, f(х, у)=1ÅxÅу и функция f(х, у) является линейной.

Для функции х имеем

c₀=f(0, 0)=0& =1,

c₁=c₀Åf(1, 0)=1Å(1& )=1Å1=0,

c₂=c₀Åf(0, 1)=1Å(0& )=1Å0=1,

то есть c₀Åc₁xÅc₂у=1Åу. Сравним таблицы истинности полученной формулы и функции f(х, у)=х& :

Как видим, таблицы истинности полученной формулы и функции f(х, у) не совпадают. Следовательно, функция х& не является линейной.

Упражнение 5.3. Принадлежат ли функции из упражнений 5.1 и 5.2 к классам Р₀, Р₁, S, M, L?

Решение. а) (из упражнения 5.1) Проверим принадлежность к классам Р₀, Р₁, S. Имеем f(0, 0, 0)=0 и f(1, 1, 1)¹1. Поэтому f(х, у, z)ÎР₀ и f(х, у, z)ÏР₁. Далее, f(х, у, z)ÏS. Действительно, имеем, например, f(0, 0, 0)¹ . Принадлежность к классу М проверяется аналогично тому, как это проделано выше. Проверим принадлежность к классу L. Предположим, что функция линейна: f(х, у, z)=c₀Åc₁xÅc₂уÅс₃z, где

c₀=f(0, 0, 0)=0, c₁=c₀Åf(1, 0, 0)=0Å0=0, c₂=c₀Åf(0, 1, 0)=0Å1=1, c₂=c₀Åf(0, 0, 1)=0Å1=1,

то есть f(х, у, z)=уÅz. Составим таблицы истинности f(х, у, z) и уÅz:

Таблицы истинности f(х, у, z) и уÅz не совпадают. Следовательно, f(х, у, z) не является линейной, то есть f(х, у, z)ÏL.

Другой способ проверки линейности функции основан на так называемых полиномах Жегалкина.

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

Определение 5. Полиномом Жегалкина называется полином вида

Åс,

(то есть сумма произведений вида ), где суммирование ведётся по некоторому множеству различных наборов (i₁, i₂, …, i_k), в которых все i_j также различны.

Любая булева функция единственным образом (с точностью до следования слагаемых) представима в виде полинома Жегалкина.

Для представления булевой функции в виде полинома Жегалкина достаточно:

1. Привести функцию к ДНФ (КНФ).

2. Выразить операции &, Ú, Ø через операции булева кольца по формулам из п.5.2.

Пример 5.3. Найдём полиномы Жегалкина для функций из примера 5.2. Для функции (х&у)Ú( & ) имеем

(х&у)Ú( & )=хуÅ Åху =хуÅ =

=хуÅ(1Åх)(1Åу)=хуÅ1ÅхÅуÅху=1ÅхÅу,

то есть (х&у)Ú( & )=1ÅхÅу (в чём мы уже убеждались). Для функции х имеем х =х(1Åу)=хÅху, то есть х =хÅху.

Как видим, для функции х полином Жегалкина содержит произведения переменных. Такие полиномы называются нелинейными. Полиномы Жегалкина вида c₀Åc₁x₁Åc₂x₂Å…Åc_nx_n называются линейными. Таким образом, линейная функция представима в виде линейного полинома Жегалкина.

Заметим, что если А и В - различные конституенты единицы, то они содержат хотя бы одну пару противоположных литер, и тогда АВ=0, АÚВ=АÅВ. Поэтому полином Жегалкина удобно получать из СДНФ формулы.

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

Решение. а) Имеем СДНФf(x, y, z)= zÚ y Úx z (см. решение упражнения 5.1, а)). Учитывая, что =1Åх, =1Åу, =1Å z и раскрывая скобки, получаем

zÚ y Úx z= zÅ y Åx z=(1Åх)(1Åу)zÅ(1Åх)y(1Å z)Åx(1Åу)z=

=zÅхzÅуzÅ хyzÅyÅхyÅyzÅхyzÅxzÅxуz=yÅzÅxyÅхyz.

То есть zÚ y Úx z=yÅzÅxyÅхyz. В частности, функция не является линейной.

Функциональная полнота.

Определение 6. Система булевых функций F={f₁, f₂, …, f_n} называется полной, если любая булева функция представима в виде суперпозиции функций из F.

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

Определение 7. Система булевых функций называется базисом, если она полна, и удаление любой функции из этой системы делает её неполной.

Упражнение 5.5. Проверить полноту следующих систем булевых функций:

а) {®, Ø}; б) {«, Å}; в) {¯}; г) { &, ®}.

Решение. а) Принадлежность данных функций к каждому из классов Поста сведём в таблицу:

	P0	P1	S	M	L
x®y	-	+	-	-	-
	-	-	+	-	+

В таблице знаком «+» на пересечении строки с указанием функции со столбцом с указанием класса обозначен тот факт, что функция принадлежит соответствующему классу, а знаком «-» - тот факт, что функция не принадлежит данному классу. В каждом столбце имеется знак «-», то есть для любого класса Поста система F={®, Ø} содержит функцию, не лежащую в данном классе. Следовательно, система функций F={®, Ø} является полной. Она образует базис, так как удаление любой функции из этой системы ведёт к тому, что оставшаяся система является неполной.

Не нашли, что искали? Воспользуйтесь поиском по сайту: