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

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

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

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

Таблица 1. Таблица истинности к примеру

Номер набора	x1	x2	x3	x4	f
0	0	0	0	0	1
1	0	0	0	1	1
2	0	0	1	0	1
3	0	0	1	1	0
4	0	1	0	0	0
5	0	1	0	1	1
6	0	1	1	0	1
7	0	1	1	1	1
8	1	0	0	0	1
9	1	0	0	1	1
10	1	0	1	0	1
11	1	0	1	1	0
12	1	1	0	0	0
13	1	1	0	1	0
14	1	1	1	0	1
15	1	1	1	1	0

Перебирают все пары минтермов исходной совершенной дизъюнктивной нормальной формы, склеивая те из них, для которых эта операция возможна. При составлении пар любой из минтермов может быть испоользован многократно. Процедура повторяется и над полученными импликантами — опять проводятся операции склеивания. Процесс повторяется до тех пор, пока не останется ни одной импликанты, допускающей склеивания с другими. Такие импликанты называются простыми. Участовавшие в склеивании элементарные конъюнкции помечаются каким-либо символом, например, «*».

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

Таблица 2. Склеивание минтермов совершенной ДНФ

Номер набора	Минтермы
0	*
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

0	1	2	5	6	7	8	9	10	14
√	√					√	√
√		√				√		√
		√		√				√	√
	√		√
			√		√
				√	√

Импликантная матрица для рассматриваемого примера (таблица 4) содержит 6 строк (по числу простых импликант) и 10 столбцов (по числу минтермов исходной СДНФ).

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

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

Таблица 5. Удаление из импликантной матрицы существенных импликант и покрываемых ими минтермов.

0, 1, 8, 9
0, 2, 8, 10
2, 6, 10, 14
1, 5
5, 7
6, 7

0	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			√

В сокращённой импликантной матрице (таблица 7) нужно выбрать минимально возможную совокупность строк, которая включает метки во всех столбцах («покрывает» все оставшиеся в таблице минтермы). Дизъюнкция простых импликант, соответствующих строкам этой совокупности, а также ранее вычеркнутых существенных импликант, образует тупиковую ДНФ. В общем случае полных покрытий с одинаковым числом строк, а значит, и тупиковых ДНФ может быть несколько.

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

;

.

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

Коэффициент сложности первой из двух получившихся тупиковых форм равен 10, а второй — 14. По этой причине минимальной ДНФ следует признать первое выражение:

.

Нет времени вникать в решение? Можно заказать работу!

Пройти тест по теме Математическая логика

К началу страницы

Метод Квайна — Мак-Класки.

Метод Квайна — Мак-Класки. <==Back

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

• Основные понятия.
• Аналитическое представление булевых функций.
• Функционально полные системы будевых функций.
• Минимизация булевых функций.
  • Метод Квайна.
  • Метод Квайна — Мак-Класки.
  • Метод Блейка — Порецкого.
  • Метод диаграмм Вейча.
  • Минимизация коньюнктивных нормальных форм.
  • Метод Петрика.
  • Минимизация частично определенных булевых функций.
• Минимизация систем булевых функций.

Метод Квайна — Мак-Класки.

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

1. Все конституанты единицы из СДНФ булевой функции f записываются их двоичными номерами.
2. Все номера разбиваются на непересекающиеся группы. Признак образования i-й группы: i единиц в каждом двоичном номере конституенты единицы.
3. Склеивание производят только между номерами соседних групп. Склеиваемые номера отмечаются каким-либо знаком (зачеркиванием).
4. Склеивания производят всевозможные, как и в методе Квайна. Неотмеченные после склеивания номера являются простыми импликантами.

Нахождение минимальных ДНФ далее производится по импликантной матрице, как и в методе Квайна. Более подробно рассмотрим метод на примере решения следующей задачи: минимизировать методом Квайна — Мак-Класки булеву функцию f, заданную таблицей истинности 4.2.1.

Таблица 4.2.1
x4x3x2x1	f
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111	0 1 0 1 0 1 0 1 0 0 0 0 0 0 1 1

• В СДНФ функции f заменим все конституенты единицы их двоичными номерами:

f = 0001 v 0011 v 0101 v 0111 v 1110 v 1111.

• Образуем группы двоичных номеров. Признаком образования i — й группы является i единиц в двоичном номере конституенты единицы (табл. 4.2.2).

Таблица 4.2.1
Номер группы	Двоичные номера конституент единицы
0	—
1	0001
2	0011, 0101
3	0111, 1110
4	1111

• Склеим номера из соседних групп табл. 4.2.1. Склеиваемые номера вычеркнем (Прим. — выделяем цветом). Результаты склеивания занесем в табл. 4.2.2. Склеим номера из соседних групп табл. 4.2.2. Склеиваться могут только номера, имеющие звездочки в одинаковых позициях. Склеиваемые номера вычеркнем. Результаты склеивания занесем в табл. 4.2.3.

Таблица 4.2.2
Номер группы	Двоичные номера конституент единицы
1	00*1, 0*01
2	0*11, 01*1
3	*111, 111*

Таблица 4. 2.3
Номер группы	Двоичные номера конституент единицы
1	0**1

• Имеем три простые импликанты: *111, 111*, 0**1.

• Строим импликантную матрицу (табл. 4.2.4). По таблице определяем совокупность простых импликант — 0**I и 111*, соответствующую минимальной ДНФ. Для восстановления буквенного вида простой импликанты достаточно выписать произведения тех переменных, которые соответствуют сохранившимся двоичным цифрам.

Таблица 4.1.2
Простые импликанты	Конституенты единицы
	0001	0011	0101	0111	1110	1111
0**1	X	X	X	X
*111				X		X
111*					Х	Х

0**1 —> /x₁x₄;
111* —> x₁x₂x₃.

Заметим, что разбиение конституент на группы позволяет уменьшить число попарных сравнений при склеивании.»

Использованная литература:

1) «Прикладная теория цифровых автоматов»    Киев «Вища Школа» 1987
    К.Г. Самофалов, А.М. Романкевич, В.Н. Валуйский,
    Ю.С. Каневский, М.М. Пиневич
    страницы (200 — 201).

Метод Куайна МакКласки — GeeksforGeeks

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

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

Метод Куайна-МакКласки (QMC):

• Метод Куайна-МакКласки, также известный как метод табуляции, используется для минимизации булевых функций.
• Упрощает логическое выражение до упрощенной формы, используя простые импликанты.
• Этот метод удобен для упрощения логических выражений с более чем 4 входными переменными.
• Используется процедура автоматического упрощения.

Терминология:

Импликант : Импликант определяется как группа единиц (для minterm).

Основной импликант: Это самая большая возможная группа единиц (для minterm).

Импликант Essential Prime: Импликант Essential Prime — это группы, которые охватывают хотя бы один минтерм, который не может быть охвачен другими кандидатами.

  Примечание:  В этом методе используется преобразование десятичного числа в двоичное. 

Шаги для метода Куайна МакКласки:

1. Расположите заданные минтермы в порядке возрастания количества единиц в их двоичном представлении.
2. Возьмите минтермы из непрерывной группы, если для создания их пары нужно изменить только один бит.
3. Поместите символ «-» там, где есть соответствующее изменение бита, и оставьте остальные биты без изменений.
4. Повторяем шаги со 2 по 3, пока не получим все простые импликанты (когда все биты, присутствующие в таблице, различны).
5. Создайте таблицу основных импликантов, состоящую из основных импликантов (полученных минтермов) в виде строк и заданных минитермов (указанных в задаче) в виде столбцов.
6. Поместите «1» в минтермы (ячейки), которые покрываются каждым основным импликантом.
7. Обратите внимание на таблицу, если минтерм покрывается только одним первичным импликантом, то первичный импликант обязателен.
8. Добавьте основные импликанты простых чисел к упрощенной булевой функции.

Пример: Упростите, используя метод табулирования: F(A,B,C,D) =∑ m(0,1,2,4,6,8,9,11,13,15)

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

90 075

ТАБЛИЦА 1
Группа	Minterm	A	B	C	D
0	0	0 9 0094	0	0	0
1	1      2      4      8 90 094	0   0  0 1	0 0 1 0	0 90 002  1  0  0	1  0  0  0
2	6      9	0  1	1  0	1  0	0  1
3	11      13	1  1	0  1	1  0	1  1
4	15	1	1	1	1

Поскольку 0 не имеет 1 в своем представлении, он хранится в одной группе (0). Точно так же 1 2 4 и 8 содержат одну единицу в своем представлении, поэтому она сохраняется в следующей группе (1). 6 и 9в следующей группе (2), 11 и 13 в следующей группе (3), 15 в последней группе (4).

Теперь для таблицы 2 возьмите минтермы из последовательных групп (только одновременная группа), которые имеют только 1-битную разницу в их представлении, и сформируйте их пару, объединив их и создав группу пар, которые принадлежат к тем же группам. которые объединены (например, 0 из группы 0 и 1 из группы 1, поэтому он добавляется в группу 0. 0 принадлежит к группе 0 в таблице 1, а 2 принадлежит к группе 1 в таблице 1, поэтому он хранится в той же группе в таблице 2. Аналогичным образом составьте все возможные пары с помощью приведенной выше таблицы и отметьте – где есть битовая разница. 

9 0093

(11,15)

(13,15)

ТАБЛИЦА-2
Группа	Пара	A 90 074	B	C	D
0	(0,1) (0, 2) (0,4) (0,8)	0 0 0  –	0  0  –  0	0  –  0  0	–  0  0  0
1	(1,9)  (2,6) (4,6 ) (8,9)	–  0  0  1	0 900 05  –  1  0	0  1  –  0	1  0  0   –
2	(9,11) 9000 5 (9,13)	1 1	0  –	–  0	1  1
3	1 1	– 1	1 –	1 1

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

ТАБЛИЦА-3
Группа	Quad	A	B	C	D
0	(0,1,8,9)  (0,2,4,6)	–  0	0   –	0  –	–  0
1	(9,11,13,15)	1	–	–	1

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

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

90 090

ПРАЙМ ИМПЛИКАНТ ТАБЛИЦА
Minterms ⇢ Prime Implicants ⇣	0 1 2 4 6 8 9 11 13 15
B’C’ (0,1,8,9)	1  1              1   1
A’D'(0,2,4,6)	1      1  1  1
AD(9,11,13,15) 900 94	1    1    1     1
Упрощенное логическое значение функция = B’C’ + A’D’ + AD

B’C’ имеет упрощенную функцию, так как minterm 1 распространяется только на B’C’. Точно так же minterms 2,4,6 покрываются только A’D’, а minterms 11,13,15 покрываются только AD.

Пример: Упростите, используя метод табулирования: F(A,B,C,D,E,F,G) = ∑m(20,28,52,60)

Решение: Преобразуйте данные minterms в их двоичное представление и упорядочить их по количеству присутствующих в двоичном представлении.

0074									C	D	E	F	G
0	20	0	0	1	0	1	0	0
1	90 002      28      52	0 0	0 1	1 1 9000 5	1  0	1  1	0  0	0  0
2	60	0	1	1	1	1	0	0

Поскольку число 20 имеет 2 единицы в своем представлении, оно хранится в одной группе (0). Точно так же 28 и 52 содержат 3 единицы в своем представлении, поэтому оно сохраняется в следующей группе (1). 60 в следующей группе (2).

Теперь для таблицы 2 возьмите минтермы из последовательных групп (только одновременная группа), которые имеют только 1-битную разницу в их представлении, и сформируйте их пару, объединив их и создав группу пар, которые принадлежат к тем же группам. которые объединены (например, 20 из группы 0 и 28 из группы 1, поэтому они добавляются в группу 0. 20 принадлежит к группе 0 в таблице 1, а 52 принадлежит к группе 1 в таблице 1, поэтому они хранятся в той же группе в таблице 2. Аналогично составьте все возможные пары с помощью приведенной выше таблицы и отметьте – где немного отличается. 

90 093     0

									B	C	D	E	F	G
(20, 28)  (20,52)	0  0	0  –	1  1	– 0	1 1	0 0	0  0
1	(28,60)  (52,60)	0  0	–  1	1  1 9 0094	1  –	1  1	0 0	0  0

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

900 77 А 9009 3 (20,28,52,60)

ТАБЛИЦА-3
Группа	Quad	Б	C	D	E	F	G
0	0	–	1	–	1	0	0

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

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

A’CEF’G’ получается из таблицы 3, поскольку A, F, G содержат 0, поэтому A’F’G’, C и E содержат 1, поэтому CE.

Таблица основных импликантов 77 20 28 52 60
A’CEF’G'(20,28,52,60)	1    1    1     1
Упрощенная логическая функция = A’CEF’G’

A’CEF’G’ находится в упрощенной функции, поскольку это единственная первичная импликанта, которая охватывает все минтермс.

Преимущества метода Куайна МакКласки:

• Этот метод подходит для большого количества входных данных (n>4), для которых построение K-карты является утомительной задачей.
• Не требует распознавания образов.

Недостатки метода Куайна Маккласки:

• Вычислительная сложность этого метода высока.

Бесплатный облачный хостинг от OnWorks

Бесплатные серверы и рабочие станции

>>

• Бесплатный Linux
• Бесплатное вино

Загрузить приложения для Windows и Linux

>>

• Приложения для Linux
• Приложения для Windows

• 1

  LMS-Ютуб

  Воспроизведение видео с YouTube в LMS (перенос
  Triode на YouTbe API v3) Это
  приложение, которое также можно получить
  из
  https://sourceforge. net/projects/lms-y…

  Скачать LMS-YouTube

• 2

  дотнет SDK

  Функциональность

  Core, необходимая для создания проектов NET
  Core, которая совместно используется
  Visual Studio и CLI. Отсутствуют сборы
  или лицензионные расходы, в том числе для
  коммерческих…

  Загрузить dotnet SDK

• 3

  СпортМузыка

  Mit dem Programm kann man schnell und
  einfach Pausen bei Sportveranstaltungen
  Мит Musik berbrcken. Hierfr haben sie
  die Mglichkeit, folgende Wiedergabvaria…

  Скачать SportMusik

• 4

  DavMail POP/IMAP/SMTP/Caldav на Exchange

  Вы когда-нибудь хотели избавиться от Outlook?
  DavMail — это шлюз
  POP/IMAP/SMTP/Caldav/Carddav/LDAP
  , позволяющий пользователям использовать любой почтовый клиент
  с Exchange и Office 365, например

  Загрузка DavMail POP/IMAP/SMTP/Caldav на Exchange

• 5

  ДивФикс++

  DivFix++ — это ваше программное обеспечение для восстановления видео AVI и предварительного просмотра
  . Он предназначен для восстановления
  и файлов предварительного просмотра, которые находятся при загрузке
  с ed2k(emule), torrent, gnutella, ftp…

  Скачать DivFix++

• 6

  Сообщество JBoss

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

  Скачать сообщество JBoss

• 7

  Минпромторг

  Mindustry — это игра-песочница
  factory в жанре Tower Defense. Создайте цепочки поставок из
  конвейерных лент, чтобы заправлять турели,
  производить материалы для строительства и
  защищать свои …

  Скачать Mindustry

• Подробнее »

Команды Linux

• 1

  аа

  аа — астрономический альманах — рассчитать
  положения планет и звезд .

  No related posts.