Спеціальні класи та функціональна повнота системи функцій алгебри логіки. Теорема Поста (стр. 2 из 5)
Визначення. Множина функцій алгебри логіки А називається повною системою (в Р2), якщо будь-яку функцію алгебри логіки можна виразити формулою над А.
Теорема 1[1, ст.6]. Система А={
} є повною.Доведення. Якщо функція алгебри логіки
відмінна від тотожного нуля, то f виражається у вигляді досконалої диз’юнктної нормальної форми, в яку входять лише диз’юнкція, кон’юнкція та заперечення. Якщо ж 
, то 
. Теорема доведена.Лема 1[1, ст.6]. Якщо система А – повна, і будь-яка функція може бути виражена формулою над іншою системою В, то В – теж повна система.
Доведення. Розглянемо довільну функцію алгебри логіки
і дві системи функцій А={g1, g2,…} і B={h1, h2,…}. Оскільки система А повна, функція може бути виражена у вигляді формули над нею 
, де 
, тобто функція представляється увигляді 
, що означає що вона може бути представлена формулою над В. Перебираючи таким чином всі функції алгебри логіки, отримаємо, що система В також повна. Лема доведена.Теорема 2[1, ст.6]. Такі системи є повними в Р2
1.
;2.
;3.
;4.
Доведення.
1. Відомо (теорема 1), що система А=
повна. Покажемо, що система В= повна. З закону де Моргана 
отримуємо, що 
, тобто кон’юнкція виражається через диз’юнкцію і заперечення, і всі функції системи А виражаються формулами над системою В. Система В повна (лема 1).2. Аналогічно пункту 1:
= 
із леми 1 випливає, що вираз пункту 2 є правильний.3.
згідно леми 1 система повна.4.
згідно леми 1 система повна.Розділ 2. Спеціальні класи функцій алгебри логіки
2.1 Замкнені класи
Визначення. Нехай А
Р. Тоді замиканням А називається множина всіх функцій алгебри логіки, які можна виразити формулами над А.Позначення :
.Мають місце наступні властивості
1.
;2.
;3.
.Визначення. Система функцій алгебри логіки А називається повною, якщо
.Визначення. Нехай А
Р. Тоді система А називається замкнутим класом, якщо замикання А збігається з 
.Теорема 3[1, ст.8]. Нехай А замкнений клас, А
Р2 і В А. Тоді В – неповна система (підмножина неповної системи буде також неповна система).Доведення
отже В – неповна система.
Теорема доведена
Приклади замкнених класів
Клас
Класу
належать такі функції: 
Класу
не належать такі функції: 
Теорема 4[1, ст.8]. Клас
– замкнений .Доведення
Нехай
Розглянемо функцію
Серед змінних функцій
можуть зустрітись однакові, тому в якості змінних функції 
візьмемо всі різні із них.Тоді
, отже функція також зберігає 0. Розглянутий тільки окремий випадок (без змінних в якості аргументів). Проте, оскільки тотожна функція зберігає нуль, підстановка простих змінних еквівалентна підстановці тотожної функції, теорема доведена.Клас
Класу
належать такі функції: 
Класу
не належать такі функції: 
Теорема 5[1, ст.8]. Клас
– замкнений.Доведення
Нехай
Розглянемо функцію
Серед змінних функцій
можуть зустрітись однакові, тому в якості змінних функції візьмемо всі різні із них.Тоді
, отже функція також зберігає 1. Розглянутий тільки окремий випадок (без змінних в якості аргументів). Проте, оскільки тотожна функція зберігає одиницю, підстановка простих змінних еквівалентна підстановці тотожної функції, теорема доведена.Клас
лінійних функцій.