Метод гиперкубов отыскания ДНФ

Доказательство:

Пусть

В(А) – мн-во, где А= {а₁, …, а_n }

V_n – мн-во двоичных векторов длины n.

Каждому подмножеству МÍA соответствует двоичный вектор φ(М) = V = (V₁, … V_n), где

1 φ (М₁ È М₂) =

2 φ (М₁ Ç М₂) =

3 φ () =

Пусть i-ая компонента вектора φ (М₁ È М₂) равна 1 Þ а_iÎ М₁ È М₂ Þ а_iÎ М₁ или а_iÎ М₂ Þ

i-ая компонента вектора φ (М₁)=1 или i-ая компонента вектора φ (М₂)=1 Þ i-ая компонента вектора φ(М₁)Ú φ (М₂)=1.

Пусть i-ая компонента вектора φ (М₁ È М₂) равна 0 Þ и Þ

i-ая компонента вектора φ (М₁)=0 и i-ая компонента вектора φ (М₂)=0 Þ i-ая компонента вектора φ(М₁)Ú φ (М₂)=0.

5. Теорема Шеннона, полнота системы булевых функций.

булевой функцией называют функцию типа Bⁿ ==>B, B={0,1} где — булево множество, а n — неотрицательное целое число, которое называют арностью или местностью функции. Элементы 1 (единица) и 0 (ноль) стандартно интерпретируют как истину и ложь, хотя в общем случае их смысл может быть любым. Элементы Bⁿ называют булевыми векторами. В случае n = 0 булева функция превращается в булеву константу.

Теорема Шеннона:

Любую булеву функцию можно представить в виде

Доказательство:

Пусть – фиксированный набор. Подставим в левую и правую части, получим

Следствие: при n = k.

где дизъюнкция берется по веем наборам (s₁, …, s_n), на которых f(s₁, …, s_n) = 1. Это СДНФ.

Следствие (двойственная теорема Шеннона): если заменить дизъюнкцию на конъюнкцию, то

при n = k

где конъюнкция берется по всем наборам (s₁, …, s_n), на которых f(s₁, …, s_n) = 0. Это СКНФ.

Полнота системы булевых функций. Система å называется полной, если при помощи суперпозиции из этого множества функций можно получить все булевы функции.

Примеры полных систем:

Суперпозицией множества функций, называется подстановка функций друг в друга.

Теорема. Отрицание, дизъюнкция и конъюнкция образуют полную систему булевых функций

Полная система булевых функций называется базисом, если она перестает быть полной при удалении хотя бы одной из этих функций.

Согласно этому определению система булевых функций не является базисом. Действительно, применяя законы де-Моргана, конъюнкцию в булевой функции можно заменить на дизъюнкцию и отрицание, а дизъюнкцию - на конъюнкцию и отрицание. Следовательно, отрицание и дизъюнкция (отрицание и конъюнкция) также образуют полную систему булевых функций. Нетрудно убедиться, что наборы и являются базисными, так как их дальнейшее сокращение без нарушения полноты системы невозможно.