Математическая логика

Конъюнктивная и дизъюнктивная нормальные формы (КНФ и ДНФ)

Дизъюнктивной нормальной формой  называется формула, имеющая вид дизъюнкции элементарных конъюнкций.

Конъюнктивной нормальной формой (КНФ) называется формула, имеющая вид конъюнкции элементарных дизъюнкций./2/

f(e1,e2,…,en)= x1e1x2e2…xnen   (2)

Для приведения функции от двух переменных f(x,y) к ДНФ следует воспользоваться формулой 2 и таблицей 1.

Каждая булева функция f(x1,x2,…,xn), которая не идентична нулю, может быть записана в виде всевозможных булевых выражений типа

f(x,y)=( (3)

Каждую булеву функцию f(x1,x2,…,xn), которая не равна тождественно единице, можно представить в виде произведения всевозможных булевых выражений вида:

f(`e1,`e2,…,`e3) = x1e1 Ú x2e2 Ú … Ú xnen (4)

Для приведения функции от двух переменных f(x,y) к КНФ следует воспользоваться теоремой 2 и таблицей 1.Следовательно ДНФ=x&y.

Построение полинома Жегалкина.

Полином Жегалкина определяется по формуле:

,  где ki ( ) попарно различные монотонные элементарные конъюнкции./2/

Для функции , которая зависит от трех переменных, полином Жегалкина будет следующий:

P(x, y) = B0ÅB1xÅB2yÅB3xy  (3)

Метод неопределенных коэффициентов заключается в том, что последовательной подстановкой x, y и соответственно значений функций при них в данный полином, находим коэффициенты β0,  β1,  β2, β3, β4,  β5,  β6, β7. Значения переменных x, y и значение функции представлены в таблице 4:

Таблица 2 – значение функции

x	Y	f (x, y)
0	0	0
0	1	0
1	0	0
1	1	1

На основании таблицы 2 составляем систему уравнений и находим последовательно коэффициенты:

 

f(00)=B0=0

f(01)=B0ÅB2=0; B2=0

f(10)=B0ÅB1=0; B1=0

f(11)=B0ÅB1ÅB2ÅB3=1; B3=1

следовательно, получили полином Жегалкина:

P(x,y)=x*y (5)

Нахождение   производной  от двух переменных. Находим две производных.

  и  ;

(5)

(6)

Используя формулу 6 можно построить таблицу истинности (таблица 6) для функции (6), а также таблицу (таблица7) значений производной (5)

Таблица 3 – Таблица истинности для функции  (6)

x	y
0	0	1	1	1	1	0	1	0	0
0	1	1	0	0	0	1	1	0	0
1	0	0	1	0	0	1	1	0	0
1	1	0	0	0	1	1	0	1	1

Таблица 4 – Значение производной  (5)

f(x,y)	f(	f(x,y)
0	0	0
0	1	1
0	0	0
1	0	1

 

Найдем производную по x,y

- (6)

- (7)

Для нахождения дифференциала функции (1) сначала построим таблицу истинности для функции (7) (таблица 8) и окончательным результатом будет таблица 9 для функции 6.

Таблица 5 - Таблица Истинности для функции (7)

x	y	x&y
0	0	0	1	1	0	1	1
0	1	0	1	0	1	0	0
1	0	0	0	0	1	0	0
1	1	1	0	1	1	0	0

Таблица 6 – Значение производной 

f(x,y)	f(	f(x,y)Å f(
0	1	1
0	0	0
0	0	0
1	0	1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2 Графы

2.1 Алгоритм Дейкстра

Рассмотрим экономическую задачу: одна крупная компания решила поощрить своих работников и устроить всем работникам отдых в городе С. Для того чтобы приехать в город С необходимо проехать несколько промежуточных городов. Перед экспертами компании была поставлена задача найти оптимальный путь. Они определили расстояния между городами и построили неориентированный граф.

Если задачу перевести на язык математики, то получится, имеется n вершин и число ребер не меньше n-1. Если две вершины соединены, то они соединены только одним ребром.

 

 

 

 

 

 

 

Рисунок 2 – Исходный граф

Вершине A присваиваем постоянный ярлык 0. Далее приписываем вершинам  смежные к A (B и I) временные ярлыки.  Bременный ярлык вершины B равен 5; временный ярлык вершины I равен 4.  Выбираем наименьший – это  будет I, и делаем его постоянным. На рисунке он выделяется жирным шрифтом. 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок 3 – Нахождения первого присоединенного ребра

L(w)=4 далее назначаем временные  ярлыки H и F и они соответственно будут равны 11 и 10, выбираем минимальный – это будет F, выделяем его и делаем его постоянным и так далее, пока не дойдем до G .

 

 

 

 

 

 

          

 

Рисунок 4-Резулитирующий граф

В результате  получается, что кратчайший путь будет равен 13 и будет пролегать через A, I, F, G.

2.2 Жадный алгоритм

Было найдено новое месторождение нефти. Для разработки и соединения месторождения с нефтеперерабатывающими заводами был составлен примерный маршрут. Перед экономистами была поставлена задача определить максимальную загруженность линий. Если всю задачу перевести на графы, то получим, что имеется неориентированный помеченный граф.

Решить – эту задачу можно с помощью Жадного алгоритма. 

Решением задачи будет следующий алгоритм. /6/

a. находится ребро с максимальным  весом, из него составляется подграф. Ясно, что таковым является ребро с весом равным 14, соединяющее  вершины D и E.                                              

б.  дальнейшим шагом находится следующее ребро с максимальным  весом.  Это ребро, соединяющее E и F (с весом 13)

в.   присоединяется ребро, связывающее E и C (с весом 12)        

г.   присоединяется ребро,  связывающее E  и G  (с весом 11) 

д.   присоединяется ребро,  связывающее I  и H  (с весом 8)   

е.   присоединяется ребро,  связывающее I и F (с весом 8)  

ж.   присоединяется ребро,  связывающее A и B (с весом 6)      

 В результате получаем граф, изображенный на рисунке 5, который  и будет примером применения  жадного алгоритма.

 

 

 

 

 

 

Рисунок 5 – Максимальное дерево покрытия

   Следовательно, получили результирующее максимальное дерево покрытия, вес которого равен сумме весов ребер, включенных в него:

Вес = 10+7+8+6+6+7=44

2.3 Построение минимального  остова

В одном большом городе имеется один большой супермаркет (F)   и существует множество дорог к нему. Известны затраты на проезд . Требуется найти путь с минимальными затратами.

Для решение этой задачи можно применить алгоритм минимального остова./6/

Алгоритм построения минимального остова: на первом этапе   строим подграф, состоящий из двух вершин и ребра, их соединяющего,  причем ребро должно быть минимального веса. Далее на каждом последующем этапе присоединяется ребро, обладающее минимальным весом среди рёбер, соединяющих уже построенный фрагмент минимального остова с вершинами, ещё не включенными во фрагмент.

Десять городов поставим в соответствие десяти вершинам графа   a, b, c, d, e, f, g, h, i, j,. Цель обозначим F,   а начало пути обозначим  A.

Решением задачи будет следующая последовательность этапов:

1 этап (H-J), 2 этап: (I-g) ,  3 этап: (h-i),   4 этап:  (I-f),   5 этап: (g-d),   6 этап: (d-b),   7 этап:(b-a), 8 этап: (b-e). Выполнение алгоритма завешено, так как добавление ребер без образования петель невозможно. Осталось  сложить веса ребер, составляющих подграф графа G, который образует минимальный остов. Эта сумма будет следующая: 2+7+4+6+5+7+6+6+4=47.   В результате получаем, что существует один путь к F – это AIF  и он равен = 10. Построив граф (рисунок 6), можно увидеть, что существует только единственный путь от начала нашего пути до указанной цели. 

 

                                                                    .  

 

 

 

 

 

 

 

Рисунок 6 –Результирующий граф

 

2.4 Задача Коммивояжера

Предприятия(A) в целях увеличить свою прибыль решила открыть свои филиалы в 10 городах (B,C,D,E,F,G,I,H,J) и, чтобы минимизировать затраты и сэкономить время экономистам была поставлена задача найти минимальный путь и так чтобы все города были пройдены по одному разу.

Так как этот граф является Гальмитонов, то одним из способов решения  будет решение при помощи Коммивояжера./6/

    а) В матрице  определяем  минимальный  элемент строки и  вычитаем его из элементов соответствующей строки. Таким образом, получаем нулевой элемент в каждой строке. Далее определяем минимальный элемент столбца (не включая и нули)  и вычитаем его из элементов соответствующего столбца (рисунок 2).