Изменения

'''Сокращенная ДНФ: ''' (англ. ''reduced disjunctive normal form'') {{---}} форма записи функции, обладающая следующими свойствами: *Любые любые два слагаемых различаются как минимум в двух позициях, *Ни ни один из конъюнктов не содержится в другом. }}'''Например, :'''<tex>(x \land y)</tex> содержится в <tex>(x \land y \land z)</tex>.

'''Минимальная ДНФ ''' (англ. ''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>

|*'''Описание алгоритма''' |'''Пример''' |- |Если у нас конъюнкт, переменные в котором равны соответствующим координатам вершины, то в эту вершину мы помещаем закрашенный чёрным кружок. |*dершине Вершине с координатами <tex>(0,1,1) </tex>соответствует конъюнкт <tex>(\neg X \wedge Y \wedge Z)</tex>, он равен единице при <tex>X=0, Y=1</tex> и <tex>Z=1</tex>) |}-* |В противном случае мы помещаем в вершину закрашенный белый кружок.

Например, для |Для такой ДНФ: <tex>(X \wedge \neg Y \wedge Z) \vee </tex> <tex> (X \wedge Y \wedge Z) \vee </tex><tex> (\neg X \wedge Y \wedge Z) \vee </tex><tex> (\neg X \wedge Y \wedge \neg Z) \vee </tex><tex>( X \wedge Y \wedge \neg Z)</tex> мы получим следующий гиперкуб (см. рисунок) |- |Далее обработка гиперкуба идёт следующим образом:

* |- |Если в данном гиперкубе есть грань, все вершины на которой закрашены чёрным, то мы можем записать её в качестве конъюнкта, где будет только переменная с неизменяющейся соответствующей ей координатой, например, грань. |Грань, на которой лежат закрашенные вершины <tex>(0,1,1), (0,1,0), (1,1,0)</tex> и <tex>(1,1,1)</tex> мы можем записать как конъюнкт <tex>Y</tex>.* |-  |Теперь мы смотрим, остались ли на рёбрах куба закрашенные и не отмеченные нами в ДНФ вершины. Если — да, то рёбра с такими вершинами мы можем записать в качестве конъюнкта, где будут только переменные с неизменяющимися соответствующим им координатами, например, ребро |Ребро, соединяющее закрашенные вершины (<tex>(0,1,1)</tex> и <tex>(1,1,1)</tex> мы можем записать как конъюнкт <tex>(Y \wedge Z)</tex>.* |- |И если после такой обработки у нас остались свободные вершины, мы просто переписываем координаты каждой такой вершины в отдельный конъюнкт, равный <tex>1</tex>. Например, вершину |Вершину <tex>(1,0,1)</tex> мы бы переписали как конъюнкт <tex>(X \wedge \neg Y \wedge Z)</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> | | | | |} Теперь для каждого конъюнкта мы помечаем соответствующую ему ячейку таблицы.  Например, ДНФ

<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>{| 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> | |<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>После этого записываем каждый прямоугольник в виде конъюнкта, в котором будут указаны только те переменные, которые одинаковы для всех ячеек этого прямоугольника. То есть, в этом примере получаем:&nbsp;<tex>(\neg Z \wedge \neg X) \vee (\neg W \wedge \neg Y)</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> 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>

{|borderclass="1wikitable" style="background-color:#FFF; text-align:center;"|!№|Эл. !Элементарная конъюнкция|!Поглощение

|<tex>1</tex>

| <tex>+</tex>

|<tex>2</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>| +

 {|borderclass="wikitable" style="1background-color:#FFF; text-align:center;"|№№ скл.!№ склеивания|!Результат

| <tex>1 - 2</tex>

| <tex>2 - 5</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>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>| +|-| 4|<tex>\neg x \neg z\neg w+</tex>| +

| 5<tex>4</tex>|<tex> xzw\neg x\neg z\neg w</tex>| <tex>+</tex>

| 6<tex>5</tex>|<tex>xy\neg z xzw</tex>| <tex>+</tex>

| 7<tex>6</tex>|<tex> xy \neg wz</tex>| <tex>+</tex>

| 8<tex>7</tex>|<tex>xywxy\neg w</tex>| <tex>+</tex>

| 9<tex>8</tex>|<tex>xyzxyw</tex>| <tex>+</tex>

 {|borderclass="wikitable" style="1background-color:#FFF; text-align:center;"|№№ скл.!№ склеивания|!Результат

| <tex>3 - 9</tex>

| <tex>4 - 5</tex>

| <tex>6 - 9|<tex>xy</tex>|-| 7 - 8|<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>2</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>\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>+</tex>

| <tex>+</tex>

|!<tex>xz^*</tex>*

|style="background-color:#F4A460FF7F50;"| <tex>+</tex>|style="background-color:#F4A460FF7F50;"| <tex>+</tex>

| <tex>+</tex>| <tex>+</tex>

|!<tex>xy^*</tex>*

| <tex>+</tex>|style="background-color:#F4A460FF7F50;"| <tex>+</tex>| <tex>+</tex>| <tex>+|-</tex>

     ==СсылкиИсточники информации==

*[http://matrixcalc.org/pf1.htmlМетод Квайна]

*[http://vuz.exponenta.ru/PDF/book/kv.htmlМинимизация булевых функций в классе ДНФ]*[http://tablica-istinnosti.ru/minimizatsiya-dnf-metodom-kvayna.htmlМинимизация ДНФ методом Квайна]