Визначення. Система булевих функцій (f1. F2. Fn) називається повною. якщо будь-яка перемикальна функція може бути представлена суперпозицією функцій даної системи.
Для того щоб система булевих функцій була повною, необхідно і достатньо, щоб вона містила:
- хоча б одну функцію, не зберігає константу нуль;
- хоча б одну функцію, не зберігає константу одиниця;
- хоча б одну функцію, яка не є лінійної;
- хоча б одну функцію, яка не є монотонною;
- хоча б одну функцію, яка не є самодвоїстих.
Це критерій повноти системи.
Система функцій 1. f2. fn>, що є повною, називається базисом.
Мінімальним базисом називається такий базис, для якого видалення хоча б однієї з функцій fi. утворюють той базис, перетворює систему функцій 1. f2. fn> в неповну.
Будемо розглядати функції, залежні від n аргументів. Число різних функцій одно.
Тривіальна повна система складається з усіх функцій.
Функції інверсії, диз'юнкції і кон'юнкції утворюють повну систему. Це випливає з основної теореми, яка каже, що будь-яка булева функція може бути записана у вигляді диз'юнкції минтермов (або кон'юнкції макстермов).
базис НЕ мінімальний, так як може бути зменшений за рахунок викидання з нього / \ або \ /. Це випливає з формул де Моргана:
Базиси і є мінімальними.
а) - функціонально повна система (це випливає з теореми Жегалкина);
б) функція імплікації і константа 1:;
в) функція імплікації і інверсії. .
Приклад. Довести, що функція Шеффера утворює повну систему
Доведення. висловимо ¯ і / \ через функцію Шеффера:
Так як - повна система, твердження доведено.
Приклад. Висловимо функцію, використовуючи тільки функцію Шеффера:
.
Приклад. Довести, що А ↓ В утворює функціонально повну систему
Так як інверсія і диз'юнкція виражаються тільки через функцію «стрілка Пірса», а - функціонально повна система, то А ↓ В є функціонально повною системою.
Приклад. Висловити функцію, використовуючи тільки функцію «стрілка Пірса»:
Вибір функціонально повної системи по таблиці.
Інверсія - не зберігається 0 і 1 і не монотонна, \ / - НЕ самодвоїстих, не лінійна.
Обидві функції самодвоїстих. система
Можна показати, що з будь-якої повної системи функцій можна вибрати повну підсистему, що містить не більше чотирьох функцій. нехай
Якщо fk (11 ... 1) = 1, то ця ж функції не самодвоїстих, так як fk (00 ... 0) ≠ 0.
Якщо ж fk (11 ... 1) = 0, то ця ж функція не зберігається константу 1 і не монотонна.
Приєднавши до fk відсутні три функції, отримаємо систему, що складається не більше ніж з чотирьох функцій.
Приклад. Скласти мінімальний базис, що включає функцію
Базиси 8, f11> і 11, f14 »не мінімальні, так як f8 і f11 і самі функціонально повні.
Приклад. Висловити функцію в системі 0, f11>:
Для перетворень використовуємо систему як основну: