Идея метода Квайна (алгоритм)
Метод Квайна – Мак-Клоски для нахождения минимальной ДНФ
Этот метод удобен для нахождения минимальной ДНФ функции от любого числа переменных.
Определение. Элементарная конъюнкция K1 покрывает ЭК K2, если каждая переменная, входящая в K1, входит и в K2.
__ __ __
X1X3 – покрытие X1X2X3X4
Nk1 Nk2
K2 = K1K
K – конъюнкция из других переменных.
__ _ _ __ _ _
X1X3 V X1X2X3X4 = X1X3 (1 V X2X4) = X1X3 – поглощение
Склеивание двух ЭК
_
Kx V Kx = K
Идея метода Квайна (алгоритм)
1. Выписываются все элементарные конъюнкции из СДНФ функции.
2. Проводятся все возможные склеивания между этими ЭК. Полученные новые ЭК сохраняются вместе со старыми.
3. Между ними снова проводим все возможные склеивания до тех пор, пока это возможно. В результате среди ЭК появятся все простые импликанты функции.
4. Проводим поглощение между всеми получившимися ЭК, то есть оставляем только те ЭК, которые не покрываются никакими другими.
5. В результате получаются только простые импликанты. Их дизъюнкция является сокращенной ДНФ. Дальше все идет в соответствии с тривиальным алгоритмом минимизации.
| 10 11-12-13
10.Принцип двойственности
F*(x1…xn) – двойственная функция,
_ _ _
F*(x1…xn) = F(x1…xn)
Например
____
_ _
(XY)* = XY = X V Y
Чтобы получить вектор двойственности функции при ее табличном задании, переворачиваем таблицу на 180 градусов и берем отрицание от получившейся функции.
Теорема. Принцип двойственности.
Если F (x1…xn) является суперпозицией функций fi (i = 1...k), то двойственная к ней функция является такой же по структуре суперпозицией, но от двойственных функций.
Доказательство следует из определения двойственной функции.
_ _ _ _ _ __
F*(x1..xn) = F(x1…xn) = f(f1…fk) = f*(f1…fk)
Следствие
f(x1..xn) = K1 V K2 V… V Kn – СДНФ
f*(x1..xn) = D1 D2 … Dn - СКНФ
Используя принцип двойственности, можно доказать следующую теорему.
Любая булева функция, тождественно не равная единице представима и притом единственным образом в виде СКНФ.
Доказательство получается из самого принципа двойственности и его следствий.
Задача минимизации ДНФ.
Определения:
1. Рангом правильной ЭК называется число разных переменных, входящих в нее.
2. Рангом ДНФ называется сумма рангов всех ЭК, входящих в ДНФ.
3. Минимальной ДНФ или Dmin для данной функции называется ДНФ, которая равна этой функции и имеет наименьший ранг.
Задача минимизации ДНФ для данной функции состоит в нахождении минимальной ДНФ.
Число ДНФ при фиксированном n – конечное (n - число переменных
Тривиальный алгоритм минимизации ДНФ состоит в следующем:
1. Выписываем все возможные ДНФ от данного числа n в порядке возрастания их рангов.
2. Последовательно сравниваем нашу функцию с каждой из этих ДНФ. Первая ДНФ, которой равна наша функция имеет минимальный ранг.
Алгоритм представления функции в виде СДНФ.
1. Выписываем носитель функции.
2. Для каждого вектора из носителя выписываем конъюнкцию соответствующих переменных. (если координата равна нулю, переменную пишем с отрицанием, если единице – без отрицания). Это и будут все полные ЭК.
3. Выписываем дизъюнкцию всех этих ЭК.
Алгоритм представления функции в виде СКНФ.
1. Выписываем носитель функции
2. Для каждого вектора из носителя выписываем дизъюнкцию соответствующих переменных. (если координата равна нулю, переменную пишем без отрицания,. если единице – с отрицанием). Это и будут все полные ЭД.
3. Выписываем конъюнкцию всех этих ЭД.
| 14-15-16 17-18-19
14. Леммы о несамодвойственной, о монотонной и о нелинейной функциях.
Если f(x1,x2,..., xn} не принадлежит самодв, то из неё путем подстановки функций x и отрицание x можно получить несамодвойственную функцию одного переменного, т.е. конст.
Если f(x1,x2,..., xn} не принадлежит монотон, то из неё путем подстановки констант 1 и 0 можно получить функцию отрицание x
Если f(x1,x2,..., xn} не принадлежит линейным, то из неё путем подстановки констант 1 и 0 и функций вида x и отрицание x, а так же может быть, путем навешивания отрицания над f, можно получить функцию x1* x2,
15. Теорема Поста о функциональной полноте.
Теорема Поста о полноте) Система булевых функций F является полной тогда и только тогда, когда она не содержится ни в одном из классов To,T1,M,S и L, т.е. когда в ней имеется хотя бы одна функция, не сохраняющая 0, хотя бы одна функция, не сохраняющая 1, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.
16 Понятие графа. Маршруты, циклы, связность. Определение дерева, его свойства.
Граф — это совокупность объектов со связями между ними.
Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах.
Маршрут в графе — это чередующаяся последовательность вершин и рёбер v0,e1,v1,e2,v2,...,ek,vk, в которой любые два соседних элемента инцидентны. Если v0 = vk, то маршрут замкнут, иначе открыт.
Инцидентность — понятие, используемое только в отношении ребра и вершины: если v1,v2 — вершины, а e = (v1,v2) — соединяющее их ребро, тогда вершина v1 и ребро e инцидентны, вершина v2 и ребро e тоже инцидентны. Две вершины (или два ребра) инцидентными быть не могут. Для обозначения ближайших вершин (рёбер) используется понятие смежности.
Циклом называют путь, в котором первая и последняя вершины совпадают. При этом длиной пути (или цикла) называют число составляющих его рёбер.
Связность. Две вершины в графе связаны, если существует соединяющая их (простая) цепь.
Дерево — связный граф, не содержащий циклов.
1. Дерево не имеет кратных рёбер и петель.
2. Любое дерево с n вершинами содержит n − 1 ребро. Более того, конечный связный граф является деревом тогда и только тогда, когда B − P = 1, где B — число вершин, P — число рёбер графа.
3. Граф является деревом тогда и только тогда, когда любые две различные его вершины можно соединить единственным элементарным путём.
4. Любое дерево однозначно определяется расстояниями (длиной наименьшей цепи) между его концевыми (степени 1) вершинами.
Любое дерево является двудольным графом. Любое дерево, содержащее счётное количество вершин, является планарным графом.
|