СПОСОБЫ ПРЕДСТАВЛЕНИЯ (ЗАДАНИЯ) ФУНКЦИЙ

Date: 2015-10-07; view: 1309.

Оглавление

1. Основы теории булевой алгебры 4

1.1. Понятие логической переменной и логической функции 4

1.2. Основные теоремы и законы булевой алгебры 6

1.2.1. Теоремы для одной переменной 6

1.2.2. Теоремы и законы для двух и более переменных 6

1.3. Способы представления (задания) функций 7

1.3.1. Представление функций на словах 8

1.3.2. Табличный способ представления логических функций 8

1.3.3. Алгебраический (аналитический) способ представления логических функций 8

1.3.4. Числовой способ представления логической функции 10

1.4. Минимизация булевых функций 11

1.4.1. Метод минимизации с помощью алгебраических преобразований (метод Квайна) 12

1.4.2. Минимизация Булевых функций с использованием карт Карно (диаграмм Вейтча) 17

1.5 Построение цифровых устройств с помощью функций алгебры логики 20

1. Пример проектирования цифрового устройства посредством системы Булевых функций _____________________________________________ 21
2. Литература 39

1.ОСНОВЫ ТЕОРИИ БУЛЕВОЙ АЛГЕБРЫ

В школьном курсе математику функцией y=f(x) называется правило, по которому каждому элементу x из множества X ставится в соответствие один элемент y из множества Y.

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

Значение y, соответствующее заданному значению x, называют значением функции. Это соответствие записывается в виде y=f(x). Символом f обозначается функция, т.е. правило (закон) взаимоотношений между переменными x и y. Другими словами функциональная зависимость между ними. Записью f(x) - обозначается значение функции, соответствующее заданному значению x.

Переменную x называют при этом независимой переменной или аргументом, а переменную y - зависимой переменной.

Важно помнить, что в обычной (школьной) алгебре аргумент x и функция f(x) могут принимать любые значения, т.е. могут быть любыми числами: и -17.9, и 1, и 1.5, и 0, и 149.7, и т.д.

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

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

1.1.ПОНЯТИЕ ЛОГИЧЕСКОЙ ПЕРЕМЕННОЙ И ЛОГИЧЕСКОЙ ФУНКЦИИ

Логической величиной (переменной) называется величина, которая может принимать только два значения или 0 или 1.

Логические величины (переменные) могут быть зависимыми и независимыми.

Логические величины (переменные), которые не зависят от других логических величин и не находятся с ними в каком-либо взаимоотношении, называются независимыми логическими величинами (переменными) или логическими аргументами.

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

Логические функции, также как и логические аргументы, могут принимать два значения: 0 или 1 ("НЕТ" или "ДА"; "ЛОЖЬ" или "ИСТИНА).

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

Из теории Булевой алгебры известно, что количество различных наборов (комбинаций), которые можно породить (организовать)из значений аргументов, каждый из которых может принимать лишь 0 или 1, равно m=2ⁿ , где n - это количество аргументов.

Количество функций, которое может быть порождено на таком количестве наборов из значений аргументов, равно k=2^m.

Задать (определить) одну из булевых функций - это значит задать (определить) значение этой функции и определить правило (закон) взаимоотношений для каждого из возможных наборов (комбинаций) значений аргументов.

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

Подтвердим изложенные выше положения примерами.

Пример 1: Пусть логические аргументы отсутствуют, т.е. n=0.

Тогда количество наборов, которые можно организовать из значений аргументов равно: m=2ⁿ=2⁰=1 – это предельный случай. Другими словами, факт отсутствия аргументов вырождается в факт отсутствия их значений, а следовательно и наборов их значений. И этот факт закодирован "1".

Количество функций, которые при этом существуют (определены) равно: k=2^m =2.

Одна из них носит название КОНСТАНТА НУЛЯ, т.к. значение ее

всегда равно нулю. Эта функция обозначается f0(...)=0.

Другая функция носит название КОНСТАНТА ЕДИНИЦЫ, т.к. значение ее всегда равно 1. Эта функция обозначается f1(...)=1.

Пример 2: Пусть n=1, т.е. имеем один аргумент.

Тогда: m=2ⁿ=2¹=2, т.е. при наличии одного аргумента можно организовать 2 набора из его значений. k=2^m =2² =4, т.е. при наличии одного аргумента можно организовать четыре функции.

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

Функция	Аргумент Х (n=1)	Название и обозначение функции
Наборы значений Х
f0(Х)			Константа 0, (f0(Х)=0)
f1(Х)			Переменная Х, (f1(Х)=Х)
f2(Х)			Инверсия Х, (f2(Х)= ), (отрицание Х, функция НЕ)
f3(Х)			Константа 1, (f3(Х)=1)

Пример 3: Пусть n=2, т.е. имеем два аргумента.

Тогда: m=2ⁿ=2²=4 - из двух аргументов можно организовать 4 набора (комбинации) из его значений. k=2^m=16. - при наличии двух аргументов может быть организовано 16 функций.

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

Функция двух аргументов	Аргументы	Наборы значений	Наименование и обозначение функции
Х1
Х2
f0(X1,X2)						Константа 0, f0(X1,X2)=0
f1(X1,X2) ………… …………					Конъюнкция (логическое умножение, логическое И) f1(X1,X2)
f3(X1,X2) …………					Переменная Х1, f3(X1,X2)=Х1
f6(X1,X2) …………					Сумма по модулю 2, f6(X1,X2)=Х1+Х2
f7(X1,X2) ………… …………					Дизъюнкция (логическое сложение, логическое ИЛИ) f7(X1,X2)=Х1+Х2
f10(X1,X2) …………					Отрицание (функция НЕ) , f10(X1,X2)=Х2
f15(X1,X2)					Константа 1, f15(X1,X2)

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

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

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

 

1.2. ОСНОВНЫЕ ТЕОРЕМЫ И ЗАКОНЫ БУЛЕВОЙ АЛГЕБРЫ

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

Базовыми операциями являются операции логического отрицание НЕ, логическое умножения И, логического сложения ИЛИ. Часто эти операции называют соответственно, так же операциями инверсии, конъюнкции и дизъюнкции. В булевой алгебре операции НЕ (отрицания), И (конъюнкция), ИЛИ (дизъюнкция) принято обозначать следующими знаками:

ü –(черточка над переменной) - НЕ;

ü * или ^ - И;

ü + или v - ИЛИ;

ü = (двойная черточка над переменной) - операция НЕ выполненная дважды (двойное отрицание).

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

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

 

1.2.1. Теоремы для одной переменной.

Эти теоремы охватывают все возможные операции над одной переменной X, а также константами 0 и 1.

1. X+0=X
2. X+1=1
3. X+X=X


4. X+ =1
5. X*0=0
6. X*1=X


7. X*X=X
8. X* =0
9. =X

 

1.2.2. Теоремы и законы для двух и более переменных.

1. Переместительный закон (закон коммутативности): Закон справедлив для любого числа переменных. Он гласит: результат выполнения операции ИЛИ и И не зависит от порядка написания переменных.

Для сложения:

X+Y=Y+X

Для умножения:

X*Y=Y*X

1. Сочетательный закон (закон ассоциативности). Закон справедлив для любого числа переменных. Он гласит: результат вычислений не зависит от порядка объединения переменных в группы при выполнении операций И или ИЛИ.

Для сложения:

X+Y+Z=X+(Y+Z)=(X+Y)+Z

Для умножения:

X*Y*Z=X*(Y*Z)=(X*Y)*Z

1. Распределительный закон (закон дистрибутивности):

Сложение по отношению к умножению: X+Y*Z=(X+Y)*(X+Z)

(аналогий в обычной алгебре нет)

Умножение по отношению к сложению:

X*(Y+Z)=Х*Y+Х*Z

(можно вносить/выносить общий член в/за скобки)

1. Закон поглощения

Для сложения:

X+Y*X=X

Х*(1+Y)/1=X*1=X

Для умножения:

X*(X+Y)=X X*X/X+X*Y=X+X*Y=X*(1+Y)=X

Случай 1:

(X+ )*Y=X*Y

X*Y+ *Y/0=X*Y+0=X*Y

X* +Y=X+Y

X* +Y*Y=X+Y

Случай 2:

(X+Y)* = *X

X* +Y* /0= *X

+X*Y= +X

1. Закон склеивания

Для сложения:

X*Y+ *Y=Y Y*(X+ )/1=Y*1=Y

Для умножения:

(X+Y)*( +Y)=Y

X* /0+(X*Y+Y* )/(Y*[X* ]/1)+Y*Y =Y+Y=Y

1. Правило Де-Моргана

Правило Де-Моргана вытекает из принципа двойственности. В соответствии с этим принципом, при замене в логической функции всех аргументов их отрицаниями, и операции умножения/сложения операциями сложения/умножения получается отрицание значения функции. Так, например:

f(X,Y,Z)=X*Y*Z

Для случая двух аргументов правило Де-Моргана имеет такой вид:

Для сложения:

Для умножения:

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

Существует четыре основных способа представления булевой функции:

ü на словах;

ü табличный;

ü алгебраический (аналитический);

ü числовой.

1.3.1.Представление функций на словах.

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

Например, функция трех переменных (аргументов) принимает значение 1, если два любых аргумента или все три равны 1. Во всех других случаях функция равна 0. Этими предложениями функция полностью определена.

1.3.2.Табличный способ представления логических функций.

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

Так, для случая трех аргументов X1, X2, X3 таблица может иметь следующий вид:

Таблица 1.3.2.1.

Примечание: Напомним, что для функции содержащей три аргумента, можно составить 2³=8 наборов из значений аргументов и на этих наборах можно определить 2⁸=256 функций.

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

1.3.3.Алгебраический (аналитический) способ представления логических функций.

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

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

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

Каждое из слагаемых (логические произведения) в этой форме могут содержать от 1-го до N аргументов.

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

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

Одна из форм записи логической функции алгебраическим способом получила название конъюнктивно нормальной формы (КНФ).

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

Каждая логическая сумма в этой форме, может содержать в своем составе от 1-го до N аргументов.

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

Как правило, целесообразнее всего получать СДНФ или СКНФ функции из таблиц истинности.

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

Для каждого набора (терма), на котором функция равна 1 записывается элементарное произведение (конъюнкции) всех аргументов. Причем, если значение аргумента в этом терме имеет значение 0, то пишется отрицание этого аргумента. Затем, эти элементарные произведения объединяются знаками логического сложения (дизъюнкциями). Другими словами, производится логическое сложение элементарных произведений (конъюнкций). Так, например, для функции f0(X1,X2,X3) из таблицы III.3.2.1 СДНФ имеет такой вид:

Для функции f25(X1,X2,X3) из этой же таблицы СДНФ имеет такой вид:

Следует заметить, что значение для каждого входящего в состав СДНФ терма равно 1. Это значит, что значение функции, записанной в СДНФ, также будет равно 1, т.к. f(X1,X2,X3)=1+1+...+1=1

1 (смотри правила выполнения логической операции дизъюнкции).

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

Для перехода от таблицы истинности к СКНФ логической функции требуется выполнение следующей последовательности действий.

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

Так, например, для функции f0(X1,X2,X3) из таблицы СКНФ имеет такой вид:

Для функции f25(X1,X2,X3) из этой же таблицы совершенная конъюнктивная нормальная форма имеет такой вид:

Следует заметить, что значение функции для каждого входящего в состав СКНФ терма равно 0. Это означает, что значение функции записанной в СКНФ также будет равно 0, т.к. f(X1,X2,X3)=0*0*...*0=0 (смотри правило выполнения логической операции конъюнкции).

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

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

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

1.3.4.Числовой способ представления логической функции.

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

f0(X1,X2,X3)_СДНФ=S(3,5,6,7).

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

Чтобы показать связь числового способа записи функции с алгебраическим, представим цифры в скобках в двоичной системе счисления. Учитывая, что аргумент X1 соответствует старшему разряду, а аргумент Х3 младшему разряду, можно написать:

f0(X1,X2,X3) 4СДНФ 0=S(3,5,6,7)=0*1*1+1*0*1+1*1*0+1*1*1.

Приняв во внимание то обстоятельство, что 0 в двоичном числе означает отрицание аргумента, а 1 есть сам аргумент, можно написать:

,

что совпадает с записью приведенной в 1.3.3.

При числовом способе представления логической функции совершенная конъюнктивная нормальная форма (СКНФ) функции трех аргументов из таблицы имеет такой вид:

f(X1,X2,X3)_СКНФ=P(0,1,2,4).

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

Учитывая, что номера наборов можно представить в двоичной системе счисления, можно записать:

f0(X1,X2,X3) 4СКНФ 0=P(0,1,2,4)=(0+0+0)*(0+0+1)*(0+1+0)*(1+0+0).

Приняв во внимание то, что в СКНФ 1 в двоичном числе означает отрицание аргумента, а 0 есть сам аргумент, можно написать:

,

что совпадает с записью приведенной в 1.3.4.

1.4. МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ

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

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

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

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

Минимизация упрощение булевой функции - это представление заданной функции в такой форме, которая содержит наименее возможное число аргументов и наименее возможное число операций над ними.

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

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

Широкое применение для минимизации функций находят два метода:

1. Метод Квайна - в основу метода положены алгебраические преобразования.
2. Метод минимизации с использованием карт Карно (диаграмм Вейтча).

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

(метод Квайна).

В основу этого метода положено следующие:

1. Обычные алгебраические приемы:

ü группирование термов, имеющих общие аргументы;

ü вынесение общих аргументов за скобки;

ü замену переменных;

ü подстановку.

2. Преобразования вытекающие из законов алгебры Буля. Наиболее часто используемыми в процессе преобразований законами являются закон склеивания и поглощения.

Напомним, что закон склеивания позволяет осуществить следующие преобразование:

X*Y+ *Y=Y*(X+ )=Y*1=Y

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

Напомним, что закон поглощения позволяет осуществить следующее преобразование:

X+X*Y=X*(1+Y)=X*1=X.

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

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

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

Другими словами, отыскиваются пары подобных элементов (слагаемых).

Важно помнить, что в булевой алгебре справедливы следующие утверждения:

ü подобными считаются элементы (слагаемые), которые могут также отличатся наличием в одном из них инверсного аргумента;

ü одно и тоже слагаемое (элемент) может является членом многих пар.

После выноса за скобки общих аргументов, в скобках остается выражение вида (X+ ), значение которого согласно закону склеивания равно 1.

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

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

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

Пример 1. Пусть имеем СДНФ булевой функции:

, которую необходимо минимизировать.

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

Первый этап минимизации состоит в проведении процедуры склеивания слагаемых (термов) логической функции.

Аналогом процедуры склеивания в обычной алгебре является процедура сведения подобных членов в алгебраических выражениях.

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

Удобно процедуру склеивания выполнять в такой последовательности:

1. Все слагаемые (термы) входящие в состав СДНФ функции пронумеровать.

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

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

Значение функции не изменится, если в ее состав будут добавлены одинаковые дизъюнктивные члены, т.е. f(X)=X=X+X+...+X.

В данном примере можно организовать такие пары:

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

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

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

1. На основании закона склеивания:

произвести сокращение (упрощение) ДНФ функции и тем самым получить сокращенную дизъюнктивную нормальную форму функции (СОДНФ).

f(X1,X2,X3)_СОДНФ=X2*X3+X1*X3+X1*X2

6. Проанализировать СОДНФ функции на предмет того, нельзя ли над этой формой еще раз провести процедуру склеивания, т.е. повторить первый этап минимизации.

В рассматриваемом примере СОДНФ булевой функции содержит в своем составе три слагаемых, каждое из которых теперь уже состоит из двух аргументов. Кроме того, слагаемые не содержат в своем составе инверсий аргументов вида 1, 2 или 3. Следовательно, в этой СОДНФ функции подобных членов нет и, возможность произвести

очередное склеивание отсутствует.

Второй этап минимизации состоит в проведении процедуры поглощения. Суть процедуры поглощения сводится к тому, чтобы в очередной СОДНФ булевой функции, полученной после n-ной процедуры склеивания, уменьшить число слагаемых. Сократить число слагаемых в СОДНФ функции можно, если к какой-либо паре слагаемых удастся применить закон поглощения, т.е. удастся осуществить над парой слагаемых преобразование вида: X+X*Y=X*(1+Y)=X*1=X.

Это становится возможным, если какое-либо слагаемое СОДНФ содержит одинаковые аргументы и, следовательно, к этим слагаемым можно применить закон, который гласит, что: X*X=X. (Для нашего примера применение этого закона стало бы возможным если бы, например, 1-е слагаемое имело бы вид X2*X2.

Тогда можно было бы организовать пары слагаемых вида: X*X+X*Y и применить к ним закон поглощения, т.е. преобразовать какую-либо пару к виду: X*X+X*Y=X+X*Y=X*(1+Y)=X, что приводит к замене пары слагаемых одним членом.

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

Это означает, что данная функция дальнейшей минимизации не поддается и уже является минимизированной.

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

Поэтому в этом случае можно написать:

f(X1,X2,X3)_СОДНФ=f(X1,X2,X3)_МДНФ=X2*X3+X1*X3+X1*X2.

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

Другими словами, целью минимизации является: преобразование логической функции СОДНФ к логической функции МДНФ.

По логическим функциям МДНФ строятся вычислительные узлы (комбинационные схемы) ЭВМ на базе электронных схем НЕ, И, ИЛИ. Эти схемы выполняют, соответственно, логические операции НЕ (инверсия), И (логическое умножение), ИЛИ (конъюнкция).

На базе таких вычислительных узлов строится арифметические устройства ЭВМ, а также устройства управления ЭВМ.

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

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

Этап 1. Склеивание членов СДНФ.

1. Пронумеруем члены СДНФ.

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

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

1. Вынесем за скобки общие аргументы имеющиеся в слагаемых ДНФ.

1. Произведем упрощение логической функции и получим ее СОДНФ:

6. Анализируем СОДНФ функции на предмет выявления в ней подобных слагаемых (членов) и возможности повторного проведения процедуры склеивания.

Однако, в этой сокращенной форме булевой функции подобных членов нет.

Этап 2. Поглощение членов СОДНФ булевой функции.

1. Члены (слагаемые) этой формы также не содержат одинаковых аргументов. Следовательно, процедуру поглощения также провести не удастся.

2. Т.О., минимальная дизъюнктивная форма функции имеет вид:

Пример 3. Пусть задана СДНФ логической функции от трех аргументов

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

Этап 1. Склеивание членов СДНФ.

1. Пронумеруем члены СДНФ

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

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

1. Вынесем за скобки общие аргументы имеющиеся в слагаемых ДНФ.

1. Произведем упрощение логической функции, и получим ее СОДНФ:

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

Этап 1.1. Повторная процедура склеивания членов СОДНФ1.

1. Пронумеруем члены СОДНФ1.

1. Организуем пары по указанному выше принципу.

3. Составим из пар, по указанному выше принципу, дизъюнктивную нормальную форму логической функции.

1. Вынесем за скобки общие аргументы, имеющиеся в слагаемых СОДНФ1.

5. Учитывая то, что Х+Х=1, можно написать (получить) вторую сокращенную ДНФ функции, т.е. получить СОДНФ2.

f(X1,X2)_СОДНФ=X2+X1.

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

Этап 2. Поглощение членов СОДНФ2.

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

Т.О., СОДНФ2 логической функции и есть ее минимальная дизъюнктивная нормальная форма (МДНФ). Следовательно, МДНФ логической функции этого примера имеет вид:

f(X1,X2,X3)_МДНФ=X2+X1.

Пример 4. Пример проведения процедуры поглощения.

Пусть после проведения очередного этапа склеивания, мы получили СОДНФ логической функции вида:

f(X1,X2,X3)_СОДНФ=X1*X1+X2*X3+X1*X3.

Анализируя эту функцию видим, что некоторые ее слагаемые содержат одинаковые аргументы. В частности, здесь одинаковые аргументы содержит 1-е слагаемое. Проведя преобразования вида Х*Х=Х получим:

f(X1,X2,X3)_СОДНФ=Х1+X2*X3+X1*X3.

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

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

f(X1,X2,X3)_МДНФ=X1+X2*X3

1.4.2. Минимизация Булевых функций с использованием карт Карно

(диаграмм Вейтча).

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

Значительно облегчает этот процесс, при минимизации функций, использование карт Карно. Карта Карно позволяет формализовать и систематизировать этот процесс.

Карта Карно представляет собой прямоугольную таблицу состоящую из ячеек. Число ячеек в таблице равно числу наборов которые можно организовать и значений аргументов. Напомним, что при числе аргументов равном n, можно организовать 2 5n 0наборов из значений аргументов.

Так, при n=3, таких наборов будет 8, при n=4 - их будет 16.

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

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

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

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

Пример нумерации клеток для функций от трех аргументов показан на рисунке:

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

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

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

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

После выполнения процедуры нумерации (адресации) клеток таблицу Карно необходимо заполнить.

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

Методика заполнения таблицы Карно состоит в использовании одного из ниже приведенных способов:

Первый способ. Заполнение карты Карно по данным таблицы истинности:

ü в клетки таблицы Карно, адреса которых совпадают с наборами аргументов таблицы истинности, где значения функции равны единицам, записываются 1 (единицы);

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

Второй способ. Заполнение карты Карно по данным взятым из совершенной дизъюнктивной нормальной формы функции СДНФ:

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

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

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

В объединенной группе может быть две, четыре или восемь единиц.

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

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

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

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

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

Следует руководствоваться следующим свойством: каждая очерченная пара единиц дает одно слагаемое (один член) в СОДНФ функции.

Для определения аргументов из которых должно состоять слагаемое (член СОДНФ) можно воспользоваться следующим правилом:

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

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

Пример 1. Пусть задана логическая функция от трех переменных f(X1,X2,X3) в виде таблицы истинности.

Минимизируем эту функцию с использованием карт Карно.

Составим карту Карно. Так как минимизации подлежит функция от трех аргументов, то карта Карно должна содержать 2 53 0=8 клеток. Каждая клетка в карте Карно имеет адрес составленный из наборов символов аргументов.

Выберем систему адресации и заполним единицами карту Карно.

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

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

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

Оставшиеся клетки, как в первом так и во втором случае можно не заполнять.

Имея заполненную единицами карту Карно, можно приступить к минимизации булевой функции.

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

Выписав пары очерченных единиц, произведем над ними процедуру склеивания.

Заметим, что каждая очерченная пара дает сокращенную дизъюнктивную форму функции (СОДНФ) одно слагаемое (один член).

После выполнения процедуры склеивания получим СОДНФ логической функции, которая для данного примера имеет вид:

Анализируя полученную СОДНФ функции видим, что она не поддается дальнейшему упрощению, т.е. к ней уже нельзя применить закон склеивания и поглощения.

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

1.5.ПОСТРОЕНИЕ ЦИФРОВЫХ УСТРОЙСТВ С ПОМОЩЬЮ