Схемотехника. Минимизация логических функций

Существует два направления минимизации:

• Ш Кратчайшая форма записи (цель - минимизировать ранг каждого терма);
• Ш Получение минимальной формы записи (цель - получение минимального числа символов для записи всей функции сразу).
• 1. Метод эквивалентных преобразований

В основе метода минимизации булевых функций эквивалентными преобразованиями лежит последовательное использование законов булевой алгебры. Метод эквивалентных преобразований целесообразно использовать лишь для простых функций и для количества логических переменных не более 4-х. При большем числе переменных и сложной функции вероятность ошибок при преобразовании возрастает.

2. Метод Квайна.

При минимизации по методу Квайна предполагается, что минимизируемая логическая функция задана в виде СДНФ. Здесь используется закон неполного склеивания. Минимизация проводится в два этапа: нахождение простых импликант, расстановка меток и определение существенных импликант.

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

Для этого:

• Ш Составляются таблицы, в строках которых пишутся найденные первичные импликанты, а в столбцах указываются термы первичной ФАЛ.
• Ш Клетки этой таблицы отмечаются в том случае, если первичная импликанта входит в состав какого-нибудь первичного терма.
• Ш Задача упрощения сводится к нахождению такого минимального количества импликант, которые покрывают все столбцы.

Алгоритм метода Квайна (шаги):

• 1. Нахождение первичных импликант (исходные термы из ДНФ записывают в столбик и склеиваю сверху вниз, непомеченные импликанты переходят в функции на этом шаге).
• 2. Расстановка меток избыточности (составляется таблица, в которой строки - первичные импликанты, столбцы - исходные термы, если некоторый min-терм содержит первичный импликант, то на пересечении строки и столбца ставим метку).
• 3. Нахождение существенных импликант (если в каком-либо столбце есть только одна метка, то первичный импликант соответствующей строки является существенным).
• 4. Строка, содержащая существенный импликант и соответствующие столбцы вычеркиваются (если в результате вычеркивания столбцов появятся строки первичных импликант, которые не содержат метки или содержат одинаковые метки в строках, то такие первичные импликанты вычеркиваются, а в последнем случае оставляется одна меньшего ранга).
• 5. Выбор минимального покрытия (из таблицы, полученной на шаге 3 выбирают такую совокупность первичных импликант, которая включает метки во всех столбцах по крайней мере по одной метке в каждом, при нескольких возможных вариантах отдается предпочтение покрытию с минимальным суммарным числом элементов в импликантах, образующих покрытие).
• 6. Результат записывается в виде функции.

Пусть задана функция:

Для удобства изложения пометим каждую конституенту единицы из СДНФ функции F каким-либо десятичным номером (произвольно). Выполняем склеивания. Конституента 1 склеивается только с конституентой 2 (по переменной х3) и с конституентой 3 (по переменной х2) конституента 2 с конституентой 4 и т. д. В результате получаем:

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

с появлением одного и того же элементарного произведения. Дальнейшие склеивания невозможны. Произведя поглощения (из полученной ДНФ вычеркиваем все поглощаемые элементарные произведения), получим сокращенную ДНФ:

Переходим к следующему этапу. Для получения минимальной ДНФ необходимо убрать из сокращенной ДНФ все лишние простые импликанты. Это делается с помощью специальной импликантной матрицы Квайна. Строки такой матрицы отмечаются простыми импликантами булевой функции, т. е. членами сокращенной ДНФ, а столбцы -- конституентами единицы, т. е. членами СДНФ булевой функции.

Импликантная матрица имеет вид см. табл. 1.1

Таблица 1.1 Импликантная матрица

Как уже отмечалось, простая импликанта поглощает некоторую конституенту единицы, если является ее собственной частью. Соответствующая клетка импликантной матрицы на пересечении строки (с рассматриваемой простой импликантой) и столбца (с конституентой единицы) отмечается крестиком (табл. 1.). Минимальные ДНФ строятся по импликантной матрице следующим образом:

• 1. ищутся столбцы импликантной матрицы, имеющие только один крестик. Соответствующие этим крестикам простые импликанты называются базисными и составляют так называемое ядро булевой функции. Ядро обязательно входит в минимальную ДНФ.
• 2. рассматриваются различные варианты выбора совокупности простых импликант, которые накроют крестиками остальные столбцы импликантной матрицы, и выбираются варианты с минимальным суммарным числом букв в такой совокупности импликант.

Следовательно функция имеет вид:

