18. Граф. Основные определения в тг (цели, циклы, дуги).

Граф — основной объект изучения математической теории графов, совокупность непустого множества вершин и наборов пар вершин (связей между вершинами).

Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра[1]. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах.

Многие структуры, представляющие практический интерес в математике и информатике, могут быть представлены графами. Например, строение Википедии можно смоделировать при помощи ориентированного графа, в котором вершины — это статьи, а дуги (ориентированные рёбра) — гиперссылки (тематическая карта).

Граф, или неориентированный граф   — это упорядоченная пара  , где   — это непустое множество вершин или узлов, а   — множество пар (в случае неориентированного графа — неупорядоченных) вершин, называемых рёбрами.

Ориентированный граф (сокращённо орграф)   — это упорядоченная пара  , где   — непустое множество вершин или узлов, и   — множество (упорядоченных) пар различных вершин, называемых дугами или ориентированными рёбрами.

Дуга — это упорядоченная пара вершин  , где вершину   называют началом, а   — концом дуги. Можно сказать, что дуга  ведёт от вершины   к вершине  .

Прочие связанные определения

Маршрутом в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершиной ребром. Цепью называется маршрут без повторяющихся рёбер. Простой цепью называется маршрут без повторяющихся вершин (откуда следует, что в простой цепи нет повторяющихся рёбер).

Ориентированным маршрутом (или путём) в орграфе называют конечную последовательность вершин и дуг, в которой каждый элемент инцидентен предыдущему и последующему.

Циклом называют цепь, в которой первая и последняя вершины совпадают. При этом длиной пути (или цикла) называют число составляющих его рёбер. Заметим, что если вершины   и   являются концами некоторого ребра, то согласно данному определению, последовательность   является циклом. Чтобы избежать таких «вырожденных» случаев, вводят следующие понятия.

Путь (или цикл) называют простым, если ребра в нём не повторяются; элементарным, если он простой и вершины в нём не повторяются.

19. Логические функции: Основные задачи. Применение. Суть функции. Обозначение. Таблица истинности. Логический смысл.

 Логическая функция — это функция логических переменных, которая может принимать только два значения: 0 или 1. В свою очередь, сама логическая переменная (аргумент логической функции) тоже может принимать только два значения: 0 или 1.

Основные задачи:

- Нахождение иднф (Идеальная дизъюнктивная нормальная форма); - икнф (ид Конъюнктивная нормальная форма); - ианф или полином Жегалкина (ид Алгебраическая нормальная форма);

- минимизация функции: аналитический метод, метод карт Карно, метод Квайна..

Применение:

Логическая функция выполняет логическую операцию или сравнение объектов и выражений, результатом вычисления логической функции будет логическое значение. В многомерных выражениях логические функции крайне важны для определения положения элементов. Они применяются в математической логике и компьютерах и компьютерных науках.

Логічних функцій однієї змінної усього чотири. Вони наведені в таблиці 2.

Таблиця 2

Логічні функції однієї змінної

X	0	1	2	3
0	0	0	1	1
1	0	1	0	1

Функції ₀ і ₃ - константи 0 і 1 відповідно; _{1 – X ;} _{2 – НЕ} X.

Логічних функцій двох змінних - 16. Вони наведені в таблиці 3.

Таблиця 3

Логічні функції двох змінних

х1 x2	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0 0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0 1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1 0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1 1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

Функції ₀ і ₁₅ константи 0 і 1, тобто функції з двома неістотними змінними. Відзначимо, що ці функції відрізняються від наведених у таблиці 3.2. Там вони унарні, а тут бінарні операції на В.

Определим ОСНОВНЫЕ логические функции:

15	0
1	0
1	0
1	0
1	0

Константы – 1 и 0 соответственно.

Инверсия (отрицание) — это логическое не. Говорят, что имея суждение А, можно образовать новое суждение, которое читается как «не А» или «неверно, что А». Для обозначения отрицания суждения употребляется символ ¬ или – над переменной. Запись ¬А читается как «не А». 

А	¬A
0	1
1	1

коньюкция - это логическое умножение. Обозначение: А & В ( АВ, А ∧ В ) . Читается так “ А и В “. 

1

0

0

0

1

Дизьюкция - это логическое сложение. Обозначение: А ∨ В , ( А + В ). Читается так: “ А или В ”. 

7

0

1

1

1

Эквиваленция - это функция тождества. Она обозначается символами = , ~ , или <=>. Выбираем обозначение  А = В. («тогда и только тогда»). Запись А = В читается как «А эквивалентно В». 

9

1

0

0

1

Импликация - это логическое следование. Импликация двух высказываний А и В соответствует союзу«ЕСЛИ…ТО». Она обозначается символом →. Читается как «из А следует В». Обозначение: A→B. 

Импликация записывается как посылка   следствие; 

Импликация как булева функция ложна лишь тогда, когда посылка истинна, а следствие ложно. 

11

1

1

0

1

Стре́лка Пи́рса — бинарная логическая операция, булева функция над двумя переменными. Введена в рассмотрение Чарльзом Пирсом (Сharles Peirce) в 1880—1881 г.г.

Стрелка Пирса, обычно обозначаемая ↓, эквивалентна операции НЕ-ИЛИ и задаётся следующей таблицей истинности:

8

1

0

0

0

Не А, Не B. Пример: здание не высокое, не низкое. Когда оба выражения ложны – функция даст истинный результат.

Штрих Ше́ффера — бинарная логическая операция, булева функция над двумя переменными. Введена в рассмотрение Генри Шеффером в 1913 г.

Штрих Шеффера, обычно обозначают, как стрелочка вверх и эквивалентен операции НЕ-И.

Например,  А / В  означает: " А и В несовместны" или "Неверно, что А и В". Ещё пример, высказывания "2 х 2 = 4"  и  "2 х 2 = 5" несовместны.

Высказывание со штрихом Шеффера   истинно тогда и только тогда, когда либо А ложно, либо В ложно , либо А и В ложны одновременно. Оно ложно и в ом случае, если истинны и А и В одновременно. Действительно, если вместо А подставить высказывание "2 х 2 = 4" и вместо В подставить высказывание "2 х 2 = 4", то  А / В дадут ложное высказывание, так как так про идентичные высказывания нельзя сказать, что они несовместны. Таблица истинности со штрихом Шеффера выглядит следующим образом 

14

1

1

1

0

Сложе́ние по мо́дулю 2 (логи́ческое сложе́ние, исключа́ющее «ИЛИ», строгая дизъюнкция,XOR, поразрядное дополнение, побитовый комплемент, жегалкинское сложение) — булева функция, а также логическая и битовая операция. В случае 2 переменных результат выполнения операции является истинным тогда и только тогда, когда лишь один из аргументов является истинным. 

6

0

1

1

0