Как проверить булеву функцию на самодвойственность

булева-алгебра — Выяснить является ли функция самодвойственной:

1)$%(x \wedge y) \vee(x \wedge z) \vee (y \wedge z)$%, пытался сначала наклыдвать отрицание на всю функцию, потом на каждый член, ничего толком не выражалось, хотелось бы хотя бы идею услышать
2)Привести пример самодвойственной линейной функции

задан 11 Дек ’15 21:26

Nikitc
89 ● 11 ● 28
58&#037 принятых

1 ответ

1) Это известная «функция голосования», она самодвойственна. Из формулы легко заметить, что функция равна 1 тогда и только тогда, когда хотя бы два из трёх значений переменных (то есть большинство) принимают значение 1. Тогда понятно, что при смене всех значений на противоположные, большинство значений станет противоположным, а это и означает самодвойственность.

При желании, можно в этом же самом убедиться и при помощи формул, хотя такой способ выглядит сложнее. По принципу двойственности, для функции $%xy\lor xz\lor yz$% из условия, двойственной будет $%(x\lor y)(x\lor z)(y\lor z)$%. Она тождественно равна предыдущей, что проверяется при помощи применения дистрибутивного закона. Если раскрыть все скобки, то получится дизъюнкция 8 конъюнкций, среди которых будут $%xy$%, $%xz$%, $%yz$%, а также $%xyz$%, но последняя из них «поглощается» любой из предыдущих.

К сказанному можно добавить, что эта же функция следующим образом представляется полиномом Жегалкина: $%xy+xz+yz$%. Здесь также можно непосредственно проверить, что при замене каждой из переменных на её отрицание (прибавляем единицу), функция принимает противоположное значение: $%(x+1)(y+1)+(x+1)(z+1)+(y+1)(z+1)=xy+xz+yz+1$%. Всё остальное, что встречается дважды, сокращается при сложении по модулю 2.

Наконец, есть совсем прямой способ проверки: для исходной функции составляем таблицу, и при стандартном порядке следования наборов получается вектор значений 00010111. Вторая часть набора является «отражением» первой относительно середины с заменой 0 на 1 и обратно; это и есть самодвойственность.

2) Пример здесь тривиален: можно взять тождественную функцию $%x$%. Подходит также отрицание $%\bar$%, а если нужен пример функции, существенно зависящей от трёх переменных, то годится $%x+y+z$% (сумма по модулю 2). Здесь сразу ясно, что при замене каждой переменой на противоположную к сумме прибавляется единица.

отвечен 11 Дек ’15 21:50

falcao
300k ● 9 ● 38 ● 55

Полные системы функций. Теорема Поста о полной системе функций

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

функции, сохраняющие константу [math]T_0[/math] и [math]T_1[/math] ,
самодвойственныые функции [math]S[/math] ,
монотонные функции [math]M[/math] ,
линейные функции [math]L[/math] .

Замкнутые классы булевых функций

Класс функций сохраняющих ноль [math]T_0[/math] .

Определение:

Говорят, что функция сохраняет ноль, если [math]f(0, 0, \ldots, 0) = 0[/math] .

Класс функций сохраняющих единицу [math]T_1[/math] .

Определение:

Говорят, что функция сохраняет единицу, если [math]f(1, 1, \ldots, 1) = 1[/math] .

Класс самодвойственных функций [math]S[/math] .

Определение:

Говорят, что функция самодвойственна (англ. self-dual), если [math]f(\overline,\ldots,\overline)=\overline[/math] . Иными словами, функция называется самодвойственной, если на противоположных наборах она принимает противоположные значения.

Класс монотонных функций [math]M[/math] .

Определение:

Говорят, что функция монотонна (англ. monotonic function) , если [math]\forall i (a_i \leqslant b_i) \Rightarrow f(a_1,\ldots,a_n)\leqslant f(b_1,\ldots,b_n)[/math] .

Класс линейных функций [math]L[/math] .

Определение:

Говорят, что функция линейна (англ. linear function), если существуют такие [math]a_0, a_1, a_2, \ldots, a_n[/math] , где [math]a_i \in \, \forall i=\overline[/math] , что для любых [math]x_1, x_2, \ldots, x_n[/math] имеет место равенство: [math]f(x_1, x_2, \ldots, x_n) = a_0\oplus a_1\cdot x_1\oplus a_2\cdot x_2 \oplus\ldots\oplus a_n\cdot x_n[/math] .

Количество линейных функций от [math]n[/math] переменных равно [math]~2^[/math] .

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

Формулировка и доказательство критерия Поста

Набор булевых функций [math]K[/math] является полным тогда и только тогда, когда он не содержится полностью ни в одном из классов [math] S,M,L,T_0,T_1 [/math] , иными словами, когда в нем имеется хотя бы одна функция, не сохраняющая ноль, хотя бы одна функция, не сохраняющая один, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.

Необходимость.

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

Достаточность.

Докажем, что если набор [math]K[/math] не содержится полностью ни в одном из данных классов, то он является полным.

Рассмотрим функцию, не сохраняющую ноль — [math]f_0[/math] (то есть функцию, для которой [math]f_0(0) = 1[/math] ). Тогда [math] f_0(1)[/math] может принимать два значения:
1. [math]f_0(1) = 1[/math] , тогда [math]f_0(x, x, x, \ldots, x) = 1[/math] .
2. [math]f_0(1) = 0[/math] , тогда [math]f_0(x, x, x, \ldots, x) = \neg x[/math] .
1. [math]f_1(0) = 0[/math] , тогда [math]f_1(x, x, x, \ldots, x) = 0[/math] .
2. [math]f_1(0) = 1[/math] , тогда [math]f_1(x, x, x, \ldots, x) = \lnot x[/math] .
Таким образом, возможны четыре варианта:
- Мы получили функцию [math] \neg [/math] .
Используем несамодвойственную функцию [math]f_s[/math] . По определению, найдется такой вектор [math]x_0[/math] , что [math]f_s(x_0) = f_s(\lnot x_0)[/math] . Где [math]x_0 = (x_, x_, \ldots, x_)[/math] .

Рассмотрим [math]f_s(x^>, x^>, \ldots, x^>)[/math] , где либо [math]x^> = x[/math] , при [math]x_ = 1[/math] . Либо [math]x^> = \lnot x[/math] , при [math]x_ = 0 [/math] . Нетрудно заметить, что [math]f_s(0) = f_s(1) \Rightarrow f_s = \operatorname [/math] . Таким образом мы получили одну из констант.
- Мы получили [math] \neg [/math] и [math]0 \Rightarrow[/math] имеем константу, равную [math]1[/math] , поскольку [math]\lnot 0 = 1[/math] .
- Мы получили [math] \neg [/math] и [math]1 \Rightarrow[/math] имеем константу, равную [math]0[/math] , поскольку [math]\lnot 1 = 0[/math] .
- Мы получили [math]1[/math] и [math]0[/math] .
Рассмотрим немонотонную функцию [math]f_m[/math] . Существуют такие [math]x_1, x_2, \ldots, x_n[/math] , что [math]f_m(x_1, x_2, \ldots, x_, 0 , x_, \ldots, x_n) = 1[/math] , [math]f_m(x_1, x_2, \ldots, x_, 1 , x_, \ldots, x_n) = 0[/math] , зафиксируем все [math]x_1, x_2, \ldots, x_n[/math] , тогда [math]f_m(x_1, x_2, \ldots, x_, x, x_, \ldots, x_n)= \lnot x[/math] .

В итоге имеем три функции: [math] \neg [/math] , [math]0[/math] , [math]1[/math] .

Используем нелинейную функцию [math]f_l[/math] . Среди нелинейных членов [math]f_l[/math] (ее представления в виде полинома Жегалкина), выберем тот, в котором минимальное количество элементов. Все аргументы кроме двух в этом члене приравняем единице, оставшиеся два назовем [math]x_1[/math] и [math]x_2[/math] . Все элементы, не входящие в данный член, примем равными нулю. Тогда эта функция будет представима в виде [math]g_l = x_1 \land x_2 [ \oplus x_1] [\oplus x_2][ \oplus ~1][/math] , где в квадратных скобках указаны члены, которые могут и не присутствовать (остальные слагаемые будут равны нулю, поскольку в них есть как минимум один аргумент, не входящий в выбранный член, так как в выбранном члене минимальное число элементов).

Рассмотрим несколько вариантов:
1. Присутствует член [math]\oplus ~1[/math] . Возьмем отрицание от [math]g_l[/math] и член [math]\oplus ~1[/math] исчезнет.
2. Присутствуют три члена, без [math]\oplus ~1[/math] : [math]g_l= x_1 \land x_2 \oplus x_1 \oplus x_2[/math] . Составив таблицу истинности для этой функции нетрудно заметить, что она эквивалентна функции [math] \vee [/math] .
3. Присутствуют два члена, без [math]\oplus ~1[/math] . Построив две таблицы истинности для двух различных вариантов, заметим, что в обоих случаях функция истинна только в одной точке, следовательно, СДНФ функции [math]g_l[/math] будет состоять только из одного члена. Если это так, то не составляет труда выразить [math] \wedge [/math] через [math] \neg [/math] и [math]g_l[/math] . Например, если функция [math]g_l(x_1, x_2, \ldots, x_n)[/math] принимает истинное значение, когда аргументы c номерами [math]i_1, i_2, \ldots, i_m[/math] ложны, а все остальные истины, то функцию [math] \wedge [/math] можно выразить как [math]g_l([\lnot]x_1, [\lnot]x_2, \ldots, [\lnot]x_n)[/math] , где [math]\lnot[/math] ставится перед аргументами с номерами [math]i_1, i_2, \ldots, i_m[/math] .
4. Присутствует один член. Выразим [math] \wedge [/math] через [math] \neg [/math] и [math]g_l[/math] аналогично пункту 3.
В итоге получим функцию [math] \neg [/math] , а также либо функцию [math] \wedge [/math] , либо функцию [math] \vee [/math] . Поскольку функцию [math] \wedge [/math] можно выразить через [math] \vee [/math] и [math] \neg [/math] , а функцию [math] \vee [/math] через [math] \wedge [/math] и [math] \neg [/math] , то мы получили базис [math] \wedge [/math] , [math] \vee [/math] , [math] \neg [/math] . Любую булеву функцию, не равную тождественному нулю, можно представить в форме СДНФ, то есть выразить в данном базисе. Если же функция равна тождественному нулю, то ее можно представить в виде [math]x \land \lnot x[/math] .

Примеры

Согласно критерию Поста система булевых функций полна тогда и только тогда, когда она не содержится целиком ни в одном из классов [math]T_0[/math] , [math]T_1[/math] , [math]S[/math] , [math]M[/math] , [math]L[/math] .

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

Широко известны такие полные системы булевых функций:
- [math]\left\<\land,\lor,\neg\right\>[/math] (конъюнкция, дизъюнкция, отрицание);
- [math]\left\<\land,\oplus,1\right\>[/math] (конъюнкция, сложение по модулю два, константа один).
Первая система используется, например, для представления функций в виде дизъюнктивных и конъюнктивных нормальных форм, вторая — для представления в виде полиномов Жегалкина.

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

Теорема о максимальном числе функций в базисе: максимально возможное число булевых функций в базисе — четыре.

Иногда говорят о системе функций, полной в некотором замкнутом классе, и, соответственно, о базисе этого класса. Например, систему [math]\left\<\oplus,1\right\>[/math] можно назвать базисом класса линейных функций.

См. также
- Булевы функции
- Суперпозиции
- Полином Жегалкина
Источники информации
- Википедия — Критерий Поста
- Википедия — Замкнутые классы булевых функций
- Образовательный сайт MiniSoft
- Post’s lattice
- Лекции по дискретной математике
Полные булевы функции Текст научной статьи по специальности «Математика»

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

i Надоели баннеры? Вы всегда можете отключить рекламу.

Похожие темы научных работ по математике , автор научной работы — Горюшкин Александр Петрович

Машинное решение задач дискретной математики
Об одноэлементной функциональной полноте в алгебре булевых функций
Передача двухкомпонентных кодов по бинарному симметричному каналу без памяти
Методика расчета цилиндрических оболочек при периодических краевых нагрузках
Контактная задача для двухслойного цилиндра
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
i Надоели баннеры? Вы всегда можете отключить рекламу.

Full boolean functions

This article covers the problems connected with the functional fullness of Boolean functions. The results may be used in the study of the structure of subalgebas algebras of the Boole functions.

Текст научной работы на тему «Полные булевы функции»

ПОЛНЫЕ БУЛЕВЫ ФУНКЦИИ А.П. Горюшкин

Камчатский государственный технический университет, г. Петропавловск-Камчатский, 683003

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

Ключевые слова: булева функция, полная система, самодвойственность, полином Жегалкина.

Full boolean functions. A.P. Goryushkin (Kamchatka State Technical University, Petropavlovsk-Kamchatskiy, Russia, 683003)

This article covers the problems connected with the functional fullness of Boolean functions. The results may be used in the study of the structure of subalgebas algebras of the Boole functions.

Key words: Boolean function, full system, duality, Zhegalkin’s multinomial.

Булевы функции являются основным аппаратом для построения математических моделей дискретных преобразователей информации. Для алгебры булевых функций важным является вопрос о порождающих (полных) системах функций. Эта алгебра обладает

порождающими множествами, состоящими всего из одной (полной) функции.

Классическими примерами полных функций с двумя переменными являются штрих Шеффера и стрелка Пирса. Эти две функции несложно сделать функциями от большего числа переменных: функция sh(xi, х2, х„) = xjvx2v. vxn является обобщенной функцией Шеффера,

а p(xb x2, . xn) = Xj & x2 &. & x n — обобщенной функцией Пирса.

В представляемой работе показано, что существуют полные функции от n переменных, отличные от этих простых обобщений; и число таких функций весьма значительно:

асимптотически полные функции составляют одну четвертую всех функций от данного числа аргументов.

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

Символ n далее будет всегда обозначать натуральное число, больше единицы, а символом + обозначается сложение по модулю два. Под словом «функция» имеется в виду булева функция. Символом P» обозначим множество всех функций от n переменных, а ПП — множество полных функций из P .

Укажем сначала верхнюю границу |ПП| — числа полных функций от n переменных.

Еслиfxb x2, . xn) — функция, образующая полную систему, то

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

а это означает, в частности, что f немонотонна.

Оставшиеся 2n — 2 строк таблицы значений для функции f(x1, x2, ., xn) могут быть заполнены

2 различными способами. По теореме Поста о функциональной полноте [1, стр. 165]

из этих 2 функций все, не являющиеся линейными или самодвойственными, будут полными. Но там точно будут и линейные, и самодвойственные, поэтому число полных функций от n

переменных строго меньше 2 , и, следовательно, относительная плотность полноты меньше

Оказывается, что эта (на первый взгляд, весьма приблизительная) оценка асимптотически

является точной, то есть предел lim

существует и равен —.

Чтобы это увидеть, достаточно найти нижнюю границу для \П»\ .

Полином Жегалкина, представляющий полную функцию ^х1, х2, . хп), содержит четное число одночленов, в противном случае _Д1, 1, . 1) = 1. Свободный член полинома равен единице, иначе ДО, 0, ., 0) = 0.

Пусть функцияАх\, х2, . хп) имеет единичный свободный член и нечетное число одночленов в полиноме Жегалкина, тогда полином ее двойственной функции Лх\ + 1, х2 + 1, . хп + 1) + 1 будет уже без свободного члена. Это значит, что самодвойственная функция с единичным свободным членом имеет четное число одночленов в полиноме Жегалкина. Следовательно, самодвойственная функция, не сохраняющая нуль, не сохраняет и единицу.

Наоборот, пусть функция Дх1, х2, . хп) не сохраняет единицу, то есть число одночленов в ее полиноме Жегалкина четное. Тогда /*(х1, х2, . хп) имеет единичный свободный член. Если f — самодвойственная, то и у функции f в ее полиноме Жегалкина должен быть свободный член, равный единице. Это значит, что самодвойственная функция, не сохраняющая единицу, не сохраняет и нуль.

Совершенная конъюнктивная форма самодвойственной функции получается из совершенной дизъюнктивной формы при переходе к двойственной функции. Поэтому самодвойственная функция принимает значение 0 в точности столько же раз, сколько и значение 1.

Пусть g — функция от п переменных, не сохраняющая ни нуль, ни единицу и принимающая значение 0 в точности столько же раз, сколько и значение 1. Чтобы задать таблицу значений для g достаточно ровно половину 2″ — 2 строк таблицы заполнить единицами (оставшаяся половина заполнится нулями). Следовательно, число функций g с перечисленными свойствами равно числу

-элементных подмножеств множества, состоящего из 2п —2 элементов. Таким образом,

число самодвойственных функций, не сохраняющих ни 0, ни 1, не превышает числа

2-2 2”-1 ! 2″-2 — 2Л~1 -1 !

Число всех функций от п переменных, не сохраняющих ни нуль, ни единицу, равно 22

и поэтому число полных функций от п переменных не меньше числа

2п-i | 2п _ 2вЧ -1 I

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

2»-i _ 1 I 2п — 2п~1 -1 ! 1 2п — 2 !

22” 4 2вЧ -1 ! 2п — 2пЛ -1 !• 22″

4 4 ■ 2п^ -1 • 2п^ ! 2 • 22”

При п —> да второе слагаемое алгебраической суммы стремится к нулю. Действительно,

и, используя формулу Стирлинга:

2.3.2. Основные замкнутые классы

А). Обозначим через К0 множество булевых функций F(X1, X2, …, Xn), сохраняющих константу 0, т. е. таких, что F(0, 0, … , 0) = 0.

Такими функциями являются, например, сама константа 0, конъюнкция Х1Х2, дизъюнкция , сумма по модулю два и др..

Не принадлежат классу К0 функции 1, , , и т. д.

Предложение. Класс функций К0 является замкнутым.

Доказательство. Действительно, пусть функция — является композицией функций F0, F1, … , Fs. Тогда , что и требовалось доказать.

Б). Пусть К1 – класс функций F(X1, X2, …, Xn), сохраняющих константу 1, т. е. таких, что F(1, 1, …, 1) = 1.

Например, константу 1 сохраняют функции 1, Х1Х2, , Х, и другие. Не сохраняют константу 1 функции , и т. д..

Предложение. Класс функций К1 является замкнутым.

Доказательство такое же, как и для класса К0.

В). Пусть KS – класс Самодвойственных функций F(X1, X2, …, Xn), т. е. таких, что .

Очевидно, функции и являются самодвойственными. Рассмотрим также . Тогда

— самодвойственная.

В общем случае, самодвойственность функции легко проверять по таблице истинности: если столбец значений, после замены нулей на единицы, единиц на нули и переворачивания, не меняется, то функция – самодвойственная (см. пример в 3).

Предложение. Класс KS является замкнутым.

Доказательство. Пусть функция является композицией самодвойственных функций F0, F1, …, FS. Применяя принцип двойствен-ности, находим

,

Что и требовалось доказать.

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

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

Предложение. Класс KL – линейных функций является замкнутым.

Д). Введём на множестве (Z2)n следующее отношение частичного порядка (свойства рефлексивности, антисимметричности и транзитивности легко проверяются). Если и — два упорядоченных бинарных набора, то положим , если . Если и , то ( как это и принято для отношения частичного порядка) будем писать: .

Определение. Булева функция F(X1, X2, …, Xn) называется монотонной, если для любых бинарных наборов и таких, что выполняется .

Монотонными являются, например функции 0, 1, Xy, . В общем случае, монотонность, функции легко проверить по диаграмме Хассе данного отношения, которая представляет собой N-мерный куб. В вершинах куба запишем соответствующие значения функции. Если найдётся хотя бы одно ребро, в верхней вершине которого записан 0 а в нижней 1, то функция – не монотонная; в противном случае, если, поднимаясь по рёбрам, значение функции не уменьшается, то она – монотонная. Ниже приведены примеры немонотонной функции F(X, Y) (ребро, на котором не выполняется условие монотонности, выделено) и монотонной функции G(X, Y, Z).

F(X, y)
Похожие публикации: