Короткі теоретичні відомості

1. Класами Поста називаються наступні 5 класів: , , , , .

2. Клас функцій, що зберігає константу 0:

3. Клас функцій, що зберігає константу 1:

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

.

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

.

Кажуть, що набір передує набору і пишуть , якщо для .

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

.

Замиканням множини бф u називається множина всіх суперпозицій функцій класу u і позначається .

Клас u називається функціонально замкненим, якщо .

Теорема. Класи Поста функціонально замкнені.

Клас функцій u називається функціонально повним, якщо .

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

Теорема Поста. Множина бф u є функціонально повним тоді і тільки тоді, коли для кожного з класів Поста знайдеться в множині u функція, яка не належить цьому класу.

Назва булевої Функції	Позначення			M	L	S
Константа 0		+	–	+	+	–
Константа 1		–	+	+	+	–
Заперечення		–	–	–	+	+
Кон’юнкція		+	+	+	–	–
Диз’юнкція		+	+	+	–	–
Додавання за модулем 2	або	+	–	–	+	–
Еквівалентність		–	+	–	+	–
Імплікація		–	+	–	–	–
Штрих Шиффера		–	–	–	–	–
Стрілка Пірса		–	–	–	–	–

Поиск по сайту: