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

  1. По таблице истинности перебираем все импликанты (по единичным наборам);
  2. Оставляем простые импликанты.
  3. Применяем таблицу покрытия.

Пример:

  x y z f
1
2
3
4
5
6
7
Метод гиперкубов отыскания ДНФ - student2.ru {0}
Метод гиперкубов отыскания ДНФ - student2.ru {1}
Метод гиперкубов отыскания ДНФ - student2.ru {2}
Метод гиперкубов отыскания ДНФ - student2.ru {3}
Метод гиперкубов отыскания ДНФ - student2.ru {7}

a) длины 3

Метод гиперкубов отыскания ДНФ - student2.ru {0,1}
Метод гиперкубов отыскания ДНФ - student2.ru {2,3}
Метод гиперкубов отыскания ДНФ - student2.ru {3,7}
Метод гиперкубов отыскания ДНФ - student2.ru {1,3}
Метод гиперкубов отыскания ДНФ - student2.ru {0,2}

б) длины 2

Метод гиперкубов отыскания ДНФ - student2.ru {0,1,2,3}

в) длины 1

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

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

Таблица покрытия:

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

4. изоморфизм между алгеброй множеств и алгеброй логических векторов

Метод гиперкубов отыскания ДНФ - student2.ru Метод гиперкубов отыскания ДНФ - student2.ru Эти две алгебры изоморфны, если существуют:

1. отображение Метод гиперкубов отыскания ДНФ - student2.ru , такое что j взаимно однозначное соответствие.

2. сохранение операций Метод гиперкубов отыскания ДНФ - student2.ru

Метод гиперкубов отыскания ДНФ - student2.ru —булеан

Метод гиперкубов отыскания ДНФ - student2.ru —булева алгебра;

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

Метод гиперкубов отыскания ДНФ - student2.ru —алгебра логических векторов.

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

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

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

I-ая теорема об изоморфизме:Алгебра множеств изоморфна алгебре логических векторов.

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

Пусть Метод гиперкубов отыскания ДНФ - student2.ru

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

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

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

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

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

1 φ (М1 È М2) = Метод гиперкубов отыскания ДНФ - student2.ru

2 φ (М1 Ç М2) = Метод гиперкубов отыскания ДНФ - student2.ru

3 φ ( Метод гиперкубов отыскания ДНФ - student2.ru ) = Метод гиперкубов отыскания ДНФ - student2.ru

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

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

Пусть i-ая компонента вектора φ (М1 È М2) равна 0 Þ Метод гиперкубов отыскания ДНФ - student2.ru Метод гиперкубов отыскания ДНФ - student2.ru и Метод гиперкубов отыскания ДНФ - student2.ru Þ

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


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

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

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

Любую булеву функцию можно представить в виде Метод гиперкубов отыскания ДНФ - student2.ru

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

Пусть Метод гиперкубов отыскания ДНФ - student2.ru – фиксированный набор. Подставим в левую и правую части, получим

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

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

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

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

Следствие (двойственная теорема Шеннона): если заменить дизъюнкцию на конъюнкцию, то Метод гиперкубов отыскания ДНФ - student2.ru

при n = k

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

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

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

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

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

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

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

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

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

Наши рекомендации