Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Лекции по проектированию цифровых устройств - файл 1_Основы алгебры логики.doc


Лекции по проектированию цифровых устройств
скачать (813.3 kb.)

Доступные файлы (11):

1_Основы алгебры логики.doc188kb.08.07.2004 05:33скачать
2а_минимизация.doc519kb.08.07.2004 06:16скачать
2_Проектиров цифр устр.doc174kb.08.07.2004 05:41скачать
3a_применение мультиплексоров.doc287kb.01.12.2001 00:22скачать
3b_Cумматоры.doc176kb.08.07.2004 05:53скачать
3c_интегральные сумматоры.doc202kb.08.07.2004 05:59скачать
3_Типовые комбинационные устройства.doc242kb.08.07.2004 06:25скачать
4_Интегральные триггеры.doc388kb.08.07.2004 06:04скачать
5_задержки в цифровых цепях.doc100kb.01.09.2004 20:00скачать
6_Проектир последоват схем.doc276kb.14.01.2007 17:22скачать
ПЦУ_программа_2002.doc111kb.01.09.2004 20:07скачать

содержание
Загрузка...

1_Основы алгебры логики.doc

Реклама MarketGid:
Загрузка...




1.ОСНОВЫ АЛГЕБРЫ ЛОГИКИ
1.1. Понятие о логических функциях
Отличительной особенностью логических функций является то, что они принимают значения в конечных множествах. Иначе говоря, область значений логической функции всегда представляет собой конечную совокупность чисел, символов, понятий, свойств и, вообще, любых объектов.

Если область значений функции содержит k различных элементов, то она называется k-значной функцией. Перечень символов, соответствующих области значений функции, называется алфавитом, а сами символы - буквами этого алфавита: N={a1,a2,...ak}.

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


y= f(x1,x2,..xn) (1.1)


представляет собой отображение множества наборов (n- мерных векторов) вида (x1,x2,..xn), являющихся областью ее определения, на множество ее значений N={a1,a2,..ak}, при условии однозначности этого отображения:
f: (x1,x2,..xn)N (1.2)
Логическую функцию можно также рассматривать как операцию, заданную законом композиции X1*X2*..*XnN, где X1,X2,..Xn - множества, на которых определены аргументы.
--------------------------------------------------------------------------------

Бинарное отношение ставит в соответствие паре объектов (a,b) третий объект с. При этом a,b операнды, с - результат операции или композиция объектов a и b. Если a принадлежит А, b принадлежит B, а с принадлежит С, то А*В C - закон композиции.

--------------------------------------------------------------------------------
Логическая функция называется однородной, если она принимает значения из того же множества, что и все ее аргументы, т.е. X1=X2=..=Xn.

Однородная логическая функция рассматривается как закон композиции NnN и определяет некоторую n-местную операцию на конечном множестве N.

Областью определения однородной функции y=f(x1, x2,..xn) служит множество наборов (x1, x2,..xn), называемых словами, где каждый из аргументов xi замещается буквами k-ичного алфавита {0,1,2,..k-1}. Очевидно, число различных слов длины n в k-ичном алфавите равно kn. Т.к. каждому такому слову имеется возможность сопоставить одно из k значений множества N, то общее количество однородных логических функций от n переменных выражается числом k^k^n.
^ 1.2.Булевы функции
Однородные логические функции, определенные на множестве N={0,1} называются двухзначными или булевыми по имени английского математика Дж. Буля (1815-1864). Областью определения булевых функций от n переменных служит множество двоичных векторов длиной n. Число различных булевых функций быстро возрастает с ростом n.

Таблица 1. Зависимость числа булевых функций от числа аргументов


^ Число аргументов

Число вх. наборов

Число БФ

n

2^n

2^2^n

1

2

4

2

4

16

3

8

256

4

16

65536

5

32

>4  109



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

^

Булевы функции одной переменной




Табл.2. БФ одной переменной





X

0 1

Наименование функции

Y0

0 0

const 0

Y1

0 1

x

Y2

1 0

/x

Y3

1 1

const 1


Лишь одна функция этой таблицы нетривиальна - y=/x . Эта функция называется "инверсией" или "отрицанием".

^

Булевы функции двух переменных

Табл.3. Булевы функции двух переменных





X1

X2

0 0 1 1

0 1 0 1

Наименование функции

Y0

0 0 0 0

const 0

Y1

0 0 0 1

конъюнкция x1&x2, x1|x2, x1x2, "И"

Y2

0 0 1 0

запрет по х2, х1*/х2

Y3

0 0 1 1

переменная х1

Y4

0 1 0 0

запрет по х1, 12

Y5

0 1 0 1

переменная х2

Y6

0 1 1 0

сумма по mod2

Y7

0 1 1 1

Дизъюнкция х1 V х2, x1+x2

Y8

1 0 0 0

стрелка Пирса x1x2

Y9

1 0 0 1

равнозначность x1x2

Y10

1 0 1 0

инверсия х2, /х2

Y11

1 0 1 1

импликация х2х1

Y12

1 1 0 0

инверсия х11

Y13

1 1 0 1

импликация х1х2

Y14

1 1 1 0

штрих Шеффера х1/х2

Y15

1 1 1 1

const 1



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

Из таблицы видно, что между БФ двух переменных имеет место соотношение:
yi=/y15-i, (i=0,1,..15) (1.3)
На основании этого можно записать:
0=/1, 1=/0 (0-15);

x=//x (3-12, 5-10);

x1/x2=/(x1x2) (1-14);

x1x2=/(x1+x2) (7-8); (1.4)

x1x2=/(x1~x2) (6-9);

x1/x2=/(x1x2) (2-13);

/x1x2=/(x2x1) (4-11);
Из 1.3 следует, что любая функция двух переменных выражается в аналитической форме через отрицание /x и любую из каждой пары {y0,y15}, {y1,y14}, {y2,y13}, {y6,y9}, {y7,y8}. Например, можно выбрать такой набор БФ: y0, /x, y1(&), y7(+), y9(~), y13(). Можно показать, что такой набор является избыточным, т.к. y9 и y13 можно выразить через остальные функции набора:
y9 = x1~x2 = x1x2+/x1/x2, y13=/x1+x2 (1.5)
Набор из оставшихся 4-х функций широко применяется на практике, но и он может быть сокращен за счет удаления y1 и y7.

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

Два выражения, дающие одинаковые значения на одних и тех же наборах переменных - называются тождественными.

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

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


а) б) в)

Рис.1.1. Диаграммы Эйлера-Венна для логических

функций НЕ (а), И (в), ИЛИ (б).
Ранее было показано, что одни БФ могут быть выражены через другие. Последние именуют базисными функциями или базисом. Исследование логических функций двух переменных показало, что возможно выделение некоторого подмножества Y' множества Y={y0,y1,..y15}, с помощью которого можно выразить любую БФ от произвольного числа аргументов. Такие подмножества называют функционально полным базисом. Построить функции большего числа переменных, используя только функции двух переменных, можно с помощью операций композиции, под которыми понимается подстановка одних функций вместо переменных в другие функции. Такая подстановка возможна в силу того, что области значений функций и переменных совпадают (0 и 1).

Функции образующие полный базис должны обладать определенными свойствами. Прежде, чем сформулировать эти свойства, рассмотрим классы логических функций.
^ Класс линейных функций
По теореме Жегалкина - любая БФ(n) может быть представлена полиномом степени не выше n. Если БФ представляется полиномом первой степени:

f(x1,x2,..xn)=k0  k1x1  k2x2 .. knxn, (1.6)

где ki принадлежит множеству {0,1}, то такая функция называется линейной. Количество линейных функций n переменных равно 2n+1. Для n=2 количество линейных функций равно 8.

Kл={y0,y3,y5,y6,y9,y10,y12,y15}.


1) y0=0

2) y3=x1

3) y5=x2

4) y6=x1  x2

5) y9=1  x1  x2

6) y10=1  x2

7) y12=1  x1

8) y15=1
^

Класс функций, сохраняющих "0"



Это функции равные 0 на нулевом наборе переменных.

K0={y0,y1,y2,y3,y4,y5,y6,y7}.

Класс функций сохраняющих "1"



Это функции равные 1 на единичном наборе переменных.

K1={y1,y3,y5,y7,y9,y11,y13,y15}.

^

Класс монотонных функций



Это функции неубывающие при любом возрастании набора аргументов 00011011.

Kм={y0,y1,y3,y7,y15}.

Класс самодвойственных функций



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

f(x1,x2,..xn)=/f(/x1,/x2,../xn).

Kс={y3,y5,y10,y12}.


Табл.4. Сводная таблица классов

функций двух переменных




Кл

К0

К1

Км

Кс

Y0

1

1




1




Y1




1

1

1




Y2




1










Y3

1

1

1

1

1

Y4




1










Y5

1

1

1

1

1

Y6

1

1










Y7




1

1

1




Y8
















Y9

1




1







Y10

1










1

Y11







1







Y12

1










1

Y13







1







Y14
















Y15

1




1

1





^

Теорема Поста-Яблонского




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


  • не сохраняющей 0;

  • не сохраняющей 1;

  • не являющейся линейной;

  • не являющейся монотонной;

  • не являющейся самодвойственной.


Существует несколько полных базисов:
B1={y1,y7,y10(y12)} И ИЛИ НЕ,

B2={y1,y10} И НЕ,

B3={y7,y10} ИЛИ НЕ,

B4={y8} функция Пирса,

B5={y14} функция Шеффера.

Функции y8 и y14 не принадлежат ни к одному из рассмотренных классов и, следовательно, в единственном числе составляют полный базис. Алгебра построенная на базисе В1 называется булевой по имени английского математика первого исследовавшего логические функции. Существуют и другие алгебры, например, Жегалкина - построенная на базисе {y1,y6,y15} (И ~ 1).


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


//x=x

Ассоциативный закон:

xvyvz=(xvy)vz

x&y&z=(x&y)&z

x&0=0

xv0=x

Коммутативный закон:

xvy=yvx

x&y=y&x

x&1=x

xv1=1

Дистрибутивный закон:

(xvy) & z=x&z v y&z

x&y v z=(xvz)&(yvz)

x&x=x

xvx=x

Законы поглощения:

xvx&y=x

(xvy)&x=x

x&/x=0

xv/x=1

Законы дуальности

(теоремы д-Моргана):

___ _ _

xvy = x&y

___ _ _

x&y=xvy


Клод Шенон предложил обобщение теорем дуальности, позволяющее отыскивать инверсию любой функции f(X), где X=(xn,..x1):

________ _

f(X/v,&)=f(X/&,v). (1.7)
В соответствии с 1.7 инверсию любой функции можно получить взаимной заменой переменных и их инверсий и операций дизъюнкции и конъюнкции.
^ 1.5. Способы задания булевых функций
Табличный
Аргументы обычно упорядочивают в порядке убывания величины индексов. Таблица может дополняться колонкой - порядковым номером строки. Удобно соблюдать соответствие между порядковым номером и двоичным кодом соответствующим данному набору значений аргументов. Подобного рода таблицы называют таблицами истинности. Существуют и другие формы таблиц, которые будут рассмотрены в дальнейшем.


Табл.5

N

x2 x1 x0

y

0

0 0 0

0

1

0 0 1

1

2

0 1 0

1

3

0 1 1

0

4

1 0 0

1

5

1 0 1

0

6

1 1 0

1

7

1 1 1

0


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



^ В виде логической схемы
Логическая функция задается в виде условного графического изображения элемента реализующего эту функцию.


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

^

Минтермы и макстермы



Минтермом или конституентой единицы называется функция n переменных:
~ ~ ~

mi (xn,xn-1 ..x1)=x1&x2&..&xn, (1.8)

~ __

где xp - т.н. первичный терм, принимающий значение xp или xp, а i - номер терма соответствующий двоичному коду, построенному на значениях первичных термов входящих в выражение 1.7. xp ставится в соответствие 1, а /xp - 0.

Видно, что имеется 2n различных минтермов для n переменных. Минтермы обладают следующими свойствами:


  • Минтерм принимает единичное значение лишь на наборе соответствующем его номеру;

  • Минтермы взаимно ортогональны, т.е. произведение любых минтермов с разными номерами равно 0;

  • Сумма всех минтермов n переменных равна 1.


Макстермом или конституентой 0 называют функцию n переменных:

~ ~ ~

Mi(xn,xn-1,..x1)=xn v xn-1 v..v x1. (1.9)
Свойства макстермов двойственны по отношению к свойствам минтермов. Названия связаны с тем, что макстерм соответствует максимальному из значений входящих в него переменных, а минтерм - минимальному.

^

Теорема разложения



Одна из важнейших теорем в алгебре логики это теорема разложения. Согласно ей любую функцию f можно разложить по переменной хp в форме

_

f(xn,..xp,..x1)=xp&f(xn,..0,..x1)vxp&f(xn,.1,..x1). (1.10)
Эта теорема легко доказывается методом перебора. Легко получить альтернативный вариант теоремы разложения

_

f(xn,..xp,..x1)=[xpvf(xn,..1,..x1)][xpvf(xn,..0,..x1)]. (1.11)
Совершенная дизъюнктивная нормальная форма (СДНФ)
Применяя последовательно теорему разложения 1.10 к любому логическому выражению, его можно свести к виду
f(X)=Vf(i)&mi, (1.12)

i

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

Для примера проведем разложение функции двух переменных f(x1,x0).

_

f(x1,x0)=x1&f(0,x0)vx1&f(1,x0)=

_ _ _ _

=x1&x0&f(0,0)v x1&x0&f(0,1) v x1&x0&f(1,0) v x1&x0&f(1,1).
^ Совершенная конъюнктивная нормальная форма (СКНФ)
В полном соответствии с принципом двойственности любую функцию можно представить в совершенной конъюнктивной нормальной форме (СКНФ) как логическое произведение макстермов на которых значение функции равно 0:
f(X)=&(f(i)vMi). (1.13)

i
^

Переход от табличной формы записи к аналитической



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

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

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

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


N

x2

x1

x0

y

0

0

0

0

1

1

0

0

1

1

2

0

1

0

0

3

0

1

1

1

4

1

0

0

0

5

1

0

1

1

6

1

1

0

0

7

1

1

1

1


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

_ _ _ _ _ __

f(X) = x2x1x0 v x2x1x0 v x2x1x0 v

_

x2x1x0 v x2x1x0
2.Запишем функцию в СКНФ. Для этого выпишем минтермы для наборов, где функция принимает 0 значения.

__ __ __ __

f(X) = (x2vx1vx0)&(x2vx1vx0)&(x2vx1vx0)

В заключение заметим, что обратный перевод из аналитической формы записи в табличную форму тривиален и состоит в подстановке значений аргументов и вычислении значений функции.
^ Представление логических функций в виде временных диаграмм
При проектировании цифровых систем интерфейсным методом широко используют метод временных диаграмм. При этом проектировщики не имеют в своем распоряжении строгих математических методов проектирования. Такое положение вещей не должно обескураживать приверженцев строгих методов, т.к. подобное состояние дел наблюдается в химии (таблица Менделеева), а сейчас и в физике (таблицы Феймана и Голдстоуна). Вместо того чтобы детально рассчитывать схемы, опираясь на интегро-дифференциальные уравнения электротехники, используют топологически преобразованные интегральные схемы (ИС) соединенные друг с другом. При этом состояния интересующие проектировщика описываются с помощью булевой алгебры и двоичной арифметики. Временные соотношения заданные временными диаграммами сводятся, обычно, к системам простых неравенств [2].

Временные диаграммы представляют собой совмещенные диаграммы, на которых уровни изображаются условно и соответствуют логическим 0 или 1. На диаграммах отображаются все характерные временные соотношения, такие как: длительности фронтов и спадов сигналов, взаимное расположение сигналов ни временной оси. Семейства временных диаграмм обычно задаются для различных режимов работы устройств и лишь для устройств со сложной логикой работы. Многочисленные примеры временных диаграмм можно найти, например, в [3].


^ Геометрическое представление БФ
БФ можно представлять в виде гиперкубов. При этом каждой вершине гиперкуба ставится в соответствие минтерм. Для функции двух переменных таким представлением является квадрат.



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



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




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


Возможно построение карт Карно и для большего числа переменных. Ниже приведена карта для 8 переменных.


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


 Далее по тексту "/"будет применяться для обозначения инверсии.



Скачать файл (813.3 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации