- •Содержание
- •Тема 1. Множества
- •1.1.Основные понятия
- •1.2. Операции над множествами
- •1.3. Геометрическое моделирование множеств. Диаграммы Венна
- •1.4. Алгебра множеств. Основные тождества алгебры множеств
- •Основные тождества алгебры множеств
- •1.5. Эквивалентность множеств
- •1.6. Счетные множества
- •1.7. Множества мощности континуума
- •Контрольные вопросы к теме 1
- •Тема 2. Отношения. Функции
- •2.1. Отношения. Основные понятия и определения
- •2.2. Операции над отношениями
- •2.3. Свойства отношений
- •2.4. Функции. Основные понятия и определения
- •Способы задания функций
- •Контрольные вопросы к теме 2
- •Тема 3. Графы
- •3.1. Основные характеристики графов
- •3.2. Матричные способы задания графов
- •Основные свойства матриц смежности и инцидентности
- •3.3. Изоморфизм графов
- •3.4. Маршруты, циклы в неориентированном графе
- •3.5. Пути, контуры в ориентированном графе
- •3.6. Связность графа
- •3.7. Экстремальные пути в нагруженных ориентированных графах
- •3.8 Алгоритм Форда – Беллмана нахождения минимального пути Предполагается, что ориентированный граф не содержит контуров отрицательной длины.
- •3.9. Алгоритм нахождения максимального пути
- •3.10. Деревья.. Основные определения
- •3.11. Минимальные остовные деревья нагруженных графов
- •Контрольные вопросы к теме 3
- •Тема 4. Булевы функции
- •4.1. Определение булевой функции
- •4.2. Формулы логики булевых функций
- •4.3. Равносильные преобразования формул
- •Основные равносильности булевых формул.
- •Правило равносильных преобразований
- •4.4. Двойственность. Принцип двойственности.
- •4.5. Булева алгебра (алгебра логики). Полные системы булевых функций
- •4.6. Нормальные формы
- •4.7. Разложение булевой функции по переменным
- •4.8. Минимизация формул булевых функций в классе дизъюнктивных нормальных форм
- •4.9. Применение алгебры булевых функций к релейно-контактным схемам
- •Контрольные вопросы к теме 4
- •Ответы на контрольные вопросы
- •Тема 2.
- •Тема 3.
- •Тема 4.
- •Указания к выполнению лабораторных работ
- •Контрольные задания по курсу "Дискретная математика".
- •1. Раздел «Множества»
- •2. Раздел «Отношения. Функции»
- •3. Раздел «Графы»
- •4. Раздел «Булевы функции»
- •Варианты заданий
- •Вопросы к экзамену по дисциплине «Дискретная математика»
- •Список рекомендованной литературы
- •Краткие сведения о математиках
4.3. Равносильные преобразования формул
В отличие от табличного задания представление функции формулой не единственно. Например, две различные формулы
x1Vx2 и (x1&x2)
реализуют одну функцию – штрих Шеффера.
Две формулы, реализующие одну и ту же функцию, называются равносильными.
Равносильность формул A и B будем обозначать следующтм образом: A B.
Для того, чтобы установить равносильность формул, можно составить таблицы значений функции для каждой формулы и сравнить их. Для равносильных формул эти таблицы совпадают. Другой способ установления равносильности формул заключается в использовании некоторых установленных равносильностей булевых формул.
Основные равносильности булевых формул.
Для любых формул A, B, C справедливы следующие равносильности:
1. Коммутативность.
а) A&B B&A (для конъюнкции);
б) AVB BVA (для дизъюнкции).
2. Ассоциативность.
а) A&(B&C) (A&C)&C (для конъюнкции);
б) AV(BVC) (AVB)VC (для дизъюнкции).
3. Дистрибутивность.
а) A&(BVC) A&BVA&C (для конъюнкции относительно дизъюнкции);
б) AV(B&C) (AVB)&(AVC) (для дизъюнкции относительно конъюнкции).
4. Закон де Моргана.
а) (A&B)AVB (отрицание конъюнкции есть дизъюнкция отрицаний);
б) (AVB) A&B (отрицание дизъюнкции есть конъюнкция отрицаний).
5. Идемпотентность.
а) A&A A (для конъюнкции);
б) AVA A (для дизъюнкции).
6. Поглощение.
а) A&(AVB) A (1– ый закон поглощения);
б) AVA&B A (2– ой закон поглощения).
7. Расщепление (склеивание).
а)A&B V A&(B) A (1–ый закон расщепления);
б) (AVB) & (AVB) A (2–ой закон расщепления).
8. Двойное отрицание.
(A) A.
9. Свойства констант.
а)A&1 A; б) A&0 0; в)AV1 1; г) AV0 A; д) 0 1; е) 1 0.
10. Закон противоречия.
A&A 0.
11. Закон “исключенного третьего”.
AVA 1.
Каждая из перечисленных равносильностей может быть доказана с помощью таблиц значений функций, составленных для выражений, стоящих слева и справа от символа “”. Докажем, например, равносильность 4а. Для этого составим таблицу 4.5.
Таблица 4.5
A |
B |
A&B |
(A&B) |
A |
B |
AVB |
0 0 1 1 |
0 1 0 1 |
0 0 0 1 |
1 1 1 0 |
1 1 0 0 |
1 0 1 0 |
1 1 1 0 |
Из таблицы 4.5 видно, что (A&B) AVB, что и требовалось доказать.
Следующие важные равносильности показывают, что все логические операции могут быть выражены через операции конъюнкции, дизъюнкции и отрицания:
12. AB AVB (A&B).
13. A~B (AB)&(BA) (A&B) V (A&B) АVB)&(AVB).
14. AAVB) V (A&B).
15. A¯B (AVB) A&B.
16. AïB (A&B)AVB.
Используя равносильности 3а и 3б и метод математической индукции, нетрудно получить также следующие равносильности (обобщенные законы дистрибутивности):
17. (A1VA2V...VAn)&(B1VB2V...VBm)
A1&B1VA1&B2V...VA1&BmV...VAn&B1VAn&B2V...VAn&Bm.
18. (A1&A2&...&An)V(B1&B2&...&Bm)
(A1VB1)&(A1VB2)&...&(A1VBm)&...&(AnVB1)&(AnVB2)&...&(AnVBm).
Используя равносильности 4а и 4б и метод математической индукции, можно получить также следующие равносильности (обобщенные законы де Моргана):
19. (A1&A2&...&An) A1VA2V...VAn.
20. (A1VA2V...VAn) A1&A2&...&An
В равносильностях 1 – 20 в качестве A, B, Ai, Bi могут быть подставлены любые формулы и, в частности, переменные. Приведем правило, с помощью которого можно переходить от одних равносильностей к другим.