Замкнений клас функцій алгебри логіки

За́мкнений клас фу́нкцій а́лгебри ло́гіки — така множина P функцій алгебри логіки, замикання якої відносно операції суперпозиції збігається з ним самим, тобто [P] = P.

Тобто, довільна функція, яку можна представити формулою з використанням функцій множини P, також входить в цю множину:

• ${\displaystyle \forall f(x_{1},\ldots ,\ x_{n})\in P:\;\;f(x_{i_{1}},\ldots ,\ x_{i_{n}})\in P}$ (замкнутість щодо заміни змінних);
• ${\displaystyle \forall f(x_{1},\ldots ,\ x_{n}),\ g_{i}(x_{1},\ldots ,\ x_{n})\in P:\;\;f(x_{1},\ldots ,\ g_{i}(x_{1},\ldots ,\ x_{n}),\ \ldots ,\ x_{n})\in P}$ (замкнутість щодо суперпозиції).

Замкненим класом функцій алгебри логіки є, наприклад, клас ${\displaystyle ~P_{2}}$ всіх функцій алгебри логіки.

В 1941 році Еміль Пост надав повний опис замкнених класів, який назвали решіткою Поста.

Приклади

Особливо важливими замкнутими класами є так звані передповні класи:

• клас функцій, що зберігають константу 0:
  ${\displaystyle T_{0}=\left\{f(x_{1},\dots ,x_{n}):\ f(0,\dots ,0)=0\right\}}$.
• клас функцій, що зберігають константу 1:
  ${\displaystyle T_{1}=\left\{f(x_{1},\dots ,x_{n}):\ f(1,\dots ,1)=1\right\}}$.
• клас самодвоїстих функцій:
  ${\displaystyle S=\left\{f(x_{1},\dots ,x_{n}):\ f({\overline {x_{1}}},\dots ,{\overline {x_{n}}})={\overline {f(x_{1},\dots ,x_{n})}}\right\}}$.
• клас монотоних функцій:
  ${\displaystyle M=\left\{f(x_{1},\dots ,x_{n}):\ \forall i(a_{i}\leq b_{i})\Rightarrow f(a_{1},\dots ,a_{n})\leq f(b_{1},\dots ,b_{n})\right\}}$.
• клас лінійних функцій:
  ${\displaystyle L=\left\{f(x_{1},\dots ,x_{n}):\ f(x_{1},\dots ,x_{n})=a_{0}\oplus a_{1}x_{1}\oplus \dots \oplus a_{n}x_{n},\;a_{i}\in \{0,1\}\right\}}$.

Ні один з передповних класів не міститься повністю в об'єднанні чотирьох інших класів; довільний замкнутий клас, відмінний від ${\displaystyle P_{2}}$, повністю міститься в хоча б в одному з п'яти передповних класів.

Іншими важливими замкнутими класами є:

• Клас кон'юнкцій K, що є замиканням множини операцій ${\displaystyle \{\wedge ,0,1\}}$. Він являє собою множину функцій виду ${\displaystyle c_{0}\wedge (c_{1}\vee x_{1})\wedge \ldots \wedge (c_{n}\vee x_{n})}$.
• Класс диз'юнкцій D, що є замиканням множини операцій ${\displaystyle \{\vee ,0,1\}}$. Він являє собою множину функцій виду ${\displaystyle c_{0}\vee (c_{1}\wedge x_{1})\vee \ldots \vee (c_{n}\wedge x_{n})}$.
• Клас U функцій одної змінної, що містить тільки константи, заперечення та селектор (функцію, що тотожна одній зі своїх змінних).
• Клас ${\displaystyle O^{m}}$ функцій (m - натуральне число, більше одиниці), в яких для довільних m наборів, на яких функція рівна нулю, знайдеться змінна, яка теж рівна нулю на всіх цих наборах.
• Класс ${\displaystyle O^{\infty }}$ функцій, для яких виконується умова ${\displaystyle f(x_{1},\ldots ,x_{n})\geq x_{i}}$.
• Класс ${\displaystyle I^{m}}$ функцій (m - натуральне число, більше одиниці), в яких для довільних m наборів, на яких функція рівна 1, знайдеться змінна, яка теж рівна 1 на всіх цих наборах.
• Класс ${\displaystyle I^{\infty }}$ функцій, для яких виконується умова ${\displaystyle f(x_{1},\ldots ,x_{n})\leq x_{i}}$.

В 1941 році Еміль Пост показав, що довільний замкнутий клас є перетином скінченної кількості вищеописаних класів. Також Пост встановив, що довільний замкнутий клас може бути порождений скінченним базисом.

Властивості

• Перетин замкнутих класів є замкнутим класом.
• Об'єднання замкнутих класів може не бути замкнутим класом.
• Доповнення замкнутого класа булевих функцій до множини всіх булевих функцій ${\displaystyle P_{2}}$ не є замкнутим класом.

Повні класи

Множина A функцій алгебри логіки називається повною системою, якщо її замикання збігається з множиною всіх функцій (для двозначної логіки [A] = P₂).

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

Система булевих функцій є повною тоді і тільки тоді, коли вона не міститься повністю ні в одному із передповних класів, тобто ${\displaystyle T_{0}}$, ${\displaystyle T_{1}}$, ${\displaystyle S}$, ${\displaystyle M}$, ${\displaystyle L}$.

Повна система називається базисом, якщо вона перестає бути повною при виключенні з неї довільної функції.

Прикладами повних систем із однієї функції є штрих Шефера та стрілка Пірса.

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

• ${\displaystyle \left\{\land ,\lor ,\neg \right\}}$ (кон'юнкція, диз'юнкція, заперечення) — відповідно до законів де Моргана не є базисом (кон'юнкцію чи диз'юнкцію можна виключити);
• ${\displaystyle \left\{\land ,\oplus ,1\right\}}$ (кон'юнкція, виключна диз'юнкція, константа 1) — є базисом.

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

Максимальна кількість булевих функцій в базисі — 4.

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

Література

• Енциклопедія кібернетики : у 2 т. / за ред. В. М. Глушкова. — Київ : Гол. ред. Української радянської енциклопедії, 1973.