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

логики

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

(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) получим =

.

2.4. Функционально-полные системы функций

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

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

Система функций алгебры логики называется функционально полной, если с помощью функций, входящих в эту систему можно представить любую из 16 функций алгебры логики двух аргументов. В пятом столбце таблицы 1.6. все функции двух аргументов представлены одной их стандартных форм, которая называется совершенной дизъюнктивной нормальной формой (СДНФ). СДНФ включает в себя три функции алгебры логики

• отрицание «НЕ»,

• конъюнкцию «И»,

• дизъюнкцию «ИЛИ».

Этот состав функций «И», «ИЛИ», «НЕ» является основным функционально-полным набором функций алгебры логики.

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

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

1. «И», «ИЛИ», «НЕ»;

2. «И-НЕ»;

3. «ИЛИ-НЕ».

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

Для представления любого логического выражения любым функционально-полным набором необходимо сначала это выражение представить функционально полным набором «И», «ИЛИ», «НЕ» используя таблицу 1.6., а затем используя закон двойного отрицания и закон инверсии заданное выражение можно представить функционально-полным набором «И-НЕ» либо «ИЛИ-НЕ». Функционально-полные наборы называют базисами.

Пример 2.5. Представить логическое выражение базисом «И», «ИЛИ», «НЕ».

Для этого согласно таблице 1.6. сначала избавимся от операции неравнозначности, а затем от операции равнозначности. В результате получим:

.

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

Для представления этого логического выражения базисом «И-НЕ» необходимо избавиться от операции ИЛИ (логического сложения). Для этого воспользуется сначала законом двойного отрицания и получим:

.

По закону инверсии опустим нижнюю черту двойного отрицания на аргумент

.

Таким образом в базисе «И-НЕ» присутствуют только две операции «И» (логическое умножение) и отрицание, которые реализуются одним логическим элементом.

Аналогично выполняется представление данного логического выражения базисом «ИЛИ-НЕ». Для этого необходимо избавиться от операции логического умножения.

