Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


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

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


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


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


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


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


[math]\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,[/math] а [math]f_M(\widetilde{\beta})=0[/math].

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


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


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


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


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

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


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


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


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

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


[math]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}[/math]

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


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


[math]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).[/math]

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


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

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


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


[math]\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),[/math]

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


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


[math]\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}[/math]

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



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


[math]\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}[/math]

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




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


[math]\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}[/math]

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


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

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


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

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


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

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


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


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


Функция задана картой Карно

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


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

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


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


[math]\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}[/math]

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


[math]\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}[/math]

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


[math]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).[/math]

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


[math]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\,.[/math]

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


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


[math]\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}[/math]

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


Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved