2020-04-12
146
Для начала дадим основные определения.
Определение. Говорят, что булева функция сохраняет 0, если f (0,0,…,0)=0.
Определение. Говорят, что булева функция сохраняет 1, если 
.
Определение. Функция, реализуемая формулой 
, называется двойственной к функции 
.
Функцию, двойственную к функции 
, обозначают 
, т.е. 
.
Определение. Говорят, что булева функция самодвойственная, если 
.
Определение. Если для любого 
(
), то говорят, что вектор 
предшествует вектору 
и пишут 
.
Например, 
; 
.
Определение. Говорят, что булева функция 
монотонна, если для любых наборов 
и 
значений переменных, таких что 
, выполняется неравенство 
.
Определение. Говорят, что булева функция линейна, если в ее каноническом полиноме Жегалкина коэффициенты при всех слагаемых, содержащих произведения переменных, равны 0.
Для того чтобы система булевых функций обладала полнотой, она должна не сохранять ноль, единицу, не быть самодвойственной, монотонной и линейной.
ПРИМЕР. Является ли система булевых функций 
полной?
Чтобы убедиться в функциональной полноте, составим таблицу, столбцы которой соответствуют классам 
, 
, 
, 
,. 
, строки – функциям 
, а в клетках проставляется «+» или «–» в зависимости от того, принадлежит ли функция соответствующему классу или не принадлежит.
|
|
|
|
|
| |
| 0 | + | – | – | + | + |
| 1 | – | + | – | + | + |
| – | – | + | – | + |
Как видно из таблицы, для каждой пары классов найдется функция, принадлежащая одному классу из пары и не принадлежащая другому
Определение. Система функций B называется базисом, если:
1. B – полна;
2. при удалении из системы B хотя бы одной функции, полнота теряется.
ПРИМЕРЫ.
1. 
– дизъюнктивный базис Буля.
2. 
– конъюнктивный базис Буля.
3. 
– базис Шеффера.
4. 
– базис Пирса.
5. 
– базис Жегалкина.
