- •Едеральное агентство по образованию
- •Оглавление
- •Раздел 1. Элементы теории множеств 8
- •Раздел 2. Элементы комбинаторики 20
- •Раздел 3. Алгебра логики 36
- •Раздел 4. Синтез управляющих систем 62
- •Раздел 5. Теория графов 77
- •Введение
- •Раздел 1 элементы теории множеств
- •1.1. Множества и операции над ними
- •1.2. Алгебра множеств
- •1.3. Разбиение множества на подмножества
- •1.4. Кортежи и декартово произведение множеств
- •1.5. Отображение множеств
- •1.6. Отношения
- •1.7. Свойства бинарных отношений
- •1.8. Алгебра подмножеств
- •1.9. Задания для самостоятельной работы
- •Раздел 2 элементы комбинаторики
- •2.1. Комбинаторика
- •2.2. Различные комбинаторные соотношения
- •2.3. Свойства биномиальных коэффициентов. Биномиальная теорема. Полиномиальная теорема
- •2.4. Принцип включения и исключения
- •2.5. Формула решета
- •2.6. Производящие функции
- •2.7. Производящие функции числа основных комбинаторных объектов
- •2.8. Задания для самостоятельной работы
- •Раздел 3 алгебра логики
- •3.1. Булевы функции
- •3.2. Формулы
- •3.3. Сопоставление формулам над множеством функций
- •3.4. Свойства элементарных функций
- •3.5. Разложение булевых функций
- •3.6. Совершенная д. Н. Ф., совершенная к. Н. Ф.
- •3.7. Полные системы
- •3.8. Примеры полных систем
- •3.9. Полиномы Жегалкина
- •3.10. Единственность представления булевых функций полиномами Жегалкина
- •3.11. Методы построения полиномов
- •I. Метод построения с помощью таблицы.
- •II. Метод неопределенных коэффициентов.
- •III. Метод суперпозиции.
- •3.12. Замыкание. Свойства операции замыкания. Замкнутые классы
- •3.13. Классы и их свойства
- •3.14. Линейные функции и их свойства
- •3.15. Принцип двойственности
- •3.16. Самодвойственные функции, их свойства
- •3.17. Лемма о несамодвойственной функции
- •3.18. Монотонные функции, их свойства
- •3.19. Лемма о немонотонной функции
- •3.20. Теорема о полноте в р2
- •3.21. Предполные классы
- •3.22. Возможность выделить из любой полной системы полную подсистему, состоящую из не более чем 4-х функций
- •3.23. Представление о результатах Поста
- •3.24. Задания для самостоятельной работы
- •Раздел 4 синтез управляющих систем
- •4.1. Схемы из функциональных элементов
- •4.2. Определение схем из функциональных элементов
- •4.3. Основные понятия и определения
- •4.4. Возможность реализации любой функции алгебры логики сфэ
- •4.5. Простейшие методы синтеза
- •4.6. Метод Шеннона
- •4.7. Асимптотически наилучший метод (метод о.Б. Лупанова)
- •4.8. Задания для самостоятельной работы
- •Раздел 5 теория графов
- •5.1. Элементы теории графов
- •5.2. Основные понятия и определения
- •5.3. Способы задания графа
- •5.4. Некоторые соотношения в графе
- •5.5. Перечисление графов
- •5.6. Оценка числа неизоморфных графов с p вершинами
- •5.7. Оценка числа неизоморфных графов с q ребрами
- •5.8. Укладки графов. Укладка графов в трехмерном пространстве
- •5.9. Планарность. Формула Эйлера для плоских графов
- •5.10. Следствия из формулы Эйлера для плоских графов
- •5.11. Операция подразделения ребра
- •5.12. Гомеоморфность графов
- •5.13. Теорема Понтрягина-Куратовского
- •5.14. Деревья и их свойства
- •5.15. Деревья и операции над ними
- •5.16. Оценка числа неизоморфных корневых деревьев на p вершинах
- •5.17. Задания для самостоятельной работы
- •Литература Основная
- •Дополнительная
- •Михеева Елизавета Алексеевна
1.5. Отображение множеств
Определение. Соответствие, сопоставляющее каждому элементу х множества Х один и только один элемент множества Y, называется отображением множества Х в множество Y.
Пример 12. Если каждое пальто в гардеробе висит на одном крючке, то ставя в соответствие каждому пальто крючок, на котором оно висит, получаем отображение множества пальто Х в множество крючков Y.
Элемент множества Y, соответствующий при отображении f элементу х из Х, обозначают f(x) и называют образом элемента х при этом отображении. Если f(x)=у, то элемент х называют прообразом элемента у при отображении f.
f : Х→Y (y = f(x)).
1.6. Отношения
Определение. Назовем n-местным отношением R на множестве М≠ Ø подмножество R Mn. При n=2 отношение R называют бинарным. То есть бинарным отношением между элементами множеств А и В называют любое подмножество R множества АВ и записывают R АВ. Для отношения R обратным является отношение R-1 ВА.
Бинарные отношения принято записывать в виде аRb, где а, b є М.
Графики прямых и обратных бинарных отношений, определенных на R, симметричны относительно биссектрисы 1 и 3 квадрантов.
1.7. Свойства бинарных отношений
1. Рефлексивность: аRa («быть не больше», «быть не меньше»).
2. Антирефлексивность: отношение не обладает свойством 1 для любого а (например, «быть больше», «быть меньше», «быть младше»).
3. Симметричность: для любых двух элементов а, b є М : аRb и bRа (т.е. R = R-1). Симметрична параллельность прямых, так как если a II b, то b II a («быть равным»; «быть взаимнопростым»).
4. Aнтисимметричность: если для а ≠ b верно отношение аRb, то ложно bRа («быть больше», «не меньше», «быть делителем»).
5. Транзитивность: если аRb и bRс, то аRс для любых а, b, с є М («быть больше», «быть параллельным», «быть равным»).
6. Антитранзитивность: отношение не обладает свойством 5.
7. Асимметричность: ни для одной пары а и b не выполняется одновременно аRb и bRа.
8. Связность: для любых а и b, если а ≠ b, то аRb или bRа.
Вывод :
Отношение ≤ и ≥ (нестрогого порядка), если оно рефлексивно, антисимметрично и транзитивно.
Отношение < и > (строгого порядка), если оно антирефлексивно, антисимметрично и транзитивно.
Пример 13. Бинарное отношение
R = {(x,y) : x є R, у є R, х2-у2>0} обладает свойствами антирефлексив-ности и транзитивности.
Пример 14. Бинарное отношение
R = {(x,y) : x є R, у є R, х-у ≥ 1} обладает свойствами антисимметрич-ности и транзитивности.
Пример 15. Свойством симметричности обладает бинарное отношение «быть подобным».
1.8. Алгебра подмножеств
Определение. Множество всех подмножеств множества М называется булеаном множества М и записывается Е = В(М).
Пример 16. Пусть М= {a,b,c,d}. Найти │E│=?
Решение: Е={Ø,{a},{b},{c},{d},{a,b},..,{a,b,c},..{a,b,c,d}}. Отсюда │E│= С°4 +С¹4+С²4+С³4+С44 = 24 = 16.
Замечание. {a}є Е ; {a,b} є Е ; {a,b,c} є Е ; { a,b,c,d} є Е. Но {{a}} Е ; {{a},{b}} Е; {{a,b,с,d}} E.
Пример 17. Х = {x1, ..,xn}. Найти │В(X)│.
Решение: │E│=│B(Х)│= 2n.