Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Метод диаграмм Вейча.
" Метод позволяет быстро получать минимальные ДНФ булевой функции f небольшого числа переменных. В основе метода лежит задание булевых функций диаграммами некоторого специального вида, получившими название диаграмм Вейча. Для булевой функции двух переменных диаграмма Вейча имеет вид (табл. 4.4.1).
Каждая клетка диаграммы соответствует набору переменных булевой функции в ее таблице истинности. В (табл. 4.4.1) это соответствие показано, В клетке диаграммы Вейча ставится единица, если булева функция принимает единичное значение на соответствующем наборе. Нулевые значения булевой функции в диаграмме Вейча не ставятся. Для булевой функции трех переменных диаграмма Вейча имеет следующий вид (табл. 4.4.2).
Добавление к ней еще такой же таблицы дает диаграмму для функции 4-х переменных (табл. 4.4.3).
Таким же образом, т. е. приписыванием еще одной диаграммы 3-х переменных к только что рассмотренной, можно получить диаграмму для функции 5-ти переменных и т. д., однако диаграммы для функций с числом переменных больше 4-х используются редко. Для приведенных диаграмм характерно следующее:
каждой клетке диаграммы соответствует свой набор;
соседние наборы расположены рядом в строке либо в столбце.
Соседними наборами называются наборы, отличающиеся одной компонентой. Напомним, что конституенты, соответствующие таким наборам, склеиваются (см. метод Квайна- Мак-Класки). Например, для функции, заданной табл. 9.22,
конституенты, соответствующие паре единиц в левой части таблицы, склеиваются и порождают элементарное произведение из 2-х букв:
х1х2/х3 v x1x2x 3 = x1x2
О паре единиц в правой части диаграммы можно сказать то же самое:
/х1х2/х3 v /x1/x2/x 3 = /x1/x3
Отметим, что получающееся элементарное произведение легко определить сразу по диаграмме: это произведение переменных, принимающих одно и то же значение в обеих клетках.
Еще одно важное замечание: столбцы, расположенные по краям диаграммы, тоже считаются соседними. Для нашего примера это означает, что имеет место еще одно склеивание, в результате которого, следуя указанному правилу, получаем элементарное произведение x2/x3 Из рассмотренных ранее методов нам известно, что возможно дальнейшее склеивание получаемых элементарных произведений. На диаграммах Вейча они тоже располагаются рядом. Общее правило склеивания на диаграммах Вейча можно сформулировать следующим образом: склеиванию подлежат прямоугольные конфигурации, заполненные единицами и содержащие число клеток, являющееся степенью 2. Получающееся новое элементарное произведение определяется как произведение переменных, не меняющих своего значения на всех склеиваемых наборах. Число m оставшихся переменных в элементарном произведении определяется легко:
m = n - log2M
где n - число переменных функции, М - число склеиваемых наборов. Метод широко используется на практике, благодаря простоте и удобству. После небольшой тренировки достигается элементарный навык определения минимальной ДНФ по диаграмме "с первого взгляда". Минимизация булевой функции заключается в нахождении минимального накрытия всех единиц диаграммы Вейча блоками из единиц (указанной конфигурации), расположенных в соседних клетках диаграммы. При этом всегда считается, что левый край диаграммы Bейча 4-х переменных примыкает к ее правому краю, а верхний oкрай диаграммы примыкает к нижнему ее краю. После получения минимального накрытия всех единиц диаграммы Вейча, минимальная ДНФ булевой функции записывается как дизъюнкция элементарных конъюнкций, соответствующих выделенным блокам единиц в диаграмме. Рассмотрим несколько примеров.
Пример. Булева функция f имеет следующую СДНФ:
f=х1х2х3 v х1/х2х3 v /х1/х2/х3 v /х1/х2/х3 v х1х2/х3.
Найти минимальную ДНФ с помощью диаграммы Вейча. Диаграмма Вейча, соответствующая функции f, представлена в табл. 4.4.5. Минимальное накрытие всех единиц диаграммы возможно только блоками по две единицы. Каждому такому блоку соответствует своя конъюнкция, как показано в табл. 4.4.5.
Следовательно, минимальная ДНФ функции имеет вид:
f = х1х2 v /х1/х2 v х1х3.
Пример.
f1=х1х2х3 v /х1х4.
f2=х1х2х4 v х2х3/х4 v х1х3 v /х2х3х4 v х1х2х3x4.
f3=х3/х4 v /х3х4.
f4=/х3х4 v /х1х4 v х1х3/х4.
f5=х3 v х4.
f6=х3х4 v /х3/х4 v х1х2х3.
Опубликовано 01.09.2013 13:45 | Автор: Сергей Балденко
Это эквивалентные понятия, обозначающие один и тот же способ минимизации булевых функций. Этот способ является графическим. Его предложил в 1952 Эдвард В. Вейч, а доработал и усовершенствовал, немного позже в 1953, Морис Карно.
Итак, карты Карно для функций 1-ой, 2-х, 3-х переменных выглядят вот так:
Исходным материалом для работы с данным графическим методом минимизации возьмем известную нам таблицу истинности, хотя в принципе карты Карно (диаграммы Вейча) можно назвать упрощенной таблицей истинности, ну ничего страшного если немного попрактикуемся. В качестве примера используем функцию 4-х переменных.
Таблица истинности будет выглядеть вот так:
Исходя из данной таблицы, получим СДНФ, которая будет выглядеть таким образом:
Следующим шагом минимизации функции будет заполнение соответствующих клеток карты Карно (диаграммы Вейча). Для функции 4-х переменных она имеет вид поля с ячейками четыре на четыре.
На основании СДНФ заполним соответствующие ячейки. Получится вот такой вид карты Карно:
Далее очень важным моментом для понимания является осознание того, что данная карта не является квадратом или прямоугольником, а является цилиндром, сгибающимся как по горизонтали, так и по вертикали, а ячейки находящиеся по краям, тоже имеют соседей как слева, так и справа.
Выглядит это примерно вот так:
Верх и низ цилиндра тоже соседи.
Принимая во внимание свойства “цилиндра” произведем заключительный этап минимизации логической функции, т.е. произведем склеивание единиц. При выполнении этого процесса количество склеиваемых единиц должно быть кратно 2 и изменять значение “истина (1)” “ложь (0)”, может только одна переменная. На рисунке также обозначим комбинации склеивания единиц (каждая склейка имеет один цвет) и количество сомножителей им соответствующее. Отобразим это все на рисунке.
Таким образом, конечное минимизированное значение функции примет следующий вид:
Однако при рассмотрении способа минимизации логической функции при помощи карт Карно, практически всегда можно встретить изображение вот такого вида. Для нашего случая это будет выглядеть так:
Данная карта Карно – это точно такая, как и предложенная ранее с той лишь разницей, что по обеим сторонам представлен так называемый код Грея (т.е. соседние значения отличаются только одним разрядом). Склеивание “единиц” производится ранее описанным способом, т.е. по изменению одной переменной, и их количество должно быть кратно 2.
Таким вот графическим методом производится минимизация логических функций. Надеюсь, описал доступно и понятно.