Реферат: Элементы комбинаторики. Правила умножения и сложения

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

- монотонная функция

Таких функций 6

5. Класс самодвойственных функций.

Переключательная функция называется самодвойственной, если на каждой паре противоположных кортежей значения функции противоположны.

На кортежах 00 и 11,01,10 противоположные значения могут иметь функции

Теорема Поста о функциональной полноте. Для того чтобы система булевых функций была полной необходимо и достаточно, чтобы она содержала:
-хотя бы одну функцию, не сохраняющую 0

-хотя бы одну функцию, не сохраняющую 1

-хотя бы одну функцию, не явл линейной

-хотя бы одну функцию, не явл монотонной

-хотя бы одну функцию, не явл самодвойственной.

Каждый базис содержит не более 4х булевых функций.