Диаграмма вейча 4 переменных

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

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

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

Четыре верхних клетки диаграммы соответствуют двоичным наборам, в которых переменная х₁ принимает значение 0; четыре нижних клетки соответствуют наборам, в которых переменная х₁ принимает значение 1.

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

Четыре центральные клетки соответствуют наборам, в которых переменная х₃ принимает значения 1, а в левом и правом крайних столбцах находятся клетки, в которых переменная х₃ принимает значение 0.

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

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

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

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

Для диаграммы Вейча четырех переменных (рис. 2) соседними клетками будут также клетки, расположенные в верхних и нижних строках для одноименных столбцов.

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

Каждой такой группе будет соответствовать группа склеивающихся конституент единицы. Причем количество клеток, входящих в одну группу, равно 2 k (где k = 1, 2, 3, . ), а каждая клетка, входящая в группу, должна иметь k соседних клеток.

Для получения минимальной ДНФ достаточно выполнить следующие условия:

каждая единичная клетка должна входить хотя бы в одну группу (при этом одна и та же клетка может входить в несколько групп);

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

количество групп должно быть минимальным.

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

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

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

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

Группе, состоящей из 2 k клеток, соответствует конъюнкция из n – k букв, где n — число переменных в исходной булевой функции.

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

№ набора

х1

х2

х3

z

СДНФ для этой функции

.

Составим диаграмму Вейча (рис. 4)

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

1) склеивается с по переменной x₁ – образуется импликанта ; склеивается с по переменной x₁ – образуется импликанта ; склеивается с по переменной x₃ – образуется импликанта . Отсюда получается первая минимальная ДНФ

;

2) склеивается с по переменной x₁ – образуется импликанта ; склеивается с по переменной x₁ – образуется импликанта ; склеивается с по переменной x₂ – образуется импликанта . Отсюда получается вторая минимальная ДНФ

.

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

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

Диаграмма Вейча для этого случая приведена на рис. 5.

Здесь возможно склеивание по четырем конституентам единицы:

; ; ; склеиваются по переменным х₂ и х₄ – образуется импликанта ;

; ; ; склеиваются по переменным х₂ и х₃ – образуется импликанта ;

; ; ; склеиваются по переменным х₁ и х₄ – образуется импликанта .

Таким образом, окончательное выражение для минимальной ДНФ:

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

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

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

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

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

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

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

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Только сон приблежает студента к концу лекции. А чужой храп его отдаляет. 8832 – | 7545 – или читать все.

78.85.5.224 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)
очень нужно

" Метод позволяет быстро получать минимальные ДНФ булевой функции f небольшого числа переменных. В основе метода лежит задание булевых функций диаграммами некоторого специального вида, получившими название диаграмм Вейча. Для булевой функции двух переменных диаграмма Вейча имеет вид (табл. 4.4.1).

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

Добавление к ней еще такой же таблицы дает диаграмму для функции 4-х переменных (табл. 4.4.3).

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

• каждой клетке диаграммы соответствует свой набор;
• соседние наборы расположены рядом в строке либо в столбце.

Соседними наборами называются наборы, отличающиеся одной компонентой. Напомним, что конституенты, соответствующие таким наборам, склеиваются (см. метод Квайна- Мак-Класки). Например, для функции, заданной табл. 9.22,

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

О паре единиц в правой части диаграммы можно сказать то же самое:

Отметим, что получающееся элементарное произведение легко определить сразу по диаграмме: это произведение переменных, принимающих одно и то же значение в обеих клетках.
Еще одно важное замечание: столбцы, расположенные по краям диаграммы, тоже считаются соседними. Для нашего примера это означает, что имеет место еще одно склеивание, в результате которого, следуя указанному правилу, получаем элементарное произведение x₂/x₃ Из рассмотренных ранее методов нам известно, что возможно дальнейшее склеивание получаемых элементарных произведений. На диаграммах Вейча они тоже располагаются рядом. Общее правило склеивания на диаграммах Вейча можно сформулировать следующим образом: склеиванию подлежат прямоугольные конфигурации, заполненные единицами и содержащие число клеток, являющееся степенью 2. Получающееся новое элементарное произведение определяется как произведение переменных, не меняющих своего значения на всех склеиваемых наборах. Число m оставшихся переменных в элементарном произведении определяется легко:

m = n – log₂M

где n – число переменных функции, М – число склеиваемых наборов. Метод широко используется на практике, благодаря простоте и удобству. После небольшой тренировки достигается элементарный навык определения минимальной ДНФ по диаграмме "с первого взгляда". Минимизация булевой функции заключается в нахождении минимального накрытия всех единиц диаграммы Вейча блоками из единиц (указанной конфигурации), расположенных в соседних клетках диаграммы. При этом всегда считается, что левый край диаграммы Bейча 4-х переменных примыкает к ее правому краю, а верхний oкрай диаграммы примыкает к нижнему ее краю. После получения минимального накрытия всех единиц диаграммы Вейча, минимальная ДНФ булевой функции записывается как дизъюнкция элементарных конъюнкций, соответствующих выделенным блокам единиц в диаграмме. Рассмотрим несколько примеров.

Пример. Булева функция f имеет следующую СДНФ:

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

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

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

Рис. 2.1. Диаграмма Вейча для функции двух переменных

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

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

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

Рис. 2.2. Диаграммы Вейча для некторых функций двух переменных

Это обстоятельство используют для получения минимальных ДНФ и КНФ.

Рассмотрим диаграммы Вейча переключательной функции f₁₃(х₁; x₂) =

Это выражение, являющееся минимальной формой функции f₁₃(x₁;x₂), получено путем склеивания конституент единиц, обведенных овалами.

Для 3-х переменных:

Рис. 2.4. Иллюстрации к построению диаграмм Вейча для функций трех пе­ре­менных: а – размещение конституент единицы; б – размещение кон­ституент нуля; в – соответствие клеток диаграммы и наборов значений аргументов

Эти диаграм­мы следует пред­став­­лять в виде ци­­линд­ра, образо­ванного соедине­ни­ем граней пер­вой и по­след­ней ко­ло­нок.

Тогда любая пара склеивающихся между собой конституент будет находится в соседних смежных клетках.

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

Рис. 2.5. Диаграммы Вейча для некторых функций, представимых двух­буквенными выражениями: а – функция x₁ x₂; б – функция x₃; в – функция x₃; г – функция ; д – функция x₁ ; е – функция x₁

Четыре единицы, расположенные в соседних смежных клетках, выражаются од­ной буквой.

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

одной переменной: а – функция x₃; б – функция ; в – функция

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

Если функция задана в СКНФ, следует записать нули в клетки диа­грам­мы, которые соответствуют конституентам нуля, входящим в данную функ­цию, а в остальных клетках записать единицы.

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

Пример 2.3.

f(x₁, x₂, x₃) = .

Данная функция имеет единственную минимальную форму, поскольку при любом другом способе объединения единиц количество букв в ДНФ уве­ли­чивается.

а – f(x₁, x₂, x₃) = x₁ x₂Ú x₁ x₃Ú ; б – f(x₁, x₂, x₃) = x₁ x₂Ú x₃Ú .

Для получения минимальной КНФ следует объединить нули пере­клю­ча­тель­ной функции: две конституенты нуля соответствуют клеткам, объе­ди­ненным пунктиром, склеиваются по x₃ и представляются импликантой x₁Ú , а оставшийся нуль – конституентой Ú x₂Ú x₃. Поэтому минимальная КНФ будет иметь вид

f(x₁, x₂, x₃) = (x₁Ú )( Ú x₂Ú x₃).

Минимальная КНФ имеет меньше букв, чем минимальная ДНФ.

Пример 2.5. Найти минимальную ДНФ функции

f(x₁, x₂, x₃) = .

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

Пример 2.6. Найти минимальную ДНФ функции

f(x₁, x₂, x₃) = .

Рис. 2.10. Варианты склеивания конституент, приводящие к различным

минимальным ДНФ: а – f(x₁, x₂, x₃) = ;

б – f(x₁, x₂, x₃) = .

Пример 2.7. Найти минимальную ДНФ функции

f(x₁, x₂, x₃) = .

Рис. 2.11. Диаграмма Вейча для переключательной функции, у которой совершенная, сокращенная, тупиковая и минимальная формы совпадают

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

Рис. 2.12. Диаграмма Вейча для функции четырех переменных

Одной букве соответ­ству­ет восемь единиц, рас­по­ло­женных в соседних клет­ках; произведению, включаю­ще­му две переменные, соот­вет­ствуют че­тыре со­сед­ние еди­ницы; про­изведению трех пе­ре­мен­ных – две и произ­ве­дению че­тырех переменных – одна еди­ница.

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

Пример 2.8.

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

Диаграмма Вейча для функции пяти аргументов имеет следующий вид:

Рис. 2.14. Диаграмма Вейча для функций пяти переменных

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

Следует помнить, что для букв , x₄, и x₅ "соседние" клетки ока­зы­ваются разнесенными.

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

Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰).

Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ – конструкции, предназначен­ные для поддерживания проводов на необходимой высоте над землей, водой.