Элементы алгебры логики

 

В настоящее время математический аппарат алгебры логики является основой проектирования цифровых устройств, особенно комбинационных схем.

Напомним основные положения алгебры логики. Символы 0 и 1 в алгебре логики не имеют количественного содержания и используются для обозначения качества высказываний: например, ложно и истинно, нет и да и т. д.

Для задания логической функции обычно используют или аналитический, или табличный способ.

Табличный способ является более громоздким, но зато он значительно нагляднее.

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

Для аналитической записи многие логические операции обозначают специальными символами.

Черта над переменной обозначает логическое отрицание (инверсию), знак V — логическое сложение, а знак умножения (точка) — логическое умножение.

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

Число аргументов однозначно определяет число различных функций от этих аргументов.

При числе аргументов, равном п, число их различных сочетаний составит 2 , а число функций уже 4 .

В то же время многие функции могут применяться и в тех случаях, когда число переменных больше двух.

В таблице 2 приведены более традиционные формы таблиц истинности для логических функций И, И-НЕ, ИЛИ и ИЛИ-НЕ при трех переменных.

Таблица 2

Таким образом, при любом числе переменных значение:

- функции И равно логической 1 только при равенстве 1 всех переменных;

- функции И-НЕ равно логическому 0 только при равенстве 1 всех переменных;

- функции ИЛИ равно логическому 0 только при равенстве 0 всех переменных;

- функции ИЛИ-НЕ равно логической 1 только при равенстве 0 всех переменных.

Как и в обычной алгебре (алгебре чисел) в алгебре логики существуют теоремы, знание которых значительно облегчает действия с логическими переменными.

Коммутативный закон:

Х1*Х2=Х2*Х1;                              X1VX2=X2VX1.

Ассоциативный закон:

Х1*(Х2*ХЗ)=(Х1*Х2)*ХЗ; XIV(X2VX3)=(XIVX2)VX.

Дистрибутивный закон:

Х1*(X2VX3)=X1*X2VX1*ХЗ;       X1VX2*X3= (X1VX2)*(X1VX3).

Правило повторения:

Х*Х=Х;                                          ХVХ=Х.

Правило отрицания:

Х* =0;                                         XV =0.

Правило двойного отрицания:

=X;                                          XV =1.

Правило склеивания:

X1(X1VX2)=X1;                             X1VX1*X2=X1.

Теорема Моргана:

= V ;                 = * .

Операции с 0 и 1:

X*1=X;                                           XV0=X.

X*0=0;                               XV1=1.