Минимизация булевых функций реферат

Обновлено: 17.05.2024

В общем случае существует несколько способов записи одной и той же булевой функции. Сложность записи булевой функции можно оценивать числом элементарных операций, используемых в такой записи и образующих функционально полную систему булевых функций.

Задачу поиска наиболее простой записи булевой функции называют задачей минимизации. Такая задача возникает в ряде приложений. В частности, при проектировании устройств автоматики или вычислительных устройств их работа может быть описана некоторой булевой функцией или системой таких функций. Каждой элементарной функции в устройствах соответствует некоторый физический элемент (ячейка), реализующий эту функцию. И, следовательно, представлению булевой функции в минимальной форме соответствует более простое устройство автоматики или вычислительной техники по сравнению с устройством, реализующим не минимальную булеву функцию.

Наиболее распространённой формой представления булевой функции является дизъюнктивная нормальная форма. Поэтому задачу упрощения булевых функций обычно формулируют в классе ДНФ.

ДНФ булевой функции называют минимальной, если ей соответствует наименьший суммарный ранг R по сравнению с другими ДНФ этой же функции. Минимальную ДНФ булевой функции будем обозначать как МДНФ.

Поскольку методы минимизации булевых функций, разработанные для ДНФ, достаточно легко переносятся на конъюнктивные нормальные формы (КНФ), ограничимся рассмотрением методов минимизации в классе ДНФ.

В основном эти методы в явной или в неявной форме основаны на выполнении трех операций. Рассмотрим эти операции.

Две элементарных конъюнкции одинакового ранга r называются соседними, если они являются функциями одних и тех же переменных и отличаются только знаком отрицания одной из переменных.

Например, следующие элементарные конъюнкции являются соседними:

и .

Первая операция, называемая операцией склеивания,для элементарных конъюнкций осуществляется по следующему правилу: дизъюнкцию двух соседних конъюнкций некоторого ранга r можно заменить одной элементарной конъюнкций ранга r-1, являющейся общей частью исходных конъюнкций.

где A – некоторая элементарная конъюнкция. В этом случае говорят, что конъюнкции и склеиваются по переменной x. Например:

Здесь и две заданные конъюнкции были склеены по переменной , в одной из которых эта переменная без отрицания, а в другой – с отрицанием.

Вторая из операций называется операцией поглощения, и она осуществляется по правилу:

Дизъюнкцию двух элементарных конъюнкций разных рангов, из которых одна является собственной частью другой, можно заменить конъюнкцией, имеющим меньший ранг.

где А и В – некоторые элементарные конъюнкции.

Третья операция – операция неполного склеивания:

Введем некоторые понятия.

Булева функция называется импликантой функции , если функция равна нулю на всех тех же наборах, на которых равна нулю и функция f. Если есть импликанта функции f, то этот факт записывают следующим образом: .

Рассмотрим импликанты функции .

x	y
0	0	0	0	0	0	0
0	1	1	1	0	0	0
1	0	1	0	1	0	1
1	1	0	0	0	0	1

Конституента единицы в СДНФ функции f всегда является её импликантой. Для функции функции и являются конституентами елиницы из ее СДНФ.

Из определения импликанты следует, что если на некотором наборе значение равно единице, то и значение функции f на этом же наборе также равно единице и в этом случае говорят, что импликанта покрывает единицу функции f.

Чем меньше переменных содержит импликанта функции f по сравнению с конституентой единицы из ее СДНФ, тем больше единиц функции она покрывает.

Элементарная конъюнкция называется простой импликантой булевой функции , если U является импликантой функции f и никакая собственная часть U не является импликантой f .

Рассмотрим пример. Зададим функция f(x, y, z) таблицей истинност. (таблица ниже). СДНФ функции имеет вид:

Укажем импликанты и простые импликанты нашей функции.

x	y	z	f(x, y, z)
0	0	0	1	0	0	0	0	1
0	0	1	1	0	1	0	0	1
0	1	0	0	0	0	0	0	0
0	1	1	1	1	1	0	0	0
1	0	0	1	0	0	1	1	1
1	0	1	1	0	0	0	1	1
1	1	0	0	0	0	0	0	0
1	1	1	0	0	0	0	0	0

Как видим из таблицы, конституента единицы является импликантой нашей функции, ее собственная часть - простой импликантой, поскольку ни , ни не являются импликантами. Аналогично имеем, , - импликанты нашей функции, - простая импликанта; покрывает 4 единицы нашей функции. Простые импликанты в таблице выделены серым цветом.

Справедливы следующие теоремы.

Всякая булева функция может быть представлена как дизъюнкция всех своих простых импликант.

Дизъюнкция всех простых импликант функции f называется сокращённой ДНФ этой функции. Сокращённая ДНФ булевой функции единственна.

Теорема 2. (теорема Квайна).

Если в совершенной дизъюнктивной нормальной форме булевой функции выполнить все операции неполного склеивания, а затем все операции поглощения, то в результате будет получена сокращенная дизъюнктивная нормальная форма этой функции, или дизъюнкция всех ее простых импликант.

Как следует из теоремы, чтобы получить все простые импликанты, мы проводим операции неполного склеивания. Это связано с тем, что одна и та же элементарная конъюнкция дизъюнктивной формы может склеиваться с несколькими конъюнкциями. При каждом таком склеивании образуются различные импликанты и, поэтому мы оставляем в выражении каждую элементарную конъюнкцию для использования ее при других склеиваниях.

От сокращенной ДНФ переходим к минимальной дизъюнктивной нормальной форме – МДНФ.

Рассмотрим один из методов минимизации булевых функций

Метод Квайна.

Этот метод удобен для нахождения МДНФ функции от любого числа переменных.

Алгоритм метода Квайна.

1. Записываем СДНФ булевой функции .

2. Проводим все возможные операции неполного склеивания конституент единицы СДНФ булевой функции, в результате операций получим элементарные конъюнкции ранга (n – 1). Проводим, если это возможно, операции поглощения между конъюнкциями различных рангов. Затем вновь проводим операции неполного склеивания и поглощения до тех пор, пока это возможно. Элементарная конъюнкция, которая не может больше участвовать в склеивании, является простой импликантой булевой функции.

3. Дизъюнкция простых импликант приводит к сокращённой ДНФ булевой функции: , где − простая импликанта.

5. Выбираем существенные импликанты, т.е. такое минимальное количество простых импликант, чтобы они совместно своими единицами покрывали все колонки импликантной матрицы.

6. Дизъюнкция существенных импликант приводит к МДНФ.

Рассмотрим пример. Найдем МДНФ булевой функции, заданной СДНФ:

1. Проведем операции неполного склеивания, их лучше выполнять последовательно, слева на право.

.
.
.
.
У нас все конституенты единицы участвовали в склеивании, поэтому операций поглощения нет. Элементарные конъюнкции больше не склеиваются между собой, следовательно, мы получили простые импликанты.

2. Из простых импликант строим сокращенную ДНФ функции:
.

3. Строим таблицу покрытия

Простые импликанты	Конституенты единицы

	1	1	0	0	0
	0	1	1	0	0
	0	0	1	0	1
	0	0	0	1	1

Выбираем существенные импликанты.

Первая импликанта входит в МДНФ обязательно, она единственная, кто покрывает единицу функции на наборе 000 (единственная единица в первой колонке), затем можно выбрать 3-ю и 4-ю простые импликанты. Получили МДНФ:

У нашей функции две МДНФ: к первой импликанте можно выбрать 2-ю и 4-ю. Получим:

Как видим, у булевой функции может быть несколько МДНФ.

Ранг обеих МДНФ, R = 6.

В тоже время, построив СКНФ заданной функции и проведя минимизацию методом Квайна в базисе КНФ, мы получим единственную МКНФ (минимальную конъюнктивную нормальную форму) меньшего ранга, R = 5.

Рассмотрим еще пример.

Проведем операции неполного склеивания.

1. .

2. .

3. .

4. .

5. .
Все конституенты единицы участвовали в склеивании, у нас нет операции поглощения. Импликанта больше не участвует в склеивании, это простая импликанта. Оставшиеся импликанты могут склеиваться между собой, продолжим склеивание.

6. .

7. .

Операции поглощения у нас опять нет, получили 2 простые импликанты. Сокращенная ДНФ функции имеет вид:

Построим таблицу покрытия.

Простые импликанты	Конституенты единицы

Обратите внимание, что простая импликанта состоит только из отрицания одной переменной и покрывает 4 единицы нашей функции.

Импликантой функции называют некоторую логическую функцию, которая обращается в ноль на том же наборе переменных, на котором равна нулю сама функция.

Любой конъюнктивный терм (элементарная конъюнкция) или группа термов, соединенных знаками дизъюнкции, входящие в СДНФ, являются импликантами исходной функции

Элементарная конъюнкция (конъюнктивный терм), в которой удален один или несколько первичных термов, называется простой импликантой.

