Критерий Поста

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

Необходимость условия теоремы доказывается просто: если бы для некоторого класса Поста [cbm]C[/cbm] выполнялось [cbm]F\subseteq C[/cbm] , то всякая суперпозиция над [cbm]F[/cbm] , согласно теореме 6.5, снова лежала бы в [cbm]C[/cbm] . Между тем существуют функции, не содержащиеся ни в одном из классов Поста, например штрих Шеффера (см. пример 6.9). Таким образом, нашлась бы функция, которую нельзя представить в виде суперпозиции над [cbm]F[/cbm] , что противоречит предположению о полноте [cbm]F[/cbm] .

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

Для немонотонной функции [cbm]f_M\in F\setminus M[/cbm] , согласно теореме 6.6, найдутся два таких набора [cbm]\widetilde{\alpha}[/cbm] и [cbm]\widetilde{\beta}[/cbm] , что

[cbm]\begin{aligned}\widetilde{\alpha}&= \bigl(\alpha_1,\ldots, \alpha_{i-1},0, \alpha_{i+1},\ldots, \alpha_n\bigr),\\[2pt] \widetilde{\beta}&= \bigl(\alpha_1,\ldots, \alpha_{i-1},1, \alpha_{i+1},\ldots, \alpha_n\bigr),\end{aligned}\quad f_M(\widetilde{\alpha})=1,[/cbm] а [cbm]f_M(\widetilde{\beta})=0[/cbm] .

Тогда [cbm]\overline{x}=f_M(\alpha_1,\ldots, \alpha_{i-1},x, \alpha_{i+1},\ldots, \alpha_n)[/cbm] , т.е. отрицание может быть получено из немонотонной функции подстановкой вместо некоторого ее переменного [cbm]x_i[/cbm] переменного [cbm]x[/cbm] , а вместо остальных переменных констант [cbm]\alpha_1,\ldots, \alpha_{i-1}, \alpha_{i+1},\ldots, \alpha_n[/cbm] , определяемых выбранными выше наборами [cbm]\widetilde{\alpha}[/cbm] и [cbm]\widetilde{\beta}[/cbm] . Но, вообще говоря, система [cbm]F[/cbm] может и не содержать констант. Поэтому константы 0 и 1 необходимо представить некоторыми формулами над [cbm]F[/cbm] .

Рассмотрим два случая.

Первый случай. В [cbm]F[/cbm] существует функция [cbm]f_0[/cbm] , не сохраняющая константу 0, которая сохраняет константу 1; или существует функция [cbm]f_1[/cbm] , не сохраняющая константу 1, но сохраняющая константу 0.

Если существует функция [cbm]f_0\notin T_0[/cbm] и [cbm]f_0\in T_1[/cbm] , то константа 1 представляется формулой [cbm]1=f_0(x,\ldots,x)[/cbm] , так как [cbm]f_0(0,\ldots,0)=1[/cbm] и [cbm]f_0(1,\ldots,1)=0[/cbm] . Чтобы выразить константу 0, используем любую функцию [cbm]g\in F[/cbm] , не сохраняющую константу 1:

[cbm]0=g(1,\ldots,1)= g\bigl(f_0(x,\ldots,x),\ldots, f_0(x,\ldots,x)\bigr).[/cbm]

Если же указанная функция [cbm]f_0[/cbm] не существует, но найдется функция [cbm]f_1\in T_0 \setminus T_1[/cbm] , to константы представляем формулами над [cbm]F[/cbm] аналогично (двойственным образом).

Второй случай. Любая функция из [cbm]F[/cbm] , не сохраняющая константу 0, не сохраняет и константу 1, и, наоборот, любая функция из [cbm]F[/cbm] , не сохраняющая константу 1, не сохраняет и константу 0.

Пусть [cbm]f_0(0,\ldots,0)=1[/cbm] и [cbm]f_0(1,\ldots,1)=0[/cbm] . Тогда мы получаем возможность представить отрицание следующей формулой:

[cbm]\overline{x}=f_0(x,\ldots,x).[/cbm]

