Перегляд вихідного коду сторінки Замкнений клас функцій алгебри логіки

{{Приєднати до|Ґратка Поста|дата=червень 2024|обговорення=Вікіпедія:Об'єднання статей/30 червня 2024}}
'''За́мкнений клас фу́нкцій а́лгебри ло́гіки''' — така [[множина]] ''P'' [[функція алгебри логіки|функцій алгебри логіки]], [[замикання (математика)|замикання]] якої відносно [[композиція функцій|операції суперпозиції]] збігається з ним самим, тобто [''P''] = ''P''.

Тобто, довільна функція, яку можна представити [[математина формула|формулою]] з використанням функцій множини ''P'', також входить в цю множину:
* <math> \forall f(x_1,\ldots ,\ x_n) \in P: \;\; f(x_{i_1},\ldots ,\ x_{i_n}) \in P</math> (замкнутість щодо заміни [[змінна|змінних]]);
* <math> \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</math> (замкнутість щодо [[суперпозиція|суперпозиції]]).

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

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

== Приклади ==
Особливо важливими замкнутими класами є так звані [[передповні класи]]:
* клас функцій, що зберігають константу 0:<br /><math>T_0=\left\{f(x_1,\dots,x_n):\ f(0,\dots,0)=0\right\}</math>.
* клас функцій, що зберігають константу 1:<br /><math>T_1=\left\{f(x_1,\dots,x_n):\ f(1,\dots,1)=1\right\}</math>.
* клас самодвоїстих функцій:<br /><math>S=\left\{f(x_1,\dots,x_n):\ f(\overline{x_1},\dots,\overline{x_n})=\overline{f(x_1,\dots,x_n)}\right\}</math>.
* клас [[монотонні функції алгебри логіки|монотоних функцій]]:<br /><math>M=\left\{f(x_1,\dots,x_n):\ \forall i (a_i\le b_i) \Rightarrow f(a_1,\dots,a_n)\le f(b_1,\dots,b_n)\right\}</math>.
* клас [[лінійні функції алгебри логіки|лінійних функцій]]:<br /><math>L=\left\{f(x_1,\dots,x_n):\ f(x_1,\dots,x_n)=a_0\oplus a_1x_1\oplus\dots\oplus a_nx_n,\; a_i\in\{0,1\}\right\}</math>.
Ні один з передповних класів не міститься повністю в [[об'єднання множин|об'єднанні]] чотирьох інших класів; довільний замкнутий клас, відмінний від <math>P_2</math>, повністю міститься в хоча б в одному з п'яти передповних класів.

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

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

== Властивості ==
* Перетин замкнутих класів є замкнутим класом.
* Об'єднання замкнутих класів може не бути замкнутим класом.
* [[Доповнення множин|Доповнення]] замкнутого класа булевих функцій до множини всіх булевих функцій <math>P_2</math> не є замкнутим класом.

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

[[Критерій Поста]] формулює  необхідну і достатнью умову повноти для системи функцій.
:''Система булевих функцій є повною тоді і тільки тоді, коли вона не міститься повністю ні в одному із передповних класів, тобто <math>T_0</math>, <math>T_1</math>, <math>S</math>, <math>M</math>, <math>L</math>.''

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

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

Широко відомими є такі повні системи булевих функцій:
* <math>\left\{\land,\lor,\neg\right\}</math> ([[кон'юнкція]], [[диз'юнкція]], [[заперечення]]) — відповідно до [[закони де Моргана|законів де Моргана]] не є базисом (кон'юнкцію чи диз'юнкцію можна виключити);
* <math>\left\{\land,\oplus,1\right\}</math> (кон'юнкція, [[виключна диз'юнкція]], константа 1) — є базисом.
Перша система використовується для представлення булевих функцій у вигляді [[ДНФ|диз'юнктивних]] та [[КНФ|кон'юнктивних]] нормальных форм, друга — для представлення у вигляді [[поліном Жегалкіна|поліномів Жегалкіна]].

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

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

===Література===
*{{ЕК}}

[[Категорія:Алгебра логіки]]
[[Категорія:Теорія дискретних функціональних систем]]