Классы поста

  • Главная
  • Справочник
  • Алгебра
  • Дискретная математика
  • Булева алгебра и функции
  • Теорема Поста и классы

В силу теоремы о представлении любой булевой функции дизъюнктивной или конъюнктивной нормальной формой стандартный базис [cbm]{lor,cdot,overline{phantom{A}}}[/cbm] является полным множеством. Поскольку, согласно законам де Моргана, можно выразить конъюнкцию через дизъюнкцию и отрицание, равно как и дизъюнкцию можно выразить через конъюнкцию и отрицание, то при удалении из стандартного базиса одной функции, дизъюнкции или конъюнкции, при сохранении отрицания, получим снова полное множество.

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

Теорема 6.3. Пусть [cbm]F[/cbm] и [cbm]G[/cbm] — некоторые множества булевых функций, причем [cbm]F[/cbm] — полное множество. Тогда, если каждая функция из [cbm]F[/cbm] может быть представлена некоторой формулой над множеством [cbm]G[/cbm] , то [cbm]G[/cbm] — полное множество.

Из условия теоремы следует, что каждая функция [cbm]fin F[/cbm] может быть представлена некоторой формулой [cbm]Psi[/cbm] над [cbm]G[/cbm] , т.е.

Докажем, что всякая формула над [cbm]F[/cbm] эквивалентна некоторой формуле над [cbm]G[/cbm] , т.е. всякая функция [cbm]varphi[/cbm] , представляемая формулой над [cbm]F[/cbm] , может быть представлена также и некоторой формулой над [cbm]G[/cbm] . Доказательство проведем по такой схеме: сначала убедимся в справедливости утверждения для «базисных» формул, т.е. для переменных и констант из [cbm]F[/cbm] , а затем в предположении, что оно уже доказано для формул [cbm]Phi_1,ldots,Phi_n[/cbm] , где [cbm]ngeqslant1[/cbm] , докажем его для любой формулы вида [cbm]f(Phi_1,ldots,Phi_n)[/cbm] , где [cbm]fin F[/cbm] . Такой метод доказательства называют доказательством индукцией по построению формулы.

Пусть [cbm]varphi[/cbm] — какая-то формула над [cbm]F[/cbm] . Если [cbm]varphi=x[/cbm] , где [cbm]x[/cbm] — булево переменное из множества [cbm]X[/cbm] , то, поскольку каждое переменное есть, по определению, и формула над [cbm]G[/cbm] , функция [cbm]varphi[/cbm] представляется формулой над [cbm]G[/cbm] .

Если [cbm]varphi[/cbm] есть константа из [cbm]F[/cbm] , то представляющая [cbm]varphi[/cbm] формула над [cbm]G[/cbm] существует ввиду (6.17).

Рассмотрим формулу над [cbm]F[/cbm] вида [cbm]f(Phi_1,ldots,Phi_n)[/cbm] , где [cbm]n>0,~fin F[/cbm] , а [cbm]Phi_1,ldots,Phi_n[/cbm] — формулы над [cbm]F[/cbm] . Согласно предположению индукции, каждая формула [cbm]Phi_1,~i=overline{1,n}[/cbm] , может быть заменена эквивалентной ей формулой [cbm]Theta_i[/cbm] над [cbm]G[/cbm] (т.е. имеет место тождество [cbm]Phi_1=Theta_i[/cbm] над [cbm]Fcup G[/cbm] ). Тогда, используя правила эквивалентных преобразований формул (см. теорему 6.1), получим тождество

а в соответствии с (6.17) будем иметь

Правая часть тождества (6.18) и есть формула над [cbm]G[/cbm] , эквивалентная исходной формуле над [cbm]F[/cbm] .

Поскольку в силу полноты множества [cbm]F[/cbm] любая булева функция может быть представлена некоторой формулой над [cbm]F[/cbm] , а любая такая формула, как мы только что доказали, эквивалентна некоторой формуле над [cbm]G[/cbm] , то любая булева функция может быть представлена некоторой формулой над [cbm]G[/cbm] , что и доказывает полноту множества [cbm]G[/cbm] .

