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

Математические средства решения логических задач составляют содержание алгебры логики, или булевой алгебры, названной так в честь ее создателя — английского математика Джорджа Буля. В соответствии с ней истинному высказыванию (наступлению события) приписывается, ставится в соответствие символ 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₀).

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

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

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

Х₁, Х₂, Х₂Х₁Х₀, Х₂Х₀.

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

,

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

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

,

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

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

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