Курсовая работа: Спеціальні класи та функціональна повнота системи функцій алгебри логіки. Теорема Поста

Визначення. Нехай АР. Тоді замиканням А називається множина всіх функцій алгебри логіки, які можна виразити формулами над А.

Позначення :.

Мають місце наступні властивості

1. ;

2. ;

3. .

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

Визначення. Нехай АР. Тоді система А називається замкнутим класом, якщо замикання А збігається з .

Теорема 3[1, ст.8]. Нехай А замкнений клас, АР₂ і ВА. Тоді В – неповна система (підмножина неповної системи буде також неповна система).

Доведення

отже В – неповна система.

Теорема доведена

Приклади замкнених класів

Клас

Класу належать такі функції:

Класу не належать такі функції:

Теорема 4[1, ст.8]. Клас – замкнений .

Доведення

Нехай

Розглянемо функцію

Серед змінних функцій можуть зустрітись однакові, тому в якості змінних функції візьмемо всі різні із них.

Тоді , отже функція також зберігає 0. Розглянутий тільки окремий випадок (без змінних в якості аргументів). Проте, оскільки тотожна функція зберігає нуль, підстановка простих змінних еквівалентна підстановці тотожної функції, теорема доведена.

Клас

Класу належать такі функції:

Класу не належать такі функції:

Теорема 5[1, ст.8]. Клас – замкнений.

Доведення