Законы алгебры логики

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

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

1. а = а. Закон двойного отрицания.

2. а Ú 1 = 1; а &1= а. Законы одинарных элементов.

а Ú 0 = а. а & 0 = 0.

3. а Ú а = а; а & а = а. Закон тавтологии (идемпотентности).

4. а Ú а = 1; а & а = 0. Закон исключенного третьего

(противоречия).

5. а Ú b = b Ú a; a & b = b & a. Коммуникативный закон.

6. a Ú (b Ú c) = (a Ú b) Ú c. Ассоциативный закон.

a & (b & c) = (a & b) & c.

7. a & (b Ú c) = a & b Ú a & c. Дистрибутивный закон.

a Ú b & c = (a Ú b) &(aÚ c).

8. a & b = а Ú b. Закон отрицания отрицания.

а Ú b = a &b. (Закон де Моргана).

9. a Ú а &b = a. Закон поглощения.

a &(а Ú b) = а.

10. a & b Ú а & b = а. Закон склеивания.

(а Ú b) & (а Ú b) = а.

11. а Ú а & b = а Ú b. Закон Порецкого.

a &(а Ú b) = а & b.

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

Пример.

F(abc) = acÚ ac (bÚc) = ac (закон поглощения).

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

1.Действия в скобках.

2.Одноместные операции (отрицание или инверсия).

3.Конъюнкция (И).

4.Дизъюнкция (ИЛИ).

5.Сложение по модулю 2.

Пример. Пусть задана логическая функция вида

F(abc) = abc Ú abc Ú abсÚ abc Ú abc.

Если задано

а = 0; b = 1; c = 0. то

F(abc) = 0×1×0 Ú 0×1×0 Ú 0×1×0Ú 0×1×0 Ú 0×1×0 = 1×1×1 Ú 0×0×1 Ú0×0×0Ú

Ú 0×1×1Ú0×1×0 = 1Ú 0 Ú 0 Ú 0 Ú 0 Ú 0 = 1.

Полученное значение совпадает с приведенным в таблице истинности (таблица 2.3) для заданного набора значений переменных.

Правильность выполнения эквивалентных преобразований можно проверить путем составления таблицы истинности для исходной и преобразованной форм логической функции так, как это показано в таблице 2.4 на примере закона Порецкого для дизъюнкции (a Ú ab = a Ú b).

Таблица 2.4

Значения переменных	Значения функций
a	b	a	a b	a Ú ab	aÚb

Как видно из таблицы 2.4, значения функций a Ú ab и a Ú b совпадают при всех значениях переменных, т.е. эти функции эквивалентны.