Минимизация логических функций

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

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

Однако этот метод обладает существенными недостатками:

как правило, такие преобразования требуют громоздких выкладок;

процесс упрощения логической функции не является алгоритмическим; во многом он зависит от мастерства и опыта разработчика;

и, самое главное, результат преобразования не гарантирует получения минимальной формы дизъюнктивной или конъюнктивной ФАЛ.

Отметим, что получение минимальной формы в своей основе содержит совершенную (дизъюнктивную или конъюнктивную) нормальную форму

Приведение дизъюнктивной (или конъюнктивной) формы записи ФАЛ к совершенному виду проходит на основе формул (1.1) и (1.2), только правые и левые их части целесообразно поменять местами (в этом случае данные формулы обычно называются операциями развертывания). Тогда ДНФ, в которой не все члены являются элементарными конъюнкциями, приводится к СДНФ следующим образом.

Пусть некоторая ДНФ имеет следующий вид:

$$f(x,y,z) =xyz\vee\overline{x}\overline{z}\vee z$$

Так как $$а = (а \And b) \vee (а \And \overline{b})$$, то исходную функцию можно представить как

$$f(x,y,z) = xyz \vee \overline{x} \overline{z} (y \vee \overline{y}) \vee (x \vee \overline{x}) \And z = xyz\vee\overline{x}y\overline{z}\vee\overline{x}\overline{y}\overline{z}\vee xz\And (y\vee\overline{y}) \vee\overline{x}z\And (y\vee\overline{y}) =$$ $$= xyz \vee\overline{x}y\overline{z}\vee\overline{x}\overline{y}\overline{z}\vee xyz\vee x\overline{y}z\vee\overline{x}yz\vee\overline{x}\overline{y}z$$

Убирая повторяющиеся члены, чего требует запись функции в совершенном виде, на основе свойства дизъюнкции a V a V ... V a = a, получим:

$$f(x,y,z)_{СДНФ} = xyz\vee\overline{x}y\overline{z}\vee\overline{x}\overline{y}\overline{z}\vee x\overline{y}z\vee\overline{x}yz\vee\overline{x}\overline{y}\overline{z}$$

Метод, основанный на теореме Квайна

Получение минимальной дизъюнктивной нормальной формы (МДНФ) выполняется в несколько этапов.

Первый этап – получение сокращенной дизъюнктивной нормальной формы (СкДНФ). Обычно он проводится на основе теоремы Квайна.

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

Второй этап – получение минимальной дизъюнктивной (конъюнктивной) нормальной формы (МДНФ или МКНФ) с использованием импликантной (имплицентной для коньюнктивной формы) матрицы. При этом в качестве промежуточного итога получается тупиковая форма (возможно, не одна).

Теорема. Любая логическая функция, тождественно не равная нулю, представима и притом однозначно в виде сокращенной ДНФ. Любая логическая функция, тождественно не равная единице, представима, и притом однозначно, в виде сокращенной КНФ.

В данном пособии практически все теоремы будут представлены без доказательств. Их доказательства, при необходимости, можно найти в специальной литературе или в интернете.

Теорема Квайна. Если в совершенной дизъюнктивной нормальной форме логической функции провести все операции неполного склеивания и затем все операции поглощения, то в результате получается сокращенная дизъюнктивная нормальная форма этой функции.

Метод получения сокращенной дизъюнктивной нормальной формы логической функции называется методом Квайна.

Таким образом, теорема Квайна дает возможность получить из СДНФ или СКНФ их сокращенные формы (СкДНФ и СкКНФ соответственно). Эти формы будут единственными для данной логической функции.

Посмотрим, как с помощью теоремы Квайна из совершенной формы представления ФАЛ можно перейти к ее сокращенной форме.

Пример 3.1. Пусть $$f_{СДНФ}(a,b,c,d) = \overline{a}\overline{b}cd\vee\overline{a}bcd\vee a\overline{b}\overline{c}\overline{d}\vee a\overline{b}c\overline{d}\vee a\overline{b}cd\vee ab\overline{c}\overline{d}\vee abcd$$

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

