Раздел: Документация
0 ... 4 5 6 7 8 9 10 ... 119 сводятся к сформулированному выше общему правилу, в то время как алгоритмы (методы) минимизации могут сильно различаться между собой. На основании идемпотентных законов один и тот же минтерм Atl(f), входящий в СДНФ, может использоваться несколько раз для образования различных контермов A,j(f), так как Кп И = кч И v кч И V ... V А\, (f). В общем случае для минимизации функций га переменных возникает необходимость использовать любой минтерм не более га раз, так как он может быть соседним не более чем с га другими минтермами. Рассмотрим пример. Пусть задана СДНФ функции трех переменных f(v) = A3(f) V A5(f) V A6(f) V K7{v) = = x3x2xi V x3x2xi V x3x2xiV x3x2xi. Здесь для получения МДНФ минтерм Ky(v) = х3х2х\ необходимо использовать три раза: /(f) - x3x2xi V x3x2xi V (х3х2Х! V x3x2xi) V x3x2x"i V Х3Х2Х1 = = х2х\{х3 V х3) V x3xi(x2 V х2) V x3x2(xi V Xi) = = x2xiV X3X1 V x3x2. Уже из этого элементарного примера видно, сколь сложно использовать аналитический метод минимизации ввиду трудоемкости работы по отысканию соседних минтермов (задача еще более усложняется при наличии в СДНФ группы, состоящей из 2т минтермов при in > 1, которые можно заменить одним контермом). Рассмотрим теперь методику получения минимальных нормальных форм (МНФ) в других базисах. Для этой цели наиболее удобно использовать закон двойственности, который обладает замечательным свойством: при преобразовании любого логического выражения на основании закона двойственности ни число первичных термов хРр, ни общее число операций дизъюнкции и конъюнкции, входящих в исходное логическое выражение, не изменяется. Пусть получена МДНФ некоторой функции /(f). Тогда, используя закон двойного отрицания и закон двойственности, будем иметь: /И = У*о-И = П*«Й-(1-80) ijij Это соотношение и дает минимальную нормальную форму в базисе И-НЕ функции /(f), так как для ее реализации требуются только операции И-НЕ. В качестве примера запишем в базисе И-НЕ МНФ функции трех переменных, МДНФ которой была найдена выше: /(f) = x2xi V 0:33:1 V х3х2 = х2хг • Х3Х\ х3х2. Конъюнкция любого числа дизтермов называется конъюнктивной нормальной формой. Получение минимальной конъюнктивной нормальной формы (МКНФ) функции /(f) легко сводится к получению МДНФ инверсной функции /(f) и преобразованию ее с помощью закона двойственности: 7Й=\/К);(1.81) ij /И = ца = Пм«;И(1-82) ijij где M,j(f) - дизъюнктивные термы (1.78). Рассмотрим пример. Пусть требуется найти МКНФ функции трех переменных /(f), значения которой равны 0 только в точках f0, fi и f4. СДНФ инверсной функции /(f) = A0(f) V Ai(f) V A4(f) = x3x2xi V x3x2xi V x3x2x\. Используя минтерм A0(f) = x3x2xi дважды, легко показать, что МДНФ (1.81) инверсной функции /(f) = x2Xi Vx3x2. Тогда МКНФ функции /(f) получается с помощью закона двойственности: /(f) = x2Xi V х3х2 - (х2 V xi)(x3 V х2). Минимальная нормальная форма в базисе ИЛИ-НЕ функции /(f) может быть получена непосредственно из МКНФ (1.82) с помощью закона двойного отрицания и закона двойственности: т = им) = УШ- (L83) ijij Найдем МНФ в базисе ИЛИ-НЕ для функции /(f), рассмотренной в предыдущем примере: /(f) = (х2 V xi)(x3 V х2) = х2 V хг V х3 V х2. Таким образом, получение МКНФ и МНФ в базисах И-НЕ и ИЛИ-НЕ функции /(f) всегда можно свести к получению МДНФ либо функции /(f), либо ее инверсии /(f). Это позволяет использовать для всех нормальных минимальных форм представления переключательных функций только метод их минимизации, приводящий к получению МДНФ. 48 Глава J. Основы теории 1.11. Диаграммы Вейча Из-за сложности использования аналитического метода минимизации, связанной с трудоемкой работой по отысканию соседних минтермов, наибольшее распространение получил графический метод минимизации с помощью диаграмм Вейча, несомненным достоинством которого является наглядность и простота использования при небольшом числе переменных (га < 6). Диаграммы Вейча (ДВ) представляют собой один из табличных способов задания функций и состоят из клеток, каждая из которых соответствует определенной точке V{ области определения функций, т. е. диаграммы Вейча для функции га переменных состоят из 2П клеток, которые можно пронумеровать числами ,i = 0,1,...,2П - 1. Таким образом, ДВ отображают га-мерное пространство на плоскость. Чтобы с помощью диаграммы Вейча задать функцию /(f), необходимо в каждую клетку с номером i занести значение функции /(i/,-) = а, = 0 или 1, которое она принимает в точке к,-. а) <5>
в) г)
Рис. 1.1 Для минимизации функций двух переменных использовать диаграммы Вейча нет смысла, так как эти функции легко упрощаются аналитическим методом или непосредственно по таблице истинности. Рассмотрим диаграммы Вейча для функций трех переменных (ДВ-3; га = 3). Так как 2n = 23 = 8, то ДВ-3 состоит из восьми клеток (рис. 1.1,а). Каждой стороне ДВ-3 соответствует своя переменная хр (р = 1,2,3), причем одной половине стороны соответствует первичный терм х- р „1 хр, а другой - первичный терм хрр = хр - хр. Поэтому каждой клетке будет соответствовать совокупность первичных термов Xе?, x\?, x\l, а 1.11. Диаграммы Вейча. 49 номер данной клетки будет Определяться числом г = е3е2е\. Любой минтерм Ki(u) представляет собой функцию, равную 1 только в одной точке щ области определения, поэтому на ДВ-3 он представляется единицей, стоящей Только в одной клетке с номером i. Например, на рис. 1.1,5показана ДВ-3 для минтерма K2(v) = x%x\x°x = x3x2xi. На рис. 1.1,б,в,г использованы упрощенные обозначения сторон ДВ-3, полностью соответствующие обозначениям на рис. 1.1,а (одна половина сторон соответствует хр, а другая - хр). Клетке с номером i = 2 соответствует на основании принятых обозначений совокупность первичных термов х3, х2 и х 1, конъюнкция которых и представляет собой минтерм К2(у). Таким образом можно сказать, что каждой клетке с номером i соответствует минтерм Ki(v). Две клетки диаграммы Вейча называются соседними, если им соответствуют соседние минтермы. Для удобства отыскания контермов, покрывающих 2Ш минтермов (тп < га, где га - число переменных), стороны диаграмм Вейча обозначают с помощью первичных термов хрр так, чтобы как можно больше соседних клеток имели общую грань. Этому требованию могут удовлетворять многие варианты обозначений. При изображении диаграмм Вейча для трехмерного пространства на плоскости не все клетки, которым соответствуют соседние минтермы, имеют общую грань. Легко убедиться (см. рис.1.1,а), что клеткам с номерами О и 4, 1 и 5 соответствуют соседние минтермы. Поэтому ДВ-3 следует представлять себе в виде трехмерной фигуры - цилиндра, получаемого путем совмещения боковых сторон ДВ-3. Тогда клетки с номерами 0 и 4, 1 и 5 будут иметь общую грань. Рассмотрим пример. Пусть требуется составить ДВ-3 для функции /(), заданной табл. 1.5. Для этого в клетки с номерами » (см. рис. 1.1,а) следует занести значения функции f(vi) = 0 или 1, которые она принимает в точках щ (см. рис. 1.1,е). В § 1.8 было показано, что СДНФ данной функции имеет вид f(u) = Ki{v) V K2(v) V K6(v) V K7(u), т.е. в ДВ-3 (см. рис. 1.1,в) единицами заполняются клетки, соответствующие этим минтермам. Таким образом, имеется жесткая связь между таблицей истинности (см. табл. 1.5), аналитическим выражением для функции и диаграммой Вейча (см. рис. 1.1,в). Некоторые особенности взаимосвязи таблицы истинности и диаграммы Вейча требуют пояснений. В таблице истинности (табл. 1.5) значения аргументов указаны в явном виде в трех столбцах, обозначенных через хз, х2 и х\, а в ДВ-3 эти значения в явном виде отсутствуют. Однако, поскольку каждой клетке с номером i соответствует точка V{ области определения функции, то данной клетке соответствует вполне определенная совокупность значений переменных х3, х2 и 4 Пухальскнй Г. И., Новосельцева Т. Я. х\ (это соответствие указано в табл. 1.5). Легко заметить, что половине клеток ДВ-3, обозначенной через хр (р = 1,2,3) соответствуют значения хр = 1, а другой половине клеток - значения хр - 0. Другая особенность взаимосвязи заключается в том, что минтермы, равные 1 в точке с номером i, в диаграмме Вейча указаны в явном виде, а в таблице истинности - в неявном (с помощью значений аргументов хр). Например, строке с номером i = 2 соответствуют значения хз = 0, х2 = 1 и X! = 0. Поэтому Ki(v) = K2{v) = x§xxj = x3x2xi, а в ДВ-3 клетка с номером i = 2 непосредственно обозначена через хз, х2 и xi (см. рис. 1.1,6). Указание в явном виде одних величин вместо других в таблицах истинности и диаграммах Вейча связано с различием в их назначении: таблицы истинности наиболее удобны для первоначального описания переключательных функций, а диаграммы Вейча - для их минимизации. Клетки, содержащие в диаграмме Вейча единицы, будем называть 1-клетками, а клетки, содержащие нули, - О-клетками. Выше было показано, что любой контерм A\j(f), не зависящий от т переменных (т < га, где га - число переменных), представляет собой дизъюнкцию 2т минтермов, каждый из которых имеет среди остальных по т соседних. Поэтому диаграмма Вейча для таких контермов содержит 2т 1-клеток. Основное свойство диаграммы Вейча заключается в том, что 1-клетки любого контерма A,j(f) образуют на ней область, являющуюся прямоугольником и только прямоугольником (для трех переменных эта область представляет собой прямоугольник на цилиндре), причем переменные хр, от которых контерм K{j{v) не зависит, имеют в этой области различные значения (хр и хр), а остальные переменные - только одно значение (хр или хр). Такие области называются т-кубами (т = 0,1,..., га; 0-кубу соответствует минтерм, а га-кубу - константа единица). Так как m-куб представляет собой область, состоящую из 2т 1-клеток, то говорят, что m-куб покрывает 2Ш 1-клеток. Чтобы записать контерм A,j(f), соответствующий некоторой прямоугольной области (некоторому m-кубу) в явном виде, необходимо просто составить конъюнкцию из первичных термов хер , которые в этой области на диаграмме Вейча имеют постоянные значения (только хр или только хр). Таким образом, в соответствии с общим правилом минимизации, получение МДНФ с помощью диаграмм Вейча сводится к отысканию минимального числа m-кубов максимального размера, состоящих из 1-клеток, т.е. к отысканию минимального покрытия m-кубами 1-клеток и составлению дизъюнкции контермов I\ij(i/), соответствующих этим m-кубам (любая 1-клетка должна войти хотя бы в один m-куб). Согласно идемпотентным законам любая 1-клетка может входить в несколько различных т- кубов. На рис. 1.1,е пунктиром обозначены два 1-куба, образованные 1-клетками с номерами 5 и 7, 1 и 5, которым соответствуют контермы Х3Х1 и x2xi, а 1-клетка с номером 2 не имеет ни одной соседней 1-клетки, поэтому ей соответствует 0-куб, представляемый минтермом хзх2Х1. МДНФ данной функции записывается в виде f(u) = Х3Х1 Vx2xj Vx3x2xi. Минимальная нормальная форма в базисе И-НЕ этой функции получается из МДНФ в соответствии с (1.80): /(«/) = Х3Х1 V Х2Х1 V X3X2Xi = Х3Х1 • x2xi • x3x2xi. Для получения МКНФ функции /(f) следует найти МДНФ инверсной функции /(f), т.е. найти минимальное покрытие всех 0-клеток функции /(f): /(f) = x3x"i Vx2xi Vx3x2xb а МКНФ получается на основании закона двойственности: f(v) = x3xi Vx2X! Vx3x2xi = (х3 V xj)(x2 V xi)(x3 V х2 V xi). Минимальная нормальная форма в базисе ИЛИ-НЕ данной функции получается из МКНФ в соответствии с (1.76): f(v) = х3 Vxi V х2 V хх V х3 V х2 V хх. Из рис. 1.1,г следует, что минимальное покрытие 1-клеток функции /(f) состоит из двух 2-кубов, которым соответствуют контермы х2 и хь поэтому МДНФ /(f) = х2 Vxb Минимальная КНФ в данном случае совпадает с МДНФ, а также можно получить формы: f(v) = zilT - МНФ в базисе И-НЕ, f(u) = х2 Vxj - МНФ в базисе ИЛИ-НЕ. Диаграммы Вейча для четырех переменных (ДВ-4) показаны на рис. 1.2. Так как v = (х4, х3, х2, xi) и vt = (е4,3, е2, е\), где г = e4e3e2ei, то номера клеток г для ДВ-4 вычисляются на основании первичных термов хР, используемых для обозначения ее сторон (рис. 1.2,а). Легко убедиться, что клеткам с номерами 0 и 2, 0 и 8, 2 и 10, 8 и 10 соответствуют соседние минтермы. Чтобы эти клетки имели общую грань, ДВ-4 для четырехмерного пространства следует представлять себе свернутой в тор путем соединения боковых сторон (получается цилиндр) и совмещения оснований цилиндра. Тогда, например, область, состоящая из 1-клеток с номерами 0, 2, 8 и 10, будет представлять собой прямоугольник на торе, т.е. 2-куб, который соответствует контерму хзхь Диаграмма Вейча, показанная на рис. 1.2,6, задает некоторую функцию /(f). Минимальное покрытие 1-клеток состоит из одного 0 ... 4 5 6 7 8 9 10 ... 119
|
||||||||||||||||||||||||||||||||||