3. Метод Квайна-Мак-Класки.

Метод представляет собой формализованный на этапе нахождения простых импликант метод Квайна. Формализация производится следующим образом:

• 1. Все конституенты единицы из СДНФ булевой функции F записываются их двоичными номерами.
• 2. Все номера разбиваются на непересекающиеся группы. Признак образования і-й группы: і единиц в каждом двоичном номере конституенты единицы.
• 3. Склеивание производят только между номерами соседних групп. Склеиваемые номера отмечаются каким-либо знаком (зачеркиванием, звездочкой и т.д.).
• 4. Склеивания производят всевозможные, как и в методе Квайна. Неотмеченные после склеивания номера являются простыми импликантами.

Образуем группы двоичных номеров. Признаком образования і-й группы является і единиц в двоичном номере конституенты единицы (табл.1.2).

Таблица 1.2 Группы двоичных номеров

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

Таблица 1.4 Результаты склеивания 2

По табл. 5. определяем совокупность простых импликант - 0--1 и 111-, соответствующую минимальной ДНФ. Для восстановления буквенного вида простой импликанты достаточно выписать произведения тех переменных, которые соответствуют сохранившимся двоичным цифрам:

Разбиение конституент на группы позволяет уменьшить число попарных сравнений при склеивании.

4. Метод диаграмм Вейча.

Метод позволяет быстро получать минимальные ДНФ булевой функции f небольшого числа переменных. В основе метода лежит задание булевых функций диаграммами некоторого специального вида, получившими название диаграмм Вейча. Для булевой функции двух переменных диаграмма Вейча имеет вид (Рис 1).

Рис.1.

Каждая клетка диаграммы соответствует набору переменных булевой функции в ее таблице истинности. На (Рис 1) это соответствие показано, в клетке диаграммы Вейча ставится единица, если булева функция принимает единичное значение на соответствующем наборе. Нулевые значения булевой функции в диаграмме Вейча не ставятся. Для булевой функции трех переменных диаграмма Вейча имеет следующий вид (Рис 2).

Рис.2.

Добавление к ней еще такой же таблицы дает диаграмму для функции 4-х переменных (Рис 3).

Рис.3.

Таким же образом, т. е. приписыванием еще одной диаграммы 3-х переменных к только что рассмотренной, можно получить диаграмму для функции 5-ти переменных и т. д., однако диаграммы для функций с числом переменных больше 4-х используются редко.

5. Карты Карно.

Метод карт Карно - это один из графических методов минимизации функции. Эти методы основаны на использовании особенности зрительного восприятия, так как с его помощью можно практически мгновенно распознать те или иные простые конфигурации.

Построим таблицу метода карт Карно (табл. 1.6).

Таблица 1.6 Карты Карно

Теперь подсчитаем совокупность всех крестиков с метками минимальным количеством крестиков. Таких крестиков в нашем случае будет 5: три четырехклеточных и два двухклеточных. Этим крестикам соответствуют следующие простые импликанты:

для первого - X 3 X 4 ;

для второго - X 1 X 3 ;

для третьего - X 2 X 3 ;

для четвертого - X 1 X 2 X 4 ;

для пятого - X 1 X 2 X 4 ;

Минимальная ДНФ будет выглядеть так:

6. Метод неопределенных коэффициентов.

Этот метод может быть использован для любого числа аргументов. Но так как этот метод достаточно громоздок, то применяется только в тех случаях, когда число аргументов не более 5-6.

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

Построим матрицу неопределенных коэффициентов для четырех аргументов. В этом случае мы будем иметь систему из 16-ти уравнений.

Приравняем все коэффициенты 0 в тех строках, которым соответствует 0 в векторе столбце. Затем приравняем 0 соответствующие коэффициенты в других строках. После этих преобразований система примет следующий вид (Рис 4):

Рис.4.

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

Запишем теперь конъюнкции, соответствующие коэффициентам, равным единицам. Мы получим минимальную ДНФ.

Продолжительность: 2 часа (90 мин.)

14.1 Ключевые вопросы

14 Лекция №13. Минимизация логических функций 1

14.1 Ключевые вопросы 1

14.2 Текст лекции 1

14.2.1 Минимизация логических функций 1

14.2.1.1 Расчетный метод 1

14.2.1.2 Карты Карно 4

14.2.2 Минимизация систем логических уравнений 7

14.2.3 Минимизация частично определенных логических функций 8

14.2.4 Вопросы для контроля 10

