Замкнутые классы булевых функций

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Замкнутый класс в теории булевых функций — такое множество P функций алгебры логики, замыкание которого относительно операции суперпозиции совпадает с ним самим: [P]=P. Другими словами, любая функция, которую можно выразить формулой с использованием функций множества P, снова входит в это же множество.

В 1941 году Эмиль Пост представил полное описание системы замкнутых классов, называемое также решеткой Поста.

Свойства замыкания функции с переменными[править | править вики-текст]

  1. Любое множество является подмножеством своего замыкания: A\subseteq[A].
  2. Замыкание подмножества является подмножеством замыкания: A\subseteq B \Rightarrow [A]\subseteq[B].
    Следует заметить, что из строгого вложения множеств следует лишь нестрогое вложение их замыканий: A\subset B \Rightarrow [A]\subseteq[B].
  3. Многократное применение операции замыкания эквивалентно однократному: [[A]]=[A].

Примеры замкнутых классов[править | править вики-текст]

Множество P_2 всех возможных булевых функций замкнуто.

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

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

Другими важными замкнутыми классами являются:

  • Класс конъюнкций K, являющийся замыканием множества \{\wedge,0,1\}. Он представляет собой множество функций вида c_0\wedge(c_1\vee x_1)\wedge\ldots\wedge(c_n\vee x_n).
  • Класс дизъюнкций D, являющийся замыканием множества \{\vee,0,1\}. Он представляет собой множество функций вида c_0\vee(c_1\wedge x_1)\vee\ldots\vee(c_n\wedge x_n).
  • Класс функций одной переменной U, содержащий только константы, отрицание и селектор (функцию, равную одному из своих аргументов на всех наборах их значений).
  • Класс O^m функций (m — любое натуральное, большее единицы число), удовлетворяющих следующему условию: для любых m наборов, на которых функция принимает нулевое значение, найдется переменная, также принимающая нулевое значение на всех этих наборах.
  • Класс O^\infty функций, для которых выполнено условие f(x_1,\ldots,x_n)\ge x_i, где x_i — одна из переменных функции.
  • Класс I^m функций (m — любое натуральное, большее единицы число), удовлетворяющих следующему условию: для любых m наборов, на которых функция принимает единичное значение, найдется переменная, также принимающая единичное значение на всех этих наборах.
  • Класс I^\infty функций, для которых выполнено условие f(x_1,\ldots,x_n)\le x_i, где x_i — одна из переменных функции.

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

Некоторые свойства замкнутых классов[править | править вики-текст]

  • Непустое пересечение замкнутых классов снова является замкнутым классом.
  • Объединение замкнутых классов может замкнутым классом не являться.
  • Замкнутый класс булевых функций, содержащий не только константы, обязательно содержит тождественную функцию.
  • Дополнение замкнутого класса булевых функций до множества всех булевых функций P_2 замкнутым классом не является.

Полные системы функций[править | править вики-текст]

Множество A функций алгебры логики называется полной системой, если замыкание этого множества совпадает с множеством всех функций. (В частности, для двузначной логики [A]=P_2.) Другими словами, должна быть возможность любую функцию алгебры логики выразить формулой с использованием функций множества A.

Критерий Поста формулирует необходимое и достаточное условие полноты системы булевых функций:
Система булевых функций полна тогда и только тогда, когда она не содержится целиком ни в одном из классов T_0, T_1, S, M, L.
В частности, если функция не входит ни в один из классов Поста, она сама по себе формирует полную систему. В качестве примера можно назвать функцию Шеффера (отрицание конъюнкции).

Широко известны такие полные системы булевых функций:

Менее известные другие полные системы булевых функций:


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

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

Иногда говорят о системе функций, полной в некотором замкнутом классе, и соответственно о базисе этого класса. Например, систему \left\{\oplus,1\right\} можно назвать базисом класса линейных функций.

Примечания[править | править вики-текст]

Литература[править | править вики-текст]