Как найти ядровую днф
Перейти к содержимому

Как найти ядровую днф

  • автор:

Минимизация нормальных форм всюду определённых булевых функций

Элементарная конъюнкция Е называется импликантой булевой функции f, если Е → f ≡ 1.

Импликанта Е называется простой, если при удалении любой буквы из неё она перестаёт быть импликантой булевой функции f.

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

Ядровая импликанта — импликанта, удаление которой из ДНФ некоторой булевой функции f приводит к ДНФ, не равносильной f.

Минимальная ДНФ данной функции f — ДНФ, имеющая наименьшее число символов переменных из всех ДНФ, задающих функцию f.

Тупиковой ДНФ функции f называется такая её ДНФ, состоящая из простых импликант, что удаление из неё любой конъюнкции нарушает равносильность ДНФ данной функции.

Сложностью ДНФ (КНФ) называется количество символов переменных, использованных в записи формулы.

Сокращённая ДНФ может быть получена из СДНФ последовательным применением, пока это возможно, формулы неполного склеивания Кu ∨ К u = Ku ∨ Кu ∨ К, а затем — формулы поглощения Ku ∨ К = К.

Задание 2.5.1

Для данной функции f(x,y,z,w), заданной векторно, проделать следующее:

  1. Записать её СДНФ и СКНФ.
  2. Методом Квайна найти сокращённую ДНФ.
  3. Для сокращённой ДНФ построить матрицу Квайна, указать ядровые импликанты.
  4. С помощью матрицы Квайна найти минимальную ДНФ, указать её сложность.
  5. Найти минимальную ДНФ данной функции с помощью карт Карнау, сравнить полученный результат с ДНФ, найденной в п. 4.
f f f
1 1111 0101 0011 1101 11 0100 1110 1101 1111 21 1011 1111 0001 1111
2 1101 1110 1010 1110 12 1111 1110 0111 1100 22 1110 1100 1111 1001
3 0111 0001 1111 1101 13 1000 1011 1111 1111 23 1001 1011 1111 1010
4 1011 1111 1111 1000 14 1111 1101 1110 0001 24 1111 1110 0111 0011
5 1101 0101 1101 1111 15 1101 0111 1100 1110 25 1010 1111 0111 0011
6 1111 1110 1010 0011 16 1011 1111 1010 1101 26 1110 0110 1111 1100
7 1111 0010 0111 1110 17 1001 1101 1010 1111 27 0111 0111 0101 1011
8 1100 1110 1111 1011 18 1110 0110 1111 1100 28 1101 1111 1110 1010
9 1100 0110 1111 0111 19 0011 1011 1010 1111 29 1111 0011 0111 0111
10 1011 1111 1110 0010 20 1111 0110 1110 1110 30 1110 1110 1010 1101

Пример решения задания 2.5.1

Решим задание 2.5.1 для функции f(x;y,z,w) = (1101 1010 1101 1100).

1. Изобразим таблицу функции f в виде двумерной таблицы — карты Карнау (табл. 2.5.1а).

Найдём СДНФ данной функции:

f(x,y,z,w) = x a ⋅ y b ⋅ z c ⋅ w d =

x 0 y 0 z 0 w 0 ∨ x 0 y 0 z 0 w 1 ∨ x 0 y 0 z 1 w 1 ∨ x 0 y 1 z 0 w 0 ∨ x 0 y 1 z 1 w 0 ∨ x 1 y 0 z 0 w 0 ∨ x 1 y 0 z 0 w 1 ∨ x 1 y 0 z 1 w 1 ∨ x 1 y 1 z 0 w 0 ∨ x 1 y 1 z 0 w 1 ∨ =

= x y z w ∨ x y z w ∨ x y zw ∨ x y z w ∨ x yz w ∨ x y z w ∨ x y z w ∨ x y zw ∨ xy z w ∨ xy z w.

Найдём СКНФ данной функции:

f(x,y,z,w) = (x a ∨ y b ∨ z c ∨ w d ) = (x 1 ∨ y 1 ∨ z 0 ∨ w 1 ) ∧ (x 1 ∨ y 0 ∨ z 1 ∨ w 0 ) ∧ (x 1 ∨ y 0 ∨ z 0 ∨ w 0 ) ∧ (x 0 ∨ y 1 ∨ z 0 ∨ w 1 ) ∧ (x 0 ∨ y 0 ∨ z 0 ∨ w 1 ) ∧ (x 0 ∨ y 0 ∨ z 0 ∨ w 0 ) = (x ∨ y ∨ z ∨ w) ∨ (x ∨ y ∨ z ∨ w ) ∨ (x ∨ y ∨ z ∨ w ) ∨ ( x ∨ y ∨ z ∨ w) ∨ = ( x ∨ y ∨ z ∨ w) ∨ ( x ∨ y ∨ z ∨ w )

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

Например, вместо x z будем употреблять набор 0 — 1 — . Тогда СДНФ функции будет соответствовать множество всех её единичных наборов. Выпишем единичные наборы данной булевой функции в таблицу, разбив их на группы в соответствии с количеством единичных компонент в наборах.

Тогда для применения формулы неполного склеивания доста точно просмотреть всевозможные пары наборов, входящих в соседние группы. Результаты склеивания наборов из I полосы поместим во II полосе, а наборы, участвующие в склеиваниях, пометим крестиком. Во второй полосе снова применяем, насколько возможно, операцию склеивания, записывая результаты в III полосу и т. д. После завершения процедуры склеивания все простые импликанты попадут в таблицу и не будут помечены крестиком. Помеченные же конъюнкции поглотятся на этапе применения формулы поглощения.

Сокращённая ДНФ данной булевой функции имеет вид: x y w ∨ yz ∨ zw ∨ y w ∨ x z .

3. Для получения из сокращённой ДНФ минимальной ДНФ изобразим следующую таблицу — матрицу Квайна (табл. 2.5.1с).

Ядровыми импликантами будут 1, 4 и 5, так как для каждой из них найдётся единичный набор, на котором она одна принимает значение 1.

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

№ простой импликанты 1 2 3 4 5
единичные наборы\простые импликанты x y w yz zw y w x z
0000 1 1
0001 1 1
0011 1
0100 1 1
0110 1
1000 1 1 1
1001 1 1 1
1011 1
1100 1 1
1101 1

Для выбора наименьшего числа столбцов, удовлетворяющих перечисленным выше требованиям, составляем символическое выражение (2 ∨3)·(2 ∨4)·4·(1 ∨3)·1·(2 ∨3 ∨5)·(2 ∨4 ∨5)·4·(5 ∨3)·5.

Приведём это символическое выражение к ДНФ, используя дистрибутивный закон и формулу поглощения (A ∨ В) · А = А.

Получим: (2 ∨3)·4·1·5 = 2·4·1·5 ∨3·4·1·5, Сопоставим каждой символической конъюнкции тупиковую ДНФ и выберем из них кратчайшую.

В нашем примере символической конъюнкции 2·4·1·5 соответствует ДНФ x y w ∨ y z ∨ y w ∨ x z , а симво лической конъюнкции 3·4·1·5 — x y w ∨ z w ∨ y w ∨ x z . Каждая из полученных ДНФ является минимальной для данной булевой функции и имеет сложность, равную количеству символов переменных в формуле, т. е. сложность 9.

5. Найдём минимальную ДНФ с помощью карты Карнау (табл. 2.5.ld).

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

При построении покрытия не забываем, что карта Карнау как бы наклеена на поверхность тора, т. е. её левая и правая, а также верхняя и нижняя границы отождествляются.

В нашем примере все единицы покрываются четырьмя прямоугольниками: прямоугольник 1×2, соответствующий конъюнкции x y w , прямоугольник 1×4, соответствующий конъюнкции z w , и два квадрата, соответствующих импликантам x z и y w. Значит, минимальная ДНФ, соответствующая этому покрытию, равна xyw ∨ zw ∨ yw ∨ xz.

Задание 2.5.2

Для функций f(x,y,z), g(x,y,z,w), h(x,y,z,w,t) найти мини- мальные ДНФ и минимальные КНФ с помощью карт Карнау, указать сложности минимальных ДНФ.

f g h
1 1011
1100
1110 1110
1111 0001
1011 1110 1100 1111
1111 0001 0101 1100
2 0111
1010
1111 0010
1111 0111
1100 1011 1011 1110
1110 1011 0111 1111
3 1001
1001
1101 1001
1111 0011
1011 1111 0011 0001
0110 1101 1011 1110
4 1110
1110
1011 1010
1111 1110
1100 1100 1110 1111
1000 1111 1011 1111
5 1010
1111
1101 1100
1111 1101
1101 0011 1111 1101
1110 1101 0111 1100
6 0110
1111
1111 1011
0011 1101
1011 1100 1111 1000
0111 1011 1110 0101
7 1000
1101
1010 1111
1011 1110
1100 1110 0111 1111
0001 1111 1011 0111
8 0111
0110
1100 1110
1100 1111
1010 1110 1111 1101
0111 1001 1110 0000
9 1110
0011
1101 1011
1111 1101
1001 1100 1101 1111
1101 1111 0001 1011
10 0111
0101
1010 1110
1110 1111
1010 1110 0111 1110
0011 1110 0110 0101
11 1000
1111
1001 0001
1110 1110
0101 1110 1110 0111
0111 1110 1101 0110
12 1011
0111
1101 1011
1110 1110
1010 0111 1101 1111
1000 1111 1110 1001
13 0011 1101 0111 1011
0011 1110
1001 1100 1110 1111
1100 1111 1010 0000
14 1011
0111
1000 0110
1111 1110
0110 1101 1111 1101
1111 1011 0111 1110
15 0111
0101
1011 1101
0011 0111
1010 1111 1011 1101
0111 1110 1101 1110
16 1000
1110
1100 1100
0111 1100
1101 0111 1101 1011
0111 1110 1111 0000
17 1111
0110
0011 0111
111 1011
0101 1000 1111 1100
1000 1110 1110 0111
18 0111
1001
1100 1100
1110 0011
0111 1111 1101 0111
1111 0101 1110 1101
19 1000
1110
0111 1110
0011 1110
0001 1111 1011 1101
0010 1111 1000 1000
20 0111
1001
1010 1110
1111 1101
1011 0001 1111 1100
0111 1001 1110 1110
21 0101
1100
1111 0011
1011 1111
1001 1011 1100 1110
0001 0111 1011 1000
22 0111
0101
1100 0000
1110 1101
1011 1111 1101 0111
1110 1110 0111 0001
23 1001
0110
1101 1110
1101 1111
0111 1110 1110 0011
1111 0011 1001 1111
24 0001
1100
1100 1110
0111 1111
1010 1111 1101 1100
1111 1010 1101 0110
25 1000
1110
1010 0111
1110 1100
0111 0111 1010 0011
1111 0010 1010 1111
26 1110
0101
1101 1001
1111 0111
0110 1111 1110 1010
0110 0110 1101 0010
27 1101
1100
0011 0011
1011 1111
1001 1110 1001 1111
0010 1001 1111 0011
28 1110
0110
1010 0101
1111 1011
0111 1011 1011 1111
1111 1011 0010 1111
29 0001
1111
1101 0111
1110 0110
1101 0100 1111 0111
1110 0110 1111 1000
30 1100
0011
0110 1101
1111 1000
0111 1010 1110 0111
1110 0111 1110 0110

Пример решения задания 2.5.2

Решим задание 2.5.2 для функций f(x, у, z) = (0111 0011), g(x,y,z,w) = (1111 1101 1010 0000), h(x,y,z,w,t) = (1111 0111 1010 0110 1111 0111 1010 1010).

Карта Карнау для функции f(x,y,z) от трёх переменных имеет такой вид (табл. 2.5.2а).

Мы считаем её как бы наклеенной на поверхность цилиндра, т. е. отождествляем верхнюю часть карты Карнау с нижней. При отыскании минимальной ДНФ единицы карты Карнау покрываем прямоугольниками вида 2×2 и 1×2, отвечающим импликантам у и x z соответственно, получаем минимальную ДНФ у ∨ x z . Её сложность равна 3.

Для нахождения минимальной КНФ покрываем нули карты Карнау двумя прямоугольниками размера- ми 1×2, которые соответствуют элементарным дизъюнкциям y ∨ ∨ и у ∨ z . В результате получаем минимальную КНФ (у ∨ x ) ⋅ (у ∨ z).

При нахождении минимальной ДНФ функции g(x,y,z,w) заполняем карту Карнау и покрываем единицы карты прямоугольниками возможно больших размеров (табл. 2.5.2b).

Получим минимальную ДНФ: уw ∨ xz ∨ x w.

Сложность минимальной ДНФ равна 6.

Отыщем минимальную КНФ функции g(x,y,z,w). Для этого произведём покрытие нулей карты Карнау (табл. 2.5.2с).

Минимальная КНФ будет иметь вид:

( x ∨ y )⋅( x ∨ w )⋅( y ∨ z ∨ w ).

Рассмотрим функцию h(x,y,z,w,t) = (1111 0111 1010 1111 0111 1010 1010).

