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

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

может быть натуральным числом большим или равным или бесконечностью.

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

Примеры функций, которые удовлетворяют условию , но не удовлетворяют условию : ,. Примеры функций, которые удовлетворяют условию , но не удовлетворяют условию : ,. Пример функции, которая сохраняет 0, но не удовлетворяет условию — дизъюнкция. Пример функции, которая сохраняет 1, но не удовлетворяет условию — конъюнкция. Примеры функций, которые удовлетворяют условию , но не удовлетворяет условию : — равна , если хотя бы её аргументов равны , иначе ; — равна , если ровно её аргументов равны , иначе . Двойственно, примеры функций, которые удовлетворяют условию , но не удовлетворяет условию : — равна , если хотя бы её аргументов равны , иначе ; — равна , если ровно её аргументов равны , иначе . Функция есть функция голосования. Для функции и не совпадают. Класс функций, удовлетворяющих условиям ⟨1ᵐ⟩ и ⟨0ᵐ⟩ Класс является предполным в ; класс для является предполным в ; класс не предполон нигде. В три предполных класса: , и . В два предполных класса: и . Примеры базисов для : , и . Примеры базисов для : и . Минимальное количество элементов в базисе — 1, максимальное — для равно 3, а для равно 2. В классах есть шефферовы функции.

Класс является предполным в ; класс для является предполным в ; класс не предполон нигде. В три предполных класса: , и . В два предполных класса: и . Примеры базисов для : , и . Примеры базисов для : и . Минимальное количество элементов в базисе — 1, максимальное — для равно 3, а для равно 2. В классах есть шефферовы функции.

Классы и двойственны друг другу. Пересечения с другими классами Ни один из классов и нельзя представить как пересечение системы замкнутых классов, не содержащих один из классов и . Пересечение и для даст ; пересечение и для даст . Пересечение с даст ; пересечение с даст . Пересечение с классом конъюнкций с константами даст класс конъюнкций с нулями ; пересечение с классом дизъюнкций с константами даст класс дизъюнкций с единицами .

Пересечение с классом линейных функций даст класс селекторов с нулями; аналогично при пересечении с классом дизъюнкций с константами и с классом несущественных функций : . Пересечение с классом линейных функций даст класс селекторов с единицами; аналогично при пересечении с классом конъюнкций с константами и с классом несущественных функций : . Пересечение классов и даст класс монотонных самодвойственных функций ; аналогично при пересечении с классом самодвойственных функций и при пересечении с классом самодвойственных функций: . Для пересечение классов и даст класс селекторов ; аналогично при пересечении с классом самодвойственных функций и при пересечении с классом самодвойственных функций: . Пересечение с классом констант даст класс нулей ; пересечение с классом констант даст класс единиц .

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

попарно различны и ни один из них не является пересечением каких-либо из указанных выше классов. Монотонные функции, удовлетворяющие условиям ⟨1ᵐ⟩ и ⟨0ᵐ⟩ Монотонные функции, удовлетворяющие условию , образуют замкнутый класс (обозначение Поста ). Класс является предполным в и в ; класс для является предполным в и в ; класс является предполным в . В два предполных класса: и . В два предполных класса: и . Пример базиса для : . Пример базиса для : . В базисе всегда ровно 2 функции. В классах нет шефферовых функций.

Монотонные функции, удовлетворяющие условию , образуют замкнутый класс (обозначение Поста ). Класс является предполным в и в ; класс для является предполным в и в ; класс является предполным в . В два предполных класса: и . В два предполных класса: и . Пример базиса для : . Пример базиса для : . В базисе всегда ровно 2 функции. В классах нет шефферовых функций.

Классы и двойственны друг другу. Функции, сохраняющие константы и удовлетворяющие условиям ⟨1ᵐ⟩ и ⟨0ᵐ⟩ Функции, сохраняющие константы и удовлетворяющие условию , образуют замкнутый класс (обозначение Поста ). Класс является предполным в и в ; класс для является предполным в и в ; класс является предполным в . В два предполных класса: и . В один предполный класс: . Пример базиса для : . Пример базиса для : .

Функции, сохраняющие константы и удовлетворяющие условию , образуют замкнутый класс (обозначение Поста ). Класс является предполным в и в ; класс для является предполным в и в ; класс является предполным в . В два предполных класса: и . В один предполный класс: . Пример базиса для : . Пример базиса для : .

Классы и двойственны друг другу. Монотонные функции, сохраняющие константы и удовлетворяющие условиям ⟨1ᵐ⟩ и ⟨0ᵐ⟩ Монотонные функции, сохраняющие константы и удовлетворяющие условию , образуют замкнутый класс (обозначение Поста ). Класс является предполным в , и в ; класс для является предполным в , и в ; класс является предполным в и . В два предполных класса: и . В один предполный класс . В один предполный класс: . Пример базиса для : . Пример базиса для : . Пример базиса для : .

Монотонные функции, сохраняющие константы и удовлетворяющие условию , образуют замкнутый класс (обозначение Поста ). Класс является предполным в , и в ; класс для является предполным в , и в ; класс является предполным в и . В два предполных класса: и . В один предполный класс . В один предполный класс: . Пример базиса для : . Пример базиса для : . Пример базиса для : .

Классы и двойственны друг другу. Примечания

Литература

Категория:Теория дискретных функций