- •Определение Множества. Элементы. Пустое, универсальное, подмножество. Равенства подмножеств. Множествами и их свойства. Декартово произведение множеств.
- •2. Операции над множествами. Диаграммы Венна.
- •Отношения. Унарные и бинарные, Тождественное и универсальное.
- •5. Отношения. Область определения, значений. Обратное отношение.
- •9. Специальные бинарные отношения:
- •Функция. Инъекции, сюръекции, биекции. Понятие последовательности. Частичная функция.
- •Эквивалентность множеств. Мощности множества. Сравнение мощностей. Типы множеств.
- •Матрицы бинарных отношений и их свойства.
- •11.Булевы алгебры.
- •12. Логические операции, их таблицы истинности.
- •23. Перестановки.
- •14. Эквивалентность формул.
- •36. Планарные графы.
- •27. Определение графа. Виды и способы задания графов.
- •28. Подграфы и части графа. Операции над графами. N-Мерные кубы.
- •Объединение: .
- •29. Маршруты, циклы, цепи. Достижимость и связность (матрицы достижимости, контрдостижимости, связности).
- •21. Теорема Жегалкина. Способы построения полиномов Жегалкина. Линейные функции.
- •41. Фундаментальные циклы, разрезы. Матрицы фундаментальных циклов, разрезов.
- •18.Минимизация днф: метод Квайна
- •13. Булевы функции, способы их задания. Представления булевых функций формулами.
- •15. Дизъюнктивные и конъюнктивные нормальные формы. Алгоритм приведения формулы к днф и кнф.
- •16. Минимизация днф. Сокращенная, тупиковая, минимальная днф.
- •17. Минимизация днф Карты Карно.
- •19. Принцип двойственности. Самодвойственные функции.
- •26. Объекты теории графов. Цели и методы.
- •30. Эйлеровы графы, циклы, цепи. Алгоритм построения эйлерова цикла.
28. Подграфы и части графа. Операции над графами. N-Мерные кубы.
Граф G’=<M’,R’> называется подграфом графа G=<M,R>, если и . Граф G’ называется частью графа g, если и .
Операции над графом G=<M,R>:
Добавление вершины:
Добавление дуги:
Удаление вершины:
Удаление дуги:
Отождествление вершин:
Дополнением графа без петель G=<M,r> называется граф .
Двухместные операции над графами G1=<M1,R1>, G2=<M2,R2>:
Объединение: .
Пересечение: , если .
Кольцевая сумма: .
Соединение:
Произведение: , где
Неорграф без петель называется полным, если его любые две различные вершины смежны. Полный граф, имеющий n вершин обозначается Kn.
n-мерными кубами. Рассмотрим граф K2, вершины которого обозначим 0 и 1. n-куб Qn определяется по следующим правилам: Q1=K2, , n>1. Вершинами n-куба являются всевозможные n-ки, состоящие из наборов нулей и единиц (всего таких наборов 2n), а ребра задаются по следующему правилу: вершины смежны тогда и только тогда, когда соответствующие кортежи различаются ровно одной координатой.
29. Маршруты, циклы, цепи. Достижимость и связность (матрицы достижимости, контрдостижимости, связности).
Пусть G=<M,R> - граф. Последовательность a1,u1,a2,u2,…,un,an+1, где , называется маршрутом, соединяющим вершины a1 и an+1, если ui=(ai,ai+1). Число n дуг в маршруте называется его длиной.
Пусть G – неорграф. Маршрут (a1,an+1) называется цепью, если все ребра [a1,a2],…,[an,an+1] различны, и простой цепью, если все его вершины, кроме, первой и последней, различны. Маршрут называется циклическим, если a1=an+1. Циклическая цепь называется циклом, а циклическая простая цепь – простым циклом.
Пусть G – орграф. Маршрут называется путем, если все его дуги различны. Путь называется контуром, если a1=an+1. Граф, не имеющий контура, называется бесконтурным.
Неорграф называется связным, если любые две его несовпадающие вершины соединены маршрутом. Граф G называется связным, если соответствующий ему неорграф F(G) тоже является связным.
Теорема: Любой граф представляется в виде объединения непересекающихся связных (сильных) компонент. Разложение графа на связные (сильные) компоненты определяется однозначно.
Теорема: Если AG – матрица смежности графа G, то (i,j)-й элемент матрицы есть число (ai,aj)-маршрутов длины k.
Образуем из матрицы (bij)=E+AG+AG2+…+AGn-1 матрицу C=(cij) порядка n по следующему правилу: . Матрица С называется матрицей связности, если G – неорграф, и матрицей достижимости, если G-орграф.
Определим матрицу контрдостижимости Q=(qij): . Q=CT.
матрицу сильных компонент S=C*Q, где операция * означает поэлементное произведение матриц С и Q.
21. Теорема Жегалкина. Способы построения полиномов Жегалкина. Линейные функции.
Теорема Жегалкина: Всякая булева функция f(x1,…,xn) представима полиномом Жегалкина, т.е в виде , где в каждом наборе вида (i1,…,ik) все ij различны, а суммирование ведется по некоторому множеству таких несовпадающих наборов. Представление функции в виде полинома Жегалкина единственно с точностью до порядка слагаемых.
Полином Жегалкина называется нелинейным (линейным) если он (не) содержит произведения переменных. Линейность булевой функции равносильна линейности соответствующего полинома Жегалкина.
Аксиомы булева кольца и равенства, выражающие операции дизъюнкции, конъюнкции и отрицания через операции этого кольца:
Если в эквивалентности формулы φ и ψ являются различными конституентами 1, то их произведение равно 0.