105
правок
Изменения
м
|-
|!<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'') {{---}} форма записи функции, обладающая следующими свойствами: * любые два слагаемых различаются как минимум в двух позициях, * ни один из конъюнктов не содержится в другом.
}}
'''Например:'''
! style="background-color:#FFF5EE;" |<tex>\neg{x}</tex>
|
|<tex>1</tex>|<tex>1</tex>
|
|-
! style="background-color:#FFF5EE;" |<tex>\neg{x}</tex>
|
|<tex>1</tex>|<tex>1</tex>
|
|-
|
|
|<tex>1</tex>|<tex>1</tex>
|}
! style="background-color:#FFF5EE;" |<tex>\neg{x}</tex>
|
| style="background-color:#FFA07A;" |<tex>1</tex>| style="background-color:#FFA07A;" |<tex>1</tex>
|
|-
! style="background-color:#FFF5EE;" |<tex>\neg{x}</tex>
|
| style="background-color:#FFA07A;" |<tex>1</tex>| style="background-color:#80D0BD;" |<tex>1</tex>| style="background-color:#00FFFF;" |<tex>1</tex>
|-
! style="background-color:#E0FFFF;" |<tex>\neg{y}</tex>
|
|
| style="background-color:#00FFFF;" |<tex>1</tex>| style="background-color:#00FFFF;" |<tex>1</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>
Метод состоит в последовательном выполнении всех возможных склеиваний и затем всех поглощений частей СДНФ пока это может быть осуществимо.
====Описание алгоритма====
Проведём операции неполного склеивания и поглощения:
{|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 - 8</tex>|<tex> xzw</tex>
|-
|<tex> 5 - 6</tex>|<tex>xy\neg z</tex>
|-
|<tex> 5 - 7</tex>|<tex> xy \neg w</tex>
|-
|<tex> 6 - 8</tex>|<tex>xyw</tex>|-|<tex> 7 - 8</tex>|<tex>xyz</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>
|}
