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

XII Международная студенческая научная конференция Студенческий научный форум - 2020

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

Бадалов К.А. 1, Гданский Н.И. 1
1Московский государственный университет технологий и управления им. К.Г. Разумовского (Первый казачий университет)
 Комментарии
Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF

Введение

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

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

На рис.1. схематически показано конструкция такого релейного элемента, в котором есть оба типа контактов: х1 – НРК и х2 – НЗК. х1 моделирует тождественную функцию, х2 - отрицание.

Рис.1. Схема релейного элемента

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

В реальных РЭ обычно содержится несколько пар электрически не связанных между собой НРК и НЗК, в том числе, контакты одного типа.

В каждый момент времени текущее состояние РУ зависит только от состояния РЭ, входящих в них, а также от способа соединения между собой, со входами и выходами их контактов.

Рассмотрим логическое описание РС. Допустим, в ее состав входит n РЭ. Обозначим их: Х1, … , Хn. В таком виде каждому НЗК элемента Хi (1in) ставится в соответствие переменная хi, а каждому НЗК Хi - отрицаниехi. В силу того, что разные контакты, входящие в состав одного релейного устройства, принадлежащие к одному виду, входят в состав различных электрических цепей, то сигналы, проходящие по одним из них не связаны с сигналами, проходящими по другим. Если приписать проводимости в цепи символ некоторой переменной , то обычно полагают, что замкнутой цепи соответствует значение  = 1, а разомкнутой - значение  = 0.

В этом случае при использовании двоичного способа кодирования как для контактов релейных элементов, так и общей проводимости управляющей схемы  данная проводимость представляет собой булеву функцию, которая зависит только от своих переменных х1, ... , хn. Такую функцию называют функцией проводимости. У РС, в котором имеется один вход и один выход, функциональные свойства могут быть взаимно одинаково применены при помощи её функцией проводимости (х1, ... , хn).

Рассмотрим зависимость между физической структурой РС и формулой ее функции проводимости. Предварительно возьмем два основных способа соединения контактов РЭ, применяемых в РС – последовательный и параллельный.

Последовательного соединения двух контактов Х и Y сводится к тому что к окончанию первого мы присоединяем начало второго. Структура такого соединение показано на в рис.2. Такая структура соединения моделирует логическую функцию “умножение”.

Параллельное соединение контактов (рис.3) производится путем соединение входов и выходов обоев контактов. Оно моделирует логическое сложение «ИЛИ».

Рис.2 Рис.3

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

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

Конъюнкцией над множеством переменных Х=(х1,... ,хn) является произведение следующего вида: К= хi1i1 . . .  хisis, где (хi1 , ... , хis )  Х, хik ik= xik либоxik .

Дизъюнкцией над множеством переменных Х=(х1, ... ,хn)является сумма вида: D= хi1i1. . . хisis, где (хi1, ... , хis)  Х, хikik=xikлибоxik.

Дизъюнктивной нормальной формой (ДНФ) булевой функции f (х n) является формульное представление вида: f = К1 ... Кр , где К1 , ... , Кр - конъюнкции.

Конъюнктивной нормальной формой (КНФ) булевой функции f (х n)является формульное выражение вида: f=D1... Dр, где D1 ,..., Dр — дизъюнкции.

Если функция f(х n)имеет на набореn = (1, ..., n) единичное значение, то конъюнктивной конституентой единицы данной функциина набореn называют конъюнкцию вида К = х11 ... хnn, гдехi i= хiприi =1 ихi i =хiприi = 0(i=1,…,n). Совершенной дизъюнктивной нормальной формой (СДНФ) булевой функции f (х n)называют формулу вида: f = К1... Кр , где К1 , ... , Кр — все конъюнктивные конституенты единицы функции f (х n).

Допустим, на наборе значений перменныхn =(1, ... ,n ) убулевой функции f (х n)в секторе истинности стоит значение 0. Дизъюнктивной конституентой нуля функции f называют дизъюнкцию вида D = х11 ... хnn, гдехi i= хiприi =1 ихii = хiприi =0(1 i n).Совершенной конъюнктивной нормальной формой (СКНФ) булевой функции f (хn)является формульное выражение вида: f = D1 ... Dр, где D1, ... , Dр — дизъюнктивные конституенты нуля функции.

3. Минимизация нормальных форм

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

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

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

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

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

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

f (хn) = F((x111 ,..., xn1n) , ..., (x1k1,...,xnkn)).

В этой общей структуре:

-  (x1i1 ,..., xnin) — внутренняя функция формы, которая является конституентой нуля либо единицы функции (в зависимости от вида формы)для одного из наборов значений переменных функции хn, т.е. на нем она принимает вылеляемое значение истинности - нуль (единица), а на всех оставшихся наборах значений переменных— противоположное значение;

- F — внешняя функция, которая соединяет в одну формулу все конституенты функции.

Те наборы переменных (x1i1,...,xnin), которые входят во внутренние функции совершенных нормальных форм, называют элементарными наборами.

Полное множество элементарных наборов совершенной формы булевой функции обозначим через {N} = {N1, ... , Nk}, где k — общее число конституент — внутренних функций в совершенной форме.

Процесс минимизации совершенной формы заключается в параллельном сокращении:

а) чисел переменных, входящих во внутренние функции формы (x1i1 ,..., xnin),

б) чисел k самих внутренних функций формы (x1i1 ,..., xnin).

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

Простым набором значений булевой функции f (хn), называют такой набор переменных (x1i1,..., xnin), входящий во внутреннюю функцию ее нормальной формы, у которого при удалении из (x1i1 , ... , xnin) любой переменной x в новой получаемой функции (x1i1, ... ,xk-1i(к-1),xk+1i(к+1), ... ,xnin) изменяется вектор истинности, т.е. нарушается эквивалентность преобразования.

Полное множество простых наборов нормальной формы обозначим через {P} = {P1,...,Ps}, где s — количество таких наборов.

4. Метод покрытый минимизации нормальных форм

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

I. По таблице истинности заданной булевой функции построение совершенной нормальной формы Определение из нее совокупности элементарных наборов функции {N}={N1, ... , Nk}.

II. Построение сокращенной нормальной формы функции на основе построенной в п.I совершенной формы. Определение по ней совокупности всех простых наборов функции {P}={P1,...,Ps}.

III. Построение матрицы А покрытий элементарных наборов {N}={N1, ... , Nk} простыми наборами {P}={P1, ...,Ps}.

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

5. Основные виды задач для РС.
Критерий оптимальности РС и его связь с их формулами

Для РС, как и для других управляющих и производственных систем рассматривают 3 основных вида задач:

1) анализ, в котором по заданной РС выявляются ее свойства – обычно с использованием ее функции проводимости,

2) синтез, в котором по требуемым свойствам РС разрабатывается ее структура, при этом, как правило, используются методы алгебры логики, обычно общее решение является неединственным,

3) оптимизация – частный случай синтеза, в котором разрабатываемая РС должна быть оптимальной, т.е. лучшей по заданным критериям качества.

Как и у других управляющих схем, основным критерием качества РС является общее число контактов РЭ, которые входят в нее. Данное число должно быть минимальным, так как в этом случае будет максимальна ее надежность, и в то же время – минимальная себестоимость и энергопотребление.

Поскольку РС реализуют функции проводимости в базисе {,,&}, то практически решение всех трех задач производят с использованием дизъюнктивных и конъюнктивных нормальных форм.

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

x & y x & z = x &(y z); ( x y ) & ( x z) = x y & z.

Наряду с ними также для оптимизации используют правила поглощения: x( х y) = x ; xxy = x .

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

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

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

6. Синтез (проектирование) РС

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

1) выделение релейных элементов схемы и составление таблицы истинности для функции проводимости,

2) построение минимальной формулы, соответствующей определенной булевой функции (в классе нормальных форм, абсолютно оптимальной),

3) разработка физической структуры РС, которая соответствует найденной минимальной формуле.

Пример. Выполнить построениие двух вариантов РС, реализующих функцию проводимости  = (01001100): 1) оптимальной в классе нормальных форм и 2) абсолютно оптимальной

Решение.Из длины вектора истинности следует, что функция имеет 3 пееменных. Обозначим их (и, соотвественно, РЭ схемы) как x, y, z. Совершенная ДНФ такой функции будет следующей:

=xyzxyzxyz .

Применяя склеивание двух последних слагаемых, получим СкДНФ, которая будет и ее МДНФ:  =xy z хy. В нее входит 5 символов переменных. Соответсвующая ей принципиальная и физическая схемы РС даны на рис.4, 5.

Рис.4 Рис.5

Данная схема является оптимальной в классе нормальных форм. Применяя дистрибутивный закон к найденной МДНФ, сократим ее на 1 символ переменной и получим формулу: =y & (x z х ), которая содержит только 4 символа переменных. Поскольку больше формулу сократить невозможно, то получаемая по ней РС является абсолютно оптимальной. Ее принципиальная и физическая схемы даны на рис.6 а) и б).

а) б)

Рис.6

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

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

Заключение

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

Литература

Фридман А., Менон П. теория и проектирование переключательных схем. Пер. с англ. Под ред. В.А. Тафта. М. Мир 1978г. 582 с.

Афанасьев А.О., Кузнецова С.А. OrCAD 7.0…9.0. Проектирование электронной аппаратуры и печатных плат СПб Наука и техника 2001г. 464 с.

Иващенко Н. Автоматическое регулирование. Теория и элементы систем Для ВТУЗов Москва Машиностроение 1978г. 736 с.

Клюев А.С. Автоматическое регулирование. Учебник техникумов. М. Высшая школа 1986г. 351 с.

Гданский Н.И. Прикладная дискретная математика. Логика. Графы. Алгоритмы. Кодирование. Уч. пособие М., Вузовская книга, 2011. 508 с.

Просмотров работы: 5