Спиридонов С.Б. - Схемотехника дискретных устройств, страница 5

Сформулируйте правилаконъюнктивной формы булевойзаписисовершенной нормальнойфункции, заданной табличным способом?2.3.15 Какие цели достигаются при минимизации булевых функций?2.3.16.На каких подходах основаны эвристическийтабличный методминимизации булевых функций?Ответы на контрольные вопросы.2.3.1. Преобразование из одного функционально полного набора в другойвозможно выполнить используя закон Де Моргана и следствия из этогозакона.2.3.2.

Булева переменная может принимать значения либо 0 (ложь), либо1 (истина).2.3.3. В булеву функцию может входить любое конечное значениебулевых переменных.2.3.4. Булева функция может принимать значения либо 0 (ложь), либо 1(истина).2.3.5.

Элементарная конъюнкция это логическое произведение n-гоколичества булевых переменных, при условии, что переменная, либо еёинверсное значениевходит в это произведение только один раз.Элементарная дизъюнкцияэто логическая суммаn-го количествабулевых переменных, при условии, что переменная, либо её инверсноезначение входит в эту логическую сумму только один раз.2.3.6. Рангом элементарной конъюнкции называется количество булевыхпеременных,входящихвэлементарнуюконъюнкцию.Рангомэлементарной дизъюнкции называется количество переменных, входящихв элементарную дизъюнкцию.2.3.7.

Если логическая функция выражена посредством логической суммыэлементарныхконъюнкций, тосчитается, чтодизъюнктивно-нормальной формой (ДНФ).выраженапосредствомлогического42она задана своейЕсли логическая функцияпроизведенияэлементарныхдизъюнкций, то считается, что она задана своей конъюнктивнонормальной формой (КНФ).2.3.8.Совершеннаядизъюнктивно-нормальнаяформалогическойфункции от n двоичных переменных называется такая ДНФ логическойфункции, в которой:- все конъюнкции имеют один и тот же ранг,- нет двух одинаковых конъюнкций,- каждая конъюнкция содержит либо прямое, либо инверсноезначение двоичной переменной,- ни одна конъюнкция не содержит двух одинаковых двоичныхпеременных.43Глава 3.

Математический аппарат проектирования схем дискретныхустройств.3.1. Синтез комбинационных схем.Цифровые электронные схемы на логических элементах нашли оченьширокое применение в конструкции многих улов вычислительныхустройств, устройств автоматики и устройствах управления.синтезом схемы понимают её проектирование (разработку).ПодДанныеэлектронные схемы получили наименование комбинационных схем (КС).Функционированиекомбинационнойсхемыописываетсябулевойфункцией.Постоянные уровни напряжения, соответствующие принятому в схемепредставлению 0 и 1, могут рассматриваться как технические аналогифункции «ложь» и «истина».Существуют различные способы задания или представления булевыхфункций:1.

Словесное представление функций.Например: функция от трех аргументов принимает значение 1, если двалюбых аргумента или все три равны 1. Во всех других случаях функцияравна 0.Этим высказыванием значения выходной функции соответствующейсхемы полностью задано.2. Табличный способ.При этом способе функция представляется в виде таблицы истинности,в которой записываются все возможные наборы аргументов и для каждогонабора устанавливается значение функции 0 и 1.3.

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

Назначение входных и выходных переменных и присвоение значений 0и 1.2. Определение табличных значений поведения булевой функциисинтезируемой комбинационной схемы.3. Составление СДНФ (либо СКНФ) по минтермам табличной записибулевой функции.4. Упрощение, то есть минимизация СДНФ (или СКНФ) и получениеминимальной ДНФ (СКНФ).4. Переход от минимальной ДНФ (либо КНФ)к минимизированнойформе в каком-либо базисе функционально-полного набора.5.

Составление комбинационной схемы из логических элементов,входящих в указанный базис.Дизъюнктивнаянормальнаяформа(ДНФ)представляетсобойлогическую сумму элементарных логических произведений, в каждое изкоторых аргумент или его отрицание входят не более одного раза.Например:f ( x1 ,x2 ,x3 ) = x1 x 2 + x2 x3 + x1x2 x3(3.1)Если каждое слагаемое содержит все переменные или их отрицания, тов этом случае логическая функция представлена в совершенной дизъюнктивной нормальной форме (СДНФ).45Конъюнктивнаянормальнаяформа(КНФ)представляетсобойлогическое произведение элементарных логических сумм, в каждую изкоторых аргумент или его отрицание входят не более одного раза.Например:f ( x1 ,x2 ,x3 ) = ( x1 + x2 )( x2 + x3 )( x1 + x2 + x3 ) (3.2)Переход от таблицы истинности к СДНФ можно осуществитьследующим путем.

