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

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

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

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


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

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


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


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


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


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


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

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


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


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


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


0=g(1,\ldots,1)= g\bigl(f_0(x,\ldots,x),\ldots, f_0(x,\ldots,x)\bigr).

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


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


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


\overline{x}=f_0(x,\ldots,x).

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


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}

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


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


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).

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


\chi(x,y)=xy\oplus ax\oplus by\oplus c\,,

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


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


\chi(x,y)= f_L(0,\ldots,0, \underbrace{x}_{i_1}, 0,\ldots,0, \underbrace{x}_{i_m}, 0,\ldots,0, <br />\underbrace{y}_{i_{m+1}}, 0,\ldots,0, \underbrace{y}_{i_k}, 0,\ldots,0),

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


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


\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}

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



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


\begin{aligned} \mathit{Table~6.6}~&\\ \begin{array}{|c|c|c|c|c|c|} \hline & T_0& T_1& S& M& L\\\hline f_1 & & & & & \\\hline f_2 & & & & & \\\hline \vdots & & & & & \\\hline f_n & & & & & \\\hline \end{array}& \end{aligned}

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




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


\begin{aligned}\mathit{Table~6.7}~&\\ \begin{array}{|c|c|c|c|c|c|} \hline & T_0& T_1& S& M& L\\\hline \sim & -& +& -& -&+ \\\hline \lor & +& +& -& +&- \\\hline 0 & +& -& -& +&+ \\\hline \end{array}& \end{aligned}

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


x_1\lor x_2=x_1\cdot x_2\oplus x_1\oplus x_2\,.

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


x_1\cdot x_2=\chi(x_1\oplus1, x_2\oplus1)\oplus1\,.

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


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

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


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


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


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

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


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

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


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


\begin{aligned}\mathit{Table~6.8}~&\\ \begin{array}{|c|c|c|c|c|c|} \hline & T_0& T_1& S& M& L\\\hline f_1 & -& -& -& -&? \\\hline f_2 & +& -& -& -&- \\\hline \end{array}& \end{aligned}

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


\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}

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


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).

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


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\,.

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


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


\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}

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

Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"

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


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

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