Главная > Документ


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

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

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

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

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

Положение переменных, задающих координаты ячеек диаграммы Вейча, может быть иным. Однако при этом должна обеспечиваться возможность задания на диаграмме всех наборов переменных. Естественно, при таких изменениях поменяются номера ячеек, но на процесс и результат минимизации ФАЛ данное обстоятельство влияния не окажет.

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

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

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

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

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

прямоугольные области на диаграмме Вейча, используемые при минимизации, могут состоять только из 2m соседних клеток, где m = 0,1,…,n;

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

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

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

Пример 3.4

Получить методом диаграмм Вейча минимальную ДНФ следующей логической функции:

f(x,y,z)СДНФ = (0,1,2,5,7)

Решение

Этап 1.

Занести значение функции на диаграмму Вейча. В связи с тем что ФАЛ задана в виде сокращенной записи совершенной дизъюнктивной нор­мальной формы, для ее представления в виде диаграммы Вейча целесообразно использовать вид этой диаграммы, представленный на рис. 3.1,а. При этом, так как по заданию предполагается получение лишь минимальной дизъюнктивной нормальной формы, для улучшения восприятия диаграммы можно отметить лишь те ячейки, которые соответствуют конституэнтам единицы, предполагая, что ячейки, оставшиеся незаполненными, соответствуют нулевым значениям ФАЛ:

y

¯y

x

1

1

¯x

1

1

1

¯z

z

¯z

Этап 2.

Отметить на диаграмме 1-клетки, входящие в единственный mкуб. Выбрать для них покрытие в виде m-куба максимального размера. При этом одна 1-клетка может входить в не­сколько mкубов одновременно. Разорван­ный овал, накрывающий клетки 2 и 0, соответствует покрытию со­сед­них клеток при представлении таблицы в виде цилиндра с соединенными левой и правой колонками:

y

¯y

x

1

1

¯x

1

1

1

¯z

z

¯z

Этап 3.

Не вошедшую ни в один из m-кубов 1-клетку можно включить в один из 2-кубов либо с 1-клеткой, стоящей справа от нее, либо с 1‑клеткой, стоящей выше нее. Так как оба альтернативных m-куба имеют одинаковый размер, то в результате получим две ми­ни­маль­ные дизъюнктивные нормальные формы:

y

¯y

x

1

1

¯x

1

1

1

¯z

z

¯z

и

y

¯y

x

1

1

¯x

1

1

1

¯z

z

¯z

Этап 4.

Представить полученные m-кубы в виде минимальных дизъюнктивных нор­маль­ных форм:

f(x,y,z)1МДНФ = xz v ¯x ¯z v ¯x ¯y

f(x,y,z)2МДНФ = xz v ¯x ¯z v z ¯y

Пример 3.5

Получить методом диаграмм Вейча минимальную ДНФ следующей логической функции:

f(x,y,z)СДНФ = xyz v x¯y ¯z v ¯xy¯z v ¯x ¯y¯z

Решение

Этап 1.

Занести значение функции на диаграмму Вейча согласно ее представлению на рис. 3.1,б:

y

¯y

x

1

1

¯x

1

1

¯z

z

¯z

Этап 2.

Отметить на диаграмме 1-клетки, входящие в единственный mкуб:

y

¯y

x

1

1

¯x

1

1

¯z

z

¯z

Этап 3.

Так как на диаграмме не осталось непокрытых 1-клеток, то ми­нимальная ДНФ будет иметь вид:

f(x,y,z)МДНФ = xyz v ¯x ¯z v ¯¯y ¯z

Пример 3.6

Получить методом диаграмм Вейча минимальную КНФ следующей логической функции:

f(x,y,z)СДНФ = ∏(0,2,5,6,7)

Решение

Этап 1.

Занести значение функции на диаграмму Вейча согласно ее представлению на рис. 3.1,а. При этом в ячейки, имеющие номера, перечисленные в сокращенной записи СКНФ функции, заносятся нули, а остальные ячейки можно оставить незаполненными:

y

¯y

x

0

0

0

¯x

0

0

¯z

z

¯z

Этап 2.

Отметить на диаграмме 0-клетки, входящие в единственный mкуб:

y

¯y

x

0

0

0

¯x

0

0

¯z

z

¯z

Этап 3.

Не вошедшую ни в один из m-кубов 0-клетку можно включить в один из 1-кубов либо с 0-клеткой, стоящей справа от нее, либо с 0‑клеткой, стоящей ниже ее. В результате получим две мини­мальные конъюнктивные нормальные формы:

y

¯y

x

0

0

0

¯x

0

0

¯z

z

¯z

f(x,y,z)1МКНФ = (¯x v ¯z) & (x v z) & (¯x v ¯y)

y

¯y

x

0

0

0

¯x

0

0

¯z

z

¯z

f(x,y,z)2МКНФ = (¯x v ¯z) & (x v z) & (¯¯y v z)

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

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

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




Скачать документ

Похожие документы:

  1. Библиографический указатель из фонда научной библиотеки

    Библиографический указатель
    ... -технических работ. МИФИ - городу Москве:Каталог.-М.,2001.-Б.п. 195. Московский государственный инженерно-физический ... .-26с. 4553. Гуров В.В. Синтезкомбинационныхсхем в примерах и решениях: Учеб.пособие/Гуров В.В.-М.:МИФИ,2001.-56с. 4554. Гусев ...
  2. Москва 2011 1 Цели и задачи дисциплины (3)

    Рабочая программа
    ... коммуникационные технологии Москва 2011 1. ... схемотехнических решений и ... и синтезасхем ЭВМ. Анализ комбинационныхсхем. Синтезкомбинационныхсхем: мультиплексор ... СПб.: БХВ-Петербург, 2001. 2. Пухальский Г.И., Новосельцева ... также примеры оценочных ...
  3. Программа обучения студентов ( syllabus ) (3)

    Программа обучения студентов
    ... домашних заданий, самостоятельное решение задач), итоги индивидуальных ... А.В. и др. «Информатика». – Москва.: ACADEMA, 1999 г. Информатика/ Под ... ДИАЛОГ-МИФИ,1993 Гуров В.В. Синтезкомбинационныхсхем в примерах М.: МИФИ, 2001 Гуров В.В., Ленский О.Д., ...
  4. РУССКАЯ ВЕРОЯТНОСТНАЯ ЛОГИКА

    Документ
    ... -ЭЛЕКТРОНЩИКА Москва 2008 ... Русская механика» А.Ф.Черняева (М.:2001 – 592с.) и « ... 1.4. СинтезкомбинационныхсхемСинтезкомбинационныхсхем можно проиллюстрировать решением простой ... Пример 1. «Энциклопедия - Россия-Он-Лайн» излагает примеррешения ...
  5. РУССКАЯ ВЕРОЯТНОСТНАЯ ЛОГИКА (2)

    Документ
    ... -ЭЛЕКТРОНЩИКА Москва 2008 ... Русская механика» А.Ф.Черняева (М.:2001 – 592с.) и « ... 1.4. СинтезкомбинационныхсхемСинтезкомбинационныхсхем можно проиллюстрировать решением простой ... Пример 1. «Энциклопедия - Россия-Он-Лайн» излагает примеррешения ...

Другие похожие документы..