- •Дидактический план
- •Литература Основная
- •Дополнительная
- •Перечень умений
- •Тематический обзор* введение. Предмет дискретной математики
- •1. Способы задания множества
- •1.1. Множество. Подмножество. Универсальное множество
- •1.2. Операции над множествами: пересечение, объединение, разность, дополнение
- •1.4. Декартово произведение множеств
- •1.3. Порождающая процедура
- •2. Функциональные соответствия
- •2.1. Соответствие между множествами
- •2.2. Взаимно однозначное соответствие
- •2.3. Числовые и точечные промежутки
- •2.4. Суперпозиция функций
- •2.5. Схемы из функциональных элементов
- •3. Алгебраические операции
- •3.1. Операции на множестве
- •3.2. Ассоциативные и коммутативные операции
- •3.3. Двоичная система счисления
- •3.4. Проценты
- •4. Бинарные отношения
- •4.1. Отношения на множествах
- •4.2. Рефлексивные, симметричные, транзитивные отношения
- •4.3. Отношения эквивалентности
- •4.4. Отношения порядка
- •Приложения
- •Примеры решения задач
- •О мощности множеств действительных чисел
- •Двоичный 5-мерный куб
- •Задания для самостоятельной работы
- •1. Составьте логическую схему базы знаний по теме юниты:
- •2. Решить задачи 1–10.
- •Тренинг умений Пример выполнения упражнения тренинга на умение № 1 Задание
- •Решение
- •Пример выполнения упражнения тренинга на умение № 2 Задание
- •Пример выполнения упражнения тренинга на умение № 3 Задание
- •Пример выполнения упражнения тренинга на умение № 4 Задание
- •Пример выполнения упражнения тренинга на умение № 5 Задание
- •Решение
- •Пример выполнения упражнения тренинга на умение № 6 Задание
- •Решение
- •Глоссарий
- •Дискретная математика юнита 1
Глоссарий
№ п/п |
Новое понятие |
Содержание |
1 |
2 |
3 |
1 |
Множество |
совокупность элементов, набор каких-либо предметов (объектов); обозначение A ={x: p(x)} - A есть множество элементов х, удовлетворяющих условию p(x) |
2 |
Характеристическое свойство элементов множества А |
свойство, которым обладают все элементы множества А и не обладает ни один из элементов, не принадлежащих А |
3 |
Подмножество |
множество Н, каждый элемент которого принадлежит также множеству М, называется подмножеством множества М |
4 |
Пересечение множеств |
множество А ∩ В, состоящее из элементов, принадлежащих множеству А и множеству В одновременно |
5 |
Объединение множеств |
множество А В, состоящее из всех элементов, которые принадлежат множеству А или множеству В |
6 |
Разность множеств |
множество А \ В, состоящее из тех элементов множества А, которые не принадлежат множеству В |
7 |
Симметрическая разность множеств |
множество А Δ В, состоящее из всех элементов, которые принадлежат ровно одному из множеств А и В |
8 |
Дополнение множества |
множество
|
9 |
Разбиение множества |
система {Bα} непустых подмножеств множества A, что все попарные пересечения – пусты (Bi ∩ Bj = , если i ≠ j, а их объединение Bα равно A. Сами Bα называются классами, или блоками разбиения. |
10 |
Декартово (прямое) произведение множеств |
1) для двух множеств: произведение A B - множество всех пар (a, b), где a A, b B; 2) для n множеств: произведение A1 A2 ... An – множество всех векторов (a1, a2,…,an), где ai Ai (т.е. a1 A1, a2 A2,..., an An); если все Ai одинаковы и равны A, то произведение A A …. A обозначается An и n раз называется n-й степенью множества A |
11 |
Соответствие между множествами |
соответствие A → B: всем или некоторым элементам множества А сопоставлены каким-нибудь способом один или несколько элементов множества В |
12 |
Образ элемента а при соответствии А→В |
множество всех элементов b B, соответствующих элементу а А |
13 |
Прообраз элемента b при соответствии А→В |
множество всех элементов a A, которым соответствует элемент b B |
14 |
Однозначное (функциональное) соответствие A → B, или отображение множества A в множество B |
соответствие, при котором каждому элементу a A поставлен в соответствие единственный элемент b B |
15 |
Взаимно-однозначное соответствие (взаимно-однозначное отображение) множеств |
правило, при котором каждому элементу A поставлен в соответствие один элемент множества B, и при этом соответствии каждый элемент B соответствует одному и только одному элементу А |
16 |
Эквивалентные множества |
множества, между которыми можно установить взаимно однозначное соответствие |
1 |
2 |
3 |
17 |
Счетное множество |
множество, эквивалентное множеству натуральных чисел |
18 |
Интервал (открытый промежуток) |
множество чисел A = {x: a < x < b}, расположенных в промежутке между числами a и b; обозначение (a, b). Концы промежутка не принадлежат интервалу |
19 |
Отрезок (замкнутый промежуток) |
множество чисел B = {x: a ≤ x ≤ b} обозначается [a, b]. Концы промежутка принадлежат интервалу |
20 |
Окрестность точки |
любой интервал, содержащий эту точку |
21 |
Суперпозиция функций |
функция, полученная из n-местной функции f(x1, x2,.., xn) и системы n функций g1, g2,..., gn некоторой подстановкой функций g1, g2,..., gn во внешнюю функцию f вместо переменных и переименованиями переменных |
22 |
Формула |
выражение, описывающее суперпозицию и содержащее функциональные знаки, символы независимых переменных (аргументов) и констант (параметров) |
23 |
Характеристическая функция множества |
пусть В = {0, 1} – множество из двух чисел. Для подмножества М универсального множества U (M U) – отображение χM: U → B, ставящее в соответствие элементам множества M единицу, а элементам дополнения – ноль |
24 |
Булеан В(Е) |
множество всех подмножеств множества Е |
25 |
Схема из функциональных элементов |
сеть, элементам которой приписаны (сопоставлены) функции, так что элементу S с k входами соответствует k-местная функция f(x1, x2,..., xk) |
26 |
Бинарная алгебраическая операция φ(a, b), или a φ b на множестве М |
паре элементов a, b множества М сопоставляется элемент того же или другого множества |
27 |
Множество, замкнутое относительно операции φ |
применение операции φ не выводит за пределы множества М, т.е. всякий результат операции φ над элементами множества М также принадлежит М |
28 |
Алгебра |
система А = (L; Ω), состоящая из множества L и набора операций Ω = {φ1, φ2,..., φk}, действующих на множестве L. Множество L называется носителем, а система операций Ω – сигнатурой алгебры А |
29 |
Алгебра множеств (алгебра Кантора) |
система (В(U), , ∩, ‾‾) на булеане В(U) с операциями объединения, пересечения и дополнения |
30 |
Ассоциативная бинарная операция |
операция φ, обладающая сочетательным свойством |
31 |
Коммутативная бинарная операция |
операция φ, обладающая переместительным свойством: a b = b a |
32 |
Бинарное (двуместное) отношение |
некоторое множество R
пар
|
33 |
Рефлексивное отношение |
бинарное отношение, обладающее свойством: для любого а выполнено а R a |
34 |
Антирефлексивное отношение |
бинарное отношение, обладающее свойством: для любого а выполнено а a |
35 |
Симметричное отношение |
бинарное отношение, обладающее свойством: для любых a, b выполнено aRb bRa (т.е. из aRb следует bRa) |
36 |
Антисимметричное отношение |
бинарное отношение, что для любых выполнено: если a ≠ b, то aRb b a (т.е. если a и b – в этом порядке(!) – находятся в отношении R, то b и a – нет). Это же свойство выражают иначе: если aRb и bRa, то a = b |
1 |
2 |
3 |
37 |
Транзитивное отношение |
бинарное отношение, обладающее свойством: для любых трех элементов a, b, c выполнено: если aRb и bRc, то aRc (если в отношении R находятся a и b, а также b и c, то в этом отношении находятся а и c) |
38 |
Отношение эквивалентности |
бинарное отношение, обладающее свойствами рефлексивности, симметричности и транзитивности |
39 |
Классы эквивалентности отношения R на множестве |
разбиение множества такая, что 1) любые два элемента из одного класса эквививалентны; 2) любые два элемента из разных классов не эквивалентны. |
40 |
Отношения порядка |
отношения x y (x предшествует y) обладают свойствами транзитивности и антисимметричности: 1) если (a b) и (b c), то (a c); 2) если (a b) и a b, то не выполнено (b a)
|
41 |
Линейно упорядоченное множество |
множество, на котором задано отношение порядка, причем любые два элемента множества М сравнимы |
42 |
Частично упорядоченное множество |
множество, на котором задано отношение порядка, причем допускаются несравнимые пары элементов |
43 |
Алфавит |
упорядоченное множество попарно различных символов, называемых буквами алфавита |
44 |
Слово в алфавите |
упорядоченная последовательность из символов алфавита |
45 |
Максимальный элемент частично упорядоченного множества |
элемент a A максимальный, если не существует элемента b A, для которого a b |
46 |
Минимальный элемент частично упорядоченного множества |
элемент a A минимальный, если не существует элемента b A, для которого b a |
47 |
Наибольший элемент частично упорядоченного множества |
элемент a A наибольший, если для всякого элемента b A (а ≠ b) выполнено b a |
48 |
Наименьший элемент частично упорядоченного множества |
элемент a A наименьший, если для всякого элемента b A (а ≠ b) выполнено а b |
