105
правок
Изменения
м
}}
<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> |<tex>1</tex> |- !style="background-color:#E0FFFF;" |<tex> \neg {y}</tex> !style="background-color:#FFF5EE;" |<tex>x</tex> | | |<tex>1</tex> |<tex>1</tex> |}<br>
<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>(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>
Теперь покрываем прямоугольниками (длины сторон которых {{---}} степени двойки (<tex>1, 2, 4</tex>)) те ячейки карт Карно, которые содержат в себе единицу (на каждом ходу мы выбираем такой прямоугольник, чтобы он покрывал наибольшее количество ещё не покрытых клеток) до тех пор, пока не покроем все такие ячейки.
Для карт Карно на примере это выглядело бы так:
|}
После этого записываем каждый прямоугольник в виде конъюнкта, в котором будут указаны только те переменные, которые одинаковы для всех ячеек этого прямоугольника.
*Операция попарного неполного склеивания:
:<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>)
*В результате получилось множество элементарных конъюнкций, разделяемых на два подмножества (по длине):
Функция от четырёх аргументов задана следующей таблицей:
{|borderclass="1wikitable" style="background-color:#FFF; text-align:center"|!Набор <tex>xyzw</tex>
|<tex>0000</tex>
|<tex>0001</tex>
|<tex>1111</tex>
|-
|<tex>1</tex>
|<tex>0</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>| <tex>+</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>|<tex>x \neg yz</tex>|-|<tex> 3 - 7</tex>|<tex>\neg x \neg z\neg w</tex>
|-
|<tex> 4 3- 87</tex>|<tex> xzw\neg x \neg z\neg w</tex>
|-
|<tex> 5 4- 68</tex>|<tex>xy\neg z xzw</tex>
|-
|<tex> 5 - 76</tex>|<tex>xy \neg wz</tex>
|-
|<tex> 6 5- 87</tex>|<tex>xyw xy \neg w</tex>
|-
|<tex> 7 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>| +|-|<tex> 9</tex>|<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>|<tex>xy</tex>|-|<tex> 7 - 8</tex>|<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>
|
|}
Обе элементарные конъюнкции на данном шаге являются элементами сокращённой ДНФ.
*Единицы функции, покрываемые ядром, но не покрываемые только каким-то одним конъюнктом из системы элементов сокращённой ДНФ помечаются “>>”.
{|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 Минимизация логических функций методом Куайна — Википедия]
[[Категория: Комбинаторика ]]
[[Категория: Булевы функции ]]
