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

Сокращенная ДНФ

Определение:

Сокращенная ДНФ: форма записи функции, обладающая следующими свойствами: Любые два слагаемых различаются как минимум в двух позициях Ни один из конъюнктов не содержится в другом. Например, [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].

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

Определение:

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

Каждая минимальная ДНФ является сокращенной, но не каждая сокращенная — минимальна. Например, запись [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] - не минимальная, но сокращенная ДНФ.

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

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

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

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

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

Например, для такой ДНФ: [math](X \wedge \neg Y \wedge Z) \vee (X \wedge Y \wedge Z) \vee (\neg X \wedge Y \wedge Z) \vee (\neg X \wedge Y \wedge \neg Z) \vee ( X \wedge Y \wedge \neg Z)[/math] мы получим следующий гиперкуб (рис. 1) Далее обработка гиперкуба идёт следующим образом: пока у нас есть незакрашенные вершины, мы выбираем грань, либо вершину, либо ребро, на которых больше всего закрашенных чёрным вершин и ещё не обработанных вершин.

• Если в данном гиперкубе есть грань, все вершины на которой закрашены чёрным, то мы можем записать её в качестве конъюнкта, где будет только переменная с неизменяющейся соответствующей ей координатой, например, грань, на которой лежат закрашенные вершины (0,1,1), (0,1,0), (1,1,0) и (1,1,1) мы можем записать как конъюнкт [math]Y[/math].
• Теперь мы смотрим, остались ли на рёбрах куба закрашенные и не отмеченные нами в ДНФ вершины. Если — да, то рёбра с такими вершинами мы можем записать в качестве конъюнкта, где будут только переменные с неизменяющимися соответствующим им координатами, например, ребро, соединяющее закрашенные вершины (0,1,1) и (1,1,1) мы можем записать как конъюнкт [math](Y \wedge Z)[/math].
• И если после такой обработки у нас остались свободные вершины, мы просто переписываем координаты каждой такой вершины в отдельный конъюнкт, равный 1. Например, вершину (1,0,1) мы бы переписали как конъюнкт [math](X \wedge \neg Y \wedge Z)[/math].

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

Карты Карно

Построим следующую таблицу n*n, где n — количество переменных:

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

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

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

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

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

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

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

• После этого записываем каждый прямоугольник в виде конъюнкта, в котором будут указаны только те переменные, которые одинаковы для всех ячеек этого прямоугольника: [math](\neg Z \wedge \neg X) \vee (\neg W \wedge \neg Y)[/math]

Метод Квайна

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

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

[math]A x \lor A \neg x = A x \lor A \neg x \lor A[/math]

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

[math]A \tilde x \lor A = A [/math]

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

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

Описание алгоритма

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

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

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

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

Набор [math]xyzw[/math]	0000	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010	1011	1100	1101	1110	1111
Значение исходной функции	1	0	0	0	1	0	0	0	0	0	1	1	1	1	1	1

№	Эл. конъюнкция	Поглощение
1	[math]\neg x\neg y\neg z\neg w[/math]	+
2	[math]\neg xy\neg z\neg w[/math]	+
3	[math]x\neg yz\neg w[/math]	+
4	[math]x\neg y zw[/math]	+
5	[math]xy\neg z\neg w[/math]	+
6	[math]xy\neg zw[/math]	+
7	[math]xyz\neg w[/math]	+
8	[math]xyzw[/math]	+

№№ скл.	Результат
1 - 2	[math]\neg x \neg z\neg w[/math]
2 - 5	[math]y \neg z\neg w[/math]
3 - 4	[math]x \neg yz[/math]
3 - 7	[math]\neg x \neg z\neg w[/math]
4 - 8	[math] xzw[/math]
5 - 6	[math]xy\neg z[/math]
5 - 7	[math]xy \neg w[/math]
6 - 8	[math]xyw[/math]
7 - 8	[math]xyz[/math]

№	Эл. конъюнкция	Поглощение
1	[math]\neg x \neg z\neg w[/math]
2	[math]y \neg z\neg w[/math]
3	[math]x \neg yz[/math]	+
4	[math]\neg x \neg z\neg w[/math]	+
5	[math] xzw[/math]	+
6	[math]xy\neg z[/math]	+
7	[math]xy \neg w[/math]	+
8	[math]xyw[/math]	+
9	[math]xyz[/math]	+

№№ скл.	Результат
3 - 9	[math]xz[/math]
4 - 5	[math]xz[/math]
6 - 9	[math]xy[/math]
7 - 8	[math]xy[/math]

№	Эл. конъюнкция	Поглощение
1	[math]xz[/math]
2	[math]xy[/math]

Ссылки

• Минимизация логических функций методом Куайна — Википедия
• http://matrixcalc.org/pf1.html
• Карта Карно — Википедия
• http://vuz.exponenta.ru/PDF/book/kv.html
• http://tablica-istinnosti.ru/minimizatsiya-dnf-metodom-kvayna.html