1.Основные понятия булевой алгебры
Технические вопросы, связанныес составлением логических схем ЭВМ, можно решить с помощью математического аппарата,объектом исследования которого являются функции, принимающие, так же как и их аргументы,только два значения — “0” и “1”.
Таким аппаратом является математическаялогика (алгебра логики, булева алгебра).
Логика — это наука о законахи формах мышления.
Математическая логика занимаетсяизучением возможностей применения формальных методов для решения логических задач.Один из разделов математической логики является алгебра логики.
Основное понятие алгебры логики- высказывание. Высказывание — это некоторое предложение, о котором можно утверждать,что оно истинно или ложно.
Любое высказывание можно обозначитьсимволом х и считать, что х=1, если высказывание истинно, а х=0 — если высказываниеложно. Истинному высказыванию соответствует утверждение -“Да”, ложному высказыванию- утверждение — “Нет”.
Логическая (булева) переменная- такая величина х, которая может принимать только два значения х={0,1}.
Высказывание абсолютно истинно,если соответствующая ей логическая величина принимает значение х=1 при любых условиях.
Высказывание абсолютно ложно,если соответствующая ей логическая величина принимает значение х=0 при любых условиях.
Функция f, зависящая от n переменных x1,x2,...,xn, называется булевой, или переключательной, если функция f и любой из ее аргументов /> принимают значения только из множества{0,1}. Аргументы булевой функции также называются булевыми.
2.Способы задания булевых функций
Произвольная булева функциязадается одним из трех способов: матричным (табличным), геометрическим и аналитическим.
При матричном способе булевафункция f(x1,...,xn) задаетсятаблицей истинности (табл. 1 и 2), в левой части которой представлены все возможныедвоичные наборы длины n, а вправой указывается значение функции на этих наборах.
Под двоичным набором понимаетсясовокупность значений аргументов x1,x2,...,xn булевой функции f. Двоичный набор имеет длину n, если он представлен n цифрами из множества{0,1}. В табл. 1 и 2 перечислены все двоичные наборы соответственно длины 3 и 4.
Таблица 1 Таблица 3х1 х2 х3 f(х1, х2,, х3)
Номер
набора f(х1, х2,, х3) 1 1 1 1 1 2 1 1 3 1 1 4 1 1 1 1 5 1 1 1 6 1 1 1 1 7 1
Таблица 2 Таблица 4.x1 x2 x3 x4 f(х1… х4) x1,x2,...,xj-1 xj,xj+1,...,xn 00..0 0...1 ... 11..1 1 1 00...0 ... 1 1 1 1 1 1 1 1 00...1 ... 1 1 1 f(х1… хn) 1 1 1 1 1 1 1 1 ... ... ... ... ... 1 1 1 1 1 1 1 1 1 1 11...1 1 1 1 1 1 1 1 1
Иногда двоичные наборы в таблицеистинности булевой функции удобно представлять номерами наборов. Запишем аргументыx1,x2,...,xn в порядке возрастанияих индексов. Тогда любой двоичный набор можно рассматривать какцелое двоичноечисло N, называемое номером набора. Например,двоичные наборы 0101 и 1000 имеют номера 5 и 8 соответственно. Очевидно, любая булевафункция может быть задана таблицей истинности, в которой двоичные наборы замененысвоими номерами (табл.3).
Булевы функции, зависящиеот большого числа переменных, задавать таблицей истинности неудобно в силу ее громоздкости.Например, таблица истинности булевой функции 8 переменных будет содержать 28 = 256строк. Поэтому для задания функций многих переменных удобно использовать модификациютаблицы истинности.
/>Рассмотримспособ построения такой таблицы истинности для функции n переменных. Множество из n переменных функции разбивается на два подмножества: x1,x2,...,xj-1 ихj, xj,xj+1,...,xn. Переменными x1,x2,...,xj-1 отмечаютстроки таблицы истинности, задавая в каждой строке значение соответствующего двоичногонабора длины j-1. Переменными xj,xj+1,...,xn отмечают ее столбцы,задавая в каждом столбце значения соответствующего двоичного набора длины n-j+1. Значение функции записывается в клетке на пересечении соответствующейстроки и столбца (табл.4.).
При геометрическом способебулева функция f(х1,..., xn) задается с помощью n-мерного куба. В геометрическом смыслекаждый двоичный набор есть n-мерныйвектор, определяющий точку n-мерногопространства. Исходя из этого, все множество наборов, на которых определена функцияn переменных, представляется вершинами n-мерного куба. Отмечая точками вершиныкуба, в которых функция принимает единичные (либо нулевые) значения, получим геометрическоепредставление функции. Например, булева функция, заданная табл.1, геометрическипредставляется 3-мерным кубом (рис. 1.в).
/>
/>
а) n=1 б) n=2 в) n=3
Рисунок 1- Геометрическоезадание булевой функции:
а) одной переменной: б) двухпеременных; в) трех переменных.
При аналитическом способебулева функция задается формулами, т. е. аналитическими выражениями, построеннымина основе операций булевой алгебры. Аналитический способ задания булевых функцийзанимает особое место в проектировании цифровых автоматов. Фактически, все преобразованиянад булевыми функциями, необходимые для построения цифровых автоматов, ведутся нааналитическом уровне.
Рассмотрим области определениябулевых функций. Между двоичными наборами и двоичными числами существует взаимнооднозначное соответствие. Следовательно, существует 2n различных наборов двоичных переменных.
Таким образом, областью определениябулевой функции n переменных при матричном способе заданияявляется множество всех возможных двоичных наборов длины n, а при геометрическом способе задания— множество всех вершин n-мерногоединичного куба.
Булеву функцию, определеннуюна всех своих наборах, называют полностью определенной.
Булеву функцию n переменных называют неполностью определенной или частичной, еслиона определена не на всех двоичных наборах длины n.
3.Булевы функции одной и двух переменных
Рассмотрим наиболее употребимыебулевы функции одной и двух переменных. Функции одной переменной представлены втабл. 5.
Таблица 5f(х) х Усл. Наименование 1 обозн f0 (х) тождественный ноль (константа 0); f1 (х) 1 х тождественная функция f2 (х) 1
/> отрицание х (инверсия); f3 (х) 1 1 1 тождественная единица (константа 1).
Функции двух переменных представленыв табл. 6.
Рассмотренные простейшие булевыфункции позволяют строить новые булевы функции с помощью обобщенной операции, называемойоперацией суперпозиции. Фактически операция суперпозиции заключается в подстановкевместо аргументов других булевых функций (в частности аргументов).
Отметим, что реально элементарнойфункции соответствует реализующий ее элемент, а суперпозиции булевых функций соответствуетсоединение элементов.
Таблица 6 х1 1 1 Наименование функции х2 1 1 f0 (х1, х2) константа 0 f1 (х1, х2) 1 конъюнкция f2 (х1, х2) 1 запрет по х2 f3 (х1, х2) 1 1 переменная х1 f4 (х1, х2) 1 запрет по х1 f5 (х1, х2) 1 1 переменная х2 f6 (х1, х2) 1 1 сумма по модулю 2 f7 (х1, х2) 1 1 1 дизъюнкция f8 (х1, х2) 1 операция Пирса (ф-ция Вебба) f9 (х1, х2) 1 1 логическая равнозначность f10 (х1, х2) 1 1 инверсия х2 f11 (х1, х2) 1 1 1 импликация от х2 к х1 f12 (х1, х2) 1 1 инверсия х1 f13 (х1, х2) 1 1 1 импликация от х1 к х2 f14 (х1, х2) 1 1 1 штрих Шеффера f15 (х1, х2) 1 1 1 1 константа 1
Суперпозиция булевых функцийпредставляется в виде логических формул. Однако следует отметить:
— одна и та же функция можетбыть представлена разными формулами;
— каждой формуле соответствуетсвоя суперпозиция и, следовательно, своя схема соединений элементов;
— между формулами представлениябулевых функций и схемами, их реализующими, существует взаимнооднозначное соответствие.
Очевидно, среди схем, реализующихданную функцию, есть наиболее простая. Поиск логической формулы, соответствующейэтой схеме, представляет большой практический интерес, а преобразование формул булевыхфункций основано на использовании соотношений булевой алгебры.
4.Основные законы и тождества булевой алгебры
Для булевой алгебры определеныодна одноместная (унарная) операция “отрицание” и две двухместные (бинарные) операцииконъюнкция и дизъюнкция (обозначаются «Ù», «Ú» соответственно). Приведем некоторые основные формулы.
Под бинарной операцией намножестве А, в общем случае понимают отображение декартового произведения множеств(А х А) в множество А. Иными словами, результат применения бинарной операции к любойупорядоченной паре элементов из А есть также элемент из множества А.
Под унарной операцией на множествеА понимают выделение (фиксацию) какого-либо элемента множества А.
Преобразование формул булевыхфункций применением только аксиом булевой алгебры малоэффективно. Для упрощенияформул используется целый ряд соотношений. Из коммутативности и ассоциативностидизъюнкции следует, что дизъюнкция нескольких переменных может выполняться последовательно,причем порядок взятия дизъюнкции не влияет на результат. Формулы де Моргана:
/> />
Следствия из формул де Моргана:
/> />
Формулы для системы функций:
операция поглощения (х поглощаету): хÚху=х; или х(хÚу)=х.
операция склеивания: хуÚх/>=х, или (хÚу)Ù(хÚ/>)=х
5.Аналитическое представление булевых функций
Рассмотрим универсальные (канонические)формы представления, дающие возможность получить аналитическую форму непосредственнопо таблице истинности для произвольной булевой функции. Эта форма в дальнейшем можетбыть упрощена. Поскольку между множеством аналитических представлений и множествомсхем, реализующих булеву функцию, существует взаимно однозначное соответствие, отысканиеканонической формы представления булевой функции является начальным этапом синтезасхемы, ее реализующей. Наиболее широкое распространение получила совершенная дизъюнктивнаянормальная форма (СДНФ). Прежде чем перейти к ее изучению, приведем определениеконституенты единицы — понятия, которым будем широко пользоваться в дальнейшем.
Конституентой единицы (коньюнктивным термом) называется функцияf(x1,x2,...,xn), принимающая значение 1 только на единственномнаборе.
Конституента единицы записываетсякак логическое произведение n различных булевыхпеременных, некоторые из них могут быть с отрицаниями. Можно легко выразить любуюбулеву функцию как дизъюнкцию конституент единицы, соответствующих тем наборам,на которых функция равна 1.
Дизъюнкция конституент 1,равных 1 на тех же наборах, что и заданная функция, называется совершенной дизъюнктивнойнормальной формой переключательной функции( СДНФ).
Наборы, на которых функцияf принимает значение 1, часто называютсяединичными, остальные — нулевыми наборами. Выписывать в СДНФ имеет смысл толькоконституенты единицы, соответствующие единичным наборам.
Пример. Выпишем СДНФ для функций,заданных таблицей истинности (табл. 7.).
Таблица 7. х1х2х3 f(х1, х2, х3) 0 0 0 1 0 0 1 1 2 0 1 0 1 3 0 1 1 4 1 0 0 5 1 0 1 1 6 1 1 0 7 1 1 1 1
fСДНФ(х1, х2, х3)=
/>Ú/>Ú/>Ú/>
fСКНФ(х1, х2, х3)=
/>Ù/>Ù />Ù/>
Другая известная форма носит названиесовершенной конъюнктивной номальной формы (СКНФ). Она строится аналогично СДНФ.
Определение. Конституентойнуля (дизьюнктивным термом) называется функция, принимающая значение 0 на единственномнаборе.
Конституента нуля записываетсяв виде элементарной дизъюнкции всех переменных. Каждому набору соответствует свояконституента 0. Например, набору 0110 переменны х1, х2, х3, х4 соответствует конституентануля />.
СКНФ представляется как конъюнкцияконституент нуля, соответствующих нулевым наборам функции.
6.Функционально полные системы булевых функций
Любая булева функция можетбыть представлена аналитически одной из нормальных форм (СДНФ, СКНФ). Последниеиспользуют ограниченное число элементарных булевых функций. Например, для СДНФ такимифункциями являются «конъюнкция», «дизъюнкция» и «отрицание». Существуют системыбулевых функций, с помощью которых можно аналитически представить любую сколь угодносложную булеву функцию. Проектирование цифровых автоматов основано на знании такихсистем булевых функций. Последнее особенно важно для разработки комплектов интегральныхмикросхем, из которых можно построить произвольный цифровой автомат. Проблема функциональнойполноты является центральной проблемой функциональных построений в алгебре логики.
Определение. Функциональнополной системой булевых функций (ФПСБФ) называется совокупность таких булевых функций{f1, f2,..., fk}, чтопроизвольная булева функция f может быть записанав виде формулы через функции этой совокупности.
К ФПСБФ следует отнести системы:{/>,/>, НЕ}, {/>, />, НЕ}.
Определение свойств ФПСБФосновано на понятии замкнутого относительно операции суперпозиции класса функций.Класс булевых функций, функционально замкнутый по операции суперпозиции, есть множествофункций, любая суперпозиция которых дает функцию, также принадлежащую этому множеству.Среди функционально замкнутых классов выделяют классы особого типа, называемые предполными,которые обладают следующим свойством. Предполный класс S не совпадает с множеством P2 всех возможных булевых функций, однако, если в него включитьлюбую, не входящую в S, булевуфункцию, то новый функционально замкнутый класс будет совпадать с множеством P2. Проведенные исследования показали,что предполных классов пять, а для построения ФПСБФ необходимо и достаточно, чтобыее функции не содержались полностью ни в одном из пяти предполных классов. Перечислимпредполные классы булевых функций:
1) булевы функции, сохраняющиеконстанту 0;
2) булевы функции, сохраняющиеконстанту 1;
3) самодвойственные булевыфункции;
4) линейные булевы функции;
5) монотонные булевы функции.
Определение. К булевым функциям,сохраняющим константу 0, относят такие булевы функции f(x1,x2,...,xn), для которых справедливо соотношение
f (0,..., 0)=0.
Примерами булевых функций,сохраняющих константу 0, являются функции f0 – f7 (табл.6.).
Определение. К булевым функциям,сохраняющим константу 1, относят такие булевы функции f(x1,x2,...,xn), для которых справедливо соотношение f (1,1, ..., 1)=1.
Примерами булевых функций,сохраняющих константу 1, являются функции f1, f3, f5, f7 (табл. 6).
Прежде чем ввести понятиекласса самодвойственных функций, дадим следующее определение.
Определение. Булевы функцииf1(x1,x2,...,xn) и f2(x1,x2,...,xn), называются двойственными друг другу, если выполняется соотношениеf1(x1,x2,...,xn) = />
Двойственными являются функциииз табл. 6 — f0 и f15, f1 и f7 и т. д.
Определение. К самодвойственнымбулевым функциям относят такие булевы функции, которые двойственны по отношениюк самим себе, т. е. справедливо соотношение f1(x1,x2,...,xn) = />.
Если условиться называть противоположныминаборами набор />/>/>и набор />, то определение самодвойственных функций дадим следующее.
Определение. Булева функцияназывается самодвойственной, если на любых двух противоположных наборах она принимаетпротивоположные значения.
Самодвойственными являютсяфункции f3, f5, f10, f12 из табл. 6… Из определения самодвойственнойфункции следует, что она полностью определяется своими значениями на первой половинестрок таблицы истинности.
Определение. К линейным булевымфункциям относят такие булевы функции, которые представимы в виде
f(x1,x2,...,xn)=с0/>с1х1/>.../>сnхn,
где сі/>/>{0, 1}, а /> - операция «сумма по mod 2».
Линейными являются булевыфункции из табл. 6 — f0, f3, f5 и т. д./>
Прежде чем ввести понятиекласса монотонных булевых функций, дадим следующее определение.
Определение. Двоичный набор/>не меньшедвоичного набора />, (т.е. />), если для каждой пары /> справедливо соотношение/>.
Так, набор 1011 ≥1010.Вместе с тем наборы 1011 и 0100 несравнимы в том смысле, что для них не выполняетсяни соотношение />, ни />.
Определение. Булева функцияf(x1,x2,...,xn) называется монотонной, если для любыхдвух наборов /> и /> таких, что /> имеет место неравенствоf/>/>f(/>)
Монотонными являются булевыфункции f0, f1,f3, f5 (из табл. 6) и т.д.
Приведем без доказательствадве формулировки теоремы о функциональной полноте.
Теорема. Для того чтобы системаS булевых функций была функционально полной,необходимо и достаточно, чтобы эта система содержала хотя бы одну булеву функцию,не сохраняющую константу 0, хотя бы одну булеву функцию, не сохраняющую константу1, хотя бы одну несамодвойственную булеву функцию, хотя бы одну нелинейную булевуфункцию и хотя бы одну немонотонную булеву функцию.
Система булевых функций являетсяфункционально полной тогда и только тогда, когда она целиком не содержится ни водном из предполных классов. При помощи функционально полной системы можно реализоватьбулеву функцию любой степени сложности.
Рассмотрим примеры ФПСБФ.К таким ФПСБФ, наиболее распространенным в практике построения цифровых автоматов,следует отнести: (/>, НЕ); (/>, НЕ); (V, НЕ); (/>, НЕ), (/>,1); где символами V, />, />, НЕ, 1 обозначеныбулевы функции: «дизъюнкция», «конъюнкция», «сумма по mod 2», «отрицание», «константа 1», соответственно.
7.Минимизация булевых функций
При проектировании цифровыхавтоматов широко используются методы минимизации булевых функций, позволяющие получатьрекомендации для построения экономичных схем цифровых автоматов. Общая задача минимизациибулевых функций может быть сформулирована следующим образом: найти аналитическоевыражение заданной булевой функции в форме, содержащей минимально возможное числобукв. Следует отметить, что в общей постановке данная задача пока не решена, однакодостаточно хорошо исследована в классе дизъюнктивно-конъюнктивных нормальных форм.
Определение. Элементарнойконъюнкцией называется конъюнкция конечного числа различных между собой булевыхпеременных, каждая из которых может иметь или не иметь отрицания.
Определение. Дизъюнктивнойнормальной формой (ДНФ) называется дизъюнкция элементарных конъюнкций.
Определение. Минимальной дизъюнктивнойнормальной формой булевой функции называется ДНФ, содержащая наименьшее число букв(по отношению ко всем другим ДНФ, представляющим заданную булеву функцию). Определение.Булева функция g(x1,x2,...,xn) называетсяимпликантой булевой функции f1(x1,x2,...,xn), еслидля любого набора переменных, на котором g = 1, справедливо f = 1. Пример. Булевафункция f задана таблицей 8. Там же приведены всеее импликанты. При записи функции и ее импликант в СДНФ имеем
f= />Ú/>Ú/>
g1=/>
g2=/>
g3=/>V/>=/>
g4=/>
g5=/>vv/>=/>
g6=/>vv/>
g7=/>Ú/>Ú/>
Определение. Импликанта g булевой функции f, являющаяся элементарной конъюнкцией, называется простой, если никакая частьимпликанты g не является импликантой функции f.
Из примера видно, что импликантыg3 и g5 являются простыми импликантами функции f. Другие импликанты не являются простыми,так как их части являются импликантами функции f, например g3 являетсячастью g1. Приведем без доказательства два утверждения,полезные при получении минимальной ДНФ.
1. Дизъюнкция любого числаимпликант булевой функции f также является импликантой этой функции.
2. Любая булева функция fэквивалентна дизъюнкции всех своих простых импликант. Такая форма представлениябулевой функции называется сокращенной ДНФ.
Перебор всех возможных импликантдля булевой функции f из рассмотренного примера дает возможностьубедиться, что простых импликант всего две: g3 и g5. Следовательно,сокращенная ДНФ функции f имеет вид:
f = g3 V g5 =/>V />
Как видно из табл. 6.8., импликантыg3 и g5 в совокупности покрывают своими единицами все единицы функцииf. Получение сокращенных ДНФ является первымэтапом отыскания минимальных форм булевых функций. Как уже отмечалось, в сокращеннуюДНФ входят все простые импликанты булевой функции. Иногда из сокращенной ДНФ можноубрать одну или несколько простых импликант, не нарушая эквивалентности исходнойфункции. Такие простые импликанты назовем лишними. Исключение лишних простых импликантиз сокращенных ДНФ — второй этап минимизации.
Определение. Сокращенная ДНФбулевой функции называется тупиковой, если в ней отсутствуют лишние простыеимпликанты.
Устранение лишних простыхимпликант из сокращенной ДНФ булевой функции не является однозначным процессом,т.е. булева функция может иметь несколько тупиковых ДНФ.
Утверждение. Тупиковые ДНФбулевой функции f, содержащие минимальноечисло букв, являются минимальными. Минимальных ДНФ тоже может быть несколько.
Рассмотрим несколько методовминимизации. Все они практически различаются лишь на первом этапе — этапе получениясокращенной ДНФ. Следует отметить, что, к сожалению, поиск минимальной ДНФ всегдасвязан с некоторым перебором решений. Существуют методы уменьшения этого перебора,однако он всегда остается.7.1.Метод Квайна
Метод Квайна основываетсяна применении двух основных соотношений.
1. Соотношение склеивания
/>
где А — любое элементарноепроизведение.
2. Соотношение поглощения
/>/>
Справедливость обоих соотношенийлегко проверяется.
Теорема Квайна. Если в СДНФбулевой функции выполнить все возможные склеивания и поглощения, то в результатебудет получена сокращенная ДНФ.
Метод применим к совершеннойДНФ. Из соотношения поглощения следует, что произвольное элементарное произведениепоглощается любой его частью.
Для доказательства достаточнопоказать, что произвольная простая импликанта р = />может быть получена. В самом деле, применяя к р операциюразвертывания (обратную операции склеивания): />по всем недостающим переменным исходнойфункции f, получаем совокупность S конституент единицы. При склеивании всех конституент из S получим импликанту р. Последнее очевидно, поскольку операция склеиванияобратна операции развертывания. Множество S конституент обязательно присутствует в совершенной ДНФ функцииf поскольку р — ее импликанта.
Минимизация по методу Квайнавыполняется по следующему алгоитму:
1. Выполняются все склеиванияв СДНФ.
2. Выполняются все поглощения.
3. Результирующая функцияпроверяется на возможность дальнейшего склеивания и поглощения.
4. После получения сокращеннойДНФ строится импликантная матрица, по которой находятся “лишние” импликанты.
Пример. Пусть имеется булевафункция, заданная таблицей истинности (табл 9). Ее СДНФ имеет вид:
f= />Ú/>Ú/>Ú/>Ú/>Ú/>
Для удобства изложения пометимкаждую конституенту единицы из СДНФ функции f каким-либо десятичным номером (произвольно). Выполняем склеивания.Конституента 1 склеивается только с конституентой 2 (по переменной х3) и с конституентой3 (по переменной х2 ) конституента 2 с конституентой 4 и т. д. В результате получаем:
1-2: />
1-3: />
2-4: />
3-4: />
4-6: />
5-6: />
Заметим, что результатом склеиванияявляется всегда элементарное произведение, представляющее собой общую часть склеиваемыхконституент.
Далее производим склеиванияполучаемых элементарных произведений. Склеиваются только те произведения, которыесодержат одинаковые переменные. Имеет место два случая склеивания:
/>Ú/>=/>Ú/>Ú/>
/>Ú/>=/>Ú/>Ú/>
с появлением одного и тогоже элементарного произведения />. Дальнейшие склеивания невозможны.Произведя поглощения (из полученной ДНФ вычеркиваем все поглощаемые элементарныепроизведения), получим сокращенную ДНФ:
/>Ú/>Ú/>
Переходим к следующему этапу.Для получения минимальной ДНФ необходимо убрать из сокращенной ДНФ все лишние простыеимпликанты. Это делается с помощью специальной импликантной матрицы Квайна. Строкитакой матрицы отмечаются простыми импликантами булевой функции, т. е. членами сокращеннойДНФ, а столбцы — конституентами единицы, т. е. членами СДНФ булевой функции.
Пример (продолжение). Импликантнаяматрица имеет вид (табл. 10).
Таблица 10.Простые Конституенты единицы импликанты
/>
/>
/>
/>
/>
/>
/> Х Х Х Х
/> Х Х
/> Х Х
Как уже отмечалось, простаяимпликанта поглощает некоторую конституенту единицы, если является ее собственнойчастью. Соответствующая клетка импликантной матрицы на пересечении строки (с рассматриваемойпростой импликантой) и столбца (с конституентой единицы) отмечается крестиком (табл.10). Минимальные ДНФ строятся по импликантной матрице следующим образом:
1) ищутся столбцы импликантнойматрицы, имеющие только один крестик. Соответствующие этим крестикам простые импликантыназываются базисными и составляют так называемое ядро булевой функции. Ядро обязательновходит в минимальную ДНФ.
2) рассматриваются различныеварианты выбора совокупности простых импликант, которые накроют крестиками остальныестолбцы импликантной матрицы, и выбираются варианты с минимальным суммарным числомбукв в такой совокупности импликант.
Пример (продолжение). Ядромнашей функции являются импликанты /> и />. Импликанта /> - лишняя, так как ядро накрываетвсе столбцы импликантной матрицы. Поэтому функция имеет единственную тупиковую иминимальную ДНФ:
fmin=/>Ú/>
Следует отметить, что числоN крестиков в одной строке всегда является степенью 2. Более того, читатель можетлегко убедиться в том, что N = 2n-k, где k — число букв, содержащихся в простой импликанте.
Заметим также, что используяразличные соотношения, можно расширить область применения метода Квайна за пределысовершенной ДНФ.7.2 Метод Квайна-Мак-Класки
Метод представляет собой формализованныйна этапе нахождения простых импликант метод Квайна. Формализация производится следующимобразом:
1. Все конституенты единицыиз СДНФ булевой функции f записываются их двоичныминомерами.
2. Все номера разбиваютсяна непересекающиеся группы. Признак образования і-й группы: і единиц в каждом двоичномномере конституенты единицы.
3. Склеивание производят толькомежду номерами соседних групп. Склеиваемые номера отмечаются каким-либо знаком (зачеркиванием,звездочкой и т.д.).
4. Склеивания производят всевозможные,как и в методе Квайна. Неотмеченные после склеивания номера являются простыми импликантами.
Нахождение минимальных ДНФдалее производится по импликантной матрице, как и в методе Квайна. Более подробнорассмотрим метод на примере решения следующей задачи: минимизировать методом Квайна-Мак-Класкибулеву функцию f, заданную таблицейистинности (табл. 9).
1. В СДНФ функции f заменим все конституенты единицы их двоичными номерами: f=0001Ú0011Ú0101Ú0111Ú1110Ú1111
2. Образуем группы двоичныхномеров. Признаком образования і-й группыявляется і единиц в двоичном номере конституенты единицы (табл.11).
3. Склеим номера из соседнихгрупп табл.11. Склеиваемые номера обозначим звездочками (номер отмечается в томслучае, если участвует в склеивании хотя бы один раз). На месте разрядов, по которымпроизошло склеивание, проставляются прочерки. Результаты склеивания занесем в табл.12. Склеим номера из соседних групп табл. 12. Склеиваться могут только номера, имеющиепрочерки в одинаковых позициях. Склеиваемые номера отметим. Результаты склеиваниязанесем в табл. 13.
4. Имеем три простые импликанты:-111, 111-, 0--1.
Таблица 11 Таблица 12 Таблица 13Номер группы Двоичные номера кон-ституент 1
Номер
группы
Двоичные номера
импликант
Номер
группы
Двоичные номера
импликант - 1 (1-2) 00-1 * 1 0--1 1 0001 * 0-01 * 0--1 2 0011 * 2 (2-3) 0-11 * 2 -111 0101 * 01-1 * 111- 3 0111 * 3 (3-4) -111 1110 * 111- 4 1111 *
Таблица 14Простые Конституенты единицы импликанты
/>
/>
/>
/>
/>
/>
/>(0--1) Х Х Х Х
/>(-111) Х Х
/>(111-) Х Х
5. Строим импликантную матрицу(табл. 14). По таблице определяем совокупность простых импликант — 0--1 и 111-,соответствующую минимальной ДНФ. Для восстановления буквенного вида простой импликантыдостаточно выписать произведения тех переменных, которые соответствуют сохранившимсядвоичным цифрам:
fmin=/>Ú/>
Заметим, что разбиение конституентна группы позволяет уменьшить число попарных сравнений при склеивании.7.3 Метод диаграмм Вейча
Метод позволяет быстро получатьминимальные ДНФ булевой функции f небольшого числа переменных.В основе метода лежит задание булевых функций диаграммами некоторого специальноговида, получившими название диаграмм Вейча. Для булевой функции двух переменных диаграммаВейча имеет вид (табл. 15). Каждая клетка диаграммы соответствует набору переменныхбулевой функции в ее таблице истинности. В табл.15. это соответствие показано. Вклетке диаграммы Вейча ставится единица, если булева функция принимает единичноезначение на соответствующем наборе. Нулевые значения булевой функции в диаграммеВейча не ставятся. Для булевой функции трех переменных диаграмма Вейча имеет следующийвид (табл. 16). Добавление к ней еще такой же таблицы дает диаграмму для функции4-х переменных (табл. 17). Таким же образом, т. е. приписыванием еще одной диаграммы4-х переменных, к только что рассмотренной, можно получить диаграмму для функции5-ти переменных и т. д., однако диаграммы для функций с числом переменных больше4-х используются редко.
Для приведенных диаграмм характерноследующее:
1) каждой клетке диаграммы соответствуетсвой набор;
Таблица 15. Таблица 16.
/>
/>
/>
/>
/> 11 01
/> 110 111 011 010
/> 10 00
/> 100 101 001 000
/>
/>
/>
Таблица 17. Таблица18.
/>
/> х1
/> х1 1100 1101 1001 1000
/>
/> 1 1 1 х1 1110 1111 1011 1010 х3
/> 1
/> 0110 0111 0011 0010 х3
/>
/>
/>
/> 0100 0101 0001 0000
/>
/> х4 х4
/>
2) соседние наборы расположенырядом в строке либо в столбце. Соседними наборами называются наборы, отличающиесяодной компонентой. Напомним, что конституенты, соответствующие таким наборам, склеиваются(см. метод Квайна-Мак-Класки). Например, для функции, заданной табл. 18, конституенты,соответствующие паре единиц в левой части таблицы, склеиваются и порождают элементарноепроизведение из двух букв:
/>/>=/>
О паре единиц в правой частидиаграммы можно сказать то же самое: />/>=/>.
Отметим, что получающеесяэлементарное произведение легко определить сразу по диаграмме: это произведениепеременных, принимающих одно и то же значение в обеих клетках.
Еще одно важное замечание:столбцы, расположенные по краям диаграммы, тоже считаются соседними. Для нашегопримера это означает, что имеет место еще одно склеивание, в результате которого,следуя указанному правилу, получаем элементарное произведение />. Из рассмотренных ранееметодов нам известно, что возможно дальнейшее склеивание получаемых элементарныхпроизведений. На диаграммах Вейча они тоже располагаются рядом. Общее правило склеиванияна диаграммах Вейча можно сформулировать следующим образом: склеиванию подлежатпрямоугольные конфигурации, заполненные единицами и содержащие число клеток, являющеесястепенью 2. Получающееся новое элементарное произведение определяется как произведениепеременных, не меняющих своего значения на всех склеиваемых наборах. Число m оставшихся переменных в элементарном произведении определяетсялегко:
m=n-log2M,
где n- число переменных,
M — число склеиваемых наборов.
Метод широко используетсяна практике, благодаря простоте и удобству. После небольшой тренировки достигаетсяэлементарный навык определения минимальной ДНФ по диаграмме «с первого взгляда».
Минимизация булевой функциизаключается в нахождении минимального покрытия всех единиц диаграммы Вейча блокамииз единиц (указанной конфигурации), расположенных в соседних клетках диаграммы.При этом всегда считается, что левый край диаграммы Вейча 4-х переменных примыкаетк ее правому краю, а верхний край диаграммы примыкает к нижнему ее краю. Для удобстваможно предположить, что диаграмма сворачивается в цилиндр как по горизонтали, таки по вертикали. После получения минимального покрытия всех единиц диаграммы Вейча,минимальная ДНФ булевой функции записывается как дизъюнкция элементарных конъюнкций,соответствующих выделенным блокам единиц в диаграмме.
В диаграмме Вейча необходимои достаточно, чтобы каждая единичная клетка участвовала в склейке хотя бы один раз.
Новую склейку можно образовыватьв том случае, если есть хотя бы одна единичная клетка, не участвовавшая до этогов склейке.
Вся диаграмма должна бытьпокрыта наименьшим количеством склеек. В склейку может входить 2n соседних клеток (2, 4, 8, 16. и т.д.).
Рассмотрим несколько примеров.
Таблица 19 Таблица 20
/>/>/>/> /> X4 X3
/>
/>
/>
/>
/>
/>х1
/> х1 1 1
/>
/>х1 1 1 х3 х1 1 1 1 1 х3
/>/> 1 1 х3
/>/> 1 1 1 1 х3
/> 1 1
/>
/> 1 1
/>
/> х4 х4
/>
/> х4 х4
/>
f1=/>v/> f2= X4 v X37.4 Карты Карно
Иногда удобно пользоватьсянесколько другим представлением диаграмм с цифровым кодом. Это карты Карно. Примерыкарт Карно приведены на рисунке 2. По граням карты проставляются двоичные коды — коды Грея, что дает возможность легко проставлять значения функции и находить результат.Правила минимизации с применение карт Карно такие же, как и для диаграмм Вейча./> /> /> /> /> /> /> />
х2х3
х1 00 01 11 10
х3х4
х1х2 00 01 11 10 000 001 011 010 00 0000 0001 0011 0010 1 100 101 111 110 01 0100 0101 0111 0110 11 1100 1101 1111 1110 10 1000 1001 1011 1010 а) б)
Рисунок 2- Карты Карно:
а) функции 3-х переменных;
б) функции 4-х переменных.
8.Особенности минимизациибулевых функций большим числом переменных
Рассмотрим некоторые особенностиработы с картами Карно для большого числа переменных. При числе переменных, равномили больше пяти, отобразить графически функцию в виде единой плоской карты невозможно.В таких случаях строят комбинированную карту, состоящую из совокупности более простыхбазовых карт, например карт для функции 4-х переменных. Процедура минимизации вэтом случае состоит в том, что сначала находят минимальные формы внутри базовыхкарт, а затем, расширяя понятия соседних клеток, находят минимальные накрытия длясовокупности карт. Соседними клетками являются клетки, совпадающие при наложениибазовых карт друг на друга. Примеры карт Карно для булевых функций 5-ти и 6-ти переменныхпредставлены на рис. 3 и 4. соответственно.
/>Рисунок 3-Карта Карно для булевой функции 5-типеременных
/>х3х4
х1х2 00 01 11 10 00 01 11 10
00
01
11
10
х5=0 х5=1 /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> />
Рисунок 4- Карта Карно длябулевой функции шести переменных
х3х4
х1х2 00 01 11 10 00 01 11 10 00 01 11 10 00 01 11 10 00 01
/>11 10 (1) (2) (3) (4)
/>х5х6 00 01 11 10
По рисунку 4 можно сделатьвывод, что соседними являются для 1-й базовой карты — 2-я и 4-я; для 2-й — 1-я и3-я; для 3-й 2-я и 4-я; для 4-й — 1-я и 3-я.
При увеличении количествапеременных на одну, площадь карты увеличивается в два раза — к ней пририсовываетсяеще такая же карта. При этом новая переменная равняется 1 на новой карте, и 0 натой, которая была ранее.
9.Минимизация конъюнктивныхнормальных форм
Минимизация КНФ производитсяаналогично рассмотренным методам минимизации ДНФ булевых функций, поэтому остановимсялишь на основных положениях.
Напомним, что конституентойнуля называется функция, принимающая значение 0 на одном наборе. Она выражаетсядизъюнкцией всех переменных функций. Например, набору 0110 соответствует конституентануля X1 v/>v /> v X4
Определение. Имплицентой g булевой функции f называетсяфункция, принимающая значение 0 на подмножестве нулевых наборов функции f.
Определение. Простой имплицентойфункции f называется элементарная дизъюнкция, являющаясяимплицентой функции f, причем никакая еесобственная часть имплицентой функции f не является.
Задачей, минимизации КНФ являетсяопределение минимальной КНФ. Эта задача также решается в два этапа— поиск сокращеннойКНФ (конъюнкция всех простых имплицент) и затем нахождение минимальной КНФ. Второйэтап минимизации выполняется с помощью таблицы Квайна точно так же, как при поискеминимальной ДНФ, так как возможны только два варианта: либо данная простая имплицентапоглощает данную конституенту нуля, либо нет в соответствии с соотношением поглощения:(A v x)A=A
Что касается первого этапа— поиска всех простых имплицент, то практически все методы минимизации ДНФ имеютсвои аналоги для КНФ. Расссмотрим это подробнее.
Соотношение склеивания поКвайну:
(A v x) (A v />) =(A v x) (A v />)A =A
Метод Квайна для конъюнктивныхформ:
1. Выполняются все неполныесклеивания в СКНФ.
2. Выполняются все поглощения.
3. Результирующая функцияпроверяется на возможность дальнейшего склеивания и поглощения.
4. После получения сокращеннойКНФ строится имплицентная матрица, по которой находятся “лишние” имплиценты.
По диаграмме Вейча поиск минимальнойКНФ осуществляется так же просто, как в случае ДНФ. Отличие состоит лишь в том,что анализируются нулевые наборы и переменные выписываются с инверсиями (по правиламзаписи конституент 0).
10.Минимизация частичноопределенных булевых функций
х1
/>
/> 1 1 1
/> 1 1 1
/>
/>
/> б)
В реальных задачах очень частобывает так, что значение булевой функции на некоторых наборах не определено и можетдоопределяться произвольно. Выходные сигналы на этих наборах могут принимать любыезначения — 0 или 1. Входные наборы, которые дают неопределенное значение функцииназываются запрещенными. При синтезе схем, реализующих неполностью определенныефункции выходным сигналам, соответствующим запрещенным наборам, придают такие значения,при которых можно построить наиболее простую схему. В этом случае доопределениефункции целесообразно производить таким образом, чтобы ее минимальная нормальнаяформа имела наименьшее число букв из всех возможных вариантов доопределения. Рассмотримпростой пример (рис.5,6.).
Рисунок 5 х1
/>
/> - - 1
/> 1 1 -
/>
/>
/>
Рисунок 6 х1
/>
/> 1 1
/> 1 1
/>
/>
/> б) х1
/>
/> 1
/> 1 1
/>
/>
/>
Функция задана диаграммойВейча, представленной рис. 5.а. Доопределение функции на неопределенных наборахединицами (рис. 5.б) или нулями (рис. 6.а) приводит к разным минимальным ДНФ. Однакоболее простая минимальная ДНФ получается, если произвести доопределение так, какэто сделано на диаграмме Вейча (рис. 6.б). Алгоритм поиска минимальной ДНФ частичноопределенной функции f можно представитьследующим образом.
1. Найти любым известным способомсокращенную ДНФ функции, получающейся доопределением единицами исходной функцииf на всех неопределенных наборах.
2. Выбрать минимальную ДНФпо импликантной матрице, где в столбцах выписаны лишь те конституенты единицы функцииf, которые соответствуют полностью определеннымединичным наборам.
Аналогичный алгоритм (с доопределениемнулевыми наборами) может быть предложен для поиска КНФ. При этом доопределение таблицыистинности функции f может быть произведено по-разному дляКНФ и ДНФ.
Заметим, что для решения рассматриваемойзадачи практически достаточно тех навыков, которые были получены при минимизацииполностью определенных булевых функций непосредственно по диаграмме Вейча. В случаях,когда минимальных форм несколько, приводится одна из них.
11.Mинимизация систем булевых функций
На практике очень часто приходитсяреализовывать совокупности булевых функций. Если произвести минимизацию булевыхфункций, входящих в систему, независимо друг от друга, то общая схема будет состоятьиз изолированных подсхем. Ее можно иногда упростить за счет объединения участковподсхем, реализующих одинаковые члены, входящие в несколько булевых функций системы.
Задача минимизации систембулевых функций хорошо исследована в классе функционально полных систем: «дизъюнкция»,«конъюнкция», «отрицание». Рассмотрим один из наиболее распространенных методовминимизации.
Определение. Система дизъюнктивныхнормальных форм булевых функций называется минимальной, если ее полное множествоэлементарных конъюнкций содержит минимальное количество букв, а каждая дизъюнктивнаянормальная форма булевой функции системы включает минимальное число элементарныхконъюнкций наименьшего ранга. При этом дизъюнктивная нормальная форма представлениябулевой функции в минимальной системе в общем случае не совпадает с ее минимальнойдизъюнктивной нормальной формой. Минимизация систем полностью определенных булевыхфункций может производиться по алгоритму, аналогичному алгоритму метода Квайна снебольшими отличиями. Алгоритм минимизации следующий.
1. Построить полное множествоА элементарных конъюнкций минимизируемой системы функций, считая, что вначале каждаяиз функций системы представлена в СДНФ. Каждой конституенте единицы множества Априсвоить признак, содержащий номера функций системы, в которые входит рассматриваемаяконституента.
2. Произвести минимизациюСДНФ функции L, конституентами единицы которой являютсявсе элементы множества A. Привыполнении склеивания двух конституент единицы каждой вновь образуемой элементарнойконъюнкции присвоить признак, состоящий из номеров функций, общих для двух склеиваемыхконституент единицы. Последнее справедливо и для двух склеиваемых элементарных конъюнкцийс признаками. Если признаки склеиваемых конституент единицы не содержат общих номеров,то склеивание не производится. Поглощение производится только для элементарных конъюнкцийс одинаковыми признаками. Полученные в результате склеивания и поглощения конъюнкцииназываются простыми импликантами системы функций.
3. Построить импликантнуюматрицу функции L, аналогичную матрицеКвайна с той разницей, что для каждой конституенты единицы выделяется столько столбцов,сколько различных номеров функций содержит ее признак. Покрытие матрицы импликантамипроизводится аналогично методу Квайна.
Наиболее интересна задачапоиска абсолютно минимальной формы — формы, содержащей минимальное число операцийзаданной функционально полной системы. В общем виде эта задача не решена. Болеетого, известно, что абсолютно минимальная форма не всегда может быть получена изминимальной ДНФ. В то же время отыскание формы, близкой к абсолютно минимальной,—реальная и практически достижимая задача.
Здесь уместно сказать о типахи классах булевых функций в определении Шеннона. Выше уже упоминалось о взаимнооднозначном соответствии между схемами и формами представления булевых функций.В то же время, очевидно, что одна и та же схема может реализовать несколько различныхбулевых функций, если какие-то входные переменные поменять местами. В этом случаефункции принадлежат к одному классу. Если же переменные переставлять, допуская ихотрицания, то функции принадлежат к одному типу. Если найти абсолютно минимальнуюформу представления хотя бы одной функции каждого класса и построить соответствующиетаблицы, то задачу синтеза переключательных схем можно было бы свести к поиску нужногокласса в таблице. Такие таблицы для функций 4-х переменных были составлены (приреализации функций контактными схемами), практического распространения этот подходне получил. Одной из причин является тот факт, что число классов очень быстро растетс ростом n.
Выводы
Известна более простая задача— задача факторизации, заключающаяся в упрощении дизъюнктивно-конъюнктивных форм,допуская отрицания лишь над переменными. Часто она называется задачей скобочнойминимизации, и в настоящее время известно достаточно много методов такого упрощения.В общем виде задача факторизации не решена, но для булевого базиса, в ряде случаев,используя операцию вынесения за скобки общих членов, можно получить скобочную форму,значительно более простую, чем минимальная ДНФ булевой функции.
Литература
1. Самофалов К.Г., Романкевич А.М., идр. Прикладная теория цифровых автоматов. — Киев. “Вища школа” 1987.
2. Соловьев Г.Н. Арифметические устройстваЭВМ. — М. “Энергия”. 1978.
3. Савельев А.Я. Прикладная теория цифровыхавтоматов — М. “Высшая школа”. 1987.
4. Каган Б.М. Электронные вычислительныемашины и системы. — М. Энергоатомиздат. 1985.
5. Лысиков Б.Г. Арифметические и логическиеосновы цифровых автоматов. — Минск. “Вышэйшая школа”. 1980.