Дискретная математика (Конспекты 15 лекций)

Страница 4

Замечание. Единственность доказана при фиксированном числе аргументов n. Так как, вводя фиктивные переменные, мы будем менять вид формулы.

Следствие. Любая булева функция представима формулой, в которую входит только конъюнкция, дизъюнкция и отрицание.

Принцип двойственности

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. Выписываем конъюнкцию всех этих ЭД.

Лекция 5

Продолжение темы «ДНФ»

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

Интервал ранга R содержит 2N-R векторов.

N – количество рассматриваемых векторов.

Интервал – носитель элементарной конъюнкции.

Теорема

Носитель дизъюнкции двух функций равен объединению носителей этих функций.

Доказательство.

" a Î Nf V g Þ f(a) V g(a) = 1 Þ f(a) = 1 ИЛИ g(a) = 1 Þ a Î Nf ИЛИ a Î N g

ч.т.д.

Носитель ДНФ является объединением интервалов.

Допустимым интервалом для данной функции называется интервал, который целиком содержится в носителе этой функции.

Nf = I1 V I2 V … V Ik

Интервал для данной функции является максимальным, если он не содержится целиком ни в каком другом допустимом интервале.

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

ЭК, N – максимальный интервал – простая импликанта.

Представление носителя в виде объединения максимальных интервалов будем называть покрытием носителя максимальными интервалами.

Дизъюнкция всех возможных простых импликант называется сокращенной ДНФ функции.

Покрытие носителя интервалами будем называть неприводимым, если ни один нельзя отбросить из правой части равенства, не нарушив это равенство.

ДНФ, которая соответствует неприводимому покрытию, называется тупиковой ДНФ.

Утверждение.

Минимальная ДНФ содержится среди тупиковых ДНФ.

Определение

Максимальный интервал называется ядровым, если он содержит хотя бы одну вершину из носителя функции, которая не принадлежит больше никакому другому максимальному интервалу.

Элементарная конъюнкция, соответствующая ядровому интервалу – ядровая импликанта.

Объединение всех ядровых интервалов – ядро функции.

Дизъюнкция всех ядровых импликант - ядровая ДНФ.

Ядро функции обязательно входит в любое неприводимое покрытие.

Алгоритм получения минимальной ДНФ.

1. Выделяем носитель функции.

2. Выделяем все возможные интервалы.

3. Выписываем все простые импликанты.

4. Выделяем ядровый интервал.

5. Используя ядро функции и комбинацию неядровых интервалов, получаем все неприводимые покрытия, для каждого из которых выписываем тупиковую ДНФ.

6. Среди тупиковых ДНФ выбираем минимальную.