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

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

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

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

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

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

де

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

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

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

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

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

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

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

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

Нехай

Тоді

Доведення.

Розглянемо

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

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

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

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

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