Теорема Шеннона. Теорема о функциональной полноте. Способы построения СДНФ и СКНФ. (43)
Пусть (x1,…,xn) – набор логических переменных, ∆= (δ1,…,δn) – набор нулей и единиц. Конституентой единицы набора ∆ называется конъюнкт . Конституентой нуля набора ∆ называется дизъюнкт
. СДНФ – дизъюнкция некоторых конституент единицы, среди которых нет одинаковых. СКНФ – конъюнкция некоторых коституент нуля, среди которых нет одинаковых. Рассмотрим разложение булевой функции f(x1,…,xn) по k переменным.
Первая теорема Шеннона: Любая булева функция f(x1,…,xn) представима в виде разложения Шеннона: Доказательство: Заметим, что
. Подставим произвольно вместо первых k переменных их значения:
. Тогда левая часть доказываемой формулы равна
. Правая часть представляет собой дизъюнкцию 2k конъюнкций вида
, которые этой подстановкой разбиваются на два класса. К первому классу относится конъюнкция, у которой набор (δ1,…,δk) совпадает с набором
:
. Эта конъюнкция равна Евой части формулы. Ко второму классу относится 2k-1 конъюнкций, у каждой из которых хотя бы в одной переменной xi,
выполнимо условие
. Следовательно каждая из них равна нулю. Используя закон
, получаем, что левая и правая части формул равны при любой подстановке переменных x1,…,xn.
Вторая теорема Шеннона: Любая булева функция f(x1,…,xn) представима в виде разложения Шеннона: .При k=n, для булевой функции f(x1,…,xn)≠0 получаем ее представление в виде СДНФ:
.
Для булевой функции f(x1,…,xn)≠1, получаем представление в виде СДНФ: .
Теорема о функциональной полноте: Для любой булевой функции f найдется формула φ, представляющая функцию f. Если f≠0, то φ однозначно представима в виде СДНФ: . Если f≠1, то φ однозначно представима в виде СКНФ:
.
Приведение ДНФ к СДНФ:
1) Данную формулу приводим к ДНФ
2) Если в конъюнкт входит некоторая переменная вместе со своим отрицанием, то этот конъюнкт удаляется из ДНФ
3) Если в конъюнкт одна и та же литера xδ входит несколько раз, то мы удаляем их все кроме одной
4) Если в некоторый конъюнкт не входит переменная y, то заменяем его на эквивалентную формулу
и применяем закон дистрибутивности
5) Если в полученном ДНФ имеется несколько одинаковых конституент единицы, то оставляем только одну из них. В результате получается СДНФ.
Приведение КНФ к СКНФ:
1) Данную формулу приводим к КНФ
2) Если в дизъюнкт входит некоторая переменная вместе со своим отрицанием, то этот дизъюнкт удаляется из КНФ
3) Если в дизъюнкт одна и та же литера xδ входит несколько раз, то мы удаляем их все кроме одной
4) Если в некоторый дизъюнкт не входит переменная y, то заменяем его на эквивалентную формулу
и применяем закон дистрибутивности
5) Если в полученном КНФ имеется несколько одинаковых конституент нуля, то оставляем только одну из них. В результате получается СКНФ.