класи поста
Визначення 2.7.Пусть. Кажуть, що ця функція зберігає нуль, есліF (0, 0, ..., 0) = 0. Клас ПостаP 0 Є безліч всіх функцій, що зберігають нуль.
Визначення 2.8.Пусть. Кажуть, що ця функція зберігає одиницю, есліF (1, 1, ..., 1) = 1. Клас ПостаP 1 Є безліч всіх функцій, що зберігають одиницю.
Неважко бачити, що класи P 0 і P 1 взаємно суперечливі в тому сенсі, що відображення F A F * є біекція кожного з цих класів на інший.
Нехай - безліч функцій N змінних з класу P 0. Тоді. Дійсно, будь-яка функція може бути задана таблицею. У першому рядку цієї таблиці, де значення всіх аргументів рівні 0, для функцій безлічі P 0 (N) коштує 0, а для функцій не з цієї множини коштує 1, отже, класу P 0 (N) належить рівно половина всіх функцій від n змінних , т. е. функцій.
Відзначимо ще такий факт. Нехай або. Тоді ототожненням змінних з неї получаетсяЛібо константа. Або функція. Дійсно, J (X) = F (X, ..., X) може бути однією з чотирьох функцій: 0, 1,, X. Але з тотожності F (X, ..., X) = X Слід, що.
Визначення 2.9.Класс ПостаS- це клас самодвоїстих функцій.
Визначення 2.11.Класс ПостаL- це клас лінійних функцій. Булева функція називається лінійної, якщо вона подана многочленом Жегалкина ступеня £ 1.
Приклад. Диз'юнкція - нелінійна функція, так як вона подана многочленом Жегалкина другого ступеня: X ÚY = X ÅY ÅXy.
Теорема 2.14.Каждий клас Посту замкнутий.
Следствіе.Каждий клас Посту не вичерпний.
Дійсно, неповнота замкнутого безлічі булевих функцій означає, що є булеві функції, які не належать цій множині. Виявляється, що є булеві функція, що не належать жодному з класів Посту; такі штрих Шеффера і стрілка Пірса. Покажемо це для штриха Шеффера:. Так як, а, то і. Оскільки, то. Так як F (0, 0)> F (1, 1), то F ÏM. Многочлен Жегалкина для штриха Шеффера має вигляд. Тому дана функція нелінійна: F ÏL.
Вправа. Перевірте, що стрілка Пірса не належать жодному з п'яти класів Посту.
Теорема 2.15. (Теорема Поста). Система булевих функцій тоді і тільки тоді є повною, коли для кожного з классовВ цій системі знайдеться функція, що не належать даному класу.
В силу теореми Поста функція X | Y Утворює повну систему, т. Е. Через штрих Шеффера можна висловити будь-яку булеву функцію. Ось відповідні вирази для заперечення і кон'юнкції:
.