Как сделать сокращенную днф

Обновлено: 06.07.2024

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

Интервал функции называется максимальным, если и не существует другого интервала такого, что . Т.е. интервал является максимальным тогда и только тогда, когда K – простой импликант функции . Отсюда

– единичное покрытие есть объединение всех максимальных интервалов.

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

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

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

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

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

Рассмотрим методы построения сокращенной ДНФ. Используем правила

склеивания	(5.1)
поглощения	(5.2)
неполного склеивания	(5.3)
обобщенного склеивания	(.4)

Здесь некоторые элементарные конъюнкции.5

Метод Блейка построения сокращенной ДНФ булевой функции состоит в последовательном применении правил (5.2) и (5.4). Сначала применяется правило (5.4) пока это возможно, а затем – (5.2).

Пример 5.5. Используя метод Блейка, построить сокращенную ДНФ функции .

(одинарной линией подчеркнуты слагаемые, которые при помощи правила (5.4) дают новую элементарную конъюнкция, которая выделена двойным подчеркиванием)

Далее применяется правило поглощения (подчеркнуты слагаемые, поглощаемые по правилу (5.2) переменной ):

Слагаемое поглощается по правилу (5.2) слагаемым . Таким образом, получили сокращенную ДНФ .

Рассмотрим табличный метод построения минимальной ДНФ, основанный на использовании карт Карно.

Пример 5.6.Используя карту Карно, построить все минимальные ДНФ функции .

Решение. Строим покрытие всеми максимальными интервалами и выпишем соответствующую этому покрытию сокращенную ДНФ.

Сокращенная ДНФ данной функции имеет вид

Построим неприводимое покрытие и выпишем все тупиковые ДНФ, реализующие заданную функцию .

где L – число литералов в ДНФ.

Рис. 5.13. Рис. 5.14.

Рис. 5.15. Рис. 5.16.

Из полученных тупиковых ДНФ выберем те, которые имеют наименьшее число литералов и выпишем минимальные ДНФ:

Рассмотрим геометрический метод нахождения сокращенной (минимальной, кратчайшей) ДНФ, который нагляден для небольшой размерности .

Пример 5.7.Используя геометрический метод, построить все минимальные ДНФ функции .

Решение. Строим покрытие куба максимальными интервалами (рис. 5.17) и выпишем соответствующую этому покрытию сокращенную ДНФ: . Построим теперь неприводимое покрытие и выпишем все тупиковые ДНФ, реализующие заданную функцию .	Рис. 5.17.
Рис. 5.18. .	Рис. 5.19. .
Рис. 5.20. . .	Рис. 5.21. .

Выпишем теперь все минимальные ДНФ, реализующие функцию (содержат наименьшее число литеров среди всех ДНФ, реализующих данную функцию).

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

Пример 5.8. Построить сокращенную ДНФ по заданной КНФ функции .

Решение. Раскрываем скобки =

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

Рассмотрим алгоритм Квайна построения сокращенной ДНФ. Сперва к совершенной ДНФ функции применяется правило неполного склеивания (5.3) (к каждой паре конъюнкций), а затем при помощи операции поглощения (5.2) удаляются те конъюнкции ранга n, которые могут быть удалены. В результате получается некоторая ДНФ . Процедура повторяется, и на (k+1)-м шаге операции неполного склеивания и поглощения применяются к конъюнкциям ранга ДНФ . В результате получается ДНФ . Алгоритм завершается, если = .

Пример 5.9. Пусть функция f задана своей совершенной ДНФ.

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

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

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

Заметим, что если некоторый символ в формуле, скажем , встречается, например, два раза, то при подсчете числа символов в формуле он учитывается два раза.

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

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

Число различных ДНФ, составленных из переменных , равно .

Прежде чем доказать данное утверждение, приведем следующее определение.

Конъюнкция называется элементарной, если при .

Число r называется рангом элементарной конъюнкции. В случае r = 0 конъюнкция называется пустой и полагается равной 1.

Так как каждая из n переменных либо не входит в элементарную, либо входит в нее с отрицанием, или без отрицания, то число элементарных конъюнкций, составленных из равно . Ясно, что число различных ДНФ, составленных из переменной , равно числу подмножеств множества, из элементов, т.е. .

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

Обозначим через множество всех точек , где . Ясно, что – множество всех вершин единичного n-мерного куба.

Сопоставим каждой булевой функции подмножество из , определенное следующим образом:

Например, функции, заданной следующей таблицей истинности:

вершин трехмерного единичного куба

