- •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. Эквивалентные преобразования. Доказательство.
- •34. Правила подстановки, замены.
- •35. Некоторые эквивалентные преобразования.
- •36. Приведение дизъюнктивной нормальной формы к совершенной дизъюнктивной нормальной форме.
- •37. Замкнутые классы. Свойства замыкания.
- •38. Класс функций, сохраняющих значение 0.
- •39. Класс функций, сохраняющих значение 1.
- •40. Принцип двойственности. Класс самодвойственных функций.
- •41. Класс монотонных функций.
- •42. Класс линейных функций.
- •43. Алгебра Жегалкина. Полином Жегалкина.
- •44. Полином Жегалкина. Теорема.
- •45. Полнота.
- •46. Лемма о немонотонных функциях.
- •47. Лемма о нелинейных функциях.
- •48. Функциональная полнота. Первая теорема о функциональной полноте.
- •49. Функциональная полнота. Теорема Поста.
- •50. Логические исчисления.
- •51. Высказывания. Формулы.
- •52. Интерпретация формулы. Теорема.
- •53. Логическое следование и логическая эквивалентность.
- •54. Логические эквивалентности. Доказательство.
- •55. Исчисление высказываний.
- •56. Понятие предиката.
- •57. Понятие квантора. Квантор существования. Квантор всеобщности.
- •58. Исчисление предикатов.
- •59. Аксиомы исчисления предикатов. Правила логического вывода.
- •60. Графы. Типы задач теории графов.
- •61. Графы. Основные определения.
- •62. Способы представления графов.
- •63. Идентификация графов, заданных своими представлениями.
- •64. Обходы графов.
- •65. Степени вершин графа.
- •66. Операции с частями графа.
- •67. Маршруты, цепи, циклы.
- •68. Связные компоненты графа.
- •69. Расстояния в графе.
- •70. Диаметр, радиус, центр графа.
- •71. Произведение графов.
- •72. Прямое произведение графов.
- •73. Эйлеровы циклы.
- •74. Теорема Эйлера.
- •75. Эйлеровы цепи.
- •76. Гамильтоновы циклы.
- •77. Некоторые классы графов и их частей. Дерево и лес.
- •78. Концевые вершины и ребра.
- •82. Цикломатическое число графа.
- •83. Ориентированные графы. Пути и циклы в ориентированном графе.
- •86.Деревья
- •49.Функциональная полнота. Теорема Поста
- •94. Блок-схемы алгоритмов
- •95.Машины Тьюринга. Основные определения.Машина
- •96.Машины Тьюринга.Сложение
- •96.Машины Тьюринга.Копирование
- •80.Типы вершин
- •84.Начальные и конечные вершины. Ранги вершин
- •90. Бінарне дерево
- •79. Дерево с корнем. Ветви.
- •81. Центры деревьев. Теорема.
- •85. Отношение достижимости. Базисный граф
- •88.Способы представления деревьев
1. Понятие множества.
Понятие «множество» относится к числу фундаментальных неопределяемых понятий в математике.
Множеством называется любая определенная совокупность объектов. Объекты их которых состоит множество называется элементами. Элементы множеств различны.
Множества обычно обозначаются прописными буквами лат. алфавита, а элементы – строчными.
П. N – множество натуральных чисел
P – множество простых чисел
Z – множество целых чисел
R – множество вещественных чисел
Если объект х принадлежит множеству, то он является элементом множества и обзначается хМ.
Если объект х не принадлежит множеству, то он не является элементом множества и обозначается х М.
- пустое множество, множество, которое не включает в себя элементов..
Обычно элементы множества выбираются из одного достаточно широкого множества U , которое называется универсумом.
Множества бывают конечные и бесконечные.
Число элементов в множестве М называется мощностью множества и обозначается М.
0 = 1
1,2,3,4,5 = 5
Если мощность множества А = мощности множества В, то говорят, что множества равномощны.
2. Способы представления множеств.
1)способ перечисления элементов;
а1,а2,а3,…аn
При помощи перечисления можно задавать только конечные множества, если способ перечисления использовать для перечисления бесконечных множеств, то форма записи не должна вызывать разночтений.
2) способ описания элементарных множеств путем задания их свойств:
Р:хх – «отличник»; К:хх – «четное число»
3) способ описания множества при помощи порождающей процедуры
Порождающая процедура – это способ получения элементов множества из уже имеющихся или из других объектов.
Элементами множества будут считаться все объекты, которые могут быть получены при помощи порождающей процедуры.
А:mm=2k, kN
4)способ описания множеств при помощи функции предикат.
Характеристически предикат – это некоторое логическое условие, выражение в фолме логического утверждения, которое принимает значение «истина» или «ложь».
М:хх5
Р(х) – в скобках указывается аргумент функции предикат.
С помощью перечисления можно задавать конечные множества. Бесконечные множества удобно задавать характеристическим предикатом или порождающей процедурой.
3. Операции над множествами.
Выполнение операций над множествами – это способ конструирования новых множеств из уже имеющихся.
1. Сравнение множеств
множество Х называется подмножеством множества Y, если каждый элемент множества Х принадлежит множеству Y.
Х Y: хХхY
Х – подмножество множества Х.
Если Х является подмножеством множества Y и множества не равны, то говорят, что Х – собственное подмножество множества Y.
Замеч. если требуется различать собственные и несобственные, то для обозначения собственных множеств используется С, для несобственных - С
2.Равенство множеств
множество Х и Y равны, если они являются подмножествами друг друга.
Х=У: Х Y и Y Х.
3.Объединение множеств
Объединение множеств Х и Y называется множество, состоящее из всех тех элементов, которые принадлежат хотя бы одному из множеств
XY:{xxX или xY}
=A1A2A3…As (общий случай)
4. Пересечение множеств
Пересечение множеств Х и Y называется множество, состоящие из тех и только тех, которые принадлежат и множеству X и множеству Y.
XY:{xxX и xY}
5. Разность множеств
Разность множеств Х и Y (ХY) называется множества всех тех элементов множества Х, которые не принадлежат множеству Y.
ХY:{xxX и xХ}
6. Симметрическая разность
(X∆Y)=(XY)/(XY)
7. Дополнение
:{xxX}