ГЛАВА 4

Алгебра логики

4.1. ОСНОВНЫЕ ПОНЯТИЯ

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

Таблица 4.1. Определения и правила алгебры Буля

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

Основные определения и правила булевой алгебры, необходимые для анализа и синтеза логических схем, представлены в табл. 4.1. Так же, как в обычной алгебре, переменные величины здесь обозначаются буквами. Каждый символ может иметь только два значения: или 1, или- 0. Таково значение определений {la. б) в табл. 4.1. Определение (2с, б) вводит очень важное понятие логического отрицания (инверсии), символом которого является черточка над соответствующей величиной.

Если перемейная X имеет значение 1, то отрицание переменной X, т. е. не Х=Х, имеет значение О и наоборот. Обратим внимание на то, что определения 4 и 5 совпадают с определениями основных алгебраических операций с двоичными числами. Справедливость 6 и 10 может быть доказана на основе рассмотренных выше определений. Главное значение имеет понятие логического сложения и логического умножения. На практике для обозначения операции сложения и умножения пользуются теми же символами, что и в обычной алгебре, но они имеют другое логическое значение. Например, Х+Х=Х выражает: .Х или .Х равняется X, а Х-Х=Х выражает: X к X равняется X.

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

A+BC+iA+BQ iD+F)=A+BC.

Правило 15 находит применение при преобразовании алгебраических выражений с комбинированными логическими суммами и произведениями. Согласно правилу 156

AB+CD= (A+CD) (В+С£))=(Л+С) {A+D) (В+С) (B+D).

Отметим, что правило 15а справедливо и в нормальной алгебре, а правило 156, дуальное правилу 15а, в нормальной алгебре не справедливо.

Для преобразования алгебраических выражений булевых функций часто используются правила 16, имеющие следующий смысл. Если в произведении сумм (или в сумме произведений) есть переменная (или комбинация переменных) в первоначальном и инверсном видах, то опускается сумма (или произведение) переменных, относящихся к первоначальным переменным (или их комбинациям) и их инверсным формам. Например, ABC+ABD + +BCD=ABC+ABD, так как можно исключить BC-BD = BCD. Аналогично

{A+B+C+D)(A+B+D-{-E){A+C+D+E)= . . ={A+B+C+D){A+~B+D+E).

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

менной Z в выражении, соответствующем инверсной величине X. и наоборот. Это правило не имеет дуальной формы, так как она тождественна основной форме 17а.

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

X + Y = XY, (4.1)

X+Y=XY, (4.2)

W=X+Y, . (•)

Xr = X-fF, (4.4)

так как они простым способом определяют дополнение каждой логической функции. Если, например, F=(A + B)ID(B + C)+AB\

то можем прямо написать, что F=AB + (D + BCy(A+B).

Законы де Моргана позволяют также упростить алгебраическое Ёыражение логических функций. Haпpимep, coглacнqJIpaви-лам 18 и /5можно написать, что А(В + С)+ВС=-А+ВС, так как В + С=ВС.

4.2. СПОСОБЫ ПРЕДСТАВЛЕНИЯ ЛОГИЧЕСКИХ ФУНКЦИЙ. НОРМАЛЬНАЯ ФОРМА ЛОГИЧЕСКИХ ВЫРАЖЕНИЙ

Каждая логическая переменная может иметь две величины. Если например Л = 1, то должно быть Л = 0. Две переменные А, В могут иметь 2=4 значения: АВ. АВ, АВ, АВ; три переменные 2=8 значений и т. д.

Систематическую и наглядную запись комбинаций логических переменных обеспечивают комбинационные (истинностные) таблицы. На рис. 4.1с представлена такая таблица для двух переменных. Однако комбинационная таблица (хотя она и выгодна для анализа определенных функций) имеет лишь ограниченное применение. Чаще используется матричная запись переменных в карты Карно, которые при наличии п переменных состоят из 2" полей. На рис. 4.16 представлена карта для двух переменных - А, В. Согласно обозначениям на карте переменной А наверху и переменной В слева, первому полю наверху слева соответствует комбинация АВ и т. д. В карте на рис. 4.1е в каждое поле записаны соответствующие двоичные числа, а в карте на рис. 4.1г - соответствующие десятичные цифры. Например, ЛВ= (11)2= (3)ю-На рис. 4.Id, е представлен принцип записи трех переменных - А,В, С,-в истинностные таблицы и карты Карно.

На рис. 4.2с, б показаны истинностная таблица четырех переменных - А. В, С. D - и принцип их записи в карты, на рис. 4.2е - принцип записи пяти переменных в карты Карно. 76