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

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

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

• $\mathrm{\forall }f(x_1,\dots ,x_n)\in P:f(x_{i_1},\dots ,x_{i_n})\in P$ (замкнутість щодо заміни змінних);
• $\mathrm{\forall }f(x_1,\dots ,x_n),g_i(x_1,\dots ,x_n)\in P:f(x_1,\dots ,g_i(x_1,\dots ,x_n),\dots ,x_n)\in P$ (замкнутість щодо суперпозиції).

Замкненим класом функцій алгебри логіки є, наприклад, клас $P_2$ всіх функцій алгебри логіки.

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

Приклади

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

• клас функцій, що зберігають константу 0:
  $T_0=\{f(x_1,\dots ,x_n):f(0,\dots ,0)=0\}$.
• клас функцій, що зберігають константу 1:
  $T_1=\{f(x_1,\dots ,x_n):f(1,\dots ,1)=1\}$.
• клас самодвоїстих функцій:
  $S=\{f(x_1,\dots ,x_n):f(\overline{x_1},\dots ,\overline{x_n})=\overline{f(x_1,\dots ,x_n)}\}$.
• клас монотоних функцій:
  $M=\{f(x_1,\dots ,x_n):\mathrm{\forall }i(a_i\le b_i)\Rightarrow f(a_1,\dots ,a_n)\le f(b_1,\dots ,b_n)\}$.
• клас лінійних функцій:
  $L=\{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\}\}$.

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

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

• Клас кон'юнкцій K, що є замиканням множини операцій $\{\wedge ,0,1\}$. Він являє собою множину функцій виду $c_0\wedge (c_1\vee x_1)\wedge \dots \wedge (c_n\vee x_n)$.
• Класс диз'юнкцій D, що є замиканням множини операцій $\{\vee ,0,1\}$. Він являє собою множину функцій виду $c_0\vee (c_1\wedge x_1)\vee \dots \vee (c_n\wedge x_n)$.
• Клас U функцій одної змінної, що містить тільки константи, заперечення та селектор (функцію, що тотожна одній зі своїх змінних).
• Клас $O^m$ функцій (m - натуральне число, більше одиниці), в яких для довільних m наборів, на яких функція рівна нулю, знайдеться змінна, яка теж рівна нулю на всіх цих наборах.
• Класс $O^{\mathrm{\infty }}$ функцій, для яких виконується умова $f(x_1,\dots ,x_n)\ge x_i$.
• Класс $I^m$ функцій (m - натуральне число, більше одиниці), в яких для довільних m наборів, на яких функція рівна 1, знайдеться змінна, яка теж рівна 1 на всіх цих наборах.
• Класс $I^{\mathrm{\infty }}$ функцій, для яких виконується умова $f(x_1,\dots ,x_n)\le x_i$.

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

Властивості

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

Повні класи

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

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

Система булевих функцій є повною тоді і тільки тоді, коли вона не міститься повністю ні в одному із передповних класів, тобто $T_0$, $T_1$, $S$, $M$, $L$.

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

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

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

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

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

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

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

Література

• Шаблон:ЕК