195
правок
Изменения
м
→Метод Квайна
*Операция элементарного поглощения
:<tex>A \tilde x \lor A = A </tex>
:(где <tex>A </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> и так далее.
Алгоритм завершается, когда подмножество является пустым, либо нельзя выполнить ни одной операции неполного попарного склеивания.
После выполнения этого алгоритма будет получена сокращенная (но еще не минимальная) форма.
{|border="1"
|Набор <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</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>
|-
|}
|Поглощение
|-
|<tex>1</tex>
|<tex>\neg x\neg y\neg z\neg w</tex>
| +
|-
|<tex>2</tex>
|<tex>\neg xy\neg z\neg w</tex>
| +
|-
|<tex>3</tex>
|<tex>x\neg yz\neg w</tex>
| +
|-
|<tex>4</tex>
|<tex>x\neg y zw</tex>
| +
|-
|<tex>5</tex>
|<tex>xy\neg z\neg w</tex>
| +
|-
|<tex>6</tex>
|<tex>xy\neg zw</tex>
| +
|-
|<tex>7</tex>
|<tex>xyz\neg w</tex>
| +
|-
|<tex>8</tex>
|<tex>xyzw</tex>
| +
{|border="1"
|№№ № склеивания
|Результат
|-
| <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> 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> 4</tex>
|<tex>\neg x \neg z\neg w</tex>
| +
|-
| <tex> 5</tex>
|<tex> xzw</tex>
| +
|-
| <tex> 6</tex>
|<tex>xy\neg z</tex>
| +
|-
| <tex> 7</tex>
|<tex>xy \neg w</tex>
| +
|-
| <tex> 8</tex>
|<tex>xyw</tex>
| +
|-
| <tex> 9</tex>
|<tex>xyz</tex>
| +
{|border="1"
|№№ № склеивания
|Результат
|-
| <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> 1</tex>
|<tex>xz</tex>
|
|-
| <tex> 2</tex>
|<tex>xy</tex>
|
На основе этой таблицы получим ядро <tex>(\neg x \land \neg z \land \neg w) \lor (x \land z) \lor (x \land y) </tex>, которое является также и минимальной ДНФ.
==Ссылки==