Данное соответствие является взаимно однозначным и обладает следующими свойствами:

1) булевой функции соответствует подмножество ;

2) булевой функции соответствует подмножество ;

3) булевой функции соответствует подмножество .

Докажем свойство 2. Пусть

А это значит, что .

Пусть ДНФ, где – элементарные конъюнкции. Подмножество называется интервалом r-го ранга, если оно соответствует элементарной конъюнкции К r-го ранга. Как показано выше, . Итак, с каждой ДНФ функции f связано покрытие такими интервалами , что .

Пусть – ранг интервала . Тогда совпадает с числом букв в ДНФ функции .

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

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

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

Очевидно, что каждый интервал из содержится в некотором максимальном интервале. Если – список всех максимальных интервалов подмножества , то нетрудно видеть, что .

ДНФ булевой функции f, соответствующая покрытию

подмножества всеми максимальными интервалами, называется сокра

щенной ДНФ функции f.

Ясно, что сокращенная ДНФ для любой булевой функции f определяется однозначно.

Пример 1. Пусть . Обозначим , , . Найдем соответствующие этим конъюнкциям интервалы , , .

Изобразим эти интервалы

Очевидно, что и – все максимальные интервалы. Интервал не является максимальным, ибо . Следовательно, покрытию подмножества соответствует сокращенная ДНФ функции , равная .

Данный геометрический подход дает и метод построения сокращенной

Теперь рассмотрим аналитический метод построения сокращенной ДНФ – метод Блейка. Этот метод основан на следующей теореме.

Теорема 1. Если в произвольной ДНФ булевой функции f произвести все возможные обобщения склеивания и устранить затем все элементарные поглощения, то в результате получится сокращенная ДНФ функции f.

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

Пример 2. Найти сокращенную ДНФ для функции .

Применяя правило обобщенного склеивания, получаем: , а затем правило поглощения и находим сокращенную ДНФ: .

Рассмотрим еще один метод построения сокращенной ДНФ – метод Нельсона. Этот метод основан на следующей теореме.

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

Пример 3. Найти сокращенную ДНФ для функции

После раскрытия скобок с помощью дистрибутивного закона, получаем:

Так как , , то имеем:

Далее, применяя правило поглощения, получаем сокращенную ДНФ:

Рассмотрим табличный метод построения сокращенной ДНФ. Этот метод основан на составлении прямоугольной таблицы (минимизирующей карты).

Минимизирующие карты для булевых функций от трех и от четырех переменных изображены в следующих таблицах:

z x y

x₄ x₃ x₁ x₂

0 0

0 1

1 1

1 0

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

Пример 4. Найти сокращенную ДНФ для функции, заданной следующей таблицей.

x₄ x₃ x₁ x₂

0 0

0 1

1 1

1 0

В данной таблице объединены клетки в максимальные интервалы

Этим интервалам соответствуют элементарные конъюнкции

Следовательно, сокращенная ДНФ для данной функции имеет вид:

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

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

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

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

Теорема 4. Сокращенная ДНФ монотонной булевой функции не содержит отрицаний переменных и является минимальной ДНФ этой функции.

Пусть К – элементарная конъюнкция, входящая в сокращенную ДНФ. Предположим, что К содержит отрицание переменных. Обозначим через произведение всех переменных, входящих в К без отрицания. Пусть – набор переменных, в которых всем переменным, входящим в , приписано значение 1, а всем остальным – значение 0. Ясно, что при этом наборе значение функции равно 1. Элементарная конъюнкция обращается в 1 при всех наборах . Очевидно, что при этих наборах значение функции также равно 1. Следовательно, .

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

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

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

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

Ввиду этого введем следующее определение.

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

Теорема 5. Всякая минимальная ДНФ является тупиковой.

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

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

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

1. Выделяются все максимальные интервалы, и строится сокращенная ДНФ.

2. Строятся все тупиковые ДНФ.

3. Среди всех тупиковых ДНФ выделяются все минимальные ДНФ.

Рассмотрим алгоритм построения всех тупиковых ДНФ.

Суть данного алгоритма состоит в следующем:

1) для булевой функции строим сокращенную ДНФ;

2) для каждой вершины из выделяем в сокращенной ДНФ функции f все такие элементарные конъюнкции , что ;

3) составляем выражение вида

4) применяем к выражению вида (6.1) законы дистрибутивности и поглощения. В результате получаем .

Теперь каждая ДНФ является тупиковой ДНФ функции .

Рассмотрим работу данного алгоритма на следующем примере.

Пример 5. Рассмотрим булеву функцию, заданную следующей таблицей:

Найдем сокращенную ДНФ данной функции по методу Нельсона. Для этого составим КНФ данной функции .

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

Напомним, что мы рассматриваем булевы функции над переменными =\" />
. С каждой элементарной конъюнкцией ^\wedge X_^\wedge \ldots \wedge X_^ " />
связано множество наборов переменных, на которых K принимает значение 1. Нетрудно понять, что это множество содержит 2_(n-k) наборов, в которых каждая из входящих в K переменных \ (1 \leq r\leq k)" />
имеет фиксированное значение " />
, а значения остальных (n-k) переменных произвольны.

Определение Пусть f - произвольная булева функция над " />
. Элементарная конъюнкция K называется допустимой для f , если .

Элементарная конъюнкция K называется максимальной для f , если для любой элементарной конъюнкции L из условия следует, что .

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

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

$\Phi_1=( X \wedge \neg Z)\vee \neg Y \vee (\neg X \wedge Z)$

Примером сокращенной ДНФ является формула из примера 4.1.

Сокращенную ДНФ можно получить из произвольной ДНФ D , используя процедуру, называемую методом Блейка .

$(X\wedge K_1) \vee (\neg X \wedge K_2) \equiv (X\wedge K_1) \vee (\neg X \wedge K_2) \vee (K_1\wedge K_2)$

(П3):

$X \vee (X\wedge K) \equiv X$

(П1): .

Теорема 4.2. В результате применения метода Блейка к произвольной ДНФ через конечное число шагов будет получена эквивалентная ей сокращенная ДНФ .

$N_K^+ \subseteq N_<K$

Доказательство Пусть после (1)-го этапа процедуры ДНФ D функции f преобразовалась в эквивалентную ДНФ D₁ . Покажем, что для всякой допустимой для f элементарной конъюнкция K в D₁ найдется такая конъюнкция K' , что . Доказательство проведем возвратной индукцией по числу переменных в K .

Базис индукции. Пусть K содержит все n переменных из " />
. Тогда состоит из единственного набора и, поскольку ^+" />
, то в сущетсвует конъюнкция K' , для которой .

Шаг индукции. Пусть для некоторого k утверждение верно для всех допустимых для f конъюнкций, содержащих не менее (k+1) -ой переменной. Докажем, что оно верно и для допустимых конъюнкций с k переменными.

Пусть допустимая для f элементарная конъюнкция K содержит k переменных и пусть " />
- переменная, не входящая в K . Тогда обе элементарные конъюнкции и являются допустимыми для f и по предположению индукции для них в " />
найдутся такие " />
и " />
, что ^+ \subseteq N_ и ^+ \subseteq N_. Если хотя бы одна из них не содержит X , то ее можно выбрать в качестве K' . В противном случае, их можно представить в виде = (X \wedge K_1^<\prime\prime>)" />
и = (\neg X \wedge K_2^<\prime\prime>)" />
. При этом ^+ \subseteq N_ и ^+ \subseteq N_. Поскольку все преобразования вида (П3) выполнены, то D₁ тогда содержит и конъюнкцию = (K_1^<\prime\prime>\wedge K_2^<\prime\prime>)" />
, для которой ^+ \subseteq N_.

$D= (\neg X_1\wedge \neg X_2 \wedge X_3)\vee (\neg X_1\wedge X_2 \wedge \neg X_3)\vee (\neg X_1\wedge X_2 \wedge X_3)\vee ( X_1\wedge \neg X_2 \wedge X_3)$

Ее совершенная ДНФ .

После применения преобразований (П3) на (1)-ом этапе получим

$D_1= (\neg X_1\wedge \neg X_2 \wedge X_3)\vee (\neg X_1\wedge X_2 \wedge \neg X_3)\vee (\neg X_1\wedge X_2 \wedge X_3)\vee\\ ( X_1\wedge \neg X_2 \wedge X_3)\vee (\neg X_2\wedge X_3) \vee (\neg X_1 \wedge X_2) \vee (\neg X_1 \wedge X_3)$

После поглощений (П1) на втором этапе останется сокращенная ДНФ

$D_2=(\neg X_2\wedge X_3) \vee (\neg X_1 \wedge X_2) \vee (\neg X_1 \wedge X_3).$

$D_2\equiv (\neg X_2\wedge X_3) \vee (\neg X_1 \wedge X_2)$

Заметим, что она не является самой короткой ДНФ для 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-ве переменные):

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