Преобразование функций алгебры логики

Тождества алгебры логики

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

Тождества имеют вид:

,

,

.

Из этих тождеств следует:

- если аргумент равен нулю, то его отрицание равно единице и наоборот;

- если хотя бы один сомножитель равен нулю, то произведение всегда будет равно нулю;

- если хотя бы одно слагаемое равно единице, то сумма всегда будет равна единице.

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

Переместительный закон:

(2.1)

(2.2)

Из этого закона следует, что в выражениях алгебры логики допустима перестановка мест слагаемых и сомножителей.

Сочетательный закон:

(2.3)

(2.4)

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

Распределительный закон:

(2.5)

(2.6)

Выражение (2.5) позволяет раскрывать скобки и выносить за скобки отдельные аргументы. Справедливость выражения (2.6) можно доказать с помощью таблицы истинности.

Таблица 2.1.

Наборы аргументов		Левая часть выражения (2.6)		Правая часть выражения (2.6)
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

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

Закон инверсии (правило Де-Моргана):

(2.7)

(2.8)

Для доказательства справедливости выражений (2.7) и (2.8) построим таблицы истинности, соответственно таблица 2.2. и таблица 2.3.

Таблица 2.2.

Наборы аргументов		Левая часть		Правая часть
0 0
0 1
1 0
1 1

Левая и правая части выражения (2.7) равны на всех наборах аргументов.

Таблица 2.3.

Наборы аргументов		Левая часть		Правая часть
0 0
0 1
1 0
1 1

Из таблицы 2.3. следует, что выражение (2.8) справедливо.

Закон двойного отрицания:

.

Закон повторения:

(2.9)

(2.10)

Выражения (2.9) и (2.10) в доказательстве не нуждаются.

Закон поглощения:

(2.11)

(2.12)

Закон поглощения (2.11) и (2.12) докажем аналитическим путем.

.

.

Закон склеивания:

(2.13)

Доказательство аналитическое

. (2.14)

Теорема разложения в ряд функции алгебры

Логики

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

(2.15)

(2.16)

В выражениях (2.15) и (2.16) функция разложена по переменной х₁. Тождества теоремы разложения доказываются путем подстановки в левые и правые части тождеств в начале , , а затем , . В обоих случаях тождества будут одинаковые.

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

Пример 2.1. Разложить функцию сначала по х₁, а затем по х₂.

В результате разложения заданной функции получили ее стандартную форму.

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

(2.17)

(2.18)

(2.19)

(2.20)

Докажем справедливость выражения (2.17). Для этого функцию левой части данного выражения разложим по переменной х_i и в результате получим

(2.21)

Левую и правую части выражения (2.21) умножим на х_i согласно (2.17) и с учетом тождества и закона повторения получим:

.

Аналогично можно доказать соотношения (2.18) ¸ (2.20).

Соотношения (2.17) ¸ (2.20) позволяют сделать следующие выводы:

1. Если в логическом выражении какой-то из аргументов находится в конъюнктивной связи с одноименными аргументами или их отрицаниями, то при упрощении логического выражения вместо одноименных аргументов записывается 1, а вместо их отрицания 0.

2. Если в логическом выражении отрицание какого-либо аргумента находится в конъюнктивной связи с одноименными аргументами или их отрицаниями, то при упрощении логического выражения вместо одноименных аргументов ставится 0, а вместо их отрицаний 1.

3. Если в логическом выражении какой-то из аргументов находится в дизъюнктивной связи с одноименными аргументами или их отрицаниями, то при упрощении логических выражений вместо одноименных аргументов записывается 0, а вместо их отрицаний 1.

4. Если в логическом выражении отрицание какого-либо аргумента находится в дизъюнктивной связи с одноименными аргументами или их отрицаниями, то при упрощении логического выражения вместо одноименных аргументов записывается 1, а вместо их отрицаний 0.

Пример 2.2. Упростить логическое выражение (логическую функцию) .

Используя соотношение (2.17) получим

.

Пример 2.3. Упростить логическую функцию

.

Применяя соотношение (2.18) получим =

.

Пример 2.4. Упростить логическую функцию

.

Применяя соотношение (2.19) получим =

.