105
правок
Изменения
м
}}
<br>{| borderclass="1wikitable" style="background-color:#FFF; text-align:center" | colspan="2" rowspan="2" | !style="background-color:#F0F8FF;" |<tex> w </tex> !style="background-color:#F0F8FF;" |<tex> w </tex> !style="background-color:#F0F8FF;" |<tex> \neg {w}</tex> !style="background-color:#F0F8FF;" |<tex> \neg {w}</tex> |- ! style="background-color:#F8F8FF;" | | !<tex>z</tex> !style="background-color:#F8F8FF;" |<tex> \neg {z}</tex> !style="background-color:#F8F8FF;" |<tex> \neg {z}</tex> !style="background-color:#F8F8FF;" |<tex>z</tex> |- !style="background-color:#E0FFFF;" |<tex>y</tex> !style="background-color:#FFF5EE;" |<tex>x</tex> | | | | |- !style="background-color:#E0FFFF;" |<tex>y</tex> !style="background-color:#FFF5EE;" |<tex> \neg {x}</tex> | |<tex>1</tex> |<tex>1</tex> | |- !style="background-color:#E0FFFF;" |<tex> \neg {y}</tex> !style="background-color:#FFF5EE;" |<tex> \neg {x}</tex> | |<tex>1</tex> |<tex>1</tex> |1 |- !style="background-color:#E0FFFF;" |<tex> \neg {y}</tex> !style="background-color:#FFF5EE;" |<tex>x</tex> | | |<tex>1</tex> |<tex>1</tex> |}<br>Теперь покрываем прямоугольниками (длины сторон которых {{---}} степени двойки (<tex>1, 2, 4</tex>)) те ячейки карт Карно, которые содержат в себе единицу (на каждом ходу мы выбираем такой прямоугольник, чтобы он покрывал наибольшее количество ещё не покрытых клеток) до тех пор, пока не покроем все такие ячейки.
<br>{| borderclass="wikitable" style="1background-color:#FFF; text-align:center" | colspan="2" rowspan="2" | !style="background-color:#F0F8FF;" |<tex> w </tex> !style="background-color:#F0F8FF;" |<tex> w </tex> !style="background-color:#F0F8FF;" |<tex> \neg {w}</tex> !style="background-color:#F0F8FF;" |<tex> \neg {w}</tex> |- | ! style="background-color:#F8F8FF;" | !<tex> z </tex> !style="background-color:#F8F8FF;" |<tex> \neg {z}</tex> !style="background-color:#F8F8FF;" |<tex> \neg {z}</tex> !style="background-color:#F8F8FF;" |<tex> z </tex> |- !style="background-color:#E0FFFF;" |<tex> y </tex> !style="background-color:#FFF5EE;" |<tex> x </tex> | | | | |- !style="background-color:#E0FFFF;" |<tex> y </tex> !style="background-color:#FFF5EE;" |<tex> \neg {x}</tex> | |style="background-color:#F4A460FFA07A;"|<tex>1</tex> |style="background-color:#F4A460FFA07A;"|<tex>1</tex> | |- !style="background-color:#E0FFFF;" |<tex> \neg {y}</tex> !style="background-color:#FFF5EE;" |<tex> \neg {x}</tex> | |style="background-color:#F4A460FFA07A;"|<tex>1</tex> |style="background-color:#B4D19A80D0BD;"|<tex>1</tex> |style="background-color:#7FFFD400FFFF;"|<tex>1</tex> |- !style="background-color:#E0FFFF;" |<tex> \neg {y}</tex> !style="background-color:#FFF5EE;" |<tex> x </tex> | | |style="background-color:#7FFFD400FFFF;"|<tex>1</tex> |style="background-color:#7FFFD400FFFF;"|<tex>1</tex>
<br>
|-
|!<tex>\neg x\neg y\neg z\neg w</tex> <tex>></tex>|!<tex>\neg x y\neg z\neg w</tex><tex> >></tex>|!<tex>x\neg yz\neg w</tex> <tex>></tex>|!<tex>x\neg yzw</tex> <tex>></tex>|!<tex>xy\neg z\neg w</tex><tex> >></tex>|!<tex>xy\neg zw</tex> <tex>></tex>|!<tex>xyz\neg w</tex><tex> >></tex>|!<tex>xyzw</tex><tex> >></tex>
|!<tex>\neg x\neg z\neg w^*</tex>*|style="background-color:#F4A460FF7F50;"| <tex>+</tex>| <tex>+</tex>
|!<tex>y\neg z\neg w</tex>
|!<tex>xz^*</tex>*
|!<tex>xy^*</tex>*
Дмитрий Мурзин переименовал страницу Сокращенная и минимальная ДНФ в Сокращённая и минимальная ДНФ: Ёфикация
{{Определение
|definition =
'''Сокращенная ДНФ: ''' (англ. ''reduced disjunctive normal form'') {{---}} форма записи функции, обладающая следующими свойствами: *Любые любые два слагаемых различаются как минимум в двух позициях, *Ни ни один из конъюнктов не содержится в другом. }}'''Например, :'''<tex>(x \land y)</tex> содержится в <tex>(x \land y \land z)</tex>.
Функцию можно записать с помощью сокращенной ДНФ не единственным способом.
Так как <tex>z \land \lnot z = 0</tex>, то такой конъюнкт не влияет на значение выражения, и его можно опустить.
Получим в итоге формулу <tex>(x \land y) \lor (y \land z) \lor (x \land z)</tex>.
== Минимальная ДНФ ==
{{Определение
|definition =
'''Минимальная ДНФ ''' (англ. ''minimal disjunctive normal form'') {{---}} такая сокращенная ДНФ, в которой содержится минимальное количество вхождений переменных.
}}
Каждая минимальная ДНФ является сокращенной, но не каждая сокращенная {{---}} минимальна.
Например, запись <tex>(x \land y) \lor (y \land z) \lor (x \land z)</tex> является минимальной ДНФ для медианы (она же сокращенная, как видно в примере выше); а запись <tex>(x \land y \land \lnot z) \lor (\neg x \land y \land z) \lor (x \land z)</tex> {{- --}} не минимальная, но сокращенная ДНФ.<br>
== Минимизация ДНФ ==
|Теперь мы смотрим, остались ли на рёбрах куба закрашенные и не отмеченные нами в ДНФ вершины. Если — да, то рёбра с такими вершинами мы можем записать в качестве конъюнкта, где будут только переменные с неизменяющимися соответствующим им координатами
|Ребро, соединяющее закрашенные вершины (<tex>(0,1,1)</tex> и <tex>(1,1,1)</tex> мы можем записать как конъюнкт <tex>(Y \wedge Z)</tex>.
|-
|И если после такой обработки у нас остались свободные вершины, мы просто переписываем координаты каждой такой вершины в отдельный конъюнкт, равный <tex>1</tex>.
=== Карты Карно ===
Построим следующую таблицу <tex>n*\times n</tex>, где <tex>n</tex> {{---}} количество число переменных:{| borderclass="1wikitable" style="background-color:#FFF; text-align:center" | colspan="2" rowspan="2" | !style="background-color:#F0F8FF;" |<tex> w </tex> !style="background-color:#F0F8FF;" |<tex> w </tex> !style="background-color:#F0F8FF;" |<tex> \neg {w}</tex> !style="background-color:#F0F8FF;" |<tex> \neg {w}</tex> |- ! style="background-color:#F8F8FF;" | | !<tex>z</tex> !style="background-color:#F8F8FF;" |<tex> \neg {z}</tex> !style="background-color:#F8F8FF;" |<tex> \neg {z}</tex> !style="background-color:#F8F8FF;" |<tex>z</tex> |- !style="background-color:#E0FFFF;" |<tex>y</tex> !style="background-color:#FFF5EE;" |<tex>x</tex> | | | | |- !style="background-color:#E0FFFF;" |<tex>y</tex> !style="background-color:#FFF5EE;" |<tex> \neg {x}</tex> | | | | |- !style="background-color:#E0FFFF;" |<tex> \neg {y}</tex> !style="background-color:#FFF5EE;" |<tex> \neg {x}</tex> | | | | |- !style="background-color:#E0FFFF;" |<tex> \neg {y}</tex> !style="background-color:#FFF5EE;" |<tex>x</tex> | | | | |}
Теперь для каждого конъюнкта мы помечаем соответствующую ему ячейку таблицы.
<br>
<br>
<tex>(\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 \neg 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 (\neg X \wedge \neg Y \wedge \neg Z \wedge \neg W)</tex>
<br>
<br>
будет выглядеть на картах Карно так:
<br>
Для карт Карно на примере это выглядело бы так:
|}
После этого записываем каждый прямоугольник в виде конъюнкта, в котором будут указаны только те переменные, которые одинаковы для всех ячеек этого прямоугольника.
*Операция попарного неполного склеивания:
:<tex>A x \lor A \neg x = A x \lor A \neg x \lor A</tex>
*Операция элементарного поглощения:
:<tex>A \tilde x \lor A = A </tex>
:(где <tex>A </tex> {{---}} любое элементарное произведениенекоторая элементарная конъюнкция, то есть конъюнкт, в который каждая из переменных входит не более одного раза)'''Например:''' Пусть <tex>A = y\neg z\neg w</tex>, тогда:*Операция попарного неполного склеивания::<tex>y\neg z\neg w x \lor y\neg z\neg w \neg x = y\neg z\neg w x \lor y\neg z\neg w \neg x \lor y\neg z\neg w</tex>*Операция элементарного поглощения::<tex>y\neg z\neg w \tilde x \lor y\neg z\neg w = y\neg z\neg w</tex>
Метод состоит в последовательном выполнении всех возможных склеиваний и затем всех поглощений частей СДНФ пока это может быть осуществимо.
====Описание алгоритма====
*Исходным является множество пар вида <tex>Ax</tex> или <tex>A \neg x</tex>
*Выполняются все возможные операции неполного попарного склеивания для элементарных конъюнкций длины <tex> n </tex> (где <tex> n </tex> {{---}} количество число аргументов).*Выполняются все возможные операции элементарного поглощения для элементарных конъюнкций длины <tex> n-1 </tex> (общая часть "<tex>p</tex>" имеет длину <tex> n-1</tex>)
*В результате получилось множество элементарных конъюнкций, разделяемых на два подмножества (по длине):
**подмножество элементарных конъюнкций длины <tex> n </tex> (оставшиеся)**подмножество элементарных конъюнкций длины <tex> n-1</tex>*Если множество элементарных конъюнкций длины <tex> n-1 </tex> не пусто, то заново выполняются операции неполного попарного склеивания и элементарного поглощения для конъюнкций длины <tex> n-1 </tex> и т.дтак далее.
Алгоритм завершается, когда подмножество является пустым, либо нельзя выполнить ни одной операции неполного попарного склеивания.
После выполнения этого алгоритма будет получена сокращенная (но еще не минимальная ) форма.
Переход от сокращённой формы к минимальной осуществляется с помощью специальной таблицы.
Функция от четырёх аргументов задана следующей таблицей:
{|borderclass="1wikitable" style="background-color:#FFF; text-align:center"|!Набор <tex>xyzw</tex>|<tex>0000</tex>|<tex>0001</tex>|<tex>0010</tex>|<tex>0011</tex>|<tex>0100</tex>|<tex>0101</tex>|<tex>0110</tex>|<tex>0111</tex>|<tex>1000</tex>|<tex>1001</tex>|<tex>1010</tex>|<tex>1011</tex>|<tex>1100</tex>|<tex>1101</tex>|<tex>1110</tex>|<tex>1111|-|Значение исходной функции|1|0|0|0|1|0|0|0|0|0|1|1|1|1|1|1</tex>
|-
!Значение
исходной
функции
|<tex>1</tex>
|<tex>0</tex>
|<tex>0</tex>
|<tex>0</tex>
|<tex>1</tex>
|<tex>0</tex>
|<tex>0</tex>
|<tex>0</tex>
|<tex>0</tex>
|<tex>0</tex>
|<tex>1</tex>
|<tex>1</tex>
|<tex>1</tex>
|<tex>1</tex>
|<tex>1</tex>
|<tex>1</tex>
|}
Проведём операции неполного склеивания и поглощения:
{|borderclass="1wikitable" style="background-color:#FFF; text-align:center;"|!№|!Элементарная конъюнкция|!Поглощение
|-
|<tex>1</tex>
|<tex>\neg x\neg y\neg z\neg w</tex>
| <tex>+</tex>
|-
|<tex>2</tex>
|<tex>\neg xy\neg z\neg w</tex>
| <tex>+</tex>
|-
|<tex>3</tex>|<tex>x\neg yz\neg w</tex>| <tex>+</tex>
|-
|<tex>4</tex>|<tex>x\neg y zw</tex>| <tex>+</tex>
|-
|<tex>5</tex>|<tex> xy\neg z\neg w</tex>| <tex>+</tex>
|-
|<tex>6</tex>|<tex> xy\neg zw</tex>| <tex>+</tex>
|-
|<tex>7</tex>|<tex>xyz\neg w</tex>| +|-|8|<tex>xyzw+</tex>| +
|-
|<tex>8</tex>
|<tex> xyzw</tex>
|<tex>+</tex>
|}
{|borderclass="wikitable" style="1background-color:#FFF; text-align:center;"|№№ !№ склеивания|!Результат
|-
| <tex>1 - 2</tex>
|<tex>\neg x \neg z\neg w</tex>
|-
| <tex>2 - 5</tex>
|<tex>y \neg z\neg w</tex>
|-
| <tex>3 - 4|<tex>x \neg yz</tex>|-| 3 - 7|<tex>\neg x \neg z\neg wyz</tex>
|-
| 4 <tex>3- 87</tex>|<tex> xzw\neg x \neg z\neg w</tex>
|-
| 5 <tex>4- 68</tex>|<tex>xy\neg z xzw</tex>
|-
| <tex>5 - 76</tex>|<tex>xy \neg wz</tex>
|-
| 6 <tex>5- 87</tex>|<tex>xyw xy \neg w</tex>
|-
| 7 <tex>6- 8</tex>|<tex>xyzxyw</tex>
|-
|<tex>7-8</tex>
|<tex> xyz</tex>
|}
На данном шаге все элементарные конъюнкции элементы вида <tex>Ax</tex> или <tex>A \neg x</tex> участвовали в операциях попарного неполного склеивания и были поглощены своими собственными частями. Поэтому простые импликанты элементы сокращённой ДНФ на этом шаге не получены.
{|borderclass="1wikitable" style="background-color:#FFF;text-align:center;"|!№|!Элементарная конъюнкция|!Поглощение
|-
| <tex>1</tex>|<tex>\neg x \neg z\neg w</tex>
|
|-
| <tex>2</tex>|<tex>y \neg z\neg w</tex>
|
|-
| <tex>3</tex>|<tex>x \neg yz</tex>| <tex>+</tex>
|-
| <tex>4</tex>|<tex>\neg x \neg z\neg w</tex>| <tex>+</tex>
|-
| <tex>5</tex>|<tex> xzw</tex>| <tex>+</tex>
|-
| <tex>6</tex>|<tex> xy\neg z</tex>| <tex>+</tex>
|-
| <tex>7</tex>|<tex>xy \neg w</tex>| <tex>+</tex>
|-
| <tex>8</tex>|<tex>xyw</tex>| +|-| 9|<tex>xyz+</tex>| +
|-
|<tex>9</tex>
|<tex> xyz</tex>
|<tex>+</tex>
|}
{|borderclass="wikitable" style="1background-color:#FFF; text-align:center;"|№№ !№ склеивания|!Результат
|-
| <tex>3 - 9</tex>
|<tex>xz</tex>
|-
| <tex>4 - 5</tex>
|<tex>xz</tex>
|-
| <tex>6 - 9|<tex>xy</tex>|-| 7 - 8|<tex>xy</tex>
|-
|<tex>7-8</tex>
|<tex> xy</tex>
|}
На данном этапе получаем простые импликанты элементы сокращённой ДНФ <tex>\neg x \land \neg z \land \neg w</tex> и <tex>y \land \neg z \land \neg w</tex>
{|borderclass="1wikitable" style="background-color:#FFF;text-align:center;"|!№|!Элементарная конъюнкция|!Поглощение
|-
| <tex>1</tex>
|<tex>xz</tex>
|
|-
| <tex>2</tex>
|<tex>xy</tex>
|
|}
Обе из элементарных конъюнкций элементарные конъюнкции на данном шаге являются простыми импликантамиэлементами сокращённой ДНФ.
В результате выполнения алгоритма мы получаем следующую сокращённую ДНФ: <tex>(\neg x \land \neg z \land \neg w) \lor (y \land \neg z \land \neg w) \lor (x \land z) \lor (x \land y) </tex>
Переход от сокращённой формы к минимальной:
*Единицы ДНФ, покрываемые элементарными конъюнкциями элементами <tex>Ax</tex> или <tex>A \neg x</tex> обозначаются "+". КонъюнктыПары <tex>Ax</tex> и <tex>A \neg x</tex>, попадающие в ядро помечаются "*".*Единицы функции, которые покрываются только каким-то одним конъюнктом из системы простых импликантэлементов сокращённой ДНФ, помечаются “>”.*Единицы функции, покрываемые ядром, но не покрываемые только каким-то одним конъюнктом из системы простых импликант, элементов сокращённой ДНФ помечаются “>>”.
{|borderclass="1wikitable" style="background-color:#FFF; text-align:center;"
|
|-
|
|
|
|-
|
| <tex>+</tex>
|
|
| <tex>+</tex>
|
|
|
|-
|
|
|style="background-color:#F4A460FF7F50;"| <tex>+</tex>|style="background-color:#F4A460FF7F50;"| <tex>+</tex>
|
|
| <tex>+</tex>| <tex>+</tex>
|-
|
|
|
|
| <tex>+</tex>|style="background-color:#F4A460FF7F50;"| <tex>+</tex>| <tex>+</tex>| <tex>+|-</tex>
|}
На основе этой таблицы получим ядро <tex>(\neg x \land \neg z \land \neg w) \lor (x \land z) \lor (x \land y) </tex>, которое является также и минимальной ДНФ.
==См. также==
* [[ДНФ]]
* [[КНФ]]
==СсылкиИсточники информации==
<references/>
*[http://ru.wikipedia.org/wiki/%D0%9C%D0%B8%D0%BD%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%BB%D0%BE%D0%B3%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D1%85_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B9_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%BC_%D0%9A%D1%83%D0%B0%D0%B9%D0%BD%D0%B0 Минимизация логических функций методом Куайна — Википедия]
*[http://matrixcalc.org/pf1.htmlМетод Квайна]
*[http://ru.wikipedia.org/wiki/%D0%9A%D0%B0%D1%80%D1%82%D0%B0_%D0%9A%D0%B0%D1%80%D0%BD%D0%BE Карта Карно — Википедия]
*[http://vuz.exponenta.ru/PDF/book/kv.htmlМинимизация булевых функций в классе ДНФ]*[http://tablica-istinnosti.ru/minimizatsiya-dnf-metodom-kvayna.htmlМинимизация ДНФ методом Квайна]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика ]]
[[Категория: Булевы функции ]]
