Нормальные формы

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

Иногда будем допускать в элементарной конъюнкции наличие повторов элементов.

Определение. Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция попарно различных элементарных конъюнкций.

Иногда будем допускать в ДНФ наличие повторов элементов.

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

Иногда будем допускать в элементарной дизъюнкции наличие повторов элементов.

Определение. Конъюнктивной нормальной формой (КНФ) называется конъюнкция попарно различных элементарных дизъюнкций. Иногда будем допускать в КНФ наличие повторов элементов.

Приложение 1. Построение матрицы достижимости.

Видно что Н4 и Н5 совпадаю. Формируем матрицу достижимости Q

Приложение 2. Расчет плотности графа.

Алгоритм нахождения плотности графа:

В качестве примера рассмотрим граф, изображенный на рис. П1.

1. Сопоставляем корню дерева заданный граф.

2. Фиксируем в графе вершину с максимальной степенью, сопоставив её концу исходящей из корня дуги.

Степень вершины v6 максимальна.

3. Строим множество исходящих из корня дуг. Их число – мощность носителя неокрестности вершины с максимальной степенью.

4. Считаем концы построенного яруса корнями новых деревьев. Устанавливаем, помечена ли вершина V символом пустое множество. Если нет, строим следующий ярус. Если да – конец алгоритма.

5. Пути между концами дуг, исходящих из корня синтезированного дерева, и висячими вершинами определяют полные подграфы заданного графа.

Рассмотрим применение этого алгоритма для приведенного графа.

а) б)

Рис. П1. Исходный граф (а) и построенное дерево (б). Получившиеся подграфы {5,6,7}, {5,6,4}, {5,8,9}

Построим ещё одно дерево для вершины v6, чтобы проверить, все ли полныеподграфы мы нашли. Все действия аналогичны. Рис. П2.

Рис. П2. Получили ещё два полных подграфа {7,6,5} и {5,8,9}, который уже был получен..

Таким образом, получили 4 полных подграфа с наибольшей степенью 3. Следовательно плотность графа равна трем.

Литература

1. Пономарев В.Ф. Дискретная математика для информатиков-экономистов. Учебное пособие. – Калининград: КГТУ и КИМБ, 2002, 239с.

2. Непейвода Н. Н. Прикладная логика: Учеб. Пособие.- 2-е изд., испр. и доп.- Новосибирск, изд-во Новосиб. Ун-та, 2000.-521с.

3. Горбатов В.А. Фундаментальные основы дискретной математики. М, Наука, ФМ, 200, 540 стр.