Методы минимизации функций алгебры логики. Минимизация логических функций
Работа по теме
МЕТОДЫ МИНИМИЗАЦИИ
ЛОГИЧЕСКИХ ФУНКЦИЙ
Ключевые понятия: логические выражения, логические функции, методы минимизации, инверсия, конъюнкция, дизъюнкция, импликация, эквиваленция.
Содержание
Введение
Люди, далекие от техники, часто смотрят на ЭВМ и другие цифровые электронные устройства как на нечто таинственное и непостижимое. Тем не менее, все эти устройства работают в строгом соответствии с четкими логическими законами. Знание и понимание этих законов помогает в общении с компьютером и другими цифровыми устройствами.
Принципы построения схемы цифрового устройства задается логическими функциями. Сложность логической функции, а отсюда сложность и стоимость реализующей ее схемы (цепи), пропорциональны числу логических операций и числу вхождений переменных или их отрицаний. В принципе любая логическая функция может быть упрощена непосредственно с помощью аксиом и теорем логики, но, как правило, такие преобразования требуют громоздких выкладок .
К тому же процесс упрощения булевых выражений не является алгоритмическим. Поэтому более целесообразно использовать специальные алгоритмические методы минимизации, позволяющие проводить упрощение функции более просто, быстро и безошибочно.
Упрощенная функция будет содержать меньше операций и комбинаций аргументов, а значит и схема, реализующая функцию, будет содержать меньше элементов, т.е. будет дешевле и надежнее .
В связи с этим минимизация логических функций особенно актуальна.
Целью работы является изучение методов минимизации функций алгебры логики.
Объектом работы стал процесс минимизации логических функций.
Предмет исследования – методы минимизации логических функций и методика преподавания этой темы в профильных классах.
Задачи исследования:
изучить основные элементы математической логики;
исследовать методы минимизации логических функций;
подобрать задачи для самостоятельной работы;
решить описанными методами подобранные задачи.
Работа состоит из введения, двух разделов, заключения и списка использованной литературы.
Во введении обосновывается актуальность темы, определяется цель и задачи исследования.
В первом разделе рассматриваются логические основы функционирования ЭВМ.
Во втором разделе раскрываются методы минимизации логических функций, приводятся примеры решения задач описанными методами.
В заключении подводятся общие итоги исследования.
Логические основы функционирования ЭВМ
Элементы математической логики
Компьютеры – это автоматические устройства, принципы работы которых базируются на элементарных законах двоичной логики.
Вычислительные машины всех поколений состояли и состоят из логических элементов и элементов памяти, принимающих два значения (бита) 0 и 1. Вся обработка информации в ЭВМ всех ее логических блоков, логических схем и устройств опиралась и будет опираться на законы и принципы математической логики .
Логика (от древнегреческого logos, означающего «слово, мысль, понятие, рассуждение, закон») – это древнейшая наука, изучающая правильность суждений, рассуждений и доказательств.
Математическая логика – это математическая дисциплина, изучающая технику доказательств .
Основоположником математической логики является великий немецкий математик Готфрид Вильгельм Лейбниц (1646 – 1716 гг.). Он выдвинул идею о применении в логике математической символики и построении логических исчислений, поставил задачу логического обоснования математики, сыграл важную роль в истории создания электронно-вычислительных машин: предложил использовать для целей вычислительной математики бинарную систему счисления. На заложенном Лейбницем фундаменте ирландский математик Джордж Буль построил здание новой науки – математической логики, – которая в отличие от обычной алгебры оперирует не числами, а высказываниями. В честь Д.Буля логические переменные в языке программирования «Паскаль» впоследствии назвали булевскими.
Математическая логика изучает вопросы применения математических методов для решения логических задач и построения логических схем, которые лежат в основе работы любого компьютера. Суждения в математической логике называют высказываниями или логическими выражениями.
Высказывание – это любое утверждение, относительно которого можно сказать истинно оно или ложно, т.е. соответствует оно действительности или нет; это символическая запись, состоящая из логических величин (констант или переменных), объединенных логическими операциями (связками) .
Различные логические выражения (высказывания) могут принимать только два значения: «истинно» или «ложно». Каждая логическая переменная может принимать только одно значение. Существуют разные варианты обозначения истинности и ложности:
Истина
И
True
T
1
Ложь
Л
False
F
0
Высказывания могут быть простыми и сложными. Простые соответствуют алгебраическим переменным, а сложные являются аналогом алгебраических функций. Функции могут получаться путем объединения переменных с помощью логических действий (операций) .
Рассмотрим логические операции, с помощью которых можно записать любое логическое выражение.
Самой простой логической операцией является операция НЕ (по-другому ее часто называют отрицанием, дополнением или инверсией и обозначают ). Результат отрицания всегда противоположен значению аргумента. Другими простыми слова, данная операция означает, что к исходному логическому выражению добавляется частица «не» или слова «неверно, что».
Таким образом, отрицанием некоторого высказывания называется такое высказывание, которое истинно, когда ложно, и ложно, когда истинно .
Логическая операция НЕ является унарной, т.е. имеет всего один операнд. Определение отрицания может быть записано с помощью так называемой таблицы истинности, в которой указано, указано, какие значения истинности (1, 0) принимает отрицание в зависимости от значений истинности исходного высказывания :
1
0
0
1
Логическое И (логическое умножение или конъюнкция) – это сложное логическое выражение, которое считается истинным в том и только том случае, когда оба простых выражения являются истинными, во всех остальных случаях данное сложное выражение ложно. Конъюнкцию высказываний и обозначают: , а иногда пишут просто . Высказывания в составе конъюнкции соединены союзом «и». Определение конъюнкции может быть записано в виде таблицы истинности, в которой для каждого из четырех возможных наборов значений исходных высказываний и задается соответствующее значение конъюнкции :
1
1
1
1
0
0
0
1
0
0
0
0
Определение конъюнкции двух высказываний естественным образом распространяется на любое конечное число составляющих: конъюнкция А 1 & A 2 & A 3 &...& A N истинна тогда и только тогда, когда истинны все высказывания А 1 , A 2 , A 3 , ...A N (а, следовательно, ложна, когда ложно хотя бы одно из этих высказываний) .
Логическое ИЛИ (логическое сложение или дизъюнкция) – это сложное логическое выражение, которое истинно, если хотя бы одно из простых логических выражений истинно и ложно тогда и только тогда, когда оба простых логических выражения ложны. Дизъюнкцию высказываний и мы обозначим символом и будем читать: или . Определение дизъюнкции может быть записано в виде таблицы истинности:
1
1
1
1
0
1
0
1
1
0
0
0
Определение дизъюнкции двух высказываний естественным образом распространяется на любое конечное число составляющих: дизъюнкция А 1 А 2 А 3 ... А N истинна тогда и только тогда, когда истинно хотя бы одно из высказываний А 1 , А 2 , А 3 , ..., А N (а следовательно, ложна, когда ложны все эти высказывания).
Операции И, ИЛИ, НЕ образуют полную систему логических операций, из которой можно построить сколь угодно сложное логическое выражение. Но помимо них существуют и другие логические операции.
Логическое следование (импликация) – это сложное логическое выражение, которое истинно во всех случаях, кроме как из истины следует ложь. То есть данная логическая операция связывает два простых логических выражения, из которых первое является условием ( ), а второе ( ) является следствием. Обозначим импликацию символом и запись « » будем читать: «Из следует ».
Запишем это определение в виде таблицы истинности:
1
1
1
1
0
0
0
1
1
0
0
1
Высказывание «Если , то » с логической точки зрения имеет тот же смысл, что и высказывание «неверно, что истинно и ложно». Это означает, что функцию импликации можно заменить комбинацией двух функций (отрицания и конъюнкции).
Логическое тождество (эквиваленция) – это сложное логическое выражение, которое является истинным тогда и только тогда, когда оба простых логических выражения имеют одинаковую истинность. Обозначают эквиваленцию символом и запись « » читают « эквивалентно », или « равносильно », или « , если и только если », « тогда и только тогда, если ». Определение эквиваленции может быть записано в виде таблицы истинности:
1
1
1
1
0
0
0
1
0
0
0
1
Логические функции и их преобразование
Логическая функция – это функция логических переменных, которая может принимать только два значения: 0 или 1. В свою очередь, сама логическая переменная (аргумент логической функции) тоже может принимать только два значения: 0 или 1 .
Каждая логическая функция может быть задана большим количеством различных по виду функций. Но даже любую достаточно сложную логическую функцию можно реализовать, имея относительно простой набор базовых логических операций. Наиболее известный базис – это набор функций «и», «или», «не».
Для операций конъюнкции, дизъюнкции и инверсии определены законы, позволяющие производить тождественные (равносильные) преобразования логических выражений :
;
.
Основываясь на законах, можно выполнять упрощение сложных логических выражений.
Исходными, из соображений удобства последующих преобразований, приняты следующие две канонические формы представления функций: совершенная дизъюнктивная нормальная форма (СДНФ) и совершенная конъюнктивная нормальная форма (СКНФ).
Прежде чем перейти к СДНФ и СКНФ введем некоторые понятия.
Элементарной конъюнкцией называется конъюнкция нескольких переменных, взятых с отрицанием или без отрицания, причём среди переменных могут быть одинаковые .
Элементарной дизъюнкцией называется дизъюнкция нескольких переменных, взятых с отрицанием или без отрицания, причём среди переменных могут быть одинаковые .
Всякую дизъюнкцию элементарных конъюнкций называют дизъюнктивной нормальной формой, то есть ДНФ .
Например, выражение является ДНФ.
Всякую конъюнкцию элементарных дизъюнкций называют конъюнктивной нормальной формой, то есть КНФ .
Например, выражение является КНФ.
Совершенной ДНФ (СДНФ) называется ДНФ, в которой нет равных элементарных конъюнкций, и все они содержат одни и те же переменные, причём каждую переменную только один раз (возможно с отрицанием) .
Например, выражение является ДНФ, но не является СДНФ; выражение является СДНФ.
Совершенной КНФ (СКНФ) называется КНФ, в которой нет равных элементарных дизъюнкций, и все они содержат одни и те же переменные, причём каждую переменную только один раз (возможно с отрицанием) .
Например, выражение .
Приведу алгоритмы переходов от одной формы к другой. Естественно, что в конкретных случаях (при определенном творческом подходе) применение алгоритмов бывает более трудоемким, чем простые преобразования, использующие конкретный вид данной формы :
переход от произвольного задания функции к ДНФ
Этот переход сводится к опусканию общих для нескольких переменных инверсий, раскрытию скобок и объединению, если они возникают, одинаковых членов с использованием законов:
Например:
переход от ДНФ к КНФ
Алгоритм этого перехода следующий: ставим над ДНФ два отрицания и с помощью правил де Моргана (не трогая верхнее отрицание) приводим отрицание ДНФ снова к ДНФ. При этом приходится раскрывать скобки с использованием правила поглощения. Отрицание (верхнее) полученной ДНФ (снова по правилу де Моргана) сразу дает нам КНФ:
Второй способ перехода от ДНФ к КНФ – использование дистрибутивного закона:
переход от КНФ к ДНФ
Этот переход осуществляется простым раскрытием скобок (при этом опять-таки используется правило поглощения):
переход от КНФ к СКНФ
Этот переход осуществляется способом, аналогичным предыдущему: если в простой дизъюнкции не хватает какой-то переменной, например, z , то добавляем в нее выражение (это не меняет самой дизъюнкции), после чего раскрываем скобки с использованием распределительного закона:
переход от ДНФ к СДНФ
Если в какой-то простой конъюнкции недостает переменной, например, z , то умножаем неполную конъюнкцию на выражение вида , после чего раскрываем скобки (при этом повторяющиеся дизъюнктные слагаемые не пишем). Например:
Для получения СДНФ и СКНФ из таблиц истинности необходимо выполнить следующие 4 пункта алгоритма :
СДНФ
СКНФ
Конструирование СДНФ и СКНФ начинается с таблицы истинности.
Отметим те строки таблицы, выходы которых равны
1
0
Выписываем для каждой отмеченной строки комбинацию переменных через знак
конъюнкция (&)
дизъюнкция (V)
Знаки операции отрицания расставляем следующим образом:
если переменная равна 1, то запишем саму эту переменную, если же она равна 0, то запишем ее отрицание.
если переменная равна 0, то запишем саму эту переменную, если же она равна 1, то запишем ее отрицание.
Все полученные выражения связываем операцией
дизъюнкции
конъюнкции
Получив СДНФ или СКНФ, можно составить электронную схему, реализующую данную логическую функцию. Для ее постороения требуется 3 логических элемента :
инвертор
конъюнктор
дизъюнктор
Но чаще всего СДНФ содержит много слагаемых и задача заключается в том, чтобы уменьшить их число и упростить логическое выражение. Для упрощения логических функций можно использовать законы логики, приведенные выше. С этой же целью были разработаны и специальные методы, речь о которых пойдет в следующем разделе.
Минимизация логических функций
Как отмечалось в предыдущей главе, логическая функция может быть представлена в виде таблицы истинности или в виде СДНФ (совершенной дизъюнктивной нормальной формы) или СКНФ (совершенной конъюнктивной нормальной формы) и может быть использована для получения логической схемы устройства. Однако полученная логическая схема, как правило, не будет оптимальна. Поэтому важным этапом синтеза логических схем является минимизация логических функций.
Минимизацией называется преобразование логических функций с целью упрощения их аналитического представления.
Существуют два направления минимизации:
Кратчайшая форма записи (при этом получаются кратчайшие формы КДНФ, ККНФ, КПНФ);
Получение минимальной формы записи (получение минимального числа символов для записи всей функции сразу).
Но следует учесть, что ни один из способов минимизации не универсален.
Для минимизации функций алгебры логики был разработан ряд методов:
метод непосредственных преобразований логических функций;
метод минимизации логических функций при помощи карт Карно;
метод Квайна-Мак-Класки;
метод Блейка-Порецкого;
метод Петрика и другие.
Остановимся более подробно на первых двух методах.
Метод непосредственных преобразований логических функций
Одним из простых методов минимизации является метод непосредственных преобразований, который осуществляется с использованием основных теорем алгебры логики .
При применении данного метода:
Записываются СДНФ логических функций,
Форма преобразуется и упрощается с использованием аксиом алгебры логики, при этом, в частности, выявляются в исходном СДНФ соседние термы (члены), в которых есть по одной не совпадающей переменной.
По отношению к соседним термам применяется закон склейки.
Термы, образованные при склеивании называются импликантами.
Полученные после склейки импликанты по возможности склеивают до тех пор, пока склеивание становится невозможным.
Полученная в результате минимизации функция называется тупиковой.
Пусть дана функция
Минимизируем ее описанным выше методом. Для этого добавим еще одно слагаемое и воспользуемся законами склеивания .
Получили минимальную функцию
Рассмотренный метод минимизации путем непосредственных преобразований достаточно прост, особенно при небольшом числе переменных. Недостатком метода является то, что он не указывает строго формализованный путь минимизации. При большом числе переменных минтермы могут группироваться по-разному, в результате чего можно получить различные упрощенные формы заданной функции. При этом нельзя быть уверенным в том, что какая-то из этих форм является минимальной. Возможно, что получена одна из тупиковых форм, которая больше не упрощается, не являясь при этом минимальной.
Метод минимизации логических функций при помощи карт Карно
Карта Карно или карта (диаграмма) Вейча – графический способ минимизации функций алгебры логики.
Карты Карно удобны при небольшом числе переменных.
Карты Карно представляют собой определенную таблицу истинности обычно для двух, трех и четырех переменных и отличаются друг от друга способом обозначения строк и столбцов таблиц истинности.
На рис. 1 представлены карты Вейча для двух, трех и четырех переменных соответственно .
рис. 1
Расположение групп переменных x не имеет значения, необходимо лишь, чтобы каждая клетка отличалась от любой соседней лишь на одну переменную. Согласно принятой форме построения карт соседними также считаются клетки первой и последней строк, клетки первого и последнего столбцов. Число клеток карты равно числу возможных комбинаций значений переменных (термов) и в каждую клетку записывается значение логической функции, соответствующее данному набору переменных. Если какая-то из возможных комбинаций присутствует в совершенной дизъюнктивной нормальной форме (СДНФ) записи функции, то в соответствующей клетке карты Карно ставится «1». Если какого-то терма в полученной функции нет, то в соответствующей клетке карты Карно ставится «0» .
Например, рассмотренная в предыдущем примере функция
заданная таблицей истинности (рис. 2 а), может быть минимизирована и с помощью карт Карно. Карта Карно для нее будет иметь вид, показанный на рис. 2 б.
рис. 2
В карте Карно логические 1 , записанные в соседних клетках, обозначают, что соответствующие этим 1 конъюнкции (произведения) отличаются лишь по одной переменной, которые дополняют друг друга и их можно опустить.
Так в первой строке карты Карно (см. рис. 2 б) переменная х , встречается в комбинации с х 1 и х 2 , которые дополняют друг друга:
Таким образом, группируя две соседние клетки в верхней строке (контур на рис. 2 б), можно исключить одну переменную – х 1 .
Аналогично, группируя две соседние клетки в левом столбце (контур на рис. 2 б) и исключая отличающиеся переменные, получим упрощенное выражение – х 2 .
Полученные упрощенные выражения объединяют с помощью операции ИЛИ.
Таким образом, соседние клетки карты Карно можно группировать для исключения переменной. Число группируемых клеток может быть и больше двух, но их число должно быть четным и они должны соприкасаться (являться соседними) друг с другом.
Допускается также иметь несколько групп перекрывающихся клеток, как в только что рассмотренном примере.
Группироваться могут также клетки первой и последней строк, первого и последнего столбцов, т. е. карту допускается сворачивать в цилиндр как по вертикальной, так и по горизонтальной оси.
Для исключения n переменных общее число группируемых клеток должно быть равно 2 n . Так, для исключения одной переменной требуется объединить две соседние клетки, а для исключения трех переменных уже требуется объединить восемь соседних клеток .
Таким образом, для того чтобы получить минимизированную логическую функцию, необходимо сгруппировать все соседние клетки карты Карно, содержащие 1, а затем объединить полученные группы с помощью операции ИЛИ. Клетки, содержащие 1, которые не удалось объединить с другими клетками, образуют в минимизированной логической функции самостоятельные члены, каждый из которых содержит все переменные .
Рассмотрим несколько примеров карт Вейча и способы построения контуров группировки соседних клеток для получения упрощенной логической функции.
Так, карта Вейча для логической функции
приведена на рисунке 3.
рис. 3
На этом рисунке показан правильный способ объединения соседних ячеек, т. е. карта Вейча как бы свернута в вертикально расположенный цилиндр.
Упрощенное выражение логической функции имеет вид
Таким образом, группируя соседние клетки в единый квадрат, удалось исключить две переменные (х 1 и х 2 ) и получить простое выражение для логической функции.
Рассмотрим пример минимизации логической функции
Карта Карно для этой функции представлена на рисунке 4:
рис. 4
Группируемые ячейки обведены двумя контурами. Нижний контур дает возможность исключить одну переменную х 3 и после этого в нем остается член .
В верхнем контуре можно исключить две переменные (х 2 и х 4 ) и после этого в нем остается член . Упрощенное булево выражение логической функции имеет вид
Рассмотрим минимизацию логической функции, карта Вейча которой представлена на рис. 5.
рис. 5
Булево выражение этой функции имеет вид
Четыре угловые клетки можно объединить в одну группу. Это объединение позволяет исключить две переменные (х 1 и х 2 ) и получить член .
Две единицы из первой строки можно объединить с двумя единицами из нижней строки, получить группу из четырех ячеек, которая позволяет исключить две переменные (х 1 и х 3 ) и получить член .
Наконец, единственную оставшуюся единицу (из второй строки и последнего столбца) можно объединить с клеткой, находящейся над ней, и это позволит исключить одну переменную (х 4 ) и получить член .
Таким образом, мы получим минимизированную логическую функцию
Метод карт Карно (диаграмм Вейча), по существу, упрощает нахождение склеиваемых конъюнкций в СДНФ исходной логической функции.
Минимизация функций алгебры логики описанными методами
В данной главе представлены подобранные нами функции и примеры их минимизации с помощью рассмотренных выше методов.
Упростить, используя карты Карно для функции 2 переменных:
Карта Карно (диаграмма Вейча) для этой функции будет иметь вид:
В первой строке можно исключить переменную х 2 и получить упрощенное выражение х 1 .
Во втором столбце можно исключить переменную х 1
Таким образом, упрощенное выражение логической функции будет иметь вид
В первом столбце можно исключить переменную х 1 и получить упрощенное выражение х 2 .
Во второй строке можно исключить переменную и получить упрощенное выражение .
Полученные упрощенные выражения соединим операцией ИЛИ.
Таким образом, упрощенное выражение логической функции будет иметь вид
Упростить, используя карты Карно для функции 3 переменных:
Диаграмма Вейча для этой функции будет иметь вид:
х 3 и получить упрощенное выражение .
х 3 и получить упрощенное выражение .
В последнем столбце можно исключить переменную х 1 и получить упрощенное выражение .
Полученные упрощенные выражения соединим операцией ИЛИ.
Таким образом, упрощенное выражение логической функции будет иметь вид
Диаграмма Вейча для этой функции будет иметь вид:
В первой строке можно исключить переменную х 3 и получить упрощенное выражение и переменную х 2 и получить упрощенное выражение .
Полученные упрощенные выражения соединим операцией ИЛИ.
Таким образом, упрощенное выражение логической функции будет иметь вид
Нами был найден и второй способ минимизации данной функции.
Тогда диаграмма Вейча для этой функции будет иметь вид:
В первой строке можно исключить переменную х 3 и получить упрощенное выражение .
В первой строке остается выражение .
Полученные выражения соединим операцией ИЛИ.
Таким образом, упрощенное выражение логической функции будет иметь вид
Очевидно, что полученная функция не является минимальной, поэтому воспользуемся методом непосредственных преобразований логических функций. Вынесем за скобки переменную х 1 и для выражения в скобках применим правило свертки. Получили тот же результат, что и в первом случае.
Это значит, что соседние клетки можно группировать разными способами, главное, не забывать основное правило: для исключения n переменных общее число группируемых клеток должно быть равно 2 n .
Диаграмма Вейча для этой функции будет иметь вид:
первой строке можно исключить переменную х 3 и получить упрощенное выражение .0 1 0 0
О втором столбце можно исключить переменную х 1 .
Полученные упрощенные выражения соединим операцией ИЛИ.
Таким образом, упрощенное выражение логической функции будет иметь вид
Диаграмма Вейча для этой функции будет иметь вид:
В первой строке можно исключить переменную х 3 и получить упрощенное выражение .
Во второй строке можно исключить переменную х 3 и получить упрощенное выражение .
Полученные упрощенные выражения соединим операцией ИЛИ.
Таким образом, упрощенное выражение логической функции будет иметь вид
Диаграмма Вейча для этой функции будет иметь вид:
В первом и последнем столбце можно исключить переменные х 1 и х 2 и получить упрощенное выражение .
Во второй строке можно исключить переменную х 2 и получить упрощенное выражение . О .
Полученные упрощенные выражения соединим операцией ИЛИ.
Таким образом, упрощенное выражение логической функции будет иметь вид
В данной главе были представлены функции двух, трех и четырех переменных, которые минимизировались с помощью диаграмм Вейча. Мною были наглядно продемонстированы и описаны особенности применения данного метода минимизации на различных функциях, в том числе и в совокупности с методом непосредственного преобразования функций алгебры логики.
Заключение
Представленная работа посвящена методам минимизации функций алгебры логики. В процессе работы были:
изучены основные элементы математической логики;
исследованы методы минимизации логических функций;
подобраны задачи для самостоятельной работы;
решены описанными методами подобранные задачи.
Мною было подробно рассмотрено 2 метода минимизации логических функций:
метод непосредственных преобразований логических функций, осуществляемый с использованием теорем алгебры логики;
метод минимизации с помощью диаграмм Вейча (карт Карно).
Первый метод получил широкое распространение даже в школьных учебниках информатики (например, учебники 10-11 класса Н. Угриновича , Л. Щауцуковой ), поскольку является одним из простых методов упрощения функций алгебры логики. Задания, представленные в учебниках указанных авторов, достаточно разнообразны:
упростить логическую формулу с помощью законов алгебры логики;
по заданной функции построить логическую схему;
упростить переключательную схему;
доказать с помощью таблицы истинности логическое выражение;
построить для данной функции таблицу истинности.
Второй метод позволяет быстро и легко исключить отличающиеся переменные и получить упрощенное выражение, которое не всегда может быть минимальным. Поэтому данный метод следует рассматривать в совокупности с методом непосредственных преобразований логических функций.
Данная тема имеет практическое значение в микроэлектронике. Кроме того, ЕГЭ по информатике и ИКТ содержит некоторое количество заданий, связанных с алгеброй логики, которые мы разделили на 4 группы .
Первая группа – это задания, требующие указать логическое выражение, равносильное данному.
Вторая группа – задания на нахождение фрагментов таблиц истинности, соответствующих данному выражению.
Третья группа включает задания на нахождение инстинности высказываний при любых значениях переменных х и у .
И четвертая группа – это задания на определение структурной формулы, соответствующей данной логической схеме.
Заданий конкретно касающихся минимизации логических функций мне не встретилось, но имеющиеся в тестах задания требуют достаточно глубоких знаний в области алгебры логики.
В связи с усложнением вступительных испытаний в высшие учебные заведения можно предположить, что в скором времени в тестах, а значит и в образовательных программах, могут появиться задания на упрощение и минимизацию логических функций.
Список литературы
Гаврюкова Г. А. Логика в информатике [Электронный ресурс]. – Режим доступа: окт. 2010).
Ивин А. А. Логика: Учебное пособие. – 2-е изд. – М.: Знание, 1998. – 233 с.
Игошин В. И. Математическая логика и теория алгоритмов: Учебное пособие для студ. высш. учеб. заведений. – 2-е изд., стер. – М.: Академия, 2008. – 448 с.
Информатика и ИКТ. Подготовка к ЕГЭ-2009. Вступительные испытания. / Под ред. Ф. Ф. Лысенко. – Ростов н/Д: Легион-М, 2009. – 208 с.
Информатика: Учебник / Б. В. Соболь [и др.]. – 3-е изд., доп. и перераб. – Ростов н/Д: Феникс, 2007. – 446 с.
Информатика: Учебное пособие / А. В. Могилев, Н. И. Пак, Е. К. Хеннер. – 3-е изд. – М.: Академия, 2004. – 848 с.
Калабеков Б. А. Цифровые устройства и микропроцессорные системы: Учебник для техникумов связи. – М.: Горячая линия – Телеком, 2000. – 336 с.
Каймин В. А. Информатика: Учебник. – 2-е изд., перераб. и доп. – М.: ИНФРА-М, 2001. – 272 с.
Коваленко А. А, Петропавловский М. Д. Основы микроэлектроники: Учебное пособие. – М.: Академия, 2006. – 240 с.
Львовский М. Б. Методическое пособие по информатике для учащихся 9-11 классов, изучающих IBM PC [Электронный ресурс]. – Режим доступа: сент. 2010).
Математические основы информатики. Элективный курс: Учебное пособие / Е. В. Андреева, Л. Л. Босова, И. Н. Фалина. – М.: БИНОМ. Лаборатория знаний, 2005. – 328 с.
Минимизация логических функций [Электронный ресурс]. – Режим доступа: авг. 2010).
Основы микроэлектроники: Учебное пособие для вузов / Н. А. Аваев, Ю. Е. Наумов, В. Т. Фролкин. – М.: Радио и связь, 1991. – 288 с.: ил.
Практикум по информатике и информационным технологиям / Н. Д. Угринович, Л. Л. Босова, Н. И. Михайлова. – 2-е изд., испр. – М.: БИНОМ. Лаборатория знаний, 2004. – 394 с.
Прикладная математика: Пособие / И. Н. Ревчук, В. К. Пчельник. – Гродно: ГрГУ им. Я. Купалы, 2007. – 128 с.
Рабкин Е. Л., Фарфоровская Ю. Б. Дискретная математика: булевы функции и элементы теории графов: Методические указания и контрольные задания [Электронный ресурс]. – Режим доступа: 7 авг. 2010).
Савельев А. Я. Основы информатики: Учебник для вузов. – М.: МГТУ им. Н. Э. Баумана, 2001. – 328 с., ил.
Степаненко И. П. Основы микроэлектроники: Учебное пособие для вузов. – 2-е изд., перераб. и доп. – М.: Лаборатория Базовых Знаний, 2001. – 488 с.
Теория и методика обучения информатике: Учебник / [М. П. Лапчик, И. Г. Семакин, Е. К. Хеннер, М. И. Рагулина и др.]; под ред. М. П. Лапчика. – М.: Академия, 2008. – 592 с.
Угринович Н. В. Информатика и ИКТ. 10 класс. Профильный уровень. – 3-е изд., испр. – М.: Бином. Лаборатория знаний, 2008. – 387 с.
Угринович Н. В. Информатика и информационные технологии: Учебник для 10-11 классов. – М.: БИНОМ. Лаборатория знаний, 2003. – 512 с.
Шауцукова Л. З. Информатика 10 – 11. – М.: Просвещение, 2004. – 420 с.
Различают комбинационные и последовательностные логические устройства.
Комбинационные логические устройства - это устройства, у которых значения выходных сигналов зависят только от комбинации входных сигналов в данный момент времени.
Последовательностные логические устройства - это устройства, выходные сигналы которых зависят от значений входных сигналов не только в данный момент времени, но и в предыдущие моменты времени. В состав этих устройств обязательно входят элементы памяти - триггеры. Различают несколько видов триггеров в зависимости от того, какую элементарную функцию памяти они реализуют.
При разработке логического устройства сначала формулируют словесное описание его алгоритма действия. Затем составляют удовлетворяющую этому описанию логическую функцию (абстрактный синтез) и далее разрабатывают структурную логическую схему устройства {структурный синтез).
В процессе абстрактного синтеза осуществляется переход от словесного описания ТП (его нормальный ход и аварийные ситуации) к составлению алгоритма функционирования в виде таблицы, циклограммы, графика и т.п. Циклограмма представляет собой ряд горизонтальных строк, равных числу входов и выходов логического устройства. Для составления логического алгоритма управления технологическим оборудованием необходимо иметь полную информацию о ТП каждой технологической операции и применяемом оборудовании. На этой стадии уточняют последовательность операций и необходимые временные задержки для всех режимов работы объекта управления, определяют параметры, подлежащие контролю и учету в ходе процесса; формулируют требования управляемого объекта к логическому устройству. Эти требования представляют в виде значений двоичных сигналов, которые должны быть поданы на исполнительные устройства системы управления в зависимости от состояния управляемого объекта.
В процессе структурного синтеза происходит переход от логической функции, описывающей алгоритм функционирования, к структурной схеме логического устройства.
Однако прежде чем приступить к разработке схемы, необходимо попытаться преобразовать исходную логическую функцию к максимально простому виду. На основе структурной схемы логического устройства разрабатывают его принципиальную схему с использованием конкретной элементной базы, например в базисе ИЛИ-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.
Все логические функции задаются либо в виде формулы, либо в виде таблицы значений. Иногда бывает нужно определить простейшую форму записи этой функции с минимальным количеством элементарных логических функций И, ИЛИ, НЕ для удобства работы. Для этого используются все рассмотренные операции начиная с №4 и методы Квайна и Вейча.
Метод Квайна позволяет найти простейшую нормальную дизъюнктивную форму логического выражения, т.е. записать логическое выражение в виде дизъюнкции или конъюнкции, при этом знак инверсии может стоять только над одним аргументом или не стоять вообще. Алгоритм дается в специальной литературе.
Метод Вейча (карты Карно)
В этом методе для изображения функции n переменных рисуется специальная таблица, которая содержит 2 n клеток. В каждой клетке ставится соответствие одному из наборов n переменных. В клетке записывается значение, принимаемое функцией при этом наборе аргументов. Все клетки, соответствующие наборам содержащие некоторую переменную без знака инверсии образуют область из 2 n -1 клеток. Эта область называется областью данной переменной (например, область переменной х). Остальные клетки образуют область этой инверсной переменной. Возможные наборы аргументов распределены по клеткам таким образом, чтобы границы областей всех переменных и их инверсии были четки, а принадлежность любой клетки к той или иной область зрительно легко выявлялась.
1) Функция одной переменной:
2) Функция двух переменных:
3) Диаграмма для дизъюнкции:
4) Диаграмма для конъюнкции:
5) Для трех аргументов:
6) Для четырех аргументов:
Можно минимизировать заданное логическое выражение, объединив в группы стоящие рядом единицы и при этом исключать ту переменную, которая переходит из прямого в инверсное состояние. Объединять можно не только по вертикали и горизонтали, но и по краям, так как в общем случае карта Карно образует тор. Пример:
б) 
8.3. Аналитические методы минимизации переключательных функций
Метод Квайна .
Метод основан на попарном сравнении и склеивании при возможности всех конституент (членов СДНФ). Для этого каждая конституента сравнивается с последующими, что приводит к получению импликант. Полученные импликанты вновь подвергаются сравнению и при возможности склеиваются – и т.д. до тех пор, пока оставшиеся импликанты уже не будут поддаваться склеиванию. Это и есть простые импликанты, их дизъюнкция представляет собой сокращенную ДНФ.
Для упорядочения целесообразно разбивать конституенты на группы по числу неинверсированных переменных. В этом случае каждая очередная конституента, начиная сверху, сравнивается только с конституентами группы, соседней снизу, с числом неинверсированных переменных на единицу больше.
Пусть имеется переключательная функция, заданная СДНФ:
Разобьем конституенты на группы по числу неинверсированных переменных.
Римская цифра номера группы соответствует числу неинверсных переменных. Проведем линии, указывающие склеиваемые конституенты. Результатом склеивания является всегда элементарная конъюнкция, представляющая собой общую часть исходных конъюнкций (в частности, конституент).
Полученные
импликанты также допускают склеивание,
причем в результате получается одна и
та же импликанта
.
Дальнейшие склеивания невозможны, поэтому полученные импликанты – простые, а сокращенная ДНФ имеет вид:
Первый этап выполнен. На втором этапе необходимо исключить лишние простые импликанты. Это делается с помощью специальной импликантной таблицы Квайна (таблицы покрытий). Строки таблицы отмечаются простыми импликантами переключательной функции, т.е. членами сокращенной ДНФ, а столбцы – конституентами единицы, т.е. членами СДНФ переключательной функции.
Как уже отмечалось, простая импликанта поглощает некоторую конституенту единицы, если является ее собственной частью. Соответствующая клетка импликантной таблицы на пересечении строки данной простой импликанты и столбцов с конституентами единицы отмечается, например, знаком «+». Минимальные ДНФ строятся по импликантной таблице следующим образом:
1) ищутся столбцы импликантной таблицы, имеющие только один крестик, соответствующие этим крестикам простые импликанты называются базисными и составляют так называемое ядро переключательной функции. Ядро обязательно входит в минимальную ДНФ;
2) рассматриваются различные варианты выбора совокупности простых импликант, которые накроют крестиками остальные столбцы импликантной матрицы, и выбираются варианты с минимальным суммарным числом букв.
Ядром
нашей функции (табл. 35) являются импликанты
и х 1 х 2 х 3 ,
т.е. функция имеет единственную тупиковую
и минимальную ДНФ:
Таблица 35
Импликантная таблица Квайна
|
Конституенты 1 (члены СДНФ) |
|||||||
|
импли-канты |
|
|
|
|
|
|
|
|
| |||||||
Видно,
что импликанта х 2 х 3 х 4
является лишней, так как она покрывает
конституенты, уже покрытые импликантами
,
х 1 х 2 х 3 .
Число крестиков в строке является степенью числа 2; более того, можно убедиться, что оно равно N=2 n - k , где k – число букв в простой импликанте, n – число переменных, от которых зависит функция.
Если вначале не задана СДНФ, то ее надо получить, используя, например, уже известные нам методы.
Ясно, что для больших импликантных таблиц трудно визуально выявить варианты с минимальным числом букв. Поэтому используется метод Петрика, позволяющий получать все тупиковые ДНФ по импликантной таблице путем построения так называемого конъюнктивного ее представления. Для этого все простые импликанты обозначаются разными буквами (А, В, С в табл. 35), а затем для каждого столбца строится дизъюнкция всех букв, обозначающих строки таблицы, пересечение которых с данным столбцом отмечено крестиком. Конъюнктивное представление импликантной матрицы образуется как конъюнкция построенных дизъюнкций для всех столбцов. К конъюнктивному представлению импликантной таблицы могут быть применены все соотношения булевой алгебры переключательных функций с целью его упрощения. После раскрытия скобок и выполнения всех возможных поглощений получается дизъюнкция конъюнкций, каждая из которых содержит все импликанты тупиковой ДНФ.
Это
означает, что тупиковая ДНФ содержит
две простые импликанты (
и одновременно С=х 1 х 2 х 3)
и имеет вид:
Метод Квайна-Мак-Класки.
Метод представляет собой формализацию метода Квайна, ориентированную на использование ЭВМ. Формализация заключается в записи конституент единицы (членов СДНФ) их двоичными номерами. Все номера разбиваются на непересекающиеся группы по числу единиц в двоичном номере. Склеивания производятся только между соседними группами. Ликвидируемый разряд обозначается знаком «–» («тире»). Дальнейшие группы из полученных импликант образуются с учетом однинакового расположения тире. Такое обозначение импликант называется обобщенными кодами. Пусть задана логическая функция
111101001000110.
Сгруппируем эти конституенты единицы по числу единиц:
Дальнейшие склеивания невозможны. Нахождение минимальных ДНФ далее производится по импликантной таблице (табл. 36):
Это означает, что тупиковые ДНФ содержат по три простые импликанты и имеют вид:
(две
инверсии);
(три
инверсии).
Таблица 36
Импликантная таблица Квайна-Мак-Класки
|
импликанты |
Конституенты единиц |
|||||||
Заметим, что склеивание двух импликант с тире возможно только при соответствующем их расположении, например:
|
|
|
|
|
Можно выбрать любую из полученных ТДНФ, а с учетом меньшего числа инверсий – первую.
Метод Блейка-Порецкого .
Метод позволяет получать сокращенную ДНФ булевой функции по ее произвольной ДНФ, а не по СДНФ, как в методах Квайна и Квайна-Мак-Класки, используя закон обобщенного склеивания . В основу метода положено следующее утверждение: если в произвольной ДНФ булевой функции провести всевозможные операции, обратные обобщенному склеиванию, а затем выполнить все поглощения, то в результате получится сокращенная ДНФ функции.
Пусть задана ДНФ функции:
Видно, что к первой и второй конъюнкциям можно применить закон обобщенного склеивания по переменной х 1 ; получим:
Аналогично для первой и третьей конъюнкций:
т.е. все остается, как есть!
Вторая и третья конъюнкции допускают обобщенное склеивание по х 2:
Переходим к ДНФ:
После применения закона идемпотентности (повторения) и поглощения получаем:
Попытки дальнейшего применения обобщенного склеивания и поглощения не дают результата. Следовательно, получена сокращенная ДНФ функции.
Таблица 37
Импликантная таблица для иллюстрации метода Блейка-Порецкого
|
импликанты |
Наборы функции и ее значения |
|||||||||
Таким
образом, рабочие (единичные) наборы
можно покрыть тремя простыми импликантами,
например,
,
,
.
В ядро входят импликанты
,
.
Тогда тупиковые ДНФ имеют вид:
(лучше по числу инверсий).
Студент должен:
Знать:
· Методы минимизации логических функций.
Уметь:
· Выполнять минимизацию функций методом непосредственных преобразований; Выполнять минимизацию функций методом непосредственных преобразований;
· Выполнять минимизацию функций с помощью карт Карно.
Метод непосредственных преобразований
Логическая функция, задающая принцип построения схемы цифрового устройства, может быть, как было показано выше, представлена в виде таблицы истинности или в виде СДНФ или СКНФ и может быть использована для получения логической схемы устройства. Однако полученная логическая схема, как правило, не будет оптимальна. Поэтому важным этапом синтеза логических схем является минимизация логических функций.
Минимизация (упрощение формы записи) функции является важной операцией при синтезе логической схемы, так как благодаря предварительно проведенной минимизацией схема реализуется с наименьшим числом элементов.
Для минимизации разработан ряд методов. Одним из простых методов минимизации является метод непосредственных преобразований, который осуществляется с использованием основных теорем алгебры логики.
Например, логическую функцию
в виде СДНФ, можно минимизировать следующим образом:
1. Добавим к данной функции слагаемое , которое уже есть в данной функции, используя правило х+х=х
2. Применим метод склеивания одинаково подчеркнутых элементарных конъюнкций
3. Применим метод склеивания для двух последних элементарных конъюнкций
Полученная в результате минимизации логическая функция называется тупиковой. Логическая функция может иметь несколько тупиковых форм.
Выявление и устранить избыточности в записи функции путем её преобразований с использованием аксиом, законов, тождеств и теорем алгебры логики требуют громоздких выкладок и связаны с большой затратой времени.
Карты Карно
Метод непосредственных преобразований наиболее пригоден для простых формул, когда последовательность преобразований очевидна для исполнителя. Наиболее часто этот метод применяется для окончательной минимизации выражений, полученных после минимизации их другими методами.
Стремление к алгоритмизации поиска соседних элементарных произведений привело к разработке табличных методов минимизации логических функций. Одним из них является метод, основанный на использовании карт Карно.
Карты Карно были изобретены в 1952 Эдвардом В. Вейчем и усовершенствованы в 1953 Морисом Карно, физиком из «Bell Labs», и были призваны помочь упростить цифровые электронные схемы.
Карта Карно - это графическое представление таблицы истинности логических функций. Она представляет собой таблицу, содержащую по 2 n прямоугольных ячеек, где n - число логических переменных.
Например, карта Карно для функции четырех переменных имеет 2 4 = 16 ячеек.
Структура карты Карно для функций двух переменных показана на рисунке 2.2. 2
Рисунок 2.2
На рисунке 2.3 представлена структура карты Карно для функции трёх переменных.
а) таблица истинности; б) структура карты Карно
Рисунок 2.3
Карта размечается системой координат, соответствующих значениям входных переменных. Например, верхняя строка карты для функции трех переменных (рисунок 2.3) соответствует нулевому значению переменной x1, а нижняя - ее единичному значению.
Каждый столбец этой карты характеризуется значениями двух переменных: х2 и х3. Комбинация цифр, которыми отмечается каждый столбец, показывает, для каких значений переменных х2 и х3 вычисляется функция, размещаемая в клетках этого столбца.
Если на указанном наборе переменных функция равна единице, то ее СДНФ обязательно содержит элементарное произведение, принимающее на этом наборе единичное значение. Таким образом, ячейки карты Карно, представляющие функцию, содержат столько единиц, сколько элементарных произведений содержится в ее СДНФ, причем каждой единице соответствует одно из элементарных произведений.
Обратим внимание на то, что координаты строк и столбцов в карте Карно следуют не в естественном порядке возрастания двоичных кодов, а в порядке 00, 01, 11, 10. Изменение порядка следования наборов сделано для того, чтобы соседние наборы были соседними, т.е. отличались значением только одной переменной.
Ячейки, в которых функция принимает значения, равные единице, заполняются единицами. В остальные ячейки записываются нули.
Процесс минимизации рассмотрим на примере, представленном на рисунке 2.4.
а) таблица истинности; б) карта Карно
Рисунок 2.4
Сначала формируем прямоугольники, содержащие по 2k ячеек, где k - целое число.
В прямоугольники объединяются соседние ячейки, которые соответствуют соседним элементарным произведениям.
Например, на рисунке 2.4,б объединены ячейки с координатами 001 и 101. При объединении этих ячеек образовался прямоугольник, в котором переменная x1 изменяет свое значение. Следовательно, она исчезнет при склеивании соответствующих элементарных произведений и останутся только х2 и х3, причем переменную х2 берем в инверсном виде, т.к. она равна 0.
Ячейки, расположенные в первой строке (рисунок 2.4 б), содержат единицы и являются соседними. Поэтому все они объединяются в прямоугольник, содержащий 2 2 = 4 ячейки.
Переменные х2 и х3 в пределах прямоугольника меняют свое значение; следовательно, они исчезнут из результирующего элементарного произведения. Переменная х1 остается неизменной и равной нулю. Таким образом, элементарное произведение, полученное в результате объединения ячеек первой строки рисунка 2.4 б, содержит лишь один х1, который берем в инверсном виде, т.к. он равен 0.
Это, в частности, следует из того, что четырем ячейкам первой строки соответствует сумма четырех элементарных произведений:
Двум ячейкам сторого столбца соответствует сумма двух произведений
Функция, соответствующая рисунку 2.4 имеет вид:
Совокупность прямоугольников, покрывающих все единицы, называют покрытием. Заметим, что одна и та же ячейка (например, ячейка с координатами 001) может покрываться два или несколько раз.
Итак, можно сделать следующие выводы:
1. Формула, получающаяся в результате минимизации логической функции с помощью карт Карно, содержит сумму стольких элементарных произведений, сколько прямоугольников имеется в покрытии.
2. Чем больше ячеек в прямоугольнике, тем меньше переменных содержится в соответствующем ему элементарном произведении.
Например, для карты Карно, изображенной на рисунке 2.5 а, прямоугольнику, содержащему четыре ячейки, соответствует элементарное произведение двух переменных, а квадрату, состоящему всего лишь из одной ячейки,- элементарное произведение 
включающее все четыре переменные.
а) б) в)
Рисунок 2.5
Функция, соответствующая покрытию, показанному на рисунке 2.5 а, имеет вид:
Несмотря на то, что карты Карно изображаются на плоскости, соседство квадратов устанавливается на поверхности тора. Верхняя и нижняя границы карты Карно как бы «склеиваются», образуя поверхность цилиндра. При склеивании боковых границ получается тороидальная поверхность. Следуя изложенным рассуждениям, устанавливаем, что ячейки с координатами 1011 и 0011, изображенные на рисунке 2.5 б, являются соседними и объединяются в прямоугольник. Действительно, указанным ячейкам соответствует сумма элементарных произведений
Аналогично объединяются и остальные четыре единичные ячейки. В результате их объединения получаем элементарное произведение .
Окончательно функция, соответствующая покрытию, изображенному на рисунке 2.5 б, имеет вид
Карта Карно, показанная на рисунке 2.5 в, содержит единичные ячейки, расположенные по углам. Все четыре ячейки являются соседними, и после объединения дадут элементарное произведение
Рассмотренные выше примеры позволяют сформулировать последовательность проведения минимизации логических функций с помощью карт Карно:
1. Изображается таблица для n переменных и производится разметка ее сторон.
2. Ячейки таблицы, соответствующие наборам переменных, обращающих функцию в единицу, заполняются единицами, остальные ячейки - нулями.
3. Выбирается наилучшее покрытие таблицы правильными прямоугольниками, которые обводим контурами. В каждом прямоугольнике должно быть 2 n ячеек.
4. Одни и те же ячейки с единицами могут входить в разные контуры.
5. Количество прямоугольников должно быть минимальным, а площадь прямоугольников максимальная.
6. Для каждого прямоугольника записываем произведение только тех переменных, которые не изменяют своего значения. Если эта переменная равна нулю, то ее записывают в инверсном виде.
7. Полученные произведения соединяем знаком логического сложения.
1. Что называют минтермами и минтермами?
2.Записать функции, заданные таблицами 2.9 и 2.10 в СДНФ и СКНФ.
Таблица 2.9
3. Упростите логические функции, используя аксиомы тождества и законы алгебры логики:
a) 
c) 
Логические элементы
Студент должен
Знать:
· Таблицы логических состояний для основных функциональных логических схем;
· Основные базисы построения логических схем.
Уметь:
· Определять логические состояния на выходах цифровых схем по известным состояниям на входах;
· Выполнять логическое проектирование в базисах микросхем;
· Выбирать микросхему по справочнику, исходя из заданных параметров и условий использования.
Принцип логического устройства базируется в ИМС на работе биполярных транзисторов в режиме ключа (либо замкнут, либо разомкнут).
Логическое действие осуществляется как с одной (одновходовый логический элемент) так и с множеством (многовходовый логический элемент) входных переменных.
При работе логических устройств используются три основных действия согласно алгебры Буля – «И», «ИЛИ», «НЕ».
Логическая функция может быть выражена словесно, в алгебраической форме, таблицей истинности, называемой переключательной таблицей, с помощью временных диаграмм. Рассмотрим все варианты представления логических функций.