ки диаграммы Вейча называются соседними, если им соответствуют соседние минтермы.

Основной особенностью диаграмм Вейча является то, что обозначения их сторон с помощью первичных термов х" производятся так, чтобы как можно больше соседних клеток имели общую грань. Этому требованию могут удовлетворять многие варианты обозначений сторон диаграммы Вейча. Указанное требование к диаграммам ейча предъявляется для удобства отыскания контермов, покрывающих 2"" минтермов {т<п, где п-число переменных). Изображение диаграмм Вейча на плоскости приводит к тому, что не все клетки, которым соответствуют соседние минтермы, имеют общую fplnb. Легко убедиться (рис, 1.1,а), что клеткам с номерами О и 4, IjjB соответствуют соседние минтермы. Поэтому диаграмму Вейча для трех переменных следует представлять себе свернутой в цилиндр путем совмещения боковых сторон. Тогда клетки с номерами О и 4, а также с номерами 1 и 5 будут иметь общую грань.

Пример. Требуется составить диаграмму Вейча для функции f(v), заданной табл. 1.4. Для этого в клетки с номерами i диаграммы Вейча следует занести значения функции /(vi)=0 или 1, которые она принимает в точках Vj (рис. 1.1, в). В § 1.2 было показано, что СДНФ данной функции имеет вид /(v)=Ki(v) vk2(v) V V/5(v)V7(v), т.е. в диаграмме Вейча единицами заполняются Клетки, соответствующие этим минтермам. Таким образом, существует однозначная связь между таблицей истинности (табл. 1.4), аналитическим выражением для функции и диаграммой Вейча (рис, 1.1,в).

Некоторые особенности взаимосвязи таблицы истинности и диаграммы Вейча требуют пояснений. В табл. 1.4 значения аргументов указаны в явном виде в трех столбцах, обозначенных Хз, х, дс,, а в диаграмме Вейча эти значения в явном виде отсутствуют. Однако поскольку каждой клетке с номером i соответствует точка vj области определения функции, то данной клетке соответствует вполне определенная совокупность значений переменных Хз, Хг и Xi (это соответствие указано в табл. 1.4). Легко заметить, что половине клеток диаграммы Вейча, обозначенной Хр( р-\, 2, 3), соответствуют значения дср = 1, а другой половине клеток - дср = 0. Другая особенность взаимосвязи заключается в том, что минтермы, равные 1 в точке с номером i, в диаграмме Вейча указаны в явном виде, а в таблице истинности - в неявном виде (с помощью значений аргументов Хр). Например, строке с номером 1=2 соответствуют значения дсз = 0, Хг = \ и дс1 = 0. Поэтому (v) = Кг (v) = =х\х\с\=х.Х2Х], а в диаграмме Вейча клетка с номером г = 2 непосредственно обозначена через x3XiXi (рис. 1.1,6).

Указание в явном виде одних величин вместо других в таблицах истинности и диаграммах Вейча связано с различием их назначения: таблицы истинности наиболее удобны для первоначального описания переключательных функций, а диаграммы Вейча - для их минимизации. Клетки, содержащие в диаграмме Вейча единицы, будем называть 1-клетками, а клетки, содержащие нули - 0-клетка-ми. Было показано, что любой контерм Ki,j(v), не зависящий от т гйерёменных {т<.п, где п - число переменных), представляет собой дизъюнкцию 2™ минтермов, каждый из которых имеет среди осталь-

ных по т соседних. Поэтому диаграмма Вейча для таких контермов содержит 2™ 1-клеток.

Основное свойство диаграмм Вейча заключается в том, что 1-клеткн любого коитерма /Ci,j(v) образуют иа ней область, являющуюся прямоугольником и только прямоугольником (для трех переменных эта область представляет собой прямоугольник иа цилиндре), причем переменные жр, от которых контерм Ki,j(v) ие зависит, имеют в этой области paзJШЧиыe значенвя (дср и %), а остальные переменные т-только одно значение (дгр или жр). Такие области называются т-кубами (т=0, 1, .... п; 0-кубу соответствует минтерм, а п-кубу - константа единица). Так как от-куб представляет собой область, состоящую ю 2» 1-клеток, то говорят, что /н-куб покрывает 2"" 1-клеток. Чтобы записать контерм Ki,Hv)> сО ответствующий некоторой прямоугольной области (некоторому т-кубу) в явном виде, необходимо просто составить коньюнкцию

