- •Учебно-методический комплекс дисциплины сд.12 дискретная математика
- •061800 «Математические методы в экономике»
- •Раздел 1. Программа учебной дисциплины. Структура программы учебной дисциплины
- •1.3 Пояснительная записка:
- •1.5. Объем дисциплины и виды учебной работы.
- •1.6 Содержание дисциплины.
- •1.7 Методические рекомендации по организации изучения дисциплины.
- •1.8 Учебно-методическое обеспечение дисциплины.
- •1.9 Материально-техническое обеспечение дисциплины.
- •1.10 Примерные зачетные тестовые задания.
- •1.11 Примерный перечень вопросов к зачету (экзамену).
- •1.12 Комплект экзаменационных билетов
- •1.13 Примерная тематика рефератов.
- •1.14 Примерная тематика курсовых работ.
- •Элементы теории множеств
- •§ 2. Бинарные операции и их свойства
- •§ 3. Операции над множествами. Законы де Моргана
- •§ 4. Вектор. Прямое произведение
- •§ 5. Мощность конечного множества
- •§ 6. Отношения и их свойства
- •§ 7. Отношение эквивалентности
- •§ 8. Отношение порядка
- •§ 9. Отображения и их свойства
- •Глава II. Элементы теории графов
- •§ 1. Графы, их вершины, рёбра и дуги
- •§ 2. Операции над графами
- •§ 3. Способы задания псевдографов. Степени вершин
- •§ 4. Отношение связности для вершин неориентированного графа
- •§ 5. Отношение достижимости для вершин орграфа
- •§ 6. Эйлеров граф и условия его существования
- •§ 7. Гамильтонов граф и условия его существования
- •§ 8. Деревья и их свойства. Цикломатическое число
- •§ 9. Формула Кэли
- •§ 10. Двудольный граф
- •§ 11. Планарность
- •§ 12. Раскраска графов
- •Глава III. Булевы функции
- •§ 1. Основные определения
- •§ 2. Свойства булевых функций
- •§ 3. Переключательные функции
- •§ 4. Совершенные нормальные формы
- •§ 5. Полнота. Примеры полных систем
- •§ 6. Замыкание и его свойства
- •§ 7. Важнейшие замкнутые классы
- •§ 8. Теорема о функциональной полноте
- •Раздел 4. Словарь терминов (глоссарий) Элементы теории множеств
- •Конечные графы
- •Функциональные системы с операциями: алгебра логики
- •Раздел 5. Практикум по решению задач (практических ситуаций) по темам лекций (одна из составляющих частей итоговой государственной аттестации) Элементы теории множеств
- •Задачи для самостоятельного решения
- •Конечные графы
- •Задачи для самостоятельного решения
- •Функциональные системы с операциями: алгебра логики
- •Задачи для самостоятельного решения
- •Раздел 6. Изменения в рабочей программе, которые произошли после утверждения программы.
- •Раздел 7. Учебные занятия по дисциплине ведут:
§ 2. Свойства булевых функций
Одну и ту же булеву функцию можно представить в виде различных логических формул.
Пример. x | y = = = (xy)
Следовательно, множество всех формул можно разбить на классы эквивалентности таким образом, что все формулы, входящие в один класс, соответствуют одной и той же булевой функции; поэтому если функции, соответствующие некоторым формулам, равны, то сами эти формулы называют эквивалентными. Запись = означает, что формулы и эквивалентны.
Приведем список эквивалентностей (тождеств), характеризующих свойства множества элементарных функций. Функции x1&x2 , x1x2 , x1x2 обладают свойствами:
1. коммутативности, 2. ассоциативности.
3. Для конъюнкции и дизъюнкции выполняются дистрибутивные законы:
((x1 x2) x3) = (x1x3) (x2x3)), ((x1 x2) x3) = (x1x3) (x2x3)).
4. Конъюнкция, дизъюнкция и отрицание связаны законами де Моргана.
5. Справедливо правило снятия двойного отрицания: =x.
6. Кроме того, выполняются свойства идемпотентности: (x&x)=x, (xx)=x.
7. Для констант справедливы следующие соотношения: =1, =0,
(x&1)=x, (x&0)=0, (x1)=1, (x0)= x, (x&)=0, (x)=1. Предпоследнее равенство наз. законом противоречия, а последнее законом исключенного третьего.
8. Конъюнкция обладает свойством дистрибутивности относительно сложения по mod 2:
((x1x2) x3) = (x1x3) (x2x3)).
Тождества легко могут быть проверены путем сопоставления функций, соответствующих правой и левой частям этих тождеств.
Cчитают операции упорядоченными по силе следующим образом: , &, , , .
Пример. Запись x1 x2 x3 x4 означает (x1 ((x2 x3) x4)).
Если операция ассоциативна, то можно вместо формул ((x1x2)x3), (x1(x2x3)) используют выражение x1x2x3, которое не является формулой, но может быть превращено в нее путем расстановки скобок, причем функциональные свойства не меняются, как бы мы эти скобки ни расставляли.
Иногда для & и употребляют выражения, аналогичные символу суммирования: xi, xi.
Сформулируем ряд правил, вытекающих из пунктов 2 и 5 списка тождеств элементарных функций, которыми удобно пользоваться при осуществлении эквивалентных преобразований:
если в лог. произведении один из множителей равен 0, то и лог. произведение равно 0,
если в лог. произведении, содержащем не менее двух множителей, есть множитель, равный 1, то этот множитель можно зачеркнуть,
если в лог. сумме, содержащей не менее двух слагаемых, имеется слагаемое, равное 0, то это слагаемое можно зачеркнуть,
если в лог. сумме одно из слагаемых равно 1, то и лог. сумма равна 1.
Очевидно, что если ‘ - подформула формулы и если заменить любое из ее вхождений на эквивалентную формулу ‘, то формула перейдет в эквивалентную ей формулу . Этот принцип вместе с тождествами для элементарных функций позволяет осуществлять эквивалентные преобразования и, тем самым, получать новые тождества.
Пример. С помощью эквивалентных преобразований выведем две полезные формулы, называемые правилами поглощения.
1) x x&y = x&1 x&y = x & (1y) = x&1 = x: эл-т лог. суммы x “поглотил” лог. произведение.
2) x & (xy) = x&x x&y = x x&y = x: лог. множитель x “поглотил” логическую сумму xy.
Существует еще один способ для получения тождеств. Он основан на использовании принципа двойственности.
Функция f*(x1,x2,...,xn) =(), называется двойственной функцией к f(x1,x2,...,xn).
Таблицу для двойственной функции из таблицы для исходной функции можно получить, если инвертировать (то есть заменить 0 на 1 и 1 на 0) столбец функции, а затем его перевернуть.
Таблица |
1.7 |
f |
f* |
0 |
1 |
1 |
0 |
x |
x |
& |
|
|
& |
Пример. Если (x1,x2)=x1x2 , то *(x1,x2)=(x1x2)( ).
Из принципа двойственности вытекает, что если две функции равны ((x1,x2,...,xn)=(x1,x2,...,xn)), то равны и соответствующие им двойственные функции (*(x1,x2,...,xn)=*(x1,x2,...,xn)).
Пример. Из истинности первого закона де Моргана непосредственно следует истинность второго закона .