Викия

Математика

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

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Share

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

Эта статья нуждается в серьёзной переработке.

Критерий Поста — одна из центральных теорем в теории булевых функций, устанавливающая необходимое и достаточное условие для того, чтобы некоторый набор булевых функций обладал достаточной выразительностью, чтобы представить любую булеву функцию. Впервые сформулирован американским математиком Эмилем Постом.

В середине 60-х годов почти одновременно в СССР и во Франции появились работы, где с иных позиций и в более доступной форме излагались результаты Поста. В 80-е годы сразу целому ряду исследователей с использованием различных подходов и различной техники удалось получить достаточно компактные доказательства результатов Поста. Алгебраический подход в изучении замкнутых классов булевых функций (подалгебр итеративной алгебры Поста над множеством \mathsf{B}=\{0,1\}) принадлежит А. И. Мальцеву.

Предварительные сведения Править

Булева функция — это функция типа \mathsf{B}^n\to\mathsf{B}, где \mathsf{B}=\{0,1\}, а nарность. Количество различных функций арности n равно 2^{2^n}, общее же количество различных булевых функций бесконечно. Вместе с тем, очевидно, что многие функции могут быть выражены через другие, с использованием оператора суперпозиции. Например, давно известно, что из дизъюнкции и отрицания можно, используя законы де Моргана, получить конъюнкцию. Кроме того, любая булева функция (за исключением тождественной единицы) может быть представленна в виде ДНФ то есть в терминах конъюнкции, дизъюнкции и отрицания. Возникает естественный вопрос: как определить, будет ли данный набор функций достаточным, чтобы представить любую булеву функцию. Такие наборы называются функционально полными. Теорема Поста даёт ответ на этот вопрос. Поскольку условие теоремы является необходимыми и достаточным, её называют также критерием.

Идея теоремы состоит в том, чтобы рассматривать множество всех булевых функций \mathsf{PA} как алгебру относительно операции суперпозиции. Сейчас она носит имя алгебра Поста. Эта алгебра содержит, в качестве своих подалгебр, множества функций, замкнутых, относительно суперпозиции. Их называют ещё замкнутыми классами. Пусть ~R — некоторое подмножество \mathsf{PA}. Замыканием [R] множества ~R называется минимальная подалгебра \mathsf{PA}, содержащая ~R. Иными словами, замыкание состоит из всех функций, которые являются суперпозициями ~R. Очевидно, что ~R будет функционально полно тогда и только тогда, когда [R] = \mathsf{PA}. Таким образом, вопрос, будет ли данный класс функционально полон сводится к проверке того, совпадает ли его замыкание с \mathsf{PA}.

Оператор [\_], является оператором замыкания. Иными словами, он обладает (среди прочих) свойствами:


  • R\subseteq[R],
  • ~[[R]]=[R],
  • R_1\subseteq R_2 \Rightarrow [R_1]\subseteq [R_2]


Говорят, что множество функций ~Q порождает замкнутый класс ~R (или класс ~R порождается множеством функций ~Q), если ~[Q]=R. Множество функций ~Q называется базисом замкнутого класса ~R, если ~[Q]=R и ~[Q_1]\ne R для любого подмножества ~Q_1 множества ~Q, отличного от ~Q.

Если к подалгебре \mathsf{PA}, не совпадающей с \mathsf{PA} прибавить один элемент, ей не принадлежащий, и образовать замыкание, результатом будет новая подалгебра, содержащая данную. При этом, она совпадёт с \mathsf{PA}, в том и только в том случае, если между исходной подалгеброй, и \mathsf{PA} нет никаких других подалгебр, то есть, если исходная подалгебра была максимальной. Таким образом, для того, чтобы проверить, что данное множество функций ~R функционально полно, достаточно убедится, что оно не входит целиком ни в одну из максимальных подалгебр \mathsf{PA}. Оказывается, что таких подалгебр всего пять, и вопрос принадлежности к ним может быть решён просто и эффективно.

Двойственность, монотонность, линейность. Критерий полноты Править

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

  • Если ~Rзамкнутый класс, то ~R^* — также замкнутый класс.
  • Множество ~S образует замкнутый класс.
  • Если множество ~Q порождает замкнутый класс ~R, то множество ~Q^* порождает замкнутый класс ~R^*. В частности, если ~Qбазис класса ~R, то ~Q^*базис класса ~R^*.

Перейдем теперь к выяснению полноты конкретных наборов функций.

Основные классы функций Править

** Функция ~n переменных называется самодвойственной, если на противоположных наборах она принимает противоположные значения, то есть самодвойственная функция ~f(x_1, x_2,\dots,x_n) удовлетворяет условию f (x_1,x_2,\dots,x_n)=\overline{f(\bar{x}_1,\bar{x}_2,\dots,\bar{x}_n)} Например, функции x, \bar{x} — являются самодвойственными, а функции 0, 1 — не являются.

Теорема о замкнутости основных классов функций Править

Отметим, что ни один из замкнутых классов ~S,M,L,T_0,T_1 целиком не содержится в объединении остальных четырёх. Это вытекает из следующих соотношений:

  1. \{\bar{x},xy+xz+yz\}\subset S\setminus(M\cup L\cup T_0\cup T_1)
  2. \{0,1,x\lor y\}\subset M\setminus(S\cup L\cup T_0\cup T_1)
  3. \{1,x+y\}\subset L\setminus(S\cup M\cup T_0\cup T_1)
  4. \{x+y,xy\}\subset T_0\setminus(S\cup M\cup L\cup T_1)
  5. \{x+y+1,x\lor y\}\subset T_1\setminus(S\cup M\cup L\cup T_0)

Всякий замкнутый класс булевых функций, отличный от ~P_2, целиком содержится хотя бы в одном из классов ~S,M,L,T_0,T_1.

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

Критерий Поста — теорема, которая позволяет определить, является ли полным набор булевых функций (полный набор значит, что любая [другая] булева функция записывается в виде формулы, где связками служат функции набора). Предложен американским математиком Эмилем Постом.

Набор булевых функций тогда и только тогда является полным, когда он не содержится ни в одном из пяти классов («предполных»):

  • монотонные функции (функция монотонно не убывает по каждому из своих аргументов);
  • функции, сохраняющие нуль (функция от нуля даёт ноль);
  • функции, сохраняющие единицу (функция от единицы даёт единицу);
  • линейные функции (функция представима многочленом, в котором каждый член состоит из одной переменной);
  • самодвойственные функции (функция двойственна сама себе).

Литература Править

  • С. С. Марченков, «Замкнутые классы булевых функций»
  • Образовательный сайт MiniSoft

См. также Править


Эта статья содержит материал из статьи Критерий Поста русской Википедии.

Викия-сеть

Случайная вики