Спеціальні класи та функціональна повнота системи функцій алгебри логіки. Теорема Поста (стр. 3 из 5)

Визначення. Функція алгебри логіки

називається лінійною, якщо

де

Іншими словами, в поліномі лінійної функції немає доданків, що містять кон'юнкцію.

Класу

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

Класу

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

Теорема 6. Клас

– замкнений.

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

Достатньо показати, що . Дійсно, якщо не враховувати доданків , то всяку лінійну функцію можна зобразити у вигляді . Якщо тепер замість кожного підставити лінійний вираз, то вийде знову лінійний вираз, константа 0 або константа 1.

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

Визначення. Функцією двоїстою до функції алгебри логіки

називається функція

Теорема 7. Принцип двоїстості

Нехай

Тоді

Доведення.

Розглянемо

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

Клас

самодвоїстих функцій.

Визначення. Функція алгебри логіки

називається самодвоїстою, якщо Тобто .

Класу

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

Класу

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

Теорема 8. Клас

– замкнений.

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

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

Отже,

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

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

Визначення

Нехай

Тоді

Визначення. Функція алгебри логіки

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

Клас

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

Класу

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

Класу

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

Теорема 9. Клас

- замкнений

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

Нехай

, для будь-якого і

Розглянемо довільні набори

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

Тоді за визначенням

і в силу монотонності функції . Але і нерівність , отже .

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

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

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

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

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

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

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

2. Алгебра Жегалкіна (

, 1 – константа одиниця) – є базисом.

Перша система використовується для представлення булевих функцій у вигляді диз’юнктних та кон’юнктних нормальних форм, друга – для представлення у вигляді поліномів Жегалкіна.

Приклад. Система функцій {

} є функціонально повною, але система функцій { } не є функціонально повна.

Якщо у функціонально повній системі є функції константи «0» чи константи «1», то вона послаблено функціонально повна.

Приклад. Система функцій {

}, що поповнена константою одиниці , тобто {{ },1}, є послаблено функціонально повна.

Максимальна кількість булевих функцій у базисі – 4.

Деколи кажуть про систему функцій повну в деякому класі, а також про базис цього класу. Наприкад, систему {

} можна назвати базисом класу лінійних функцій.

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

Приклад. Мінімально повний базис є {

}, але система { } не є мінімально повним базисом.

Функціонально Замкнуті класи, відмінні від порожнього класу і сукупності всіх можливих булевих функцій, називаються власними функціонально замкненими класами.

Отже, довільна функція, яку можна зобразити формулою з використанням функцій множини P, також входить в цю множину

1.

- замкнутість щодо заміни змінних;

2.

- замкнутість щодо суперпозиції.

В 1941 році Еміль Пост надав повний опис замкнених класів, який назвали решіткою Поста.