- •10. Алгебра логики
- •10.1.Булева алгебра
- •10.2. Двойственность формул булевой алгебры
- •10.3. Нормальные формы
- •10.4. Совершенные нормальные формы
- •10.5. Проблема разрешимости
- •10.6. Конституенты и представление функций
- •10.7. Алгебра Жегалкина
- •10.8. Канонические многочлены
- •10.9. Типы булевых функций
- •10.10. Функциональная полнота
- •Свойства булевых функций
10.10. Функциональная полнота
Система функций, суперпозицией которых может быть представлена любая функция из некоторого множества булевых функций, называется функционально полной. Если в такой системе допускаются константы 0 и 1, то ее называют ослабленно функционально полной. Говорят, что функционально полная система функций образует базис в логическом пространстве. Система функций называется минимально полным базисом, если удаление из нее любой функции превращает эту систему в неполную.
Рассмотренные в (9.4) функционально полные системы комплектовались путем сопоставления различных выражений для булевых функций. Общее решение вопроса основано на теореме о функциональной полноте: для того чтобы система булевых функций была полной, необходимо и достаточно, чтобы она включала хотя бы одну функцию: не сохраняющую константу 0, не сохраняющую константу 1, несамодвойственную, нелинейную и немонотонную. Эту теорему следует понимать так, что одна и та же функция может представлять в функционально полной системе одно или несколько требуемых свойств, если она обладает этими свойствами.
С помощью табл. 9.1 можно следующим образом охарактеризовать свойства булевых функций с позиций функциональной полноты (звездочкой отмечены свойства, которыми обладает данная функция:
Таблица 10.1
Свойства булевых функций
Булевы функции |
Формулы |
Свойства |
||||
Несохранение 0 |
Несохранение 0 |
Несамодвойст-венность |
Нелинейность |
Немонотонность |
||
Константа 0 |
0 |
|
* |
* |
|
|
Константа 1 |
1 |
* |
|
* |
|
|
Отрицание |
* |
* |
|
|
* |
|
Конъюнкция |
|
|
* |
* |
|
|
Дизъюнкция |
|
|
* |
* |
|
|
Импликация |
* |
|
* |
* |
* |
|
Эквиваленция |
* |
|
* |
|
* |
|
Отрицание импликации |
|
* |
* |
* |
* |
|
Сумма по модулю 2 |
|
* |
* |
|
* |
|
Штрих Шеффера |
* |
* |
* |
* |
* |
|
Стрелка Пирса |
* |
* |
* |
* |
* |
Отсюда видно, что рассмотренные в (9.4) системы операций (дизъюнкция и отрицание, конъюнкция и отрицание, штрих Шеффера, стрелка Пирса) удовлетворяют теореме о функциональной полноте. Система операций алгебры Жегалкина (сумма по модулю 2 и конъюнкция) вместе с константой 1 образует ослабленно функционально полную систему.
Выбрав любую элементарную функцию и дополнив ее одной или несколькими другими функциями так, чтобы все они вместе удовлетворяли теореме о функциональной полноте, можно выразить через них все другие булевы функции. Например, в основу одного из таких комплектов можно положить импликацию и константу 0. Тогда и , а через дизъюнкцию и отрицание выразятся и все остальные функции. В качестве другого функционально полного комплекта можно взять конъюнкцию, эквиваленцию и константу 0. При этом и формулы алгебры логики, построенной на этих операциях, будут двойственны формулам алгебры Жегалкина, если в качестве двойственных символов принять + и ~, а также 1 и 0.
По-видимому, все лучшее, что можно извлечь из различных вариантов функционально полных систем, уже заложено в булевой алгебре и алгебре Жегалкина. Но при решении специальных задач не исключается построение и применение других алгебр логики.