Переходим к построению формул для констант, так как они потребуются нам далее при построении формулы для конъюнкции. Чтобы представить константы формулами над [cbm]F[/cbm] , воспользуемся несамодвойственной функцией [cbm]f_S[/cbm] из [cbm]F[/cbm] . Для этой функции найдется такой набор [cbm]\widetilde{\alpha}[/cbm] , что [cbm]f_S(\overline{\widetilde{\alpha}})= f_S(\widetilde{\alpha})[/cbm] . Введем функцию от одного переменного [cbm]h(x)=f_S(x^{\alpha_1},\ldots,x^{\alpha_n})[/cbm] (в предположении, что [cbm]\widetilde{\alpha}= (\alpha_1,\ldots, \alpha_n)[/cbm] . Легко видеть, что [cbm]h(0)= f_S(\overline{\widetilde{\alpha}})= f_S(\widetilde{\alpha})=h(1)[/cbm] , так как для любого [cbm]\sigma\in\{0;1\}[/cbm] имеем

[cbm]0^{\sigma}= \begin{cases}1,&\text{if}\quad \sigma=0;\\ 0,&\text{if}\quad \sigma=1;\end{cases}\quad 1^{\sigma}= \begin{cases}1,&\text{if}\quad \sigma=1;\\ 0,&\text{if}\quad \sigma=0.\end{cases}[/cbm]

Итак, значение [cbm]h(x)[/cbm] есть константа. Если она равна 0, то константу 1 представляем через функцию, не сохраняющую константу 0; если же [cbm]h(x)\equiv1[/cbm] , то константу 0 представляем через функцию, не сохраняющую константу 1.

Опишем построение формулы для конъюнкции. Берем нелинейную функцию [cbm]f_L[/cbm] из [cbm]F[/cbm] . В полиноме Жегалкина для этой функции выберем произвольное нелинейное слагаемое, содержащее наименьшее число переменных; пусть это будет слагаемое [cbm]x_{i_1},\ldots,x_{i_k}[/cbm] при [cbm]2\leqslant k \leqslant n[/cbm] . Вместо каждого переменного [cbm]x_m[/cbm] функции [cbm]f_L[/cbm] , где [cbm]m\in\{i_1,\ldots,i_k\}[/cbm] , подставим константу 0, т.е. заменим нулем все переменные, которые не вошли в выбранную ранее конъюнкцию. Получим "редуцированную" функцию

[cbm]f'_L= x_{i_1},\ldots,x_{i_k}\oplus a_{i_1}x_{i_1}\oplus\ldots\oplus a_{i_k}x_{i_k}\oplus a_0= f_L(0,\ldots,0,x_{i_1},0,\ldots,0,x_{i_k},0,\ldots,0).[/cbm]

Заметим, что коль скоро мы уже представили константы формулами над [cbm]F[/cbm] , то функция [cbm]f'_L[/cbm] тоже представлена формулой над [cbm]F[/cbm] . Разобьем теперь множество переменных [cbm]\{x_{i_1},\ldots,x_{i_k}\}[/cbm] произвольно на две части: [cbm]\{x_{i_1},\ldots,x_{i_m}\}[/cbm] и [cbm]\{x_{i_{m+1}},\ldots,x_{i_k}\}[/cbm] , где [cbm]1\leqslant m\leqslant k-1[/cbm] , и заменим все переменные первой части переменным [cbm]x[/cbm] , а переменные второй части — переменным [cbm]y[/cbm] . В результате получим функцию от двух переменных

[cbm]\chi(x,y)=xy\oplus ax\oplus by\oplus c\,,[/cbm]

где [cbm]a=a_{i_1}\oplus\ldots\oplus a_{i_m},~ b=a_{i_{m+1}}\oplus\ldots\oplus a_{i_k},~ c=a_0[/cbm] .

Ясно также, что функция х может быть представлена такой формулой над [cbm]F\colon[/cbm]

[cbm]\chi(x,y)= f_L(0,\ldots,0, \underbrace{x}_{i_1}, 0,\ldots,0, \underbrace{x}_{i_m}, 0,\ldots,0,
\underbrace{y}_{i_{m+1}}, 0,\ldots,0, \underbrace{y}_{i_k}, 0,\ldots,0),[/cbm]

т.е. функция [cbm]\chi[/cbm] получена из нелинейной функции [cbm]f_L\in F[/cbm] путем подстановки на место ее переменных с номерами [cbm]i_1,\ldots,i_m[/cbm] переменного [cbm]x[/cbm] , на место переменных с номерами [cbm]i_{m+1},\ldots,i_k[/cbm] — переменного [cbm]y[/cbm] , а на место всех остальных переменных — константы 0, уже представленной формулой над [cbm]F[/cbm] (см. выше).

Определим функцию [cbm]\psi(x,y)=\chi(x\oplus b,y\oplus a)\oplus ab\oplus c[/cbm] . Выразив эту функцию из полинома Жегалкина для [cbm]\chi[/cbm] получим

[cbm]\begin{aligned}\psi(x,y)&= \chi(x\oplus b,y\oplus a)\oplus ab\oplus c=\\[2pt] &=(x\oplus b)(y\oplus a)\oplus a(x\oplus b) \oplus b(y\oplus a) \oplus c\oplus ab \oplus c=\\[2pt] &=xy\oplus ax\oplus by\oplus ab\oplus ax\oplus ab\oplus by\oplus ab\oplus c\oplus ab\oplus c=xy,\end{aligned}[/cbm]

поскольку сумма по модулю 2 любого четного числа равных слагаемых равна 0. Итак, функция [cbm]\psi[/cbm] и есть конъюнкция. Так как прибавление к любой функции константы по модулю 2 есть либо сама исходная функция, либо ее отрицание, а отрицание уже представлено формулой над базисом [cbm]F[/cbm] , то тем самым и конъюнкция представлена такой формулой.

Чтобы исследовать полноту конкретного множества функций [cbm]F=\{f_1,f_2,\ldots,f_n\}[/cbm] , нужно построить так называемую критериальную таблицу (табл. 6.6).

[cbm]\begin{array}{|c|c|c|c|c|c|}\multicolumn{6}{r}{\mathit{Table~6.6}}\\\hline & T_0& T_1& S& M& L\\\hline f_1 & & & & & \\\hline f_2 & & & & & \\\hline \vdots & & & & & \\\hline f_n & & & & & \\\hline \end{array}[/cbm]

Строки таблицы соответствуют функциям исследуемого множества, а столбцы — классам Поста. В результате анализа функций множества [cbm]F[/cbm] клетки таблицы заполняются: если функция [cbm]f_i[/cbm] принадлежит некоторому классу Поста [cbm]C[/cbm] , то в соответствующей клетке критериальной таблицы ставится знак и "+" (плюс), а если нет, то — знак "–" (минус). Множество [cbm]F[/cbm] тогда полно, если и только если в каждом столбце таблицы стоит хотя бы один знак "–".


Пример 6.21. а. Пусть [cbm]F=\{\sim,\lor,0\}[/cbm] . Ниже приведены результаты исследования элементов этого множества на принадлежность к классам Поста, а также заполненная критериальная таблица (табл. 6.7).

[cbm]\begin{array}{|c|c|c|c|c|c|}\multicolumn{6}{r}{\mathit{Table~6.7}}\\\hline & T_0& T_1& S& M& L\\\hline \sim & -& +& -& -&+ \\\hline \lot & +& +& -& +&- \\\hline 0 & +& -& -& +&+ \\\hline \end{array}[/cbm]

При этом [cbm]1=x\sim x[/cbm] , так как функция [cbm]\sim[/cbm] (эквивалентность) не сохраняет константу 0, но сохраняет константу 1 (т.е. имеет место первый случай из доказательства достаточности условия теоремы Поста). Константа 0 принадлежит самому множеству [cbm]F[/cbm] . Поскольку [cbm]\overline{x}=x\sim0[/cbm] , то ввиду полноты множества [cbm]\{\lor,\overline{\phantom{A}}\}[/cbm] будет полным и рассматриваемое множество. Конъюнкцию можно представить формулой над [cbm]F[/cbm] , следуя доказательству теоремы Поста. Берем единственную нелинейную функцию данного множества, дизъюнкцию, и записываем для нее полином Жегалкина:

[cbm]x_1\lor x_2=x_1\cdot x_2\oplus x_1\oplus x_2\,.[/cbm]

Видно, что этот полином есть не что иное, как функция [cbm]\chi(x,y)[/cbm] при [cbm]a=b=1[/cbm] и [cbm]c=0[/cbm] . Следовательно,

[cbm]x_1\cdot x_2=\chi(x_1\oplus1, x_2\oplus1)\oplus1\,.[/cbm]

Но так как [cbm]\overline{x}=x\sim0[/cbm] , то [cbm]x_1\cdot x_2= \bigl((x_1\sim0)\lor (x_2\sim0)\bigr)\sim0[/cbm] . Этот же результат (в данном конкретном случае) можно получить и гораздо проще:

[cbm]x_1\cdot x_2= \overline{\overline{x}_1\lor \overline{x}_2}= \bigl((x_1\sim0)\lor (x_2\sim0)\bigr)\sim0.[/cbm]

Итак, исходное множество является полным.

Заметим, что это полное множество двойственно к базису Жегалкина в том смысле, что каждая из его функций двойственна к соответствующей функции базиса Жегалкина: эквивалентность двойственна к сумме по модулю 2, дизъюнкция — к конъюнкции, константа 0 — к константе 1. Полезно заметить также, что никакое собственное подмножество заданного множества не будет полным.

б. Функция [cbm]f_1[/cbm] задана картой Карно (рис. 6.21), а вектор значений функции [cbm]f_2[/cbm] есть [cbm](0,1,0,0)[/cbm] .

Критерий Поста

Для функции [cbm]f_2[/cbm] очень просто находятся ДНФ и полином Жегалкина:

[cbm]f_2=\overline{x}_1x_2=(x_1\oplus1)x_2=x_1x_2\oplus x_2\,,[/cbm]

откуда следует нелинейность функции [cbm]f_2[/cbm] . Легко показать также, что эта функция принадлежит лишь классу [cbm]T_0[/cbm] .

Так как [cbm]f_1(0,0,0,0)=1[/cbm] , а [cbm]f_1(1,1,1,1)=0[/cbm] , то функция [cbm]f_1[/cbm] не сохраняет ни константу 0, ни константу 1. Далее, эта функция несамодвойственна, поскольку [cbm]f_1(0,1,1,1)=(1,0,0,0)=1[/cbm] ; немонотонность ее следует из того, что, например, [cbm]f_1(0,0,0,0)=1[/cbm] , но [cbm]f_1(0,1,0,0)=0[/cbm] . Вопрос о нелинейности функции [cbm]f_1[/cbm] оставим пока открытым, так как даже из частично заполненной критериальной таблицы (табл. 6.8) вытекает, что множество [cbm]\{f_1,f_2\}[/cbm] полно.

[cbm]\begin{array}{|c|c|c|c|c|c|}\multicolumn{6}{r}{\mathit{Table~6.8}}\\\hline & T_0& T_1& S& M& L\\\hline f_1 & -& -& -& -&? \\\hline f_2 & +& -& -& -&- \\\hline \end{array}[/cbm]

Формулы для отрицания и констант находятся легко:

[cbm]\begin{aligned}\overline{x}&= f_1(x,x,x,x),\quad 0=f_2(x,x),\\ 1&=f_1\bigl(f_2(x,x), f_2(x,x), f_2(x,x), f_2(x,x)\bigr). \end{aligned}[/cbm]

Формулу для конъюнкции проще всего построить прямо по ДНФ для функции [cbm]f_2:[/cbm]

[cbm]x_1\cdot x_2=f_2(\overline{x}_1,x_2)= f_2 \bigl(f_1(x_1,x_1,x_1, x_1), x_2\bigr).[/cbm]

Вернемся теперь к отложенному вопросу о нелинейности функции [cbm]f_1[/cbm] . По приведенной на рис. 6.21 карте Карно можно построить одну из минимальных ДНФ, представляющих эту функцию в виде

[cbm]f_1= \overline{x}_1x_2x_4\lor x_1x_3 \overline{x}_4\lor \overline{x}_1 \overline{x}_2 \overline{x}_3\lor x_1 \overline{x}_2 \overline{x}_4\,.[/cbm]

Подставляя в последнюю формулу 0 вместо [cbm]x_1[/cbm] , а [cbm]x[/cbm] вместо [cbm]x_2[/cbm] , 1 вместо [cbm]x_3[/cbm] и [cbm]y[/cbm] вместо [cbm]x_4[/cbm] , получаем [cbm]x\cdot y=f_1(0,x,1,y),[/cbm] , что доказывает нелинейность функции [cbm]f_1[/cbm] и одновременно полноту множества [cbm]\{f_1\}[/cbm] .

Константы же можно представить формулами над базисом [cbm]\{f_1\}[/cbm] , используя несамодвойственность функции [cbm]f_1[/cbm] (см. разбор второго случая в доказательстве достаточности условия теоремы Поста): мы уже видели, что [cbm]f_1(0,1,1,1)= f_1(1,0,0,0)=1[/cbm] , т.е. набор [cbm]\widetilde{\alpha}[/cbm] из упомянутого места в доказательстве теоремы Поста есть [cbm]0111[/cbm] , и тогда функция [cbm]h[/cbm] , фигурирующая в том же месте доказательства и равная в данном случае константе 1, будет иметь вид [cbm]h(x)=f_1(\overline{x},x,x,x)[/cbm] . Но так как [cbm]\overline{x}=f_1(x,x,x,x)[/cbm] , то получаем

[cbm]\begin{aligned}1&=f_1 \bigl(f_1(x,x,x,x),x,x,x\bigr),\\ 0&=f_1 \bigl(f_1(f_1(x,x,x,x),x,x,x), f_1(f_1(x,x,x,x),x,x,x), f_1(f_1(x,x,x,x),x,x,x), f_1(f_1(x,x,x,x),x,x,x)\bigr). \end{aligned}[/cbm]

Подставив эти формулы в написанную выше формулу для конъюнкции, получим окончательно формулу над базисом [cbm]\{f_1\}[/cbm] для конъюнкции. Мы не выписываем эту формулу ввиду ее громоздкости.

Источник

Поделитесь с другими:

Если материал понравился Вам и оказался для Вас полезным, поделитесь им со своими друзьями!

Читать по теме:

Интересные статьи: