Главная / Информатика / Методы минимизации логических функций

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

Название документа Мулдашева.doc






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


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










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





Содержание

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

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

Содержание 2

Введение 3

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

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

Логические функции и их преобразование 9

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

Метод непосредственных преобразований логических функций 16

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

Минимизация функций алгебры логики описанными методами 22

Заключение 29

Список литературы 31



Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



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

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

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

Вычислительные машины всех поколений состояли и состоят из логических элементов и элементов памяти, принимающих два значения (бита) 0 и 1. Вся обработка информации в ЭВМ всех ее логических блоков, логических схем и устройств опиралась и будет опираться на законы и принципы математической логики [8].

Логика (от древнегреческого logos, означающего «слово, мысль, понятие, рассуждение, закон») – это древнейшая наука, изучающая правильность суждений, рассуждений и доказательств.

Математическая логика – это математическая дисциплина, изучающая технику доказательств [8].

Основоположником математической логики является великий немецкий математик Готфрид Вильгельм Лейбниц (1646 – 1716 гг.). Он выдвинул идею о применении в логике математической символики и построении логических исчислений, поставил задачу логического обоснования математики, сыграл важную роль в истории создания электронно-вычислительных машин: предложил использовать для целей вычислительной математики бинарную систему счисления. На заложенном Лейбницем фундаменте ирландский математик Джордж Буль построил здание новой науки – математической логики, – которая в отличие от обычной алгебры оперирует не числами, а высказываниями. В честь Д.Буля логические переменные в языке программирования «Паскаль» впоследствии назвали булевскими.

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

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

Различные логические выражения (высказывания) могут принимать только два значения: «истинно» или «ложно». Каждая логическая переменная может принимать только одно значение. Существуют разные варианты обозначения истинности и ложности:

Истина

И

True

T

1

Ложь

Л

False

F

0


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

Рассмотрим логические операции, с помощью которых можно записать любое логическое выражение.

Самой простой логической операцией является операция НЕ (по-другому ее часто называют отрицанием, дополнением или инверсией и обозначают hello_html_m1f1de136.gif). Результат отрицания всегда противоположен значению аргумента. Другими простыми слова, данная операция означает, что к исходному логическому выражению добавляется частица «не» или слова «неверно, что».

Таким образом, отрицанием hello_html_m1f1de136.gif некоторого высказывания hello_html_mcd9c74f.gif называется такое высказывание, которое истинно, когда hello_html_mcd9c74f.gif ложно, и ложно, когда hello_html_mcd9c74f.gif истинно [3].

Логическая операция НЕ является унарной, т.е. имеет всего один операнд. Определение отрицания может быть записано с помощью так называемой таблицы истинности, в которой указано, указано, какие значения истинности (1, 0) принимает отрицание hello_html_m1f1de136.gif в зависимости от значений истинности исходного высказывания hello_html_mcd9c74f.gif:

hello_html_mcd9c74f.gif

hello_html_m1f1de136.gif

1

0

0

1


Логическое И (логическое умножение или конъюнкция) – это сложное логическое выражение, которое считается истинным в том и только том случае, когда оба простых выражения являются истинными, во всех остальных случаях данное сложное выражение ложно. Конъюнкцию высказываний hello_html_mcd9c74f.gif и hello_html_54b57ca0.gif обозначают: hello_html_5e33c31a.gif, а иногда пишут просто hello_html_m45c10600.gif. Высказывания в составе конъюнкции соединены союзом «и». Определение конъюнкции может быть записано в виде таблицы истинности, в которой для каждого из четырех возможных наборов значений исходных высказываний hello_html_mcd9c74f.gifи hello_html_54b57ca0.gif задается соответствующее значение конъюнкции hello_html_5e33c31a.gif:

hello_html_mcd9c74f.gif

hello_html_54b57ca0.gif

hello_html_5e33c31a.gif

1

1

1

1

0

0

0

1

0

0

0

0


