Информатика и вычислительная техника

       

Основные сведения из алгебры логики


В ЭВМ информация подвергается не только арифметической, но и логической обработке. Основу работы логических схем и устройств ЭВМ составляет специальный математический аппарат, называемый алгеброй логики, или исчислением высказываний. При этом под высказыванием понимается любое утверждение, о котором можно сказать истинно оно или ложно. В логике высказываний интересуются не содержанием высказываний, а только их истинностью или ложностью, никакие другие признаки высказываний в алгебре логики не рассматриваются. Одно и то же высказывание

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
  xi.

Конъюнкцией, или логическим умножением двух высказываний х и у, называется логическая функция Р, истинная только в том случае, когда истинны одновременно х и у. Таблица истинности для конъюнкции имеет вид:

Конъюнкция обозначается знаком & , который читается как "И".



В общем случае операция конъюнкции может быть определена для любого числа аргументов: х1 & х2 & ... =
n
&
i = 1
  xi.

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 :: Содержание


Содержание раздела