Методов минимизации булевых функций в настоящее время существует довольно много. Все они, как правило, состоят из двух этапов. На первом этапе получают список всех простых импликант, т.е. сокращенную ДНФ. На втором этапе, используя таблицу покрытий, удаляют “лишние” импликанты, покрывемые другими импликантами. В результате получают ДНФ, из которой нельзя удалить ни одной импликанты. Такую ДНФ называют тупиковой.

5.1 Метод Квайна

На первом этапе в методе Квайна попарно сравнивают все импликанты, входящие в СДНФ, в целях выявления возможности поглощения какой-то переменной на основе закона склеивания:

Процедура продолжается до тех пор, пока не останется ни одного члена, допускающего поглощение с другим термом. В результате получают некоторое количество простых импликант. Дизъюнкция этих импликант является сокращенной ДНФ.

На втором этапе строится таблица покрытий.В строках этой таблицы указываются найденные простые импликанты, а в столбцах – термы исходного выражения функции. Клетки таблицы отмечаются, если простая импликанта входит в состав какого-либо терма. В итоге минимизация булевой функции сводится к тому, чтобы найти такое минимальное количество простых импликант, которые покрывают все столбцы. В результате получают тупиковую ДНФ.

Недостаток метода–необходимость попарного сравнении всех конъюнктивных термов на первом этапе при нахождении простых импликант. С ростом числа исходных термов увеличивается количество попарных сравнений, что усложняет решение задачи минимизации.

5.2 Метод Квайна с применением п-мерных кубов

Данный метод устраняет недостаток предыдущего метода, т.е. устраняет необходимость попарного сравнения всех термов на первом этапе при нахождении простых импликант. Для этого строится п-мерный куб, по которому визуально можно определить те конъюнктивные термы, склеивание которых порождают простые импликанты.

При решении задачи минимизации булевой функции удобно вместо конъюнктивных термов использовать, соответствующие им, двоичные наборы.

Минимизировать булеву функцию

Здесь в скобках стоят десятичные эквиваленты соответствующих двоичных наборов.

Представим функцию в виде СДНФ:

Запишем конъюнктивные термы в виде двоичных наборов:

Построим единичный 4 – мерный куб и выделим вершины, соответствующие двоичным наборам, входящим в заданную булеву функцию (рис. 10):

1 этап. Определение сокращенной ДНФ.

Применим закон склеивания для отмеченных вершин (для двоичных наборов) куба, соединенных ребром:

Прочерк означает, что переменная в этом месте отсутствует.

Для некоторых простых импликант склеивание можно продолжить:

По закону идемпотентности:

Дизъюнкция полученных простых импликант является сокращенной ДНФ:

2 этап. Определение тупиковой ДНФ.

Для определения тупиковой ДНФ построим таблицу покрытий, в которую следует включать и двоичные наборы, не участвовавшие в склеивании:

Определяя минимальное число строк, покрывающих все столбцы таблицы, находим тупиковую ДНФ:

Недостатком метода является само построение п – мерного куба, т.к. при числе переменных это построение затруднительно.

5.3 Метод Квайна – Мак-Класки

Метод Квайна – Мак-Класки представляет собой предыдущий метод, но без геометрического построения п – мерных кубов: кубы присутствуют, но абстрактно.

Метод основан на кубическом представлении конъюнктивных термов ДНФ с предварительным разбиением кубов на подгруппы, определяемые одинаковым числом единиц. Разбиение дает возможность сравнивать кубы только соседних по числу единиц групп для уменьшения количества переборов.

В итеративной процедуре минимизации попарное сравнение можно производить только между соседними группами.

Нахождение простых импликат на первом этапе:

1. Все исходные конъюнктивные термы записываются в виде их двоичных наборов.

2. Все наборы разбиваются на непересекающиеся группы по числу единиц. Условие образования r-куба – наличие расхождения в (r-1)-кубах только по одной координате в одном двоичном разряде и наличие общих независимых координат.

3. В i-группу включают все двоичные наборы, имеющие в своей записи i единиц.

4. Попарное сравнение производится только между соседними по номеру группами. Группы, которые различаются в двух разрядах и более, не имеет смысла сравнивать.

1
Лекция №3
по математической логике и теории алгоритмов
Тема: Минимизация булевых функций.
Существует немало методов минимизации логических функций, однако наибольший интерес представляют те, которые могут быть формализованы, а соответственно запрограммированы без соответствующих сложностей. Широкое внедрение вычислительной техники и систем управления во все сферы человеческой деятельности и усложнение задач, решаемых этими системами, требуют разработки новых и совершенствования существующих методов логического проектирования цифровых устройств.
Логическое проектирование при этом понимается в широком смысле, основанное на методах минимизации логических функций, которое включает не только статику систем, т.е. их структуру и функциональные связи, но и анализ динамики как на уровне структуры, а также на уровне переходных процессов, связанную с изменением переменных и временными характеристиками элементов.
В связи с этим исследования, направленные на развитие методов минимизации логических функций, обеспечивающих упрощение, улучшение основных характеристик, а также снижение времени и стоимости разработки внедрения системы никогда не потеряют своей актуальности.
Определение 1. Длиной элементарной конъюнкции называется количество переменных в ней.
Определение 2. Длиной дизъюнктивной нормальной формы называется сумма длин, входящих в неё.
Определение 3. Элементарные конъюнкции называются соседними, если они имеют одинаковую длину и отличаются на одну переменную (в одной элементарной конъюнкции присутствует переменная, а в другой её отрицание).
Определение
4.
Дизъюнктивная нормальная форма минимальной длины, тождественно равной данной булевой функции, называется ее минимальной дизъюнктивной нормальной формой
(МДНФ).
Определение 5. Дизъюнктивная нормальная форма, не допускающая склеек, называется тупиковой.
Очевидно, что у любой булевой функции существует минимальная дизъюнктивная нормальная форма, так как из всех длин
l = 1, 2, 3. равных ей дизъюнктивных нормальных форм, всегда

2 можно выбрать минимальную.
К сожалению, единственность отсутствует: многие булевы функции имеют несколько МДНФ одинаковой длины.
Существуют различные способы минимизации булевых функций.
1. Метод непосредственных преобразований.
Преобразования логической формулы к минимальной дизъюнктивной нормальной форме разбивается на 2 этапа:
1. Пусть удалось выделить в ДНФ множитель вида
x
x

, тогда, заменив его единицей, можно уменьшить длину ДНФ. Эта процедура называется склейкой по переменной х.
Чтобы обнаружить склейку в ДНФ, необходимо найти в ней соседние элементарные конъюнкции. С помощью соседних элементарных конъюнкций получается склейка.
Иногда она бывает минимальной, но чаще минимизацию можно продолжить.
2. С помощью сокращающих логических тождеств возможно ещё уменьшить длину тупиковой дизъюнктивной нормальной формы.
К ним относятся: а)
x
xy
x


- закон поглощения; б)
y
x
y
x
x



- закон сокращения.
Пример. Совершенная дизъюнктивная нормальная форма задана в двоичном виде 0000 0001 0010 0101 0110 0111 1000 1001 1010. Привести ее к минимальной дизъюнктивной нормальной форме.
Р еш ен и е
1. Запишем булеву функцию в виде формулы, после чего применим процедуру склейки.

 







t
yz
x
yt
x
t
z
y
z
y
t
yz
x
yt
x
t
z
y
z
y
x
x
t
yz
x
z
y
x
yt
x
t
z
y
z
y
x
t
yz
x
t
t
z
y
x
t
z
z
y
x
t
z
y
x
x
t
t
z
y
x
t
z
y
x
t
z
y
x
t
z
y
x
yzt
x
t
yz
x
t
z
y
x
t
z
y
x
t
z
y
x
t
z
y
x




















































