- •1.Основные понятия теории множеств.
- •2.Операции над множествами.
- •3.Соответствия, отображения и функции.
- •4. Отношения на множествах
- •5. Операции на множествах, понятие алгебры
- •6. Алгебра Кантора. Законы алгебры Кантора
- •7. Алгебраические системы. Решетка Хассэ
- •8.Задание множеств конституентами (числом)
- •9. Основные понятия комбинаторики
- •10. Размещения
- •11. Перестановки
- •12. Сочетания
- •13. Треугольник Паскаля
- •14. Бином Ньютона
- •15. Задание графов
- •16. Свойства графов
- •17. Понятие о задачах на графа
- •18. Понятие о переключательных функциях
- •19. Двоичные переключательные функции и способы их задания
- •20. Основные логические операции
- •21. Элементарные переключательные функции
- •22. Определение свойств переключательных функций
- •23. Функциональная полнота систем переключательных функций. Теорема Поста о функциональной полноте систем пф
- •24. Переключательные схемы - техническая реализация пф
- •25. Основные законы булевой алгебры пф
- •26.27. Формы представления переключательных функций. Сднф. Скнф
- •28. Цели минимизации пф
- •29. Основные понятия минимизации пф
- •30. Метод Квайна-Мак-Класки
- •31.32. Задание пф картой Карно. Карта Карно на три и четыре переменных
- •33. Минимизация на кубе соседних чисел
- •35. Основные определения теории автоматов
- •36. Описание конечных автоматов таблицами переходов-выходов и графами
- •37. Техническая интерпретация конечного автомата
- •38. Синтез комбинационных автоматов в заданном базисе
- •39. Элементарные автоматы памяти
- •40. Системы счисления - основа различных кодов
- •41. Представление информации в эвм
2.Операции над множествами.
Объединением множеств А и В называется множество АВ, все элементы которого являются элементами множества А или множества В:
АВ={x:xA или хВ},
где – знак объединения.
На диаграмме Эйлера это может быть показано штриховкой (рис. 2).
Рис. 2. Объединение множеств АВ
Пересечением множеств А и В называется множество АВ, элементы которого являются элементами обоих множеств:
АВ={x:xA и хВ},
где – знак пересечения.
Соответствующая диаграмма Эйлера изображена на рис. 3.
Рис. 3. Пересечение множеств АВ
Разностью множеств А и В называется множество А\В, состоящее из элементов, принадлежащих множеству А и не принадлежащих множеству В:
А\В={x:xA и хВ},
где – знак непринадлежности (отрицание принадлежности), \ – знак разности.
Соответствующая диаграмма Эйлера изображена на рис. 4.
Так, если А={1,2,3,4,5}, В={4,6}, то А\В={1,2,3,5}, В\А={6}.
Симметрической разностью множеств А и В называется множество АВ=(А\В)(В\А), изображенное на рис. 5, – знак симметрической разности.
Так, если А={1,2,3}, В={3,4,5}, то АВ={1,2,4,5}.
Рис. 5. Симметрическая разность множеств АВ
Рассмотренные операции являются двухместными (бинарными). Имеется одноместная (унарная) операция дополнения.
Дополнением множества А является множество , содержащее элементы универсума I, не включенные во множество А:
где – знак дополнения, «инверсия», читается «не А».
Соответствующая диаграмма Эйлера изображена на рис. 6.
Рис. 6. Дополнение множества А до универсума I
Так, если А={3,4}, а I={1,2,3,4,5}, тоA={1,2,5}.
Используя рассмотренные операции, можно выражать одни множества через другие, при этом сначала выполняется одноместная операция дополнения, затем пересечения и только потом – операция объединения (разности). Для изменения порядка выполнения операций в выражении используют скобки.
3.Соответствия, отображения и функции.
Соответствием между множествами А и В называется подмножество их декартова произведения GА·В.
Если (а,b)G, то b соответствует а при соответствии G. Множество проекций пр1G называется областью определения соответствия, множество пр2G – областью значений соответствия. Если пр2G=А, то соответствие полностью определенное (в противном случае – частичное). Если пр2G=В, то соответствие сюрьективно.
Множество всех bВ, соответствующих элементу а, в А называется образом а в В при соответствии G. Множество всех а, которым соответствует b, называется прообразом b в А при соответствии G.
Всюду определенное соответствие называют отображением и иногда записывают как Г:ХY, где – знак отображения.
Подмножество FX·Y называется функцией, если для каждого элемента х, хХ найдется не более одного элемента yY в парах вида (х,y)F. При этом, если для каждого элемента х имеется один элемент y, то функция полностью определена, в противном случае – частично определена (недоопределена). Множество Х – область определения функции F, множество Y – область значений функции. Часто вместо записи (х,y)F используют запись y=F(х), при этом элемент х называют аргументом или переменной, а y – значением функции F. Количество аргументов определяет местность функции.
Сопоставим с декартовым произведением двух множеств прямоугольную решетку, узлы которой взаимно однозначно соответствуют элементам декартова произведения [9-10].
На рис. 7а изображено подмножество декартова произведения множеств Х={х1,х2,х3,х4} и Y={y1,y2,y3}, не являющееся функцией, на рис. 7б – являющееся полностью определенной функцией; на рис. 7в – являющееся частично определенной функцией.
а) F1XY, не являющееся функцией, т.к. одному значению х может соответствовать два значения y. |
б) F2XY, являющееся полностью определенной функцией. |
в) F3XY, являющееся недоопределенной функцией, не определенной на значении аргумента х3. |
Соответствие G между множествами Х и Y называется взаимно однозначным, если каждому элементу хХ соответствует определенный элемент yY, и, наоборот, каждый элемент yY оказывается поставленным в соответствие одному элементу хХ.
Соответствие между множеством функций и множеством чисел называется функционалом [19]. Часто говорят «функционал качества».
Например, функционалом может быть определенный интеграл, ставящий в соответствие некоторой функции число.
Соответствие между двумя множествами функций называется оператором. Например, имеется оператор дифференцирования.
Множество А называется эквивалентным множеству В, если существует взаимнооднозначное соответствие множеств А и В, это обозначается как
А=В или АВ.
Этот факт позволяет определять неизвестную мощность одних множеств по известной мощности других, им эквивалентным. Множества, эквивалентные (равномощные) множеству натуральных чисел, называются счетными. В счетных множествах возможна нумерация элементов. Пример множества, не являющегося счетным – множество всех действительных чисел отрезка [0,1]. Это доказывается теоремой Кантора [19]. Попробуем пронумеровать это множество. Расположим все числа, изображенные бесконечными десятичными дробями в порядке нумерации:
0, а11 а12 а13 ...
0, а21 а22 а23 ...
0, а31 а32 а33 ...
. . . . . .,
где первая цифра индекса – номер бесконечной десятичной дроби. Рассмотрим теперь любую бесконечную десятичную дробь 0, b1 b2 b3... такую, что b1а11, b2а22, b3а33 и т.д. Такая дробь не входит в указанную последовательность, так как отличается от первого числа первой цифрой, от второго числа – второй цифрой и т.д. Следовательно, все числа из отрезка [0,1] не могут быть пронумерованы, т.е. это множество несчетно. Его мощность называется континуум и все эквивалентные ему множества называются континуальными. Так, множество всех подмножеств счетного множества континуально.