- •1. Понятие логического высказывания. Элементарное и сложное высказывание. Логические выражения (формулы) и логические операции. Диаграммы Венна.
- •2. Представление логических выражений в дизьюнктивной (коньюнктивной) нормальной форме. Теорема Шеннона и принцип двойственности.
- •3. Логические законы (тавтологии).
- •4.Множества и подмножества.Универсально множество.Основные определения и свойства.Мощность множества,степень множества.
- •5 Операции над множествами, их свойства. Связь с логическими законами.
- •6.Описание числовых множеств на плоскости.Диаграммы Эйлера.
- •10.Понятие функции как специального вида отношений. Инъекцивная, сюрьективная, биективная функции
- •8. Бинарные отношения. Основные определения и способы задания отношений. Обратное отношение. Композиция отношений.
- •7.Кортеж, прямое произведение множеств. Понятие графика и свойства графиков.
- •11. Алгебраические системы. Алгебра множеств и булева алгебра.
- •22. Элементы цикломатики. Фундаментальная система циклов, цикломатическое и коциклическое число.
- •13.Понятие изоморфизма графов. Основные инварианты графа. Теорема Эйлера о степенях вершин. Подграфы и операции над графами.
- •24. Гамильтоновы графы. Достаточные условия существования гамильтонова цикла.
- •15. Вершинная и реберная связность графа. Мосты, блоки, точки сочленения. Разделяющие множества и разрезы. Теорема Менгера в вершинной и реберной форме
- •16. Двудольные графы и паросочетания. Свойства двудольных графов. Теорема Холла о совершенном паросочетании.
- •17. Неориентированные (свободные) и ориентированные (корневые) деревья. Свойства деревьев.
- •19. Способы представления деревьев в эвм. Упорядоченные и бинарные деревья, их свойства.
- •20.Поиск кратчайших путей на взвешенных графах. Алгоритм Форда-Беллмана и алгоритм Дейкстры.
- •21. Сети и потоки в сетях. Топологическая сортировка сети. Определение потока. Теорема Форда-Фалкерсона.
- •25. Задача коммивояжера. Решение задачи методом ветвей и границ.
- •27. Задача о раскраске графа. Понятие хроматического числа, его связь с валентностью вершин. Примеры графов с известным хроматическим числом. Теорема о раскраске планарных графов
- •23. Эйлеровы и полуэйлеровы графы. Алгоритм построения эйлерова цикла в эйлеровом графе.
4.Множества и подмножества.Универсально множество.Основные определения и свойства.Мощность множества,степень множества.
Множество - некоторая совокупность абстрактных или реальных объектов, рассматриваемая как единое целое в рамках решаемой задачи. Математическая теория множеств оперирует с абстрактными понятиями, а не с конкретными объектами. Потому-то в абстрактной математической теории иногда возникают казусы, называемые парадоксами
Способы задания множеств. Если множество состоит из небольшого числа элементов, то его можно задать простым перечислением. Если нет, то можно найти и сформулировать какое-то свойство, которым все эти элементы обладают, или условие, которому они удовлетворяют. Отсюда три способа задания множества: перечислением, предикатом (условием), или способом отбора элементов (алгоритмом порождения множества).
Перечисление: A={a1,a2,…,an}. Пример: множество простых чисел из первого десятка натуральных чисел - A={1,2,3,5,7}.
Предикатный способ: A={a|P(a)}, где P(a) – условие (предикат), которому удовлетворяет а. Пример: множество положительных действительных чисел – A={a|a>0}.
Порождающая процедура: A={a|a=F}. Пример: множество из n нечетных положительных чисел - A={a|a=2k+1, k=0,1,2,3,…n}.
Если множество содержит очень большое количество элементов, его можно описать только предикатом или порождающей процедурой.
Количество элементов, из которых состоит множество A, называется мощностью множества и обозначается M(A)=|A|.
Объект a является элементом множества A, обозначают так: aA. Если объект не является элементом A, пишут aA. aA – это элементарное высказывание, которое может быть либо истинным, либо ложным, но не то и другое вместе. Это высказывание часто называют предикатом принадлежности.
В теории множеств совокупность объектов, из которой формируются множества конкретной модели, называют универсальным множеством или универсумом. Универсум принято обозначать буквой U. Множество состоит из отдельных элементов, значит, оно делимо и можно ввести еще одно понятие – подмножество множества А. Будем обозначать его Q(A) и писать, что Q(A)A. Если Q(A) может совпадать с A, пишут Q(A)A. Множество множеств иногда называют классом или семейством.
Сколько же подмножеств мы можем сформировать из нашего конкретного множества А? Давайте заведем коробку, куда будем складывать элементы ai, назовем ее Q(A) и займемся комбинаторикой.
Вначале наша коробка пуста, то есть ai, i=1,…,|A| высказывание «aiA» ложно. Множество, не содержащее ни одного элемента, называют пустым и обозначают символом . Итак, Q0(A)=. Для него мы имеем набор истинностных значений высказываний «aiA» (набор логических переменных) - (0,…,0). Теперь кинем в коробку один элемент. Получим набор значений логических переменных (0,…,1). Уберем выбранный элемент и кинем другой. Получим набор (0,…,1,0). Потом будем кидать парами, тройками и так далее. Таких наборов для М двоичных переменных, как мы уже знаем (вспомните таблицы истинности) - 2|A|. Значит, мощность множества всех подмножеств заданного множества A мощности M(A)=|A| есть 2|A|, что соответствует количеству различных наборов из M булевых переменных. Множество всех подмножеств {Qi(A)} данного множества A поэтому называют булеаном. B(A)={Qi(A)|i=0,1,…, 2|A| }.
Любому подмножеству конечного множества мощности n можно сопоставить элементарную конъюнкцию из n переменных, где каждой переменной xi соответствует высказывание «aiA».
Сколько существует подмножеств заданной мощности N<M для нашего множества A? Способ расположения элементов в такой конструкции нас не интересует. Эта ситуация соответствует такому понятию комбинаторики, как число сочетаний из M элементов по N. Число возможных перестановок из N элементов PN=N!, число размещений из M элементов по N, с учетом их положения (с нумерацией элементов) .
Если не учитывать нумерацию элементов внутри подмножества (что и называется сочетанием), то это число будет в PN раз меньше: . Итак, |{Qi}|=.
Степенью множества A называется его прямое произведение само на себя: An=A…A – всего n раз