Для каждого набора, на котором функция равна единице,записывается произведение всех аргументов, причем, если аргумент в этомнаборе принимает значение "0", то пишется его отрицание. Затемпроизводится логическое сложение этих элементарных произведений.Для перехода от таблицы истинности к СКНФ логической функции, покаждому набору двоичных переменных, на котором функция принимаетзначение “0”, записывается дизъюнкция всех переменных, и полученныедизъюнкции логически перемножаются. При записи логических сумминвертируются те переменные, которые в таблице истинности имеютзначение единицы.Пример написания СДНФ и СКНФ логической функции. Пустьлогические функции у1 и у2 заданы в виде таблицы истинности, табл.3.1.Таблица.3.

1. Типовая таблица истинностих1х2х3у1у20000000111010010111110001101111100111110Тогда СДНФ и СКНФ логических функций у1 и у2 запишутсяследующим образом:46Y1СДНФ = x1x2 x3 + x1x2 x3 + x1x2 x3 + x1x2 x3(3.3)Y1СКНФ = ( x1 + x2 + x3 )( x1 + x 2 + x3 )( x1 + x2 + x3 )( x1 + x 2 + x3 ) (3.4)Y2СДНФ = x1 x 2 x3 + x1x2 x3 + x1x2 x3 + x1x2 x3(3.5)Y2СКНФ = ( x1 + x2 + x3 )( x1 + x 2 + x3 )(3.6)Комбинационные схемы, реализующие вышеприведенные СДНФ иСКНФ логических функций, должны содержать соответственно:У1сднф–четыре трехвходовые схемы И и одна четырехвходовая схемаИЛИ,У1скнф–четыре трехвходовые схемы ИЛИ и одна четырехвходовая схема«И»,У2сднф–шесть трехвходовых схем И и одна шестивходовая схема ИЛИ,У2скнф–две трехвходовые схемы ИЛИ и одна двухвходовая схема И.В качестве примера минимизации с помощью карт Карно взятылогические функции, приведенные в табл.3.2.Карта Карно для функции У1 приведена на рис.3.1.Рис.3.1. Карта Карно для функции У1Карта Карно для функции у2 приведена на рис.

3.2.47Рис. 3.2. Карта Карно для функции у2После минимизации с помощью карт Карно получаются следующиеминимальные дизъюнктивная и конъюнктивнаянормальные формылогических функций у1 и у2:y1днф = x3 + x1x2 ,(3..7)y1мкнф = ( x1 + x3 )( x2 + x3 ) ,(3.8)у2мднф=х1+х2+х3 ,(3.9)у2мкнф=х1+х2+х3.(3.10)При реализации логических функций на элементах Шеффера (И-НЕ)необходимо дважды проинвертировать МДНФ функций у1 и у2:y1шеф = x3 x1x 2 ,(3.11)y2шеф = x1 x 2 x3(3.12)Схемы реализации функций у1 и у2 на элементах Шеффера приведенына рис.3.3. и рис.3.4.48Рис.3.3 Реализация функции Y1X1&Y1X2X3Рис.3.4.

Реализация функции Y1Рассмотрим ещё один пример синтеза комбинационной схемы.Необходимо спроектировать схему, разрешающую движение лифта.Описание входных и выходных переменных:x1 - дверной контакт,при замкнутом контакте (дверь закрыта) x1при разомкнутом контакте= 1,x1 = 0 (дверь открыта).x2 - перегрузка, x2 = 1 - перегрузка, x2 = 0 - нет перегрузки,x3 - кнопка этажа, x3 = 1 -кнопка этажа нажата, x3 = 0 , кнопка этажа ненажата,Y-сигнал движения лифта:Y =1- лифт может двигаться,Y =0движение лифта блокируется.При трёх переменных таблица истинности должна иметь 8 различныхвариантов переменных. С учётом логики движения лифта составляемтаблицу истинности (табл.

3.2 .)49Таблица 3.2. Таблица истинности сигнала управления лифтом.Записываем СДНФ:х1х2х3у00000010010001101000101111001110Y = x1 * x2 * x3 ,этой функции соответствуеткомбинационная схема рис. 16.x1x2&1Yx3Рис. 3.5. Комбинационная схема безопасности пуска лифта.Если необходимо реализовать данную схему в другом базисе, например«ИЛИ-НЕ», то путём преобразований на основе теоремы Шеннона можнополучить другое выражение булевой функции:Y = x1 * x2 * x3 = x1 + x2 + x3(3.13)Комбинационная схема, соответствующая преобразованному выражениюпредставлена на рис. 3.6 .50x1≥1x2x3≥1Y≥1Рис. 3.6 .

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

Отключение должно происходить, когдасработали не менее двух датчиков из трёх. Аварийный датчик принимаетзначение «1» при срабатывании, отключение системы должно происходить,когда значение выходного сигнала управляющей схемыАварийным датчикам соответствуют булевы переменные x1 ,Y равно 1.x2 , x3 .Таблица истинности для синтеза схемы аварийного отключения (табл.3.3):51Таблица 3.3. Таблица истинности для синтеза схемы аварийногоотключения.х1х2х3у00000010010001111000101111011111СДНФ по таблице истинности имеет следующий вид:Y = x1 * x2 * x3 + x1 * x2 * x3 + x1 * x2 * x3 + x1 * x2 * x3(3.14)Проверим возможность минимизации полученной функции с помощью картКарно.