14.2 Текст лекции

14.2.1 Минимизация логических функций

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

расчетный;

карт Карно.

14.2.1.1 Расчетный метод

Здесь применяют:

– склеивание,

– поглощение,

– развертывание.

Склеивание

а) Если в выражении встречается сумма двух конъюнкций, в одной из которых одна из переменных стоит в прямом значении, а в другой в инверсном значении, а остальные переменные одинаковые, то эту сумму конъюнкций, можно заменить одной конъюнкцией, не содержащей переменную, имеющую разные значения:

Конъюнкции, отличающиеся только значениями одной переменной (в одну из них переменная входит без отрицания, а в другую с отрицанием), называются соседними.

Замечание:
и дистрибутивном законе конъюнкции относительно дизъюнкции (см. Лекцию № 10)

.

б) Если в выражении встречается произведение двух дизъюнкций, в одной из которых одна из переменных стоит в прямом значении, а в другой в инверсном значении, а остальные переменные одинаковые, то это произведение дизъюнкций, можно заменить одной дизъюнкцией, не содержащей переменную, имеющую разные значения:

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

Замечание: Это правило основано на законе дополнительности

и дистрибутивном законе дизъюнкции относительно конъюнкции (см. Лекцию № 10)

в) Правила обобщенного склеивания.

В первом случае исчезло произведение bc , во втором исчезает суммаbc , в третьем снова произведениеbc (третий случай после раскрытия скобок сводится к первому). Доказываются эти правила, как обычно, составлением и сравнением таблиц истинности для левой и правой части или с помощью развертывания (см. ниже).

Поглощение

а) Если в выражении встречается сумма двух произведений, одно из которых является частью другого, то эту сумму можно заменить меньшим произведением:

б) Если в выражении встречается произведение двух сумм, одна из которых является частью другой, то это произведение сумм можно заменить меньшей суммой:

a (ab ) = a ; a (ab )(ac )…= a ; (ab )(abc )= ab .

Развертывание

Развертывание позволяет восстановить в формулах «потерянные» (например, в результате минимизации) переменные или перейти от ДНФ и КНФ к совершенным формам – СДНФ и СКНФ. Восстановление переменных для ДНФ и КНФ производится по–разному. Рассмотрим примеры.

Пусть имеем ДНФ

в которой, очевидно, потеряна переменная y . Для восстановления переменнойy произведение переменныхxz умножается на 1, затем 1 заменяется суммой прямого и инверсного обозначений недостающей переменной, и на основе дистрибутивного закона проводится преобразование

Пусть имеем КНФ
, где также потеряна переменнаяy . Для ее восстановления к сумме
добавляется 0, затем 0 заменяется произведением недостающей переменной на ее инверсию и применяется дистрибутивный закон

Используя развертывание, можно раскрыть смысл понятий «конституента единицы» и «конституента нуля».

Пусть n = 2 (переменныеa иb ).

Развернем единицу 1.

1= 1=
=.

Получили СДНФ функции двух переменных f = 1, где каждая конъюнкция является составляющей (конституентой) единицы.

Развернем 0.

Получили СКНФ функции двух переменных f = 0, где каждая дизъюнкция является составляющей (конституентой) нуля.

Полезность развертывания показывает пример доказательства правил обобщенного склеивания (см. п. 4.1.1):

Рассмотрим первое правило

Развернем левую часть тождества, в первом произведении которой недостает переменной c , во втором произведении недостаетb , а в третьем нетa .

После приведения подобных членов, применив простое склеивание

получаем правую часть, следовательно, тождество доказано.

Рассмотрим второе правило

Развернем левую часть тождества.

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

После приведения подобных членов, применив простое склеивание, будем иметь

Получили правую часть, следовательно, правило доказано.

Общий порядок проведения минимизации функции, заданной СДНФ, здесь следующий.

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

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

Полученная тупиковая форма случайно может оказаться минимальной. В общем случае для поиска минимальной формы необходим перебор тупиковых форм.

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

Пример 1: Минимизировать функцию

После применения операции склеивания и приведения подобных членов получаем

Обобщенное склеивание здесь можно проводить по нескольким вариантам, которые дают следующие результаты:

.

Исключены
,
,
: (
), (
), (
).

В скобках показаны термы, участвующие в обобщенном склеивании.

Исключены
,
,
: (
), (
), (
).

Как видим, здесь имеется две минимальных нормальных формы. По сложности они одинаковы.

Пример 2: Продолжая решение задачи по созданию устройства рис. 3, проведем минимизацию мажоритарной функции (см. табл. 12), для которой выше были получены СДНФ и СКНФ.

Здесь первую сумму мы поочередно рассматривали в паре со второй, третьей и четвертой суммами и после склеивания этих пар получили результат.

1.6. Использование множеств в языке Паскаль

2. Элементы общей алгебры

2.1. Операции на множествах

2.2. Группа подстановок Галуа

2.3. Алгебра множеств (алгебра Кантора)

2.4. Алгебраические системы. Решетки

2.5. Задание множеств конституентами

2.6. Решение уравнений в алгебре множеств.

3. Элементы комбинаторики

3.1. Комбинаторные вычисления

3.2. Основные понятия комбинаторики

3.3. Размещения

3.4. Перестановки

3.5. Сочетания

3.6. Треугольник Паскаля.

3.7. Бином Ньютона

3.8. Решение комбинаторных уравнений

4. Основные понятия теории графов

4.1. Способы задания графов

4.2. Характеристики графов

4.3. Понятие о задачах на графах

4.4. Задача о Ханойской башне

5. Переключательные функции и способы их задания

5.1. Понятие о переключательных функциях

5.2. Двоичные переключательные функции и способы их задания

5.3. Основные бинарные логические операции

5.4. Понятие о переключательных схемах и технической реализации переключательных функций

5.5. Использование логических операций в теории графов

6. Элементарные двоичные переключательные функции и функциональная полнота систем переключательных функций

6.1. Элементарные переключательные функции одной переменной

6.2. Элементарные переключательные (логические) функции двух переменных

6.3. Функциональная полнота систем переключательных функций

6.4. Базисы представления переключательных функций

6.5. Пример анализа и определения свойств пф, заданной десятичным номером

7. Основные законы булевой алгебры и преобразование переключательных функций

7.1. Основные законы булевой алгебры переключательных функций

7.2. Равносильные преобразования. Упрощение формул алгебры переключательных функций

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

8. Минимизация переключательных функций

8.1. Цель минимизации переключательных функций

8.2. Основные понятия и определения, используемые при минимизации

8.3. Аналитические методы минимизации переключательных функций

8.4. Минимизация переключательных функций по картам Карно

8.5. Метод поразрядного сравнения рабочих и запрещенных наборов

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

8.6. Минимизация переключательных функций, заданных в базисе {, и, не}

8.7. Минимизация систем переключательных функций

8.8. Минимизация переключательных функций методом неопределенных коэффициентов

9. Понятие об автомате и его математическом описании

9.1. Основные определения теории конечных автоматов

9.2. Описание конечных детерминированных автоматов

9.3. Понятие о технической интерпретации конечных автоматов

9.4. Синтез комбинационных автоматов в заданном базисе

9.5. Булева производная

9.6. Элементарные автоматы памяти на основе комбинационного автомата и задержки

9.7. Синтез автомата – распознавателя последовательности

10. Элементы теории кодирования

10.1. Понятие о кодировании

10.2. Системы счисления, как основа различных кодов

10.3. Понятие о помехоустойчивом кодировании

10.4. Кодирование по Хэммингу

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

10.6. Понятие о криптографической защите информации

10.7. Понятие о сжатии информации

8.3. Аналитические методы минимизации переключательных функций

Метод Квайна .

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

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

Пусть имеется переключательная функция, заданная СДНФ:

Разобьем конституенты на группы по числу неинверсированных переменных.

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

Полученные импликанты также допускают склеивание, причем в результате получается одна и та же импликанта
.

Дальнейшие склеивания невозможны, поэтому полученные импликанты – простые, а сокращенная ДНФ имеет вид:

Первый этап выполнен. На втором этапе необходимо исключить лишние простые импликанты. Это делается с помощью специальной импликантной таблицы Квайна (таблицы покрытий). Строки таблицы отмечаются простыми импликантами переключательной функции, т.е. членами сокращенной ДНФ, а столбцы – конституентами единицы, т.е. членами СДНФ переключательной функции.

Как уже отмечалось, простая импликанта поглощает некоторую конституенту единицы, если является ее собственной частью. Соответствующая клетка импликантной таблицы на пересечении строки данной простой импликанты и столбцов с конституентами единицы отмечается, например, знаком «+». Минимальные ДНФ строятся по импликантной таблице следующим образом:

1) ищутся столбцы импликантной таблицы, имеющие только один крестик, соответствующие этим крестикам простые импликанты называются базисными и составляют так называемое ядро переключательной функции. Ядро обязательно входит в минимальную ДНФ;

2) рассматриваются различные варианты выбора совокупности простых импликант, которые накроют крестиками остальные столбцы импликантной матрицы, и выбираются варианты с минимальным суммарным числом букв.

Ядром нашей функции (табл. 35) являются импликанты
и х 1 х 2 х 3 , т.е. функция имеет единственную тупиковую и минимальную ДНФ:

Таблица 35

Импликантная таблица Квайна

		Конституенты 1 (члены СДНФ)
	импли-канты

Видно, что импликанта х 2 х 3 х 4 является лишней, так как она покрывает конституенты, уже покрытые импликантами
, х 1 х 2 х 3 .

Число крестиков в строке является степенью числа 2; более того, можно убедиться, что оно равно N=2 n - k , где k – число букв в простой импликанте, n – число переменных, от которых зависит функция.

Если вначале не задана СДНФ, то ее надо получить, используя, например, уже известные нам методы.

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

Это означает, что тупиковая ДНФ содержит две простые импликанты (
и одновременно С=х 1 х 2 х 3) и имеет вид:

Метод Квайна-Мак-Класки.

Метод представляет собой формализацию метода Квайна, ориентированную на использование ЭВМ. Формализация заключается в записи конституент единицы (членов СДНФ) их двоичными номерами. Все номера разбиваются на непересекающиеся группы по числу единиц в двоичном номере. Склеивания производятся только между соседними группами. Ликвидируемый разряд обозначается знаком «–» («тире»). Дальнейшие группы из полученных импликант образуются с учетом однинакового расположения тире. Такое обозначение импликант называется обобщенными кодами. Пусть задана логическая функция

111101001000110.

Сгруппируем эти конституенты единицы по числу единиц:

Дальнейшие склеивания невозможны. Нахождение минимальных ДНФ далее производится по импликантной таблице (табл. 36):

Это означает, что тупиковые ДНФ содержат по три простые импликанты и имеют вид:

(две инверсии);

(три инверсии).

Таблица 36

Импликантная таблица Квайна-Мак-Класки

	импликанты			Конституенты единиц

Заметим, что склеивание двух импликант с тире возможно только при соответствующем их расположении, например:

Можно выбрать любую из полученных ТДНФ, а с учетом меньшего числа инверсий – первую.

Метод Блейка-Порецкого .

Метод позволяет получать сокращенную ДНФ булевой функции по ее произвольной ДНФ, а не по СДНФ, как в методах Квайна и Квайна-Мак-Класки, используя закон обобщенного склеивания . В основу метода положено следующее утверждение: если в произвольной ДНФ булевой функции провести всевозможные операции, обратные обобщенному склеиванию, а затем выполнить все поглощения, то в результате получится сокращенная ДНФ функции.

Пусть задана ДНФ функции:

Видно, что к первой и второй конъюнкциям можно применить закон обобщенного склеивания по переменной х 1 ; получим:

Аналогично для первой и третьей конъюнкций:

т.е. все остается, как есть!

Вторая и третья конъюнкции допускают обобщенное склеивание по х 2:

Переходим к ДНФ:

После применения закона идемпотентности (повторения) и поглощения получаем:

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

Таблица 37

Импликантная таблица для иллюстрации метода Блейка-Порецкого

импликанты			Наборы функции и ее значения

Таким образом, рабочие (единичные) наборы можно покрыть тремя простыми импликантами, например,
,
,
. В ядро входят импликанты
,
. Тогда тупиковые ДНФ имеют вид:

(лучше по числу инверсий).

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

Комбинационные логические устройства - это устройства, у которых значения выходных сигналов зависят только от комбинации входных сигналов в данный момент времени.

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

При разработке логического устройства сначала формулируют словесное описание его алгоритма действия. Затем составляют удовлетворяющую этому описанию логическую функцию (абстрактный синтез) и далее разрабатывают структурную логическую схему устройства {структурный синтез).

В процессе абстрактного синтеза осуществляется переход от словесного описания ТП (его нормальный ход и аварийные ситуации) к составлению алгоритма функционирования в виде таблицы, циклограммы, графика и т.п. Циклограмма представляет собой ряд горизонтальных строк, равных числу входов и выходов логического устройства. Для составления логического алгоритма управления технологическим оборудованием необходимо иметь полную информацию о ТП каждой технологической операции и применяемом оборудовании. На этой стадии уточняют последовательность операций и необходимые временные задержки для всех режимов работы объекта управления, определяют параметры, подлежащие контролю и учету в ходе процесса; формулируют требования управляемого объекта к логическому устройству. Эти требования представляют в виде значений двоичных сигналов, которые должны быть поданы на исполнительные устройства системы управления в зависимости от состояния управляемого объекта.

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

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

Исторически первыми устройствами, для описания действий которых использовали логические функции, были устройства, выполненные на релейно-контактных элементах. Для проектирования таких устройств была разработана теория релейно-контактных схем (ТРКС). Затем появились бесконтактные устройства, предназначенные только для логических преобразований сигналов и представляющие собой конструктивно оформленные изделия.

Устройства автоматики, действие которых описывается элементарными логическими функциями, обычно называют в соответствии с реализуемой ими логической операцией элементами НЕ, И, ИЛИ, И-НЕ, ИЛИ-HE (см. табл. 4.1).

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

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

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

Сочетательный закон. Результат последовательного сложения переменных или умножения их не зависит от порядка этих действий:

Закон поглощения. Сложение переменной с этой же переменной , умноженной на другую переменную , или умножение переменной на сумму этой же переменной и другой переменной равно первой переменной:

Распределительный закон. Общий множитель можно выносить за скобки , как в обычной алгебре:

Закон склеивания. Сумма произведений первой и второй переменных и второй переменной и инверсии первой переменной равна второй переменной. Произведение суммы двух переменных и суммы инверсии первой переменной со второй переменной равно второй переменной:

Закон инверсии (закон Моргана - Шеннона). Отрицание логического сложения равносильно произведению отрицаний слагаемых , и , наоборот , отрицание логического умножения равносильно сумме отрицаний сомножителей:

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

ных их инверсиями при одновременном изменении знака «плюс» на знак «умножение» и наоборот. Например, x t x 2 +x 3 x 4 =(x l x 2)(x 3 x 4) = (x l +х 2)(х 3 +х 4). Закон инверсии встречается только в алгебре логики.

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

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

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

Последнее тождество для минимизации получено путем двойной инверсии упрощаемого выражения. Первая инверсия дает

Вторая инверсия дает

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

и в базис И-НЕ (рис. 4.5, г):

Количество черточек сверху формул равно количеству элементов отрицания, т.е. элементов ИЛИ-HE и И-НЕ. В первой формуле шесть отрицаний, и соответственно схема на рис. 4.5, в содержит шесть элементов ИЛИ-HE. Во второй формуле пять отрицаний, и соответственно схема на рис. 4.5, г содержит пять элементов И-НЕ.

Рис . 45.

а - на релейных элементах; б - на элементах ИЛИ, И, НЕ; в - на элементах

ИЛИ-HE; г-на элементах И-НЕ

Пример 4.1

Упростите выражение/ = (х + у)(х + z) и начертите релейный эквивалент до упрощения и после него. Здесь/ - выходной сигнал (состояние замыкающего контакта) релейного элемента F.

Решение

Упростим заданное выражение в соответствии с законами алгебры логики: Учитывая, что х х = х, запишем

Учитывая, что 1 + у + z = 1, окончательно запишем /= х + у z. После упрощения релейный эквивалент выглядит следующим образом:

Упростите выражение f = х-у + х y-z +y-z и начертите релейный эквивалент до упрощения и после него.

Решение

До упрощения релейный эквивалент в соответствии с заданным выражением выглядит следующим образом:

Упростим заданное выражение в соответствии с законами алгебры логики, вынося общий множитель за скобки:

Релейно-контактная схема этого выражения примет вид

Здесь учтено, что x-z =x + z иа + а = 1, или x+z+x+z = 1, где a = x + z; а = x+z. Поэтому после преобразования упрощенное выражение примет вид

После упрощения выражения релейный эквивалент выглядит так:

Проверим правильность преобразования с помощью таблицы состояния (табл. 4.2), в которой показаны все возможные комбинации двух переменных х и 2, и убедимся, что выражение х + г + х-г всегда равно единице.

Таблица 4.2

Таблица состояния

		X + Z + X-Z

Рассмотрим пример применения алгебры логики для создания системы автоматического регулирования уровня воды в резервуаре Р (рис. 4.6). Исполнительный механизм ИМ осуществляет подачу воды в резервуар путем полного открытия или закрытия подающего вентиля А. В резервуаре имеются два датчика уровня воды: датчик верхнего уровня В и датчик нижнего уровня Н. Когда уровень воды достигнет или превысит положение датчика, сигнал его становится равным единице. Если уровень воды опустится ниже уровня датчика, сигнал на его выходе становится равным нулю.

Рис. 4.6.

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

Рис. 4.7.

на рис. 4.6

Условия работы, т.е. все комбинации входных сигналов и сигнала управления, переведены на язык алгебры логики и представлены на рис. 4.7 в верхней таблице в виде единиц и нулей. В таблице указано, при каких соотношениях входных сигналов имеется или отсутствует сигнал Q на выходе релейной САР. Сигнал на выходе является результатом логических операций над входными сигналами.

Если по данным таблицы мы попытаемся записать условия работы в виде логических функций, то обнаружим, что включенному сигналу управления соответствуют два различных соотношения входных сигналов. То же относится и к выключенному сигналу управления. Получается неоднозначность выходного сигнала в зависимости от сочетания входных сигналов. При В = 0 и Н = 1 есть положение, когда Q = 0 и есть положение, когда Q=l. Это значит, что в схеме должен быть элемент памяти, в качестве которого можно использовать уже знакомый нам RS-триггер Т. Для включения триггера используем появление нулевого сигнала на выходе 11 (II = 0). Этот сигнал инвертируется и подается на устанавливающий вход S триггера Т. Поскольку сигнал В не изменяется, то его не будем учитывать и запишем условие для включения S = Н. Условия для сброса триггера и снятия сигнала управления записываем как R = В.

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

Рассмотрим еще один пример применения алгебры логики для создания логических релейных защит электротехнических объектов на примере релейной защиты силового трансформатора, приведенной на рис. 4.8.

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

Рис. 4.8.

а - силовая схема; б - схема цепей защиты

Основной защитой трансформатора Т1 при коротком замыкании в трансформаторе (КЗ в точке К1) служит дифференциальная релейная защита (на схеме она не показана). Резервной защитой при коротком замыкании на отходящих шинах подстанции за выключателем Q2 (КЗ в точке К2) служит максимальная токовая защита, действующая при срабатывании токовых реле КЛ1-К АЗ. Короткое замыкание в трансформаторе Т1 должно отключаться выключателем Q1 от действия резервной защиты без выдержки времени, т.е. «мгновенно». Короткое замыкание в точке К2 должно без выдержки времени отключаться выключателем Q2 (защита выключателя Q2 на схеме не показана). Если по каким-либо причинам защита, воздействующая на выключатель Q2 или сам выключатель Q2, не сработает, то от резервной защиты с выдержкой времени должен отключиться выключатель Q1.

Рассмотрим, как можно повысить быстродействие рассматриваемой резервной защиты, если КЗ произошло в трансформаторе и основная защита не сработала. Для этого измерительные органы ставят на входе и выходе трансформатора Т1. Они выполняют функцию определения места КЗ: на защищаемом объекте или на участке внешней сети. При КЗ на защищаемом объекте (КЗ в основной зоне) они разрешают работу резервной защиты без выдержки времени, а при внешнем КЗ они блокируют цепь мгновенного отключения, и защита работает как резервная с выдержкой времени.

Определение места КЗ выполняется следующим образом. При КЗ в Т1 (точка К1) трансформаторы тока ТА 1-ТАЗ обтекаются током КЗ, и срабатывают реле тока КА1-КАЗ. Трансформаторы тока ТА4-ТА5 на выходе трансформатора Т1 не обтекаются током КЗ. Реле тока КА4 и КА5 не срабатывают, их размыкающие контакты замкнуты. В такой ситуации защита должна сработать без выдержки времени. Промежуточное реле KL подает сигнал на отключение выключателя Q1.

Условия работы промежуточного реле KL для отключения без выдержки времени словесно можно сформулировать так: реле KL сработает, если сработает реле КЛ1, ИЛИ сработает реле КА2 ИЛИ, сработает реле КАЗ И НЕ сработают реле КА4 И реле КА5.

В символах математической логики условие срабатывания реле KL записывается так:

При КЗ на участке внешней сети (точка К2) трансформаторы тока ТА4 и ТА5 обтекаются током КЗ, что приводит к срабатыванию реле тока КА4 и КА5 и размыканию их размыкающих контактов в цепи релейной защиты без выдержки времени. Таким образом, работа защиты без выдержки времени блокируется. Резервная защита при КЗ в точке К2 работает с выдержкой времени.

Условие срабатывания реле времени резервной защиты формулируется словесно так: реле времени КТ сработает, если сработает реле КА1, ИЛИ сработает реле КА2, ИЛИ сработает реле КАЗ.

В символах математической логики условие срабатывания реле времени записывается как

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

Схема на рис. 4.8, б построена в соответствии с уравнениями (4.13) и (4.14). Срабатывание защиты без выдержки времени (логической защиты) фиксируется указательным реле КН1. Срабатывание защиты с выдержкой времени фиксируется указательным реле КН2.

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

Зачем это нужно?

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

К тому же процесс упрощения булевых выражений не является алгоритмическим. Поэтому более целесообразно использовать специальные алгоритмические методы минимизации, позволяющие проводить упрощение функции более просто, быстро и безошибочно. К таким методам относятся, например, метод Квайна, метод карт Карно, метод испытания импликант, метод импликантных матриц, метод Квайна-Мак-Класки и др. Эти методы наиболее пригодны для обычной практики, особенно минимизация логической функции с использованием карт Карно. Метод карт Карно сохраняет наглядность при числе переменных не более шести. В тех случаях, когда число аргументов больше шести, обычно используют метод Квайна-Мак-Класки.

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

Минимизация логических функций при помощи карт Карно

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

Карты Карно были изобретены в 1952 Эдвардом В. Вейчем и усовершенствованы в 1953 Морисом Карно, физиком из «Bell Labs», и были призваны помочь упростить цифровые электронные схемы.

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

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

Возможность поглощения следует из очевидных равенств

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

Как известно, булевы функции N переменных, представленные в виде СДНФ или СКНФ могут иметь в своём составе 2N различных термов. Все эти члены составляют некоторую структуру, топологически эквивалентную N–мерному кубу, причём любые два терма, соединённые ребром, пригодны для склейки и поглощения.

На рисунке изображена простая таблица истинности для функции из двух переменных, соответствующий этой таблице 2-мерный куб (квадрат), а также 2-мерный куб с обозначением членов СДНФ и эквивалентная таблица для группировки термов:

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

Как видно из рисунка, для трёхмерного случая возможны более сложные конфигурации термов. Например, четыре терма, принадлежащие одной грани куба, объединяются в один терм с поглощением двух переменных:

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

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

Аналогичным образом можно работать с функциями четырёх, пяти и более переменных. Примеры таблиц для N=4 и N=5 приведены на рисунке. Для этих таблиц следует помнить, что соседними являются клетки, находящиеся в соответственных клетках крайних столбцов и соответственных клетках верхней и нижней строки. Для таблиц 5 и более переменных нужно учитывать также, что квадраты 4х4 виртуально находятся друг над другом в третьем измерении, поэтому соответственные клетки двух соседних квадратов 4х4 являются сосоедними, и соответствующие им термы можно склеивать.

Карта Карно может быть составлена для любого количества переменных, однако удобно работать при количестве переменных не более пяти. По сути Карта Карно - это таблица истинности составленная в 2-х мерном виде. Благодаря использованию кода Грея в ней верхняя строка является соседней с нижней, а правый столбец соседний с левым, т.о. вся Карта Карно сворачивается в фигуру тор (бублик). На пересечении строки и столбца проставляется соответствующее значение из таблицы истинности. После того как Карта заполнена, можно приступать к минимизации.

Если необходимо получить минимальную ДНФ, то в Карте рассматриваем только те клетки которые содержат единицы, если нужна КНФ, то рассматриваем те клетки которые содержат нули. Сама минимизация производится по следующим правилам (на примере ДНФ):

Далее берём первую область и смотрим какие переменные не меняются в пределах этой области, выписываем конъюнкцию этих переменных, если неменяющаяся переменная нулевая, проставляем над ней инверсию. Берём следующую область, выполняем то же самое что и для первой, и т. д. для всех областей. Конъюнкции областей объединяем дизъюнкцией.
Например(для Карт на 2-ве переменные):

Для КНФ всё то же самое, только рассматриваем клетки с нулями, не меняющиеся переменные в пределах одной области объединяем в дизъюнкции (инверсии проставляем над единичными переменными), а дизъюнкции областей объединяем в конъюнкцию. На этом минимизация считается законченной. Так для Карты Карно на рис.1 выражение в формате ДНФ будет иметь вид:

В формате КНФ: