. Таблица истинности имеет структуру: 
Законы алгебры логики
I. Законы однопарных элементов
1) закон универсального множества: x Ú 1 =1; x ×1 = x.
2) закон нулевого множества: x Ú 0 = x; x ×0 = 0.
II. Законы отрицания
1) закон двойного отрицания: 
;
2) закон дополнительности: 
;
3) закон двойственности (де Моргана): 
III. Комбинационные законы
1) законы тавтологии: x Ú x = x; x × x = x.
2) коммутативные законы: x Ú y = y Ú x; x × y = y × x.
3) сочетательные (ассоциативные): x Ú (y Ú z)=(x Ú y)Ú z;
x ×(y × z)=(x × y) × z.
4) распределительные (дистрибутивные): x ×(y Ú z)=(x × y)Ú (х × z);
x Ú (y × z)=(x Ú y) × (x Ú z)
5) законы поглощения (абсорбции): x Ú (x × y) = x; x × (x Ú y) = x.
6) законы склеивания: 
; 
.
Упрощение функций
Чтобы упростить логическую функцию, т.е. преобразовать формулу к виду с наименьшим числом вхождений переменных, можно использовать законы логики или диаграммы Вейча (карты Карно).
Пример 5: Упростить функцию: 
.
I способ. С помощью законов логики:
= 
= 
= 
.
При упрощении применялись законы: закон де Моргана, закон двойного отрицания, распределительный закон.
II способ. С помощью карт Карно:
|
| 
|
| |
| 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 |
| 
|
|
|
Карта Карно позволяет выделить произведения, которые можно упростить. Если произведения стоят в соседних клетках, то из общего выражения можно исключить одну переменную:
= 
.
Переключательные схемы
В компьютерах широко применяются электрические схемы, содержащие сотни и тысячи переключательных элементов: реле, выключателей и т.п. При разработке таких схем используется аппарат алгебры логики.
|
|
Переключательная схема – это схематическое изображение некоторого устройства, состоящего из переключателей и соединяющих их проводников, а также из входов, на которые подается, и выходов, с которых снимается, электрический сигнал.
Каждый переключатель имеет два состояния: замкнутое и разомкнутое. Переключателю Х поставим в соответствие логическую переменную х, которая принимает значение 1 в том и только в том случае, когда переключатель Х замкнут и схема проводит ток; если же переключатель разомкнут, то х равен нулю.
Будем считать, что два переключателя Х и 
связаны таким образом, что когда Х замкнут, то разомкнут, и наоборот. Следовательно, если переключателю Х поставлена в соответствие логическая переменная х, то переключателю должна соответствовать переменная 
.
Всей переключательной схеме можно поставить в соответствие логическую переменную, равную единице, если схема проводит ток, и равную нулю – если не проводит. Эта переменная является функцией от переменных, соответствующих всем переключателям схемы, и называется функцией проводимости.
Найдем функции проводимости F некоторых переключательных схем:
Схема не содержит переключателей и проводит ток всегда, F =1;
Схема содержит один постоянно разомкнутый контакт, F =0;
Схема проводит ток, когда переключатель X замкнут, и не проводит, когда X разомкнут, F ( x ) = x;
Схема проводит ток, когда переключатель X разомкнут, и не проводит, когда X замкнут, F ( x ) = ;
Схема проводит ток, когда оба переключателя замкнуты, F (x, y) = x. × y; 
Схема проводит ток, когда хотя бы один из переключателей замкнут, F ( x, y )= x Ú y;
Две схемы называются равносильными, если через одну из них проходит ток тогда и только тогда, когда он проходит через другую (при одном и том же входном сигнале). Из двух равносильных схем более простой считается та схема, функция проводимости которой содержит меньшее число логических операций или переключателей.
Пример 6. Построить схему, содержащую 4 переключателя x, y, z и t, такую, чтобы она проводила ток тогда и только тогда, когда замкнут контакт переключателя t и какой-нибудь из остальных трёх контактов.
|
|
Решение.
Очевидно, что функция проводимости имеет вид F (x, y, z, t) = t . (x v y v z), а схема выглядит так:
Пример 7. Найти функцию проводимости схемы:
Решение.
Имеется четыре возможных пути прохождения тока при замкнутых переключателях a, b, c, d, e: через переключатели a, b; через переключатели a, e, d; через переключатели c, d и через переключатели c, e, b. Функция проводимости:
F (a, b, c, d, e)= (a . b) v (a . e . d) v (c . d) v (c . e . b).
Пример 8. Упростить переключательную схему:
Решение.
.
Упрощенная схема:
Логические схемы
С х е м а И (Конъюнкция)
Схема И реализует конъюнкцию двух или более логических значений. Единица на выходе схемы И будет тогда и только тогда, когда на всех входах будут единицы. Когда хотя бы на одном входе будет ноль, на выходе также будет ноль. Связь между выходом z этой схемы и входами x и y описывается соотношением: z = x × y (читается как " x и y "). Операция конъюнкции на структурных схемах обозначается знаком "&" (читается как "амперсэнд"), являющимся сокращенной записью английского слова and.
| x | y | x × y |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
С х е м а ИЛИ (Дизъюнкция)
Схема ИЛИ реализует дизъюнкцию двух или более логических значений. Когда хотя бы на одном входе схемы ИЛИ будет единица, на её выходе также будет единица. Знак "1" на схеме – от устаревшего обозначения дизъюнкции как ">=1" (т.е. значение дизъюнкции равно единице, если сумма значений операндов больше или равна 1). Связь между выходом z этой схемы и входами x и y описывается соотношением: z = x Ú y (читается как " x или y ").
|
| x | y | x Ú y |
| 0 | 0 | 0 | |
| 0 | 1 | 1 | |
| 1 | 0 | 1 | |
| 1 | 1 | 1 |
С х е м а НЕ (отрицание)
Схема НЕ (инвертор) реализует операцию отрицания. Связь между входом x этой схемы и выходом z можно записать соотношением z = , x где читается как "не x " или "инверсия х ". Если на входе схемы 0, то на выходе 1. Когда на входе 1, на выходе 0.
| x | 
|
| 1 | 0 |
| 0 | 1 |
С х е м а И–НЕ (Элемент Шеффера)
Схема И–НЕ состоит из элемента И и инвертора и осуществляет отрицание результата схемы И. Связь между выходом z и входами x и y схемы записывают следующим образом: 
читается как "инверсия x и y ".
| x | у | 
|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
С х е м а ИЛИ–НЕ (Элемент Вебба)
Схема ИЛИ–НЕ состоит из элемента ИЛИ и инвертора и осуществляет отрицание результата схемы ИЛИ. Связь между выходом z и входами x и y схемы записывают следующим образом: z = 
, читается как "инверсия x или y ".
| x | Y | 
|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
С х е м а Импликация
Схема Импликация состоит из элемента ИЛИ и осуществляет дизъюнкцию отрицания входа x и входа y схемы ИЛИ. Связь между выходом z и входами x и y схемы записывают следующим образом: 
читается как "из x следует y ".
| x | Yy | x ® y |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
С х е м а Эквивалентность
Связь между выходом z и входами x и y схемы записывают следующим образом: 
, читается как " x эквивалентно (равносильно) y ".
|
| x | y | x º y |
| 0 | 0 | 1 | |
| 0 | 1 | 0 | |
| 1 | 0 | 0 | |
| 1 | 1 | 1 |
