Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Принципы минимизации⇐ ПредыдущаяСтр 26 из 26 Основным методом минимизации логических функций, представленных в виде СДНФ или СКНФ, является операция попарного неполного склеивания и элементарного поглощения. Операция попарного склеивания осуществляется между двумя термами (членами), содержащими одинаковые переменные, вхождения которых (прямые и инверсные) совпадают для всех переменных, кроме одной. В этом случае все переменные, кроме одной, можно вынести за скобки, а оставшиеся в скобках прямое и инверсное вхождение одной переменной подвергнуть склейке. Например: Аналогично для КНФ: Возможность поглощения следует из очевидных равенств Таким образом, главной задачей при минимизации СДНФ и СКНФ является поиск термов, пригодных к склейке с последующим поглощением, что для больших форм может оказаться достаточно сложной задачей. Карты Карно предоставляют наглядный способ отыскания таких термов. Как известно, булевы функции N переменных, представленные в виде СДНФ или СКНФ, могут иметь в своём составе 2 N различных термов. Все эти члены составляют некоторую структуру, топологически эквивалентную N –мерному кубу, причём любые два терма, соединённые ребром, пригодны для склейки и поглощения. На рисунке изображена простая таблица истинности для функции из двух переменных, соответствующий этой таблице 2-мерный куб (квадрат), а также 2-мерный куб с обозначением членов СДНФ и эквивалентная таблица для группировки термов: В случае функции трёх переменных приходится иметь дело с трёхмерным кубом. Это сложнее и менее наглядно, но технически возможно. На рисунке в качестве примера показана таблица истинности для булевой функции трёх переменных и соответствующий ей куб. Как видно из рисунка, для трёхмерного случая возможны более сложные конфигурации термов. Например, четыре терма, принадлежащие одной грани куба, объединяются в один терм с поглощением двух переменных: В общем случае можно сказать, что 2K термов, принадлежащие одной K–мерной грани гиперкуба, склеиваются в один терм, при этом поглощаются K переменных. Для упрощения работы с булевыми функциями большого числа переменных был предложен следующий удобный приём. Куб, представляющий собой структуру термов, разворачивается на плоскость как показано на рисунке. Таким образом появляется возможность представлять булевы функции с числом переменных больше двух в виде плоской таблицы. При этом следует помнить, что порядок кодов термов в таблице (00 01 11 10) не соответствует порядку следования двоичных чисел, а клетки, находящиеся в крайних столбцах таблицы, соседствуют между собой. Аналогичным образом можно работать с функциями четырёх, пяти и более переменных. Примеры таблиц для N =4 и N =5 приведены на рисунке. Для этих таблиц следует помнить, что соседними являются клетки, находящиеся в соответственных клетках крайних столбцов и соответственных клетках верхней и нижней строки. Для таблиц 5 и более переменных нужно учитывать также, что квадраты 4х4 виртуально находятся друг над другом в третьем измерении, поэтому соответственные клетки двух соседних квадратов 4х4 являются сосоедними, и соответствующие им термы можно склеивать. Описание Карта Карно может быть составлена для любого количества переменных, однако удобно работать при количестве переменных не более пяти. По сути Карта Карно — это таблица истинности составленная в 2-х мерном виде. Благодаря использованию кода Грея в ней верхняя строка является соседней с нижней, а правый столбец соседний с левым, т.о. вся Карта Карно сворачивается в фигуру тор (бублик). На пересечении строки и столбца проставляется соответствующее значение из таблицы истинности. После того как Карта заполнена, можно приступать к минимизации. Если необходимо получить минимальную ДНФ, то в Карте рассматриваем только те клетки которые содержат единицы, если нужна КНФ, то рассматриваем те клетки, которые содержат нули. Сама минимизация производится по следующим правилам (на примере ДНФ): 1. объединяем смежных клеток, содержащих единицы, в область так, чтобы одна область содержала 2 n (n целое число = 0…∞) клеток (помним про то, что крайние строки и столбцы являются соседними между собой), в области не должно находиться клеток, содержащих нули; 2. область должна располагаться симметрично оси(ей) (оси располагаются через каждые четыре клетки); 3. не смежные области, расположенные симметрично оси(ей), могут объединяться в одну; 4. область должна быть как можно больше, а количество областей как можно меньше; 5. области могут пересекаться; 6. возможно несколько вариантов накрытия. Далее берём первую область и смотрим какие переменные не меняются в пределах этой области, выписываем конъюнкцию этих переменных, если неменяющаяся переменная нулевая, проставляем над ней инверсию. Берём следующую область, выполняем то же самое что и для первой, и т. д. для всех областей. Конъюнкции областей объединяем дизъюнкцией. Например (для Карт на 2-ве переменные): Для КНФ всё то же самое, только рассматриваем клетки с нулями, не меняющиеся переменные в пределах одной области объединяем в дизъюнкции (инверсии проставляем над единичными переменными), а дизъюнкции областей объединяем в конъюнкцию. На этом минимизация считается законченной. Так для Карты Карно на рис.1 выражение в формате ДНФ будет иметь вид: В формате КНФ: Так же из ДНФ в КНФ и обратно можно перейти использовав Законы де Моргана.
Список используемой литературы: 1) Виды информации и её свойства. Материал из Викиучебника. - https://ru.wikibooks.org/wiki/Виды_информации_и_её_свойства; 2) 20. Классификация вычислительной техники. Koralexand.ru. Информатика. - http://koralexand.ru/?page_id=117; 3) Шаг 2. Общие сведения об информации. Формы представления информации. Информатика и программирование: Шаг за шагом. Кафедра информационных технологий Курганского Государственного университета. - http://it.kgsu.ru/TI_2/obinf002.html; 4) Учебник по дискретной математике ДНФ, СДНФ, КНФ, СКНФ - http://www.mini-soft.ru/document/diskretnaya-matematika-3; 5) Урок N 16 Логические элементы и логические функции. Элементы математической логики. - http://www.gmcit.murmansk.ru/text/information_science/base/logic/materials/logic2/12/lvov/lvov.htm; 6) Карты Карно. Векторное управление - http://векторное-управление.рф/karty-karno.html; 7) Основные характеристики ЭВМ - http://steam-portal.do.am/publ/ehvm/osnovnye_kharakteristiki_ehvm/2-1-0-4; 8) Законы алгебры логики. DigTeh.ru Цифровая техника в радиосвязи. - http://digteh.ru/digital/AlgLog.php; 9) 3. Методы минимизации функций алгебры логики - http://edu.dvgups.ru/METDOC/GDTRAN/YAT/AT/TEOR_DISK_USTR/METOD/UP_LAB/frame/3.htm; 10) Представление числовых данных в памяти ЭВМ - http://comp-science.narod.ru/Cod/cod.html; 11) Минимизация СКНФ, СДНФ. - http://vsem-dm.narod.ru/24.html.
|