Проведем все операции неполного склеивания между термами данной функции. Для этого необходимо определить возможность склеивания каждого из наборов, составляющих функцию, с любым другим набором, а именно, проверить, чтобы наборы были соседними, то есть были одного ранга (зависели от одинакового количества переменных – на первом этапе в совершенных формах это выполняется по определению) и отличались только в одной переменной. В результате получим:

$$f(x, y, z) = cd \vee a\overline{b}\overline{d}\vee a\overline{c}\overline{d}\vee a\overline{b}c\vee\overline{a}cd\vee\overline{b}cd\vee bcd\vee acd\vee\overline{a}\overline{b}cd\vee\overline{a}bcd\vee a\overline{b}\overline{c}\overline{d}\vee a\overline{b}c\overline{d}\vee a\overline{b}cd\vee ab\overline{c}\overline{d}\vee abcd$$

После проведения всех возможных операций поглощения в данной функции получимсогласно теореме Квайнасокращенную дизъюнктивную форму исходной функции. Очевидно, что она будет единственной:

$$f(x, y, z) = cd\vee a\overline{b}\overline{d}\vee a\overline{c}\overline{d}\vee a\overline{b}c$$

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

Тупиковой ДНФ называется дизъюнкция простых импликант, ни одну из которых из выражения функции исключить нельзя. Некоторые функции имеют несколько тупиковых форм.

Импликантная матрица имеет следующую структуру. Ее столбцы соответствуют всем элементарным конъюнкциям исходной функции, а строки содержат все импликанты сокращенной дизъюнктивной нормальной формы (Табл. 3.2).

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

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

В рассматриваемом случае таких существенных импликант будет две: cd и $$a\overline{c}\overline{d}$$. Они покрывают все минтермы исходной функции, кроме $$a\overline{b}c\overline{d}$$. Данный минтерм может быть покрыт как импликантой$$a\overline{b}\overline{d}$$, так и импликантой $$a\overline{b}c$$.

В результате мы получим две тупиковые нормальные формы:

$$f_{1тнф}(a,b,c,d) = cd\vee a\overline{c}\overline{d}\vee a\overline{b}\overline{d}$$ и

$$f_{2тнф}(a,b,c,d) = cd\vee a\overline{c}\overline{d}\vee a\overline{b}c.$$

Тупиковые формы, содержащие наименьшее количество символов, будут минимальными.Обе полученные выше минимальные формы содержат одинаковое число символов. Так что по принятому нами критерию их обе можно считать минимальными:

$$f_{1МДНФ}(a,b,c,d) = cd\vee a\overline{c}\overline{d}\vee a\overline{b}\overline{d}$$ и

$$f_{2МДНФ}(a,b,c,d) = cd\vee a\overline{c}\overline{d}\vee a\overline{b}c.$$

Таким образом, определенные выше дизъюнктивные нормальные формы – сокращенная, тупиковая и минимальная находятся в следующем соотношении. Тупиковая ДНФ получается из сокращенной путем удаления некоторых слагаемых. Минимальная ДНФ находится среди тупиковых. Сокращенная форма для одной логической функции – единственная. Тупиковых и минимальных форм может быть несколько.

Минимизация логических функций методом Квайна – Мак-Класки

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

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

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

В 1956 году Эдвард Мак-Класки2Уиллард Ван Орман Куайн (англ. Willard Van Orman Quine) — американский философ, логик и математик. Родился 25 июня 1908 года в Акроне, штат Огайо. Умер 25 декабря 2000 года в Бостоне, штат Массачусетс, в возрасте 92 лет.доработал данный метод. Он предложил ряд модификаций, который существенно сократили количество необходимых сравнений при получении сокращенной нормальной формы и максимально адаптировали его для компьютерной минимизации логических функций.

Суть этих предложений (применительно к ФАЛ, представленным в виде дизъюнктивных нормальных форм) заключается в следующем.

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

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

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

Процесс продолжается до тех пор, пока возможны склейки.

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

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

Это связано с тем, что склеиться могут лишь те набору, которые зависят от одних и тех же переменных и отличаются лишь в одной из них. Поэтому целесообразно рассматривать лишь наборы, которые отличаются ровно на одну единицу или ноль, то есть наборы соседних групп. Из этого вытекает и необходимость введения "пустых" групп, а также то свойство, что элемент 0-группы "склеится" со всеми элементами 1-группы, а элемент группы из всех единиц "склеиться" со всеми элементами предшествующей группы.

