Глава 1. Минимизация функций алгебры логики в классе днф[*]

Оглавление

Предисловие 4

Введение 5

Глава1. Минимизация функций алгебры логики в классе ДНФ 7

1. Геометрический метод 8

2. Метод неопределенных коэффициентов 10

3. Метод минимизирующих карт (Гарвардский метод) 13

4. Метод Квайна 16

5. Метод Квайна-Мак-Класки 23

6. Метод карт Карно (Вейча) 25

7. Абсолютно минимальные представления 31

Глава 2. Преобразования и минимизация в базисе, 32

состоящем из функции Вебба или из функции Шеффера.

Список литературы 42

Приложение 44

Задачи к практическим занятиям, выполнению

расчетно-графических работ и для самостоятельного

изучения методов минимизации ФАЛ.

ПРЕДИСЛОВИЕ

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

В пособии излагаются принципы построения наиболее простых и распространенных методов минимизации, дополненные подробным разбором решений типовых примеров.

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

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

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

ВВЕДЕНИЕ

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

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

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

В настоящее время наибольшее распространение получил базис, состоящий из отрицания, конъюнкции и дизъюнкции {-,&, Ú }. Образующие его функции наиболее просты с точки зрения математических преобразований и технической реализации.

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

1) закон склеивания (или , где - произвольная булева функция, - отдельный знак);

2) закон поглощения (или , где - любая булева функция, - отдельный знак).

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

Заметим, что речь идет о минимальном числе букв, а не переменных. Например, содержит 7 букв, но 3 переменных.

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

Введем некоторые необходимые понятия.

Рассмотрим функцию . Каждое из слагаемых соответствует только одной единицы в таблице истинности данной функции. Говорят, что каждое слагаемое покрывает единицу функции, а в совокупности они покрывают данную функцию, т.е. являются ее покрытием. Но заметим, что упростив функцию , получим более простое покрытие. Оба представления соответствуют одной и той же таблице истинности функции, т.е. обращаются в 1 и 0 на одних и тех же наборах переменных (табл. 2.1). Если обратиться к отдельным слагаемым 2-го представления, нетрудно заметить, что обращается в единицу на двух наборах (1, 0), (1, 1), а - на (0, 0), (1, 0), совместно они покрывают единицами все единицы данной функции. Отметим, что оба слагаемых и обращаются одновременно в нуль на наборе (0, 1), т.е. там, где функция равна нулю.

Таблица 2.1

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

Функция , являющаяся элементарным произведением и входящая в функцию , называется импликантой.

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

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

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

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

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

Приведем схему упрощения формы булевой функции

Сокращенная ДНФ

Тупиковая ДНФ

Минимальные ДНФ (МДНФ)

Кратчайшие ДНФ (КрДНФ)

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

ГЛАВА 1. МИНИМИЗАЦИЯ ФУНКЦИЙ АЛГЕБРЫ ЛОГИКИ В КЛАССЕ ДНФ[*].

Из известных методов минимизации булевых функций в данной главе рассматриваются наиболее простые и распространенные в базисе {-,&, Ú }.

I Геометрический метод.

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

Изобразим область определения произвольной булевой функции трех переменных – это вершины трехмерного куба. Элементам куба можно поставить во взаимо-однозначное соответствие конъюнкции различного ранга: вершинам куба – конъюнкции третьего ранга, ребрам – второго, граням – первого. Каждый геометрический эквивалент меньшей размерности покрывается всеми геометрическими эквивалентами большей размерности. Конъюнкции большего ранга покрываются конъюнкциями меньшего ранга (см. рисунок 2-1).

Так, например, конъюнкции и покрываются конъюнкцией (две вершины- ребро);конъюнкции , ,, покрываются либо двумя конъюнкциями и , либо и

либо только (четыре вершины –либо два ребра, либо одна грань).

рис. 2-1

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

, где

- ранги покрывающих интервалов. Задача о нахождении минимальной ДНФ соответствует нахождению такого покрытия

, в котором сумма рангов всех покрывающих интервалом является минимальной, т.е.

- минимально, ибо ранг

совпадает с числом букв, входящий в

Для функций и на приведенных рисунках 2-2 минимальными формами будут , или Для второй функции задача решается неоднозначно.

Пример 1: Минимизировать функцию, заданную следующей таблицей истинности

Таблица 2-2
x ₁
x ₂
x ₃
f(x ₁, x ₂, x ₃)

Ее формула в СДНФ имеет вид:

Отметим на рис. 2-3 вершины, соответствующие конъюнкциям, входящим в СДНФ данной функции.

x ₂

Заметим, что четыре вершины лежат в одной грани

, а две на одном ребре

Откуда следует, что минимальная форма функции и есть сумма этих интервалов

, т.е.

Другого варианта решения здесь не может быть. Задача решается однозначно.

2 Метод неопределенных коэффициентов.

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

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

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

(1)

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

Рассмотрев все уравнения, в правой части которых стоят нули, и приравняв все коэффициенты этих уравнений нулю, в остальных уравнениях вычеркивают вошедшие в них нулевые коэффициенты. Удобно полученную систему переписать в более сокращенной форме, оставив в ней уравнения, в правой части которых стоят единицы, убрав при этом из этих уравнений нулевые коэффициенты. Затем выбирают в системе самые короткие уравнения. В этих уравнениях приравнивают единице коэффициенты, определяющие конъюнкции наименьшего возможного ранга (это возможно, т.к. дизъюнкция равна единице при обращении в единицу хотя бы одного члена). При этом надо выбрать такие конъюнкции наименьшего ранга, которые чаще встречаются в уравнениях системы. Остальные коэффициенты можно положить равными 0 или 1. Затем рассматривают оставшиеся уравнения и в них выбирают коэффициенты, соответствующие конъюнкциям наименьшего ранга по тому же принципу, и т.д.

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

Пример 2. Минимизировать функцию (см. пример 1).

Составим систему (обратите внимание на то, что она имеет стандартный вид, лишь в правой части изменяются значения в зависимости от таблицы истинности функции). Для удобства записи системы слева помещают координаты вершин (область определения функции). Верхние индексы коэффициентов комбинируют соответственно из записанных координат вершин с учетом взятых нижних индексов. Например, для второй вершины (0,0,1) верхним индексом для коэффициента будет 00; для - 01 и т.д.

Из уравнений 2, 5, 6 в силу свойств дизъюнкции вытекает, что

Удобно вычеркнуть уравнения, в правой части которых стоят нули, а в остальных уравнениях вычеркнуть коэффициенты равные нулю.

После этого система примет вид:

(2)

В системе (2) в силу свойства дизъюнкции можно приравнять единице коэффициент , тогда 2, 3, 4 и 5 уравнения этой системы превращаются в тождества, из первого же уравнения системы возьмем . Все остальные коэффициенты во всех уравнениях положим равными нулю.

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

Итак, мы нашли , остальные коэффициенты равны нулю. Отсюда минимальная форма данной функции:

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

3.Метод минимизирующих карт (гарвардский метод).

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

Рассмотрим следующую таблицу

(3)

Эта таблица служит более компактной записью системы уравнений (1) метода неопределенных коэффициентов, где вместо коэффициентов в соответствующей клетке записываются сами конъюнкции. Каждая строка таблицы (3) заменяет собою соответственно 1-ое, 2-ое, …… 8-ое уравнения системы (1). Дизъюнкция всех элементов строки таблицы есть значение функции в вершине, определяемой соответствующими переменными. Так, первая строка есть значение функции в вершине , четвертая в или в переводе на координаты соответственно в (1, 1, 1), (1, 0, 0).

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

Пусть, например, в СДНФ не входит конъюнкция , тогда в минимальную форму не входит, например, член (аналогично и другие конъюнкции 3-ей строки).

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

Таблица (3) называется минимизирующей картой.

Минимизация функции производится по следующим правилам:

1. Все строки таблицы, которые соответствуют конъюнкциям последнего столбца, отсутствующим в СДНФ данной функции, вычеркивают.

2. В столбцах оставшихся строк вычеркивают все элементы, попавшие в вычеркнутые строки.

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

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

Заметим, что нахождение МДНФ неоднозначно, ибо произволен выбор минимальных конъюнкций в строках. Однако, все получаемые по этому методу МДНФ будут “одинаково минимальны”.

Пример 3. Минимизировать функцию (см. пример 1)

Строим для функции минимизирующую карту

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

Итак, получим МДНФ данной функции в виде:

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

Пример 4. Минимизировать функцию.

Согласно правилам 1, 2 вычеркиваем конъюнкции

Для удобства табличку оставшихся конъюнкций начертим отдельно, выбросив 1-3 столбцы, 1, 8 строки.

Положим во 2-ой строке равным 1, обведем рамочкой, остальные члены положим равными нулю. Вычеркнем нулевые члены в 6-й строке, в 1-й строке. Выберем 1 из оставшихся строк самые короткие, 1-я и 6-я строки. Положим в них соответственно , остальные члены равными нулю. В строках 4 и 5 будет по одному члену, равному 1. Итак, в каждой строке таблицы есть один член, равный 1, следовательно, минимальная форма функции будет

Возможен другой вариант минимальной формы. Рассмотрим на таблице.

Пусть в 4-й строке , а остальные члены равны нулю. Тогда в строке 5: можно положить равными нулю. Вычеркнем в 1-й и 6-й строках (они короче других), положим соответственно . Тогда в строках 2 и 3 будет по одному члену, равному единице. Итак, минимальная форма функции

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

МЕТОД КВАЙНА.

Этот метод применим к функции, записанной в СДНФ. Метод минимизации функции проводится поэтапно.

1 этап. Нахождение первичных простых импликант.

Все конъюнкции СДНФ данной функции сравнивают между собой попарно, применяя закон склеивания . Удобно предварительно члены функции занумеровать, и поместить в таблицу. Сравнить последовательно 1-й член со всеми остальными. Результаты склеивания записать во 2-й столбец, указывая в скобках номера склеенных членов, а склеенные члены 1-го столбца отметить звездочкой (*).Ранг полученных конъюнкций на единицу ниже, т.е. они содержат на один знак меньше. Эти конъюнкции нумеруются, затем операцию повторяют, записывая результат в 3-й столбец и т.д. Заканчивают эту процедуру когда вновь полученные конъюнкции уже не склеиваются между собой. Все неотмеченные знаком * конъюнкции называются первичными (простыми) импликантами. Все члены, отмеченные знаком *, будут поглощены простыми импликантами на основании операции поглощения . Для удобства простые импликанты в таблице обводятся рамочкой.

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

Прежде рассмотрим 1-й этап на примерах.

Пример 5. Минимизировать функцию (см. пример 1)

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

	Члены	Результаты 1-го склеивания	Результаты 2-го склеивания
1.	*	(1, 2)	(2, 5)
2.	*	* (2, 3)	(3, 4)
3.	*	* (2, 4)
4.	*	* (3, 5)
5.	*	* (4, 5)

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

Пример 6. Минимизировать функцию.

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

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

Если в результате склеивания получаются одинаковые импликанты, то оставляют только одну из них.

Итак, 1-й этап (“Нахождение первичных простых импликант”) закончен. Ими являются все импликанты, обведенные рамочками.

Этап. Расстановка меток.

Составляется таблица, число строк которой равно числу найденных простых импликант, а число столбцов – числу членов СДНФ данной функции. В 1-й столбец записываются первичные импликанты, в 1-ю строку

	Члены	Результаты 1-го склеивания	Результаты 2-го склеивания
1.	*	(1, 4)	(3, 9)
2.	*	(1, 6)	(4, 6)
3.	*	* (2, 3)
4.	*	* (2, 7)
5.	*	(3, 4)
6.	*	* (3, 8)
7.	*	(5, 6)
8.	*	(5, 8)
9.		* (7, 8)

члены функции. Если в член СДНФ входит первичная импликанта, то на пересечении их ставится метка .

У первичных импликант 3-го порядка метки удобно проставить по номерам склеенных членов 1-го столбца, приписанным у импликант рядом (в скобках), а у первичных импликант 2-го порядка по номерам членов 1-го столбца. Число меток в строке зависит от числа исключенных букв в импликанте. Для исключенных букв число меток будет .