- •Донецк-2001
- •Донецк-2001
- •1Введение в теорию множеств
- •1.1Основные определения
- •1.2Способы задания множества
- •1.3Операции над множествами
- •1.4Основные законы алгебры множеств
- •2.1Теоретические сведения
- •2.2Способы задания отношений
- •1.5Контрольные вопросы
- •2Отношения на множествах
- •2.3Свойства бинарных отношений
- •2.4Функциональные отношения
- •2.5Контрольные вопросы
- •3Основные понятия комбинаторики.
- •3.1Правила суммы и произведения
- •3.1.1Правила суммы
- •3.1.2Правило произведения
- •3.1.3Сложный выбор объектов
- •3.2Соединения без повторений
- •3.2.1Перестановки
- •3.2.2Размещения
- •3.2.3Сочетания
- •3.2.4Свойства сочетаний
- •3.3Соединения с повторениями
- •3.3.1Перестановки с повторениями
- •3.3.2Размещения с повторениями.
- •3.3.3Сочетания с повторениями.
- •3.4Контрольные вопросы
- •4Булева алгебра
- •4.1Определение функции алгебры логики
- •4.2Способы описания фал
- •4.2.1Табличный способ представления фал
- •4.2.2Графическое представление фал
- •4.3Функции алгебры логики одного аргумента
- •4.4Функции алгебры логики двух аргументов
- •4.5Условные приоритеты булевых функций
- •4.6Фиктивные аргументы фал
- •4.6.1Алгоритм нахождения фиктивных аргументов
- •4.8Выражение одних элементарных функций через другие
- •4.9Аналитическая запись фал
- •4.9.1Дизъюнктивная нормальная форма (днф)
- •4.10Полные системы фал
- •4.11Контрольные вопросы
- •5Методы минимизации функций алгебры логики.
- •5.1Основные определения
- •5.2Минимизация фал на кубе
- •Пункты решения задачи по минимизации
- •Четырехмерное пространство
- •5.3Метод Квайна
- •5.4Метод Мак-Класки
- •5.5Графический метод минимизации: карты Карно и диаграммы Вейча
- •5.6Основные принципы построения карт Карно
- •5.7Контрольные вопросы
- •6Контрольные работы для студентов заочного отделения.
- •6.1Контрольная работа № 1.
- •6.2Контрольная работа № 2.
- •6.3Алгоритм генерации варианта
- •7Примеры решения типовых зданий.
- •7.1Контрольная работа №1.
- •7.2Контрольная работа №2.
- •1 Введение в теорию множеств 3
- •2 Отношения на множествах 10
- •3 Основные понятия комбинаторики. 15
- •4 Булева алгебра 23
- •5 Методы минимизации функций алгебры логики. 36
- •6 Контрольные работы для студентов заочного отделения. 46
- •7 Примеры решения типовых зданий. 58
1.2Способы задания множества
Перечисление элементов.
Например:
А = {1,3,5,6,889,-10}
Задание определяющего свойства.
Например:
X = { x | 1 > х > 5, x є Z };
А = {a2 | a − четное число}.
Пустое множество – множество, не содержащее ни одного элемента. Пустое множество обозначается
Универсальное – множество, содержащее все возможные элементы. Универсальное множество обозначается U.
Утверждение "а является элементом множества А" записывается в виде аА (а принадлежит множеству А).
Утверждение "а не является элементом множества А" записывается в виде аА (а не принадлежит множеству А).
Множества А и В называются равными (обозначается А = В), если они состоят из одних и тех же элементов.
Если каждый элемент множества А является также элементом множества В, то говорят, что А содержится или включается в В. В этом случае пишут А В. Множество A называется подмножеством множества B,если A B.
В тех случаях, когда одновременно имеют место соотношения A B и A B, говорят, что A строго включается в B, и используют запись A B.
1.3Операции над множествами
Объединением множеств A и B (обозначается A B) называется множество, состоящее из всех элементов, принадлежащих хотя бы одному из этих множеств, т.е A B = а а A или а B.
Пересечением множеств A и B (обозначается AB) называется множество, состоящее из всех элементов, принадлежащих каждому из этих множеств, т.е. А B = а а А и а B.
Разностью множеств А и B (обозначается А \ B) называется множество, состоящее из всех элементов множества A , не принадлежащих множеству B, т.е. А \ B =а а А и а B.
Дополнением
множества
А
в универсальном множестве U
(обозначается
,
А)
называется множество, состоящее из всех
элементов универсального множества U,
не принадлежащих множеству А,
т.е.А
= U
\ A.
Симметрической разностью множеств A и B (обозначается A B или A B) называется множество, состоящее из всех элементов, принадлежащих в точности одному из этих множеств, т.е. A B а либо а A и а B, либо а A и а B. Операция симметрической разности может быть выражена через операции объединения, пересечения и разноси следующим образом A B = (A \ B) (B \ A) = (A B) \ (A B).
Операции над множествами можно проиллюстрировать графически с помощью диаграмм Эйлера-Венна. В этом случае исходные множества изображают кругами, а множество-результат выделяют штриховкой.
Рис.I. Операции над множествами: а) объединение; б) пересечение; в) разность; г) дополнение; д) симметрическая разность.
1.4Основные законы алгебры множеств
1) Коммутативные законы
А В = В А
А В = В А
А В = В А
2) Ассоциативные законы
А (В С) = (А В) С
А (В С) = (А В) С
3)Дистрибутивные законы
А (В С) = (А В) (А С)
А (В С) = (А В) (А С)
4)Законы с и U
А
= А А
U = А А
=
U
А = А U = U А =
=
= U
6) Законы идемпотентности
А
А = А А
А = А
= А
7) Законы поглощения
А (А В) = А А ( В) = А В
А (А В) = А А ( В) = А В
8) Законы де Моргана
______
A
B =
_______
A B =
9) Законы склеивания
(А В) ( В) = В
(А В) ( В) = В
Справедливость законов алгебры множеств доказывается на основе определения равенства: Х = Y, если
1) Х Y: x X x Y;
2) Y Х: y Y y X.
Сформулированный принцип называют интуитивным принципом объемности.
Для доказательств будем использовать следующие обозначения ({ − и ; [ − или ) и соотношения :
x
A
B
x
A
B
x
A
B
x
A
B
x
A \ B
x
A \ B
x
A
Например:
Используя отношения принадлежности, доказать тождество
(A B) \ C = (A \ C) (B \ C).
Пусть X = (A B) \ C;
Y = (A \ C) (B \ C).
Если x X x (A B) \ C
или
.
Если y Y y (A \ C) (B \ C)
y
[(A
\ C)
\ (B
\ C)]
[(B
\ C)
\ (A
\ C)]
или
.
Отсюда или = или .
Следовательно тождество верно.
