Викия

Математика

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

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

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


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

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

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

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

Свойства замыкания Править

  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, целиком содержится хотя бы в одном из пяти классов Поста.

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

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

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

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

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

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

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

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

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

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


Эта статья содержит материал из статьи Замкнутые классы булевых функций русской Википедии.

Викия-сеть

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