Читайте также:
|
Определение. Система функций 
называется функционально полной системой, если любая логическая функция может быть представлена формулой над системой , т.е. является суперпозицией функций этой системы.
Система 
является функционально полной. Равным образом, функционально полна любая система , через функции которой можно выразить конъюнкцию, дизъюнкцию и отрицание. Действительно, для любой логической функции 
из такой системы следует составить булеву формулу, и она обязательно существует и выразить в ней конъюнкцию, дизъюнкцию и отрицание через функции системы . Аналогично обосновывается более общее утверждение.
Теорема: Если все функции функционально полной системы 
представимы формулами над системой , то система также функционально полна.
Пример 9.1:
а) Системы 
и 
функционально полны, поскольку, с помощью законов Де Моргана и двойного отрицания можно выразить в каждой из этих систем функцию, недостающую до 
через остальные две:
.
С точки зрения функциональной полноты систему следует считать избыточной: она сохраняет свойство полноты и при удалении из неё конъюнкции или дизъюнкции. Однако легко видеть из приведённого примера, что, хотя системы 
и 
не являются избыточными, формулы в них получаются длиннее.
б) Системы 
(штрих Шеффера) и 
(стрелка Пирса) являются функционально полными.
Таким образом, система 
сводится к системе , а система 
– к системе 
.
в) Система 
является функционально полной. Поскольку 
, данная система сводится к .
На свойствах этой системы остановимся подробнее.
Дата добавления: 2015-10-28; просмотров: 57 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Тема 8.6. ДНФ, интервалы и покрытия | | | Тема 9.2. Алгебра Жегалкина и линейные функции |