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

Теорема 8. Клас – замкнений.

Доведення. Нехай

Тоді з принципу двоїстості випливає, що

Отже,

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

2.3 Клас монотонних функцій та його замкненість

Визначення

Нехай

Тоді

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

Клас усіх монотонних функцій.

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

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

Теорема 9. Клас - замкнений

Доведення. Оскільки тотожна функція монотонна, достатньо перевірити лише випадок суперпозиції функцій.

Нехай , для будь-якого і

Розглянемо довільні набори , такі, що . Позначимо Тоді для будь-якого маємо , тобто . Позначимо .

Тоді за визначенням і в силу монотонності функції . Але і нерівність , отже .

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

Критерій Поста формулює необхідну і достатню умову повноти для системи функцій: система булевих функцій є повна тоді і тільки тоді, коли вона не міститься повністю в жодному з класів Т₀ , Т₁ , S, M, L.

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

Прикладом повних систем із однією функцією є штрих Шеффера та стрілка Пірса.

Широко відомими є такі повні системи булевих функцій:

1. Булева алгебра — алгебраїчна структура з двома бінарними та унарною операціями (), відповідно до законів де Моргана вона не є базисом оскільки диз’юнкцію чи кон’юнкцію можна виключити.

2. Алгебра Жегалкіна (, 1 – константа одиниця) – є базисом.