Табличные методы минимизации функций. Анализ и синтез логических устройств

Работа по теме

МЕТОДЫ МИНИМИЗАЦИИ
ЛОГИЧЕСКИХ ФУНКЦИЙ

Ключевые понятия: логические выражения, логические функции, методы минимизации, инверсия, конъюнкция, дизъюнкция, импликация, эквиваленция.

Содержание

Введение

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

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

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

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

В связи с этим минимизация логических функций особенно актуальна.

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

Объектом работы стал процесс минимизации логических функций.

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

Задачи исследования:

изучить основные элементы математической логики;

исследовать методы минимизации логических функций;

подобрать задачи для самостоятельной работы;

решить описанными методами подобранные задачи.

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

Во введении обосновывается актуальность темы, определяется цель и задачи исследования.

В первом разделе рассматриваются логические основы функционирования ЭВМ.

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

В заключении подводятся общие итоги исследования.

Логические основы функционирования ЭВМ

Элементы математической логики

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

Вычислительные машины всех поколений состояли и состоят из логических элементов и элементов памяти, принимающих два значения (бита) 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 и получить упрощенное выражение . О .

Полученные упрощенные выражения соединим операцией ИЛИ.

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

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

Заключение

Представленная работа посвящена методам минимизации функций алгебры логики. В процессе работы были:

1. изучены основные элементы математической логики;

   исследованы методы минимизации логических функций;

   подобраны задачи для самостоятельной работы;

   решены описанными методами подобранные задачи.

Мною было подробно рассмотрено 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 с.

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

Зачем это нужно?

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

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

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

Минимизация логических функций при помощи карт Карно

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

Карты Карно были изобретены в 1952 Эдвардом В. Вейчем и усовершенствованы в 1953 Морисом Карно, физиком из «Bell Labs», и были призваны помочь упростить цифровые электронные схемы.

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

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

Возможность поглощения следует из очевидных равенств

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

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

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

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

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

В общем случае можно сказать, что 2K термов, принадлежащие одной K–мерной грани гиперкуба, склеиваются в один терм, при этом поглощаются K переменных.

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

Аналогичным образом можно работать с функциями четырёх, пяти и более переменных. Примеры таблиц для N=4 и N=5 приведены на рисунке. Для этих таблиц следует помнить, что соседними являются клетки, находящиеся в соответственных клетках крайних столбцов и соответственных клетках верхней и нижней строки. Для таблиц 5 и более переменных нужно учитывать также, что квадраты 4х4 виртуально находятся друг над другом в третьем измерении, поэтому соответственные клетки двух соседних квадратов 4х4 являются сосоедними, и соответствующие им термы можно склеивать.

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

Если необходимо получить минимальную ДНФ, то в Карте рассматриваем только те клетки которые содержат единицы, если нужна КНФ, то рассматриваем те клетки которые содержат нули. Сама минимизация производится по следующим правилам (на примере ДНФ):

Далее берём первую область и смотрим какие переменные не меняются в пределах этой области, выписываем конъюнкцию этих переменных, если неменяющаяся переменная нулевая, проставляем над ней инверсию. Берём следующую область, выполняем то же самое что и для первой, и т. д. для всех областей. Конъюнкции областей объединяем дизъюнкцией.
Например(для Карт на 2-ве переменные):

Для КНФ всё то же самое, только рассматриваем клетки с нулями, не меняющиеся переменные в пределах одной области объединяем в дизъюнкции (инверсии проставляем над единичными переменными), а дизъюнкции областей объединяем в конъюнкцию. На этом минимизация считается законченной. Так для Карты Карно на рис.1 выражение в формате ДНФ будет иметь вид:

В формате КНФ:

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

В основе методов минимизации лежит операция склеивания (алгоритм объединения соседний двоичных чисел):

где А - элементарная конъюнкция.

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

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

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

Минимизация сложных логических выражений с помощью матрицы Карно

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

Матрицы Карно целесообразно использовать для минимизации ФАЛ на наборах из 2,3,4,5 и 6 переменных. Номера столбцов в матрицах Карно образуют младшие разряды, а номера строк - старшие разряды наборов. Номера клеток составляются из номеров строк и столбцов и соответствуют наборам переменных.

Рассмотрим матрицу Карно для функции алгебры логики на наборах из 4-х переменных (табл. 1).

Таблица 1. Матрица Карно

Столбцы и строки в этой матрице обозначены двоичными соседними числами: 00-0I-II-I0. Поэтому номера смежных по горизонтали и вертикали клеток, а также крайних в строках и столбцах клеток являются соседними числами, например:

клетки с номерами и;

клетки с номерами;

клетки с номерами;

клетки с номерами.

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

В «подкубы» объединяются:

• - две клетки с номерами, являющимися соседними числами, при этом исключается одна переменная;
• - четыре клетки (строка, столбец, квадрат, угловые клетки), при этом исключается две переменные;
• - восемь клеток (две соседних или крайних строки (столбца)), при этом исключается три переменные.

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

Пусть необходимо минимизировать следующую функцию алгебры логики:

Матрица Карно, заполненная в соответствии с этой формулой, может быть представлена в виде таблицы 2:

Таблица 2. Матрица Карно

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

Метод Квайна

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

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

по всем недостающим переменным x ik , ..., xim исходной функции f, получаем совокупность S конституент единицы. При склеивании всех конституент из S получим импликанту р. Последнее очевидно, поскольку операция склеивания обратна операции развертывания. Множество S конституент обязательно присутствует в совершенной ДНФ функции f поскольку р - ее импликанта.

В результате выполнения склеивания получается конъюнкция n-1 ранга, а конъюнкции остаются в исходном выражении и участвуют в сравнении с другими членами СДНФ. Таким образом, удается снизить ранг термов.

Склеивание и поглощение выполняются до тех пор, пока имеются члены, не участвовавшие в попарном сравнении. Термы, подвергшиеся операции склеивания, отмечаются. Неотмеченные термы представляют собой простые импликанты и включаются в сокращенную ДНФ. Все отмеченные конъюнкции ранга n-1 подвергаются вновь операции склеивания до получения термов n-2 ранга и так далее до тех пор, пока количество неотмеченных конъюнкций больше 2. В результате выполнения первого этапа получена сокращенная ДНФ.

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

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

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

f СДНФ = V (1,2,5,6,7)=x1 x2 x3 + x1 x2 x3 + x1 x2 x3 + x1 x2 x3 + x1 x2 x3

1 2 3 4 5

Выполним операцию склеивания:

• 1 - 3 (x1 ) x2 x3 1
• 2 - 4 (x1 ) x2 x3 2
• 3 - 5 (x2 ) x1 x3 3
• 4 - 5 (x3 ) x1 x2 4

В результате выполнения первого шага склеивания получаем четыре новые конъюнкции, простых импликант не выявлено. Полученные конъюнкции более не склеиваются и образуют сокращенную ДНФ.

f сокр СДНФ =x2 x3 + x2 x3 + x1 x3 + x1 x2

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

Таблица 3. Импликантная таблица

	x 1 x2 x3	X 1 x2 x3	x 1 x2 x3	x 1 x2 x3	x 1 x2 x3

Простые импликанты являются обязательными так как только они покрывают конституэнтыи включаются в минимальное покрытие. Остается одна непокрытая конституэнта x1 x2 x3 которая может быть покрыта одной из двух оставшихся простых импликант. Это приводит к получению двух тупиковых форм.

Метод Блейка - Порецкого

Метод позволяет получать сокращенную ДНФ булевой функции f из ее произвольной ДНФ. Базируется на применении формулы обобщенного склеивания:

справедливость которой легко доказать. Действительно,

Следовательно,

В основу метода положено следующее утверждение: если в произвольной ДНФ булевой функции f произвести все возможные oбобщенные склеивания, а затем выполнить все поглощения, то в результате получится сокращенная ДНФ функции f.

Рассмотрим пример. Пусть булева функция f задана произвольной ДНФ.

Необходимо используя метод Блейка - Порецкого получить сокращенную ДНФ функции f. Проводим обобщенные склеивания. Легко видеть, что первый и второй элемент исходной ДНФ допускают обобщенное склеивание по переменной х 1 . В результате склеивания получим:

Первый и третий элемент исходной ДНФ допускают обобщенное склеивание как по переменной х 1 , так и по х2 . После склеивания по x1 имеем:

После склеивания по x 2 имеем:

Второй и третий элемент ДНФ допускают обобщенное склеивание по переменной х 2 . После склеивания получаем:

Выполнив последнее обобщенное склеивание, приходим к ДНФ:

После выполнения поглощений получаем:

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

Минимизация не полностью определенных ФАЛ

Если при синтезе логической схемы, реализующей некоторую ФАЛ n переменных, окажется, что некоторые наборы из общего числа 2n никогда не смогут появиться на входах схемы, то данная логическая функция не определена на этих наборах. Тогда 2n наборов переменных можно подразделить на три группы: наборы, на которых функция принимает единичное значение L, нулевое значение D и группа наборов, на которых функция не определена N (неопределенные наборы). ФАЛ, содержащая неопределенные наборы, называется неполностью или частично определенной. Неопределенные наборы могут быть использованы для улучшения качества минимизации. При этом неопределенные наборы (при минимизации, например, картами Вейча, Карно) могут участвовать в образовании контуров как с единичными, так и с нулевыми наборами. Это приводит к формированию более простой минимизированной логической функции.

Универсальным методом минимизации является использование законов и соотношений алгебры логики, которые позволяют проводить минимизацию ФАЛ при любом числе переменных.

Продолжительность: 2 часа (90 мин.)

14.1 Ключевые вопросы

14 Лекция №13. Минимизация логических функций 1

14.1 Ключевые вопросы 1

14.2 Текст лекции 1

14.2.1 Минимизация логических функций 1

14.2.1.1 Расчетный метод 1

14.2.1.2 Карты Карно 4

14.2.2 Минимизация систем логических уравнений 7

14.2.3 Минимизация частично определенных логических функций 8

14.2.4 Вопросы для контроля 10

14.2 Текст лекции

14.2.1 Минимизация логических функций

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

расчетный;

карт Карно.

14.2.1.1 Расчетный метод

Здесь применяют:

– склеивание,

– поглощение,

– развертывание.

Склеивание

а) Если в выражении встречается сумма двух конъюнкций, в одной из которых одна из переменных стоит в прямом значении, а в другой в инверсном значении, а остальные переменные одинаковые, то эту сумму конъюнкций, можно заменить одной конъюнкцией, не содержащей переменную, имеющую разные значения:

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

Замечание:
и дистрибутивном законе конъюнкции относительно дизъюнкции (см. Лекцию № 10)

.

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

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

Замечание: Это правило основано на законе дополнительности

и дистрибутивном законе дизъюнкции относительно конъюнкции (см. Лекцию № 10)

в) Правила обобщенного склеивания.

В первом случае исчезло произведение bc , во втором исчезает суммаbc , в третьем снова произведениеbc (третий случай после раскрытия скобок сводится к первому). Доказываются эти правила, как обычно, составлением и сравнением таблиц истинности для левой и правой части или с помощью развертывания (см. ниже).

Поглощение

а) Если в выражении встречается сумма двух произведений, одно из которых является частью другого, то эту сумму можно заменить меньшим произведением:

б) Если в выражении встречается произведение двух сумм, одна из которых является частью другой, то это произведение сумм можно заменить меньшей суммой:

a (ab ) = a ; a (ab )(ac )…= a ; (ab )(abc )= ab .

Развертывание

Развертывание позволяет восстановить в формулах «потерянные» (например, в результате минимизации) переменные или перейти от ДНФ и КНФ к совершенным формам – СДНФ и СКНФ. Восстановление переменных для ДНФ и КНФ производится по–разному. Рассмотрим примеры.

Пусть имеем ДНФ

в которой, очевидно, потеряна переменная y . Для восстановления переменнойy произведение переменныхxz умножается на 1, затем 1 заменяется суммой прямого и инверсного обозначений недостающей переменной, и на основе дистрибутивного закона проводится преобразование

Пусть имеем КНФ
, где также потеряна переменнаяy . Для ее восстановления к сумме
добавляется 0, затем 0 заменяется произведением недостающей переменной на ее инверсию и применяется дистрибутивный закон

Используя развертывание, можно раскрыть смысл понятий «конституента единицы» и «конституента нуля».

Пусть n = 2 (переменныеa иb ).

Развернем единицу 1.

1= 1=
=.

Получили СДНФ функции двух переменных f = 1, где каждая конъюнкция является составляющей (конституентой) единицы.

Развернем 0.

Получили СКНФ функции двух переменных f = 0, где каждая дизъюнкция является составляющей (конституентой) нуля.

Полезность развертывания показывает пример доказательства правил обобщенного склеивания (см. п. 4.1.1):

Рассмотрим первое правило

Развернем левую часть тождества, в первом произведении которой недостает переменной c , во втором произведении недостаетb , а в третьем нетa .

После приведения подобных членов, применив простое склеивание

получаем правую часть, следовательно, тождество доказано.

Рассмотрим второе правило

Развернем левую часть тождества.

Используя дистрибутивный закон дизъюнкции относительно конъюнкции, получаем

После приведения подобных членов, применив простое склеивание, будем иметь

Получили правую часть, следовательно, правило доказано.

Общий порядок проведения минимизации функции, заданной СДНФ, здесь следующий.

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

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

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

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

Пример 1: Минимизировать функцию

После применения операции склеивания и приведения подобных членов получаем

Обобщенное склеивание здесь можно проводить по нескольким вариантам, которые дают следующие результаты:

.

Исключены
,
,
: (
), (
), (
).

В скобках показаны термы, участвующие в обобщенном склеивании.

Исключены
,
,
: (
), (
), (
).

Как видим, здесь имеется две минимальных нормальных формы. По сложности они одинаковы.

Пример 2: Продолжая решение задачи по созданию устройства рис. 3, проведем минимизацию мажоритарной функции (см. табл. 12), для которой выше были получены СДНФ и СКНФ.

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

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

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

Метод Вейча (карты Карно)

В этом методе для изображения функции n переменных рисуется специальная таблица, которая содержит 2 n клеток. В каждой клетке ставится соответствие одному из наборов n переменных. В клетке записывается значение, принимаемое функцией при этом наборе аргументов. Все клетки, соответствующие наборам содержащие некоторую переменную без знака инверсии образуют область из 2 n -1 клеток. Эта область называется областью данной переменной (например, область переменной х). Остальные клетки образуют область этой инверсной переменной. Возможные наборы аргументов распределены по клеткам таким образом, чтобы границы областей всех переменных и их инверсии были четки, а принадлежность любой клетки к той или иной область зрительно легко выявлялась.

1) Функция одной переменной:

2) Функция двух переменных:

3) Диаграмма для дизъюнкции:

4) Диаграмма для конъюнкции:

5) Для трех аргументов:

6) Для четырех аргументов:

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

б)