 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Системы булевых функций
|
|
Пусть даны булевы функции f(g1, g2, …, gm) и g1(x1, x2, …, xn), g2(x1, x2, …, xn), …, gm(x1, x2, …, xn). Подставим функции gi в функцию f. Получим новую булеву функцию
f( и g1(x1, x2, …, xn,), g2(x1, x2, …, xn,), …, gm(x1, x2, …, xn,)),
которую называют суперпозицией функций f и gi (i = 1,2,…m), т.е. при помощи операции суперпозиции получили новую булеву функцию.
Набор булевых функций M = { f1, f2, …,fk} называется полной системой булевых функций или базисом, если любая булева функция выражается через них при помощи операции суперпозиции в конечном числе раз.
Пример.
Набор булевых функций:
является полной системой булевых функций, так как любая булева функция может быть аналитически представлена в форме СДНФ или СКНФ.
Эту полную систему называют стандартным базисом.
Пример.
Теорема (о двух системах)
Пусть имеется полная система булевых функций M = { f1, f2, …,fm}. Тогда для полноты некоторой другой системы булевых функций N = { g1, g2, …,gn} необходимо и достаточно, чтобы любая функция 
выражалась через функции системы N при помощи операции суперпозиции.
Доказательство.
Необходимость очевидна. (Почему?)
Достаточность. Рассмотрим произвольную булеву функцию h. Тогда она выражается через функции при помощи операции суперпозиции в силу полноты системы M. Но, в свою очередь, любая функция выражается через функции 
при помощи операции суперпозиции. Следовательно, можно через функции gj выразить любую булеву функцию, и, значит, система N полна.
Дата публикования: 2014-11-04; Прочитано: 473 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
