3. Используя результаты, полученные в п.П.1,2 и описание построения двоичной таблицы, зададим множество m(m1,m2,m3) указанной таблицы. Таблица будет иметь вид:

d(c)	M1	M2	M3	M
0	0	0	0	1
1	0	0	1	0
2	0	1	0	0
3	0	1	1	1
4	1	0	0	1
5	1	0	1	0
6	1	1	0	1
7	1	1	1	1

4. Используя определение гиперкуба (n-мерного куба), легко построить такой гиперкуб для нашего случая. Гиперкуб изображен на рис.2.3.

Рис.2.3

Здесь каждая вершина обозначена двоичным вектором, которому взаимно однозначно соответствует область пространства J (конституанта) и соответствующий ей десятичный эквивалент. Вершины, у которых двоичные векторы отличаются только в одном разряде (безразлично в каком) соединены ребром. Области, соответствующие указанным вершинам, имеют общую границу на диаграмме Венна. Вершины, соответствующие областям (конституантам) , входящим в заданное множество, заштрихованы.

5. Аналитическое выражение (объединение конституант ) множества m запишется, согласно полученным выше результатам, в виде

Пример 2. Множество M задано диаграммой Венна (рис.2.4). Представим множество M в виде: 1. таблицы, 2. двоичного вектора, 3. десятичного эквивалента, 4. гиперкуба, 5. аналитического выражения.

Рис.2.4

1. Те области (конституанты), которые входят в заданное множество M, отмечены штриховкой. Номер каждой области в символе Венна соответствует десятичному эквиваленту этой области. Штриховка области означает, что конституанта, соответствующая десятичному эквиваленту заштрихованной области, входит в множество M. Поэтому в таблице в столбце M на соответствующем месте будет стоять единица. Учитывая это, можно построить таблицу:

d(c)	M1	M2	M3	M
0	0	0	0	0
1	0	0	1	1
2	0	1	0	0
3	0	1	1	1
4	1	0	0	1
5	1	0	1	0
6	1	1	0	0
7	1	1	1	1

2. Двоичный вектор V, соответствующий заданному множеству M, есть столбец M в построенной таблице, записанный в виде V = (1,0,0,1,1,0,1,0).

3. Зная вектор V , можно записать десятичный эквивалент, задающий множество M.

d(M) = 1.2⁷ + 0.2⁶ + 0.2⁵ + 1.2⁴ + 1.2³ + 0.2² + 1.2¹ + 0.2⁰ =

= 128 + 16 + 8 + 2 = 154.

Таким образом d(M) = 154.

4. Построим гиперкуб. Воспользовавшись, например, таблицей, отметим на нем вершины, которые соответствуют конституантам, входящим в заданное множество M. Искомый гиперкуб изображен на рис.2.5.

Рис.2.5

5. Используя, например, гиперкуб, запишем заданное множество M как объединение конституант

ПРИМЕРЫ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

1. Множество M задано аналитическим выражением

Задать множество M гиперкубом и двоичным вектором.

2. Множество M задано диаграммой Венна (рис.2.6)

Рис.2.6

Задать множество M десятичным эквивалентом и аналитическим выражением.

3. Множество M задано десятичным эквивалентом d(M) = 157.

Задать множество M таблицей и диаграммой Венна.

4. Множество M задано гиперкубом (рис.2.7)

Рис.2.7

Задать множество M двоичным вектором и аналитическим выражением.

5. Множество M задано двоичным вектором V = (10011110). Задать множество M десятичным эквивалентом и диаграммой Венна.

3. МИНИМИЗАЦИЯ ПРЕДСТАВЛЕНИЯ МНОЖЕСТВА

Часто при решении той или иной задачи необходимо упростить или преобразовать к удобному виду различные выражения, содержащие множества.

Методы минимизации (упрощения) множества:

1. Применение законов и свойств операций над множествами (тождественные преобразования) .

2. Графический метод (круги Эйлера)

3. Метод Квайна.

Существуют и другие методы минимизации.

Запишем дополнительные законы операций над множествами, которые часто используются в тождественных преобразованиях:

1. Законы склеивания

2. Законы поглощения

Под сложностью представления множества M понимают число символов в задающем его выражении.

Пример 1. Упростить выражение

Используя законы и свойства операций над множествами, получим следующее выражение

Здесь в вертикальных скобках указаны законы и свойства, которые использовались при упрощении.

Пример 2. Упростить выражение

графическим способом.

Изобразим с помощью кругов Эйлера пересечение . Данному пересечению соответствует область с наклонной штриховкой (рис.3.1). Теперь изобразим пересечение . Этому пересечению на рис. 3.1 соответствует область с вертикальной штриховкой. Изображаем пересечение . Область с горизонтальной штриховкой соответствует этому пересечению (рис.3.1). Объединяя полученные области, получаем, что Это хорошо видно из рис.3.1.

Рис.3.1

Пример 3. В трехмерном пространстве J = {M₁,M₂,M₃} задано множеством M(M₁,M₂,M₃) десятичным эквивалентом d(M) = 217. Минимизировать множество M методом Квайна. Определить сложность заданного множества и минимизированного множества.

В примере 1 п.2 заданное множество M представлено различными способами задания. Воспользуемся некоторыми из них для минимизации заданного множества.

Метод Квайна состоит из двух этапов: