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

Например:x1 ∧ x2 ∧ x3 ∧ x4 ∧ x5Рангомконъюнкции(2.2)называетсячислодвоичныхпеременных,составляющих элементарную конъюнкцию.Например :x1 ∧ x2 ∧ x3 ∧ x4 ∧ x5 - это конъюнкция 5-го ранга, таккак составлена из произведения пяти переменных и их отрицаний.Конъюнктивно-нормальная форма (КНФ).Еслилогическаяфункциявыраженапосредствомлогическогопроизведения элементарных дизъюнкций, то считается, что оназадана своей КНФ.Y = ( A + B ) * ( C + D ) = ( A ∨ B ) ∧ (C + D )32(2.3)Элементарной дизъюнкцией n-го ранга называется логическая суммадвоичных переменных и их отрицаний, причём, каждая переменная всумме должна встречаться, только один раз. Например:x1 ∨ x2 ∨ x3 ∨ x4 ∨ x5Рангомдизъюнкцииназываетсячислодвоичныхпеременных,составляющих элементарную дизъюнкцию.Например:x1 ∨ x2 ∨ x3 ∨ x4 ∨ x5- это дизъюнкция 5-го ранга, таккак составлена из логической суммы пяти переменных и их отрицаний.Одна и та же логическая функция может быть представлена как своейДНФ так и КНФ, путём эквивалентных преобразований.Из множества этих нормальных форм функций выделяют однусовершеннуюдизъюнктивную(СДНФ)иоднусовершеннуюконъюнктивную (СКНФ) формы.Совершенная дизъюнктивно-нормальная форма логической функции от nдвоичных переменных называется такая ДНФ логической функции вкоторой:- все конъюнкции имеют один и тот же ранг;- нет двух одинаковых конъюнкций;- каждая конъюнкция содержит либо прямое, либо инверсное значениедвоичной переменной;- ни одна конъюнкция не содержит двух одинаковых двоичныхпеременных.Конъюнкции n-го ранга, составляющие СДНФ функции и обращающиефункцию в 1 при определённом наборе переменных получили названиеминтермы.Совершенная конъюнктивно-нормальная форма логической функции от nдвоичных переменных называется такая КНФ логической функции вкоторой:- все дизъюнкции имеют один и тот же ранг;33- каждая дизъюнкция содержит либо прямое, либо инверсное значениедвоичной переменной;- нет двух одинаковых дизъюнкций;- ни одна дизъюнкция не содержит двух одинаковых двоичныхпеременных.Дизъюнкции n-го ранга, составляющие СКНФ функции и обращающиефункцию в 0 при определённом наборе переменных получили названиеминтермы.Примеры СКНФ и СДНФ.СДНФ:Y = ( x1 * x2 * x3 ) + ( x1 * x2 * x3 ) + ( x1 * x2 * x3 )СКНФ:Y = ( x1 + x2 + x3 ) * ( x1 + x2 + x3 ) * ( x1 + x2 + x3 )Пример.

Табличное задание булевой функции приведено в табл. 2.1.Таблица 2.1. Таблица задания булевой функции.x3x2x1Y00001111001100110101010100010111Составивить булевые функции в СДНФ и СКНФ.Решение:СоставлениеСДНФпотабличномузаданиюбулевойфункциисформулировано в следующих правилах:соответствующиеминтермамэлементарныезнаками дизъюнкций,34конъюнкцииобъединитьвэлементарныхконъюнкцияхпеременная=1записываетсяпрямымзначением, а переменная=0, своим инверсным значением (с черточкой надименем переменной).Итоговая запись СДНФY = ( x3 * x2 * x1 ) ++( x3 * x2 * x3 ) ++( x3 * x2 * x1 ) + ( x3 * x2 * x1 )СоставлениеСКНФпотабличномузаданиюбулевойфункциисформулировано в следующих правилах:Соответствующиеминтермамэлементарныедизъюнкцииобъединитьзнаками конъюнкций,вэлементарныхдизъюнкцияхпеременная=0записываетсяпрямымзначением, а переменная=1, своим инверсным значением (с черточкой надименем переменной).Y = ( x3 + x2 + x1 ) **( x3 + x2 + x1 ) * ( x3 + x2 + x1 ) **( x3 + x2 + x1 )Минимизация булевых функций.Основная задача состоит в получении такой формы, которойсоответствует логическая функция с минимальным числом элементов.Различают несколько методов минимизации булевых функций.При эвристических методах преобразования логических функций,использующих законы алгебры логики.

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

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

Карты Карнопредоставляют наглядный способ отыскания таких термов.Как известно, булевы функции N переменных, представленные в видеСДНФ или СКНФ могут иметь в своём составе 2N различных термов. Всеэтичленысоставляютнекоторуюструктуру,топологическиэквивалентную N–мерному кубу, причём любые два терма, соединённыеребром, пригодны для склейки и поглощения.36Метод карт Карно.КартуКарноможнорассматриватькакграфическоепредставлениесовокупности всех наборов переменных для данного числа переменных.КартыКарнобылиизобретеныв1952ЭдвардомВ.Вейчемиусовершенствованы в 1953 Морисом Карно, физиком из «Bell Labs», и былипризваны помочь упростить цифровые электронные схемы.Каждый набор переменных изображается на карте в виде клетки.Таким образом, при n=3 карта имеет 8 клеток, а при n=6 – 64 клетки, рис.2.1и рис.2.2. соответственно.х1х200х3010111 10Рис.

2.1 Карта Карно для трёх переменных.х1х2х3000 001 011 010 110 111 101 100х4х5х5000001011010110111101100Рис.2.2. Карта Карно для шести переменных.37Карта Карно образуется путем такого расположения клеток, прикотором наборы переменных, находящиеся в соседних клетках, отличаютсязначением одной переменной. В картах Карно соседними считаются такжекрайние клетки каждого столбца или строки. Расположенные в них наборыпеременных отличаются значением одной переменной.Минтермы логической функции, т.е.

наборы двоичных переменных,прикоторых эта функция равна 1, отмечаются единицами всоответствующих клетках. Для наборов переменных не входящих влогическую функцию соответствующие им клетки остаются пустыми.Логическая функция, записанная в СДНФ или заданная в виде таблицыистинности, переносится на карту Карно. Затем карта покрываетсяконтурами. В контур может входить 2n рядом расположенных клеток,содержащих единичное значение логической функции, т.е. 2,4,8 и т.д. точек.Допускается пересечение контуров.Два минтерма, находящиеся в соседних клетках, т.е. в одном контуре,могут быть заменены одним логическим произведением, содержащим наодну переменную меньше.

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

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

В этом случае, наборыдвоичныхпеременных,прикоторыхлогическаяфункцияравна0(макстермы), отмечаются нулями в соответствующих клетках карты.Аналогично образуются контура, охватывающие клетки с макстермами,далее контура анализируются, и записывается минимальная КНФ (МКНФ)логической функции в виде логического произведения логических суммдвоичных переменных, в которых двоичные переменные, имеющие нулевоезначение, записываются без инверсии, а имеющие единичное значение синверсией.Крайние квадраты карты являются соседними при ее скручивании. Этозначит, что они тоже подлежат минимизации. На плоскости можноизобразить карту Карно для 4-х переменных. Для 5 и более переменныхнеобходимы объемные фигуры.Рис.

2.3. Скручивание карты Карно.39x3 x4k4k1x1 x2k1k3k1k1k2k4Рис. 2.4. Пример карты Карно для 4-х переменных.Итоги изучения главы 2.Помнить:- законы и теоремы алгебры логики, основные определения и термины.Понимать:- различия и особенности дизъюнктивных и конъюнктивных форм булевыхфункций.- особенности совершенных дизъюнктивных и конъюнктивных формбулевых функций.Применять:- законы и теоремы булевой алгебры логики с целью получения упрощённых(минимизированных) выражений.- методы минимизации булевых функций.Анализировать и оценивать:- возможность применения аппарата булевой алгебры в проектных решенияхпереключательных и комбинационных схем.402.3.

Контрольные вопросы.Вопросы категории 1. «Помнить»2.3.1. С помощью какого закона можно сделать преобразование булевойфункции из одного функционально-полного набора в другой?2.3.2. Какие два значения может принимать булева переменная?2.3.3. Какое число булевых переменных может входить в булеву функцию?2.3.4. Какие два значения может принимать булева функция?2.3.5.

Перечислите три функционально-полных набора логических функций.Вопросы категории 2. «Понимать»2.3.9.Сформулируйтеправила,характеризующиенормальнуюдизъюнктивную и нормальную конъюнктивную форму булевой функции.2.3.10Сформулируйтеправила,характеризующиесовершеннуюнормальную дизъюнктивную и совершенную нормальную конъюнктивнуюформу булевой функции.2.3.11 Какую информацию содержит таблица истинности булевой функции?2.3.7.Дайтеопределениепонятиямэлементарнаяконъюнкцияиэлементарная дизъюнкция.2.3.8.

Дайте определение терминам: ранг элементарной конъюнкции и рангэлементарной дизъюнкции.Вопросы категории 3. «Применять»2.3.6. Каким свойством обладает функционально полный набор логическихэлементов?2.3.12 Поясните термин «минтерм», применительно к функции, заданнойтаблицей истинности.Вопросы категории 4. «Анализировать и оценивать»2.3.13. Сформулируйте правиладизъюнктивной формы булевойзаписисовершенной нормальнойфункции, заданной табличным способом?412.3.14.