naf-st.ru naf-st.ru naf-st.ru naf-st.ru
 
Поиск по сайту
 

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


Основы алгебры логики К содержанию Интегрирующие и дифференцирующие цепи
Page copy protected against web site content infringement by Copyscape

Минимизация логических функций необходима для упрощения сложных выражений этих самых функций, например, сложные логические функции могут отображаться в две-три и более строк (допустим, на листе формата А4). Понятно, что сразу приступать к схемной реализации таких функций по большому счету тупо. Минимизировать логические функции можно с помощью всяких правил и законов алгебры логики (про это здесь), можно с помощью так называемых карт Карно. Представление функций с помощью карт Карно очень удобно, когда число переменных невелико (меньше или равно 6). По сути карта Карно - это табличка, которая содержит 2n клеток, где n - число переменных (n=1, 2, 3 ... n). К каждой клетке содержится логическое произведение переменных или их инверсий. Одни переменные располагаются по горизонтали, другие - по вертикали. Изображаться карты Карно могут по-разному. Например, так:

x3x4 x1x2
00 01 10 11
00        
01        
10        
11        

Или так:


Изображение карты Карно

Что касается первой таблички, первый знак (0 или 1) относится к первому символу (x1 или x3). Второй знак, соответственно, ко второму символу. Т. е., если в самой нижней правой ячейке стоит 1, то функция записывается x2x4. Во втором варианте вертикальные и горизонтальные черточки напротив ячеек означают, что переменная перекрывает эти ячейки, т. е. x1 перекрывает две верхние стрроки, x2 - два верхних столбца и т. п. И так, и так правильно, но лично мне более предпочтителен второй вариант.

Заполняются карты Карно следующим образом. Допустим есть некая функция из четырех переменных. Карта Карно будет содержать 16 клеток (24 = 16). Функция вот такая:



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



Как это все делается? Посмотрите, вторая сверху слева ячейка, в ней стоит 1 и этой единице соответствует первое слагаемое в формуле. Единица стоит именно там, поскольку в этой ячейке перекрываются все переменные. Стоит уйти на ячейку влево, вправо, вверх, вниз и одна из переменных уже перекрывать ее не будет. Если одна из переменных с инверсией, что характерно для второго слагаемого, единица ставится с учетом не перекрытия ячейки этой переменной, т. е. для второго слагаемого x1 с инверсией и единица стоит в третьей (сверху) строке третьего столбца. Для четвертого слагаемого с инверсией переменные x2 и x4. Поэтому единица стоит в последней строке (второй столбец). Так проставляются все единицы. В пустых ячейках по идее стоят нули (не показаны для наглядности). Подытожим, если переменная без инверсии, ей соответствует 1, если с инверсией - 0. Суть ясна?

После проставления всех единиц начинается объединение ячеек, в которых стоят эти самые единицы. Объединяются клетки по следующим правилам: число объединяемых клеток 2, 4, 8, 16, 32 и т. д., т. е. 2n, объединять надо как можно больше клеток, а самих объединений должно быть как можно меньше. На рисунке ниже показано, как это делается:



Для тех, кто не понял, единицы в количестве три, пять, шесть, семь, девять, десять и т. п. не объединяются. Если единицы стоят буквой "Т", "Г" и пр., то они также не объединяются.

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



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

Page copy protected against web site content infringement by Copyscape
Основы алгебры логики К содержанию Интегрирующие и дифференцирующие цепи
Новости:




 

copyright © 2003-2018 naf-st.ru, info@naf-st.ru
При полном, либо частичном цитировании материалов сайта naf-st.ru ссылка (для интернет изданий гиперссылка) обязательна!!! Будьте взаимовежливы!
Карта сайта
Поиск по сайту
Помощь
Новости
Обратная связь
Карта сайта
Поиск по сайту
Помощь
Новости
Обратная связь