Нахождение минимальной ДНФ

1. Строим сокращенную ДНФ.

2. Последовательно удаляем лишние конъюнкты из сокращенной ДНФ, находим все тупиковые ДНФ.

3. Находим минимальную ДНФ, выбирая тупиковую ДНФ с наименьшим весом.

?4. Монотонные функции. Теорема о сокращенной ДНФ для монотонных функций. Композиция монотонных функций есть снова монотонная функция.

Набор (x1, x2,..., xn) ∈ B^n меньше или равен набору (y1, y2,..., yn) ∈ B^n,

(x1, x2,..., xn) ≤ (y1, y2,..., yn), если x1 ≤ y1, x2 ≤ y2,..., xn ≤ yn.

Функция f: B^n → B называется монотонной, если

(x1,..., xn) ≤ (y1,..., yn) ⇒ f(x1,..., xn) ≤ f(y1,..., yn)

для всех (x1, x2,..., xn),(y1, y2,..., yn) ∈ B^n.

0, 1, x, y, x ∨ y, x & y — монотонные функции.

Теорема. Простые импликанты монотонных функций не содержат отрицаний.

Доказательство. Пусть — простой импликант монотонной функции f(x1, x2,..., xn) при k ≤ n. Тогда

Значит Таким образом Значит, импликант f, а это противоречит

тому, что — простой импликант.

Теорема. Сокращенная ДНФ монотонной функции является тупиковой (и, следовательно, минимальной).

Доказательство. Пусть K = x1 &... & xk — простой импликант f(x1, x2,..., xn), k≤n, f=K∨f’, где f’—

дизъюнкция всех простых импликантов f, кроме K.

Докажем, что f!= f’. Заметим, что каждый импликант K’!= K должен содержать литерал xi,i > k, так как K — простой. Поэтому, при .

Имеем Значит, f!= f’.

5. Многочлен Жегалкина. Представимость булевых функций многочленами Жегалкина.

Определение. Многочленом Жегалкина называется сумма нескольких элементарных конъюнктов без отрицаний.

Примеры. 0, 1, xy, 1 + x, x + y, x + y + xy, 1 + x + xy + xyz,

Теорема. Любая булева функция f: B^n → B представляется в виде многочлена Жегалкина, причем единственным образом

Доказательство существования. Представим f в СДНФ

Заметим, что при имеем

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

Тогда , где суммирование проводится по всем конъюнктам K без отрицаний от переменных x1, x2,... xk.

Доказательство единственности. Пусть и f1, f2,..., fN— все булевы функции от n аргументов. Пусть Gi —количество различных многочленов Жегалкина функции fi,

В силe доказанного Gi ≥ 1, Тогда для количества G всех многочленов Жегалкина от n аргументов имеем

поскольку всего существует только 2^n конъюнктов без отрицаний, каждый из которых может входить или не входить в многочлен. Поэтому, Gi = 1 для каждого , то есть каждая fi имеет только один многочлен Жегалкина

6. Замкнутые классы булевых функций. Классы T_0 и T_1. Классы монотонных, линейных и самодвойственных функций.

Пусть M - некоторое множество булевых функций. Множество [M], состоящее из всех функций, представимых формулами над M, называется замыканием M.

Определение. Класс функций C ⊆ F называется замкнутым, если [C] = C, то есть каждая формула над C принадлежит C.