2. Получена тупиковая ДНФ. Применим закон сокращения.
)
(
)
(
)
(
)
(
yz
x
yt
x
t
y
z
y
z
t
y
x
t
z
y
t
z
t
y
x
t
z
z
y
t
yz
x
yt
x
t
z
y
z
y



















Полученная дизъюнктивная нормальная форма является минимальной (МДНФ), так как дальнейшие упрощения невозможны.

5 конъюнкции


z
z
y
x

и


z
z
xy

. Поэтому объединение двух соседних единиц всегда приводит к закону инверсии, согласно которому дизъюнкция противоположных значений переменной равна
1.
Поэтому при записи ответа после применения карты Карно переменные, заключенные в общий контур, связываются конъюнкцией (как и общий множитель при вынесении за скобки), а такие отдельные конъюнкции, т.е. различные контуры, объединяются между собой дизъюнкцией.
Если записать полученный результат, то, очевидно, к нему вновь можно применить то же правило:


y
y
x
x
xy
y
x
z
y
x
f





)
,
,
(
Однако в данном примере удобнее рассмотреть целиком весь квадрат из четырех единиц и сравнить переменные, записанные на горизонтальных и вертикальных клетках.
y
x

y
x

y
x

y
x

z
1 1
z
1 1
Очевидно, общие множители сохранятся после упрощения (ведь их можно было вынести за скобки), а инвертируемые уйдут согласно закону инверсии. Поэтому целесообразнее опустить инвертируемые пары
x
x

и
z
z

, а в ответе сохранить общую для всех клеток переменную
y
Рассмотрим пример минимизации булевой функции, содержащей четыре переменных.
Пример. Пусть
)
,
,
,
(
t
z
y
x
t
z
y
x
t
z
y
x
t
z
y
x
t
z
y
x
t
z
y
x
t
z
y
x
f

























Решение. Занесем единицы в соответствующие клетки карты
Карно:
t
z

t
z

t
z

t
z

y
x

1 1
y
x

1 1
y
x

y
x

1 1
Рассмотрим переменные, заключенные контуром в квадрат.
Среди них есть повторяющиеся в соседних клетках (это x и t ) и

6 инвертируемые (это пары
y
y, и
z
z, ). Повторяющиеся переменные как общий множитель мы сохраним, а инвертируемые – опустим. Из контура, содержащего две единицы, вынесем переменные
y
x, , расположенные на одной строке, а также одинаковую для первых двух столбцов переменную z , при этом опустим инвертируемую пару
t
t,
. После этих преобразований булева функция примет вид:
z
y
x
t
x
t
z
y
x
f





)
,
,
,
(
Пример. Пусть
)
,
(
y
x
y
x
y
x
y
x
f






Решение. Составим карту Карно для двух переменных.
y
y
x
1
x
1 1
Нанесем на карту Карно единицы. Объединим единицы в контуры. Так как получилось два контура, один из которых дает
x
, а другой
y
, то упрощенный вариант булевой функции содержит дизъюнкцию двух членов:
x
и
y
. Попадание единицы в два и более контуров соответствует закону идемпотентности
x
x
x


, поэтому каждое слагаемое (элементарная конъюнкция) может быть представлено столько раз, сколько нужно для упрощения. При этом они группируются с другими слагаемыми, с которыми попали в один контур, независимо. Фактически сделано следующее:




y
x
x
y
y
y
x
y
x
x
y
x
y
x
y
x















Получили
)
,
(
y
x
y
x
f



Минимизация логических функций является одной из типовых задач в процессе обучения схемотехнике. Посему считаю, что такая статья имеет место быть, надеюсь Вам понравится.

Зачем это нужно?

Сложность логической функции, а отсюда сложность и стоимость реализующей ее схемы (цепи), пропорциональны числу логических операций и числу вхождений переменных или их отрицаний. В принципе любая логическая функция может быть упрощена непосредственно с помощью аксиом и теорем логики, но, как правило, такие преобразования требуют громоздких выкладок.

К тому же процесс упрощения булевых выражений не является алгоритмическим. Поэтому более целесообразно использовать специальные алгоритмические методы минимизации, позволяющие проводить упрощение функции более просто, быстро и безошибочно. К таким методам относятся, например, метод Квайна, метод карт Карно, метод испытания импликант, метод импликантных матриц, метод Квайна-Мак-Класки и др. Эти методы наиболее пригодны для обычной практики, особенно минимизация логической функции с использованием карт Карно. Метод карт Карно сохраняет наглядность при числе переменных не более шести. В тех случаях, когда число аргументов больше шести, обычно используют метод Квайна-Мак-Класки.

В процессе минимизации той или иной логической функции, обычно учитывается, в каком базисе эффективнее будет реализовать ее минимальную форму при помощи электронных схем.

Минимизация логических функций при помощи карт Карно

Карта Карно — графический способ минимизации переключательных (булевых) функций, обеспечивающий относительную простоту работы с большими выражениями и устранение потенциальных гонок. Представляет собой операции попарного неполного склеивания и элементарного поглощения. Карты Карно рассматриваются как перестроенная соответствующим образом таблица истинности функции. Карты Карно можно рассматривать как определенную плоскую развертку n-мерного булева куба.

В карту Карно булевы переменные передаются из таблицы истинности и упорядочиваются с помощью кода Грея, в котором каждое следующее число отличается от предыдущего только одним разрядом.

Основным методом минимизации логических функций, представленных в виде СДНФ или СКНФ является операция попарного неполного склеивания и элементарного поглощения. Операция попарного склеивания осуществляется между двумя термами (членами), содержащими одинаковые переменные, вхождения которых (прямые и инверсные) совпадают для всех переменных, кроме одной. В этом случае все переменные, кроме одной, можно вынести за скобки, а оставшиеся в скобках прямое и инверсное вхождение одной переменной подвергнуть склейке. Например:

Возможность поглощения следует из очевидных равенств

Таким образом, главной задачей при минимизации СДНФ и СКНФ является поиск термов, пригодных к склейке с последующим поглощением, что для больших форм может оказаться достаточно сложной задачей. Карты Карно предоставляют наглядный способ отыскания таких термов.

Как известно, булевы функции N переменных, представленные в виде СДНФ или СКНФ могут иметь в своём составе 2N различных термов. Все эти члены составляют некоторую структуру, топологически эквивалентную N–мерному кубу, причём любые два терма, соединённые ребром, пригодны для склейки и поглощения.

На рисунке изображена простая таблица истинности для функции из двух переменных, соответствующий этой таблице 2-мерный куб (квадрат), а также 2-мерный куб с обозначением членов СДНФ и эквивалентная таблица для группировки термов:

В случае функции трёх переменных приходится иметь дело с трёхмерным кубом. Это сложнее и менее наглядно, но технически возможно. На рисунке в качестве примера показана таблица истинности для булевой функции трёх переменных и соответствующий ей куб.

Как видно из рисунка, для трёхмерного случая возможны более сложные конфигурации термов. Например, четыре терма, принадлежащие одной грани куба, объединяются в один терм с поглощением двух переменных:

В общем случае можно сказать, что 2K термов, принадлежащие одной K–мерной грани гиперкуба, склеиваются в один терм, при этом поглощаются K переменных.

Для упрощения работы с булевыми функциями большого числа переменных был предложен следующий удобный приём. Куб, представляющий собой структуру термов, разворачивается на плоскость как показано на рисунке. Таким образом появляется возможность представлять булевы функции с числом переменных больше двух в виде плоской таблицы. При этом следует помнить, что порядок кодов термов в таблице (00 01 11 10) не соответствует порядку следования двоичных чисел, а клетки, находящиеся в крайних столбцах таблицы, соседствуют между собой.

Аналогичным образом можно работать с функциями четырёх, пяти и более переменных. Примеры таблиц для N=4 и N=5 приведены на рисунке. Для этих таблиц следует помнить, что соседними являются клетки, находящиеся в соответственных клетках крайних столбцов и соответственных клетках верхней и нижней строки. Для таблиц 5 и более переменных нужно учитывать также, что квадраты 4х4 виртуально находятся друг над другом в третьем измерении, поэтому соответственные клетки двух соседних квадратов 4х4 являются сосоедними, и соответствующие им термы можно склеивать.

Карта Карно может быть составлена для любого количества переменных, однако удобно работать при количестве переменных не более пяти. По сути Карта Карно — это таблица истинности составленная в 2-х мерном виде. Благодаря использованию кода Грея в ней верхняя строка является соседней с нижней, а правый столбец соседний с левым, т.о. вся Карта Карно сворачивается в фигуру тор (бублик). На пересечении строки и столбца проставляется соответствующее значение из таблицы истинности. После того как Карта заполнена, можно приступать к минимизации.

Если необходимо получить минимальную ДНФ, то в Карте рассматриваем только те клетки которые содержат единицы, если нужна КНФ, то рассматриваем те клетки которые содержат нули. Сама минимизация производится по следующим правилам (на примере ДНФ):

$\infty$

Объединяем смежные клетки содержащие единицы в область, так чтобы одна область содержала 2 n (n целое число = 0…) клеток(помним про то что крайние строки и столбцы являются соседними между собой), в области не должно находиться клеток содержащих нули;
Область должна располагаться симметрично оси(ей) (оси располагаются через каждые четыре клетки);
Не смежные области расположенные симметрично оси(ей) могут объединяться в одну;
Область должна быть как можно больше, а кол-во областей как можно меньше;
Области могут пересекаться;
Возможно несколько вариантов накрытия.

Далее берём первую область и смотрим какие переменные не меняются в пределах этой области, выписываем конъюнкцию этих переменных, если неменяющаяся переменная нулевая, проставляем над ней инверсию. Берём следующую область, выполняем то же самое что и для первой, и т. д. для всех областей. Конъюнкции областей объединяем дизъюнкцией.
Например(для Карт на 2-ве переменные):

Читайте также: