Содержание
-
Тема 1.5Основные понятия алгебры логики
-
Функции алгебры логики (булевы функции)
№ Значения булевых функций в зависимости от значений аргументов x и y Обозна-чение функции Название функции x 0 0 1 1 y 0 1 0 1 1 F0(x, y) 0 0 0 0 2 F1(x, y) 0 0 0 1 3 F2(x, y) 0 0 1 0 4 F3(x, y) 0 0 1 1 5 F4(x, y) 0 1 0 0 6 F5(x, y) 0 1 0 1 Конъюнкция, логическое умножение, И, , AND Запрет по x, отрицание импликации Запрет по y, отрицание импликации Переменная x Переменная y Константа ноль
-
7 F6(x, y) 0 1 1 0 8 F7(x, y) 0 1 1 1 9 F8(x, y) 1 0 0 0 10 F9(x, y) 1 0 0 1 11 F10(x, y) 1 0 1 0 12 F11(x, y) 1 0 1 1 13 F12(x, y) 1 1 0 0 14 F13(x, y) 1 1 0 1 15 F14(x, y) 1 1 1 0 16 F15(x, y) 1 1 1 1 Сумма по модулю 2, логическая неравнозначность, М2, XOR Дизъюнкция, логическое сложение, ИЛИ, OR Стрелка Пирса, отрицание дизъюнкции, ИЛИ-НЕ, NOT OR Эквивалентность Отрицание, инверсия y, НЕ, NOT Импликация от y к x Импликация от x к y Штрих Шеффера, отрицание конъюнкции, И-НЕ, NOT AND Константа единица Отрицание, инверсия x, НЕ, NOT
-
Основные законы алгебры логики
1) Законы нулевого множества 2) Законы универсального множества 3) Законы идемпотентности (повторения, тавтологии) 4) Закон двойной инверсии
-
5) Законы дополнительности: 8) Дистрибутивные законы (законы распределения): - закон логического противоречия - закон исключенного третьего 6) Коммутативные законы (законы перемещения) 7) Ассоциативные законы(законы сочетания) - конъюнкции относительно дизъюнкции - дизъюнкции относительно конъюнкции
-
9) Законы поглощения 10) Законы склеивания (распространения) 11) Законы де Моргана (законы инверсии): - для двух переменных - в общем виде
-
Формы описания логических функций
1) Словесное 2) В виде таблиц истинности x2 x1 x0 y = f(x2,x1,x0) 0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1
-
Формы описания логических функций
3) В виде последовательности десятичных чисел 4) В виде алгебраических выражений. Операция замены аргументов одной функции другими, более простыми функциями называется суперпозицией функций F(x2,x1,x0) = (1,2,4,7) = (1,2,4,7) F(x2,x1,x0) = (0,3,5,6) = (0,3,5,6) Элементарная конъюнкция Элементарная дизъюнкция
-
Формы описания логических функций
Дизъюнктивная нормальная форма (ДНФ) Конъюнктивная нормальная форма (КНФ)
-
Если в состав логического выражения входят наборы элементарных конъюнкций с одинаковым количеством переменных, связанные дизъюнкцией, то такая форма ФАЛ называется совершенной дизъюнктивной нормальной формой (СДНФ) Если в состав логического выражения входят наборы элементарных дизъюнкций с одинаковым количеством переменных, связанные конюнкцией, то такая форма ФАЛ называется совершенной конъюнктивной нормальной формой (СКНФ)
-
Пример построения СДНФ и СКНФ
Значения аргументов Значения функции СДНФ СКНФ x2 x1 x0 f(x2,x1,x0) 0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1
-
СДНФ СКНФ
-
Логические элементы
& x0 xn–1 . . . «И» y = x0…xn–1 y = x0…xn–1 1 x0 xn–1 . . . y = x0+…+xn–1 «ИЛИ» y = x0…xn–1 «НЕ» 1 x _ x
-
x0 xn–1 «И-НЕ» & … ________ y = x0…xn–1 ________ y = x0…xn–1 x0 xn–1 «ИЛИ-НЕ» 1 … ________ y = x0+…+xn–1 ________ y = x0…xn–1
-
Тема 1.6Логические основы ЭВМ
-
Минимизация булевых функций
Метод непосредственных преобразований
-
Метод непосредственных преобразований Для ранее построенной СДНФ
-
Для ранее построенной СКНФ
-
Минимизация булевых функций
Метод Карно-Вейча x2 x1 x0 y = f(x2,x1,x0) x2 x1 x0 y = f(x2,x1,x0) 0 0 0 1 1 0 0 0 0 0 1 1 1 0 1 0 0 1 0 0 1 1 0 0 1 1 1 1 1 1 1 0 0 1 0 0 1 0 1 1 0 1 x2 x1 x0 1 1 0
-
Метод Карно-Вейча 1 0 1 0 0 1 1 0 0 1 0 0 1 0 1 1 0 1 x2 x1 x0
-
Свойства карты Карно: комбинации значений переменных для соседних клеток карты Карно различаются значением только одной входной переменной. При переходе с одной клетки в соседнюю клетку всегда изменяется значение только одной переменной на ее инверсное значение; соседними являются между собой крайние левые и крайние правые клетки карты, а также крайние верхние и крайние нижние клетки (как если бы карты были свернуты в цилиндры по вертикали и горизонтали).
-
Все единицы (при записи функции в дизъюнктивной форме) и все нули (при записи функции в конъюнктивной форме) должны быть замкнуты в прямоугольные контуры. Единичные контуры могут содержать несколько единиц, но не должны содержать нулей. Нулевые контуры могут содержать несколько нулей, но не должны содержать единиц. Одноименные контуры могут накладываться один на другой, т.е. одна и та же единица (или ноль) может входить в несколько единичных (нулевых) контуров. Число клеток в контуре должно быть равно 2i , где i = 0, 1, 2, …, n, т.е. число клеток в контуре выражается числами 0, 1, 2, 4, 8, 16, 32, … Каждой единичной клетке отвечает конъюнкция входных переменных, которые определяют данную клетку. Каждой нулевой клетке отвечает дизъюнкция инверсий входных переменных, которые определяют данную клетку. Выражения, которые отвечают контурам, не содержат тех переменных, чьи границы пересекаются площадью, ограниченной данным контуром. Дизъюнктивная форма ФАЛ составляется в виде дизъюнкций конъюнкций, которые отвечают единичным контурам. Конъюнктивная форма ФАЛ составляется в виде конъюнкций дизъюнкций, которые отвечают нулевым контурам. Если каждой клетке отвечает свой контур, то результирующее выражение представляет собой СДНФ или СКНФ данной ФАЛ. Минимальной ДНФ или КНФ отвечает минимальное количество единичных или нулевых контуров.
-
Минимизация булевых функций
Метод Карно-Вейча 1 0 1 0 0 1 1 0 0 1 0 0 1 0 1 1 0 1 x2 x1 x0 0 0 0 1 0 1 1 1 0 1 1 0 1 1 0 1 0 0 x2 x1 x0 y1 y2 Минимальная ДНФ: z1 z2 Минимальная КНФ: F(x2, x1, x0) = y1 y2
-
Построение логических схем
Минимальная ДНФ: & 1 1 x2 x1 x0 & 1 y Преобразуем ДНФ: x2 x1 x0 1 & y &
-
Минимальная КНФ: Цифровая схема реализации 1 & y 1 x2 x1 x0 1 1
-
Применим к КНФ двойную инверсию: 1 y x2 x1 x0 1 1 1 1
-
Кроме того, применив к последнему выражению для КНФ закон идемпотентности: можно реализовать КНФ с использованием только одного типа логических элементов. y x2 x1 x0 1 1 1 1 1
Нет комментариев для данной презентации
Помогите другим пользователям — будьте первым, кто поделится своим мнением об этой презентации.