Специальные главы математики

Рецензенты: Жирнова Т.С. – доцент кафедры математики Ефременко В.М. – заведующий кафедрой электроснабжения

Множества и отображения

Лекция 1

Понятие множества

Множество – одно из основных понятий математики, является первичным и

Способы задания множеств

Множество считается заданным, если перечислены все его элементы или

Пустое множество

Если множество не содержит элементов, обладающих характеристическим признаком, то

Изображение множеств

Множества изображают с помощью кругов Эйлера ( диаграмм Венна).

Подмножество

Универсальное множество

Операции над множествами

К основным операциям над множествами относятся:
1. Пересечение множеств;
2.

Пересечение множеств

Объединение множеств

Разность множеств

Дополнение к множеству

U

A

Симметрическая разность

Кортежи и декартово произведение множеств, бинарные отношения, отображения множеств, функции.

Лекция 2

Кортежи

Равенство кортежей

Два кортежа равны, если:
1. Они имеют одинаковую длину;
2. Их координаты,

Декартовое произведение множеств

Бинарные отношения

Специальные бинарные отношения

1. Рефлексивное отношение;
2. Симметричное отношение;
3. Транзитивное отношение.

Рефлексивное бинарное отношение

Симметричное бинарное отношение

Транзитивное бинарное отношение

Отображение множеств

Составные высказывания. Простейшие связки, другие связки.

Лекция 3

Высказывания

Элементарные и составные высказывания

Составное логическое высказывание – образовано из других высказываний

Логические связки

Логическая связка – любая логическая операция над высказыванием.
Например, употребляемые в

Простейшие логические операции

Отрицание

Конъюнкция

Дизъюнкция

Импликация

Эквивалентность

1. Отрицание;
2. Конъюнкция;
3. Дизъюнкция;
4. Импликация;
5. Эквивалентность.
Для изменения указанного порядка выполнения логических

ДРУГИЕ СВЯЗКИ

Штрих Шеффера

Стрелка Пирса

СУММА ПО МОДУЛЮ ДВА

Логические отношения

Лекция 4

Таблица истинности для конверсии импликации

Таблица истинности для контрапозиции

Таблица истинности для конверсии контрапозиции

Основные законы, определяющие свойства логических операций

Основные законы, определяющие свойства логических операций.

Основные законы, определяющие свойства логических операций

Основные законы, определяющие свойства логических операций

Основные законы, определяющие свойства логических операций

Булевы функции. Свойства элементарных булевых функций

Лекция 5

Булевы функции

Равенство булевых функций

ЭЛЕМЕНТАРНЫЕ БУЛЕВЫ ФУНКЦИИ

ТАБЛИЦА ИСТИННОСТИ БУЛЕВОЙ ФУНКЦИИ ДВУХ ПЕРЕМЕННЫХ

ТАБЛИЦА ИСТИННОСТИ БУЛЕВОЙ ФУНКЦИИ ОДНОЙ ПЕРЕМЕННОЙ

Булевы функции одной переменной

Булевы функции двух переменных

Булевы функции двух переменных

Булевы функции двух переменных

Свойства элементарных булевых функций

1. Функции: конъюнкция, дизъюнкция, сумма по модулю два,

Свойства элементарных булевых функций

Свойства элементарных булевых функций

Свойства элементарных булевых функций

Cвойства элементарных булевых функций

Конъюктивная нормальная форма

Дизъюнктивная нормальная форма

Алгоритм построения КНФ и ДНФ

Алгоритм построения КНФ И ДНФ

3) Избавиться от знаков двойного отрицания.
4) Применить

Совершенная конъюктивная нормальная форма

Совершенной конъюктивной нормальной формой (СКНф) называется такая её

Совершенная конъюктивная нормальная форма

Совершенная дизъюнктивная нормальная форма

Совершенной дизъюнктивной нормальной формой (СДНФ) называется её ДНФ,

Совершенная дизъюнктивная нормальная форма

Основные понятия теории графов. Степень вершины, маршруты, цепи, циклы.

Лекция 6

ПОНЯТИЕ ГРАФА

Графом называют совокупность объектов со связями между ними или граф

СМЕЖНЫЕ

Вершины соединены ребром

Ребра имеют общую вершину

Вершины 1 и 2 – смежные
Вершины

Инцидентность вершины и ребра – вершина является началом или концом ребра
Если

Дуга (ребро )– петля, если вход и выход дуги относятся к

Мультиграф

- это граф, в котором пара вершин соединяется несколькими ребрами

Степень вершины -

Это число ребер, инцидентных вершине.
Если вершине инцидентна петля,

Четность вершин: число нечетных вершин любого графа четно

Вершина – четная (нечетная),

Сумма степеней всех вершин графа -четное число, равное удвоенному числу ребер

Степень выхода вершины орграфа – число выходящих из вершины ребер

Степень выхода

Степень входа вершины орграфа – число входящих в вершину ребер

Степень входа

Источник – вершина, степень выхода которой положительна, степень входа равна нулю. Вершина

Изолированная вершина

Изолированная вершина – это вершина, у которой степень входа и

Изолированная вершина

Изолированная вершина – это вершина, у которой степень входа и

Маршрут М- последовательность вершин и ребер, в которой любые два соседних

Длина маршрута- число ребер маршрута (с повторениями)

Замкнутый маршрут или цикл – начальная вершина совпадает с конечной

Расстояние между двумя вершинами -это

Минимальная длина из всех возможных маршрутов между

Цепь – маршрут, в котором каждое ребро встречается только один раз

Ориентированные графы. Изоморфизм графов. Операции над графами.

Лекция 7

Ориентированный граф (орграф)

Ребро графа называется ориентированным, если одну вершину называют началом,

Маршрутом в орграфе называют – путь: 1. Направление каждого ребра совпадает с

Цепь, путь, цикл – простые, если они проходят через любую из

Связность графа

Граф связный, если все его вершины связаны между собой

Мост- ребро в графе, если после его удаления граф становится несвязным

Изоморфные графы

Графы называются изоморфными, если существует взаимно-однозначное соответствие между ними, сохраняющее

Изоморфные графы

Графы называются изоморфными, если существует взаимно-однозначное соответствие между ними, сохраняющее

Плоский (планарный)граф

Граф называется плоским, если существует изоморфный ему граф, в

Хроматическое число - это

Минимальное число цветов для раскрашивания карты графа таким

Связный плоский граф с n вершинами и m ребрами разбивает плоскость

Деревья

Дерево – конечный связный граф без циклов

Лес

Упорядоченное объединение деревьев, представляющее собой несвязный граф.
При этом число связных

Цикломатическое число графа:

-число ребер графа
-число связных компонент графа
-число

Операции над графами: объединение графов

Объединение графов и - это новый граф ,

Операции над графами: пересечение графов

Пересечение графов и - это граф, для которого

Кольцевая сумма графов и это граф

Способы задания графов. Матрицы смежности, инцидентности графов.

Лекция 8

Пустой граф - все вершины имеют нулевые степени

Полный граф – каждые

Дополнение графа –это другой граф , с теми же вершинами, что

МАТРИЦА ИНЦИДЕНТНОСТИ

Матрица инцидентности графа G с конечным числом вершин n и

МАТРИЦА ИНЦИДЕНТНОСТИ

Матрицей инцидентности орграфа называется прямоугольная матрица размерности
- число

СВОЙСТВА МАТРИЦЫ ИНЦИДЕНТНОСТИ: 1. Число строк равно числу вершин 2. Число

ГРАФ МАТРИЦА ИНЦИДЕНТНОСТИ
Задаем нумерацию дуг графа:
(1, 2)
(1,3)
(3,2)
(3,4)
(5,4)
(5,6)
(6,5)

1

2

4

3

5

6

7

МАТРИЦА СМЕЖНОСТИ ГРАФА

Матрица смежности графа G с конечным числом вершин n

Граф Матрица смежности

Граф

Матрица смежности