12.2. Основные логические операции
Математический аппарат, описывающий действия цифровых устройств, базируется на алгебре логики, или, как её еще называют по имени автора, английского математика Джорджа Буля (1815-1864 г.г.), булевой алгебре. В практических целях первым применил его американский ученый Клод Шеннон в 1938 году при исследовании электрических цепей с механическими выключателями.
Алгебра логики оперирует двоичными переменами, которые условно обозначаются как 0 и 1 и подчиняются условию х = 1, если х 0 и х = 0, если х 1. В её основе лежит понятие переключательной (логической) функции вида y = f (х1, х2,…,xn) относительно аргументов х1, х2,…,xn, которая, как и её аргументы, может принимать только два значения: 0 и 1. Логическая функция может быть задана словесно, алгебраическим выражением и таблицей, которая называется таблицей истинности.
Действия над двоичными переменными производятся по правилам логических операций. Основных логических операций три:
отрицание (инверсия, операция НЕ);
логическое умножение (конъюнкция, операция И);
логическое сложение (дизъюнкция, операция ИЛИ).
Более сложные логические преобразования можно свести к указанным трем операциям.
Инверсия выполняется над одной
переменной: функция y
= 1 при х = 0 и у = 0 при х =
1. Инверсия обозначается как у =
(игрек равен не икс), соответственно
.
Операция НЕ имеет аксиомы:
;
Результат двойного отрицания логической
переменной равен самой логической
переменной:
.
Логическое умножение производится над двумя и более логическими переменными:
.
Операция И имеет следующие аксиомы: 1·0 = 0·1 = 0; 1·1 = 1, т.е. нулевое значение хотя бы одного из аргументов обеспечивает нулевой результат операции. Для функции И справедливы следующие соотношения:
х ∙ 0 = 0; х ∙ х = х; х ∙ 1 = х; 
.
Логическое и арифметическое умножение двоичных чисел тождественны.
Операция логического сложения так же, как и операция логического умножения, справедлива для бесконечного числа переменных.
.
Аксиомы операции ИЛИ: 1 + 1 = 1; 0 + 1 = 1 + 0 =
1; 0 + 0 = 0. Аксиома 1 + 1 = 1 не имеет аналога
в двоичной арифметике, где 1 + 1 = 10. Для
функции ИЛИ справедливы соотношения:
х + 0 = х; х + х = х; х + 1 = 1;
.
12.3. Законы алгебры логики
При проектировании цифровых устройств пользуются аксиомами алгебры логики. Законы алгебры логики вытекают из аксиом п. 12.2. Здесь они приводятся без доказательства. Их правильность легко проверить по таблицам истинности либо путём подстановки 0 и 1 вместо соответствующих значений переменных.
Основные законы алгебры логики представляют собой комбинации из инверсий, дизъюнкций и конъюнкций над логическими переменными и возможные соотношения между ними.
1. Переместительный закон: х1 + х2 = х1 + х2; х1 ∙ х2 = х2 ∙ х1.
2. Сочетательный закон: х1 (х2 ∙ х3) = (х1 ∙ х2) х3 = х2 (х1 ∙ х3).
3. Распределительный закон: х1 ∙ х2 + х1 ∙ х3 = х1 (х2 + х3);
(х1 + х2) ∙ (х1 + х3) = х1 + (х2 ∙ х3).
4. Закон универсального множества: 1 + х1 + х2 +…+ хn = 1.
5. Закон нулевого множества: 0 ∙ х1 ∙ х2 ∙…∙ хn = 0.
6. Законы повторения: х + х +…+ х = х; х ∙ х ∙…∙ х = х.
7. Закон многократной инверсии:
; 
.
8. Законы дополнительности:
; 
.
9. Законы поглощения: х1 + х1 ∙ х2 = х1; х1 (х1 + х2) = х1.
10. Законы склеивания:
; 
.
11. Законы отрицания:
функция Шеффера – это отрицание коньюнкции и читается И-НЕ
;
функция Пирса – это отрицание дизъюнкции и читается ИЛИ-НЕ
.
Функции Шеффера и Пирса являются полными, так как посредством этих функций можно описать работу сколь угодно сложного логического устройства.
12. Закон Блэка-Порецкого:
;
.