Карту Карнау для пяти переменных можно воспринимать, как «двухслойную» карту Карнау для функции от 4 переменных, где верхний слой соответствует значениям х = 0, а нижний — х = 1, причём клетки, образующие «двухслойный» прямоугольник, соответствуют импликантам, в которых переменная х отсутствует. Двухслойные прямоугольники будем изображать жирными линиями, а однослойные — тонкими (табл. 2.5.2d).

Все единицы карты Карнау могут быть покрыты тремя двухслойными прямоугольниками и двумя однослойными. Минимальная ДНФ будет иметь вид: zt v y t v x z w t v xy t .

Её сложность равна 13.

Для отыскания минимальной КНФ покроем прямоугольниками нули карты Карнау (табл. 2.5.2е).

Все нули карты Карнау могут быть покрыты тремя двухслойными прямоугольниками и двумя однослойными.

Минимальная КНФ будет иметь вид:

( y ∨ w ∨ t )-( y ∨ z ∨ t )⋅(y ∨ z ∨ w ∨ t)⋅( x ∨ y ∨ t )⋅(x ∨ z ∨ w ∨ t).

Найти сокращённую, ядровую и все тупиковые ДНФ для функции f=0011 1000 0010 0001

Author24 — интернет-сервис помощи студентам

Найти сокращённую, ядровую и все тупиковые ДНФ для функции f=0011 1000 0010 0001; решить методом Карно.
Составил карту Карно (надеюсь, что верно).
Получилось вот что, вроде это сокращенная ДНФ? Да и вроде как ещё и ядровая? А тупиковые? Их нет?

Изображения
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:

Найти сокращенную, все тупиковые и минимальные днф булевой функции
найти сокращенную все тупиковые и минимальные днф булевой функции двумя способами а) методом.

Найти сокращенную, все тупиковые и минимальные ДНФ булевой функции
f(0,1,1)=f(1,0,0)=f(1,1,0)=0 Найти сокращенную, все тупиковые и минимальные ДНФ булевой.

Найти Сокращенную Днф Функции
Формула,которой она задана, и другие задания прикреплены ниже

476 / 279 / 90
Регистрация: 15.11.2013
Сообщений: 530

Ну, во-первых, карта Карно неправильно нарисована. Два последних столбца надо поменять местами. Или, если хотите, две последние строки.

Но сути это не меняет. Сокращённая равна ядровой, равна единственной тупиковой и равна минимальной.

87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
Помогаю со студенческими работами здесь

Составить СДНФ по значениям булевой функции, найти сокращенную и минимальную ДНФ
Составить СДНФ по значениям булевой функции, найти сокращенную и минимальную ДНФ x1|x2|x3|f.

Найти сокращенную и минимальную ДНФ
Помогите пожалуйста решить. Найти сокращенную и минимальную ДНФ булевой функции f(x,y,z);.

Найти минимальную КНФ и сокращенную ДНФ
Пропустил пару тем теперь вот каюсь, не знаю как решать, сможете помочь решить? Если что то не.

Найти сокращенную ДНФ построить полином Жегалкина.
Помогите, объясните как найти сокращенную ДНФ с помощью геометрического метода Карт Карно

