Логическое умножение
Эта функция двух переменных и истинна тогда, когда одновременно истинны обе входные переменные. Эта функция имеет кроме названия «логическое умножение» также названия « функция конъюнкции », «функция И ». При использовании аналитической ( формульной ) записи функция логического умножения изображается символом «&», знаком «*» или «·» (как в математике).
Запись « a & b » читается « a и b ».
Условно – графическое обозначение функции И в логической схеме
а &
а & b
b
Таблица истинности
-
№ набора
a
B
a & b
0
0
0
0
1
0
1
0
2
1
0
0
3
1
1
1
Согласно таблице истинности логическое умножение одноразрядных двоичных чисел аналогично арифметическому умножению.
Логические временные диаграммы схемы И.
a
1
0 t
b
1
0
t
y =a&b
1
0
t
Логическое сложение
Эта функция двух переменных и истинна, когда истинна хотя бы одна входная переменная. Функция имеет несколько названий – «логическое сложение», «функция дизъюнкции», «функция ИЛИ». При использовании аналитической (формульной) записи функция логического сложения изображается символом «V» или «+».
Запись «a V b» читается «a или b».
Условно – графическое изображение в логических схемах
a 1
a + b
b
Таблица истинности
-
№ набора
a
b
a +b
0
0
0
0
1
0
1
1
2
1
0
1
3
1
1
1
Логические временные диаграммы схемы ИЛИ
a
1
0 t
b
1
0
t
y =a+b
1
0 t
Согласно таблице истинности логическое сложение одноразрядных двоичных чисел не совпадает с арифметическим сложением.
Три рассмотренные функции позволяют реализовать любую логическую функцию. Однако удобнее это делать при использовании не табличного, а аналитического способа.
Аналитический способ задания логической функции
При аналитическом (формульном) способе задания переключательной функции используется суперпозиция – подставка функции вместо аргумента. Используя суперпозицию можно получить любую сколь угодно сложную функцию. В аналитическом выражении порядок выполнения действий определяется старшинством операций и круглыми скобками. Приоритет такой: НЕ → И → ИЛИ.
Пример.
Записать функцию f = a & b , где
a = x1 & x2,
b = x1 V x2,
тогда f = x1 & x2 & ( x1 V x2 ),
Аналитический способ позволяет задать сложную функцию, значительно компактнее, чем табличный.
Основные законы булевой алгебры
Переместительный закон
a V b = b V a
a & b = b & a
Сочетательный закон
a V ( b V c ) = ( a V b ) V c
a & ( b & c ) = ( a & b ) & c
Распределительный закон
a & ( b V c ) = a & b V a & c
a V b & c = ( a V b ) & ( a V c)
Примечание: a+b*c = (a+b)*(a+c).
Проиллюстрируем правильность последнего закона с помощью таблицы истинности: функция имеет 3 входа, число входных наборов 8 (23).
Номер набора |
a |
b |
c |
b & c |
a V b |
a V c |
aVb&c |
(aVb) & (aVc) |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
2 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
3 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
4 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
5 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
6 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
7 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Закон нулевого множества
a & 0 = 0
a V 0 = a
Закон универсального множества
a & 1 = a
a V 1 = 1
Закон повторения
a & a = a
a V a = a
Следствие: a & a & … & a = a
a V a V … V a = a
Закон поглощения
a V a & b =a
a & ( a V b ) =a
Доказательство:
a V a & b = a & 1 V a & b = a & ( 1 V b) = a & 1 = a
умножим вынесем
a & ( a V b ) = a & a V a & b = a V a & b = a
умножим
Законы для инверсии:
а) закон дополнения
a & НЕ( a ) = 0
a V НЕ( a ) = 1
б) закон склеивания
a & b V a & НЕ( b ) = a
( a V b ) & ( a V НЕ( b )) =a
в) закон двойного отрицания
НЕ( НЕ( a )) = a
г) правило Де - Моргана
НЕ( a & b ) = НЕ( a ) V НЕ( b )
НЕ( a V b ) = НЕ( a ) & НЕ( b ).
Следствием является правило Де – Мограна – Шеннона:
Для того, чтобы взять отрицание от какого-либо выражения, надо все знаки логического сложения заменить знаками логического умножения, все знаки логического умножения заменить знаками логического сложения и взять отрицание всех членов выражения.
Применение законов для упрощения логических выражений:
X & Y V X & НЕ( Y ) V НЕ( X ) & Y V НЕ( X ) & НЕ( Y ) =
= X & ( Y V НЕ( Y ) + НЕ( X ) & ( Y V НЕ( Y ) =
= X & 1 V НЕ( X ) & 1 = X V НЕ( X ) = 1
или X(Y+ НЕ(Y))+НЕ(X)(Y+НЕ(Y))
( X V Y) & ( X V НЕ(Y)) & (НЕ(X) V Y ) & (НЕ(X) V НЕ(Y)) =
= ( X V Y & НЕ(Y)) & (НЕ(X) V Y & НЕ(Y)) =
= ( X V 0 ) & (НЕ(X) V 0) = X & НЕ(X) = 0
НЕ((X V НЕ(Y)) & НЕ(Z) V НЕ(X & НЕ(Y) & Z)) =
= НЕ((X V НЕ(Y)) & НЕ(Z)) & (X & НЕ(Y) & Z) =
= ( НЕ(X V НЕ(Y)) V Z ) & X & НЕ(Y) & Z ) =
= ( НЕ(X) & Y V Z) & X & НЕ(Y) & Z =
= НЕ(X) & Y & X & НЕ(Y) & Z V & X & НЕ(Y) & Z =
= 0 V X & НЕ(Y) & Z = X & НЕ(Y) & Z
Упражнения.
Упростить логические выражения: (правило Д-М.)
а) НЕ(НЕ(a ) V b) = a & НЕ(b);
б) НЕ((a V b) & НЕ(c)) = НЕ(a V b) V c = (НЕ (a) & НЕ(b)) V c;
в) НЕ(a & НЕ(b) V НЕ(c)) = (НЕ(a) V b) & c.
Проверка с помощью таблиц истинности.
а)
a |
b |
НЕ(a) |
НЕ(b) |
НЕ(a) V b |
НЕ(НЕ(a) V b)) |
a & НЕ(b) |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
б)
a |
b |
c |
НЕ(a) |
НЕ(b) |
НЕ(c) |
aVb |
(aVb)&НЕ(c) |
НЕ((aVb)&НЕ(c)) |
(НЕ(a)& НЕ(b))Vc |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
в)
a |
b |
c |
НЕ(a) |
НЕ(b) |
НЕ(c) |
a&НЕ(b)VНЕ(c) |
НЕ(a&bVНЕ(c)) |
(НЕ(a)Vb)&c |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
Упростить с помощью закона поглощения:
а) a & ( a V b ) & ( a V c ) = a & ( a V c ) = a;
б) ( a1 & a2 ) V ( a1 & a2 & a3 ) V a1 V a2 V ( a1 & a2 ) =
= ( a1 & a2 ) V a1 V a2 = a1 V a2;
Упростить выражения с помощью закона склеивания:
а) ( a V b & c ) V ( a V b & НЕ(c)) = a V b;
б) ( a V b V c ) & ( a V НЕ(b) V c) = a V c.
4. Применяя законы логики, упростить выражения:
а) НЕ(НЕ(x) & НЕ(y)) V НЕ(x) & ( x V НЕ(НЕ(x) V y )) =
= ( x V y ) V НЕ(x) & ( x V ( x & НЕ(y)) = ( x V y ) V НЕ(x) & (x) =
= x V y V НЕ(x) & x = x V y;
б) НЕ( x & y) V (НЕ(x) & y & z ) & (НЕ(x) V НЕ((x & y) V НЕ(y))) =
= (НЕ(x) V НЕ(y)) V (НЕ(x) & y & z ) & (НЕ(x) V (НЕ(x) V НЕ(y)) & y) =
= (НЕ(x) V НЕ(y)) V (НЕ(x) & y & z ) & (НЕ(x) V НЕ(x) & y V НЕ(y) & y ) =
= (НЕ(x) V НЕ(y)) V (НЕ(x) & y & z ) & НЕ(x) =
= (НЕ(x) V НЕ(y)) V (НЕ(x) & y & z );
в) (x & НЕ(y) & z) V ( x & (НЕ(y & z)) V ( x & y & z ) V ( x & НЕ(y)) =
= (( x & z ) & НЕ(y)) V (( x & z ) & y ) V ( x & (НЕ( y & z ) V НЕ(y))) =
= ( x & z ) & (НЕ(y) V y ) V ( x & (( НЕ(y) V НЕ(z)) V НЕ(y))) =
= ( x & z ) V ( x & (НЕ(y) V НЕ(z))) = x & ( z V (НЕ(y) V НЕ(z))) =
= x & ( НЕ(y) V z V НЕ(z)) = x & ( НЕ(y) V 1) = x.
Проверка с помощью таблиц истинности:
а)
-
X
Y
НЕ(x)
НЕ(y)
НЕ(x)&
НЕ(y)
НЕ(НЕ(x)&
НЕ(y))
НЕ(x)Vy
F1
F2
F3
F4
0
0
1
1
1
0
1
0
0
0
0
1
0
0
1
0
1
0
1
1
1
1
0
1
1
0
0
1
1
0
0
1
1
1
1
0
0
0
1
1
0
1
1
1
Обозначения:
F1 = НЕ(НЕ(x) V y);
F2 = x V НЕ(НЕ(x) V y));
F3 = НЕ(НЕ(x) & НЕ(y)) V НЕ(x) & (x V НЕ(НЕ(x) V y));
F4 = x V y.
б)
-
X
y
z
F1
F2
F3
F4
F5
F6
F7
F8
F9
F10
0
0
0
1
1
1
0
0
0
1
0
1
1
0
0
1
1
1
1
0
0
0
1
0
1
1
0
1
0
1
1
0
0
0
1
1
0
1
1
0
1
1
1
1
0
1
0
1
1
1
1
1
1
0
0
1
0
1
0
0
0
0
0
1
1
1
0
1
1
0
1
0
0
0
0
0
1
1
1
1
0
0
0
0
0
1
0
0
0
0
0
1
1
1
0
0
0
0
1
0
0
0
0
0
Обозначения:
F1 = НЕ(x & y);
F2 = НЕ(x);
F3 = НЕ(y);
F4 = НЕ(x) & y & z;
F5 = x & y;
F6 = НЕ((x & y) V НЕ(y));
F7 = НЕ(x) V НЕ((x & y) V НЕ(y));
F8 = (НЕ(x) &y & z) & (НЕ(x) V НЕ((x & y ) V НЕ(y)));
F9 = левая часть;
F10 = правая часть.
в)
Обозначения:
F1 = x & НЕ(y) & z;
F2 = НЕ(y & z);
F3 = x & НЕ(y & z);
F4 = x & y z;
F5 = x & НЕ(y);
F6 = левая часть;
F7 =правая часть = x.
X |
y |
z |
НЕ(y) |
F1 |
F2 |
F3 |
F4 |
F5 |
F6 |
F7 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |