Методические указания к лабораторным занятиям по дисциплине “ Дискретная математика” Новочеркасск 2008 (стр. 2 из 5)
≡ (x 
y 
) 
( x 
) ( 
) ( 
) –СКНФ◄2. Множества
2.1.Операции над множествами. Подмножество
При решении задач этого раздела нужно знать определения подмножества и основных операций над множествами.
Пример 1. Пусть А =
, В = 
. Найти А 
В, А 
В, А\В, В\А, А 
В.►По определению операций над множествами получим:
А
В = 
; А В ={4}; А\В = {1, 5},В\А = {2};A
B = {1, 2, 5}. ◄Пример 2. Найти все подмножества множества А ={1, 4, 7}.
►Множество всех подмножеств множества А обозначается
, = { 
, {1}, {4}, {7}, {1, 4}, {1, 7}, {4, 7}, {1, 4, 7}}, , А – несобственные подмножества А, остальные подмножества - собственные.◄2.2. Булева алгебра множеств
Основным типом примеров этого пункта является доказать равенство множеств, заданных формулами алгебры множеств. Решение таких примеров следует начинать с построения диаграмм Виенна для левой и правой частей. Если картинки не совпали, то вы уже решили пример и показали, что равенство не имеет места. В противном случае рекомендуется перейти к булевым формулам алгебры множеств и воспользоваться основными равенствами булевой алгебры множеств.
Пример 1. Доказать, что А\(А\В) = А
В,►Построим диаграммы Виенна левой и правой частей (рис. 1.1).
a) левая часть
→ →
A\B A\(A\B)
b) правая часть
→
А
ВРис.1.1. Диаграммы Виенна
Перейдем к булевым формулам алгебры множеств:
А\(А\В) = А
= А 
= А ( 
) = = А ( 
В) = (А ) 
(А 
) = 
(А В) = = А В◄3. Графы
Во многих задачах теории графов графы удобно описывать матрицами. Выделяют матрицу смежности и матрицу инцидентности.
Пример 1. Для графа G, приведенного на рис. 1.2, найти матрицу смежности A(G) и матрицу инцидентности B(G).
Рис. 1.2. Граф G
►По определению:
A
= ,  |
B
= .◄4. Минимизация булевых функций
Минимизация – это упрощение логических выражений путем уменьшения количества операций и символов в формулах, которые реализуют булевые функции. Одной из целей минимизации является упрощение логических устройств и достижение максимальной экономичности разрабатываемых систем.
Для минимизации булевых функций используется ряд методов, среди которых наибольшее применение находят:
1) метод неопределенных коэффициентов;
2) метод Квайна – Мак Класски.
Пример 1. Методом неопределенных коэффициентов минимизировать функцию
= Y 
.►Представим функцию в виде ДНФ самого общего вида:
= 
1 2 3 ,