Главная страница  Систематические методы минимизации 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [ 23 ] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128]

ГЛАВА 4

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

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

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

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

1а) А-=.0, если Хф 1

16) Х = 1, если ХО

2а) X = 0, X = 1

26) Х=1, Х=0

За) 0-0=0

36) 1 1 = 1

4а) 1.0==0-1=0

46) 0-f 1 = 10 = 1

5а) М = 1

56) 00 = 0

6а) X-f 0-=Х • .

66)Х-1=Х

7а)Х4-1 = 1

76) Х-0 = 0

8а) Х - X = X

8б)Х-Х = Х

9а) Х- X = 1

96)Х-Х = 0

Юа) 5=хХ

Иа) X-fy=-y-f X

116) ХУ=У-Х

12а) X-fX-y=X

126) Х-{ХУ)=Х

13а) (ХУ)-У = Х-У

136) X-y-f У = Х-1-У

14а) X+y4Z=X-l-(y-f Z)=(Xy)+Z

146) X-Y-Z = X(y-T)=(X-Y)-Z

15а) X-y-*-X-Z=X-(yZ)

156) (X + y)(A:-f z)=x-fy-z

16а) {Xy)-(X-Z)(yZ)=

166) X-Y Jt-Z->tY-ZX-Y -Х- Z

=(X-fy).(X+Z)

17а) {X+y)-(XZ)=X-Z4-X-y

18а) XY-ZXYZ

186) X-Y-Z=XArYJbi



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

Основные определения и правила булевой алгебры, необходимые для анализа и синтеза логических схем, представлены в табл. 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




[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [ 23 ] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128]

0.0242