Полные системы функций. Теорема Поста о полной системе функций
Американский математик Эмиль Пост сформулировал необходимое и достаточное условие полноты системы булевых функций. Для этого он ввел в рассмотрение следующие замкнутые классы булевых функций:
- функции, сохраняющие константу [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]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] может принимать два значения:
- [math]f_0(1) = 1[/math] , тогда [math]f_0(x, x, x, \ldots, x) = 1[/math] .
- [math]f_0(1) = 0[/math] , тогда [math]f_0(x, x, x, \ldots, x) = \neg x[/math] .
- [math]f_1(0) = 0[/math] , тогда [math]f_1(x, x, x, \ldots, x) = 0[/math] .
- [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] , где в квадратных скобках указаны члены, которые могут и не присутствовать (остальные слагаемые будут равны нулю, поскольку в них есть как минимум один аргумент, не входящий в выбранный член, так как в выбранном члене минимальное число элементов).
Рассмотрим несколько вариантов:
- Присутствует член [math]\oplus ~1[/math] . Возьмем отрицание от [math]g_l[/math] и член [math]\oplus ~1[/math] исчезнет.
- Присутствуют три члена, без [math]\oplus ~1[/math] : [math]g_l= x_1 \land x_2 \oplus x_1 \oplus x_2[/math] . Составив таблицу истинности для этой функции нетрудно заметить, что она эквивалентна функции [math] \vee [/math] .
- Присутствуют два члена, без [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] .
- Присутствует один член. Выразим [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
- Лекции по дискретной математике
Научный форум dxdy
Последний раз редактировалось ariel777 05.07.2019, 08:13, всего редактировалось 3 раз(а).
Не могу осилить условие линейности булевой функции. Теорию на вики https://clck.ru/GvU9Q прочитал. Но не понял практическое применение, так как нигде не могу найти примеры применения этой теории.
Вот, допустим, задание:Необходимо проверить, является ли функция линейной. Какие шаги я должен сделать при проверке и с чего начать?
Насколько я понимаю, конкретно эта функция уже представлена в виде многочлена Жегалкина. По определению функция является линейной если:
«. ее полином Жегалкина содержит только первые степени слагаемых.» вот этот момент про степень я недопонял. О какой степени речь? И пример какой-нибудь, пожалуйста.Re: Проверка линейности логической функции
05.07.2019, 11:21
Последний раз редактировалось Connector 05.07.2019, 12:00, всего редактировалось 5 раз(а).
Кстати, если в разложении возникает конструкция вида
, то от неё всегда легко избавиться, заменив на 
.Re: Проверка линейности логической функции
Как определить линейная булева функция или нет
Такое решение:
Если выполняется условие:
f2 = АЛЬФА0 + АЛЬФА1*x1+АЛЬФА2*x2+.АЛЬФАn*xn
то функция линейная
В моем случае
АЛЬФА0 = 1
АЛЬФА1 = 1
АЛЬФА2 = 1
АЛЬФА3 = 0
f2 = 1+x1+x2(выполняется, значит линейная)Я не пойму, что такое АЛЬФА1,АЛЬФА2, как ее находить?
Лучший ответ
Полином Жегалкина у булевой функции от трёх переменных x₁, x₂ и x₃ будет иметь вид:
f(x₁, x₂, x₃) = a₀ + a₁x + a₂x₂ + a₃x₃ + a₁₂x₁x₂ + a₁₃x₁x₃ + a₂₃x₂x₃ + a₁₂₃x₁x₂x₃, где:
коэффициенты a₀, a₁, a₂, a₃, a₁₂, a₁₃, a₂₃, a₁₂₃ ∈ .Чтобы найти эти коэффициенты, нужно подставить в полином Жегалкина (написанный выше) значения функции на различных наборах переменных и решить систему уравнений. Далее, подставив найденные коэффициенты в полином, убеждаемся в его линейности.
f(000) = 1 → a₀ = 1
f(001) = 1 → a₀ + a₃ = 1 → 1 + a₃ = 1 → a₃ = 0
f(010) = 0 → a₀ + a₂ = 0 → 1 + a₂ = 0 → a₂ = 1
f(011) = 0 → a₀ + a₂ + a₃ + a₂₃ = 0 → 1 + 1 + 0 + a₂₃ = 0 → a₂₃ = 0
f(100) = 0 → a₀ + a₁ = 0 → 1 + a₁ = 0 → a₁ = 1
f(101) = 0 → a₀ + a₁ + a₃ + a₁₃ = 0 → 1 + 1 + 0 + a₁₃ = 0 → a₁₃ = 0
f(110) = 1 → a₀ + a₁ + a₂ + a₁₂ = 1 → 1 + 1 + 1 + a₁₂ = 1 → a₁₂ = 0
f(111) = 1 → a₀ + a₁ + a₂ + a₃ + a₁₂ + a₁₃ + a₂₃ + a₁₂₃ = 1 → 1 + 1 + 1 + 0 + 0 + 0 + 0 + a₁₂₃ = 1 → a₁₂₃ = 0Тогда f(x₁, x₂, x₃) = 1 + x₁ + x₂ — линейный.
Остальные ответы
За вас это решать никто не будет. Если при разложении в полином Жигалкина функция не будет содержать конъюнкций нескольких переменных, то функция линейная. Для примера:
1) ПЖ линейной ф-ции: A0+A1x+A2y+A3z+A4j+A5k
2) ПЖ нелинейной ф-ции: A0+A1x+A2y+A3z+A4xy+A5yz+A6xzhttp:// apollyon1986. narod. ru/docs/dm/FILES/9.html здесь почитайте
дискретная-математика — Определение, является ли функция линейной
Здравствуйте! Пусть функция задана набором из $%0$% и $%1$%: $%1001011010010110$%. Можно ли как-то быстро понять, линейная она или нет, или нужно строить полином Жегалкина?
задан 14 Окт ’15 18:00
Math_2012
1.6k ● 3 ● 34 ● 132
77% принятых1 ответ
Можно. Для этого применяем то деление на «половинки», которое уже встречалось раньше. Если функция линейна, то левая половинка или равна правой, или противоположна ей. В данном случае половинки совпадают, то есть первый тест функция прошла. Совпадение говорит о том, что переменная $%x_1$% фиктивна (в противном случае она была бы слагаемым).
Теперь считаем, что нам дан «половинный» набор 10010110, и это функция от $%x_2$%, $%x_3$%, $%x_4$%. Снова разбиваем пополам, и видим противоположность наборов. Значит, $%x_2$% присутствует, и к ней прибавляется функция от $%x_3$%, $%x_4$%, заданная строкой 1001. По тому же принципу, это $%x_3$% плюс функция от $%x_4$%, заданная как 10. Из-за противоположности половинок мы видим, что $%x_4$% входит, и к ней прибавлена константа 1. Итого мы получаем, что функция линейна, и она задана формулой $%1+x_2+x_3+x_4$%.
Полином Жегалкина в общем случае находить сложнее, и если здесь один из тестов даёт «сбой», то мы знаем, что он нелинеен, хотя и не вычисляли его в явной форме.
отвечен 14 Окт ’15 18:41
falcao
300k ● 9 ● 38 ● 55@falcao: А почему совпадение двух половинок говорит о том, что $%x_1$% фиктивна?
(14 Окт ’15 19:34) Math_2012
@Math_2012: это следует из устройства таблицы, то есть из порядка перечисления наборов. Проиллюстрирую на примере трёх переменных: 000, 001, 010, 011, 100, 101, 110, 111. Видно, что сначала идут наборы вида 0ab, а потом в том же порядке 1ab. Если значения на первой половине равны соответственно значениям на второй, то f(0,a,b)=f(1,a,b) при любых a, b, что в точности означает фиктивность первой переменной. Аналогично, если первая половина противоположна второй: тогда переход к противоположному набору есть прибавление 1 (первой координаты).
(14 Окт ’15 22:19) falcao
Точно, могла и сама догадаться.