1. Понятие множества. Конечные и бесконечные множества, пустое множество. Подмножество: количество подмножеств конечного множества

40. Понятие ориентированного графа (орграфа). Способы задания орграфа. Если пара в наборе х является упорядоченными x=(ViVj),Vi — начало, Vj — конец ребра, то граф называется ориентированным или орграфом. Для ориентированных графов справедливо утверждение (ViVj)≠(VjVi). 41. Матрица смежности для орграфа. Степень входа и степень выхода вершины. Матрицей смежности орграфа D, называется квадратная матрица А(D)=[aij] порядка n, у которой элементы aij равны. Степенью вершины v графа называется число дельта(v) ребер инцидентных вершине v. Замечание. В случае не ориентированного псевдографа вклад каждой петли в степень вершины равен 2. Полустепенью исхода вершины v орграфа D называется число дельта+(v) дуг исходящий из вершины v. Полустепенью захода вершины v орграфа D называется число дельта-(v) дуг заходящих в вершину v. Замечание. В случае ориентированного псевдографа вклад каждой петли равен 1 и в полустепень исхода и в полустепень захода. 42. Ориентированный путь. Ориентированный цикл (контур). Пусть дан ориентированный граф G (V, X). Последовательность V1x1V2x2,…,xkVk+1 (k=>1), в которой чередуются вершины и ребра, называется путем, соединяющим вершины V1 и Vk+1. Все пути делятся на замкнутые и незамкнутые. Не замкнутый путь, в котором все дуги попарно различны, называется цепью. Цепь, в которой все вершины попарно различны, называется простой цепью. Замкнутый путь, в котором все дуги попарно различны, называется контуром. Контур, в котором все вершины попарно различны, называется простым. 44. Матрица достижимости. Эквивалентность (взаимодостижимость) вершин в орграфе. Матрицей достижимости орграфа D называется квадратная матрица T(D)=[tij] порядка n, у которой tij равно: 1, если Vj достижима из Vi; 0, если Vj не достижима из Vi.

1. Множество всех упорядоченных пар (ai, bj) обычно называют декартовым произведением множеств А и В (иногда — прямым произведением. Для обозначения этой операции используется знак арифметического умножения: A xB.
2. Операции над множествами: объединение, пересечение, разность, симметричная разность, дополнение.
Объединением или суммой n множеств
A1, A2, …, An называется множество, состоящее из эле-
ментов, входящих хотя бы в одно из этих n множеств:
A= A1U A2U…UAn
где знак U обозначает операцию объединения множеств.
Пересечением или произведением [47, с. 93] n
множеств A1, A2, …, An называется множество A, каждый
элемент которого принадлежит каждому из множеств
A1, A2, …, An:
A=A1nA2nA3n…nAn
где знак n обозначает операцию пересечения множеств.
дополнением множества A называется множество всех тех элементов, которые являются элементами множества I, но не входят в множество A. Обозначается дополнение чертой над символом мно-
жества: A
Разностью множеств A и B называется множество всех элементов, принадлежащих множеству A, но не входящих в множество B. Обозначать разность множеств будем знаком минус
Симметрическая разность множеств A и B (ее
иногда называют также дизъюнктивной разностью) —
это мно-жество вида
A ⊕B = { x / x ∈A ∧x ∉B, или x ∉A ∧x ∈B},
где знак ⊕обозначает операцию симметрической разно-
сти (используют и другие знаки, например A B [3]).
3.
4. Пусть дано множество вида
А = {а1,а2, …, аn }.
Зафиксируем элементы этого множества в каком-либо порядке. Затем переставим местами некоторые элементы. Получим новую последовательность. Снова переставим некоторые элементы и т. д. Указанные последовательности называются перестановками без повторений.

Дано множество А, содержащее n элементов. Из них образуют упорядоченные последова-тельности длины m, в которых каждый элемент множества А встречается не более одного раза. Эти последовательности называют размещениями без повторений.

Дано множество, содержащее n элементов. Из них образуют размещения с повторениями, т. е. упорядоченные последовательности длины m, причем одни и те же элементы в любую последова-
тельность могут входить многократно.
10. Существуют 2 вида нормальных форм для БФ: дизъюнктивная нормальная форма (ДНФ) и конъюнктивная нормальная форма (КНФ). ДНФ называется дизъюнкция элементарных конъюнкций. КНФ – конъюнкция элементарных дизъюнкций.
11. Элементарное высказывание (буква) является формулой нулевого уровня. Если элементарное высказывание всегда верно, мы будем его обозначать буквой И, а если оно всегда неверно, — буквой Л. Тогда формулы первого уровня — это элементарные высказывания, к которым применена только одна логическая связка.
Пусть Ф1 и Ф2 — формулы ненулевого уровня. Тогда записи (¬(Ф1)), ((Ф1) (Ф2)), ((Ф1) (Ф2)), ((Ф1)→(Ф2)) также являются формулами. Если же одна из формул Ф1 и Ф2 , к которым применяется логическая связка, имеет нулевой уровень, то она в скобки не заключается.
13.

17.Элементы Графа состоит из точек и линий, которые их соединяют. Точки называют

вершинами графа, а линии — ребрами. Два ребра называются смежными, если у них есть
общая вершина. Два ребра называются кратными, если они соединяют одну и ту же пару
вершин.
18. Бинарное отношение R определяется как соотношение A R B, которое