Изменения

Запишем известную [[Определение булевой функции|функцию]] <tex>\left<x, y, z\right> </tex> (медиана) в [[СДНФ]]:

#Ни один из конъюнктов не является подмножеством другогосодержится в другом. Например, <tex>(x \land y)</tex> — подмножество содержится в <tex>(x \land y \land z)</tex>.

Минимальная ДНФ {{---}} та такая сокращенная ДНФ, в которой содержится минимальное количество вхождений переменных.

Сначала мы рисуем куб в системе отсчёта Oxyz (названия координатных осей должны соответствовать соответствуют названиям переменных). Затем каждую вершину обрабатываем следующим образом:

Например, для такой ДНФ: <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> мы получим такой следующий гиперкуб:<br><br> [[Файл:Гиперкуб.PNG|Гиперкуб, полученый нами(рис.]]1)Далее обработка гиперкуба идёт следующим образом:<br>Пока пока у нас есть незакрашенные вершины, мы выбираем грань, либо вершину, либо ребро, на которых больше всего закрашенных чёрным вершин и ещё не обработанных вершин.

Этот способ работает при количестве переменных не более 4. Мы рисуем Построим следующую таблицу n*n, где n — {{---}} количество переменных:

*Теперь мы покрываем прямоугольниками (длины сторон которых — {{---}} степени двойки (1, 2, 4)) те ячейки карт Карно, которые содержат в себе единицу (на каждом ходу мы выбираем такой прямоугольник, чтобы он покрывал наибольшее количество ещё не покрытых клеток) до тех пор, пока не покроем все такие ячейки (для карт Карно на примере это выглядело бы так):

#*Операция попарного неполного склеивания:

:(где A - любое элементарное произведение)#*Операция элементарного поглощения

Суть метода заключается :(где A {{---}} любое элементарное произведение, то есть конъюнкт, в который каждая из переменных входит не более одного раза.)Метод состоит в последовательном выполнении всех возможных склеиваний и затем всех поглощений частей СДНФ пока это может быть осуществимо.

#*Исходным является множество конституэнт единицы функции - импликанты нулевого ранга.пар вида <tex>Ax</tex> или <tex>A \neg x</tex>#*Выполняются все возможные операции неполного попарного склеивания для элементарных конъюнкций длины n (где n{{--кол-во }} количество аргументов).#*Выполняются все возможные операции элементарного поглощения для элементарных конъюнкций длины n-1 (общая часть "p" имеет длину n-1)#*В результате получилось множество элементарных конъюнкций, разделяемых на два подмножества(по длине):##**подмножество элементарных конъюнкций длины n (оставшиеся)##**подмножество элементарных конъюнкций длины n-1#*Если множество элементарных конъюнкций длины n-1 не пусто, то выполняются шаги со второго для конъюнкций длины n-1 и т.д.