Элементы математической логики

Как и в обычной алгебре, в булевой алгебре вводятся действия над ее переменными. Как в обычной математике все действия в конечном итоге можно свести к четырем действиям арифметики (на этом строятся компьютерные алгоритмы и программы), так и в алгебре логики существует три действия, при помощи которых могут быть выражены любые более сложные логические действия. По сути дела, мы уже во введении познакомились с одним из этих действий, называемым инверсией. Ниже будем употреблять для него общепринятое название «отрицание». Обозначения этого и двух других базисных действий — конъюнкции и дизъюнкции — приведены в табл. 3.

В пособии будем использовать первый из предложенных способов обозначения. Так же как и в математике, вместо а • b будем писать ab. Каждое действие опишем таблицей истинности и дадим ему геометрическую и релейную интерпретации, а также обозначение соответствующего элемента в структурных логических и электронных схемах. Помимо этого приведем один из вариантов электронной схемы на транзисторной основе, хотя надо помнить, что таких исполнений может быть достаточно много. Ниже будем избегать рассмотрения способов технической реализации, поскольку в теории ДА нас интересуют функции автомата, а не его электронные схемы.

Таблица 3.

Описание основных логических операций

Отрицание (НЕ). Логическая операция, в результате которой из данного высказывания «а» получается высказывание «не а». В геометрической интерпретации если, а есть принадлежность точки данной области, то а есть принадлежность всей остальной (заштрихованной) области, или непринадлежность заданной области. Электронная схема на /?/7/?-транзисторе и другие интерпретации приведены на рис. 5.

Рис. 5. Интерпретация операции НЕ: а — таблица истинности; б — геометрическая интерпретация; в — релейная интерпретация; г — обозначение операции НЕ на логических схемах; д — интерпретация с помощью транзистора.

Дизъюнкция (операция ИЛИ). Дизъюнкция двух высказываний (аргументов) истинна, если истинно хотя бы одно из высказываний — а или Ь.

Заштрихованная область (рис. 6, б) соответствует принадлежности, а или Ь. Часто дизъюнкцию п аргументов называют логической суммой х_{ ИЛ И х₂ ИЛ И …х_п =х_{ +х₂+ ••• ⁺ х, — На выходе логического устройства сигнал ИЛИ появляется при наличии сигнала на одном или нескольких входах. Два параллельных контакта в релейной схеме образуют логическую схему ИЛИ. Замыкание одного из контактов или обоих приведет к появлению сигнала на выходе (а + Ь).

Схема на диодах (рис. 6, д) дает представление об электронной реализации этой операции.

Рис. 6. Интерпретация операции ИЛИ: а — таблица истинности; б — геометрическая интерпретация; в — релейная интерпретация; г — обозначение элемента ИЛИ на логических схемах; д — интерпретация в виде схемы с диодами.

Конъюнкция (операция И). Конъюнкция двух высказываний истинна лишь при истинности обоих высказываний а и Ь.

Заштрихованная область (рис. 7, б) принадлежит одновременно а и Ь. Часто конъюнкцию называют логическим умножением х, Их₂И …Их_п =х_{ • х₂'… *х_п.

В таблице истинности видно (рис 7, а), что ab есть произведение двоичных чисел а и Ь.

Рис. 7. Интерпретация операции И:

а — таблица истинности; б — геометрическая интерпретация; в — релейная интерпретация; г — обозначение элемента И на логических схемах; д — интерпретация в виде схемы с диодами На выходе логического устройства И сигнал появляется при одновременной подаче сигналов на все входы. В теории релейных схем такое устройство соответствует двум последовательным НРК (рис. 7, в). На рис. 7, д приведена схема И на диодах (здесь r" R). При отсутствии высокого потенциала (U_m < Е) хотя бы на одном из входов протекает ток от +Е к нулевому потенциалу и напряжение на выходе близко к нулю, т. е. ab = 0. Только в случае U_a> +Е и U_ь > +Е (а=, b= 1) напряжение U_ob = +Е, следовательно, ab= 1.

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

где d = b (c+abможет быть реализована на элементной базе НЕ, ИЛИ, И в виде схемы, показанной на рис. 8, а.

Рис. 8. Структурная схема логической реализации функции (1а) и (16).

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

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

• ассоциативность (сочетание).

• коммутативность (перестановка).

• дистрибутивность (распределение).

• двойное отрицание

Заметим, что выражение (2) к обычной алгебре неприменимо. Рассмотрим некоторые специфические соотношения. Помня, что конъюнкции (И) соответствуют последовательно включенные НРК, дизъюнкции (ИЛИ) — параллельно включенные НРК, отрицанию (НЕ) — НЗК, а также учитывая, что 1 (истинность) в электрических релейных схемах принято толковать как всегда замкнутый контакт, а 0 (ложность) — как разрыв (всегда разомкнутый контакт), можем получить следующие выражения и их релейную интерпретацию (рис. 9).

В заключение приведем два важных в алгебре логики тождества, получивших название законов Де Моргана:

1) отрицание дизъюнкции есть конъюнкция отрицаний.

2) отрицание конъюнкции есть дизъюнкция отрицаний.

С учетом свойства двойного отрицания (3), т. е. отрицая левую и правую части в выражениях (4) и (5), получаем.

Рис. 9. Релейная интерпретация логических операций: а — функции с разомкнутой перемычкой; б — функции с замкнутой перемычкой; в — функции с несколькими одноименными контактами; г — последовательное и параллельное соединение HP К и НЗК Последние выражения можно рассматривать как следствия, которые для релейных схем имеют следующее звучание:

• • параллельное соединение НРК противоположно последовательному соединению НЗК;
• • последовательное соединение НРК противоположно параллельному соединению НЗК.

В булевой алгебре важное место занимает принцип двойственности. Введем понятие двойственной функции, которая получается из исходной при взаимной замене символов 0 и 1 и операций дизъюнкции (ИЛИ) и конъюнкции (И). Пусть/= а + Ьс, тогда двойственная функция f= а (Ь + с), иными словами, если в общем виде/= (И, 0, 1,/, +, &), то двойственная ей функция /'= (И, 1, 0,/, &, +). Здесь Кесть совокупность переменных {*, …, х₂}.

Теперь можно сформулировать принцип двойственности: если имеет место тождество f (V) = q (Р), то двойственные функции тождественны — f (V) = q'(V). Например, дано тождество/= q

Справедлива тождественность для двойственных функций/= q'

Проверим сказанное, используя законы Де Моргана:

Сами законы Де Моргана подчиняются принципу двойственности:

Клод Шеннон обобщил законы Де Моргана и принцип двойственности в один закон инверсии (отрицания): при отрицании функции/все знаки сложения заменяются на знак умножения, и наоборот, при одновременной инверсии всех аргументов (для сохранения последовательности действий иногда приходится вводить скобки).

Пример. Дана функция / = a[b + а-. Найти ей обратную.

1) Преобразование по закону Де Моргана

Примечание: 1 + be = 1.

2) Преобразование по закону Шеннона.

где (р = 6 [а +Ь +с).

Следовательно, в соответствии с законом инверсии ср = b +^a be’j. Далее получаем