- •1.Множества и подмножества. Операции над ними.
- •2. Основные равносильности алгебры множеств.
- •3. Определение кортежа. Декартово (прямое) произведение множеств.
- •4. Определение отношения и теоретико-множественные операции над ними
- •5. Операции над отношениями.
- •6. Образ и прообраз множества в отношении.
- •7.Соответствия. Свойства соответствий.
- •8.Отношения. Свойства отношений.
- •9.Разбиение множеств.
- •10.Отношение эквивалентности.
- •11.Отношение порядка.
- •12. Табличный способ задания данных. Домены и атрибуты.
- •13. Ключи и нормализованное отношение. Реляционная модель базы данных.
- •14. Реляционная алгебра. Традиционные теоретико-множественные операции.
- •15. Реляционная алгебра. Специальные операции.
- •16. Реляционная алгебра как язык запросов.
- •17. Первая и вторая нормальные формы отношений
- •17. Первая и вторая нормальные формы отношений
- •20. Локальные степени графа.Части графа и подграфы.
- •21. Эйлеровы графы.
- •22. Гамельтоновы цепи и циклы.
- •23. Алгоритм Райяна решения задачи коммиваяжёра.
- •24. Деревья. Основные понятия и определения.
- •25. Задача о минимальном соединении (построение дерева-остова).
- •Алгоритм:
- •26. Деревья. Задача о минимальном пути.
- •Алгоритм:
- •Алгоритм Дейкстры:
- •27. Транспортные сети. Задача о максимальном потоке.
- •28. Теорема и алгоритм Форда-Фалкерсона.
- •Алгоритм построения полного потока:
- •Алгоритм Форда-Фалкерсона:
- •29. Деревья. Циклический ранг графа.
- •30. Задача раскраски графов. Хроматическое число.
- •32. Основные равносильности алгебры логики.
- •33.Функции логических переменных
- •X 0 1 Прим.
- •X1 x2 x3
- •X1&x2, x1’&x2, x1&x1& x2’.
- •36.Приведение к сндф по таблицам истинности
- •37. Аналитическое приведение формулы к сндф.
- •31. Высказывание. Основные логические операции.
- •18. Третья нормальная форма отношений.
- •19. Графы. Основные определения и способы задания.
1.Множества и подмножества. Операции над ними.
Множества относятся к основополагающим понятиям математики. Синонимы множества – совокупность, набор. Элементы, входящие во множество – элементы множества. (). К элементам множества предъявляется только требование – быть точноопределёнными и различными (должны удовлетворять закону противоречия исключённого третьего).З-н исключённого третьего: любой элемент может либо принадлежать множеству либо нет (третьего не дано). З-н противоречия: должна быть возможность однозначно судить элементы множеству или. Порядок элементов в множестве безразличен. Множества по числу элементов делятся на: конечные и бесконечные.
Ø - пустое множество (не содержит ниодного элемента).
Множества и подмножества АсВ (А – подмножество В), еслисправедливо, следовательно.
–справедливо. Любое множество является подмножеством самого себя. Если , то А – собственное подмножество В.(собственное)(несобственное). Пустое множество – подмножество А – истина вследствие ложной последовательности.
Равенство множеств Множества равны, если они состоят из одних и тех же элементов. А=В тогда и только тогда, когда .
Операции над множествами
1)Объединение множеств – множество, к-е содержит все элементы объединяющихся множеств (теоретикомножественное сложение). , С- состоит из всех тех элементов, к-е принадлежат множеству А или В.;.
2) Пересечение множеств – мн-во, состоящее из эл-в, к-ые принадлежат всем множествам. ,;. ЕслиØ , то А и В не пересекаются.
3)Разность множеств – мн-во состоящее из элементов, к-ые принадлежат 1-му множеству и не принадлежат второму. С=А\В.
4)Дополнение множества А – множество элементов, к-ые не принадлежат множеству А. .
Все множества, к-ые рассматриваются одновременно при операциях, должны быть подмножеством «универсума» (основного множества) . От выборазависит, что считать дополнением.
Беулеан М – множество всех подмножеств множества М. А\В=..
Принцип двойственности Одним из вариантов выражения двойственности является принцип де Моргана.
L=P : LcP, PcL. .
1)Рассмотрим любой элемент LcP и докажем, что любой элемент P принадлежит L. , еслидополнению, то он непоследнему.. Но если, тои,. Значит.
2) PcL.
2. Основные равносильности алгебры множеств.
Основные операции: объединение, пресечение, дополнение. Применяя операции над подмножеством некоторого основного множества принадлежащие множеству всех подмножеств, в результате получаем некоторое подмножество основного множества. Множество всех подмножеств основного множества с определёнными в этом множестве тремя операциями, к-ые обладают определённым набором свойств – алгебра множеств.
Основные свойства:
1) Свойство двойного отрицания: .
2) Закон идемпотентности: ,.
3) Закон коммутативности: ,.
4) Свойство ассоциативности: ,.
5) Закон де Моргана: ,.
6) Закон дистрибутивности: ,.
7) Закон тождества: Ø,.
8) Закон отрицания: ,Ø.
9) Закон поглощения: ,.
Основное множество иногда называют и обозначают единицей алгебры. Пустое множество - нуль. Пересечение - умножение. Объединение – сложение.
Правило опускания скобок: приоритет операций: скобки можно опускать если согласно приоритету операций восстанавливается требуемая последовательность операций. - однотипно.
Эквивалентные множества. Мощность множества 2 множ. эквивал. если между их элем. можно установ. взаимооднозначное соответств. (+ одинаковое число элементов). Множество счётных чисел эквивалентно множеству натуральных чисел. Мощностью множества называется то общее, что есть у всех множеств эквивалентных данному множеству.|A|=W. Множество целых чисел – чётное множество. Несчётное множество – бесконечное множество не эквивалентное счётному множеству. Континиум – самый простой пример несчётного множества. Например, множество точек отрезка [0;1] имеет мощность множества континиума.