Замкнений клас функцій алгебри логіки — Вікіпедія
![]() | Було запропоновано приєднати цю статтю або розділ до Ґратка Поста, але, можливо, це варто додатково обговорити. Пропозиція з червня 2024. |
За́мкнений клас фу́нкцій а́лгебри ло́гіки — така множина P функцій алгебри логіки, замикання якої відносно операції суперпозиції збігається з ним самим, тобто [P] = P.
Тобто, довільна функція, яку можна представити формулою з використанням функцій множини P, також входить в цю множину:
- (замкнутість щодо заміни змінних);
- (замкнутість щодо суперпозиції).
Замкненим класом функцій алгебри логіки є, наприклад, клас всіх функцій алгебри логіки.
В 1941 році Еміль Пост надав повний опис замкнених класів, який назвали решіткою Поста.
Особливо важливими замкнутими класами є так звані передповні класи:
- клас функцій, що зберігають константу 0:
. - клас функцій, що зберігають константу 1:
. - клас самодвоїстих функцій:
. - клас монотоних функцій:
. - клас лінійних функцій:
.
Ні один з передповних класів не міститься повністю в об'єднанні чотирьох інших класів; довільний замкнутий клас, відмінний від , повністю міститься в хоча б в одному з п'яти передповних класів.
Іншими важливими замкнутими класами є:
- Клас кон'юнкцій K, що є замиканням множини операцій . Він являє собою множину функцій виду .
- Класс диз'юнкцій D, що є замиканням множини операцій . Він являє собою множину функцій виду .
- Клас U функцій одної змінної, що містить тільки константи, заперечення та селектор (функцію, що тотожна одній зі своїх змінних).
- Клас функцій (m - натуральне число, більше одиниці), в яких для довільних m наборів, на яких функція рівна нулю, знайдеться змінна, яка теж рівна нулю на всіх цих наборах.
- Класс функцій, для яких виконується умова .
- Класс функцій (m - натуральне число, більше одиниці), в яких для довільних m наборів, на яких функція рівна 1, знайдеться змінна, яка теж рівна 1 на всіх цих наборах.
- Класс функцій, для яких виконується умова .
В 1941 році Еміль Пост показав, що довільний замкнутий клас є перетином скінченної кількості вищеописаних класів. Також Пост встановив, що довільний замкнутий клас може бути порождений скінченним базисом.
- Перетин замкнутих класів є замкнутим класом.
- Об'єднання замкнутих класів може не бути замкнутим класом.
- Доповнення замкнутого класа булевих функцій до множини всіх булевих функцій не є замкнутим класом.
Множина A функцій алгебри логіки називається повною системою, якщо її замикання збігається з множиною всіх функцій (для двозначної логіки [A] = P2).
Критерій Поста формулює необхідну і достатнью умову повноти для системи функцій.
- Система булевих функцій є повною тоді і тільки тоді, коли вона не міститься повністю ні в одному із передповних класів, тобто , , , , .
Повна система називається базисом, якщо вона перестає бути повною при виключенні з неї довільної функції.
Прикладами повних систем із однієї функції є штрих Шефера та стрілка Пірса.
Широко відомими є такі повні системи булевих функцій:
- (кон'юнкція, диз'юнкція, заперечення) — відповідно до законів де Моргана не є базисом (кон'юнкцію чи диз'юнкцію можна виключити);
- (кон'юнкція, виключна диз'юнкція, константа 1) — є базисом.
Перша система використовується для представлення булевих функцій у вигляді диз'юнктивних та кон'юнктивних нормальных форм, друга — для представлення у вигляді поліномів Жегалкіна.
Максимальна кількість булевих функцій в базисі — 4.
Деколи говорять про систему функцій повну в деякому класі, а також про базис цього класу. Наприклад, систему можна назвати базисом класа лінійних функцій.
- Енциклопедія кібернетики : у 2 т. / за ред. В. М. Глушкова. — Київ : Гол. ред. Української радянської енциклопедії, 1973.