из первичных термов дср, которые в этой области на диаграмме

Вейча имеют постоянные значения (только Хр или только Хр).

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

На рис. 1.1, в штриховыми линиями обозначены два 1-куба, образованные 1-клетками с номерами 5 и 7, 1 и 5, которым соответствуют контермы Хгх и XiX, а 1-клетка с номером 2 ие имеет ни одной соседней 1 клетки, поэтому ей соответствует 0-куб, представляемый минтермом хъХгХ1. Ж]ЩФ данной функции записывается в виде ]iy)-x%x\/xiX\\JXbXiX\. МНФ в базисе И - НЕ этой функции получается из МДНФ в соответствии с (1.52) /(v) =

= ХъХ(\/ХгХх\/ХгХхХъХ1-Х<1Хх-ХгХгХ.

Для получения МКНФ функции /(v) следует иайти МДНФ инверсной функции /(v), т.е. следует найти минимальное покрытие всех 0-клеток функции /(v): \(v) = x%xC\/X2Xt\/X3X-iXu а МКНФ получается на основании закона двойственности ]{у1)~=хъХ\\/хмУ

\ГхгХгХ1 = (х\/х{)-{х2\1х,)(,Хъ\1х.А/хх). МНФ в базисе ИЛИ-НЕ данной функции получается из МКНФ в соответствии с (1.55)

/(v) =ДСзУ1У-»2 VaJiVsVVi.

Из рис. 1.1, г следует, что минимальное покрытие 1-клеток функции /(v) состоит из двух 2-кубов, которым соответствуют контермы Хг и Гь поэтому МФНФ функции \{\)=Хг\1Х1. МКНФ функции в данном случае совпадает с МДНФ, а /(v)-дсг! - МНФ

в базисе И - НЕ и /(v) =Г2VTi - МНФ в базисе ИЛИ -НЕ.

Диаграммы Вейча для четырех переменных показаны на рнс. 1.2. Так как у=(лг4, Хъ, Хг, х{) и Vi= (4, ез, е, е\), где {-еевгеи то номера клеток i диаграммы Вейча вычисляются на основании пер-

S) Рис. 1.2

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

0, 2, 8 и 10, будет представлять собой прямоугольник на торе, т. е. 2-куб, который соответствует контерму хх.

Диаграмма Вейча, показанная на рис. 1.2,6, задает некоторую функцию /(v). Минимальное покрытие 1-клеток состоит из одного 3-куба и двух 2-кубов, которым соответствуют контермыдсг, ХзХ\ и Хгх\, поэтому МДНФ данной функции ](у)-=ХгУх%Х\\/хх.. Минимальное же покрытие 0-клеток £Остоит из двух 1-кубов, которым соответствуют контермы хъХ2.Х\ и ХъХгХи поэтому МКНФ этой функции {у) = {хъУх2\;х)1{хз\1ХзМх{). Из МДНФ и МКНФ не составляет труда получение МНФ в базисах И - НЕ и ИЛИ - НЕ.

Выбор от-кубов, покрывающих 1-клетки диаграммы Вейча, не всегда столь очевиден, как это было в предыдущих примерах. На рис. \2,в часть 1-клеток можно было бы покрыть 2-кубом (ему соответствует контерм хх"). Однако при покрытии остальных четырех 1-клеток 1-кубами становится понятным, что необходимостьис-пользования 2-куба отпадает. МДНФ этой функции ]{y)=xiXi\l \/XaX2Xi\/XsX2Xi\/XiXiX2 Таким образом, не всегда следует начинать покрытие 1 клеток с отыскания от-кубов максимального размера.

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

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

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

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

1, п, т,е, и? 1; 2; 4; 8; 16 и т.д. 1-клеток;