Как составить карту вейча

Метод диаграмм Вейча

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

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

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

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

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

Рис. 1.

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

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

Рис. 2.

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

Рис. 3.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 1

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

.

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

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Метод минимизирующих карт (карты Карно, диаграммыВейча)

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

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

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

Функцию в СДНФ наносят на карту, отмечая, например, знаком “1” ячейки, соответствующие тем наборам, на которых ФАЛ равна единице, т.е. в СДНФ функции эта ячейка соответствует одному изееминтермов. Остальные ячейки отмечаются знаком “0”.

Если данную таблицу рассматривать как цилиндр, образованный соединением первой и последней колонок, то тогда склеивающиеся между собой конституэнты единицы или нуля в диаграммах Вейча будут расположены в соседних клетках. При этом прямоугольники, покрывающие 2^kсоседних клеток, описывают имликанту (имплиценту), имеющую ранг (n-k), где n – число переменных, от которых зависит функция.

Клетки, содержащие в диаграмме Вейча единицы, будем называть 1-клетками, а клетки, содержащие нули – 0-клетками.

Основное свойство диаграмм Вейча заключается в том, что любая первичная импликанта ранга (n-m) образует на ней прямоугольник и только прямоугольник 1-клеток площадью 2^m, где n – количество переменных, от которых зависит функция. Такие прямоугольники называют m-кубами (m=0,1,…,n.; 0-кубу соответствует минтерм, а n-кубу – константа “единица”). Так любая пара единиц в соседних клетках диаграммы Вейча для логической функции трех переменных представляется импликантой второго ранга. Четыре единицы, образующие прямоугольник, выражаются одной переменной (с отрицанием или без него).

Чтобы записать первичную импликанту, представляющую собой некий m-куб на диаграмме Вейча, необходимо просто составить конъюнкцию тех переменных, которые в пределах данного m-куба сохраняют постоянные значения (только прямые или только инверсные).

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

При получении МДНФ с помощью диаграммы Вейча необходимо обратить внимание на следующее:

• m-кубу, покрывающему2^m 1-клеток, соответствует первичная импликанта, не зависящая от m переменных, причем исключаются те m переменных, которые в прямоугольной области на диаграмме Вейча, состоящей из 1-клеток, имеют различное значение (прямое и инверсное);
• прямоугольные области на диаграмме Вейча, используемые при минимизации, могут состоять только из 2^m соседних клеток, где m = 0,1,…,n;
• каждая клетка на диаграмме Вейча, вне зависимости от способа разметки этой диаграммы, имеет ровно n соседних клеток; в связи с этим диаграмма Вейча представляется нанесенной на поверхность соответствующего тела (цилиндра – для случая трех переменных, тора – для случая четырех переменных);
• поиск минимального покрытия 1-клеток следует начинать с выбора тех 1-клеток, которые могут войти в один и только один m-куб; если после этого на диаграмме остаются 1 клетки, не вошедшие ни в один из m-кубов, то следует рассмотреть несколько вариантов покрытий этих клеток; с целью минимизации результата оставшиеся 1-клетки покрываются, по возможности, m-кубами максимального размера.

Получение минимальной КНФ проводится аналогичным образом по отношению к 0 клеткам.

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

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

Зачем это нужно?

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

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

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

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

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

Карты Карно были изобретены в 1952 Эдвардом В. Вейчем и усовершенствованы в 1953 Морисом Карно, физиком из «Bell Labs», и были призваны помочь упростить цифровые электронные схемы.

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

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

Возможность поглощения следует из очевидных равенств

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

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

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

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

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

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

Для упрощения работы с булевыми функциями большого числа переменных был предложен следующий удобный приём. Куб, представляющий собой структуру термов, разворачивается на плоскость как показано на рисунке. Таким образом появляется возможность представлять булевы функции с числом переменных больше двух в виде плоской таблицы. При этом следует помнить, что порядок кодов термов в таблице (00 01 11 10) не соответствует порядку следования двоичных чисел, а клетки, находящиеся в крайних столбцах таблицы, соседствуют между собой.

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

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

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

1. Объединяем смежные клетки содержащие единицы в область, так чтобы одна область содержала 2ⁿ (n целое число = 0…) клеток(помним про то что крайние строки и столбцы являются соседними между собой), в области не должно находиться клеток содержащих нули;
2. Область должна располагаться симметрично оси(ей) (оси располагаются через каждые четыре клетки);
3. Не смежные области расположенные симметрично оси(ей) могут объединяться в одну;
4. Область должна быть как можно больше, а кол-во областей как можно меньше;
5. Области могут пересекаться;
6. Возможно несколько вариантов накрытия.

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

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

В формате КНФ:

Скачать материал

Скачать материал