Редактирование: Сокращённая и минимальная ДНФ

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 
== Сокращенная ДНФ ==
 
== Сокращенная ДНФ ==
 
+
Запишем [[Определение булевой функции|функцию]] <tex>\left<x, y, z\right> </tex> (медиана) в [[СДНФ]]:
{{Определение
 
|definition =
 
'''Сокращенная ДНФ''' (англ. ''reduced disjunctive normal form'') {{---}} форма записи функции, обладающая следующими свойствами:
 
* любые два слагаемых различаются как минимум в двух позициях,
 
* ни один из конъюнктов не содержится в другом.
 
}}
 
'''Например:'''
 
<tex>(x \land y)</tex> содержится в  <tex>(x \land y \land z)</tex>.
 
 
 
Функцию можно записать с помощью сокращенной ДНФ не единственным способом.
 
 
 
Запишем [[Определение булевой функции|функцию]] <tex>\left<x, y, z\right> </tex> (медиана) в виде [[СДНФ|совершенной ДНФ]]:
 
 
<tex>(x \land y \land z) \lor (x \land y \land \lnot z) \lor (x \land \lnot y \land z) \lor (\neg x \land y \land z)</tex>.
 
<tex>(x \land y \land z) \lor (x \land y \land \lnot z) \lor (x \land \lnot y \land z) \lor (\neg x \land y \land z)</tex>.
 
Известно, что это выражение равносильно следующему:
 
Известно, что это выражение равносильно следующему:
Строка 18: Строка 6:
 
Вынесем в каждой скобке общий конъюнкт (например, в первой <tex>(x \land y \land z) \lor (x \land y \land \lnot z)=(x \land y) \lor (z \land \lnot z)</tex>.
 
Вынесем в каждой скобке общий конъюнкт (например, в первой <tex>(x \land y \land z) \lor (x \land y \land \lnot z)=(x \land y) \lor (z \land \lnot z)</tex>.
 
Так как <tex>z \land \lnot z = 0</tex>, то такой конъюнкт не влияет на значение выражения, и его можно опустить.
 
Так как <tex>z \land \lnot z = 0</tex>, то такой конъюнкт не влияет на значение выражения, и его можно опустить.
Получим в итоге формулу <tex>(x \land y) \lor (y \land z) \lor (x \land z)</tex>.
+
Получим в итоге формулу <tex>(x \land y) \lor (y \land z) \lor (x \land z)</tex>.<br><br>
 +
{{Определение
 +
|definition =
 +
Сокращенная ДНФ: форма записи функции, обладающая следующими свойствами:
  
 +
#Никакие два слагаемых нельзя объединить по рассмотренному выше правилу.
 +
#Ни один из конъюнктов не содержится в другом. Например, <tex>(x \land y)</tex> содержится в  <tex>(x \land y \land z)</tex>.
 +
 +
}}
 +
Функцию можно записать с помощью сокращенной ДНФ не единственным способом.
 
== Минимальная ДНФ ==
 
== Минимальная ДНФ ==
 
{{Определение
 
{{Определение
 
|definition =
 
|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>(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>
  
 
== Минимизация ДНФ ==
 
== Минимизация ДНФ ==
Строка 33: Строка 29:
 
=== Визуализация гиперкубами ===
 
=== Визуализация гиперкубами ===
  
[[Файл:Гиперкуб.PNG||right]]
+
[[Файл:Гиперкуб.PNG||right|рис. 1]]
 
Этот способ работает при количестве переменных не больше трёх (в противном необходимо вводить четвёртое или следующие за ним измерения для представления фигур).
 
Этот способ работает при количестве переменных не больше трёх (в противном необходимо вводить четвёртое или следующие за ним измерения для представления фигур).
Сначала мы рисуем куб в системе отсчёта <tex>Oxyz</tex> (названия координатных осей соответствуют названиям переменных). Затем каждую вершину обрабатываем следующим образом:
+
Сначала мы рисуем куб в системе отсчёта Oxyz (названия координатных осей соответствуют названиям переменных). Затем каждую вершину обрабатываем следующим образом:
{| border="0"
+
*Если у нас конъюнкт, переменные в котором равны соответствующим координатам вершины (пример: вершине с координатами (0,1,1) соответствует конъюнкт <tex>(\neg X \wedge Y \wedge Z)</tex>, он равен единице при X=0, Y=1 и Z=1), то в эту вершину мы помещаем закрашенный чёрным кружок.
|'''Описание алгоритма'''
+
*В противном случае мы помещаем в вершину закрашенный белый кружок.
|'''Пример'''
 
|-
 
|Если у нас конъюнкт, переменные в котором равны соответствующим координатам вершины, то в эту вершину мы помещаем закрашенный чёрным кружок.
 
|Вершине с координатами <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>(X \wedge \neg Y \wedge Z) \vee (X \wedge Y \wedge Z) \vee (\neg X \wedge Y \wedge Z) \vee (\neg X \wedge Y \wedge \neg Z) \vee ( X \wedge Y \wedge \neg Z)</tex> мы получим следующий гиперкуб (рис. 1)
|-
+
Далее обработка гиперкуба идёт следующим образом:
|Далее обработка гиперкуба идёт следующим образом:
 
 
пока у нас есть незакрашенные вершины, мы выбираем грань, либо вершину, либо ребро, на которых больше всего закрашенных чёрным вершин и ещё не обработанных вершин.
 
пока у нас есть незакрашенные вершины, мы выбираем грань, либо вершину, либо ребро, на которых больше всего закрашенных чёрным вершин и ещё не обработанных вершин.
|-
+
*Если в данном гиперкубе есть грань, все вершины на которой закрашены чёрным, то мы можем записать её в качестве конъюнкта, где будет только переменная с неизменяющейся соответствующей ей координатой, например, грань, на которой лежат закрашенные вершины (0,1,1), (0,1,0), (1,1,0) и (1,1,1) мы можем записать как конъюнкт <tex>Y</tex>.
|Если в данном гиперкубе есть грань, все вершины на которой закрашены чёрным, то мы можем записать её в качестве конъюнкта, где будет только переменная с неизменяющейся соответствующей ей координатой.
+
*Теперь мы смотрим, остались ли на рёбрах куба закрашенные и не отмеченные нами в ДНФ вершины. Если — да, то рёбра с такими вершинами мы можем записать в качестве конъюнкта, где будут только переменные с неизменяющимися соответствующим им координатами, например, ребро, соединяющее закрашенные вершины (0,1,1) и (1,1,1) мы можем записать как конъюнкт <tex>(Y \wedge Z)</tex>.
|Грань, на которой лежат закрашенные вершины <tex>(0,1,1), (0,1,0), (1,1,0)</tex> и <tex>(1,1,1)</tex> мы можем записать как конъюнкт <tex>Y</tex>.
+
*И если после такой обработки у нас остались свободные вершины, мы просто переписываем координаты каждой такой вершины в отдельный конъюнкт, равный 1. Например, вершину (1,0,1) мы бы переписали как конъюнкт <tex>(X \wedge \neg Y \wedge Z)</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>(Y) \vee (X \wedge Z)</tex>.
 
В итоге нашу изначальную ДНФ можно записать как <tex>(Y) \vee (X \wedge Z)</tex>.
Строка 65: Строка 46:
 
=== Карты Карно ===
 
=== Карты Карно ===
  
Построим следующую таблицу <tex>n \times n</tex>, где <tex>n</tex> {{---}} число переменных:
+
Построим следующую таблицу n*n, где n {{---}} количество переменных:
{| class="wikitable" style="background-color:#FFF; text-align:center"
+
{| border="1"
| colspan="2" rowspan="2" |
+
|
! style="background-color:#F0F8FF;" |<tex>w</tex>
+
|
! style="background-color:#F0F8FF;" |<tex>w</tex>
+
!<tex> w </tex>
! style="background-color:#F0F8FF;" |<tex>\neg{w}</tex>
+
!<tex> w </tex>
! style="background-color:#F0F8FF;" |<tex>\neg{w}</tex>
+
!<tex> \neg w</tex>
|-
+
!<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>
+
!<tex>z</tex>
|-
+
!<tex> \neg z</tex>
! style="background-color:#E0FFFF;" |<tex>y</tex>
+
!<tex> \neg z</tex>
! style="background-color:#FFF5EE;" |<tex>x</tex>
+
!<tex>z</tex>
|
+
|-
|
+
!<tex>y</tex>
|
+
!<tex>x</tex>
|
+
|
|-
+
|
! style="background-color:#E0FFFF;" |<tex>y</tex>
+
|
! style="background-color:#FFF5EE;" |<tex>\neg{x}</tex>
+
|
|
+
|-
|
+
!<tex>y</tex>
|
+
!<tex> \neg x</tex>
|
+
|
|-
+
|
! style="background-color:#E0FFFF;" |<tex>\neg{y}</tex>
+
|
! style="background-color:#FFF5EE;" |<tex>\neg{x}</tex>
+
|
|
+
|-
|
+
!<tex> \neg y</tex>
|
+
!<tex> \neg x</tex>
|
+
|
|-
+
|
! style="background-color:#E0FFFF;" |<tex>\neg{y}</tex>
+
|
! style="background-color:#FFF5EE;" |<tex>x</tex>
+
|
|
+
|-
|
+
!<tex> \neg y</tex>
|
+
!<tex>x</tex>
|
+
|
|}
+
|
 
+
|
Теперь для каждого конъюнкта мы помечаем соответствующую ему ячейку таблицы.  
+
|
 
+
|}
Например, ДНФ
+
Теперь для каждого конъюнкта мы помечаем соответствующую ему ячейку таблицы. Например, ДНФ
 
<br>
 
<br>
 
<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 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 (X \wedge \neg Y \wedge Z \wedge \neg W)</tex>
+
<tex>(\neg X \wedge Y \wedge Z \wedge W) \vee (\neg X \wedge Y \wedge \neg Z \wedge W) \vee (\neg X \wedge Y \wedge \neg Z \wedge \neg W) \vee (\neg X \wedge Y \wedge Z \wedge \neg W) \vee (X \wedge \neg Y \wedge Z \wedge W) \vee (X \wedge \neg Y \wedge \neg Z \wedge W) \vee (\neg X \wedge \neg Y \wedge \neg Z \wedge \neg W)</tex>
 
<br>
 
<br>
 
<br>
 
<br>
 
будет выглядеть на картах Карно так:
 
будет выглядеть на картах Карно так:
 
<br>
 
<br>
{| class="wikitable" style="background-color:#FFF; text-align:center"
+
<br>
| colspan="2" rowspan="2" |
+
{| border="1"
! style="background-color:#F0F8FF;" |<tex>w</tex>
+
|
! style="background-color:#F0F8FF;" |<tex>w</tex>
+
|
! style="background-color:#F0F8FF;" |<tex>\neg{w}</tex>
+
!<tex> w </tex>
! style="background-color:#F0F8FF;" |<tex>\neg{w}</tex>
+
!<tex> w </tex>
|-
+
!<tex> \neg w</tex>
! style="background-color:#F8F8FF;" |<tex>z</tex>
+
!<tex> \neg w</tex>
! style="background-color:#F8F8FF;" |<tex>\neg{z}</tex>
+
|-
! style="background-color:#F8F8FF;" |<tex>\neg{z}</tex>
+
|
! style="background-color:#F8F8FF;" |<tex>z</tex>
+
|
|-
+
!<tex>z</tex>
! style="background-color:#E0FFFF;" |<tex>y</tex>
+
!<tex> \neg z</tex>
! style="background-color:#FFF5EE;" |<tex>x</tex>
+
!<tex> \neg z</tex>
|
+
!<tex>z</tex>
|
+
|-
|
+
!<tex>y</tex>
|
+
!<tex>x</tex>
|-
+
|
! style="background-color:#E0FFFF;" |<tex>y</tex>
+
|
! style="background-color:#FFF5EE;" |<tex>\neg{x}</tex>
+
|
|
+
|
|<tex>1</tex>
+
|-
|<tex>1</tex>
+
!<tex>y</tex>
|
+
!<tex> \neg x</tex>
|-
+
|
! style="background-color:#E0FFFF;" |<tex>\neg{y}</tex>
+
|1
! style="background-color:#FFF5EE;" |<tex>\neg{x}</tex>
+
|1
|
+
|
|<tex>1</tex>
+
|-
|<tex>1</tex>
+
!<tex> \neg y</tex>
|
+
!<tex> \neg x</tex>
|-
+
|
! style="background-color:#E0FFFF;" |<tex>\neg{y}</tex>
+
|1
! style="background-color:#FFF5EE;" |<tex>x</tex>
+
|1
|
+
|1
|
+
|-
|<tex>1</tex>
+
!<tex> \neg y</tex>
|<tex>1</tex>
+
!<tex>x</tex>
 +
|
 +
|
 +
|1
 +
|1
 +
|}
 +
<br>
 +
*Теперь мы покрываем прямоугольниками (длины сторон которых {{---}} степени двойки (1, 2, 4)) те ячейки карт Карно, которые содержат в себе единицу (на каждом ходу мы выбираем такой прямоугольник, чтобы он покрывал наибольшее количество ещё не покрытых клеток) до тех пор, пока не покроем все такие ячейки (для карт Карно на примере это выглядело бы так):
 +
<br>
 +
{| border="1"
 +
|
 +
|
 +
!<tex> w </tex>
 +
!<tex> w </tex>
 +
!<tex> \neg w</tex>
 +
!<tex> \neg w</tex>
 +
|-
 +
|
 +
|
 +
!<tex> z </tex>  
 +
!<tex> \neg z</tex>
 +
!<tex> \neg z</tex>
 +
!<tex> z </tex>  
 +
|-
 +
!<tex> y </tex>
 +
!<tex> x </tex>  
 +
|
 +
|
 +
|
 +
|
 +
|-
 +
!<tex> y </tex>
 +
!<tex> \neg x</tex>
 +
|
 +
|style="background:#F4A460"|1
 +
|style="background:#F4A460"|1
 +
|
 +
|-
 +
!<tex> \neg y</tex>
 +
!<tex> \neg x</tex>
 +
|
 +
|style="background:#F4A460"|1
 +
|style="background:#B4D19A"|1
 +
|style="background:#7FFFD4"|1
 +
|-
 +
!<tex> \neg y</tex>
 +
!<tex> x </tex>  
 +
|
 +
|
 +
|style="background:#7FFFD4"|1
 +
|style="background:#7FFFD4"|1
 
|}
 
|}
 
+
<br>
Теперь покрываем прямоугольниками (длины сторон которых {{---}} степени двойки (<tex>1, 2, 4</tex>)) те ячейки карт Карно, которые содержат в себе единицу (на каждом ходу мы выбираем такой прямоугольник, чтобы он покрывал наибольшее количество ещё не покрытых клеток) до тех пор, пока не покроем все такие ячейки.
+
*После этого записываем каждый прямоугольник в виде конъюнкта, в котором будут указаны только те переменные, которые одинаковы для всех ячеек этого прямоугольника:&nbsp;<tex>(\neg Z \wedge \neg X) \vee (\neg W \wedge \neg Y)</tex>
 
 
Для карт Карно на примере это выглядело бы так:
 
 
 
{| class="wikitable" 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:#FFA07A;" |<tex>1</tex>
 
| style="background-color:#FFA07A;" |<tex>1</tex>
 
|
 
|-
 
! style="background-color:#E0FFFF;" |<tex>\neg{y}</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:#FFF5EE;" |<tex>x</tex>
 
|
 
|
 
| style="background-color:#00FFFF;" |<tex>1</tex>
 
| style="background-color:#00FFFF;" |<tex>1</tex>
 
|}
 
 
 
После этого записываем каждый прямоугольник в виде конъюнкта, в котором будут указаны только те переменные, которые одинаковы для всех ячеек этого прямоугольника.
 
 
 
То есть, в этом примере получаем:&nbsp;<tex>(\neg Z \wedge \neg X) \vee (\neg W \wedge \neg Y)</tex>
 
  
 
===Метод Квайна===
 
===Метод Квайна===
Этот метод основан на применении двух основных операций:
+
Этот метод основан на применении двух основных соотношений:
 
*Операция попарного неполного склеивания:
 
*Операция попарного неполного склеивания:
 
:<tex>A x \lor A \neg x = A x \lor A \neg x \lor A</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 \tilde x \lor A = A </tex>
:(где <tex>A</tex> {{---}} некоторая элементарная конъюнкция, то есть конъюнкт, в который каждая из переменных входит не более одного раза)
+
:(где A {{---}} любое элементарное произведение, то есть конъюнкт, в который каждая из переменных входит не более одного раза.)
'''Например:'''
 
 
 
Пусть <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>Ax</tex> или  <tex>A \neg x</tex>
*Выполняются все возможные операции неполного попарного склеивания для элементарных конъюнкций длины <tex> n</tex> (где <tex> n</tex> {{---}} число аргументов).
+
*Выполняются все возможные операции неполного попарного склеивания для элементарных конъюнкций длины n (где n {{---}} количество аргументов).
*Выполняются все возможные операции элементарного поглощения для элементарных конъюнкций длины <tex> n-1</tex> (общая часть "<tex>p</tex>" имеет длину <tex> n-1</tex>)
+
*Выполняются все возможные операции элементарного поглощения для элементарных конъюнкций длины n-1 (общая часть "p" имеет длину n-1)
*В результате получилось множество элементарных конъюнкций, разделяемых на два подмножества (по длине):
+
*В результате получилось множество элементарных конъюнкций, разделяемых на два подмножества(по длине):
**подмножество элементарных конъюнкций длины <tex> n</tex> (оставшиеся)
+
**подмножество элементарных конъюнкций длины n (оставшиеся)
**подмножество элементарных конъюнкций длины <tex> n-1</tex>
+
**подмножество элементарных конъюнкций длины n-1
*Если множество элементарных конъюнкций длины <tex> n-1</tex> не пусто, то заново выполняются операции неполного попарного склеивания и элементарного поглощения для конъюнкций длины <tex> n-1</tex> и так далее.
+
*Если множество элементарных конъюнкций длины n-1 не пусто, то выполняются шаги со второго для конъюнкций длины n-1 и т.д.
 
Алгоритм завершается, когда подмножество является пустым, либо нельзя выполнить ни одной операции неполного попарного склеивания.
 
Алгоритм завершается, когда подмножество является пустым, либо нельзя выполнить ни одной операции неполного попарного склеивания.
После выполнения этого алгоритма будет получена сокращенная (но еще не минимальная) форма.
+
После выполнения алгоритма будет получена сокращенная минимальная форма
 
 
Переход от сокращённой формы к минимальной осуществляется с помощью специальной таблицы.
 
Члены СДНФ заданной функции вписываются в столбцы, а в строки — члены сокращённой формы. Отмечаются столбцы членов СДНФ, которые поглощаются отдельными элементами сокращённой формы.
 
 
 
Члены сокращённой формы, не подлежащие исключению, образуют ядро. Такие члены определяются по вышеуказанной матрице. Для каждой из них имеется хотя бы один столбец, перекрываемый только этим членом.
 
 
 
Для получения минимальной формы достаточно выбрать из членов сокращённой формы, не входящих в ядро, такое минимальное их число с минимальным количеством букв в каждом из этих членов, которое обеспечит перекрытие всех столбцов, не перекрытых членами ядра.
 
 
 
====Пример====
 
 
 
Функция от четырёх аргументов задана следующей таблицей:
 
{| class="wikitable" 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</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>
 
|}
 
  
Проведём операции неполного склеивания и поглощения:
+
Импликанты, не подлежащие исключению, образуют ядро. Такие импликанты определяются по вышеуказанной матрице. Для каждой из них имеется хотя бы один столбец, перекрываемый только этой импликантой.
 +
Для получения минимальной формы достаточно выбрать из импликантов, не входящих в ядро, такое минимальное их число с минимальным количеством букв в каждом из этих импликант, которое обеспечит перекрытие всех столбцов, не перекрытых членами ядра.
  
{| class="wikitable" 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>
 
|}
 
 
 
{| class="wikitable" style="background-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>Ax</tex> или  <tex>A \neg x</tex> участвовали в операциях попарного неполного склеивания и были поглощены своими собственными частями. Поэтому элементы сокращённой ДНФ на этом шаге не получены.
 
 
 
{| class="wikitable" 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>+</tex>
 
|-
 
|<tex>9</tex>
 
|<tex> xyz</tex>
 
|<tex>+</tex>
 
|}
 
 
 
{| class="wikitable" style="background-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>\neg x \land \neg z \land \neg w</tex> и <tex>y \land \neg z \land \neg w</tex>
 
 
 
{| class="wikitable" 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>, попадающие в ядро помечаются "*".
 
*Единицы функции, которые покрываются только каким-то одним конъюнктом из системы элементов сокращённой ДНФ, помечаются “>”.
 
*Единицы функции, покрываемые ядром, но не покрываемые только каким-то одним конъюнктом из системы элементов сокращённой ДНФ помечаются “>>”.
 
 
 
{| class="wikitable" 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:#FF7F50;" | <tex>+</tex>
 
|<tex>+</tex>
 
|
 
|
 
|
 
|
 
|
 
|
 
|-
 
!<tex>y\neg z\neg w</tex>
 
|
 
|<tex>+</tex>
 
|
 
|
 
|<tex>+</tex>
 
|
 
|
 
|
 
|-
 
!<tex>xz^*</tex>
 
|
 
|
 
| style="background-color:#FF7F50;" | <tex>+</tex>
 
| style="background-color:#FF7F50;" | <tex>+</tex>
 
|
 
|
 
|<tex>+</tex>
 
|<tex>+</tex>
 
|-
 
!<tex>xy^*</tex>
 
|
 
|
 
|
 
|
 
|<tex>+</tex>
 
| style="background-color:#FF7F50;" | <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/>
 
<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://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://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://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://vuz.exponenta.ru/PDF/book/kv.html
*[http://tablica-istinnosti.ru/minimizatsiya-dnf-metodom-kvayna.html Минимизация ДНФ методом Квайна]
+
*http://tablica-istinnosti.ru/minimizatsiya-dnf-metodom-kvayna.html
 
 
[[Категория: Дискретная математика и алгоритмы]]
 
 
 
[[Категория: Комбинаторика ]]
 
 
 
[[Категория: Булевы функции ]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: