1. Найдем m сокр. Для этого определим объединение конституант, соответствующих соединенным ребрам заштрихованным вершинам гиперкуба:

Здесь первая и вторая, третья и четвертая объединенные конституанты опять отличаются в одном разряде. Поэтому объединения следует продолжить, т.е.

2. Строим таблицу покрытий Квайна:

Новые Конституанты	Конституанты
	000	010	100	110	111
- - 0	1	1	1	1
11-				1	1

Здесь в новой конституанте первой строки два прочерка. Поэтому следует перебрать все варианты их замены на 0 и 1. Такими вариантами будут: 00, 01, 10, 11.

Удаление любой строки нарушает покрытие столбцов строками. Следовательно,

Таким образом,

Сложности множеств M и M _min равны:

Примеры для самостоятельной работы

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

используя законы и свойства операций над множествами.

2. Провести тождественные преобразования соотношения

3. Упростить соотношение

графическим методом.

4. Упростить выражение

с помощью кругов Эйлера.

5. Упростить выражение

6. Упростить выражение

.

7. В трехмерном пространстве J = {M₁,M₂,M₃} множество M(M₁,M₂,M₃) задано двоичным вектором V = (1,0,0,1,1,1,1,1). Минимизировать данное множество M методом Квайна. Определить сложность заданного множества и минимизированного множества.

8. В трехмерном пространстве J = {M₁,M₂,M₃} задано множество M(M₁,M₂,M₃) диаграммой Венна (рис.3.4)

Рис.3.4

Минимизировать данное множество M методом Квайна. Определить сложность заданного множества и минимизированного множества.

9. В трехмерном пространстве J = {M₁,M₂,M₃} задано множество M(M₁,M₂,M₃) аналитическим выражением

Минимизировать данное множество M методом Квайна. Определить сложность заданного множества и минимизированного множества.

10. В трехмерном пространстве J = {M₁,M₂,M₃} задано множество M(M₁,M₂,M₃) таблицей

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

Минимизировать данное множество M методом Квайна. Определить сложность заданного множества и минимизированного множества.

СПИСОК ЛИТЕРАТУРЫ

1. Горбатов В.А. Основы дискретной математики. – М.: Высшая школа, 1986. – 311 с.

2. Кузнецов О.П. , Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат, 1986. – 480 с.

3. Коршунов Ю.М. Математические основы кибернетики. – М.: Энергоатомиздат, 1987. – 496 с.

4. Сигорский В.П. Математический аппарат инженера. – Киев: Техника, 1975. – 768 с.

СОДЕРЖАНИЕ

1. Понятие алгебры. Алгебра множеств 3

2. Способы задания множеств 15

3. Минимизация представления множеств 26

Учебное издание

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

ПО КУРСУ «ДИСКРЕТНАЯ МАТЕМАТИКА»

(ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ, ЧАСТЬ 11)

для студентов всех форм обучения специальностей

« Компьютерные интеллектуальные системы и сети » ,

«Технология проблемного и системного программирования»

Составитель БОГДАНОВ Александр Евгеньевич

Ответственный за выпуск Н.И.Нагулин