Основные сведения из алгебры логики
В ЭВМ информация подвергается не только арифметической, но и логической обработке. Основу работы логических схем и устройств ЭВМ составляет специальный математический аппарат, называемый алгеброй логики, или исчислением высказываний. При этом под высказыванием понимается любое утверждение, о котором можно сказать истинно оно или ложно. В логике высказываний интересуются не содержанием высказываний, а только их истинностью или ложностью, никакие другие признаки высказываний в алгебре логики не рассматриваются. Одно и то же высказывание
104
не может быть одновременно истинным и ложным или не истинным и не ложным.
Если высказывание истинно, то считают, что его значение равно единице; если высказывание ложно, то считают, что его значение равно нулю. Таким образом, значения высказываний можно рассматривать как переменную величину, принимающую только два дискретных значения: 0 или 1. Это приводит к полному соответствию между логическими высказываниями в математической логике и двоичными цифрами в двоичной системе счисления.
Всякое устройство ЭВМ, выполняющее арифметические или логические операции, можно рассматривать как функциональный преобразователь, входными переменными (аргументами) которого являются исходные двоичные числа, а выходной функцией от нее - новое двоичное число, образованное в результате выполнения двоичной операции. При этом как входные переменные, так и выходные функции могут принимать лишь одно из двух возможных значений: 0 или 1.
В каждом конкретном случае количество входных переменных будет различным. В простейшем виде это одна переменная х, принимающая значение 0 или 1. В общем случае таких переменных может быть п, т.е. x1, x2, ..., хn. Так как каждая переменная х; при этом равна 0 или 1, то для n переменных образуется множество разнообразных сочетаний или наборов входных переменных.
В алгебре логики строго доказывается, что для n переменных количество различных наборов равно 2n. Так, для одной переменной х существует только два набора: или , так как 2 = 2; для двух переменных x1, x2 - четыре различных набора: , , , , так как 2 = 4; для трех переменных x1, x2, х3 - восемь различных наборов, так как 23 = 8, и т.д.
Функция f(x1, x2, ..., хn), определяемая на наборах входных двоичных переменных х1, x2, ..., хn и принимающая в качестве возможных значений 0 или 1, называется логической функцией. Примем без доказательства, что общее число различных логических функций от n аргументов равно 22n. Например, для n = 1, 2, 3 и т.д. их будет соответственно 4, 16, 256 и т.д.
Над логическими переменными в алгебре логики производятся логические операции, основными из которых являются операции отрицания, дизъюнкции и конъюнкции.
Операции отрицания соответствует логическая функция одного аргумента, которая истинна, если аргумент ложен, и ложна, когда аргумент истинен. Операцию отрицания называют также операцией НЕ или инверсией.
105
Данная операция обозначается чертой, которая ставится над аргументом, например, х.
Для представления логических операций удобно пользоваться таблицами истинности, в которых возможным наборам аргументов ставятся в соответствие значения функций. Табличное представление операции отрицания имеет вид:
Очевидным является следующее свойство операции отрицания x = х.
В отличие от операции отрицания для операций дизъюнкции и конъюнкции уже требуется, как минимум, два аргумента.
Дизъюнкцией двух высказываний х и у называется логическая операция, в результате которой образуется логическая функция F, истинная в том случае, если хотя бы одно из высказываний х или у истинно. В соответствии с этим определением таблица истинности для дизъюнкции имеет вид:
Дизъюнкция обозначается знаком ? , который читается как "ИЛИ", т.е. F = x ? y.
Часто данную операцию называют операцией логического сложения. В общем случае эта операция может быть определена для любого числа аргументов: x1 ? x2 ? x3 ? ... =
| n |
| ? |
| i = 1 |
Конъюнкцией, или логическим умножением двух высказываний х и у, называется логическая функция Р, истинная только в том случае, когда истинны одновременно х и у. Таблица истинности для конъюнкции имеет вид:
Конъюнкция обозначается знаком & , который читается как "И".
В общем случае операция конъюнкции может быть определена для любого числа аргументов: х1 & х2 & ... =
| n |
| & |
| i = 1 |
106
Для дизъюнкции, конъюнкции и отрицания справедливы следующие логические выражения:
В алгебре логики действуют четыре основных закона: переместительный (коммутативный), сочетательный (ассоциативный), распределительный (дистрибутивный) и общей инверсии (правило или формула де Моргана). Приведем соотношения, отражающие эти законы.
1. Переместительный закон:
- - для дизъюнкции х1 ? х2 = x2 ? х1;
- - для конъюнкции х1 & х2 = х2 & х1.
2.. Сочетательный закон:
- - для дизъюнкции (х1 ? x2) ? x3 = х1 ? (x2 ? x3);
- - для конъюнкции (х1 & x2) & x3 = х1 & (x2 & x3).
3, Распределительный закон:
- - для дизъюнкции (x1 ? x2) & x3 = х1 & х3 ? x2 & х3;
- - для конъюнкции (x1 & x2) ? x3 = (х1 ? х3) & (x2 ? х3).
4. Закон общей инверсии (формула де Моргана):
- - для дизъюнкции х1 ? х2 = х1 & х2;
- - для конъюнкции х1 & х2 = х1 ? х2.
Следует отметить, что все приведенные законы, кроме закона общей инверсии и распределительного закона для конъюнкции, полностью аналогичны соответствующим законам для сложения и умножения в обычной алгебре. Такая аналогия отсутствует для формулы де Моргана и для распределительного закона для конъюнкции. Их справедливость можно доказать с помощью таблиц истинности, вычисляя в них значения левой и правой частей доказываемого логического выражения для всех наборов логических переменных.
Докажем, например, справедливость формул де Моргана для дизъюнкции и конъюнкции. С этой целью составим таблицу для четырех наборов переменных x1 и х2, а затем в столбцах этой таблицы вычислим по соответствующим правилам алгебры логики значения левых и правых частей доказываемых формул. Полученные результаты сведем в таблицу.
107
| * | ** | * | ** | ||||||
| x1 | x2 | x1 ? x2 | x1 ? x2 | x1 & x2 | x1 ? x2 | x1 | x2 | x1 & x2 | x1 ? x1 |
| 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
Сравнивая в этой таблице столбцы, отмеченные одной или двумя звездочками, убеждаемся в том, что они совпадают. Следовательно, справедливы формулы де Моргана для дизъюнкции и конъюнкции.
Следует также отметить, что приведенные законы алгебры логики справедливы не только для двух, но и для любого числа переменных. Например, закон общей инверсии для дизъюнкции и конъюнкции в общем случае имеет вид:
x1 ? x2 ? x3 ? … = x1 & x2 & x3 & … ; x1 & x2 & x3 & … = x1 ? x2 ? x3 ? … .
Аналогично, для распределительного закона имеют место следующие соотношения:
x1 & (x2 ? x3 ? …) = (x1 & x2) ? (x1 & x3) ? …; x1 ? (x2 & x3 & …) = (x1 ? x2) & (x1 ? x3) & ….
Из распределительного закона для дизъюнкции и конъюнкции вытекают так называемые
- формулы склеивания:
(x1 & x2) ? (x1 & x2) = x1; (x1 & x2) & (x1 ? x2) = x1;
- формулы поглощения:
x1 ? (x1 & x2) = x1; x1 & (x1 ? x2) = x1; x1 ? (x1 & x2) = x1 ? x2; x1 & (x1 ? x2) = x1 & x2.
В их справедливости можно убедиться, составив необходимые таблицы истинности.
108
104 :: 105 :: 106 :: 107 :: 108 :: Содержание
