4.3. Основні замкнуті класи логічних функцій

Існує п’ять основних замкнутих класів логічних функцій, яких називають класами Поста⁶. Розглянемо ці класи.

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

Таким чином, у множині логічних функцій є клас логічних функцій — клас функцій, які зберігають константу нуль:

Покажемо, що клас — замкнутий. Оскільки , то досить показати, що з того, що , випливає, що , тобто , що й треба було довести.

Приклад 4.5. Функціями, які зберігають константу нуль, є функції: , , , , та ін. Але , , , , тощо.

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

Оскільки існують такі функції, то в множині є відповідний клас логічних функцій  — клас функцій, які зберігають константу одиниця:

Покажемо, що клас — замкнутий. Оскільки то досить показати, що з того, що , випливає, що , тобто , що й треба було довести.

Функціями класу є функції, двоїсті до функцій класу .

Приклад 4.6. Функціями, які зберігають константу одиниця, є функції: , , , , , , та ін. Але , , , тощо.

Раніше (див. п. 2.6) ми розглядали самодвоїсті функції — такі, що .

Позначимо символом S клас самодвоїстих функцій:

.

Покажемо, що клас S — замкнутий. Нехай і нехай . Тоді, відповідно до принципу двоїстості, . Оскільки , , , …, , то:

,

що і треба було показати.

Приклад 4.7. Самодвоїстими є, наприклад, такі функцій: , , , що легко перевірити за таблицями істинності.

Визначення 4.6. Логічну функцію називають монотонною, якщо для всіх інтерпретацій, таких, що виконується нерівність .

Відповідний клас монотонних логічних функцій позначають символом М, і цей клас визначається так:

.

Клас М — замкнутий (доведення цього твердження досить складне).

Приклад 4.8. Монотонними є, наприклад, такі функції: , , , , . Немонотонними є, наприклад, функції: , .

Теорема 4.2 (критерій монотонності логічної функції). Логічна функція , відмінна від константи, монотонна тоді і тільки тоді, якщо вона є суперпозицією функцій і .

Раніше (див. п. 3.3) ми розглядали лінійні функції — такі, що їхні многочлени Жегалкіна не містять кон’юнкцій змінних, тобто є лінійними многочленами.

Позначимо символом L клас лінійних функцій:

.

Клас L — замкнутий (див. приклад 4.2.б).

Приклад 4.9. Лінійними функціями є, наприклад, функції: , , ; нелінійною, наприклад, є функція .

Зазначимо, що класи , , S, М, L — попарно різні (див. таблицю):

Табл. 4. Належність деяких функцій до класів Поста

4.4. Критерій Поста повноти системи функцій

Наведена нижче теорема є важливим критерієм повноти системи функцій .

Теорема 4.3 (критерій Поста). Система функцій повна тоді і тільки тоді, якщо вона повністю не міститься в жодному з класів , , S, М, L.

Зазначимо, що, на перший погляд, нескоротна (з якої не можна вилучити жодної функції, щоб система не втратила властивості повноти) повна система має містити не більше п’яти функцій, так, щоб кожна з них не належала кожному з п’яти класів Поста. Проте з будь-якої повної системи функцій можна вилучити підсистему, яка містить не більше, ніж чотири функції. Справді, будь-яка одна логічна функція , яка не зберігає нуль ( ), на інтерпретації з усіма одиницями або набуває значення 0 ( ) і тоді ця функція не є монотонною ( ), або набуває значення 1 ( ) і тоді ця функція не є самодвоїстою ( , , а, отже, ).

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

З таблиці видно, що: , отже, ; , отже, ; , тоді , тобто , отже, ; оскільки — функція на першій інтерпретації набуває значення 1, а на останній значення 0, то ; оскільки , то . Як ми бачимо, ця функція не належить жодному з класів Поста. Отже, відповідно до критерію Поста, вона утворює повну систему.

Важливим також є наслідок з критерію Поста.

Наслідок 4.1. Будь-який замкнутий клас , який не є повним, міститься принаймні в одному з класів , , S, М, L.

Система функцій із замкнутого класу К:

1) повна в К, якщо ;

2) є базисом К, якщо вона повна в К, але будь-яка її власна підсистема не повна в К.

Приклад 4.11. Наведемо приклади базисів для деяких множин логічних функцій:

а) система є базисом множини всіх логічних функцій ;

б) система є базисом в класі монотонних функцій М;

в) система є базисом в класі лінійних функцій L.

Критерій Поста доводить, що будь-який замкнутий клас має базис, проте потужність множини замкнутих класів злічувана.