1.11. Диаграммы Вейча

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

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

Рис. 1.1

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

номер данной клетки будет Определяться числом

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

Две клетки диаграммы Вейча называются соседними, если им соответствуют соседние минтермы. Для удобства отыскания контермов, покрывающих минтермов где число переменных), стороны диаграмм Вейча обозначают с помощью первичных термов так, чтобы как можно больше соседних клеток имели общую грань. Этому требованию могут удовлетворять многие варианты обозначений. При изображении диаграмм Вейча для трехмерного пространства на плоскости не все клетки, которым соответствуют соседние минтермы, имеют общую грань. Легко убедиться (см. что клеткам с номерами О и 4, 1 и 5 соответствуют соседние минтермы. Поэтому ДВ-3 следует представлять себе в виде трехмерной фигуры — цилиндра, получаемого путем совмещения боковых сторон Тогда клетки с номерами 0 и 4, 1 и 5 будут иметь общую грань.

Рассмотрим пример. Пусть требуется составить ДВ-3 для функции заданной табл. 1.5. Для этого в клетки с номерами (см. рис. 1.1,а) следует занести значения функции или 1, которые она принимает в точках (см. рис. 1.1,е). В § 1.8 было показано, что СДНФ данной функции имеет вид

т.е. в ДВ-3 (см. рис. 1.1,в) единицами заполняются клетки, соответствующие этим минтермам. Таким образом, имеется жесткая связь между таблицей истинности (см. табл. 1.5), аналитическим выражением для функции и диаграммой Вейча (см. рис. 1.1,в).

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

х (это соответствие указано в табл. 1.5). Легко заметить, что половине клеток ДВ-3, обозначенной через соответствуют значения другой половине клеток — значения Другая особенность взаимосвязи заключается в том, что минтермы, равные 1 в точке с номером в диаграмме Вейча указаны в явном виде, а в таблице истинности — в неявном (с помощью значений аргументов Например, строке с номером соответствуют значения Поэтому клетка с номером непосредственно обозначена через рис. 1.1,6).

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

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

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

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

должна войти хотя бы в один m-куб). Согласно идемпотентным законам любая 1-клетка может входить в несколько различных -кубов.

На рис. 1.1,в пунктиром обозначены два 1-куба, образованные 1-клетками с номерами 5 и 7, 1 и 5, которым соответствуют контермы а 1-клетка с номером 2 не имеет ни одной соседней 1-клетки, поэтому ей соответствует 0-куб, представляемый минтермом . МДНФ данной функции записывается в виде

Минимальная нормальная форма в базисе И-НЕ этой функции получается из МДНФ в соответствии с (1.80):

Для получения МКНФ функции следует найти МДНФ инверсной функции т.е. найти минимальное покрытие всех 0-клеток функции

а МКНФ получается на основании закона двойственности:

Минимальная нормальная форма в базисе ИЛИ-НЕ данной функции получается из МКНФ в соответствии с (1.76):

Из рис. 1.1, г следует, что минимальное покрытие 1-клеток функции состоит из двух -кубов, которым соответствуют контермы поэтому Минимальная КНФ в данном случае совпадает с МДНФ, а также можно получить формы:

Диаграммы Вейча для четырех переменных (ДВ-4) показаны на рис. 1.2. Так как где то номера клеток для ДВ-4 вычисляются на основании первичных термов , используемых для обозначения ее сторон (рис. 1.2,а). Легко убедиться, что клеткам с номерами 0 и и 8, 2 и 10, 8 и 10 соответствуют соседние минтермы. Чтобы эти клетки имели общую грань, ДВ-4 для четырехмерного пространства следует представлять себе свернутой в тор путем соединения боковых сторон (получается цилиндр) и совмещения оснований цилиндра. Тогда, например, область, состоящая из 1-клеток с номерами 0, 2, 8 и 10, будет представлять собой прямоугольник на торе, т.е. -куб, который соответствует контерму

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

Рис. 1.2

3-куба и двух 2-кубов, которым соответствуют контермы поэтому МДНФ данной функции

Минимальное же покрытие 0-клеток состоит из двух 1-кубов, которым соответствуют контермы поэтому МКНФ этой функции

Из МДНФ и МКНФ не составляет труда получить МНФ в базисах И-НЕ и ИЛИ-НЕ.

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

Таким образом, не всегда следует начинать покрытие 1-клеток с отыскания m-кубов максимального размера.

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

для получения МДНФ необходимо найти минимальное покрытие 1-клеток, которое состоит из минимального числа -кубов максимального размера;

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

прямоугольные области на диаграммах Вейча, используемые при покрытии функции могут состоять только из -клеток, где т. е. из 1, 2, 4, 8, 16 и т. д. 1-клеток;

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

если 1-клеток, входящих только в один m-куб, нет, то следует рассмотреть несколько вариантов минимизации.

Рис. 1.3

Диаграммы Вейча для числа переменных составляются из идентичных ДВ-4 (в смысле обозначения сторон первичными термами Знак означает, что имеется несколько одинаковых ДВ-4. На рис. 1.3 представлены диаграммы Вейча для Две ДВ-4 будем называть соседними, если они имеют общую грань. Клетки, расположенные в одинаковых местах соседних ДВ-4, являются соседними, так как им соответствуют соседние минтермы. Так, например, клетки с номерами 0 и 16, 5 и 21 и т. п. (рис. 1.3,а), 0 и 16,0 и 32, 5 и 21,5 и 37 и т. п. (рис. 1.3,в) являются соседними, но клетки 0 и

48, 5 и 53, 16 и 32 и т. п. (см. рис. 1.3,в) не являются соседними, так как они расположены не в соседних ДВ-4.

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

В ДВ-6 ш-кубы, расположенные в одинаковых местах всех четырех ДВ-4, образуют -куб. Поэтому МДНФ функции, показанной на рис. 1.3,г,

Основываясь на сформулированных выше правилах минимизации с помощью диаграмм Вейча, достаточно просто также отыскивать МДНФ функций семи и восьми переменных. Для этого нужно только подходящим образом выбрать способ расположения на ДВ-7 и ДВ-8. Удобнее всего располагать эти ДВ-4 так, как и клетки на ДВ-3 и ДВ-4, т.е. на рис. 1.1 и 1.2 следует заменить на а каждую клетку заменить на ДВ-4. Тогда соседними будут те же ДВ-4, что и клетки на рис. 1.1 и 1.2. Правила покрытия ш-кубами 1-клеток функций трех и четырех переменных полностью переносятся на покрытие одинаковых m-кубов (по размеру и местоположению на на ДВ-7 и ДВ-8.

Модификация диаграмм (карт) Вейча, введенных в 1952 г., известна под названием карт Карно (1953 г.) [7, 9]. Известны также методы минимизации Квайна — Мак-Класки, Блейка и др. [7].