Пример 3.2.

Минимизировать методом Квайна – Мак-Класки следующую логическую функцию:

f(a,b,c,d)_СДНФ = ∑(3,7,8,10,11,12,15)

Решение

Этап 1

Выписать двоичное представление наборов, образующих СДНФ данной функции: (0011, 0111, 1000, 1010, 1011, 1100, 1111)

Этап 2.

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

Для данной ФАЛ отсутствует элемент 0-группы, поэтому помечаем эту группу как пустую:

Этап 3

Сравнить каждый код из одной группы с каждым кодом из соседних групп. Если найдены два кода, отличающиеся только в одном разряде (то есть они могут "склеиваться"), то пометить эти коды каким-либо особым символом, например "*", и в новую группу поместить код, сохраняющий значение в совпадающих разрядах и имеющий какой-либо особый символ, например "-", на месте несовпадающего разряда. При этом образуется n-1 новая группа кодов. Если код попадает в несколько "склеек", то он символом * может помечаться только один раз.

Эта процедура повторяется для вновь образованных групп до тех пор, пока возможна процедура "склеивания" элементов соседних групп. Максимальное возможное число шагов на этом этапе равно n. На всех шагах, начиная со второго, необходимо следить за тем, чтобы два "склеиваемых" кода представляли собой термы одного ранга изависили от одних и тех же логических переменных, то есть знаки "-" у них должны находиться в одних и тех же позициях. При появлении в одной группе нескольких одинаковых импликант для дальнейшего анализа следует оставить лишь одну из них (x V x = x).

Последовательность выполнения шагов этапа 3:

Таким образом, сокращенной дизъюнктивной нормальной формой исходной функции будет конъюнкция набора (--11) из последнего столбца преобразований, а также наборов (10-0), (1-00), (101) из предыдущих столбцов, которые не имеют пометок и, следовательно, не попали в "склейки" на последующих этапах.

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

Этап 4

Составить импликантную матрицу.

Первичные импликанты	Конституэты единицы
	0011	0111	1000	1010	1011	1100	1111
--11	+	+			+		+
10-0			+	+
1-00			+			+
101-				+	+
-111		+					+

Этап 5

Найти существенные импликанты функции.

Для рассматриваемой функции существенными импликантами будут - -11 и 1-00, так как только первичная импликанта --11 позволяет покрыть минтерм 0011 исходного набора, а первичная импликанта 1-00 необходима для покрытия минтерма 1100.

Первичные импликанты	Конституэты единицы
	0011	0111	1000	1010	1011	1100	1111
--11	+	+			+		+
10-0			+	+
1-00			+			+
101-				+	+
-111		+					+

Этап 6

Найти тупиковые дизъюнктивные нормальные формы и выбрать из них минимальные ДНФ.

Рассматриваемая функция имеет две различные тупиковые, они же минимальные дизъюнктивные формы:

Обе тупиковые формы содержат одинаковое количество символов. Поэтому по нашему критерию их обе можно считать минимальными дизъюнктивными нормальными формами исходной функции.

Как вы, наверное, заметили, в примерах 3.1 и 3.2 мы минимизировали одну и ту же логическую функцию, но в примере 3.2 этот процесс прошел гораздо быстрее.

Пример 3.3.

Минимизировать ФАЛ, заданную в виде совершенной конъюнктивной нормальной формы, методом Квайна – Мак-Класки:

f(a,b,c,d)_СДНФ= ∏(0,7,10,11,13,14,15)

Решение

Последовательность и содержание этапов, выполняемых при минимизации заданной в СКНФ логической функции, эквивалентны аналогичным этапам, выполнявшимся при минимизации логической функции, заданной в СДНФ (см. примеры 3.1 и 3.2).

Этап 1

Записать двоичное представление наборов, образующих СКНФ данной функции: (0000, 0111, 1010, 1011, 1101, 1110, 1111)

Этап 2

Разбить полученные коды на группы, содержащие одинаковое количество нулей в коде. ДляФАЛ, зависящих от n переменных, таких групп может быть n+1 (ни одного нуля в коде, один нуль, два нуля, ... , n нулей в коде). Расположить группы по возрастанию количества нулей. Если количество получившихся групп меньше n+1, то отсутствующие группы помечаются как пустые:

Этап 3

Сравнить каждый код из одной группы с каждым кодом из соседних групп. Если найдены два кода, отличающихся только в одном разряде (то есть они могут "склеиваться" между собой согласно (3.1.4)), то пометить их каким-либо особым символом, например, "*", и в новую группу поместить код, сохраняющий значение в совпадающих разрядах и имеющий какой-либо особый символ, например "-", на месте несовпадающего разряда. При этом образуется n-1 новая группа кодов.

Эта процедура повторяется для вновь образованных групп до тех пор, пока возможна процедура "склеивания" элементов соседних групп. Максимально возможное число шагов на этом этапе равно n. На всех шагах, начиная со второго, необходимо следить за тем, чтобы два "склеиваемых" кода представляли собой термы, зависящие от одних и тех же логических переменных, то есть знаки "-" у них должны находиться в одних и тех же позициях. При появлении в одной группе нескольких одинаковых термов для дальнейшего анализа следует оставить лишь один из них.

Результатом этого этапа является получение всех первичных имплицент функции и ее сокращенной конъюнктивной нормальной формы.

Этап 4

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

В ячейку таблицы ставится какой-либо отличительный символ, например "+", если первичная имплицента, стоящая в заголовке строки, является собственной частью конституэнты нуля, стоящей в заголовке столбца. В противном случае ячейка остается пустой:

Простейший контроль правильности заполнения таблицы может быть проведен аналогично примеру 3.1.

Этап 5

Найти существенные имплиценты.

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

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

Для рассматриваемой функции все содержащиеся в заголовках строк минтермы будут существенными, так как первичная имплицента 1-1- необходима для покрытия макстермов 1010, 1011, 1110 и 111 исходного набора, имплиценнта -111 – для покрытия макстерма 0111, имплиценнта 11-1 – для покрытия макстерма 1101, а имплицента 0000 необходима для покрытия такого же макстерма в исходном наборе.

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

Полученная единственная минимальная конъюнктивная нормальная форма имеет следующий вид:

Пример 3.4.

Получить методом Квайна – Мак-Класки минимальные ДНФ и КНФ для ФАЛ, заданной в виде совершенной конъюнктивной нормальной формы:

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

Решение

Вначале получим минимальную конъюнктивную нормальную форму по схеме, изложенной в примере 3.3.

Этап 1

Записать двоичные коды наборов, образующих СКНФ данной функции:

(000, 010, 101, 110, 111)

Этап 2

Разбить полученные коды на группы, содержащие одинаковое количество нулей в коде. Расположить группы по возрастанию количества нулей:

Этап 3

Выполнить склейку кодов, попарно сравнивая элементы соседних групп:

Этап 4

Составить имплицентную матрицу:

Первичные имплиценты	Конституэты нуля
	000	010	101	110	111
11-				+	+
1-1			+		+
-10		+		+
0-0	+	+

Этап 5

Определить существенные имплиценты.

Для рассматриваемой функции существенными имплицентами будут 0-0 и 1-1.

Этап 6

Найти тупиковые конъюнктивные нормальные формы и выбрать из них минимальные КНФ.

Из анализа имплицентной матрицы получим, что функция имеет две тупиковые конъюнктивные нормальные формы, каждая из которых является минимальной:

Теперь получим минимальную дизюнктивную нормальную форму.

Этап 1

Записать двоичные коды наборов, образующих СДНФ данной функции:

(001, 011, 100)

Этап 2

Разбить полученные коды на группы, содержащие одинаковое количество единиц в коде. Расположить группы по возрастанию количества единиц:

Этап 3

Выполнить склейку кодов, попарно сравнивая элементы соседних групп:

Этап 4

Составить импликантную матрицу:

Первичные имплиценты	Конституэты нуля
	001	011	100
0-1	+	+
100			+

Этапы 5 и 6

Анализ импликантной матрицы показывает, что все полученные первичные импликанты являются существенными и, следовательно, рассматриваемая ФАЛ имеет единственную минимальную дизъюнктивную нормальную форму:

Пример 3.5.

Минимизировать методом Квайна – Мак-Класки следующую логическую функцию:

f(a,b,c,d,e)_СДНФ = ∑(0,1,2,3,4,6,8,10,12,15,17,18,20,24,31)

Решение

Этап 1

Выписать двоичное представление наборов, образующих СДНФ данной функции: (00000, 00001, 00010, 00011, 00100, 00110, 01000, 01010, 01100, 01111, 10001, 10010, 10100, 11000, 11111).

Этапы 2 и 3.

Разбить полученные двоичные коды на группы, содержащие одинаковое количество единиц в коде. Расположить группы по возрастанию (или убыванию) количества единиц. Выполнить склейку кодов из соседних групп.

Для данной ФАЛ отсутствует элемент 3-группы, поэтому помечаем эту группу как пустую.

00000*	0000-* 000-0* 00-00* 0-000*	000 - - 000 - - 00 - - 0 00- - 0 0- - 00 0-0-0 0- -00
00001* 00010* 00100* 01000*	000-1* 0001-* 00-10* 0-010* 001-0* 0-100* 010-0* 01-00* -0001 -0010 -0100 -1000	–
00011* 00110* 01010* 01100* 10001* 10010* 10100* 11000*	–	–
–	–	–
01111*	-1111	–
11111*	–	–

Этап 4

Составить импликантную матрицу:

Первичные импликанты	Конституэты единицы
	00000	00001	00010	00011	00100	01000	01010	01100	01111	10001	10010	10100	11000	11111
000--	+	+	+	+
00--0	+		+		+	+
0-0-0	+		+				+	+
0--00	+				+		+		+
-0001		+									+
-0010			+									+
-0100					+								+
-1000							+							+
-1111										+					+

Этапы 5 и 6

Анализ импликантной матрицы показывает, что все полученные первичные импликанты являются существенными и, следовательно, рассматриваемая ФАЛ имеет единственную минимальную дизъюнктивную нормальную форму:

Таким образом, использование метода Квайна – Мак-Класки позволяет проводить минимизацию логических функций от произвольного количества аргументов.

Метод минимизирующих карт (карты Карно, диаграммыВейча)

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

Диаграммы Вейча представляет собой прямоугольник, разбитый на ячейки, число которых равно общему числу наборов для данной функции n переменных, то есть оно равно 2n. Так, для функции 3-х переменных ячеек будет 8, для 4-х переменных – 16 и т.д.

Каждая ячейка соответствует определенному набору, или терму, причем наборы располагаются так, чтобы соседние наборы, или термы как по горизонтали, так и по вертикали, отличались бы только значением одной переменной: в одной ячейке она была бы в прямом виде, а в соседней – с инверсией. Причем надо учесть, что ячейки, расположенные на противоположных концах каждой строки или столбца, также являются соседними.

Функцию в СДНФ наносят на карту, отмечая, например, знаком "1" ячейки, соответствующие тем наборам, на которых ФАЛ равна единице, т.е. в СДНФ функции эта ячейка соответствует одному изееминтермов. Остальные ячейки отмечаются знаком "0".

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

Клетки, содержащие в диаграмме Вейча единицы, будем называть 1-клетками, а клетки, содержащие нули – 0-клетками.

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

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

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

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

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

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

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

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

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

Пример 3.5.

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

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

Решение

Этап 1.

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

(рис 3.1)

Этап 2.

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

Этап 3.

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

Этап 4.

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

$$f(x,y,z)_{1МДНФ} = xz\vee\overline{x} \overline{z} \vee\overline{x} \overline{y} $$ $$f(x,y,z)_{2МДНФ} = x z \vee\overline{x} \overline{z} \vee z \overline{y} $$

Пример 3.6. Минимизировать функцию, заданную в виде СКНФ:

f(a,b,c,d)_СКНФ= ∏(2,3,5,6,7,10,11,13,14)

Минимальная форма:

$$f(a,b,c,d)_{МКНФ} = (a \vee overline{c})\And (b \vee overline{c})\And (overline{c} \vee d)\And (overline{b} \vee c \vee overline{d})$$

Пример 3.7. На этом примере хотелось бы продемонстрировать необходимость использования одного из основных принципов построения минимальных форм, а именно, поиск существенных импликант на первоначальном этапе анализа диаграммы.

Пусть необходимо найти минимальную дизъюнктивную нормальную форму для логической функции, заданной в виде СДНФ:

f(a,b,c,d)_СДНФ= ∑(0,2,3,7,9,10,11,14)

Решение

Этап 1.

Занести значение функции на диаграмму Вейча для четырех переменных:

Этап 2.

Сначалапокажем, что бросающееся в глаза решение, связанное с использованием одного 3-куба и четырех 2-кубов, не обеспечивает получения минимальномой ДНФ:

Решение на данном этапе должно проходить следующим образом.

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

На диаграмме они отмечены полужирным шрифтом и будут являться существенными импликантами.

Этап 3.

Так как все 1-клетки вошли в какой-либо из m-кубов, то осталось только записать минимальную ДНФ:

$$f(a,b,c,d)_{МДНФ} = a \overline{b}d \vee a c\overline{d} \vee\overline{a}сd \vee\overline{a}\overline{b}\overline{d}$$

Необходимо обратить внимание на то, что, как указывалось выше, не следует начинать поиск покрытий с отыскания m-кубов максимально возможной площади. Так, в данном случае 1-клетки (2,3,10,11) можно было бы включить в 2-куб ($$\overline{b}c$$). Однако при этом все равно сохранилась бы необходимость покрытия остальных 1 клеток 1-кубами. Поэтому данный 2 куб в окончательный вариант покрытия входить не должен.

Следует отметить, что метод минимизирующих карт дает быстрое и наглядное решение для функции от небольшого числа переменных (обычно, он используется для минимизации ФАЛ от трех либо четырех переменных, в очень редких случаях при достаточном опыте разработчика он может быть использован для минимизации функции от пяти переменных).

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

Минимизация неполностью определенных ФАЛ

Неполностью определенной ФАЛ от n переменных называется функция, заданная на множестве наборов входных переменных, меньше чем 2ⁿ.

Такая ситуация в вычислительной технике встречается в двух случаях:

какие-либо из наборов переменных никогда не могут появиться, и поэтому значение функции на этих наборах определять не имеет смысла. Например, в качестве входных переменных выступают показания часов. Тогда наборы от 12 до 15 (при 4-разрядном представлении) никогда в реальности не встретятся;

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

Пусть функция f(x₁, x₂,..., x_n) не определена на p наборах аргументов. Тогда не полностью определенную функцию $$\phi(x^1,x^2,...,x^n)$$ будем считать эквивалентной функции $$f(x^1,x^2,...,x^n)$$, если ее значения на тех наборах, на которых функция $$f(xx^1,x^2,...,x^n)$$ определена, совпадают.

Очевидно, существует 2^р различных функций, эквивалентных исходной. Задача минимизации состоит в выборе такой эквивалентной $$\phi (x^1,x^2,...,x^n)$$, которая имеет простейшую форму.Проведем такую минимизацию по методу диаграмм Вейча.

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

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

Пример 3.8. Получить методом диаграмм Вейча минимальную дизъюнктивную нормальную форму неполностью определенной ФАЛ, заданной в следующем виде:

f(a,b,c,d) = ∑(0,5,8,12,15), Х(1,2,3,10.13,14),

где под знаком X перечислены номера наборов, на которых значение функции не определено.

Решение

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

Для получения минимальной ДНФ вначале на диаграмме Вейча отметим на все 1 клетки и клетки с неопределенными значениями логической функции:

Отметим существенные имликанты для данной функции, принимая клетки с неопределенными значениями за 1-клетки, если это способствует построению покрытия меньшего ранга:

Импликанты в столбце $$\overline{b}\overline{d}$$ нельзя в полной мере считать существенными, так как для каждой из них можно подобрать два равнозначных покрытия, но именно приставленное на диаграмме выше позволяет покрыть их обе сразу. Здесь мы сталкиваемся с ситуацией некоторого эвристического перебора, о котором говорилось выше и который во многом зависит от опыта разработчика.

