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

Математические средства решения логических задач составляют содержание алгебры логики, или булевой алгебры, названной так в честь ее создателя — английского математика Джорджа Буля. В соответствии с ней истинному высказыванию (наступлению события) приписывается, ставится в соответствие символ 1 (логическая 1), а ложному (не наступлению события) — символ 0 (логический 0).

Необходимо отметить, что символы 0 и 1 никакого отношения к числовому значению сигнала не имеют. Они лишь описывают качественное состояние события, и поэтому к ним неприменимы арифметические операции. В электрических цепях эти символы обычно представляются так же, как аналогичные в цифровом сигнале: логическая 1 — высоким U¹, а логический 0 — низким уровнем потенциала U⁰.

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

В алгебре логики определены отношение эквивалентности (=) и три операции:

дизъюнкция (операция ИЛИ), обозначаемая знаком V;

конъюнкция (операция И), обозначаемая знаком & или точкой, которую можно опускать (например, х × у = х у);

отрицание (инверсия, операция НЕ), обозначаемое чертой над переменными или над элементами 0 и 1 (например, `х, `0, `1).

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

Алгебра логики определяется следующей системой аксиом:

0Ú0=0,	0Ù0=0,	` ,
0Ú1=1,	0Ù1=0,	` ,
1Ú0=1,	1Ù0=0,
1Ú1=1,	1Ù1=1.

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

хÚ0=х,	хÙ0=0,	,
хÚ1=1,	хÙ1=х,	,
хÚх=х,	хÙх=х,
хÚ`х=1,	хÙ`х=0.

Для алгебры логики действительны следующие законы:

Переместительный закон:	Х1ÚX2=X2ÚX1; Х1×Х2=Х2×Х1.
Сочетательный закон:	Х1ÚХ2ÚХ3 = (Х1ÚХ2)ÚХ3 = Х1Ú(Х2ÚХ3); Х1×Х2×Х3 = (Х1×Х2)×Х3 = Х1×(Х2×Х3).
Распределительный закон:	Х1×(Х2ÚХ3) = X1×Х2ÚX1×Х3; Х1Ú(Х2×Х3) = (Х1ÚX2)×(X1ÚХ3).
Закон поглощения:	Х1ÚХ1×X2=Х1; X1×(Х1ÚХ2)=Х1.
Закон склеивания:	,
Закон отрицания (закон инверсии, теорема де Моргана):

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

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

Для функции n переменных можно использовать общее обозначение:

y=f(х_n-1, x_n-2, … ,x₁,x₀).

Любое самое сложное логическое высказывание можно описать, используя три логические операции: сложение (дизъюнкцию), умножение (конъюнкцию) и отрицание (инверсию), — которыми могут быть связаны простые высказывания. В указанном смысле этот набор логических функций называют функционально полным набором или базисом.

Для аналитического описания функционирования логических схем важную роль имеют понятия термов.

Термами называются переменные, инверсии переменных, их конъюнкции и дизъюнкции:

Х₁, `Х<sub>2</sub>, Х<sub>2</sub>×`Х₁×`Х<sub>0</sub>, `Х₂ÚХ₀.

Минимальным термом (минтермом или конституентой единицы) называется функция вида конъюнкции n переменных:

,

где знак ~ (тильда) означает прямое или инверсное значение переменной. Минтерм равен единице только на единственном наборе переменных.

Максимальным термом (макстермом или конституентой нуля) называется функция вида дизъюнкции n переменных:

,

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

Конъюнктивным термом (контермом) называется конъюнкция любого числа переменных .

Дизъюнктивным термом (дизтермом) называется дизъюнкция любого числа переменных .