Логические функции. 
Электроэнергетика: информационное обеспечение систем управления

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

Сложное логическое выражение, записанное в виде логической функции, например

может быть представлено в базисе «HE-ИЛ И—И». Для нашего примера получается.

Соответствующая структурная схема автомата, реализующего функцию /в базисе «HE-ИЛ И-И», имеет вид, показанный на рис. 10.

Рис. 10. Реализация функции (6) в базисе «И-ИЛИ-НЕ».

Здесь имеется в виду, что любая входная переменная сразу же преобразуется в свое инверсное отображение, поэтому даны а, Ь, с и а, Ь, с. Всего в данном автомате использовано 10 базисных элементов.

Аксиомы и законы Де Моргана позволяют осуществить преобразование логического выражения, направленное на упрощение структурной схемы. Если при этом достигается минимальное число базисных элементов, то говорят об оптимальной, или минимизированной логике.

Проведем преобразования для функции (7):

Полученное выражение заметно проще, и соответствующая ему структурная схема (рис. 11) включает в себя лишь два элемента. Таким образом, тождественные преобразования меняют логическое выражение, но не саму логическую функцию.

Рис. 11. Минимизированная реализация функции (6) в базисе «И-ИЛИ-НЕ>

Тождественность выражения (6) и полученного выражения (8) может быть проверена при помощи таблицы истинности (табл. 6) для трех аргументов. В ней использованы обозначения:

Таблица 6.

Сравнение таблиц истинности для выражений (6) и (8)

Как видно из приведенной таблицы истинности, колонки/= (3 (получена по выражению (6)) и/= у (получена по выражению (8)) тождественны друг другу. В данной функции сигнал на выходе/появляется во всех случаях, кроме одного, когда а =, b= 1, с = 1.

Среди всех логических действий особое место занимают два: со₈ = х + у

(ИЛИ—НЕ) и щ₄=х-у (И—НЕ), получивших в логике названия операция

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

В логике существует понятие функционально полной системы — ФПС. Система (набор элементарных логических действий) является.

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

Покажем, что базис на основе одного действия «ИЛИ—НЕ» есть ФПС. Поскольку все логические действия могут быть представлены в базисе «И—ИЛИ—НЕ», то достаточно показать, что каждое из этих трех действий может быть выражено через операцию ИЛИ—НЕ, тем самым будет доказана функциональная полнота этого универсального действия. Введем обозначение для действия «стрелка Пирса» (отрицание дизъюнкции (см. ш₈)): х + у = al b, действительно:

• 1) отрицание x = x-x = x+x = xlx;
• 2) конъюнкция xy = xy = x + y = (x + x)+(y+y) = u+v, где и = x ± х, v = у I у, следовательно, ху = и ± v = (х ± х) I (у 1 у)
• 3) дизъюнкция x+y=x+y=xlу. Введя обозначениех l y = w, получаем х + у = w = w~+ w≅ w l w = (x i y) i (x i y).

Соответствующие структурные схемы на элементной базе «ИЛИ—НЕ» показаны на рис. 12.

Рис. 12. Реализация в базисе «ИЛИ—НЕ» операций: а — НЕ; б— И;*- ИЛИ Совершенно аналогично обосновывается ФПС в базисе «И—НЕ». Введем обозначение для операции «штрих Шеффера» (отрицание конъюнкции (см. a>₄)): х у = х у, действительно:

• 1) отрицание х = х-х = хх;
• 2) конъюнкция xy = xy = z, где z = х | у. Следовательно, xy = zz = {xy) (ф);
• 3) дизъюнкция х + у = х +, у = х-.у = (х|х)-(ф) = (;ф)| (ф).

Соответствующие структурные схемы на элементной базе «И-НЕ» показаны на рис. 13.

Рис. 13. Реализация в базисе «И-НЕ» операций: а-НЕ;б-И;