315
правок
Изменения
Новая страница: «Известны два способа минимизации дизъюнктивных нормальных форм: == Визуализация гиперкуб…»
Известны два способа минимизации дизъюнктивных нормальных форм:
== Визуализация гиперкубами ==
Этот способ работает при количестве переменных не больше трёх (в противном случае нам придётся вводить четвёртое и следующие за ним измерения для представления фигур).
Сначала мы рисуем куб в системе отсчёта Oxyz (названия координатных осей должны соответствовать названиям переменных). Затем каждую вершину обрабатываем следующим образом:
*Если у нас конъюнкт, переменные в котором равны соответствующим координатам вершины (пример: вершине с координатами (0,1,1) соответствует конъюнкт <math>(\neg X \and Y \and Z)</math>, он равен единице при X=0, Y=1 и Z=1), то в эту вершину мы помещаем закрашенный чёрным кружок.
*В противном случае мы помещаем в вершину закрашенный белый кружок.
Например, для такой ДНФ: <math>(X \and \neg Y \and Z) \or (X \and Y \and Z) \or (\neg X \and Y \and Z) \or (\neg X \and Y \and \neg Z) \or ( X \and Y \and \neg Z)</math> мы получим такой гиперкуб: [[Файл:Гиперкуб.PNG|Гиперкуб, полученый нами.]]
Далее обработка гиперкуба идёт следующим образом:
*Если в данном гиперкубе есть грань, все вершины на которой закрашены чёрным, то мы можем записать её в качестве конъюнкта, где будет только переменная с неизменяющейся соответствующей ей координатой, например, грань, на которой лежат закрашенные вершины (0,1,1), (0,1,0), (1,1,0) и (1,1,1) мы можем записать как конъюнкт <math>Y</math>.
*Если в данном гиперкубе есть ребро, все вершины на котором закрашены чёрным, то мы можем записать его в качестве конъюнкта, где будут только переменные с неизменяющимися соответствующим им координатами, например, ребро, соединяющее закрашенные вершины (0,1,1) и (1,1,1) мы можем записать как конъюнкт <math>(Y \and Z)</math>.
В итоге нашу изначальную ДНФ можно записать как <math>(Y) \or (X \and \neg Y \and Z)</math>.
== Визуализация гиперкубами ==
Этот способ работает при количестве переменных не больше трёх (в противном случае нам придётся вводить четвёртое и следующие за ним измерения для представления фигур).
Сначала мы рисуем куб в системе отсчёта Oxyz (названия координатных осей должны соответствовать названиям переменных). Затем каждую вершину обрабатываем следующим образом:
*Если у нас конъюнкт, переменные в котором равны соответствующим координатам вершины (пример: вершине с координатами (0,1,1) соответствует конъюнкт <math>(\neg X \and Y \and Z)</math>, он равен единице при X=0, Y=1 и Z=1), то в эту вершину мы помещаем закрашенный чёрным кружок.
*В противном случае мы помещаем в вершину закрашенный белый кружок.
Например, для такой ДНФ: <math>(X \and \neg Y \and Z) \or (X \and Y \and Z) \or (\neg X \and Y \and Z) \or (\neg X \and Y \and \neg Z) \or ( X \and Y \and \neg Z)</math> мы получим такой гиперкуб: [[Файл:Гиперкуб.PNG|Гиперкуб, полученый нами.]]
Далее обработка гиперкуба идёт следующим образом:
*Если в данном гиперкубе есть грань, все вершины на которой закрашены чёрным, то мы можем записать её в качестве конъюнкта, где будет только переменная с неизменяющейся соответствующей ей координатой, например, грань, на которой лежат закрашенные вершины (0,1,1), (0,1,0), (1,1,0) и (1,1,1) мы можем записать как конъюнкт <math>Y</math>.
*Если в данном гиперкубе есть ребро, все вершины на котором закрашены чёрным, то мы можем записать его в качестве конъюнкта, где будут только переменные с неизменяющимися соответствующим им координатами, например, ребро, соединяющее закрашенные вершины (0,1,1) и (1,1,1) мы можем записать как конъюнкт <math>(Y \and Z)</math>.
В итоге нашу изначальную ДНФ можно записать как <math>(Y) \or (X \and \neg Y \and Z)</math>.