Определение конъюнкции двух высказываний естественным образом распространяется на любое конечное число составляющих: конъюнкция А1 & A2 & A3 &...& AN истинна тогда и только тогда, когда истинны все высказывания А1, A2, A3, ...AN (а, следовательно, ложна, когда ложно хотя бы одно из этих высказываний) [1].

Логическое ИЛИ (логическое сложение или дизъюнкция) – это сложное логическое выражение, которое истинно, если хотя бы одно из простых логических выражений истинно и ложно тогда и только тогда, когда оба простых логических выражения ложны. Дизъюнкцию высказываний hello_html_mcd9c74f.gif и hello_html_54b57ca0.gif мы обозначим символом hello_html_265a6ee2.gif и будем читать: hello_html_mcd9c74f.gif или hello_html_54b57ca0.gif. Определение дизъюнкции может быть записано в виде таблицы истинности:

hello_html_mcd9c74f.gif

hello_html_54b57ca0.gif

hello_html_265a6ee2.gif

1

1

1

1

0

1

0

1

1

0

0

0


Определение дизъюнкции двух высказываний естественным образом распространяется на любое конечное число составляющих: дизъюнкция А1 hello_html_m24ce8d55.gif А2 hello_html_m24ce8d55.gif А3 hello_html_m24ce8d55.gif...hello_html_m24ce8d55.gif АN истинна тогда и только тогда, когда истинно хотя бы одно из высказываний А1, А2, А3, ..., АN (а следовательно, ложна, когда ложны все эти высказывания).

Операции И, ИЛИ, НЕ образуют полную систему логических операций, из которой можно построить сколь угодно сложное логическое выражение. Но помимо них существуют и другие логические операции.

Логическое следование (импликация) – это сложное логическое выражение, которое истинно во всех случаях, кроме как из истины следует ложь. То есть данная логическая операция связывает два простых логических выражения, из которых первое является условием (hello_html_mcd9c74f.gif), а второе (hello_html_54b57ca0.gif) является следствием. Обозначим импликацию символом hello_html_1b730b13.gif и запись «hello_html_m1d268a6d.gif» будем читать: «Из hello_html_mcd9c74f.gif следует hello_html_54b57ca0.gif».

Запишем это определение в виде таблицы истинности:


hello_html_mcd9c74f.gif

hello_html_54b57ca0.gif

hello_html_m1d268a6d.gif

1

1

1

1

0

0

0

1

1

0

0

1


Высказывание «Если hello_html_mcd9c74f.gif, то hello_html_54b57ca0.gif» с логической точки зрения имеет тот же смысл, что и высказывание «неверно, что hello_html_mcd9c74f.gif истинно и hello_html_54b57ca0.gif ложно». Это означает, что функцию импликации можно заменить комбинацией двух функций (отрицания и конъюнкции).

Логическое тождество (эквиваленция) – это сложное логическое выражение, которое является истинным тогда и только тогда, когда оба простых логических выражения имеют одинаковую истинность. Обозначают эквиваленцию символом hello_html_39bcdcee.gif и запись «hello_html_m2b4ab587.gif» читают «hello_html_mcd9c74f.gif эквивалентно hello_html_54b57ca0.gif», или «hello_html_mcd9c74f.gif равносильно hello_html_54b57ca0.gif», или «hello_html_mcd9c74f.gif, если и только если hello_html_54b57ca0.gif», «hello_html_mcd9c74f.gif тогда и только тогда, если hello_html_54b57ca0.gif». Определение эквиваленции может быть записано в виде таблицы истинности:

hello_html_mcd9c74f.gif

hello_html_54b57ca0.gif

hello_html_m2b4ab587.gif

1

1

1

1

0

0

0

1

0

0

0

1


Логические функции и их преобразование

Логическая функция – это функция логических переменных, которая может принимать только два значения: 0 или 1. В свою очередь, сама логическая переменная (аргумент логической функции) тоже может принимать только два значения: 0 или 1 [1].

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

Для операций конъюнкции, дизъюнкции и инверсии определены законы, позволяющие производить тождественные (равносильные) преобразования логических выражений [1, 11]:

  1. закон двойного отрицания: hello_html_m74518b35.gif;

  2. коммутативность конъюнкции: hello_html_395b5c3f.gif;

  3. коммутативность дизъюнкции: hello_html_m42e26ff2.gif;

  4. ассоциативность конъюнкции: hello_html_1825baf5.gif;

  5. ассоциативность дизъюнкции: hello_html_m55ff9384.gif;

  6. дистрибутивность конъюнкции относительно дизъюнкции:
    hello_html_b431bef.gif
    ;

  7. дистрибутивность дизъюнкции относительно конъюнкции:
    hello_html_m70eb919.gif;

  8. законы идемпотентности: hello_html_5868a63.gif,
    hello_html_m1f609e91.gif;

  9. закон исключенного третьего: hello_html_m58163da9.gif;

  10. закон непротиворечия: hello_html_m43e0896f.gif;

  11. законы поглощения 1: hello_html_m787afacc.gif,
    hello_html_m5875bb9a.gif,
    hello_html_m1523783c.gif,
    hello_html_m472b33b8.gif;

  12. законы де Моргана: hello_html_m3267a654.gif,
    hello_html_dafeea5.gif;

  13. законы склеивания: hello_html_m2ac2157c.gif,
    hello_html_5e7a8ebb.gif
    ;

  14. замена импликации: hello_html_339d5219.gif;

  15. правила Порецкого: hello_html_m5b00264f.gif,

hello_html_3d706550.gif;

  1. правила свертки: hello_html_md5bc1ca.gif,

hello_html_5fde40be.gif.

Основываясь на законах, можно выполнять упрощение сложных логических выражений.

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

Прежде чем перейти к СДНФ и СКНФ введем некоторые понятия.

Элементарной конъюнкцией называется конъюнкция нескольких переменных, взятых с отрицанием или без отрицания, причём среди переменных могут быть одинаковые [15].

Элементарной дизъюнкцией называется дизъюнкция нескольких переменных, взятых с отрицанием или без отрицания, причём среди переменных могут быть одинаковые [15].

Всякую дизъюнкцию элементарных конъюнкций называют дизъюнктивной нормальной формой, то есть ДНФ [15].

Например, выражение hello_html_1f9d6bb9.gif является ДНФ.

Всякую конъюнкцию элементарных дизъюнкций называют конъюнктивной нормальной формой, то есть КНФ [15].

Например, выражение hello_html_678d4374.gifявляется КНФ.

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

Например, выражение hello_html_58a219b.gifявляется ДНФ, но не является СДНФ; выражение hello_html_m4c6e24d0.gifявляется СДНФ.

Совершенной КНФ (СКНФ) называется КНФ, в которой нет равных элементарных дизъюнкций, и все они содержат одни и те же переменные, причём каждую переменную только один раз (возможно с отрицанием) [15].

Например, выражение hello_html_m6e9f39f6.gif.

Приведу алгоритмы переходов от одной формы к другой. Естественно, что в конкретных случаях (при определенном творческом подходе) применение алгоритмов бывает более трудоемким, чем простые преобразования, использующие конкретный вид данной формы [3]:

  1. переход от произвольного задания функции к ДНФ

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

  1. законы идемпотентности: hello_html_5868a63.gif,
    hello_html_m1f609e91.gif;

  2. закон исключенного третьего: hello_html_m58163da9.gif;

  3. закон непротиворечия: hello_html_m43e0896f.gif;

Например:


hello_html_3989dd87.gif


  1. переход от ДНФ к КНФ

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

hello_html_m7466d11d.jpg


Вhello_html_m711cc7d.jpgторой способ перехода от ДНФ к КНФ – использование дистрибутивного закона:


  1. переход от КНФ к ДНФ

Этот переход осуществляется простым раскрытием скобок (при этом опять-таки используется правило поглощения):

hello_html_m667eadf7.jpg


  1. переход от КНФ к СКНФ

Эhello_html_m4f53564e.jpgтот переход осуществляется способом, аналогичным предыдущему: если в простой дизъюнкции не хватает какой-то переменной, например, z, то добавляем в нее выражение hello_html_47972f35.gif (это не меняет самой дизъюнкции), после чего раскрываем скобки с использованием распределительного закона:

  1. переход от ДНФ к СДНФ

Если в какой-то простой конъюнкции недостает переменной, например, z, то умножаем неполную конъюнкцию на выражение вида hello_html_3f15643f.gif, после чего раскрываем скобки (при этом повторяющиеся дизъюнктные слагаемые не пишем). Например:

  1. пhello_html_3a459b51.jpgереход к СДНФ и СКНФ с помощью таблиц истинности

Для получения СДНФ и СКНФ из таблиц истинности необходимо выполнить следующие 4 пункта алгоритма [15]:

СДНФ

СКНФ


  1. Конструирование СДНФ и СКНФ начинается с таблицы истинности.

  2. Отметим те строки таблицы, выходы которых равны

1

0


  1. Выписываем для каждой отмеченной строки комбинацию переменных через знак

конъюнкция (&)

дизъюнкция (V)


Знаки операции отрицания расставляем следующим образом:

если переменная равна 1, то запишем саму эту переменную, если же она равна 0, то запишем ее отрицание.

если переменная равна 0, то запишем саму эту переменную, если же она равна 1, то запишем ее отрицание.


  1. Все полученные выражения связываем операцией

дизъюнкции

конъюнкции


Получив СДНФ или СКНФ, можно составить электронную схему, реализующую данную логическую функцию. Для ее постороения требуется 3 логических элемента [9, 18]:


инвертор

hello_html_77714e28.jpg

конъюнктор

hello_html_m3311b2eb.jpg

дизъюнктор

hello_html_m32ce4de7.jpg


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

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

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

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

Существуют два направления минимизации:

  1. Кратчайшая форма записи (при этом получаются кратчайшие формы КДНФ, ККНФ, КПНФ);

  2. Получение минимальной формы записи (получение минимального числа символов для записи всей функции сразу).

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

Для минимизации функций алгебры логики был разработан ряд методов:

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

  2. метод минимизации логических функций при помощи карт Карно;

  3. метод Квайна-Мак-Класки;

  4. метод Блейка-Порецкого;

  5. метод Петрика и другие.

Остановимся более подробно на первых двух методах.

Метод непосредственных преобразований логических функций

Одним из простых методов минимизации является метод непосредственных преобразований, который осуществляется с использованием основных теорем алгебры логики [11].

При применении данного метода:

  1. Записываются СДНФ логических функций,

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

hello_html_m6f228515.gif


По отношению к соседним термам применяется закон склейки.

Термы, образованные при склеивании называются импликантами.

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

hello_html_m20da718e.gif



Пhello_html_m3c97d93.gifолученная в результате минимизации функция называется тупиковой.

Пусть дана функция

Минимизируем ее описанным выше методом. Для этого добавим еще одно слагаемое hello_html_m2097708e.gifи воспользуемся законами склеивания [12].

hello_html_19b2d4e2.gif


Пhello_html_7e08643d.gifолучили минимальную функцию


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


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

Карта Карно или карта (диаграмма) Вейча – графический способ минимизации функций алгебры логики.

Карты Карно удобны при небольшом числе переменных.

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

Нhello_html_33c9b633.jpgа рис. 1 представлены карты Вейча для двух, трех и четырех переменных соответственно [12].




рис. 1

Расположение групп переменных x не имеет значения, необходимо лишь, чтобы каждая клетка отличалась от любой соседней лишь на одну переменную. Согласно принятой форме построения карт соседними также считаются клетки первой и последней строк, клетки первого и последнего столбцов. Число клеток карты равно числу возможных комбинаций значений переменных (термов) и в каждую клетку записывается значение логической функции, соответствующее данному набору переменных. Если какая-то из возможных комбинаций присутствует в совершенной дизъюнктивной нормальной форме (СДНФ) записи функции, то в соответствующей клетке карты Карно ставится «1». Если какого-то терма в полученной функции нет, то в соответствующей клетке карты Карно ставится «0» [12].

Нhello_html_m3c97d93.gifапример, рассмотренная в предыдущем примере функция


зhello_html_m2b2f853.jpgаданная таблицей истинности (рис. 2 а), может быть минимизирована и с помощью карт Карно. Карта Карно для нее будет иметь вид, показанный на рис. 2 б.





рис. 2

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

Тhello_html_m6152fb0.pngак в первой строке карты Карно (см. рис. 2 б) переменная х, встречается в комбинации с х1 и х2, которые дополняют друг друга:


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

Аналогично, группируя две соседние клетки в левом столбце (контур на рис. 2 б) и исключая отличающиеся переменные, получим упрощенное выражение – х2.

Полученные упрощенные выражения объединяют с помощью операции ИЛИ.

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


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

Допускается также иметь несколько групп перекрывающихся клеток, как в только что рассмотренном примере.

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

Для исключения n переменных общее число группируемых клеток должно быть равно 2n. Так, для исключения одной переменной требуется объединить две соседние клетки, а для исключения трех переменных уже требуется объединить восемь соседних клеток [12].

Таким образом, для того чтобы получить минимизированную логическую функцию, необходимо сгруппировать все соседние клетки карты Карно, содержащие 1, а затем объединить полученные группы с помощью операции ИЛИ. Клетки, содержащие 1, которые не удалось объединить с другими клетками, образуют в минимизированной логической функции самостоятельные члены, каждый из которых содержит все переменные [12].

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

Тhello_html_41afe9ab.gifак, карта Вейча для логической функции


приведена на рисунке 3.



hello_html_m7114cc03.jpg

рис. 3

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

Уhello_html_764032c1.gifпрощенное выражение логической функции имеет вид


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

Рhello_html_57310a25.gifассмотрим пример минимизации логической функции

Карта Карно для этой функции представлена на рисунке 4:

hello_html_7ed6f32a.jpg

рис. 4

Группируемые ячейки обведены двумя контурами. Нижний контур дает возможность исключить одну переменную х3 и после этого в нем остается член hello_html_m38031a30.gif.

В верхнем контуре можно исключить две переменные (х2 и х4) и после этого в нем остается член hello_html_4d4a5f9d.gif. Упрощенное булево выражение логической функции имеет вид

hello_html_m4045324f.gif

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

hello_html_m18b86c4.jpg

рис. 5

Булево выражение этой функции имеет вид

hello_html_6e21efe3.png

Четыре угловые клетки можно объединить в одну группу. Это объединение позволяет исключить две переменные (х1 и х2) и получить член hello_html_2522a5b9.gif.

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

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

Таким образом, мы получим минимизированную логическую функцию

hello_html_m31b25df5.gif


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

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

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


  1. Упростить, используя карты Карно для функции 2 переменных:


  1. hello_html_c6c1f43.gif

Кhello_html_2d9f6146.gifарта Карно (диаграмма Вейча) для этой функции будет иметь вид:

В первой строке можно исключить переменную х2 и получить упрощенное выражение х1.

Во втором столбце можно исключить переменную х1 и получить упрощенное выражение hello_html_6ac57536.gif.

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

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


  1. hello_html_30d3988c.gif

Дhello_html_737c27b2.gifиаграмма Вейча для этой функции будет иметь вид:

Вhello_html_m2d252bd1.gif первом столбце можно исключить переменную х1 и получить упрощенное выражение х2.

Во второй строке можно исключить переменную hello_html_182f8885.gif и получить упрощенное выражение hello_html_m752021e5.gif.

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

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


  1. Упростить, используя карты Карно для функции 3 переменных:


  1. hello_html_m708d6682.gif

Диаграмма Вейча для этой функции будет иметь вид:

Вhello_html_2142fff2.gif первой строке можно исключить переменную х3 и получить упрощенное выражение hello_html_523f6cab.gif.

Во второй строке можно исключить переменную х3 и получить упрощенное выражение hello_html_m74fd8276.gif.

В последнем столбце можно исключить переменную х1 и получить упрощенное выражение hello_html_m16e1337a.gif.

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

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


  1. hello_html_m569e5109.gif

Дhello_html_3ee476ff.jpgиаграмма Вейча для этой функции будет иметь вид:

В первой строке можно исключить переменную х3 и получить упрощенное выражение hello_html_5f0de96.gif и переменную х2 и получить упрощенное выражение hello_html_m252d1e7a.gif.

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

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

Нами был найден и второй способ минимизации данной функции.

Тогда диаграмма Вейча для этой функции будет иметь вид:

В первой строке можно исключить переменную х3 и получить упрощенное выражение hello_html_m1aa16149.gif.

Вhello_html_1d9f67b8.png первой строке остается выражение hello_html_38aeba3e.gif.

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

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

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


Это значит, что соседние клетки можно группировать разными способами, главное, не забывать основное правило: для исключения n переменных общее число группируемых клеток должно быть равно 2n.


  1. hello_html_526f8636.gif

Дhello_html_18f57902.jpgиаграмма Вейча для этой функции будет иметь вид:

В

1 1 0 0

hello_html_m4ab43bb8.gifhello_html_m2fb8fe3d.gif первой строке можно исключить переменную х3 и получить упрощенное выражение hello_html_5f0de96.gif.

В

0 1 0 0

о втором столбце можно исключить переменную х1 и получить упрощенное выражение hello_html_m5023da42.gif.

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

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


  1. hello_html_5c3032a0.gif

Диаграмма Вейча для этой функции будет иметь вид:

Вhello_html_14d34565.png первой строке можно исключить переменную х3 и получить упрощенное выражение hello_html_5f0de96.gif.

Во второй строке можно исключить переменную х3 и получить упрощенное выражение hello_html_m43d93ce2.gif.

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

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

hello_html_3fdb8af9.gif



Диаграмма Вейча для этой функции будет иметь вид:

Вhello_html_m15085f20.png первом и последнем столбце можно исключить переменные х1 и х2 и получить упрощенное выражение hello_html_a2dc5bb.gif.

Во второй строке можно исключить переменную х2 и получить упрощенное выражение hello_html_34ac446.gif.

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

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

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


  1. Упростить, используя карты Карно для функции 4 переменных:

hello_html_m699cb9a.gif



Дhello_html_589382d2.pngиаграмма Вейча для этой функции будет иметь вид:

Группируем угловые клетки, в которых можно исключить переменные х1 и х2 и получить упрощенное выражение hello_html_m424a5ec6.gif.

В первом столбце можно исключить переменную х1 и получить упрощенное выражение hello_html_72801e0f.gif.

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

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

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


hello_html_3882a85a.gif



Диаграмма Вейча для этой функции будет иметь вид:

Во второй и третьей строке группируем четыре центральные соседние клетки, в которых можно исключить переменные х1 и х2 и получить упрощенное выражение hello_html_m22c8e4db.gif.

Вhello_html_735b0d02.png первом и последнем столбце третьей строки можно исключить переменную х2 и получить упрощенное выражение hello_html_m2e2189ed.gif.

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

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

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


hello_html_5178c123.gif



Диаграмма Вейча для этой функции будет иметь вид:

Вhello_html_m6028da07.png первой строке группируем две соседние клетки, в которых можно исключить переменную х2 и получить упрощенное выражение hello_html_47d06c1d.gif.

В последней строке группируем четыре соседние клетки, в которых можно исключить переменные х2 и х3 и получить упрощенное выражение hello_html_m430445c0.gif.

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

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

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


hello_html_2b2fb350.gif



Дhello_html_522a06b0.pngиаграмма Вейча для этой функции будет иметь вид:

В последнем столбце группируем угловые клетки, в которых можно исключить переменную х1 и получить упрощенное выражение hello_html_m4ebd21a8.gif.

В двух последних строках группируем четыре соседние клетки, в которых можно исключить переменные х2 и х4 и получить упрощенное выражение hello_html_m6cbabe61.gif.

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

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


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

Заключение

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

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

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

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

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

Мною было подробно рассмотрено 2 метода минимизации логических функций:

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

  2. метод минимизации с помощью диаграмм Вейча (карт Карно).

Первый метод получил широкое распространение даже в школьных учебниках информатики (например, учебники 10-11 класса Н. Угриновича [20, 21], Л. Щауцуковой [22]), поскольку является одним из простых методов упрощения функций алгебры логики. Задания, представленные в учебниках указанных авторов, достаточно разнообразны:

  • упростить логическую формулу с помощью законов алгебры логики;

  • по заданной функции построить логическую схему;

  • упростить переключательную схему;

  • доказать с помощью таблицы истинности логическое выражение;

  • построить для данной функции таблицу истинности.

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

Данная тема имеет практическое значение в микроэлектронике. Кроме того, ЕГЭ по информатике и ИКТ содержит некоторое количество заданий, связанных с алгеброй логики, которые мы разделили на 4 группы [4].

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

Вторая группа – задания на нахождение фрагментов таблиц истинности, соответствующих данному выражению.

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

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

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

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

Список литературы

  1. Гаврюкова Г. А. Логика в информатике [Электронный ресурс]. – Режим доступа: http://gmoi.narod.ru/s/u/logic.htm (21 окт. 2010).

  2. Ивин А. А. Логика : Учебное пособие. – 2-е изд. – М.: Знание, 1998. – 233 с.

  3. Игошин В. И. Математическая логика и теория алгоритмов: Учебное пособие для студ. высш. учеб. заведений. – 2-е изд., стер. – М.: Академия, 2008. – 448 с.

  4. Информатика и ИКТ. Подготовка к ЕГЭ-2009. Вступительные испытания. / Под ред. Ф. Ф. Лысенко. – Ростов н/Д: Легион-М, 2009. – 208 с.

  5. Информатика : Учебник / Б. В. Соболь [и др.]. – 3-е изд., доп. и перераб. – Ростов н/Д: Феникс, 2007. – 446 с.

  6. Информатика : Учебное пособие / А. В. Могилев, Н. И. Пак, Е. К. Хеннер. – 3-е изд. – М.: Академия, 2004. – 848 с.

  7. Калабеков Б. А. Цифровые устройства и микропроцессорные системы: Учебник для техникумов связи. – М.: Горячая линия – Телеком, 2000. – 336 с.

  8. Каймин В. А. Информатика : Учебник. – 2-е изд., перераб. и доп. – М.: ИНФРА-М, 2001. – 272 с.

  9. Коваленко А. А, Петропавловский М. Д. Основы микроэлектроники: Учебное пособие. – М.: Академия, 2006. – 240 с.

  10. Львовский М. Б. Методическое пособие по информатике для учащихся 9-11 классов, изучающих IBM PC [Электронный ресурс]. – Режим доступа: http://markbook.chat.ru/book/oglavlen.htm (19 сент. 2010).

  11. Математические основы информатики. Элективный курс : Учебное пособие / Е. В. Андреева, Л. Л. Босова, И. Н. Фалина. – М.: БИНОМ. Лаборатория знаний, 2005. – 328 с.

  12. Минимизация логических функций [Электронный ресурс]. – Режим доступа: http://www.reltehnika.ru/book/2_1.html (19 авг. 2010).

  13. Основы микроэлектроники : Учебное пособие для вузов / Н. А. Аваев, Ю. Е. Наумов, В. Т. Фролкин. – М.: Радио и связь, 1991. – 288 с.: ил.

  14. Практикум по информатике и информационным технологиям / Н. Д. Угринович, Л. Л. Босова, Н. И. Михайлова. – 2-е изд., испр. – М.: БИНОМ. Лаборатория знаний, 2004. – 394 с.

  15. Прикладная математика : Пособие / И. Н. Ревчук, В. К. Пчельник. – Гродно: ГрГУ им. Я. Купалы, 2007. – 128 с.

  16. Рабкин Е. Л., Фарфоровская Ю. Б. Дискретная математика: булевы функции и элементы теории графов: Методические указания и контрольные задания [Электронный ресурс]. – Режим доступа: http://dvo.sut.ru/libr/himath/w163rabk/index.htm (27 авг. 2010).

  17. Савельев А. Я. Основы информатики : Учебник для вузов. – М.: МГТУ им. Н. Э. Баумана, 2001. – 328 с., ил.

  18. Степаненко И. П. Основы микроэлектроники : Учебное пособие для вузов. – 2-е изд., перераб. и доп. – М.: Лаборатория Базовых Знаний, 2001. – 488 с.

  19. Теория и методика обучения информатике : Учебник / [М. П. Лапчик, И. Г. Семакин, Е. К. Хеннер, М. И. Рагулина и др.]; под ред. М. П. Лапчика. – М.: Академия, 2008. – 592 с.

  20. Угринович Н. В. Информатика и ИКТ. 10 класс. Профильный уровень. – 3-е изд., испр. – М.: Бином. Лаборатория знаний, 2008. – 387 с.

  21. Угринович Н. В. Информатика и информационные технологии : Учебник для 10-11 классов. – М.: БИНОМ. Лаборатория знаний, 2003. – 512 с.

  22. Шауцукова Л. З. Информатика 10 – 11. – М.: Просвещение, 2004. – 420 с.

1 Канонические формы – запись формы функции по единым правилам.


Название документа автор.doc

Мулдашева Светлана Викторовна

учитель информатики

без категории

Свято-Покровская православная классическая гимназия г. Саратова

г. Саратов

e-mail: shevcova_sv@mail.ru, muldasheva.sv@yandex.ru



Методы минимизации логических функций
  • Информатика
Описание:

Содержание

Введение

  • Логические основы функционирования ЭВМ
    • Элементы математической логики
    • Логические функции и их преобразование
  • Минимизация логических функций
    • Метод непосредственных преобразований логических функций
    • Метод минимизации логических функций при помощи карт Карно
    • Минимизация функций алгебры логики описанными методами

Заключение

Список литературы



Введение

Люди, далекие от техники, часто смотрят на ЭВМ и другие цифровые электронные устройства как на нечто таинственное и непостижимое. Тем не менее, все эти устройства работают в строгом соответствии с четкими логическими законами. Знание и понимание этих законов помогает в общении с компьютером и другими цифровыми устройствами.
Принципы построения схемы цифрового устройства задается логическими функциями. Сложность логической функции, а отсюда сложность и стоимость реализующей ее схемы (цепи), пропорциональны числу логических операций и числу вхождений переменных или их отрицаний. В принципе любая логическая функция может быть упрощена непосредственно с помощью аксиом и теорем логики, но, как правило, такие преобразования требуют громоздких выкладок.
К тому же процесс упрощения булевых выражений не является алгоритмическим. Поэтому более целесообразно использовать специальные алгоритмические методы минимизации, позволяющие проводить упрощение функции более просто, быстро и безошибочно.
Упрощенная функция будет содержать меньше операций и комбинаций аргументов, а значит и схема, реализующая функцию, будет содержать меньше элементов, т.е. будет дешевле и надежнее.
В связи с этим минимизация логических функций особенно актуальна.
Целью работы является изучение методов минимизации функций алгебры логики.
Объектом работы стал процесс минимизации логических функций.
Предмет исследования – методы минимизации логических функций и методика преподавания этой темы в профильных классах.
Задачи исследования:

  1. изучить основные элементы математической логики;
  2. исследовать методы минимизации логических функций;
  3. подобрать задачи для самостоятельной работы;
  4. решить описанными методами подобранные задачи.

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

Автор Мулдашева Светлана Викторовна
Дата добавления 24.02.2012
Раздел Информатика
Подраздел
Просмотров 5733
Номер материала 1449
Скачать свидетельство о публикации

Оставьте свой комментарий:

Введите символы, которые изображены на картинке:

Получить новый код
* Обязательные для заполнения.


Комментарии:

↓ Показать еще коментарии ↓