Линейные функции

Определение. Функция называется линейной, если её полином Жегалкина не содержит конъюнкций. Общий вид линейной функции
f = C ₀ Å C ₁× x ₁Å C ₂× x ₂ Å… Å C _n× x _n.

Число различных линейных функций от не более чем n переменных определяется формулой N = 2ⁿ⁺¹.

Суперпозиция линейных функций есть функция линейная, следовательно, множество линейных функций образуют класс линейных функций, обозначаемый как L. Базисом класса L служит множество { x Å y, 1}

23. Замкнутые системы

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

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

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

1. Любое множество является подмножеством своего замыкания: .

2. Замыкание подмножества является подмножеством замыкания: .
Следует заметить, что из строгого вложения множеств следует лишь нестрогое вложение их замыканий: .

3. Многократное применение операции замыкания эквивалентно однократному: .

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

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

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

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

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

§ Класс функций, сохраняющих константу 0:
.

§ Класс функций, сохраняющих константу 1:
.

§ Класс самодвойственных функций:
.

§ Класс монотонных функций:
.

§ Класс линейных функций:
.

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

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

§ Непустое пересечение замкнутых классов снова является замкнутым классом.

§ Объединение замкнутых классов может замкнутым классом не являться.

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

§ Дополнение замкнутого класса булевых функций до множества всех булевых функций замкнутым классом не является