1 Лекция 1 БУЛЕВА АЛГЕБРА ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ Логические основы построения микропроцессорных систем

2 Содержание лекции 1 Темы слайда Булева алгебра. Основные понятия 3 Булевы функции одной переменной 7 Булевы функции двух переменных 12 Свойства Булевых функций 40 Законы Булевой алгебры 47 Правила и тождества Булевой алгебры 51 Свойства функции сложение по модулю два 56 Свойства функций штрих Шеффера, стрелка Пирса 58 Булевы функции двух аргументов, обозначения 61 Вопросы 64

3 Булева алгебра (БА) – раздел математической логики. Булева функция (БФ) и ее аргументы принимают два значения (0 или 1). В БА нет линейных коэффициентов, деления, корня, логарифма и т.д., используется двоичная арифметика.

4 БА лежит в основе работы цифровых устройств (ЦУ). Достоинства ЦУ - высокая точность, помехозащищенность при передаче, хранении и обработке информации. С помощью БА выполняются логические и математические операции (автоматика, компьютеры и т.д.).

5 В электронных схемах логические операции выполняются с помощью логических элементов. Логические сигналы 0 и 1 задаются с помощью разных уровней напряжения: положительная логика: 0 -низкий уровень сигнала, 1-высокий; отрицательная логика – наоборот. Пример: логический 0: 0 - 0,4 В; логическая 1: 2,4 - 5 В.

6 Для изображения логических схем используются условные графические обозначения (УГО) элементов. Существует несколько стандартов УГО: - американский стандарт – milspec 806B; - стандарт - МЭК А – созданный Международной Электротехнической Комиссией; - российский стандарт – ГОСТ

7 Представление БФ: 1. Словесное 2. Графическое 3. Табличное 4. Алгебраическое 5.Схемное.

8 Различные сочетания значений аргументов БФ называются наборами. Функция F (n) определена на 2 n наборах. Для n аргументов существует 2 2 n различных БФ.

9 БФ одной переменной Таблица истинности (ТИ) Таблица Обозначение Название Константа ноль 101 Повторение 210 Отрицание (инверсия) Константа единица

10 Основные БФ: 1. Повторение ( F 2 ): Обозначение:

11 2. Отрицание, инверсия, «НЕ», NOT Если аргумент равен 0, то функция равна 1, и наоборот.

12 Обозначение: X F a) по ГОСТ и стандарту МЭК б) по стандарту milspec

13 Временные диаграммы «НЕ»

14 Реализация «НЕ»

15 БФ двух переменных (x, y). Таблица истинности. Таблица 1.2 xyF0F0 F1F1 F2F2 F3F3 F4F4 F5F5 F6F Таких функций 16.

16 xyF7F7 F8F8 F9F9 F 10 F 11 F 12 F 13 F 14 F Продолжение ТИ

17 Основные булевы функции двух и более переменных:

18 3. Конъюнкция (операция «И», логическое умножение, AND): Функция «И» равна нулю, если равен нулю хотя бы один аргумент (F 8 ): F =x /\ y или F =x y F =x y или F =x & y

19 Обозначение (2И): X y F a) по ГОСТ и стандарту МЭК б) по стандарту milspec

20 Таблица истинности:

21 Временные диаграммы «2И»

22 Реализация «2И»

23 4. Дизъюнкция (операция «ИЛИ», логическое сложение, OR): Функция«ИЛИ» равна 1, если равен 1 хотя бы один аргумент (F 14 ): F=x+y или F=x y

24 Обозначение (2ИЛИ): б) стандарт milspec в) стандарт МЭК а) ГОСТ 1 X y F

25 Таблица истинности:

26 Временные диаграммы «2ИЛИ»

27 Реализация «2ИЛИ»

28 5. Сумма по модулю два (MOD2): Выполняется двоичное сложение в одном разряде без учета переноса (F 6 ): F = x y Обозначение: M2 X y F

29 Таблица истинности:

30 Временные диаграммы элемента

31 6. Исключающее ИЛИ (XOR) : БФ равна 1, если равен 1 только один ее аргумент – «1 и только 1» (F 6 ): F = x XOR y Функция может быть выражена через логические операции:

32 Таблица истинности:

Обозначение: 33 a) по ГОСТ и стандарту МЭК б) по стандарту milspec

34 7. Эквивалентность(равнозначность) : Функция принимает 1 значение только при равенстве входных переменных(F 6 ): F = x y или F = x ~ y Функция может быть выражена через логические операции:

35 = X y F Обозначение:

36 Таблица истинности:

37 8. Неэквивалентность(неравнозначность) : Функция принимает 1 значение только при неравенстве входных переменных(F 6 ): F = x y = X y F Обозначение:

38 Таблица истинности:

39 Внимание: Три логических элемента Сумма по модулю 2, Исключающее ИЛИ, Неравнозначность при двух входных переменных имеют полностью идентичные таблицы истинности, и полностью взаимозаменяемы. Функция Эквивалентность в том случае обозначается как инверсия этих функций.

40 XYZXORM

41 9. Стрелка Пирса (отрицание дизъюнкции, «ИЛИ – НЕ», NOT OR, NOR): Логическое сложение с инверсией результата ( F 1 ): F = x y F=x+y или F=x y

42 Таблица истинности:

43 Обозначение (2ИЛИ-НЕ): 1 X y F б) стандарт milspec в) стандарт МЭК а) ГОСТ

Штрих Шеффера (отрицание конъюнкции, «И – НЕ», NOT AND, NAND): Логическое умножение с инверсией результата (F 7 ): F = x / y F =x /\ y или F =x y F =x y или F =x & y

45 Таблица истинности:

46 Обозначение (2И-НЕ): X y F б) по стандарту milspec a) по ГОСТ и стандарту МЭК

Мажоритарность Мажоритарный элемент имеет много входов. Выходная переменная элемента принимает единичное значение, если большая часть её входных переменных равна единице.

48 Так, переменная F на выходе трехходового мажоритарного элемента принимает единичное значение, если два или три его входа имеют единичное значение.

49 XYZF

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

51 2 X y F z Обозначение: a) по ГОСТ и стандарту МЭК

Импликация от х к у: Сложение переменной Y с инверсным значением переменной X (F 11 ): F = x y Обозначение :

53 Таблица истинности:

Импликация от y к x: Сложение переменной X с инверсным значением переменной Y (F 13 ): F = y x Обозначение :

55 Таблица истинности:

Запрет: Логическое умножение на инверсию одной переменной (F 2 ): Обозначение:

57 Таблица истинности:

58 ПРИЛОЖЕНИЯ Приложение 1.1. Свойства БФ. Приложение 1.2. Законы БА. Приложение 1.3. Тождества БА. Приложение 1.4. БФ двух аргументов.

59 Приложение 1.1. Свойства БФ 1 – «ИЛИ», 2 – «И», 3 – «НЕ».

60 (1)

61 (2)

62 (3)

63 Примеры свойств функций, их реализация

64

65

66 Приложение 1.2. Законы БА

67 Переместительный Сочетательный

68 Распределительный

69 Реализация законов БА

70 Приложение 1.3. Правила и тождества БА

71 Правило де Моргана для «И», «ИЛИ»

72 Тождества для «И», «ИЛИ»:

73 Правило поглощения: Склеивания:

74 Примеры реализации законов, правил, тождеств БА

75 Свойства функции «сложение по модулю два»

76 Определение операции: Правило де Моргана: Свойства:

77 Свойства функций стрелка Пирса, штрих Шеффера.

78 Определение операции « »: Определение операции «/»: Правило де Моргана:

79 Свойства:

80 Приложение 1.4. БФ двух аргументов (таблица 1.2)

81

82

83 ВОПРОСЫ

84 Укажите правильное определение: 1. Функция И равна нулю, если равен нулю только один аргумент. 2. Функция ИЛИ равна нулю, если равен нулю только один аргумент. 3. Функция И равна единице, если равен единице хотя бы один аргумент. 4. Функция И равна нулю, если равен нулю хотя бы один аргумент. 5. Функция ИЛИ равна единице, если равны единице все аргументы.

85 Указать наименование логических элементов на рисунке. Может ли у этих элементов быть один вход и почему?

86 КОНЕЦ

87 Лекция 2 Комбинационные устройства (без элементов памяти): логическая функция зависит от комбинации значений входных переменных

88 Содержание лекции 2 Темы слайда Выражение Булевых функций через другие Булевы функции 71 Базис «И, ИЛИ, НЕ» 78 Совершенная дизъюнктивная нормальная форма 84 Минимизация логических функций 90 Таблица Карно 90 Определение равносильности Булевых функций 101 Цифровые логические элементы 107 Основные параметры логических элементов 109 Электрические параметры логических элементов 112

89 Лекции 1-2. Содержание лекции 2 Темы слайда Временные параметры логических элементов 117 Примеры корпусов микросхем 122 Пример цоколевки микросхем 127 П 2.1. Закон двойственности 131 П 2.2. Функциональная декомпозиция Булевых функций 133 П 2.3. Алгоритм нахождения совершенной коньюктивной нормальной формы 135 Вопросы 137

90 Выражение Булевых функций (БФ) через другие БФ.

91 - Базис - БФ, при помощи которых можно выразить любую другую БФ. Примеры базисов: 1. «И – НЕ»; 2. «ИЛИ – НЕ»; 3. «И, ИЛИ, НЕ»; 4. «, И, 1» и другие.

92 Пример: выразить в базисах «ИЛИ-НЕ», «И-НЕ» операцию «ИЛИ».

93 Пример: выразить в базисах «ИЛИ-НЕ», «И-НЕ» операцию «И».

94 Реализация И, ИЛИ, НЕ в базисе И-НЕ

95

96

97 Базис «И, ИЛИ, НЕ»

98 Логическую функцию можно разложить по переменной X i : (2.1)

99 Пусть x i = 0, тогда:

100 Пусть x i = 1, тогда:

101 Выражение (2.1) позволяет записать все логические функции, используя операции И, ИЛИ, НЕ. Пример: разложение функции «И» 2-х переменных. Разложение по x 1 :

102 Продолжим для x 0 : Для функции «И» из ТИ:

103 Пример: разложение функции «Сложение по модулю два»: Выражение (2.1) - совершенная дизъюнктивная нормальная форма (СДНФ), где: Слагаемые - произведения всех переменных или их отрицаний.

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

105 Пример. Имеется три двоичных датчика: x 0 ; x 1 ; x 2. Необходимо реализовать ЛФ F мажор принимающую значение 1, когда равны 1 значения двух и более датчиков (повышение надежности датчиков за счет дублирования). 1. Составим таблицу истинности логической функции (ЛФ).

106 Таблица истинности логической функции

107 (3, 5, 6, 7 наборы, где функция равна 1) 2. Запишем ДНСФ:

Составим схему:

ТАБЛИЦА КАРНО (ТК) Правила построения 1.1. Количество клеток ТК равно количеству строк таблицы истинности. МИНИМИЗАЦИЯ ЛОГИЧЕСКИХ ФУНКЦИЙ

Слева и сверху - значения аргументов В двух соседних клетках отличается значение только одного аргумента (клетки на противоположных краях таблицы - соседние) В клетки заносятся значения ЛФ Клетки с «1» объединяются в прямоугольники по 2 i клеток.

Для прямоугольников записывается произведение аргументов, не изменяющих значения в соседних клетках Переменные в произведении – в прямом виде, если их значение в соседних клетках «1», иначе – в инверсном Произведения складываются по ИЛИ в искомую ЛФ.

112 ТК функции F МАЖОР

113 Прямоугольники - A, B, C, причем (x 1 в соседних клетках меняет значение и его в конъюнкции нет).

114 Составим схему после минимизации: Исходная схема:

АНАЛИТИЧЕСКИЕ ПРЕОБРАЗОВАНИЯ (реализуются в карте Карно)

116 Примечание: 3, 5, 6, 7 строчки таблицы и добавлено (X 2 ·X 1 ·X 0 ) + (X 2 ·X 1 ·X 0 )

117

118

119 Применяя Правило де Моргана получим (в базисе И-НЕ):

120 Определение равносильности БФ При помощи: - таблицы истинности; - законов алгебры логики; - приведением к СДНФ (или СКНФ - см. Приложения).

121 Пусть даны три функции: Определим их равносильность.

С помощью ТИ. xyxy функции на всех наборах одинаковы. F 1 = F 2 = F 3.

С помощью логических преобразований.

124 F 1 = F 2 = F 3.

При помощи СДНФ F 1 является СДНФ. F 1 = F 2 = F 3.

126 Цифровые логические элементы на интегральных микросхемах (ИМС): Импульсные - управление по перепаду потенциала импульса. Используются положительные перепады, обозначение: отрицательные:

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

128 Основные параметры логических элементов: 1 Набор логических функций; 2 Число входов по И и по ИЛИ; 3 Коэффициент разветвления по выходу; 4 Потребляемая мощность; 5 Задержка распространения сигнала или максимальная частота входного сигнала (динамические параметры).

129 Цифровые микросхемы: Логическая функция, обозначение, схема. Например: К 155 ЛА 4

130 (2-2И-2ИЛИ) (2-2И-2ИЛИ-НЕ)

131 ЭЛЕКТРИЧЕСКИЕ ПАРАМЕРЫ ЛОГИЧЕСКИХ ЭЛЕМЕНТОВ

132 ПараметрК155К555К531КР1531 U 1 вх. мин., В2222 U 0 вх. макс., В0.8 U 0 вых. макс., В I 0 вых. макс., мА16820 U 1 вых. мин., В I 1 вых., макс., мА I 1 вых. макс. с ОК, мкА I 1 вых. макс. сост. Z, мкА I 0 вых. макс. сост. Z, мкА I 1 вх. макс., мкА I 0 вх. макс., мА I к.з. макс., мА (U 0 вых =0) -(18 55) (60 150) t зд. Р., нс R н, к Ом P пот., м Вт ТТЛ микросхемы (при Uпит = 5В)

133 ПараметрК176К561КР1561 U 1 вх. мин., В777 U 0 вх. макс., В333 I вх. макс., мкА U 0 вых. макс., В I 0 вых. макс., мА U 1 вых. мин., В I 1 вых. макс., мА t зд. Р., нс КМОП микросхемы (при Uпит =10В)

134 Уровни логических сигналов на входах и выходах микросхем ТТЛ и КМОП логики

135 Выходное напряжение современных трёхвольтовых микросхем, таких как SN74LVT совпадает с уровнями нуля и единицы пятивольтовых микросхем.

136 ВРЕМЕННЫЕ ПАРАМЕРЫ ЛОГИЧЕСКИХ ЭЛЕМЕНТОВ

137 Задержка распространения сигнала от входа к выходу логического элемента

138 ПЕРЕДНИЕ и ЗАДНИЕ ФРОНТЫ при ПЕРЕКЛЮЧЕНИИ МИКРОСХЕМЫ в реальных условиях эксплуатации

139 ПЕРЕДНИЕ и ЗАДНИЕ ФРОНТЫ при ПЕРЕКЛЮЧЕНИИ МИКРОСХЕМЫ в реальных условиях эксплуатации

140 ПЕРЕДНИЕ и ЗАДНИЕ ФРОНТЫ

141 ПРИМЕРЫ КОРПУСОВ МИКРОСХЕМ

142 ТИПЫ КОРПУСОВ МИКРОСХЕМ

143 ТИПЫ КОРПУСОВ МИКРОСХЕМ

144 ТИПЫ КОРПУСОВ МИКРОСХЕМ 0,45 х 0,25

145 Устройство микросхемы

146 Пример цоколевки микросхем FZH 125 FLH И-НЕ 4-2И A, B, C, D, E – входы; Y - выходы; Vcc – питание; GND – земля.

147

148

149 ПРИЛОЖЕНИЯ Приложение 2.1. Закон двойственности Приложение 2.2. Функциональная декомпозиция БФ Приложение 2.3. СКНФ

150 Двойственная форма БФ: получается из заданной формы путем замены дизъюнкции на конъюнкцию и наоборот. Двойственная форма функции F обозначается F *. П 2.1. Закон двойственности

151

152 П 2.2. Функциональная декомпозиция БФ Используя разложение по переменным, БФ можно представить: а) с помощью двух составляющих; б) разложением на множители.

153 а) СДНФ: б) Совершенная коньюктивная нормальная форма (СКНФ):

154 П 2.3. Алгоритм нахождения СКНФ: -выделяют наборы, где функция равна 0; -составляют произведения наборов из сумм переменных, входящих в прямом виде, если переменная равна 0, в инверсном, если равна 1. Используется для разработки цифровых устройств.

155

156 ВОПРОСЫ 1. Привести пример базиса. 2. Чем ограничена максимальная частота импульсов на входе цифровой микросхемы? 3. Для каких целей может использоваться СДНФ?

157 КОНЕЦ