Схемотехника. Минимизация логических функций / Geektimes. Минимизация логических функций является одной из типовых задач в процессе обучения схемотехнике. Посему считаю, что такая статья имеет место быть, надеюсь Вам понравится. Зачем это нужно? В принципе любая логическая функция может быть упрощена непосредственно с помощью аксиом и теорем логики, но, как правило, такие преобразования требуют громоздких выкладок. К тому же процесс упрощения булевых выражений не является алгоритмическим. Поэтому более целесообразно использовать специальные алгоритмические методы минимизации, позволяющие проводить упрощение функции более просто, быстро и безошибочно.
Построение таблицы истинности и карт Карно по заданным входным наборам. Программа «Минимизация логических функций» разработана в среде . Минимизация логических функций является одной из типовых задач в процессе. Инструкция Для Алфавитного Каталога Библиотеки. Минимизация логических функций при помощи карт Карно. А еще неплохо в учебных целях самому написать такую программу.
Данная программа призвана облегчить минимизацию булевой функции методом карт Карно. Карты Карно. Программное обеспечение. Подробное решение с оформлением в Word. Построение СКНФ и СДНФ с картами Карно (Вейча). Минимизация булевой функций методом Квайна.
К таким методам относятся, например, метод Квайна, метод карт Карно, метод испытания импликант, метод импликантных матриц, метод Квайна- Мак- Класки и др. Эти методы наиболее пригодны для обычной практики, особенно минимизация логической функции с использованием карт Карно. Метод карт Карно сохраняет наглядность при числе переменных не более шести. В тех случаях, когда число аргументов больше шести, обычно используют метод Квайна- Мак- Класки.
В процессе минимизации той или иной логической функции, обычно учитывается, в каком базисе эффективнее будет реализовать ее минимальную форму при помощи электронных схем. Минимизация логических функций при помощи карт Карно. Карта Карно — графический способ минимизации переключательных (булевых) функций, обеспечивающий относительную простоту работы с большими выражениями и устранение потенциальных гонок. Представляет собой операции попарного неполного склеивания и элементарного поглощения. Карты Карно рассматриваются как перестроенная соответствующим образом таблица истинности функции. Карты Карно можно рассматривать как определенную плоскую развертку n- мерного булева куба. Карты Карно были изобретены в 1.
Эдвардом В. Вейчем и усовершенствованы в 1. Морисом Карно, физиком из «Bell Labs», и были призваны помочь упростить цифровые электронные схемы. В карту Карно булевы переменные передаются из таблицы истинности и упорядочиваются с помощью кода Грея, в котором каждое следующее число отличается от предыдущего только одним разрядом. Основным методом минимизации логических функций, представленных в виде СДНФ или СКНФ является операция попарного неполного склеивания и элементарного поглощения. Операция попарного склеивания осуществляется между двумя термами (членами), содержащими одинаковые переменные, вхождения которых (прямые и инверсные) совпадают для всех переменных, кроме одной.
В этом случае все переменные, кроме одной, можно вынести за скобки, а оставшиеся в скобках прямое и инверсное вхождение одной переменной подвергнуть склейке. Например: Возможность поглощения следует из очевидных равенств.
Таким образом, главной задачей при минимизации СДНФ и СКНФ является поиск термов, пригодных к склейке с последующим поглощением, что для больших форм может оказаться достаточно сложной задачей. Карты Карно предоставляют наглядный способ отыскания таких термов. Как известно, булевы функции N переменных, представленные в виде СДНФ или СКНФ могут иметь в своём составе 2. N различных термов. Все эти члены составляют некоторую структуру, топологически эквивалентную N–мерному кубу, причём любые два терма, соединённые ребром, пригодны для склейки и поглощения. На рисунке изображена простая таблица истинности для функции из двух переменных, соответствующий этой таблице 2- мерный куб (квадрат), а также 2- мерный куб с обозначением членов СДНФ и эквивалентная таблица для группировки термов: В случае функции трёх переменных приходится иметь дело с трёхмерным кубом. Это сложнее и менее наглядно, но технически возможно.
На рисунке в качестве примера показана таблица истинности для булевой функции трёх переменных и соответствующий ей куб. Как видно из рисунка, для трёхмерного случая возможны более сложные конфигурации термов. Например, четыре терма, принадлежащие одной грани куба, объединяются в один терм с поглощением двух переменных: В общем случае можно сказать, что 2. K термов, принадлежащие одной K–мерной грани гиперкуба, склеиваются в один терм, при этом поглощаются K переменных. Для упрощения работы с булевыми функциями большого числа переменных был предложен следующий удобный приём. Куб, представляющий собой структуру термов, разворачивается на плоскость как показано на рисунке.
Таким образом появляется возможность представлять булевы функции с числом переменных больше двух в виде плоской таблицы. При этом следует помнить, что порядок кодов термов в таблице (0. Аналогичным образом можно работать с функциями четырёх, пяти и более переменных.
Создать книгу · Скачать как PDF · Версия для печати . Карты Карно. Минимизация логических функций.
Примеры таблиц для N=4 и N=5 приведены на рисунке. Для этих таблиц следует помнить, что соседними являются клетки, находящиеся в соответственных клетках крайних столбцов и соответственных клетках верхней и нижней строки. Для таблиц 5 и более переменных нужно учитывать также, что квадраты 4х. Карта Карно может быть составлена для любого количества переменных, однако удобно работать при количестве переменных не более пяти.
По сути Карта Карно — это таблица истинности составленная в 2- х мерном виде. Благодаря использованию кода Грея в ней верхняя строка является соседней с нижней, а правый столбец соседний с левым, т. На пересечении строки и столбца проставляется соответствующее значение из таблицы истинности. После того как Карта заполнена, можно приступать к минимизации.
Если необходимо получить минимальную ДНФ, то в Карте рассматриваем только те клетки которые содержат единицы, если нужна КНФ, то рассматриваем те клетки которые содержат нули. Сама минимизация производится по следующим правилам (на примере ДНФ): Объединяем смежные клетки содержащие единицы в область, так чтобы одна область содержала 2n (n целое число = 0. Берём следующую область, выполняем то же самое что и для первой, и т. Конъюнкции областей объединяем дизъюнкцией. Например(для Карт на 2- ве переменные). Для КНФ всё то же самое, только рассматриваем клетки с нулями, не меняющиеся переменные в пределах одной области объединяем в дизъюнкции (инверсии проставляем над единичными переменными), а дизъюнкции областей объединяем в конъюнкцию.
На этом минимизация считается законченной. Так для Карты Карно на рис. ДНФ будет иметь вид.
Карты Карно. Минимизация логических функций. Завантаження списк.
Теперь программа умеет находить ДНФ и КНФ. Так же усовершенствованы некоторые алгоритмы. Не забываем так же скачивать аналогичную . Совершенная конъюнктивная нормальная форма · Минимизация логических функций · Метод непосредственных преобразований. Карты Карно.