Используя законы логики, приведем данную формулу к виду, содержащему только дизъюнкции элементарных конъюнкций. Полученная формула и будет искомой ДНФ:
Для построения СДНФ составим таблицу истинности для данной формулы:
Помечаем те строки таблицы, в которых формула (последний столбец) принимает значение 1. Для каждой такой строки выпишем формулу, истинную на наборе переменных , , данной строки:
строка 1: ;
строка 3: ;
строка 5: .
Дизъюнкция этих трех формул будет принимать значение 1 только на наборах переменных в строках 1, 3, 5, а следовательно, и будет искомой совершенной дизъюнктивной нормальной формой (СДНФ):
.
Пример 4. Приведите формулу к СКНФ двумя способами:
а) с помощью равносильных преобразований;
б) с помощью таблицы истинности.
Решение:
a)
Преобразуем вторую элементарную дизъюнкцию:
.
Формула имеет вид:
б) составим таблицу истинности для данной формулы:
Помечаем те строки таблицы, в которых формула (последний столбец) принимает значение 0. Для каждой такой строки выпишем формулу, истинную на наборе переменных , , данной строки:
строка 2: ;
строка 6: .
Конъюнкция этих двух формул будет принимать значение 0 только на наборах переменных в строках 2 и 6, а следовательно, и будет искомой совершенной конъюнктивной нормальной формой (СКНФ):
.
Вопросы и задачи для самостоятельного решения
1. С помощью равносильных преобразований приведите к ДНФ формулы:
а) ;
б) ;
в) .
2. С помощью равносильных преобразований приведите к КНФ формулы:
а) ;
б) ;
в) .
3. С помощью второго дистрибутивного закона преобразуйте ДНФ в КНФ:
а) ;
б) .
4. Преобразуйте заданные ДНФ в СДНФ:
а) ;
б) ;
в) .
5. Преобразуйте заданные КНФ в СКНФ:
а) ;
б) ;
в) .
6. Для заданных логических формул постройте СДНФ и СКНФ двумя способами: с помощью равносильных преобразований и с помощью таблицы истинности.
а) ;
б) ;
в) .
3. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
3.1. Основные понятия теории графов
Графы возникли в XVIII столетии, когда известный математик, Леонард Эйлер пытался решить теперь уже классическую задачу о Кёнигсбергских мостах. В то время в городе Кёнигсберге (Калининград) было два острова, соединенных семью мостами с берегами реки Преголь и друг с другом.
Задача состояла в том, что необходимо было совершить прогулку по городу таким образом, чтобы, пройдя ровно по одному разу по каждому мосту, вернуться в то же место, откуда начиналась прогулка.
В 1736 г. Эйлер показал, что сделать это невозможно.
С тех пор поток задач с применением графов нарастал. Однако теория графов как математическая дисциплина сформировалась только в середине 30-х гг. XX в. благодаря работам таких математиков, как Г. Кёниг,
Л.С. Понтрягин, А.А. Зыков и др.
Впервые же понятие «граф» ввел венгерский математик Д. Кёниг в 1936 г.
С графами, сами того не замечая, мы сталкиваемся постоянно. Например, графом является схема движения автобуса. Точками на ней представлены остановки, а линиями – пути движения автобуса. Исследуя свою родословную и возводя ее к далекому предку, мы строим так называемое генеалогическое дерево. И это дерево – граф. Применяются графы для решения задач химии, экономики, электротехники и автоматики, также широко используются в информатике и строительстве. Без графов сложно анализировать классификации в различных науках.
Определение 1.Неориентированным графом (или графом) называется совокупность двух множеств – непустого множества (множества вершин) и множества неупорядоченных пар различных элементов множества ( – множество ребер).
Обычно граф изображают в виде диаграммы, на которой вершины обозначаются точками, а ребра, соединяющие две вершины, – линиями между этими точками.
Например, изображение графа с множеством вершин и множеством ребер может иметь следующий вид (рис. 12).
Изображение графа с множеством вершин и множеством ребер может иметь вид, представленный на рис. 13.
| Рис. 12 | Рис. 13 |
Определение 2. Пусть – вершины, – соединяющее их ребро. Тогда вершина и ребро инцидентны, вершина и ребро также инцидентны, при этом называются концами ребра. Два ребра, инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными.
Определение 3.Ребро, соединяющее вершину саму с собой, называют петлей. Ребра, инцидентные одной и той же паре вершин, называются параллельными, или кратными.
Определение 4.Степенью вершины называется удвоенное количество петель, инцидентных этой вершине, плюс количество остальных инцидентных ей ребер. Обозначение: . Вершина степени 0 называется изолированной, а степени 1 – висячей (концевой). Ребро, инцидентное висячей вершине, называют концевым.
Например,в графе (рис. 14) вершины и – смежные, и инцидентны ребру и являются его концами; – смежные ребра; вершины и не являются смежными, поскольку между ними есть вершина , и – не являются смежными ребрами:
, .
В графе (рис. 15) вершина – изолированная, вершина – висячая; ребро, соединяющее вершину саму с собой, образует петлю:
, , .
| Рис. 14 | Рис. 15 |
Теорема 1.Сумма степеней вершин графа всегда четная.
Теорема 2. Сумма степеней всех вершин графа равна удвоенному числу ребер, т. е. , где – число ребер.
Определение 5. Ребро, имеющее направление от одной вершины к другой, называется направленным (или ориентированным, или дугой) и изображается стрелкой, направленной от вершины, называемой началом, к вершине, именуемой концом. Граф, содержащий направленные ребра, называется ориентированным графом (или орграфом).
Замечание 1. В орграфе у каждой вершины две степени: входящая (число ребер, входящих в вершину) и исходящая (число ребер, выходящих из вершины). Петля несет вклад в обе степени по одному.
| Рис. 16 |
Дуга : 1 – начало дуги, 2 – конец дуги; – петля; ребра , – кратные: , , , , .
Определение 6. Чередующаяся последовательность вершин и ребер в графе (или только ребер), в которой любые два элемента инцидентны, называется маршрутом. Количество ребер , входящих в маршрут, называют длиной маршрута.
Определение 7. Маршрут, все ребра которого различны, называется цепью, а маршрут, для которого различны все вершины, называется простой цепью.
Определение 8. Замкнутая цепь называется циклом, а замкнутая простая цепь – простым циклом.
Определение 9. Цикл, который содержит все ребра графа, называется эйлеровым циклом. Простой цикл, содержащий все вершины графа, называется гамильтоновым.
Например, в графе (рис. 17):
– маршрут, но не цепь (длина – 3);
– цепь, но не простая цепь (длина – 5);
– простая цепь (длина – 4);
– цикл, но не простой цикл (длина – 6);
– простой цикл (длина – 3).
Определение 10.Для орграфов цепь называется путем, а цикл – контуром.
Например, в орграфе (рис. 18):
и – пути;
– контур.
| Рис. 17 | Рис. 18 |
Основные виды графов:
1) мультиграф – граф, содержащий кратные ребра;
2) граф с петлями – граф, содержащий петли (рис. 15);
3) псевдограф – граф, содержащий как петли, так и кратные ребра (рис. 16);
4) простой граф – граф без петель и кратных ребер (рис. 14);
5) полный граф – простой граф, в котором каждая пара вершин соединена ребром (рис. 19);
6) дерево – простой граф, не содержащий циклов;
7) эйлеровый граф – граф, содержащий эйлеровый цикл;
8) гамильтоновый граф – граф, содержащий гамильтоновый цикл.
Рис. 19
Вопросы и задачи для самостоятельного решения
1. Для следующего графа (рис. 20):
а) выпишите смежные вершины и смежные ребра;
б) выпишите вершины с инцидентными ребрами;
в) определите степени каждой вершины графа;
г) укажите, как называются вершины ; ребра V и VI;
д) укажите, как называется такой граф.
2. Для следующих графов определите, чем являются последовательности ребер и вершин.
2.1. Для графа на рис. 21:
а) ; в) ;
б) ; г) .
2.2. Для графа на рис. 22:
а) ; в) ;
б) ; г) .
2.3. Для графа на рис. 23: .
3. Для следующего графа (рис. 24):
а) выпишите степени всех вершин;
б) определите, чем являются последовательности ребер и вершин: 1, 2, 1, 3, 4 и 1, 2, 4.
| Рис. 20 | Рис. 21 |
| Рис. 22 | Рис. 23 | Рис. 24 |
4. Найдите эйлеровый граф (рис. 25).
| а |
| в |
| б |
Рис. 25
3.2. Способы задания графов
В подразд. 3.1 мы уже познакомились с двумя способами описания графов: в виде задания двух множеств вершин и ребери графическим способом.
Рассмотрим другие способы задания графов.
1. Матрица инцидентности.
Пусть дан граф , где – количество вершин, – количество ребер, тогда матрица инцидентности имеет размер .
Для неориентированного графа она имеет вид
Для орграфа
Замечание 1.Если граф без петель, то в матрице смежности по главной диагонали стоят нули.
Пример 1.Составьте матрицы инцидентности для следующих графов (рис. 26, а, б).
| а |
| б |
Рис. 26
Решение:
а) ; б) .
В каждом столбце матрицы инцидентности неориентированного или ориентированного графа только два элемента отличны от нуля (или один, если ребро является петлей). Для матрицы инцидентности ориентированного графа либо столбец содержит один элемент, равный 1, либо один элемент, равный , либо столбец нулевой.
Отношение инцидентности можно еще задать списком ребер графа. Каждая строка этого списка соответствует ребру, в котором записаны номера вершин, инцидентных ему.
2. Матрица смежности.
Пусть дан граф , где – количество вершин, тогда матрица смежности отражает смежность вершин и имеет размер .
Для неориентированного графа она имеет вид
Для орграфа
Для неориентированного мультиграфа значение равно количеству ребер, инцидентных i-й и j-й вершинам, для ориентированного графа этот элемент матрицы смежности равен количеству ребер с началом в i-й вершине и концом в j-й. Таким образом, матрица смежности неориентированного графа симметрична, а ориентированного – не обязательно симметрична.
Пример 2. Найдите матрицы смежности для графов (рис. 27, а, б).
| а |
| б |
Рис. 27