Пример 6.17. Рассмотрим базис Жегалкина [cbm]{oplus,cdot,1}[/cbm] . Чтобы доказать полноту этого множества, заметим, что

т.е. каждый элемент стандартного базиса может быть представлен формулой над базисом Жегалкина. Отсюда и следует (ввиду полноты стандартного базиса и теоремы 6.3) полнота базиса Жегалкина.


Любую формулу над базисом Жегалкина называют полиномом Жегалкина. Полином Жегалкина от [cbm]n[/cbm] переменных может быть записан в виде

где коэффициенты полинома [cbm]a_{i_1i_2ldots i_m}in{0;1}[/cbm] индексированы всеми возможными подмножествами множества [cbm]{1,2,ldots,n}[/cbm] (коэффициент [cbm]a_0[/cbm] соответствует пустому множеству). В частности, при [cbm]n=3[/cbm] будем иметь:

(общий вид полинома Жегалкина от трех переменных). Формула вида

называется полиномом Жегалкина первой степени от переменных. В таком полиноме отсутствуют «нелинейные» слагаемые, т.е. все коэффициенты, индексированные более чем одноэлементными подмножествами, равны 0 (и вместе с ними равны 0 все слагаемые, содержащие конъюнкции переменных).

Можно доказать следующее достаточно простое, но важное утверждение.

Теорема 6.4. Полином Жегалкина для любой булевой функции определен однозначно.

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

Пример 6.18. Пусть вектор значений булевой функции [cbm]f[/cbm] равен [cbm]11001011[/cbm] . Найдем полином Жегалкина, представляющий [cbm]f[/cbm] . Поскольку размерность вектора значений [cbm]f[/cbm] равна [cbm]2^3=8[/cbm] , то [cbm]f[/cbm] задана как функция от трех переменных. Тогда она представляется некоторым полиномом Жегалкина третьей степени, общий вид которого дает формула (6.19). Наша задача — найти такие значения коэффициентов этого полинома, при которых он представляет функцию [cbm]f[/cbm] . Ясно, что значение функции [cbm]f[/cbm] на наборе [cbm]000[/cbm] равно коэффициенту [cbm]a_0[/cbm] в формуле (6.19). Но, согласно заданному вектору значений, оно равно 1. Следовательно, [cbm]a_0=1[/cbm] . Далее,

откуда, решая уравнение относительно [cbm]a_3[/cbm] в поле [cbm]mathbb{Z}_2[/cbm] , получим [cbm]a_3=0[/cbm] ;

Чтобы найти коэффициенты [cbm]a_{12},,a_{13}[/cbm] и [cbm]a_{23}[/cbm] , нужно рассмотреть значения функции на наборах [cbm]110,,101[/cbm] и [cbm]011[/cbm] соответственно. Так, для первого набора получим

(сумма по модулю 2 любого четного числа равных слагаемых равна 0). Поскольку в то же время [cbm]f(1,1,0)=1[/cbm] , то [cbm]a_0=1[/cbm] . Аналогично [cbm]f(1,0,1)=a_{13}oplus a_0=0[/cbm] , откуда [cbm]a_{13}=1[/cbm] ; [cbm]f(0,1,1)=a_{23}oplus a_2oplus a_0=0[/cbm] , и, так как [cbm]a_2=a_0=1,~a_{23}=0[/cbm] . Наконец,

Итак, окончательно имеем [cbm]f=x_1x_2x_3oplus x_1x_2oplus x_1x_3oplus x_2oplus 1[/cbm] .


Как видно из примера 6.18, суть метода неопределенных коэффициентов состоит в следующем. Записывая полином Жегалкина сначала в общем виде, с неопределенными коэффициентами, мы выражаем значение полинома на фиксированных наборах через коэффициенты и приравниваем его заданному значению функции. Начинаем с нулевого набора и находим коэффициент [cbm]a_0[/cbm] , равный значению заданной функции на нулевом наборе. Зная его, из рассмотрения значений функции на наборах, содержащих в точности одну единицу, находим коэффициенты а,- при «одиночных» переменных (коэффициенты «линейной части» полинома). Зная их, из рассмотрения значений функции на наборах, содержащих в точности две единицы, находим коэффициенты при конъюнкциях двух переменных и т.д. При этом выполняются вычисления и решаются простейшие линейные уравнения в поле вычетов по модулю 2.

Пример 6.19. а. Рассмотрим множество [cbm]{mid}[/cbm] , состоящее из единственной функции (штриха Шеффера). Полнота этого множества следует из легко проверяемых тождеств

б. Полнота множества [cbm]{downarrow}[/cbm] , единственным элементом которого является стрелка Пирса, проверяется аналогично.

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

Определение 6.8. Функцию [cbm]f[/cbm] называют функцией, сохраняющей константу 0 (соответственно константу 1), если [cbm]f(widetilde{0})=0[/cbm] (соответственно: [cbm]f(widetilde{1})=1[/cbm] , где [cbm]widetilde{0}[/cbm] — нулевой, а [cbm]widetilde{1}[/cbm] — единичный наборы значений переменных функции [cbm]f[/cbm] .

Например, мажоритарная функция является функцией, сохраняющей и константу 0, и константу 1. Отрицание не сохраняет ни 0, ни 1, а эквивалентность сохраняет 1, но не сохраняет 0. Множество всех функций, сохраняющих константу 0 (константу 1), обозначается [cbm]T_0[/cbm] (соответственно [cbm]T_1[/cbm] ).

Наборы [cbm]widetilde{alpha}[/cbm] и [cbm]overline{widetilde{alpha}}[/cbm] из булева куба [cbm]mathbb{B}^n={0;1}^n[/cbm] (для произвольного фиксированного [cbm]n[/cbm] ) будем называть взаимно противоположными, говоря при этом также, что набор [cbm]overline{widetilde{alpha}}[/cbm] есть инверсия (или отрицание) набора [cbm]widetilde{alpha}[/cbm] (в силу единственности дополнения любого элемента булевой алгебры набор [cbm]widetilde{alpha}[/cbm] будет, очевидно, инверсией набора [cbm]overline{widetilde{alpha}}[/cbm] ).

Определение 6.9. Функцию [cbm]ginmathcal{P}_{2,n}[/cbm] называют двойственной к функции [cbm]finmathcal{P}_{2,n}[/cbm] , если для всякого [cbm]widetilde{alpha}in {0;1}^n[/cbm] имеет место [cbm]g(widetilde{alpha})= overline{f} (overline{widetilde{alpha}})[/cbm] .

Полагаем также, что константа 0 является двойственной к константе 1 и наоборот.

Пример 6.20. а. Стрелка Пирса есть функция, двойственная к штриху Шеффера, так как

б. Сумма по модулю 2 двойственна к эквивалентности, так как [cbm]xsim y=overline{xoplus y}=overline{overline{x}oplus overline{y}}[/cbm] .

Эти две функции являются и отрицанием друг друга, но неверно в общем случае, что функция д, будучи отрицанием функции [cbm]f[/cbm] , двойственна к [cbm]f:[/cbm] штрих Шеффера не есть функция, двойственная к конъюнкции, а стрелка Пирса не есть функция, двойственная к дизъюнкции, но конъюнкция двойственна к дизъюнкции и наоборот, а стрелка Пирса двойственна к штриху Шеффера и наоборот.


В общем случае в силу уже упомянутого свойства единственности дополнения в булевой алгебре функция [cbm]h[/cbm] , двойственная к функции [cbm]g[/cbm] , которая двойственна к [cbm]f[/cbm] , равна [cbm]f[/cbm] .

Определение 6.10. Функцию [cbm]finmathcal{P}_{2,n}[/cbm] называют самодвойственной, если она двойственна к себе самой, т.е.

Таким образом, функция самодвойственна тогда и только тогда, когда на взаимно противоположных наборах она принимает взаимно противоположные значения. Следовательно, для того чтобы убедиться в несамодвойственности заданной функции [cbm]f[/cbm] , достаточно найти хотя бы одну пару взаимно противоположных наборов [cbm]widetilde{alpha}[/cbm] и [cbm]overline{widetilde{alpha}}[/cbm] , таких, что значения функции на них совпадают, т.е. [cbm]f(widetilde{alpha})=f(overline{widetilde{alpha}})[/cbm] . Так, мажоритарная функция является самодвойственной, а эквивалентность — нет, поскольку при [cbm]widetilde{alpha}=(0;0)[/cbm] имеем [cbm]0sim0=1[/cbm] и [cbm]1sim1=1[/cbm] .

Множество всех самодвойственных функций (при всех [cbm]ngeqslant1[/cbm] ) обозначим [cbm]S[/cbm] .

Определение 6.11. Функцию [cbm]finmathcal{P}_{2,n}[/cbm] называют монотонной, если для любых наборов [cbm]widetilde{alpha},widetilde{beta}inmathcal{B}^n[/cbm] , таких, что [cbm]widetilde{alpha}leqslant widetilde{beta}[/cbm] , имеет место [cbm]f(widetilde{alpha})leqslant f(widetilde{beta})[/cbm] .

Другими словами, функция монотонна тогда и только тогда, когда для любого набора [cbm]widetilde{alpha}[/cbm] имеет место следующее свойство: если значение функции на наборе [cbm]widetilde{alpha}[/cbm] равно 1, то оно равно 1 и на всех наборах, строго больших (по отношению булева порядка на [cbm]mathbb{B}^n[/cbm] ) набора [cbm]widetilde{alpha}[/cbm] . Любой минимальный (относительно того же порядка) набор [cbm]widetilde{alpha}[/cbm] , для которого значение [cbm]f(widetilde{alpha})[/cbm] монотонной функции [cbm]f[/cbm] равно 1, называют нижней единицей функции [cbm]f[/cbm] . Очевидно, что вектор значений монотонной булевой функции полностью определяется множеством ее нижних единиц*. Мажоритарная функция монотонна, и множество ее нижних единиц есть [cbm]{011,101,110}[/cbm] . Штрих Шеффера — немонотонная функция, так как [cbm]00<11[/cbm] , но [cbm]0|0=1[/cbm] , а [cbm]1|1=0[/cbm] . Множество всех монотонных функций принято обозначать через [cbm]M[/cbm] .

*Нетрудно понять, что множество нижних единиц монотонной функции [cbm]f[/cbm] есть множество всех минимальных элементов множества [cbm]C_f^1[/cbm] — конституент единицы функции [cbm]f[/cbm] .

Определение 6.12. Функцию [cbm]finmathcal{P}_{2,n}[/cbm] называют линейной, если она может быть представлена полиномом Жегалкина первой степени от п переменных, т.е. формулой вида (6.20).

Множество всех линейных функций принято обозначать через [cbm]L[/cbm] .

Любая булева константа и любая проектирующая функция х являются линейными функциями. Такова, разумеется, сумма по модулю 2. Отрицание также линейно, ибо [cbm]overline{x}= xoplus1[/cbm] . Конъюнкция и дизъюнкция не являются линейными функциями, так как не могут быть представлены полиномом Жегалкина первой степени (см. теорему 6.4).

Определение 6.13. Множества функций [cbm]T_0,,T_1,,S,,M,,L[/cbm] называются классами Поста.

Замечание 6.9. Каждый класс Поста состоит из функций с соответствующим свойством для любого числа переменных. Можно доказать также, что если функция [cbm]f[/cbm] принадлежит какому-то классу Поста [cbm]C[/cbm] , то и любая функция, равная функции [cbm]f[/cbm] , принадлежит этому же классу. Другими словами, добавление или удаление фиктивных переменных не выводит за пределы любого из классов Поста.

Полезно еще заметить, что любая проектирующая функция х принадлежит одновременно всем пяти классам Поста. Действительно, если [cbm]f(x)=x[/cbm] , то [cbm]f(0)=0[/cbm] и [cbm]f(1)=1[/cbm] , то есть [cbm]fin T_0cap T_1[/cbm] . Отсюда же вытекает и самодвойственность функции [cbm]x[/cbm] . Монотонность следует из того, что [cbm]0<1[/cbm] и [cbm]f(0)=0<f(1)=1[/cbm] . Линейность очевидна.

В то же время существуют функции, не принадлежащие ни одному из классов Поста. Таков, например, штрих Шеффера. Все свойства, кроме нелинейности, следуют прямо из таблицы этой функции. Нелинейность же доказывается выводом полинома Жегалкина для штриха Шеффера: [cbm]x|y=overline{xcdot y}=xcdot yoplus1[/cbm] , что не есть полином Жегалкина первой степени.

Фундаментальным свойством каждого класса Поста является его замкнутость (в смысле определения 6.3). Это означает для любого из классов Поста [cbm]C[/cbm] , что всякая суперпозиция над [cbm]C[/cbm] снова есть элемент [cbm]C[/cbm] .


Теорема о замкнутости классов Поста

Теорема 6.5. Каждый класс Поста замкнут.

Нужно для каждого класса Поста [cbm]Cin{T_0,T_1,S,M,L}[/cbm] доказать, что замыкание [cbm][ C][/cbm] множества булевых функций [cbm]C[/cbm] совпадает с [cbm]C[/cbm] . Пусть [cbm]f(g_1,ldots,g_n)[/cbm] — какая-то суперпозиция над [cbm]C[/cbm] . Обозначим ее через [cbm]varphi[/cbm] . Без ограничения общности можно считать, что все функции [cbm]f,g_1,ldots, g_nin mathcal{P}_{2,n}[/cbm] (для некоторого [cbm]n[/cbm] ).

Рассуждаем, используя индукцию по определению суперпозиции. Если для каждого [cbm]i=overline{1,n}[/cbm] функция [cbm]g_i=x_i[/cbm] , где [cbm]x_i[/cbm] — переменное, то [cbm]varphi=f(x_1,ldots,x_n)in C[/cbm] . Предположим, что в суперпозиции [cbm]varphi[/cbm] все функции [cbm]g_i[/cbm] есть элементы класса Поста [cbm]C[/cbm] (в частности, это может быть и соответствующая проектирующая функция, которая ввиду замечания 6.9 принадлежит всем классам Поста). Докажем, что и [cbm]varphi=f(g_1,ldots,g_n)in C[/cbm] .

1. Если [cbm]C=T_0[/cbm] , то [cbm]varphi(widetilde{0})= f(g_1(widetilde{0}),ldots, g_2(widetilde{0}))= f(0,ldots,0)=0[/cbm] , так как [cbm]f,g_1,ldots,g_nin T_0[/cbm] . Следовательно, [cbm]varphiin T_0[/cbm] .

2. При [cbm]C=T_1[/cbm] рассуждаем точно так же.

3. Пусть [cbm]C=S[/cbm] . Фиксируем произвольно набор [cbm]widetilde{alpha}in {0;1}^n[/cbm] . Вычислим (используя само двойственность всех функций):

Следовательно, [cbm]varphiin S[/cbm] .

4. [cbm]C=M[/cbm] . Берем произвольно наборы [cbm]widetilde{alpha}[/cbm] и [cbm]widetilde{beta}[/cbm] так, что [cbm]widetilde{alpha}leqslant widetilde{beta}[/cbm] . Докажем, что [cbm]varphiin M[/cbm] . Имеем

так как все функции [cbm]g_i,~i=overline{1,n}[/cbm] , монотонны и тем самым вектор [cbm](g_1(widetilde{alpha}), ldots g_n(widetilde{alpha}))[/cbm] не больше вектора [cbm](g_1(widetilde{beta}), ldots g_n(widetilde{beta}))[/cbm] , а функция [cbm]f[/cbm] также монотонна. Тогда ясно, что [cbm]varphiin M[/cbm] .

5. Если же [cbm]C=L[/cbm] , то очевидно, что при подстановке в линейную функцию (полином Жегалкина первой степени) вместо ее переменных произвольных линейных функций получится снова линейная функция. Итак, мы доказали замкнутость каждого класса Поста.


Докажем теперь теорему, характеризующую одно важное свойство немонотонных функций.

Теорема 6.6. Если функция [cbm]f[/cbm] не является монотонной, т.е. [cbm]fin M[/cbm] , то найдутся два таких набора [cbm]widetilde{alpha},widetilde{beta}[/cbm] , что

и [cbm]f(widetilde{alpha})=1,~f(widetilde{beta})=0[/cbm] , т.е. эти два набора различаются значениями в точности одной компоненты, а значение функции равно О на большем наборе и равно 1 на меньшем.

Так как функция [cbm]f[/cbm] не является монотонной, то найдутся такие два набора [cbm]widetilde{gamma}[/cbm] и [cbm]widetilde{delta}[/cbm] , что [cbm]widetilde{gamma}<widetilde{delta}[/cbm] , но [cbm]f(widetilde{gamma})=1,~ f(widetilde{delta})=0[/cbm] . Строгое неравенство [cbm]widetilde{gamma}< widetilde{delta}[/cbm] означает, что найдутся такие номера (не меньше одного) [cbm]1leqslant i_1<i_2<ldots< i_kleqslant n[/cbm] , что

т.е. все компоненты наборов, кроме выделенных, с номерами [cbm]i_1,i_2,ldots,i_k[/cbm] соответственно совпадают, а все компоненты с выделенными номерами у меньшего набора равны 0, а у большего равны 1. Построим монотонно возрастающую последовательность наборов

так что для каждого [cbm]sin{1,2,ldots,k}[/cbm] набор [cbm]widetilde{gamma}_s[/cbm] получается из набора [cbm]widetilde{gamma}_{s-1}[/cbm] заменой нулевого значения компоненты с номером [cbm]i_s[/cbm] единичным. Поскольку [cbm]f(widetilde{gamma})=1[/cbm] , а [cbm]f(widetilde{delta})=0[/cbm] , то обязательно найдется такое [cbm]sin{1,2,ldots,k}[/cbm] , что [cbm]f(widetilde{gamma}_{s-1})=1[/cbm] , а [cbm]f(widetilde{gamma}_s)=0[/cbm] (на наборе [cbm]widetilde{gamma}_{s-1}[/cbm] значение функции еще равно 1, а на наборе [cbm]widetilde{gamma}_{s}[/cbm] оно уже равно 0). Полагая [cbm]widetilde{alpha}= widetilde{gamma}_{s-1}[/cbm] и [cbm]widetilde{beta}= widetilde{gamma}_{s}[/cbm] получим доказываемое.

calcsbox.com

Система булевых функций F={f1,…,fn} называется полной, если любая булева функция представима в виде терма сигнатуры (f1,…,fn}, т.е в виде суперпозиции функций из F.

Классы Поста:

1) P0={f|f(0,…,0)=0} — класс булевых функций, сохраняющих ноль

2) P1={f|f(1,…,1)=1} – класс булевых функций, сохраняющих 1

3) S={f|f+=f} – класс самодвойственных функций

4) M – класс монотонных функций. Булева функция f(x1,…,xn) называется монотонной, если для любых наборов нулей и единиц (α1,…,αn) и (β1,…,βn) из условий αi≤βi следует f(α1,…,αn)≤f(β1,…,βn)

5) Класс I – это класс линейных функций. Булева функций f(x1,…,xn) называется линейной, если в булевом кольце Классы поста функция f представима в виде Классы поста .

Каждый класс Поста замкнут относительно операций замены переменных и суперпозиции.

Теорема Поста: Система F булевых функций тогда и только тогда является полной, когда для каждого из классов P0, P1, S, M, L в системе F найдется функция, не принадлежащая этому классу..

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

Доказательство: Предположим, что существует базис F, состоящий более чем из четырех функций. По теореме Поста тогда получаем, что F состоит ровно из пяти функций, каждая из которых не принадлежит ровно одному классу Поста. Пусть f – функция из F, не принадлежащая классу P0. Тогда f(0,…,0)=1 и f(1,…,1)=1, но тогда f не принадлежит классу самодвойственных функций, а это противоречит предположения.

studopedia.ru

Чтобы составить таблицу Поста, нужно решить вопрос о принадлежности каждой из четырёх рассматриваемых функций к классам (  large P_0, P_1, S, L, M ). Если некоторая функция принадлежит тому или иному классу, то на пересечении соответствующей строки и соответствующего столбца ставится знак "плюс", если не принадлежит, то ставится знак "минус"

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

Сразу делаем вывод о нелинейности всех рассматриваемых в задаче функций.

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

2) Решим вопрос о принадлежности функций к классу (  large P_0 ). Имеем:

Итак, функции (  large f_2 ) и (  large f_3 ) сохраняют нуль, а функции (  large f_1 ) и (  large f_4 ) — не сохраняют.

3) Проверим, какие из функций принадлежат к классу (  large P_1 ). Имеем:

Вывод: все рассматриваемые функции, кроме (  large f_2 ), сохраняют единицу.

4) Выясним, какие функции принадлежат к классу (  large S ). Используя определение самодвойственной функции, получим:

Итак, ни одна из функций не принадлежит к классу самодвойственных функций.

5) Используя определения элементарных булевых функций, составим таблицы значений для функций (  large f_1, f_2, f_3, f_4 ) и выясним, являются ли они монотонными.

Рассмотрим первую и вторую строки таблицы. Функция (  large f_1 ) не является монотонной, так как

но

Рассмотрев третью и четвертую строки таблицы, делаем вывод, что функция (  large f_2 ) также не является монотонной, поскольку

но

Рассмотрим третью и седьмую строки таблицы. Функция (  large f_3 ) не является монотонной, так как

но

Рассмотрев первую и вторую строки таблицы, замечаем, что 

но

Значит, функция (  large f_4 ) также не является монотонной.

Используя полученные выше данные, составим таблицу Поста:

Согласно теореме Поста, системы (  large { f_1,f_2,f_3,f_4 } ), (  large { f_1,f_2,f_3 } ), (  large { f_1,f_2,f_4 } ), (  large { f_2,f_3,f_4 } ), (  large { f_1,f_2 } ), (  large {f_2 ,f_4 } ) полны, поскольку в каждой из них есть функция, не сохраняющая нуль, есть функция, не сохраняющая единицу, есть функция, не являющаяся самодвойственной, есть нелинейная функция, есть немонотонная функция. Системы (  large {f_1 ,f_3,f_4 } ), (  large { f_1,f_3 } ), (  large { f_1,f_4 } ), (  large { f_2,f_3 } ), (  large { f_3,f_4 } ), (  large { f_1 } ), (  large { f_2 } ), (  large { f_3 } ), (  large {f_4 } ), в силу той же теоремы, не являются полными. Но являются ли перечисленные выше полные системы базисами? Будем рассуждать, используя определение базиса булевых функций. Системы (  large { f_1,f_2 } ), (  large {f_2 ,f_4 } ) есть базисы, поскольку после удаления из них любой функции они превращаются в систему из одной функции, а все такие системы, как сказано выше, не полны. Удаляя из системы (  large { f_1,f_2,f_3 } ) функцию (  large f_3 ) получаем полную систему, удаляя из системы (  large { f_1,f_2,f_4 } ) функцию (  large f_1 ) получаем полную систему, удаляя из системы (  large { f_2,f_3,f_4 } ) функцию (  large f_3 ) получаем полную систему. Следовательно, системы (  large { f_1,f_2,f_3 } ), (  large { f_1,f_2,f_4 } ), (  large { f_2,f_3,f_4 } ) не являются базисами. Система (  large {f_1, f_2,f_3,f_4 } ) не базис, так как, например, удаление из неё функции (  large f_4 ) приводит к полной системе.

Итак, базисами являются только две системы: (  large { f_1,f_2 } ) и (  large {f_2 ,f_4 } ).

maths24.net

Теорема о замкнутости классов Поста

Теорема 6.5. Каждый класс Поста замкнут.

Нужно для каждого класса Поста [math]Cin{T_0,T_1,S,M,L}[/math] доказать, что замыкание [math][ C][/math] множества булевых функций [math]C[/math] совпадает с [math]C[/math]. Пусть [math]f(g_1,ldots,g_n)[/math] — какая-то суперпозиция над [math]C[/math]. Обозначим ее через [math]varphi[/math]. Без ограничения общности можно считать, что все функции [math]f,g_1,ldots, g_nin mathcal{P}_{2,n}[/math] (для некоторого [math]n[/math]).

Рассуждаем, используя индукцию по определению суперпозиции. Если для каждого [math]i=overline{1,n}[/math] функция [math]g_i=x_i[/math], где [math]x_i[/math] — переменное, то [math]varphi=f(x_1,ldots,x_n)in C[/math]. Предположим, что в суперпозиции [math]varphi[/math] все функции [math]g_i[/math] есть элементы класса Поста [math]C[/math] (в частности, это может быть и соответствующая проектирующая функция, которая ввиду замечания 6.9 принадлежит всем классам Поста). Докажем, что и [math]varphi=f(g_1,ldots,g_n)in C[/math].

1. Если [math]C=T_0[/math], то [math]varphi(widetilde{0})= f(g_1(widetilde{0}),ldots, g_2(widetilde{0}))= f(0,ldots,0)=0[/math], так как [math]f,g_1,ldots,g_nin T_0[/math]. Следовательно, [math]varphiin T_0[/math].

2. При [math]C=T_1[/math] рассуждаем точно так же.

3. Пусть [math]C=S[/math]. Фиксируем произвольно набор [math]widetilde{alpha}in {0;1}^n[/math]. Вычислим (используя само двойственность всех функций):

Следовательно, [math]varphiin S[/math].

4. [math]C=M[/math]. Берем произвольно наборы [math]widetilde{alpha}[/math] и [math]widetilde{beta}[/math] так, что [math]widetilde{alpha}leqslant widetilde{beta}[/math]. Докажем, что [math]varphiin M[/math]. Имеем

так как все функции [math]g_i,~i=overline{1,n}[/math], монотонны и тем самым вектор [math](g_1(widetilde{alpha}), ldots g_n(widetilde{alpha}))[/math] не больше вектора [math](g_1(widetilde{beta}), ldots g_n(widetilde{beta}))[/math], а функция [math]f[/math] также монотонна. Тогда ясно, что [math]varphiin M[/math].

5. Если же [math]C=L[/math], то очевидно, что при подстановке в линейную функцию (полином Жегалкина первой степени) вместо ее переменных произвольных линейных функций получится снова линейная функция. Итак, мы доказали замкнутость каждого класса Поста.

mathhelpplanet.com

You May Also Like

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Этот сайт использует Akismet для борьбы со спамом. Узнайте как обрабатываются ваши данные комментариев.