Оставшаяся непокрытой одна 1-клетка может быть включена в два равноценных покрытия:

Это даст тупиковую (она же и минимальная) нормальную форму:

$$f(a,b,c,d)_{МДНФ1} = ab\vee\overline{b}\overline{d}\vee\overline{a}\overline{c}d$$

Другой вариант покрытия этой 1-клетки даст следующую минимальную дизъюнктивную нормальную форму:

$$f(a,b,c,d)_{МДНФ2} = ab\vee\overline{b}\overline{d}\vee b\overline{c}d$$

Теперь получим МКНФ этой же функции. Для этого удобнее сначала представить сокращенную запись ее совершенной конъюнктивной нормальной формы:

$$f(a,b,c,d)_{СДНФ} = \sum(0,5,8,12,15), Х(1,2,3,10.13,14)$$ $$f(a,b,c,d)_{СКНФ} = \And (4,6,7,9,11), Х(1,2,3,10.13,14)$$

Отметим на диаграмме Вейча все 0-клетки и клетки с неопределенными значениями функции:

Выделим на диаграмме существенные имлиценты:

Так как все покрытия, использованные для покрытия существенных имплицент, покрыли и все остальные имплиценты данной функции, то эта ФАЛ будет иметь единственную минимальную КНФ:

$$f(a,b,c,d)_{МКНФ} = (a \vee\overline{c}) (b \vee d) (a \vee\overline{b}\vee d)$$

Отметим, что значения функции в неопределенных клетках при получении минимальной дизъюнктивной и минимальной конъюнктивной нормальной форм не связаны между собой. Так, например, значение Х-клетки с координатами $$\overline{a}\overline{b}c\overline{d}$$ было принято равным единице при получении минимальной дизъюнктивной нормальной формы и, в то же время, равной нулю при получении минимальной конъюнктивной нормальной формы.

Х-клетки, которые не способствовали получению наилучшего покрытия 1-клеток при получении МДНФ, принимаем за 0-клетки. Аналогично, Х-клетки, которые не способствовали получению наилучшего покрытия 0-клеток при получении МКНФ, принимаем за 1 клетки.Так для рассматриваемой функции при получении МДНФ Х-клетку с координатами $$\overline{a}\overline{b}c\overline{d}$$при получении МДНФ мы рассматриваем как 1-клетку, а при получении МКНФ – как 0-клетку.

Краткие итоги

В лекции рассмотрены различные методы минимизации логических функций: на основе теоремы Квайна, метода Квайна – Мак-Класки, диаграмм Вейча, не полностью определенных логических функций, которые могут быть использованы как для небольшого (три-четыре) числа переменных непосредственно разработчиками несложных вычислительных устройств, так и для минимизации ФАЛ от произвольного числа аргументов с использованием разнообразных компьютерных алгоритмов.

Вопросы и задания

Перечислите и охарактеризуйте методы минимизации логических функций.

Укажите преимущества и недостатки различных методов минимизации логических функций.

Дайте формулировку теоремы Квайна. Позволяет ли теорема Квайна минимальную форму записи логической функции?

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

Можно ли утверждать, что для того, чтобы получить минимальную конъюнктивную нормальную форму какой-либо логической функции, достаточно получить инверсию от ее минимальной дизъюнктивной нормальной формы?

Какие из видов функции имеют единственное представление: совершенная форма, сокращенная, тупиковая, минимальная?

Что представляют собой импликантные и имплицентные матрицы? Для каких целей они используются?

Какие усовершенствования внес Мак-Класки в минимизацию логических функций?

С какой целью в методе Квайна – Мак-Класки двоичные наборы разбиваются на группы по количеству единиц в наборе? Какую роль играют "пустые" группы в этом методе?

Каковы области применения при минимизации диаграмм Вейча и метода Квайна – Мак-Класки? Почему?

Почему машинные алгоритмы минимизации логических функций обычно базируются на методе Квайна – Мак-Класки?

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

Как выполнить минимизацию не полностью определенной ФАЛ методом Квайна – Мак-Класки?