Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Лекции - Теория дискретных устройств - файл лекция3.doc


Лекции - Теория дискретных устройств
скачать (1179.2 kb.)

Доступные файлы (11):

Лекция10.doc522kb.17.11.2010 17:46скачать
Лекция11.doc1221kb.17.11.2010 17:49скачать
Лекция1.doc211kb.07.12.2010 15:54скачать
Лекция2.doc98kb.06.12.2010 21:27скачать
лекция3.doc120kb.06.12.2010 22:25скачать
лекция4.doc173kb.09.03.2011 17:18скачать
Лекция5.docx176kb.10.03.2011 16:09скачать
лекция6.doc82kb.07.12.2010 01:39скачать
Лекция7.doc81kb.18.11.2010 15:16скачать
Лекция8.doc133kb.18.11.2010 19:07скачать
Лекция9.doc141kb.01.12.2010 18:09скачать

лекция3.doc

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

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

Но только для алгебры логики действует закон двойственности (правило де Моргана):

; =.

Законы двойственности обобщены К. Шенноном для любых булевых функ­ций (ФАЛ):

.

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

Пример:



(*)

Заметим, что в первоначальную запись функции (*) можно значительно уп­ростить. Действительно, вынесем за скобки , тогда получим:





Использование этих законов позволяет упрощать исходную запись ФАЛ.

Вернемся к анализу ФАЛ, представленной в таблице 3.

В первой исходной записи ФАЛ, полученной по таблице 3, в каждом логиче­ском произведении переменных (конъюнкция) присутствовали все переменные из набора x1x2x3, а сами конъюнкции соединены символом логического сложения (дизъюнкции). Такая форма записи ФАЛ называется совершенной дизъюнктивной нормаль­ной формой (СДНФ).

^ Если не все переменные из набора x1x2x3 представлены в каждой из конъ­юнкций, то такая форма по прежнему остается нормальной дизъюнктивной фор­мой, но она не относится к классу совершенных.

^ ДНФ представления одной и той же ФАЛ может быть много, но совершенная ДНФ (СДНФ) одна единственная.

Кроме СДНФ существует так называемая конъюнктивная нормальная форма, которая также может быть совершенной (СКНФ) и не совершенной, т.е. просто КНФ.

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

^ Анализ СДНФ и СКНФ показывает неэкономичность записи ФАЛ. Исполь­зуя свойства ФАЛ можно преобразовать выражения за счет так называемой опе­рации склеивания, т.е.

, т.к. .

,

где a – любая ФАЛ.

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

Карта Карно представляет собой булево пространство в виде таблицы, в которой отображаются конституенты СДНФ.

Конституента – это набор перемен­ных, соединенных знаком конъюнкции (И).

Если функция при этом наборе пе­ремен­ных равна 1, то в клетку матрицы записывается 1. Черточками над клетками булева пространства помечаются строки и столбцы (по горизонтали и по вертикали), в которых обозначенная переменная примет значение 1.
Например представлена ФАЛ, для которой СДНФ имеет вид:

.

Составим таблицу для этого множества:

Таблица 11


В таблице 11 значение х1 = 1 распространяется на столбцы 2 и 3, считая справа налево, а значение х2 = 1 – на столбцы 1 и 2. Аналогично черточка

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

Для минимизации все клетки, содержащие 1, объединяются в замкнутые об­ласти с числом клеток 2, 4, 8… (в зависимости от числа переменных в ФАЛ). Области могут пересекаться, и одни и те же клетки могут входить в разные об­ласти. «Соседними» являются не только клетки, расположенные рядом по горизонтали и вертикали, но и клетки, находящиеся на противоположных гра­ницах карты. При охвате клеток замкнутыми областями следует стремиться к ми­нимальному числу областей.

Действительно, для верхней области, охватывающей две 1 при , видно, что значение x2 несущественно, т.к. ФАЛ равна 1 как при x2, так и при , но обе 1 в булевом пространстве при лежат в области x1. Аналогично для значения x3 не существенно значение x1, но обе 1 соответствуют x2.
^ Для табл. 11 получим:

.

Одним из вариантов карты Карно является представление кодирования бу­лева пространства кодом Грея, в котором при переходе от клетки к клетке как по вертикали, так и по горизонтали меняется значение только одной переменной.

Такое представление хорошо воспринимается визуально благодаря симмет­рии по осям. В данном случае это оси «0–0» и «1–1». Эта симметрия позволяет легче находить области склеивания конституент, для которых значения какой-либо переменной xi не влияет на значение ФАЛ. Речь идет о «ручной» минимизации с использованием визуального восприятия, что эффективно при n ≤ 6.

Для столь простого примера нельзя сделать четкий вывод в пользу того или иного способа кодирования булева пространства, но при числе переменных, рав­ном 4, 6 и более, преимущества кода Грея будут очевидны при визуальном методе минимизации ФАЛ.
Минимизация ФАЛ базируется на использовании свойств карт Карно. Наборы значений переменных для соседних клеток карты Карно отличаются лишь одной переменной.

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

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

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

- для каждой клетки, в которой функция имеет значение 1, записывается конъ­юнкция всех входных переменных (прямых или инверсных);

- составляется дизъюнкция этих конъюнкций, которая и представляет собой СДНФ данной функции.

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

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

  2. Площадь любого контура должна быть симметричной относительно гра­ниц пе­ременных, пересекаемых данным контуром. Другими словами, число кле­ток в контуре должно быть равно 1, 2, 4, 8, 16, 32, ….

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

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

  5. Каждой единичной клетке соответствует конъюнкция входных перемен­ных, оп­ределяющих данную клетку. Каждой нулевой клетке соответствует дизъ­юнкция инверсий входных переменных, определяющих данную клетку.

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

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

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


Рассмотрим пример ФАЛ для шести переменных (табл. 12).

Таблица 12


Все области «1», объединенные двойными линиями, представляют один интервал ФАЛ, для кото­рого по горизонтали очевидна независимость от x1 и x3, а по вертикали от x4 и x6, т.е. весь интервал соответствует . Верхняя область, объединенная сплошным овалом в одну линию по горизонтали, соответствует x2x3, а по вертикали , т.е. , а нижняя соответствует , тогда получим:

.

Последняя запись в скобках для х3 и х6 как уже говорилось называется функ­цией (обозначим Ζ) суммы по модулю 2 и обозначаются символом . Другое назва­ние функции Ζ – функция неравнозначности, т.к. она принимает значение 1 только при различных значениях переменных.

.

Заметим, что обратная ей функция имеет вид:



.

Эта функция называется функцией тождественности, т.к. она принимает зна­чение 1 только при одинаковых (тождественных «0» и «1») значениях перемен­ных

.

Тогда выражение для y можно записать в виде

.

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


* Примечание: В наиболее доступной форме методы минимизации б.ф. изложены в работах [1, 2, 37, 42, 52]. Этот вопрос глубоко исследован в работах [4, 6, 7, 11, 41]. В работе [47] предложен эффективный алгоритм минимизации б.ф. для большого числа переменных. Практические алгоритмы минимизации на базе специальных алгоритмических языков приведены в [6].




Скачать файл (1179.2 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации