Нахождение простых импликант
Перебирают все пары минтермов исходной совершенной дизъюнктивной нормальной формы,
склеивая те из них, для которых эта операция возможна. При составлении пар любой из минтермов может быть
испоользован многократно. Процедура повторяется и над полученными импликантами — опять проводятся
операции склеивания. Процесс повторяется до тех пор, пока не останется ни одной импликанты, допускающей
склеивания с другими. Такие импликанты называются простыми. Участовавшие в склеивании элементарные
конъюнкции помечаются каким-либо символом, например, «*».
Наличие такого символа означает, что данная элементарная конъюнкция уже учтена в
какой-то из импликант, полученных в результате склеивания, и поглощается последней. Если какой-либо из
минтермов изначально не удалось склеить ни с одним другим, то он уже сам по себе является простой
импликантой. Дизъюнктивная нормальная форма, составленная из всех простых импликант, полученных
в результате описанной процедуры, представляет собой сокращённую ДНФ, эквивалентную исходной СДНФ. Данный
этап иллюстирует таблица ниже (таблица 2).
Таблица 2. Склеивание минтермов совершенной ДНФ
| Номер набора | Минтермы |
| * | |
| 1 | * |
| 2 | * |
| 5 | * |
| 6 | * |
| 7 | * |
| 8 | * |
| 9 | * |
| 10 | * |
| 14 | * |
| Склеиваемые наборы | Минтермы |
| 0, 1 | |
| 0, 2 | |
| 0, 8 | |
| 1, 5 | |
| 1, 9 | |
| 2, 6 | |
| 2, 10 | |
| 5, 7 | |
| 6, 7 | |
| 6, 14 | |
| 8, 9 | |
| 8, 10 | |
| 10, 14 |
В левой части таблицы показаны минтермы исходной совершенной ДНФ. Анализируюются все
возможные пары минтермов, и, если это возможно, производится их склеивание. Минтермы, участовавшие в
операции склеивания, помечаются символом «*». Результаты склеивания с указанием номеров «склеенных» минтермов
показаны в правой части таблицы 2.
В результате первого этапа склеивания получены 13 импликант ранга 3. Поскольку помеченными
оказались все минтермы, среди них простых импликант нет, тем самым в 13 импликантах содержится вся исходная
информация, и, ДНФ, составленная из этих импликант, полностью эквивалентна исходной совершенной ДНФ. Далее
повторим процедуру попарного склеивания применительно к полученным 13 импликантам. Это показано в таблице 3.
Таблица 3. Склеивание импликант ранга 3
| Склеиваемые наборы | Минтермы |
| 0, 1 | * |
| 0, 2 | * |
| 0, 8 | * |
| 1, 5 | |
| 1, 9 | * |
| 2, 6 | * |
| 2, 10 | * |
| 5, 7 | |
| 6, 7 | |
| 6, 14 | * |
| 8, 9 | * |
| 8, 10 | * |
| 10, 14 | * |
| Склеиваемые наборы | Импликанты |
| 0, 1, 8, 9 | |
| 0, 2, 8, 10 | |
| 0, 8, 1, 9 | |
| 0, 8, 2, 10 | |
| 2, 6, 10, 14 | |
| 2, 10, 6, 14 |
Из таблицы видно, что импликанты, обозначенные как 1,5; 5,7 и 6,7 остались непомеченными.
Это означает, что они не были склеены ни с одной другой импликантой, поэтому являются простыми и должны
учитываться на последующих этапах минимизации. В ходе склеивания образовались три пары импликант ранга 2.
В соответсвии с теоремой идемпотентности из нескольких одинаковых импликант можно составить только одну.
Нетрудно заметить, что дальнейшее склеивание трёх оставшихся импликант ранга 2 невозможно, то есть эти
импликанты простые. Таким образом, в дополнение к трём простым импликантам ранга 3:
,
и
получены ещё три простые
импликанты ранга 2: ,
и
. Логическая сумма
перечисленных простых импликант представляет собой сокращённую ДНФ:
Составление импликантной матрицы и расстановка меток избыточности
Этот и последующие шаги имеют целью убрать из сокращённой ДНФ все лишние простые
импликанты, тем самым перейти от сокращённой ДНФ к тупиковым формам, а затем и к минимальным. Задача
решается с помощью специальной импликантной матрицы. Каждая строка такой матрицы соответствует одной из
простых импликант, входящих в сокращённую ДНФ, иными словами, количество строк в матрице равно числу
простых импликант в сокращённой ДНФ. Столбцы матрицы представляют минтермы исходной СДНФ, при этом
каждому из них соответствует свой столбец.
Если минтерм в столбце импликантной матрицы содержит в себе простую импликанту
из какой-либо строки матрицы, то на пересечении данного столбца и данной строки ставится метка избыточности.
Это означает, что данная простая импликанта поглощает соответсвующий минтерм и способна заменить его
в окончательном логическом выражении.
Таблица 4. Импликантная матрица Квайна
| 0, 1, 8, 9 | |
| 0, 2, 8, 10 | |
| 2, 6, 10, 14 | |
| 1, 5 | |
| 5, 7 | |
| 6, 7 |
| 1 | 2 | 5 | 6 | 7 | 8 | 9 | 10 | 14 | |
| √ | √ | √ | √ | ||||||
| √ | √ | √ | √ | ||||||
| √ | √ | √ | √ | ||||||
| √ | √ | ||||||||
| √ | √ | ||||||||
| √ | √ |
Импликантная матрица для рассматриваемого примера (таблица 4) содержит 6 строк (по числу
простых импликант) и 10 столбцов (по числу минтермов исходной СДНФ). В матрице минтермы обозначены своими
номерами, а слева от простых импликант перечислены номера минтермов, из которых эти импликанты были
получены. Расставим в ней метки в тех позициях, где простая импликанта, указанная в левом столбце,
покрывает минтерм, записанный в верхней строке.
Презентация на тему: » 5. Минимизация логических функций методом Квайна – Мак-Класки Метод Карно позволяет минимизировать логические функции с относительно малым числом переменных.» — Транскрипт:
1
5. Минимизация логических функций методом Квайна – Мак-Класки Метод Карно позволяет минимизировать логические функции с относительно малым числом переменных. Кроме того метод является визуальным и сложным для алгоритмизации. Метод минимизации Квайна – Мак-Класки (далее просто Мак-Класки) является систематичным и его легко алгоритмизировать. Кроме того в нем отсутствуют ограничения на число переменных логической функции.
2
Метод Мак-Класки состоит из двух основных этапов: 1.Нахождение всех простых импликант логической функции, используя правило склеивания 2. Минимизации полученного множества простых импликант (задача нахождения оптимального покрытия) 10. Законы склеивания: a)(A & B) (A & B) A b)(A B) & (A B) A
3
Метод Мак-Класки. 1-ый этап. Разделить двоичные векторы области единиц логической функции на секции в соответствии с их индексами. Индекс двоичного вектора = число единиц, входящих в состав этого вектора. Составить таблицу интервалов, используя правило склеивания. Склеивать между собой только те двоичные векторы, которые отличаются друг от друга только в одной координате (ближайшие векторы). Склеивание происходит по этой координате. Ближайшие векторы могут находится только в соседних секциях таблицы. В конце первого этапа получают все простые импликанты логической функции.
4
В ходе второго этапа полученное множество простых импликант минимизируют, т.е. выбирают минимальное количество простых импликант, которое позволяет покрыть всю область единиц логической функции (типичная задача нахождения оптимального покрытия). Метод Мак-Класки. 2-ой этап.
5
1-ый этап – нахождение всех простых импликант логической функции. Пример 5.1 пусть задана логическая функция f (X 1, X 2, X 3, Х 4 ) = (0,1,2,5,6,7,8,9,10,14) 1 Найти МДНФ методом Мак-Класки. Решение: Выпишем двоичные векторы области единиц логической функции и найдем их индексы V 1 (X 1, X 2, X 3,Х 4 ) ={(0000), (0001), (0010), (0101), (0110), (0111), (1000), (1001), (1010), (1110),} Разделим двоичные векторы на секции в соответствии с их индексами, получим таблицу:
6
индексинтервал Таблица интервалов: Склеиваем между собой ближайшие векторы соседних секций пока это возможно.
7
индексинтервалиндексинтер- вал индексинтервалобозн A A A Все оставшиеся не склеенными интервалы образуют множество всех простых импликант логической функции. А1 А2 А3
8
2-ой этап – минимизация полученного множества простых импликант логической функции. Импли- кант A1 0-01xx A2 01-1xx A3 011-xx A4 -00-xxxx A5 -0-0xxxx A6 —10xxxx Вся область единиц должна быть покрыта простыми импликантами (в каждом столбце хотя бы один «х»), и их должно быть минимальное количество.
9
Оптимальное покрытие: А2, А4, А6. МДНФ: А2 А4 А6 = X 1 &X 2 &X 4 X 2 & X 3 X 3 & X 4.
10
Сходство методов Мак-Класки и Карно: 1.Векторы соседних клеток карты Карно = векторы соседних секций таблицы склеивания метода Мак- Класки. 2.Объдинение в контуры на карте Карно = склеивание в методе Мак-Класки. 3.Нахождение МДНФ и МКНФ методом Мак-Класки отличаются между собой по таким же принципам как и в методе Карно.
12
= (X 1 X 2 X 4 ) & ( X 1 X 2 X 3 ) & ( X 3 X 4 )
Булевы функции
Параметры решения
►f(x,y,z) = x → y!zx → y!zУпростить выражение
(...) — ввод скобок, x -отрицание (NOT, !, ¬), & — логическое И, AND, ∧, *, v — логическое ИЛИ, OR, ∨, = — эквивалентность, ˜, ≡, , ⊕ — сумма по модулю 2, | — штрих Шеффера, И-НЕ, AND-NOT, ↓ — стрелка Пирса, ИЛИ-НЕ, OR-NOT, ← — обратная импликация.
(…)
x
˅
&
=
→
⊕
|
↓
←
Clear
Для вложенного отрицания необходимо использовать знак !. Например, 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 — ложно.
булеву функциюдизъюнкцииконъюнкцииотрицания
Область определения БФ E – конечное множество, поэтому БФ можно задать с помощью таблицы истинности, содержащей |E|=2n строк. Столбец значений БФ при этом представляет собой двоичное слово длиной 2n. Поэтому количество различных БФ n переменных равно 22n.
-
x f
0 1
1 0 -
x y f
0 0 0
0 1 0
1 0 0
1 1 1 -
x y f
0 0 0
0 1 1
1 0 1
1 1 1 -
x y f
0 0 0
0 1 1
1 0 1
1 1 0 -
x y f
0 0 1
0 1 0
1 0 0
1 1 0 -
x y f
0 0 1
0 1 0
1 0 0
1 1 1 -
x y f
0 0 1
0 1 1
1 0 0
1 1 1 -
x y f
0 0 1
0 1 1
1 0 1
1 1 0
Основные равносильности логики высказываний
| Название | Формула |
| Закон исключенного третьего | X v !X ≡ И |
| Закон противоречия | X & !X ≡ Л |
| Закон коммутативности | X & Y ≡ Y & XX 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&ZX 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 ≡ XX&(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
Выбор минимального элемента
В сокращённой импликантной матрице (таблица 7) нужно выбрать минимально возможную
совокупность строк, которая включает метки во всех столбцах («покрывает» все оставшиеся в таблице
минтермы). Дизъюнкция простых импликант, соответствующих строкам этой совокупности, а также ранее
вычеркнутых существенных импликант, образует тупиковую ДНФ. В общем случае полных покрытий с одинаковым
числом строк, а значит, и тупиковых ДНФ может быть несколько.
Из матрицы (таблица 7) видно, что минимальное покрытие не исключённых ранее минтермов
обеспечивает простая импликанта
либо пара импликант и
. С учётом ранее выявленных
существенных импликант получаем две тупиковые ДНФ:
;
.
Минимизация булевых функций
В данном сервисе для минимизации булевых функций используются метод Квайна и карт Карно-Вейча. После получения минимальной формы имеется возможность заново построить логическую схему. Если исходная схема понадобится в дальнейшем, то ее можно предварительно сохранить (меню Действия/Сохранить).
- Kx v K ≡ K — тождество поглощения;
- Kx v Kx ≡ K — тождество склеивания;
- Kx v Ky ≡ K(xvy) — дистрибутивный закон,
Kiiii
Метод карт Карно
Склеить можно как целиком всю карту, либо только выделенные единицы (меню Операции). ►
Удалить
Операции
- Сохранить как docx
- Сохранить как png
Количество переменныхСетка
После минимизации можно получить логическую схему функции и построить таблицу истинности (кнопка Далее)
Далее
Этот метод используется для БФ не более, чем с шестью аргументами и основан на тождестве склеивания: Kx v Kx ≡ K — две элементарные конъюнкции (ЭК) склеиваются, если они отличаются только знаком инверсии одного аргумента. Чтобы облегчить нахождение таких пар (четверок, восьмерок,…) склеивающихся ЭК, используют специальное представление БФ в виде таблицы – карты Карно (другое название — диаграмма Вейча). Чтобы заполнить карту Карно необходимо щелкнуть левой кнопкой мышки на соответствующую ячейку.
Карта Карно обладает той особенностью, что две ПЭК, соответствующие соседним клеткам карты, отличаются знаком инверсии только одного аргумента, т.е. их можно склеивать. Причем соседними являются не только клетки, например, с номерами 1 и 3, но и клетки с номерами 12 и 8, 12 и 4, т.е. карту можно «сворачивать» в цилиндр, соединяя горизонтальные (вертикальные) ее границы.
Две единицы «склеиваются» каждый раз, когда они стоят рядом в строке или столбце (карту можно свернуть в цилиндр). В результате склеивания число букв, входящих в ПЭК, уменьшается на единицу.
Нахождение существенных импликант и ислючение связанных с ними строк и столбцов
Присутствие в столбце только одной метки означает, что простая импликанта строки, где
стоит эта метка, является существенной или базисной импликантой, то есть обязательно войдёт в минимальную
ДНФ. Строка, содержащая существенную импликанту, а также столбцы, на пересечении с которыми в этой строке
стоит метка избыточности, вычёркиваются. Это позволяет упростить последующие шаги минимизации. Если
после упомянутого вычёркивания в оставшейся части таблицы появятся строки, не содержащие меток или содержащие
идентично расположенные метки, то такие строки также вычёркиваются. В последнем случае оставляют одну —
ту, в которой простая импликанта имеет наименьший ранг среди остальных вычёркиваемых импликант.
Таблица 5. Удаление из импликантной матрицы существенных импликант и покрываемых
ими минтермов.
| 0, 1, 8, 9 | |
| 0, 2, 8, 10 | |
| 2, 6, 10, 14 | |
| 1, 5 | |
| 5, 7 | |
| 6, 7 |
| 1 | 2 | 5 | 6 | 7 | 8 | 9 | 10 | 14 | |
| √ | √ | √ | √ | ||||||
| √ | √ | √ | √ | ||||||
| √ | √ | √ | √ | ||||||
| √ | √ | ||||||||
| √ | √ | ||||||||
| √ | √ |
В нашей функции по одной метке имеют столбцы 9 и 14. Следовательно, имеют место две
существенные импликанты: и
. С учётом этого поиск остальных
импликант минимальной ДНФ можно упростить, исключив строки с существенными импликантами, а также
перекрываемые ими столбцы. Это показано в таблице . (удаляемые столбцы закрашены).
После вычёркивания существенных импликант и
, а также столбцов с
минтермами, которые поглощаются этими импликантами, получим сокращённую матрицу (таблица 6).
Таблица 6. Сокращённая импликантная матрица
| 5 | 7 | ||
| 0, 2, 8, 10 | |||
| 1, 5 | √ | ||
| 5, 7 | √ | √ | |
| 6, 7 | √ |
Первая строка не содержит меток избыточности, поэтому её можно удалить. (таблица 7)
Таблица 7. Сокращённая импликантная матрица после исключения пустых строк.
| 5 | 7 | ||
| 1, 5 | √ | ||
| 5, 7 | √ | √ | |
| 6, 7 | √ |