По заданной ДНФ постройте сокращенную ДНФ
ссылка удалена вот такая днф, по ней надо построить сокращенную, а я не 3наю как( Добавлено.

Или воспользуйтесь поиском по форуму:

Научный форум dxdy

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе «Помогите решить/разобраться (М)».

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

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.

Минимизиция булевых функций

На страницу Пред. 1 , 2 , 3 След.

26.11.2008, 09:03

Я не спорю, могла и напутать, а хотя-бы образцов решений типовых задач ни у кого нет?

Здесь более наглядно задачи

26.11.2008, 17:59
Неужели ни у кого нет примерных задач хотя-бы? очень нужно
26.11.2008, 18:24

Заслуженный участник

07.05.2009, 22:51

Помогите, пожалуйста, разобраться в тот как надо находить минимальные ДНФ и ядровые ДНФ.
Допустим, у меня функция заданная вектором $\tilde f=10101101$. С помощью булева куба я нашел сокращенную ДНФ этой функции: $\bar x_1\bar x_3\vee \bar x_2\bar x_3\vee x_1\bar x_2\vee x_1 x_3$. Вот никак в голову не могу взять, как находить минимальные и ядровые ДНФ данной функции. Помогите разобраться. Или ссылки привести на источники, где это доходчиво объясняется.

08.05.2009, 10:25

Заслуженный участник

Я так понял условие упражнения: функция принимает значения 1 на наборах c номерами 0, 2, 4, 5, 7.
Тогда у меня получается другой результат при минимизации на кубе — «более минимальный».

По поводу минимальных ДНФ посмотрите ссылки, приведенные Выше участником Brukvalub .

// 8.05.09 близкие темы соединены. / GAA

08.05.2009, 11:51

Заслуженный участник

GAA писал(а):
Тогда у меня получается другой результат при минимизации на кубе — «более минимальный».

Ну, сокращённая ДНФ не обязана быть минимальной…

rar писал(а):
Или ссылки привести на источники, где это доходчиво объясняется.

Из «ссылок на источники» посоветовал бы Яблонского, наверное.
08.05.2009, 13:33

Я все эти материалы перерыл — так и не понял как найти ядровую и все минимальные ДНФ по булеву кубу. Ну не могу понять!

Добавлено спустя 38 минут 14 секунд:

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

08.05.2009, 14:09

Заслуженный участник

Последний раз редактировалось GAA 10.05.2009, 11:37, всего редактировалось 1 раз.

$x_1\bar x_2 \bar x_3$

1. По поводу минимальных ДНФ по кубу. Нарисуйте куб и нанесите на него точки — пометьте вершины. В Вашем случае нет граней со всеми помеченными вершинами, но точки можно «покрыть» ребрами. Два определенных ребра войдут в ответ обязательно. А вот точку можно покрыть ребрами двумя способами. Т.обр. в ответе будет две минимальных ДНФ. Приведите, пожалуйста, эти ДНФ.

Добавлено спустя 8 минут 31 секунду:

2. По поводу ядровой см. приведенную Brukvalub ом ссылку .

08.05.2009, 14:14

$D_<min>=\bar x_1\bar x_3 \vee \bar x_2 \bar x_3$» /> и вторая <img decoding= Заслуженный участник

rar писал(а):

$D_<min>=\bar x_1\bar x_3 \vee \bar x_2 \bar x_3$» /> и вторая <img decoding= Заслуженный участник

Последний раз редактировалось GAA 08.05.2009, 17:46, всего редактировалось 2 раз(а).

rar писал(а):
Ну, а не могли бы мне расписать как в моем случае найти. Я видимо совсем не догоняю!

1. Нарисовать куб.
2. Пометить вершины, на которых функция принимает значение 1 (их пять штук).
3. Соединить вершины ребрами (будет три ребра, например, ребро, соединяющее вершины $x_1 \bar x_2 \bar x_3$и $x_1 \bar x_2 x_3$есть $x_1 \bar x_2$).
4. Записать результат в виде дизъюнкции трех конъюнктов (т.е. трех элементарных конъюнкций).

При редактировании добавлена расшифровка: «т.е. трех элементарных конъюнкций.»

08.05.2009, 15:15

Заслуженный участник

rar писал(а):
Мне надо по булеву кубу найти минимальные и ядровые ДНФ.

Употреблять множественное число в обоих случаях не очень корректно.

Ядровая ДНФ — она единственная. Собственно, фишка в том и состоит, что мы можем ещё чуть-чуть «сократить» сокращённую ДНФ, не начиная строить и перебирать тупиковые.

Что касается минимальных, то обычно тоже довольствуются тем, что отыскивают какую-нибудь одну. Дело в том, что могут иметься минимальные ДНФ, не являвшиеся тупиковыми, и «выцеплять» их сложно.

Вообще, элементарные геометрические соображения не могут много дать для построения минимальной ДНФ. В общем случае мы получим лишь сколько-то тупиковых ДНФ, которые нужно будет просто выписать и сравнить на предмет «длины».

$\bar x_1\bar x_3\vee \bar x_2\bar x_3\vee x_1\bar x_2\vee x_1 x_3$

Объясню на примере, что такое ядровая ДНФ. Пусть сокращённая ДНФ некоторой формулы имеет такой вид, как указал rar : . Каждому из дизъюнктов соответствует некоторая «грань» куба. В нашем случае все «грани» одномерные, т. е. рёбра.

Отыщем теперь в сокращённой ДНФ «важные» грани, то есть те, единственно благодаря которым оказались покрыты некоторые точки. К примеру, «важной» будет грань $x_1 x_3$: если бы не она, кто из граней сокращённой ДНФ покрыл бы вершину $7_2$? Другая «важная» грань сокращённой ДНФ — это $\bar x_1\bar x_3$. Установите самостоятельно вершину, которая оказалась покрыта лишь благодаря ей.

Других «важных» граней отыскать не удаётся. Собственно, объединение этих «важных» граней и называется ядром. В некоторых источниках и сами эти грани называются ядровыми .

При минимизации сокращённой ДНФ ядровые грани выкинуты из неё быть не могут. Это, конечно, плохо. Но раз уж так, можно попытаться выкинуть из сокращённой ДНФ те грани, которые покрываются объединением ядровых. ДНФ, получаемая из сокращённой выкидыванием всех («неважных») граней, покрываемых ядром, и называется ядровой.

В нашем случае сокращённая ДНФ не имеет «неважных» граней, покрываемых ядром. Значит, ядровая ДНФ совпадает с сокращённой.

Сокращённая и минимальная ДНФ

Например: [math](x \land y)[/math] содержится в [math](x \land y \land z)[/math] .

Функцию можно записать с помощью сокращенной ДНФ не единственным способом.

Запишем функцию [math]\left\lt x, y, z\right\gt [/math] (медиана) в виде совершенной ДНФ: [math](x \land y \land z) \lor (x \land y \land \lnot z) \lor (x \land \lnot y \land z) \lor (\neg x \land y \land z)[/math] . Известно, что это выражение равносильно следующему: [math]((x \land y \land z) \lor (x \land y \land \lnot z)) \lor ((x \land \lnot y \land z) \lor (x \land y \land z)) \lor ((\neg x \land y \land z) \lor (x \land y \land z))[/math] . Вынесем в каждой скобке общий конъюнкт (например, в первой [math](x \land y \land z) \lor (x \land y \land \lnot z)=(x \land y) \lor (z \land \lnot z)[/math] . Так как [math]z \land \lnot z = 0[/math] , то такой конъюнкт не влияет на значение выражения, и его можно опустить. Получим в итоге формулу [math](x \land y) \lor (y \land z) \lor (x \land z)[/math] .

Минимальная ДНФ

Определение:
Минимальная ДНФ (англ. minimal disjunctive normal form) — такая сокращенная ДНФ, в которой содержится минимальное количество вхождений переменных.

Каждая минимальная ДНФ является сокращенной, но не каждая сокращенная — минимальна. Например, запись [math](x \land y) \lor (y \land z) \lor (x \land z)[/math] является минимальной ДНФ для медианы (она же сокращенная, как видно в примере выше); а запись [math](x \land y \land \lnot z) \lor (\neg x \land y \land z) \lor (x \land z)[/math] — не минимальная, но сокращенная ДНФ.

Минимизация ДНФ

Рассмотрим несколько способов минимизации дизъюнктивных нормальных форм:

Визуализация гиперкубами

Гиперкуб.PNG

Этот способ работает при количестве переменных не больше трёх (в противном необходимо вводить четвёртое или следующие за ним измерения для представления фигур). Сначала мы рисуем куб в системе отсчёта [math]Oxyz[/math] (названия координатных осей соответствуют названиям переменных). Затем каждую вершину обрабатываем следующим образом:

Описание алгоритма Пример
Если у нас конъюнкт, переменные в котором равны соответствующим координатам вершины, то в эту вершину мы помещаем закрашенный чёрным кружок. Вершине с координатами [math](0,1,1) [/math] соответствует конъюнкт [math](\neg X \wedge Y \wedge Z)[/math] , он равен единице при [math]X=0, Y=1[/math] и [math]Z=1[/math] )
В противном случае мы помещаем в вершину закрашенный белый кружок. Для такой ДНФ: [math](X \wedge \neg Y \wedge Z)\vee[/math] [math] (X \wedge Y \wedge Z) \vee [/math] [math] (\neg X \wedge Y \wedge Z) \vee[/math] [math] (\neg X \wedge Y \wedge \neg Z) \vee [/math] [math]( X \wedge Y \wedge \neg Z)[/math] мы получим следующий гиперкуб (см. рисунок)
Далее обработка гиперкуба идёт следующим образом:

пока у нас есть незакрашенные вершины, мы выбираем грань, либо вершину, либо ребро, на которых больше всего закрашенных чёрным вершин и ещё не обработанных вершин.

В итоге нашу изначальную ДНФ можно записать как [math](Y) \vee (X \wedge Z)[/math] .

Карты Карно

Построим следующую таблицу [math]n \times n[/math] , где [math]n[/math] — число переменных:

[math]w[/math] [math]w[/math] [math]\neg[/math] [math]\neg[/math]
[math]z[/math] [math]\neg[/math] [math]\neg[/math] [math]z[/math]
[math]y[/math] [math]x[/math]
[math]y[/math] [math]\neg[/math]
[math]\neg[/math] [math]\neg[/math]
[math]\neg[/math] [math]x[/math]

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

[math](\neg X \wedge Y \wedge \neg Z \wedge W) \vee (\neg X \wedge Y \wedge \neg Z \wedge \neg W) \vee (\neg X \wedge \neg Y \wedge \neg Z \wedge W) \vee (\neg X \wedge \neg Y \wedge \neg Z \wedge \neg W) \vee (\neg X \wedge \neg Y \wedge Z \wedge \neg W) \vee (X \wedge \neg Y \wedge \neg Z \wedge \neg W) \vee (X \wedge \neg Y \wedge Z \wedge \neg W)[/math]

будет выглядеть на картах Карно так:

[math]w[/math] [math]w[/math] [math]\neg[/math] [math]\neg[/math]
[math]z[/math] [math]\neg[/math] [math]\neg[/math] [math]z[/math]
[math]y[/math] [math]x[/math]
[math]y[/math] [math]\neg[/math] [math]1[/math] [math]1[/math]
[math]\neg[/math] [math]\neg[/math] [math]1[/math] [math]1[/math]
[math]\neg[/math] [math]x[/math] [math]1[/math] [math]1[/math]

Теперь покрываем прямоугольниками (длины сторон которых — степени двойки ( [math]1, 2, 4[/math] )) те ячейки карт Карно, которые содержат в себе единицу (на каждом ходу мы выбираем такой прямоугольник, чтобы он покрывал наибольшее количество ещё не покрытых клеток) до тех пор, пока не покроем все такие ячейки.

Для карт Карно на примере это выглядело бы так:

[math]w[/math] [math]w[/math] [math]\neg[/math] [math]\neg[/math]
[math]z[/math] [math]\neg[/math] [math]\neg[/math] [math]z[/math]
[math]y[/math] [math]x[/math]
[math]y[/math] [math]\neg[/math] [math]1[/math] [math]1[/math]
[math]\neg[/math] [math]\neg[/math] [math]1[/math] [math]1[/math] [math]1[/math]
[math]\neg[/math] [math]x[/math] [math]1[/math] [math]1[/math]

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

То есть, в этом примере получаем: [math](\neg Z \wedge \neg X) \vee (\neg W \wedge \neg Y)[/math]

Метод Квайна

Этот метод основан на применении двух основных операций:

  • Операция попарного неполного склеивания:
  • Операция элементарного поглощения:

Пусть [math]A = y\neg z\neg w[/math] , тогда:

  • Операция попарного неполного склеивания:
  • Операция элементарного поглощения:

Метод состоит в последовательном выполнении всех возможных склеиваний и затем всех поглощений частей СДНФ пока это может быть осуществимо.

Описание алгоритма
  • Исходным является множество пар вида [math]Ax[/math] или [math]A \neg x[/math]
  • Выполняются все возможные операции неполного попарного склеивания для элементарных конъюнкций длины [math] n[/math] (где [math] n[/math] — число аргументов).
  • Выполняются все возможные операции элементарного поглощения для элементарных конъюнкций длины [math] n-1[/math] (общая часть » [math]p[/math] » имеет длину [math] n-1[/math] )
  • В результате получилось множество элементарных конъюнкций, разделяемых на два подмножества (по длине):
    • подмножество элементарных конъюнкций длины [math] n[/math] (оставшиеся)
    • подмножество элементарных конъюнкций длины [math] n-1[/math]

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

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

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

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

    Пример

    Функция от четырёх аргументов задана следующей таблицей:

    Проведём операции неполного склеивания и поглощения:

    Элементарная конъюнкция Поглощение
    [math]1[/math] [math]\neg x\neg y\neg z\neg w[/math] [math]+[/math]
    [math]2[/math] [math]\neg xy\neg z\neg w[/math] [math]+[/math]
    [math]3[/math] [math] x\neg yz\neg w[/math] [math]+[/math]
    [math]4[/math] [math] x\neg y zw[/math] [math]+[/math]
    [math]5[/math] [math] xy\neg z\neg w[/math] [math]+[/math]
    [math]6[/math] [math] xy\neg zw[/math] [math]+[/math]
    [math]7[/math] [math] xyz\neg w[/math] [math]+[/math]
    [math]8[/math] [math] xyzw[/math] [math]+[/math]
    № склеивания Результат
    [math]1 — 2[/math] [math]\neg x \neg z\neg w[/math]
    [math]2 — 5[/math] [math]y \neg z\neg w[/math]
    [math]3-4[/math] [math] x \neg yz[/math]
    [math]3-7[/math] [math] \neg x \neg z\neg w[/math]
    [math]4-8[/math] [math] xzw[/math]
    [math]5-6[/math] [math] xy\neg z[/math]
    [math]5-7[/math] [math] xy \neg w[/math]
    [math]6-8[/math] [math] xyw[/math]
    [math]7-8[/math] [math] xyz[/math]

    На данном шаге все элементы вида [math]Ax[/math] или [math]A \neg x[/math] участвовали в операциях попарного неполного склеивания и были поглощены своими собственными частями. Поэтому элементы сокращённой ДНФ на этом шаге не получены.

    Элементарная конъюнкция Поглощение
    [math]1[/math] [math]\neg x\neg z\neg w[/math]
    [math]2[/math] [math]y\neg z\neg w[/math]
    [math]3[/math] [math] x\neg yz[/math] [math]+[/math]
    [math]4[/math] [math] \neg x\neg z\neg w[/math] [math]+[/math]
    [math]5[/math] [math] xzw[/math] [math]+[/math]
    [math]6[/math] [math] xy\neg z[/math] [math]+[/math]
    [math]7[/math] [math] xy\neg w[/math] [math]+[/math]
    [math]8[/math] [math] xyw[/math] [math]+[/math]
    [math]9[/math] [math] xyz[/math] [math]+[/math]
    № склеивания Результат
    [math]3-9[/math] [math]xz[/math]
    [math]4 — 5[/math] [math]xz[/math]
    [math]6-9[/math] [math] xy[/math]
    [math]7-8[/math] [math] xy[/math]

    На данном этапе получаем элементы сокращённой ДНФ [math]\neg x \land \neg z \land \neg w[/math] и [math]y \land \neg z \land \neg w[/math]

    Элементарная конъюнкция Поглощение
    [math]1[/math] [math]xz[/math]
    [math]2[/math] [math]xy[/math]

    Обе элементарные конъюнкции на данном шаге являются элементами сокращённой ДНФ.

    В результате выполнения алгоритма мы получаем следующую сокращённую ДНФ: [math](\neg x \land \neg z \land \neg w) \lor (y \land \neg z \land \neg w) \lor (x \land z) \lor (x \land y) [/math]

    Переход от сокращённой формы к минимальной:

    • Единицы ДНФ, покрываемые элементами [math]Ax[/math] или [math]A \neg x[/math] обозначаются «+». Пары [math]Ax[/math] и [math]A \neg x[/math] , попадающие в ядро помечаются «*».
    • Единицы функции, которые покрываются только каким-то одним конъюнктом из системы элементов сокращённой ДНФ, помечаются “>”.
    • Единицы функции, покрываемые ядром, но не покрываемые только каким-то одним конъюнктом из системы элементов сокращённой ДНФ помечаются “>>”.
    [math]\neg x\neg y\neg z\neg w[/math] [math]\gt [/math] [math]\neg x y\neg z\neg w[/math] [math]\gt \gt [/math] [math]x\neg yz\neg w[/math] [math]\gt [/math] [math]x\neg yzw[/math] [math]\gt [/math] [math]xy\neg z\neg w[/math] [math]\gt \gt [/math] [math]xy\neg zw[/math] [math]\gt [/math] [math]xyz\neg w[/math] [math]\gt \gt [/math] [math]xyzw[/math] [math]\gt \gt [/math]
    [math]\neg x\neg z\neg w^*[/math] [math]+[/math] [math]+[/math]
    [math]y\neg z\neg w[/math] [math]+[/math] [math]+[/math]
    [math]xz^*[/math] [math]+[/math] [math]+[/math] [math]+[/math] [math]+[/math]
    [math]xy^*[/math] [math]+[/math] [math]+[/math] [math]+[/math] [math]+[/math]

    На основе этой таблицы получим ядро [math](\neg x \land \neg z \land \neg w) \lor (x \land z) \lor (x \land y) [/math] , которое является также и минимальной ДНФ.

    См. также

    Источники информации

    • Минимизация логических функций методом Куайна — Википедия
    • Метод Квайна
    • Карта Карно — Википедия
    • Минимизация булевых функций в классе ДНФ
    • Минимизация ДНФ методом Квайна

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *