Как сделать мкнф

Обновлено: 08.07.2024

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

Инструкция к сервису

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

Булевы функции

С помощью этого калькулятора по булевой функции строится таблица истинности, определяются свойства функции и другие параметры (см. вкладку Параметры решения ). ► При этом вводится только само логическое выражение без префикса. Например, при f(x,y,z) = x → y!z , ввести необходимо только x → y!z .
Введеное выражение также можно упростить, используя законы логики высказываний (на следующем шаге выбрать параметр Упростить выражение ).

(. ) - ввод скобок, x -отрицание ( NOT , ! , ¬), & - логическое И, AND, ∧, *, v - логическое ИЛИ, OR, ∨, = - эквивалентность, ˜, ≡, ↔, ⊕ - сумма по модулю 2, | - штрих Шеффера, И-НЕ, AND-NOT, ↓ - стрелка Пирса, ИЛИ-НЕ, OR-NOT, ← - обратная импликация.

Для вложенного отрицания необходимо использовать знак ! . Например, x v y = !(x v y ) или x v y = x v !y
Далее Построить схему

По найденной таблице истинности можно определить логические значения высказываний, например, при x=0 , y=0 , z=1
Чтобы проверить высказывание на истинность или ложность, функцию необходимо вводить без знака равно ( = ). Например, A+B → A&B =1 , необходимо ввести A+B → A&B . Если в результате преобразований получится, что f=1 , то высказывание истинно, если f=0 - ложно.

Логические (функциональные) элементы являются наиболее распространенными: в силу полноты системы любую булеву функцию (БФ) можно представить в виде суперпозиции дизъюнкции, конъюнкции и отрицания. В качестве функциональных элементов (ФЭ) можно рассматривать любые булевы функции, при этом их можно соединять друг с другом, подавая выходы одних элементов на входы других (суперпозиция БФ).

Отрицание, ¬

Конъюнкция, &

Дизъюнкция, v

Сумма по модулю 2, x⊕y

Стрелка Пирса, x↓y

Эквивалентность, x↔y

Импликация, x→y

Штрих Шеффера, x|y

Основные равносильности логики высказываний

Название	Формула
Закон исключенного третьего	X v !X ≡ И
Закон противоречия	X & !X ≡ Л
Закон коммутативности	X & Y ≡ Y & X X v Y ≡ Y v X
Закон ассоциативности	(X & Y)&Z ≡ X&(Y&Z) (X v Y) v Z ≡ X v (Y v Z)
Закон дистрибутивности	X&(Y v Z) ≡ X&Y v X&Z X v Y&Z ≡ (X v Y)&(X v Z)
Закон двойного отрицания	!!X ≡ X
Закон идемпотентности	X&X ≡ X, X v X ≡ X
Законы де Моргана	!(X v Y) ≡ !X & !Y !(X & Y) ≡ !X v !Y
Закон поглощения	X v X&Y ≡ X X&(X v Y) ≡ X
Законы склеивания	(X & Y)v(X & !Y) ≡ X (X v Y)&(X v !Y) ≡ X
Замена импликации	X → Y ≡ !X v Y
Замена эквиваленции	X = Y ≡ X&Y v !X&!Y

Пример . Упростите выражение: (x˅y˅z)→(x˅y)*(x˅z)
Упростим функцию, используя основные законы логики высказываний.
Замена импликации: A → B = !A v B
Для нашей функции:
(x v y v z)→((x v y) (x v z)) = x v y v z v (x v y) (x v z)
Упростим функцию, используя законы де Моргана: !(A v B) = !A & !B
Для нашей функции:
x v y v z = x y z
По закону дистрибутивности:
(x v y) (x v z) = x v x z v y x v y z
получаем:
f = x y z v x v x z v y x v y z
После элементарных преобразований получаем:
f = x y z v x v x z v y x v y z = x y z v x v y z
f = y z v y z v x

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

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

Kx v K ≡ K - тождество поглощения;
Kx v K x ≡ K - тождество склеивания;
Kx v Ky ≡ K(xvy) - дистрибутивный закон,

Метод карт Карно

После минимизации можно получить логическую схему функции и построить таблицу истинности (кнопка Далее )
Далее

Минимизая функции через равносильные преобразования

Алгоритм минимизии логической функции

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

Алгоритм Куайна построения сокращенной ДНФ

Получить СДНФ функции.
Провести все операции неполного склеивания.
Провести все операции поглощения.

Построение логической схемы по таблице истинности

По заданной СДНФ (по таблице истинности) определяются существенные и фиктивные переменные, полином Жегалкина и принадлежность классам T0,T1, S, M, L. ► Также можно создать новую логическую схему (если не выбран пункт Строить новую схему при минимизации булевой функции). Если вычисления происходят по исходной схеме и она понадобится в дальнейшем, то ее можно предварительно сохранить (меню Действия/Сохранить ).

Пример . Найдите СДНФ(А) и СКНФ(А) с помощью равносильных преобразований и таблицы истинности, если A = x v y v(x→y)&x

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

Правило склеивания. Упрощение выражений булевых функций (минимизация) основывается на понятии несущественности переменных. Переменная называется несущественной на паре наборов, если при изменении ее значения на противоположное булева функция сохраняет свое значение.

Например, для булевой функции трех переменных, /(1, 3, 5, 6, 7)=1, 6-я и 7-я конъюнкции имеют вид: , х_х₂х₃. По дистрибутивному закону:

Таким образом, две конъюнкции, содержащие несущественную переменную, заменяются одной, в которой несущественная переменная отсутствует.

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

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

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

Операция Ах + Ах = А называется полным склеиванием, а операция

Ах + Ах = А + Ах + Ах - неполным склеиванием (для ДНФ).

Операция (А + х)(А + х) = А называется полным склеиванием, а операция (А + х)(А + х) = А(А + х)(А + х) - неполным склеиванием (для КНФ).

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

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

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

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

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

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

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

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

Сокращенная КНФ - это конъюнкция всех простых имплицент.

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

Тупиковая КНФ - это конъюнкция простых имплицент, из которых ни одна не является лишней.

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

Минимизация булевых функций с использованием карт Карно. Рассмотрим визуальный метод минимизации булевых функций с помощью карт (диаграмм) Карно, который является одним из наиболее удобных методов при небольшом числе переменных (до 6). Данный метод был разработан в 1953 г. американским ученым Морисом Карно.

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

Отметим, что метод карт Карно применим к минимизации булевых функций до 6-ти переменных (до 4 переменных на плоскости) и до 6 - в трехмерной интерпретации.

Минимальной ДНФ (МДНФ) функции F(X1, . ,Xn) называется ДНФ, реализующая функцию F и содержащая минимальное число символов переменных по сравнению со всеми другими видами ДНФ, реализующими функцию F.

Если для всякого набора = (A1, . An) значений переменных условие G( )=1 влечёт , то функция G называется частью функции F (или функция F накрывает функцию G). Если при этом для некоторого набора = (C1, . Cn) функция G( )=1, то говорят, что функция G накрывает единицу функции F на наборе (или что G накрывает конституенту единицы функции F). Заметим, что конституента единицы функции F есть часть функции F, накрывающая единственную единицу функции F.

Элементарная конъюнкция K называется импликантом функции F, если для всякого набора =(A1, . An) из 0 и 1 условие K( )=1 влечет F( )=1.

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

Ясно, что всякий импликант функции F есть часть функции F.

Теорема. Всякая функция реализуется дизъюнкцией всех своих простых имликант (ПИ).

Доказательство. Пусть F(X1, . Xn) есть функция, а A = K1 v. v Km – дизъюнкция всех ее простых импликант. Пусть = (A1, . An) – произвольный набор длины N из 0 и 1.

Если A( ) = 1, то найдется дизъюнктивное слагаемое Ki ( ) = 1, что влечет F( ) = 1, ибо Ki есть импликант функции F.

Если F( ) = 1, то в СДНФ для функции F найдется элементарная конъюнкция K, равная на этом наборе единице. Один из простых имликантов Kj функции F получается выбрасыванием некоторых множителей из K и потому Kj( ) = 1, а тогда A( ) = 1.

Следовательно, F = A. Теорема доказана.

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

Пусть A и B – произвольные формулы. Из свойств булевых операций вытекают следующие обратимые правила преобразования ДНФ:

1) – полное склеивание (развертывание);

2) – неполное склеивание;

3) – обобщенное склеивание;

4) – поглощение;

5) – идемпотентность ( удаление дублирующих членов).

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

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

Алгоритм Квайна построения сокращенной ДНФ.

1. Получить СДНФ функции F.

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

3. Провести все операции поглощения.

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

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

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

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

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

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

1. Строим СДНФ функции F:

. Пронумеруем дизъюнктивные члены в полученной СДНФ в порядке от 1 до 11.

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

Первый этап склеивания в таблице 3.2.

После первого этапа склеиваний (и возможных поглощений) получаем, что

Пронумеруем дизъюнктивные члены в полученной ДНФ в порядке их следования от 1 до 15.

Второй этап склеиваний в таблице 3.3.

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

Метод Блейка

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

Пример 2. Построить сокращенную ДНФ по ДНФ D функции F(X,Y,Z), где

После первого этапа получаем:

После второго этапа получаем сокращенную ДНФ:

Алгоритм построения сокращенной ДНФ с помощью КНФ

(метод Нельсона)

Пусть F(X1, … , Xn) есть некоторая функция алгебры логики. Построим для F некоторую КНФ. Осуществим далее следующие преобразования.

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

2. В полученном выражении удалим нулевые дизъюнктивные слагаемые.

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

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

Для каждой элементарной дизъюнкции D в КНФ и каждой элементарной конъюнкции K в сокращенной ДНФ (сокр. ДНФ) существует некоторый множитель вида X из K, содержащийся в D, т. е.

" DÎ ДНФ " K Î сокр. ДНФ $ Xa Î K (XaÎ D).

Допустим противное: в КНФ существует элементарная конъюнкция D, в сокращенной ДНФ существует элементарная конъюнкция K, для которой всякий множитель вида Xa из K не входит в D. Не уменьшая общности возьмем для простоты

Положим X1 = A1, …, Xk=Ak, Xk+1 = Ck+1 ¹ Ak+1, …, Xr = Cr ¹ Ar. Тогда K(A1, …, Ak) = 1, и потому F (A1, …, Ak, Ck+1, …, Cr ) = 1. С другой стороны, D(Ck+1,…, Cr) = 0, и потому F (A1, …, Ak, Ck+1, …, Cr ) = 0. Противоречие.

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

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

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

F = (1111010010101111) из примера 1 :

Сокращенная ДНФ для функции

Что, естественно, совпадает с результатом примера 1.

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

После раскрытия скобок имеем:

После второго этапа получаем сокращенную ДНФ:

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

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

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

Вывод. Для получения МДНФ функции F необходимо построить все ТДНФ функции F и выбрать из них те, которые содержат минимальное число букв.

Построение всех тупиковых ДНФ.

Пусть F(X1, …, Xn) есть функция алгебры логики.

1. Построим СДНФ функции F, и пусть P1, P2, …,Pn есть ее коституенты единицы).

2. Построим сокращенную ДНФ функции, F и пусть K1, K2, …, Km – ее простые импликанты.

3. Построим матрицу покрытий простых импликант функции F ее конституентами единицы (табл. 3.4), полагая, что

+, если каждый множитель в Ki является множителем в Pj; (Pj есть Aij= часть для Ki ); Æ в противном случае.

P1 P2 … Pj …Pn

A11 a12 … a1J …a1N

A21 a22 … a2J … a2N

Ai1 ai2 … aij … ain

Am1 am2… amj … amn

4. Для каждого столбца J ( 1 £ J £ N ) найдем множество Ej всех тех номеров I строк, для которых Aij = 1. Пусть Составим выражение Назовем его решеточным выражением. Это выражение можно рассматривать как формулу, построенную в свободной дистрибутивной решетке с образующими 1, 2, …,M и с операциями & и Ú .

5. В выражении A раскроем скобки, приведя выражение A к равносильному выражению где перечислены все конъюнкции элементы которой взяты из скобок 1,2,…,N соответственно в выражении A.

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

Утверждение. Каждая элементарная конъюнкция I1&I2&…&Ir в С дает ТДНФ для F . Все ТДНФ для функции F исчерпываются элементарными конъюнкциями в выражении С.

Пример 5. Сокращенная ДНФ для функции F = (1111010010101111) имеет вид

Для функции F построим все минимальные ДНФ.

1. Строим матрицу покрытий (таблица 3.5).

Конституенты единицы функции F

X `X `X `X `X X X X X X X

=> число карт Карно равно числу выходов, так как каждая из функций Y„ минимизируется с помощью своей карты;

где Z*,, — общие из членов Z 1 . Z*. 2г для функции Y„.

Представление минимизированных логических функций в виде (13) значительно упрощает схемное решение, так как общие члены Z 1 , z K реализуются один раз для всего комбинационного устройства.

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

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

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

Минимальная нормальная форма – это нормальная форма, содержащая минимальное количество переменных, использованных с отрицанием или без.

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

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

Метод эквивалентных логических преобразований

Получение МДНФ (МКНФ) через упрощение СДНФ (СКНФ) по правилам преобразования.

Диаграмма Вейча (карта Карно)

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

Операция склеивания осуществляется между двумя совершенными конъюнктами (дизъюнктами), у которых совпадают все литералы, кроме одного. По правилам склеивания совпадающие литералы выносятся за скобки, а оставшиеся подвергнуть склейке.

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

Интервал логической функции от переменных – это такое множество наборов значений переменных, что:

· Значение функции на этом множестве постоянно;

· Мощность (величина, размер интервала) этого множества равна , ;

· является количеством переменных, которые упрощаются на этом множестве, а оставшихся ( ) переменных достаточно для описания логической функции на данном множестве;

· Если , то каждый следующий набор отличается от предыдущего значением только одной переменной.

Типы интервалов

Интервал размера 1

Вырожденный случай. Упрощения не происходит. Интервал может встречаться на любых диаграммах.

Интервал размера 2

Упрощается одна переменная. Интервалы могут встречаться на любых диаграммах.

Интервал размера 4

Упрощается 2 переменных. Некоторые интервалы встречаются, начиная с диаграммы Вейча для функции от 3 переменных.

Интервалы размером 8

Упрощается 3 переменных. Некоторые интервалы встречаются, начиная с диаграммы Вейча для функции от 4 переменных.

Алгоритм минимизации

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

2. Заполнить таблицу значениями функции с учетом цели минимизации (удобно выписывать только 1 для МДНФ и только 0 для МКНФ).

3. Выделить контурами интервалы из единиц (МДНФ) или нулей (МКНФ), соблюдая следующие правила:

a. Необходимо стараться выделить максимально большие интервалы;

b. Каждый новый интервал должен содержать хотя бы одно значение, принадлежащее только ему;

c. Необходимо выделить минимально возможное количество интервалов.

4. Выписать формулу МДНФ (МКНФ), для чего:

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

b. Соединить выписанные конъюнкты (дизъюнкты) через дизъюнкцию (конъюнкцию).

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