Преобразование таблиц истинности в логические выражения[1]
При проектировании цифровых схем разработчик зачастую начинает с таблицы истинности, описывающей, что схема должна делать.
Задача проектирования, в основном, состоит в том, чтобы определить, какой тип схемы будет выполнять функцию, описанную в таблице истинности.
В то время как есть уникумы, кажется, обладающие (сверх)естественной способностью окинуть взглядом таблицу истинности и сразу же определить необходимые логические схемы или схемы релейной логики для решения задачи, для остальных простых смертных доступны процедурные методы, позволяющие поэтапно выполнить эту задачу.
Здесь булева алгебра самым ярким образом доказывает свою полезность.
Чтобы проиллюстрировать этот процедурный метод, спроектируем схему для решения реального проекта.
Предположим, нам дали задание разработать схему обнаружения пламени в установке для сжигания токсичных отходов.
Сильный жар огня предназначен для утилизации токсичных отходов, подаваемых в мусоросжигательную печь.
Подобные методы сжигания обычно используются для нейтрализации медицинских отходов, которые могут быть заражены смертельными вирусами или бактериями:
Рис. 1. Сильный жар огня предназначен для нейтрализации токсичности отходов, попадающих в мусоросжигательную печь.
Пока в мусоросжигательной печи поддерживается пламя, можно безопасно подкидывать в неё отходы для утилизации.
Однако, если пламя погаснет, будет небезопасно продолжать подачу отходов в топку, поскольку они будут выходить из выхлопной трубы не нейтрализованными и представлять угрозу для здоровья любого, кто находится в непосредственной близости.
Что нам нужно в этой системе, так это надёжный способ обнаружения наличия пламени и возможность организовать подачу отходов только в том случае, если наличие пламени «подтверждается» системой.
Существует несколько различных технологий обнаружения пламени: оптическая (обнаружение света), тепловая (обнаружение высокой температуры) и электропроводность (обнаружение ионизированных частиц, из которых состоит низкотемпературная плазма, коей является пламя), каждая из которых имеет свои уникальные преимущества и недостатки.
Предположим, что из-за высокой степени опасности, связанной с потенциальным выходом не подвергшихся нейтрализации отходов из выхлопной трубы этого мусоросжигательного завода, было решено сделать систему обнаружения пламени избыточной (с несколькими датчиками), чтобы отказ любого измерителя приводил к блокировке выбросов токсинов через выхлопную трубу.
Каждый сенсорный датчик оснащён нормально разомкнутым контактом (разомкнут, если пламя отсутствует; замкнут, если пламя обнаружено), который будем использовать для активации входов логической системы:
Рис. 2. Избыточная система защиты с тремя сенсорными датчиками. Если хотя бы один датчик не обнаруживает пламя, запорный клапан блокирует поступление токсичных отходов в печь.
Наша задача сейчас - разработать схему логической системы для открытия запорного клапана тогда и только тогда, когда есть достаточное пламя, наличие которого подтверждено сенсорными датчиками.
Однако сначала мы должны определиться, каким должно быть логическое поведение этой системы управления.
Хотим ли мы, чтобы клапан открывался, если только один из трёх датчиков обнаруживает пламя? Вероятно, нет, потому что это противоречит цели наличия сразу нескольких датчиков.
Если какой-либо из датчиков выйдет из строя, он будет ложно указывать на наличие огня при его отсутствии, т.е. логическая система, основанная на принципе «любой из трёх датчиков, обнаруживший пламя», выдала бы такой же выходной сигнал, что и система, где пламени нет, но один из датчиком работает некорректно.
Гораздо лучшим решением было бы спроектировать систему так, чтобы клапан открывался тогда и только тогда, когда все три датчика одновременно обнаруживают достаточное пламя.
Таким образом, если любой датчик окажется неисправным и будет ложно показывать наличие пламени, он не сможет удерживать клапан в открытом положении; скорее, для возникновения этого опасной ситуации потребовалось бы, чтобы все три датчика одновременно вышли из строя – что крайне маловероятно.
Таким образом, наша таблица истинности будет выглядеть так:
Рис. 3. Выход будет «высоким» (и только в этом случае отходы будут поступать в печь) если все три датчика одновременно подтверждают наличие пламени.
Не составить труда понять, что эта функциональность может быть сгенерирована с помощью логического элемента И с тремя входами: выход схемы будет «высоким», тогда и только тогда, когда И вход A И вход B И вход C одновременно «высокие»:
Рис. 4. Выход данной вентильной схемы будет «высоким» тогда и только тогда, когда все входы (и A и B и C) имеют «высокий» уровень.
При использовании релейной схемы мы могли бы создать эту функцию И, подключив три контакта реле последовательно или просто подключив три контакта датчика последовательно, так что единственный способ подачи электроэнергии для открытия запорного клапана – это если все три датчика «видят» пламя:
Рис. 5. При использовании релейной схемы можно подключить три контакта реле последовательно, создавая логическую функцию И.
Электроэнергия будет направлена на открытие запорного клапана только в том случае, если все три датчика показывают наличие пламени.
Хотя такая стратегия проектирования обеспечивает максимальную безопасность, она делает систему очень восприимчивой к «обратным» отказам датчиков.
Предположим, что один из трёх датчиков вышел из строя таким образом, что он показывает отсутствие пламени, хотя на самом деле наличествует хорошее пламя в камере сгорания печи.
Этот единичный сбой приведёт к излишнему перекрытию запорного клапана, что приведёт к потере производственного времени и потере топлива (придётся лишний раз тратиться на розжиг огня, а не для уничтожения отходов).
Было бы неплохо настроить логическую систему так, чтобы допускался подобный вид сбоя без ненужного отключения системы, но при этом обеспечивалось бы контроль безопасности в случае, если какой-либо отдельный датчик выходит из строя «на высоком уровне» (постоянно показывая пламя, независимо от того, обнаружено ли оно).
Стратегия, которая удовлетворит обе потребности, будет представлять собой логику «минимум два датчика из трёх», при которой запорный клапан открыт, если по крайней мере два из трёх сенсорных датчика показывают достаточное пламя.
Таблица истинности для такой системы будет выглядеть так:
Рис. 6. Запорный клапан открыт, если два-три датчика фиксируют пламя.
Сумма произведений
Здесь далеко не всем очевидно какая логическая схема удовлетворяет данной таблице истинности.
Однако простой метод проектирования такой схемы можно найти в стандартной форме логического выражения, называемой как Сумма-Произведений или просто СуП (англ. SOP от Sum-Of-Products).
Как вы, возможно, догадались, логическое выражение Сумма-Произведений – это буквально набор логических величин, сложенных (суммированных) вместе, причём каждый член представляет собой мультипликативную комбинацию (произведение) логических переменных.
Примером выражения СуП может быть что-то вроде этого: «ABC + BC + DF», т.е. сумма произведений «ABC», «BC» и «DF».
Выражения Суммы-Произведений легко генерировать из таблиц истинности.
Всё, что нужно сделать, это проверить таблицу истинности на предмет любых строк, выходные данные в которых является «высокими» (равны 1), и написать логический член произведения, который равен значению 1 с учётом этих входных условий.
Например, четвёртая строке в таблице истинности для нашей логической системы соответствует условию «минимум два из трёх»: A = 0, B = 1 и C = 1. Тогда один из членов в нашей сумме произведений будет иметь вид A'BC, поскольку этот член принимает значение 1 тогда и только тогда, когда A = 0, B = 1 и C = 1:
Рис. 7. Четвёртая строка соответствует нужному условию и на её основе формируем один из членов Суммы-Произведений (с учётом входных значений, при которых этот член принимает «высокое» значение).
В таблице истинности есть ещё три другие строки, имеющие на выходе значение 1, эти строки также используются, чтобы составить логические выражения для произведений:
Рис. 8. Отметим все строки, используемых для формирования членов нашей Суммы-Произведений.
Наконец, складываем эти четыре логических выражения вместе, получая одно логическое выражение, описывающее таблицу истинности в целом:
Рис. 9. Складываем полученные члены, собственно, это и есть требуемая сумма произведений для данного случая.
Теперь, когда у нас есть логическое выражение СуП для функции таблицы истинности, мы можем легко спроектировать логический вентиль или логическую схему реле на основе этого выражения:
Рис. 10.1. Вентильная схема, спроектированная на основе полученной Суммы-Произведений.
Рис. 10.2. Релейная схема, спроектированная на основе полученной Суммы-Произведений.
К сожалению, обе схемы избыточно сложны и не помешало бы сделать их попроще.
Используя методы булевой алгебры, выражение можно значительно сократить:
В результате упрощения теперь можем создать гораздо более простую логическую схему, выполняющие ту же функцию (состоящую хоть из вентилей, хоть из электромеханических реле):
Рис. 12.1. Вентильная схема, спроектированная на основе упрощённой Суммы-Произведений.
Рис. 12.2. Релейная схема, спроектированная на основе упрощённой Суммы-Произведений.
Любой из этих контуров будет адекватно выполнять задачу по управлению запорным клапаном для установки сжигания отходов, открывающимся, если хотя бы два датчика из трёх обнаружат пламя.
Как минимум, это то, что нам нужно, чтобы иметь вполне безопасную установку для сжигания токсичных отходов.
Однако мы можем расширить функциональность системы, добавив к ней логическую схему, предназначенную для определения того, что не согласуется ли один из датчиков с двумя другими.
Если все три датчика работают правильно, они должны обнаруживать пламя с одинаковой точностью.
Таким образом, в идеале все они должны одновременно регистрировать «низкое» состояние (000: нет пламени) или все одновременно регистрировать «высокое» состояние (111: достаточное пламя).
Любая другая комбинация выходных сигналов (001, 010, 011, 100, 101 или 110) говорит о том, что датчики работают в разнобой и, следовательно, это может служить тревожным сигналом о возможном отказе одного (или даже двух) из них.
Если добавить схему для обнаружения любого из этих шести состояний «Рассогласованность датчиков», то выход этой схемы можно было использовать для активации тревоги.
Кто бы ни следил за мусоросжигательной установкой, ему придётся принять решение: либо продолжить работу с возможно неисправным датчиком (если будет один из этих входов: 011, 101 или 110), либо из соображений безопасности выключить мусоросжигательную установку до выяснения и устранения неполадок.
Кроме того, если установка выключена (нет пламени), при этом один или несколько датчиков по-прежнему показывают пламя (001, 010, или 100), это будет указывать на то, что существует определённые проблемы с одним из датчиков.
Первым шагом в разработке этой схемы обнаружения «рассогласованности датчиков» является написание таблицы истинности, описывающей её (схемы) поведение.
Поскольку у нас уже есть таблица истинности, описывающая выходные данные логической схемы «достаточного пламени», мы можем просто добавить в таблицу ещё один выходной столбец, чтобы представить вторую схему, и составить таблицу, представляющую всю логическую систему:
Рис. 13. К имеющемуся выходному столбцу для «достаточного пламени» («Пламя в норме») добавим выходной столбец для обнаружения «рассогласованности датчиков».
Само собой можно сгенерировать выражение Суммы-Произведений для этого нового столбца из таблицы истинности. Учитывая, что в столбце шесть единиц на выходе – в итоге будет шесть членов по три переменных в каждом!
Такое логическое выражение потребует немало шагов для упрощения, при этом велика вероятность допустить ошибки при алгебраических преобразованиях:
Рис. 14. Если для нового столбца сформировать сумму произведений, то упростить логическое выражение с шестью членами будет непросто.
Произведение сумм
Есть альтернатива генерации выражения Суммы-Произведений для всех «высоких» (1) условий выхода в таблице истинности. И эта альтернатива – так называемое Произведение-Сумм, или ПрС (англ. POS от Product-of-Sums), учитывающее все «низкие» (0) состояния выхода.
Поскольку в последнем столбце таблицы истинности гораздо меньше случаев «низкого» выхода, результирующее выражение Произведение-Сумм будет содержать меньше составляющих.
Как следует из названия, выражение Произведение-Сумм – это набор складываемых членов (сумм), которые затем перемножаются вместе (получаем произведение этих сумм).
Примером ПрС-выражения может быть «(A + B) (C + D)», т.е. произведение сумм «A + B» и «C + D».
Для начала определяем, какие строки в последнем столбце таблицы истинности имеют «низкие» (0) выходы, и записываем логический член суммы, который будет равен 0 для входных условий этой строки.
Например, в первой строке таблицы истинности, где A = 0, B = 0 и C = 0, суммирующий член будет «(A + B + C)», поскольку он будет иметь значение 0, тогда и только тогда, когда A = 0, B = 0 и C = 0:
Рис. 15. Находим первую строку с выходом 0 в столбце «Рассогласованность датчиков» и формируем для него сумму с учётом входных величин.
Ещё есть только одна другая строка, в котором в последнем столбце таблицы истинности имеется «низкий» (0) выход, поэтому всё, что нужно, это составить ещё один суммирующий член для формирования нашего выражения Произведение-Сумм.
Этот последний суммирующий член даёт выход 0 для входного условия A = 1, B = 1 и C = 1.
Следовательно, этот член должен быть записан как «(A '+ B' + C ')», потому что только сумма дополнений к этим входным переменным равна 0:
Рис. 16. Ещё одна строка (последняя) даёт нам член для Произведения-Сумм, так как для неё выход в столбце «Рассогласованность датчиков» равен 0.
Завершённое выражение Произведение-Сумм, конечно же, представляет собой мультипликативную комбинацию этих двух сумм:
Рис. 17. Перемножаем члены полученные из обеих строк с выходом 0 для столбца «Рассогласованность датчиков».
В то время как выражение Сумма-Произведений реализуется в форме набора логических элементов И, выходы которых подключаются к единому элементу ИЛИ, выражение Произведение-Сумм реализуется как набор элементов ИЛИ, вводимых в единый элемент И:
Рис. 18. Вентильная схема на основе полученного Произведения-Сумм.
Соответственно, в то время как выражение Сумма-Произведений реализуется как параллельный набор последовательно соединённых контактов реле, выражение Произведение-Сумм реализуется как последовательный набор параллельно соединённых контактов реле:
Рис. 19. Релейная схема на основе полученного Произведения-Сумм.
Две предыдущие схемы (рисунки 18 и 19) – разные версии только логической схемы «Рассогласованность датчиков», а не схемы обнаружения «Пламя в норме».
Глобальная логическая система будет комбинацией цепей «Пламя в норме» и «Рассогласованность датчиков» в одной схеме.
Реализованная в программируемом логическом контроллере (ПЛК), вся логическая система может выглядеть примерно так:
Рис. 20. Полная схема («Пламя в норме» + «Рассогласованность датчиков») реализованная в ПЛК.
Как видите, стандартные логические формы Сумма-Произведений и Произведение-Сумм являются мощными инструментами для обработки таблиц истинности.
Они позволяют вывести общее логическое выражение – на основе которого, в конечном итоге, построить реальную логическую схему – не имея ничего, кроме таблицы истинности, которая суть письменная спецификация того, что мы хотим, чтобы логическая схема выполняла.
Возможность перейти от письменной спецификации к реальной схеме с использованием простых детерминированных процедур означает, что можно автоматизировать процесс проектирования цифровой схемы.
Другими словами, компьютер можно запрограммировать так, чтобы он спроектировал собственную логическую схему на основе спецификации таблицы истинности!
Шаги, которые нужно пройти от таблицы истинности до проектирования конечной схемы, настолько однозначны и прямолинейны, что для их выполнения не требуется (если вообще требуется) творчество или эвристики.
Итог
Сумма-Произведений, или просто СуП (англ. SOP от Sum-Of-Products), состоящее из складываемых логических выражений, может быть сгенерирована из таблиц истинности довольно легко, путем определения, какие строки таблицы имеют выход 1. Тогда нужно составить соответствующие произведения на основе этих строк и затем сложить эти произведения. Получим логическое выражение, представляющее таблицу истинности в целом.
Выражения Сумм-Произведений хорошо поддаются реализации в виде набора логических элементов И (произведения), выходы которых направляются в единый вентиль ИЛИ (сумма).
Произведение-Сумм, или просто ПрС (англ. POS от Product-Of-Sums), это логические выражения также легко генерируемые из таблиц истинности путём определения, какие строки таблицы имеют выход 0, записи единого суммирующего члена для каждой строки и, наконец, перемножения всех суммирующих членов. В результате будет логическое выражение, представляющее таблицу истинности в целом.
Логические выражения Произведения-Сумм хорошо подходят для реализации в виде набора логических элементов ИЛИ (суммы), выходы которых направляются в единый вентиль И (произведение).
