Составители:
Рубрика:
16
путем (x
1
, x
3
, x
5
). Итак , кратчайший путь из x
1
в x
6
таков (x
1
, x
3
, x
5
, x
4
,
x
6
). Построим далее остовное дерево кратчайших путей. Соответствующий
этому дереву граф представлен на рис.4.
Рис.4
Заметим, что сравнение рисунков 3 и 4 подтверждает известную теорему
о графах: наименьшее число ребер р , которое нужно удалить из связного
графа,чтобы получить дерево, удовлетворяет соотношению
р = N - n + 1,
где N - число ребер исходного графа,
n - число вершин графа.
В нашем случае р = 11 - 8 + 1 = 4, т.е. количество удаляемых ребер графа
для получения дерева не может быть меньше четырех. Непосредственный
подсчет показывает, что в рассматриваемой задаче оно равно шести.
Глава 2. Элементы алгебры логики
§ 2.1. Понятие высказывания. Двоичные переменные
Математическая логика
- это наука, изучающая правила построения
математических доказательств. Одним из разделов математической логики
является алгебра логики
, которая имеет дело с высказываниями.
Под высказыванием мы будем понимать всякое предложение, которое
может быть истинным
или ложным. Алгебра логики по определенным
правилам записывает высказывания в виде формул, которые аналогичны
формулам обычной арифметики. Применяя формальные преобразования к
логическим формулам, в алгебре логики из исходных посылок получают их
логические следствия, т.е. новые знания об изучаемом явлении. Высказывания
принято обозначать буквами латинского алфавита: A, B, C, a, b и т.д.
Приведем примеры некоторых высказываний:
А: - ”8 - четное число”;
B: - “снег - зеленый”;
С: - “всякий прямоугольник есть параллелограмм”;
a: - “всякий ромб есть квадрат”.
В этих примерах высказывания А, С - истинные высказывания, B, a -
ложные.
Страницы
- « первая
- ‹ предыдущая
- …
- 14
- 15
- 16
- 17
- 18
- …
- следующая ›
- последняя »
