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

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

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

Метод диаграмм Вейча, усовершенствованный Карно, применяется в случае, если число аргументов ФАЛ не больше 5–6. Карты Карно .

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

Карты Карно можно рассматривать как определенную плоскую развертку n- мерного булева куба. Перышкин Физика Учебник 8 подробнее. Карты Карно были изобретены в 1. Эдвардом В. Вейчем и усовершенствованы в 1. Морисом Карно, физиком из «Bell Labs», и были призваны помочь упростить цифровые электронные схемы. В карту Карно булевы переменные передаются из таблицы истинности и упорядочиваются с помощью кода Грея, в котором каждое следующее число отличается от предыдущего только одним разрядом.

Каждая клетка диаграммы соответствует набору переменных булевой функции в ее таблице истинности. 4.4.1) это соответствие показано, . Построение СКНФ и СДНФ с картами Карно (Вейча). Минимизация булевой функций. Построение карты Вейча-Карно Минимизация булевой функции.

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

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

Программа Carno Minimizer предназначена для минимизации логических функций методом карт Карно и Диаграм Вейча. Программа позволяет . Карты карно (схемы Вейча) это наглядное представление логической функции в виде карты, которая удобна для оптимизации. С каждой из сторон . Минимизацию логических функций можно провести, используя диаграммы Вейча (или аналогичный метод карт Карно). Диаграмма Вейча для функции F . Минимизация логических функций при помощи карт Карно. Он изобрел «диаграммы Вейча», которые кстати намного удобнее для .

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

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

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

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

Для таблиц 5 и более переменных нужно учитывать также, что квадраты 4х. Карта Карно может быть составлена для любого количества переменных, однако удобно работать при количестве переменных не более пяти. По сути Карта Карно — это таблица истинности составленная в 2- х мерном виде. Образец Заполнения Формы Уведомления О Втором Гражданстве.

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

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

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