Цифровые интегральные микросхемы Микроэлектроника - (стр. 3 из 19)

В алгебре логики используется целый ряд теорем.

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

1. A Ú 0 = A4. A Ú Ā = 17. A · A = A

2. A Ú 1 = 15. A · 0 = 08. A · Ā = 0

3. AÚA = A6. A · 1 = 19.

Теоремы для двух и более переменных:

10. а) A Ú B = B Ú A, б) AB = BA

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

11. а) A Ú B Ú C = A Ú (B Ú C) = (A Ú B) Ú C,

б) ABC = A(BC) = (AB)C – сочетательный закон.

12. а) A (B Ú C) = AB Ú AC, б) A Ú BC = (A Ú B)(A Ú C) –

распределительный закон.

Данная теорема и все последующие вытекают из принципа двойственности. Применим его к выражению 12, а:

– левая часть,

– правая часть.

Введя новые обозначения:

, получим обозначения: , а это и есть теорема 12, б.

13. а) A Ú AB = A, б) A(A Ú B) = A

– закон поглощения (A поглощает B).

Доказательство 13, а:

AÚAB = A(1 ÚB) = A · 1 = A, (используя теоремы 2, 6).

Теорема 13, б следует из принципа двойственности.

14. а)

, б) .

Доказательство 14.а:

, (используя теоремы 8 и 1).

Теорема 14, б следует из принципа двойственности.

15. а) AB Ú ĀB = B, б) (A Ú B)(Ā Ú B) = B, закон склеивания (склеивание по A).

Доказательство 15, а:

AB Ú ĀB = B(A Ú Ā) = B · 1 = B, (используя теоремы 4 и 6).

Теорема 15, б следует из принципа двойственности.

Логические (булевы) функции

Булева функция (F) является результатом выполнения логических операций над двоичными переменными – аргументами (A, B, C, …) и полностью зависит от их значений.

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

Каждая комбинация аргументов называется набором, при N аргументах существует 2^N наборов.

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

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

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

Полностью определенная функция F₁ трех аргументов A, B, C принимает значение 1, если два любых аргумента (или все три) равны 1. В других случаях функция равна нулю. Количество наборов равно 2³ = 8.

Недоопределенная функция F₂ трех аргументов A, B, C принимает значение 1, если два любых аргумента равны 1, и равна нулю в остальных случаях, кроме случаев однозначности всех трех аргументов.

Если пронумеровать наборы от 0 до 2³ – 1, эти словесно заданные функции можно представить в виде таблицы истинности (табл. 1).

Таблица 1

Номера наборов	A	B	C	F1	F2	F3	F4
0	0	0	0	0	–	0	0
1	0	0	1	0	0	0	1
2	0	1	0	0	0	0	1
3	0	1	1	1	1	0	1
4	1	0	0	0	0	0	1
5	1	0	1	1	1	0	1
6	1	1	0	1	1	0	1
7	1	1	1	1	–	1	1

Функция F ₂ не определена на 0 и 7 наборах, где все три аргумента однозначны, поэтому в таблице 1 против этих наборов проставлены прочерки.

Отдельный интерес представляют функции F₃ и F₄ .

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

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

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

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

Минтерм – конъюнкция всех переменных в наборе, которые берутся в прямом виде, если их значение равно единице, либо в инверсном виде, если их значение в наборе равно нулю.

Функция F₁ в Сов ДНФ будет иметь вид:

.

Совершенной конъюнктивной, нормальной формой (Сов КНФ) функции называют конъюнкцию конституент нуля – макстермов, взятых на тех наборах, на которых нулю равна сама функция.

Макстерм – дизъюнкция всех переменных в наборе, которые берутся в прямом виде, если их значение равно нулю, либо в инверсном виде, если их значение в наборе равно единице.

Функция F₁ в Сов КНФ примет вид:

.

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

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

Аналитические методы минимизации

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

Представление булевой функции в Сов ДНФ в большинстве случаев не является минимальным.

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

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

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

Используя, например, неполное склеивание последней коституенты в Сов ДНФ функции F₁ последовательно с остальными, приходим к следующему выражению:

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

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

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

Найдем для примера тупиковую форму Сокр ДНФ

.

Испытаем член AC. AC = 1, если A = 1 и C = 1. Подставим в оставшееся выражение

A = 1 и C = 1, получим

.

При B = 0 F(A, B, C) = 1·1 Ú 0·0 = 1, но при

F(A, B, C) = 0·1 Ú 0·0 = 0. Следовательно, член ACне лишний.

Испытаем член BC, равный 1 при B = 0, C = 1. При этом

.

Последнее выражение равно 1 как при A = 1, так и при A = 0. Поэтому член

– лишний.

Испытание члена

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

.

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

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

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

При заполнении карты Карно в ее клетки проставляют значения функции для соответствующих наборов, которые являются координатами клеток. Например, для функции двух переменных А и В (рис. 5) карта Карно имеет вид