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

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

2. Клас диз'юнкцій D, що є замиканням множини операцій {}. Він представляє собою множину функцій виду .

3. Клас U функцій одної змінної, що містить тільки константи, заперечення та селектор (функцію, що тотожна одній зі своїх змінних).

4. Клас функцій (m - натуральне число, більше одиниці), в яких для довільних m наборів, на яких функція рівна нулю, знайдеться змінна, яка теж рівна нулю на всіх цих наборах.

5. Клас функцій, для яких виконується умова .

6. Клас функцій (m - натуральне число, більше одиниці), в яких для довільних m наборів, на яких функція рівна 1, знайдеться змінна, яка теж рівна 1 на всіх цих наборах.

7. Клас функцій, для яких виконується умова .

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

Властивості:

1. Перетин замкнутих класів є замкнутим класом.

2. Об'єднання замкнутих класів може не бути замкнутим класом.

3. Доповнення замкнутого класа булевих функцій до множини всіх булевих функцій P₂ не є замкнутим класом.

Розділ 3. Теорема Поста

Лема 2(про несамодвоїсту функцію.) [1, ст. 10]. З будь-якої несамодвоїстої функції алгебри логіки , підставляючи замість усіх змінних функції і, можна отримати.

Доведення

Нехай

Тоді

Побудуємо функцію так:

Дійсно

Зауважимо, що підстановка задовольняє умові теореми, так

як

Лемy доведенo.

Лема 3(про немонотонну функцію.) [1, ст. 11]. З будь-якої немонотонної функції алгебри логіки , підставляючи замість усіх змінних функції , можна отримати функцію