Элементарная логика. Аксиомы, основные теоремы и тождества алгебры логики.

Различные логические переменные могут быть связаны функциональными зависимостями. Функциональные зависимости между логическими переменными могут быть описаны логическими формулами или таблицами истинности.

В общем виде логическая формула функции двух переменных записывается в виде: y=f(X₁, X₂), где X₁, X₂ — входные переменные.

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

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

Дизъюнкция.В отличие от обычного арифметического или алгебраического суммирования здесь наличие двух единиц даёт в результате единицу. Поэтому при обозначении логического суммирования предпочтение следует отдать знаку (∨) вместо знака (+) [1].

Первые две строчки таблицы истинности операции дизъюнкции (x₁=0) определяют закон сложения с нулём: x ∨ 0 = x, а вторые две строчки (x₁ = 1) — закон сложения с единицей: x ∨ 1 = 1.

Конъюнкция.Таблица 4 убедительно показывает тождественность операций обычного и логическог умножений. Поэтому в качестве знака логического умножения возможно использование привычного знака обычного умножения в виде точки [1].

Первые две строчки таблицы истинности операции конъюнкции определяют закон умножения на ноль: x·0 = 0, а вторые две — закон умножения на единицу: x·1 = x.

Исключающее ИЛИ.Под функцией «Исключающее ИЛИ» понимают следующее: единица на выходе появляется тогда, когда только на одном входе присутствует единица. Если единиц на входах две или больше, или если на всех входах нули, то на выходе будет нуль.

Надпись на обозначении элемента ИСКЛЮЧАЮЩЕЕ ИЛИ «=1» (Рисунок 1, г) как раз и обозначает, что выделяется ситуация, когда на входах одна и только одна единица.

Эта операция аналогична операции арифметического суммирования, но, как и другие логические операции, без образования переноса. Поэтому она имеет другое название сумма по модулю 2 и обозначение ⊕, сходное с обозначением арифметического суммирования.

аксиомы:

		ассоциативность
		коммутативность
		законы поглощения
		дистрибутивность
		дополнительность

Законы:

1 Переместительный: X ∨ Y = Y ∨ X; X · Y = Y · X.

2 Cочетательный: X ∨ Y ∨ Z = (X ∨ Y) ∨ Z = X ∨(Y ∨ Z); X · Y · Z = (X · Y) · Z = X· (Y· Z).

3 Идемпотентности: X ∨ X = X; X · X = X.

4 Распределительный: (X ∨ Y)· Z = X· Z ∨ Y· Z.

5 Двойное отрицание: .

6 Закон двойственности (Правило де Моргана):

Для преобразования структурных формул применяется ряд тождеств:

X ∨ X · Y = X; X(X ∨ Y) = X — Правила поглощения.

X· Y ∨ X· = X, (X ∨ Y)·(X ∨ ) = X – Правила склеивания.