Наиболее употребляемая операция при минимизации функций - это операция склеивания.

AB+ ВB=B (A+ В)=B.

Рассмотрим три наиболее распространенных метода минимизации.

1. Пусть будут заданы номера наборов четырех переменных, на которых логическая функция принимает единичное значение: f (2,5,6,7,10,12,13,14)=1.

Выразим эту логическую функцию в СДНФ (символ конъюнкции писать не будем):

f (0010,0101, 0110, 0111, 1010, 1100, 1101, 1110) =

На первом этапе минимизации исходную СДНФ можно упростить за счет использования закона склеивания, тогда получим:

Обращаем внимание на то, что одну и ту же конституенту (импликанту) можно склеивать с другими конституентами (импликантами) многократно, так как в логике Буля действует закон идемпотентности:

поэтому любую конституенту можно размножить.

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

Таблица 8

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

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

2. Не менее эффективным способом минимизации логических функций является метод сочетания индексов. Для его изложения составим табл. 9, в графах которой записаны возможные сочетания индексов. В последней графе выписаны значения функции. Анализ таблицы начинается слева по столбцам. Принцип исключения i, j_кода следующий. На пересечении i_столбца, например, с сочетанием индексов 23, и j_строки, например, 3_ей, находится код 10, что соответствует импликанте. Следовательно, в этом столбце везде, где встречается код 10, т. е. в строках 2, 3, 10 и 11, эти коды исключаются, поскольку значение функции в 3_ей строке равно нулю. Теперь возьмем столбец с сочетанием индексов 124. Здесь во 2_ой и 6_ой строках оставлены коды 010, а в 10_ой и 14_ой строках - код 011. Сделано это потому, что эти коды встречаются только на строках со значением функции, равным единице. Напротив, код 110 этого же столбца встречается как при единичных значениях функции, так и при нулевых.

Таблица 9

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

Далее руководствуются следующим правилом. Для того чтобы функция приняла значение, равное единице, достаточно того, чтобы только какая-нибудь одна импликанта на строке приняла единичное значение. Прежде всего, оставляем минимальную импликанту, которая перекрывает единицы в строках 2, 6, 10 и 14. Затем, естественно, обращаемся к 12_ой строке. Здесь оставляем единственный на строке код 011, что отвечает импликанте. Эта же импликанта ответственна за 13_ую строку, оканчивающуюся тоже единицей. Осталось рассмотреть 5_ую и 7_ую строки. Общей для них является импликанта: . Таким образом, тремя импликантами мы перекрыли все единичные значения функции, что совпадает с результатом, полученным на основе таблиц Куайна.

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

Таблица 10

Получили два слагаемых

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

Таблица 11

Таблица 12

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

Метод применим для функций от любого числа переменных, но мы рассмотрим его для функций от 3-х переменных.

Представим в виде ДНФ с неопределенными коэффициентамиk:

(**)

В этой ДНФ представлены все возможные элементарные коньюнкции, которые могут входить в функцию, а коэффициенты kмогут принимать значения 0 или 1. Значения коэффициентов нужно выбрать так, чтобы данная ДНФ была минимальной.

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

Если в каком-то из этих уравнений правая часть равна 0, то все слагаемые левой части тоже равны 0. Эти коэффициенты можно исключить из всех уравнений, правые части которых равны 1. В этих уравнениях значение 1 следует присвоить тому коэффициенту, который соответствует коньюнкции наименьшего ранга. Эти коэффициенты и определят МДНФ.

Пример

Составляем систему, используя выражение (**).

После исключения нулевых слагаемых получаем

Полагаем остальные коэффициенты считаем нулевыми. Получаем МДНФ:

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

Рассмотренный метод неопределенных коэффициентов эффективен, если число аргументов функции не больше, чем 5 – 6. Это связано с тем, что число уравнений равно 2 n . Более эффективным является выписывание не всех возможных конъюнкций для функции, а только тех, которые могут присутствовать в ДНФ данной функции. На этом основан метод Квайна. При этом предполагается, что функция задана в виде СДНФ. В данном методе элементарные конъюнкции рангаn, входящие в ДНф, называются минитермами рангаn. Метод Квайна состоит из последовательного выполнения следующих этапов.

1. Нахождение первичных импликант

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

Склеиваем минитермы 4-го ранга и помечаем склеивающиеся минитермы звездочками

Образуем минитермы 2-го ранга:

Первичными (простыми) импликантами являются:

2. Расстановка меток

Для данной функции Сокр. ДНФ имеет вид:

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

Продолжение примера

3. Нахождение существенных импликант

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

В рассматриваемом примере исключаем строку и столбцы.

В результате получаем таблицу

4. Вычеркивание лишних столбцов и строк

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

5. Выбор минимального покрытия максимальными интервалами

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

Продолжение примера

Минимальное покрытие таблицы образуют строки, соответствующие импликантам . Тогда МДНФ имеет вид:

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

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

Пример

Найдем МДНФ для функции:

Минитермы 4-го ранга по группам

Минитермы 3-го ранга

Минитермы 2-го ранга

Непомеченные минитермы или простые импликанты

Строим таблицу меток

Обе первичные импликанты существенны и определяют минимальное покрытие, т. е. МДНФ имеет вид.

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

3.3.1. Минимизация ФАЛ с помощью матрицы Карно

Матрица Карно представляет собой своеобразную таблицу истинности ФАЛ, которая разбита на клетки. Количество клеток матрицы равно 2 n , где n – число аргументов ФАЛ. Столбцы и строки матрицы обозначаются наборами аргументов. Каждая клетка матрицы соответствует конституэнте единицы ФАЛ (двоичному числу). Двоичное число клетки состоит из набора аргументов строки и столбца. Матрица Карно для ФАЛ, зависящей от двух аргументов, представлена в виде таблицы 3.3., от трех аргументов таблицей 3.4. и от четырех аргументов таблицей 3.5.

Таблица 3.3.

Таблица 3.5.

х 3 х 4 х 1 х 2
	0 0 0 0	0 0 0 1	0 0 1 1	0 0 1 0
	0 1 0 0	0 1 0 1	0 1 1 1	0 1 1 0
	1 1 0 0	1 1 0 1	1 1 1 1	1 1 1 0
	1 0 0 0	1 0 0 1	1 0 1 1	1 0 1 0

Клетки матриц (таблицы 3.3., 3.4. и 3.5.) пронумерованы десятичными эквивалентами двоичных чисел клеток. Рядом расположенные клетки матриц, как по горизонтали, так и по вертикали, содержат соседние двоичные числа. Кроме этого соседние двоичные числа находятся во всех столбцах верхней и нижней строк, так же как во всех строках крайних столбцов.

Процесс минимизации ФАЛ с помощью матрицы Карно основан на законе склеивания соседних двоичных чисел. Можно склеивать двоичные числа рядом расположенных клеток, но рекомендуется склеивать наборы аргументов, которыми обозначены строки и столбцы матриц. Рассмотрим склеивание двоичных чисел клеток первого столбца матрицы (табл. 3.5.).

Клетки 0 и 4, соответственно двоичные числа 0000 и 0100, результат склеивания 0-00.

Клетки 8 и 12, двоичные числа 1000 и 1100, результат 1-00. Полученные импликанты склеиваются между собой, т.к. тире стоит в одном и том же разряде и двоичные числа импликант являются соседними, окончательный результат - - 00.

Клетки 8 и 12

Таким образом, если склеиваются все двоичные числа одного столбца, то пропадают те разряды, которыми обозначены строки. Аналогично, если будут склеиваться все двоичные числа одной строки, например 4, 5, 7, 6, то пропадают все разряды, которыми обозначены столбцы, т.е. результат будет следующий 01- -.

Если будут склеиваться двоичные числа только двух любых клеток, то прочерк ставиться вместо того разряда двоичных чисел строки или столбца, который изменится при переходе клеток из одной строчки в другую (или из одного столбца в другой). Например, склеиваются числа клеток 5 и 13, получим результат -101, или клеток 7 и 6 результат 011-.

При склеивании двоичных чисел восьми рядом расположенных клеток пропадает три переменные, например для клеток 3, 7, 15, 11, 2, 6, 14, 10 пропадают переменные х 1 , х 2 , х 3 . Переменные х 1 , х 2 пропадают потому, что склеиваются все клетки столбцов, а х 3 потому, что последние два столбца склеиваются между собой.

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

Известно, что для каждой ФАЛ имеет место количество наборов аргументов 2 n , где n – число аргументов от которых зависит функция или логическое выражение.

Наборы аргументов делятся на три вида

1. Наборы аргументов, на которых функция равна единице, называются рабочими.

2. Наборы аргументов, на которых функция равна нулю, называются запрещенными.

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

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

где – десятичные эквиваленты рабочих наборов,

– десятичные эквиваленты запрещенных наборов.

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

Пример 3.3. Минимизировать заданную ФАЛ в виде СДНФ с помощью матрицы Карно .

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

Таблица 3.5.

х 2 х 3 х 1
	0

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

Пример 3.4. Минимизировать логическое выражение, заданное рабочими и запрещенными наборами с помощью матрицы Карно.

Строим матрицу Карно на четыре переменных и заполним клетки единицами и нулями соответственно для рабочих и запрещенных наборов.

Таблица 3.6.

х 3 х 4 х 1 х 2	00
			(1)
	(1)		(1)

При объединении клеток с единицами в контуры желательно, чтобы в каждый контур включалось наибольшее число клеток из максимально возможного. Для этого клетки некоторых безразличных наборов используем как клетки рабочих наборов, подставив в них единицы в скобках. В результате получим три контура, содержащие по 4 клетки. В обобщенном коде контура, включающего в себя все клетки одной строки, пропадают переменные х 2 х 3 (10 - -). В обобщенном коде контура, включающего все клетки одного столбца пропадают переменные х 1 х 2 (- - 11) и для контура, содержащего по две клетки двух строк пропадают переменные х 2 (при переходе в контуре из одной строки в другую) и х 3 (при переходе из одного столбца в другой). В результате получим минимальную ДНФ в следующем виде

Возможные варианты объединения клеток матрицы Карно в контуры показаны на рисунке 3.4.

х 3 х 4 х 1 х 2

А = 0 - 0 -

З = - 0 - 0

Н

Б = 1 - 1 -

К = - - - 1

В = - - 0 0

Л = - 1 - -

Г = 1 0 - -

М = - - - 0

Д = - 0 0 1

Н = - 0 - -

Е = - 0 1 -

Ж = - 1 - 1

Рис. 3.1. Возможные варианты объединения клеток матрицы Карно в контуры

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

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

В матрице на пять переменных (таблица 3.7.) строкам соответствуют наборы переменных х 1 х 2 х 3 , а столбцам наборы переменных х 4 х 5 . Каждой клетке матрицы соответствует пятиразрядное двоичное число. В клетках матрицы (табл. 3.7.) проставлены десятичные эквиваленты соответствующих двоичных чисел.

Таблица 3.7.

х 4 х 5 х 1 х 2 х 3

Минимизация ФАЛ с помощью матрицы на пять переменных заключается в объединении клеток с рабочими наборами (включая при необходимости и клетки с безразличными наборами) в контуры и получении для этих контуров соответствующих им обобщенных кодов.

Особенность здесь заключается в том, что в столбцах матрицы на пять переменных объединять по четыре клетки в контуры можно только или четыре клетки сверху, или четыре клетки внизу, или четыре клетки посередине. Например, для последнего столбца матрицы контуры могут состоять из клеток 2, 6, 14, 10, или 26, 30, 22, 18 или 14, 10, 26, 30.

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

Строим матрицу на пять переменных и заполняем клетки рабочих наборов единицами, запрещенных – нулями.

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

Таблица 3.8.

х 4 х 5 х 1 х 2 х 3
	(1)	(1)	(1)
	(1)
	(1)	(1)
		(1)	(1)
	(1)		(1)
			(1)
	(1)		(1)

Получаем минимальную ДНФ

Контрольные вопросы

1. Дать определение сокращенной ДНФ.

2. Что представляет собой тупиковая ДНФ?

3. Как выбирается минимальная ДНФ из тупиковых ДНФ?

4. Для чего используется импликантная таблица и как она строится?

5. Пояснить аналитический способ минимизации ФАЛ Квайна-Мак-Класски.

6. Как строится матрица Карно на три и четыре переменных?

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

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

Похожая информация.

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

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

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

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

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

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

Однако прежде чем приступить к разработке схемы, необходимо попытаться преобразовать исходную логическую функцию к максимально простому виду. На основе структурной схемы логического устройства разрабатывают его принципиальную схему с использованием конкретной элементной базы, например в базисе ИЛИ-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 выражение в формате ДНФ будет иметь вид:

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