5. Аналитическое построение сокращенной днф

Сокращенная ДНФ обладает тем свойством, что записывается единственным образом для каждой булевой функции. Кроме того, любая ТДНФ, а следовательно и любая МДНФ, получается из сокращенной ДНФ (СокрДНФ) путем удаления из нее некоторых элементарных конъюнкций.

Для построения СокрДНФ обычно используется задание функции в виде СДНФ или произвольной ДНФ. Наиболее универсальным методом перехода к СокрДНФ является выполнение над исходной ДНФ преобразований вида:

а) A  AB = A – поглощение, где A и B – элементарные конъюнкции;

б) x A B = x A B  AB – склеивание;

или x A A = A – полное склеивание;

или x A A = x A A  A – неполное склеивание.

При этом вначале следует выполнить всевозможные попарные склеивания входящих в ДНФ элементарных конъюнкций, а затем поглощения. Далее, если это возможно, преобразования применяют повторно. При этом сложность полученной СокрДНФ может оказаться больше сложности исходной ДНФ.

Пример:

Пусть функция трех переменных f(x, y, z) задана в виде СДНФ:

f(x, y, z) =

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

Тогда f(x, y, z) =

 x y = 

Теперь выполняя всевозможные поглощения, получим:

f(x, y, z) = .

Последняя формула является СокрДНФ.

Теперь рассмотрим функцию трех переменных f(x, y, z), заданную формулой вида ДНФ: f(x, y, z) =

При склеивании первой и второй конъюнкции получим 0, склеивание всех остальных пар добавит к исходной ДНФ дополнительные конъюнкции и тогда: f(x, y, z) = _.

Выполняя поглощение, получим: f(x, y, z) =

Теперь, применяя ещё раз склеивание и поглощение, переходим к следующей формуле:

f(x, y, z) = x . И, поскольку преобразования больше невозможны, последняя формула является СокрДНФ.

6. Локальные алгоритмы

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

Применение локальных алгоритмов к задаче минимизации булевых функций основано на понятии окрестности k–го порядка максимального интервала или соответствующей ему простой импликанты.

Под окрестностью нулевого порядка для некоторого максимального интервала N_Кi (или для элементарной конъюнкции К_i) функции f(x₁, x₂, … , x_n) понимают сам этот интервал (или саму эту конъюнкцию). Записывают этот факт так S₀(N_Кi)={N_Кi}.

Окрестность 1-го порядка интервала N_Кi представляет множество всех максимальных интервалов, имеющих непустое пересечение с S₀(N_Кi), т.е. S₁(N_Кi)={S₀(N_Кi),N_Кj,…,N_Кm}, где N_Кj∩ S₀(N_Кi),…,N_Кm∩ S₀(N_Кi). В терминах конъюнкций окрестность 1–го порядка простой импликанты К_i представляет собой множество тех простых импликант функции f(x₁, x₂, … , x_n), которые имеют общий множитель с конъюнкцией К_i, или являются близкими к ней.

Окрестность 2-го порядка для N_Кi – это множество интервалов, пересекающихся с окрестностью 1-го порядка хотя бы в одной вершине. А в терминах конъюнкций – это множество близких к К_i конъюнкций, а также конъюнкций, близких к последним. Аналогично можно определить окрестность порядка k для интервала N_Кi – это множество всех максимальных интервалов функции f, имеющих непустое пересечение с окрестностью порядка (k–1) для N_Кi.

В локальных алгоритмах могут рассматриваться окрестности 1–го (алгоритм Куайна), 2–го (алгоритм регулярных точек) и k –го порядков (кольцевой алгоритм). Накопление информации об окрестностях простых импликант позволяет в дальнейшем проанализировать возможность удаления импликанты из СокрДНФ для получения минимальной ДНФ.

Рассмотрим построение окрестностей максимальных интервалов и простых импликант на примере.

Пусть функция трех переменных задана сокращенной ДНФ: . Это задание равносильно заданию функции сокращенным покрытием N_f: {(1,1,0),(1,1,1)}{(1,0,0),(1,1,0)}{(0,0,0),(1,0,0)}. Введем обозначения: К₁=ху, К₂=, К₃= и N_К1= {(1,1,0),(1,1,1)}, N_К2={(1,0,0),(1,1,0)}, N_К3={(0,0,0),(1,0,0)}. Тогда окрестности нулевого порядка для каждой простой импликанты и каждого максимального интервала совпадают с ними самими. Окрестность 1–го порядка импликанты К₁ есть множество {К₁, К₂}, а максимального интервала N_К1 – соответственно S₁(N_К1)= {N_К1, N_К2}.

S₁(К₂)= {К₂, К₁, К₃}, S₁(N_К2)= {N_К2, N_К1, N_К3};

S₁(К₃)= {К₃, К₂}, S₁(N_К2)= {N_К3, N_К2};

S₂(К₁)= {К₁, К₂, К₃}, S₂(N_К1)= {N_К1, N_К2, N_К3};

S₂(К₂)= {К₂, К₁, К₃}= S₁(К₂), S₂(N_К2)= {N_К2, N_К1, N_К3}= S₁(N_К2);

S₂(К₃)= {К₃, К₂, К₁}, S₂(N_К3)= {N_К3, N_К2, N_К1};

S₃(К₁)= {К₁, К₂, К₃}= S₂(К₁), S₃(N_К1)= {N_К1, N_К2, N_К3}= S₂(N_К1);

S₃(К₃)= {К₃, К₂, К₁}= S₂(К₃), S₃(N_К3)= {N_К3, N_К2, N_К1}= S₂(N_К3). И далее все окрестности более высоких порядков совпадают с уже найденными.