В алгебре логики используется целый ряд теорем.
Теоремы для одной переменной:
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 аргументах существует 2N наборов.
Если, известны значения функции на всех наборах аргументов, она называется полностью определенной. Если же на некоторых наборах значение функции неизвестно, то она называется недоопределенной, а соответствующие наборы – запрещенными наборами. Значения функции на запрещенных наборах можно задать по своему усмотрению (доопределить функцию).
Логические функции могут иметь различные формы представления: словесное, табличное, алгебраическое, графическое.
Рассмотрим два примера словесного задания булевой функции.
Полностью определенная функция F1 трех аргументов A, B, C принимает значение 1, если два любых аргумента (или все три) равны 1. В других случаях функция равна нулю. Количество наборов равно 23 = 8.
Недоопределенная функция F2 трех аргументов A, B, C принимает значение 1, если два любых аргумента равны 1, и равна нулю в остальных случаях, кроме случаев однозначности всех трех аргументов.
Если пронумеровать наборы от 0 до 23 – 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 2 не определена на 0 и 7 наборах, где все три аргумента однозначны, поэтому в таблице 1 против этих наборов проставлены прочерки.
Отдельный интерес представляют функции F3 и F4 .
Конституентой единицы (F3) называют функцию n аргументов, которая принимает значение, равное единице, только на одном наборе аргументов. На всех остальных наборах она равна нулю.
Конституентой нуля (F4) называют функцию n аргументов, которая принимает значение, равное нулю, только на одном наборе аргументов.
От табличного задания булевой функции можно перейти к ее алгебраическому представлению, причем в двух формах: совершенной дизъюнктивной, нормальной форме и совершенной конъюнктивной, нормальной форме.
Совершенной дизъюнктивной, нормальной формой (Сов ДНФ) функции называют дизъюнкцию конституент единицы – минтермов, взятых на тех наборах, на которых единице равна сама функция.
Минтерм – конъюнкция всех переменных в наборе, которые берутся в прямом виде, если их значение равно единице, либо в инверсном виде, если их значение в наборе равно нулю.
Функция F1 в Сов ДНФ будет иметь вид:
Совершенной конъюнктивной, нормальной формой (Сов КНФ) функции называют конъюнкцию конституент нуля – макстермов, взятых на тех наборах, на которых нулю равна сама функция.
Макстерм – дизъюнкция всех переменных в наборе, которые берутся в прямом виде, если их значение равно нулю, либо в инверсном виде, если их значение в наборе равно единице.
Функция F1 в Сов КНФ примет вид:
.Теоремы булевой алгебры позволяют достаточно просто перейти от одной формы представления булевой функции к другой. Однако, с точки зрения минимизации алгебраических выражений более удобна Сов ДНФ.
1.5 Минимизация булевых функций
Аналитические методы минимизации
Используя законы булевой алгебры, можно получить для одной и той же логической функции множество эквивалентных представлений. Чем проще аналитическое выражение функции, тем экономичнее и проще ее практическая реализация на интегральных микросхемах. Сложность булевой функции определяется ее рангом, т.е. количеством переменных в ее конъюнктивных или дизъюнктивных членах.
Представление булевой функции в Сов ДНФ в большинстве случаев не является минимальным.
Используя операции поглощения и склеивания, его можно существенно упростить. Часто используется неполное склеивание, при котором оба члена, участвовавших в склеивании (или один из них), могут повторно склеиваться с другими оставшимися членами Сов ДНФ.
В процессе минимизации важно отыскать смежные конституенты, которые отличаются только одним аргументом (в одну конституенту аргумент входит с инверсией, а в другую – без нее).
Две смежные конституенты, склеиваясь, образуют импликанту рангом на единицу ниже, чем исходные конституенты.
Используя, например, неполное склеивание последней коституенты в Сов ДНФ функции F1 последовательно с остальными, приходим к следующему выражению:
Процесс многоступенчатого склеивания приводит к импликантам, которые не склеиваются с другими. Такие импликанты называют простыми. Форма записи булевой функции в ДНФ, состоящая только из простых импликант, называется сокращенной дизъюнктивной нормальной формой (Сокр ДНФ).
В некоторых случаях в Сокр ДНФ могут содержаться лишние импликанты, которые могут быть исключены без изменения значения функции.
Одним из методов отыскания лишних импликант является метод испытания членов: чтобы испытать некоторый член функции, следует исключить его из Сокр ДНФ и подставить в оставшееся выражение такие значения аргументов, которые обращают исключенный член в единицу. Если при такой подстановке оставшееся выражение окажется тождественно равным единице, то испытуемый член является лишним.
Найдем для примера тупиковую форму Сокр ДНФ
.Испытаем член 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. Поэтому член
– лишний.Испытание члена
по этой же методике показывает, что он не является лишним, в итоге тупиковая форма исходной функции имеет вид: .Минимизация булевых функций с помощью карт Карно
Для минимизации функций относительно небольшого числа переменной (не более шести) наиболее простым и наглядным является графический метод, использующий карты Карно.
Карта Карно – это прямоугольник, разбитый на квадраты, число которых равно числу наборов рассматриваемой функции, т. е. 2n. Клетки размечаются так, чтобы наборы, для которых возможны смежные конституенты, оказались бы в соседних клетках.
При заполнении карты Карно в ее клетки проставляют значения функции для соответствующих наборов, которые являются координатами клеток. Например, для функции двух переменных А и В (рис. 5) карта Карно имеет вид