Программа Carno Minimizer предназначена для минимизации логических функций методом карт Карно и Диаграм Вейча. Программа позволяет. Программа минимизации логических функций. Приложение написано на VBScript для работы в Internet Explorer. Большинство других браузеров не. При синтезе однотактных устройств алгебры логики приходится осуществлять минимизацию логической функции, описывающей. Реализация минимизации логических функций методом КвайнаМак Класки Хабрахабр. К рассмотрению предлагается одна из возможных реализаций алгоритма минимизации логических булевых функций ЛФ заданных в виде совершенной дизъюнктивной нормальной формы СДНФ методом КвайнаМак Класки далее просто Мак Класки и проблемы, выявленные при е тестировании. В исследуемом варианте алгоритм Мак Класки реализован на языке C с использованием Generic коллекций библиотеки. NET. Хотелось бы отметить, что задача минимизации ЛФ, по моему мнению, незаслуженно обходится стороной в тематике алгоритмов машинного обучения, т. Следовательно, этот набор входных терм, из общего их возможного числа inline2Ninline, где N количество двух классовых категориальных двоичных переменных в термах, является обучающей выборкой для задачи обучения с учителем с известным данном случае истинным выходным значением целевой функции. Для всех остальных возможных терм, не входящих в обучающую выборку, минимизированная ЛФ должна принимать ложное false значение. Одним из легко реализуемых для любого количества входных переменных алгоритмов минимизации ЛФ является метод Мак Класки. Согласно теории метод Мак Класки состоит из двух основных этапов Нахождение всех простых терм ЛФ, используя правило законы склеивания a A B Для запуска оптимизации нужно вызывать один из перегруженных методов Start. В пункте 1 происходит многократный попарный перебор терм с целью выявления возможности их склейки. Два терма склеиваются, если они отличаются друг от друга значениями только лишь в одной из позиций у одного стоит. Склеивающиеся исходные родительские термы исключаются из дальнейшей работы, а вместо их двоих далее на следующей итерации п. OGqF-Lpd0fU/hqdefault.jpg' alt='Программа Минимизация Логических Функций' title='Программа Минимизация Логических Функций' />Таким образом, двоичный алфавит входных исходных терм внутри алгоритма расширяется до троичного. Первый способ, основанный на 6. NET словаре Dictionarylt UInt. Такое раздвоение обусловлено тем, что первый способ работает несколько быстрее, чем второй, поэтому его использование приоритетнее, но он работает корректно только при количестве входных переменных до 4. Действительно, т. Tree. Func. Term. Промежуточные узлы дерева реализованы с помощью класса Tree. Node. Middle. Каждый из них может ссылаться максимум на три последующих узла в зависимости от того были ли в дерево добавлены соответствующие термы. Все конечные узлы являются экземплярами класса Tree. Node. End, глубина до которых от корня у них всех одинакова и равна количеству входных переменных. Каждый конечный узел также имеет ссылку на другой узел Tree. Node. End, который был добавлен до него, реализуя тем самым однонаправленный связанный список. Такого рода список используется для быстрого перебора всех конечный узлов поискового дерева в процессе их склеивания. Минимизация логических функций является одной из типовых. А еще неплохо в учебных целях самому написать такую программу. В видео показана работы программы, которая выполняет минимизацию булевых функций методом КвайнаМакКласки. Больше узнать. Минимизация функций алгебры логики. Метод непосредственных преобразований логических функций. Метод Квайна. Описание работы программы. Данная программа позволяет производить минимизацию логических функций с любым числом переменных методом. Если в п. 1 для терма не находится другого отличающегося от него только в одной позиции терма, т. Reduce. Redundancy. Terms. Отбрасывание избыточных терм в Reduce. Redundancy. Terms осуществляется с помощью алгоритма приближенного решения задачи о покрытии множества подмножествами переменной длины. Покрытие, близкое к кратчайшему дат алгоритм преобразования таблицы покрытий ТП, основанный на методе минимальный столбецмаксимальная строка, который можно посмотреть, например здесь. R4/pic/Image123.gif' alt='Программа Минимизация Логических Функций' title='Программа Минимизация Логических Функций' />Приблизительная логика его работы состоит в следующем Исходная таблица считается текущей преобразуемой ТП, множество строк покрытий пусто В текущей таблице выделяется столбец с наименьшим числом единиц. Среди строк, содержащих единицы в этом столбце, выделяется одна с наибольшим числом единиц. Karnaugh_Map_Example_2.gif' alt='Программа Минимизация Логических Функций' title='Программа Минимизация Логических Функций' />Эта строка включается в покрытие, текущая таблица сокращается вычеркиванием всех столбцов, в которых выбранная строка имеет единицу Если в таблице есть не вычеркнутые столбцы, то выполняется п. Учебник Физическая Культура 3-4 Класс Петрова Т. В. Первая процедура позволяет для набора входных переменных количеством N сформировать совокупность терм количеством inline2Ninline, вычислить случайное значение ЛФ для каждого терма и выгрузить в файл только те термы, для которых соответствующее им значение функции было равно TRUE. После этого проводится проверка правильности работы минимизированной формы функции путм вычисления е значения для каждого терма и сравнения с исходным. Test. Quine. Mc. Cluskey. Random нажать для просмотраpublic static void Test. Quine. Mc. Cluskey. Randomstring s. File. Name, int i. Variable. Amount. Если же используется сокращнный неполный набор с количеством Q lt Qпор lt inline2Ninline, то проблема не возникает до той поры, пока размер входного набора данных не перерастт некоторый порог Qпор, критичный для алгоритма. В качестве возможных путей преодоления этой проблемы исследовалась возможность определения Tree. Node. End и Tree. Node. Middle не в виде классов языка C, а в виде структур. Но в связи с принципиальным отличием между классами и структурами, состоящая в том, что нельзя получить ссылку на структуру, этот путь оказался тупиковым вследствие того, что исследуемая реализация в своей работе опирается именно на ссылки к Tree. Node. End и Tree. Node. Middle. Другим направлением преодоления проблемы с памятью было максимальная очистка памяти сборщиком мусора перед каждой итерацией в внутри п. Для этого в код функции Logic. Func. Minimize были добавлены явные вызовы сборщика мусора garbage collector. Выяснилось, что с уборкой мусора время работы значительно меньше, чем без не Хотя, казалось бы, на работу сборщика мусора должно тратиться время, что должно было ухудшить результат. Возможное объяснение этого феномена заключается в том, что освобождение памяти сборщиком уменьшает е дефрагментацию в куче, что положительно сказывается на скорости поиска свободных участков при последующем е массовом выделении. Каких либо иных возможностей на преодоление неприятностей с нехваткой памяти я не вижу. В связи с чем возникает вопрос можно ли что то изменить, чтобы добиться стабильной работы алгоритма на полном наборе входных терм с количеством переменных хотя бы до 3. Или это врожднное свойство этого алгоритма, которое не поддатся коррекции Тем не менее, несмотря на возможные проблемы с памятью, предложенная реализация алгоритма Мак Класки в реальных задачах может быть использована в качестве достаточно быстрого и наджного оптимизатора ЛФ, заданных набором терм своих входных переменных, при которых логическая функция принимает истинное значение, когда количество переменных Nlt 1. Q lt lt inline2Ninline. Схемотехника. Минимизация логических функций Geektimes. Минимизация логических функций является одной из типовых задач в процессе обучения схемотехнике. Посему считаю, что такая статья имеет место быть, надеюсь Вам понравится. Зачем это нужно В принципе любая логическая функция может быть упрощена непосредственно с помощью аксиом и теорем логики, но, как правило, такие преобразования требуют громоздких выкладок. К тому же процесс упрощения булевых выражений не является алгоритмическим. Поэтому более целесообразно использовать специальные алгоритмические методы минимизации, позволяющие проводить упрощение функции более просто, быстро и безошибочно. К таким методам относятся, например, метод Квайна, метод карт Карно, метод испытания импликант, метод импликантных матриц, метод Квайна Мак Класки и др. Эти методы наиболее пригодны для обычной практики, особенно минимизация логической функции с использованием карт Карно. Метод карт Карно сохраняет наглядность при числе переменных не более шести. В тех случаях, когда число аргументов больше шести, обычно используют метод Квайна Мак Класки. В процессе минимизации той или иной логической функции, обычно учитывается, в каком базисе эффективнее будет реализовать ее минимальную форму при помощи электронных схем. Минимизация логических функций при помощи карт Карно. Карта Карно графический способ минимизации переключательных булевых функций, обеспечивающий относительную простоту работы с большими выражениями и устранение потенциальных гонок. Представляет собой операции попарного неполного склеивания и элементарного поглощения. Карты Карно рассматриваются как перестроенная соответствующим образом таблица истинности функции. Карты Карно можно рассматривать как определенную плоскую развертку n мерного булева куба. Карты Карно были изобретены в 1. Эдвардом В. Вейчем и усовершенствованы в 1. Морисом Карно, физиком из Bell Labs, и были призваны помочь упростить цифровые электронные схемы. В карту Карно булевы переменные передаются из таблицы истинности и упорядочиваются с помощью кода Грея, в котором каждое следующее число отличается от предыдущего только одним разрядом. Основным методом минимизации логических функций, представленных в виде СДНФ или СКНФ является операция попарного неполного склеивания и элементарного поглощения. Операция попарного склеивания осуществляется между двумя термами членами, содержащими одинаковые переменные, вхождения которых прямые и инверсные совпадают для всех переменных, кроме одной. В этом случае все переменные, кроме одной, можно вынести за скобки, а оставшиеся в скобках прямое и инверсное вхождение одной переменной подвергнуть склейке. Например Возможность поглощения следует из очевидных равенств. Таким образом, главной задачей при минимизации СДНФ и СКНФ является поиск термов, пригодных к склейке с последующим поглощением, что для больших форм может оказаться достаточно сложной задачей. Карты Карно предоставляют наглядный способ отыскания таких термов. Как известно, булевы функции N переменных, представленные в виде СДНФ или СКНФ могут иметь в свом составе 2. N различных термов. Все эти члены составляют некоторую структуру, топологически эквивалентную Nмерному кубу, причм любые два терма, соединнные ребром, пригодны для склейки и поглощения. На рисунке изображена простая таблица истинности для функции из двух переменных, соответствующий этой таблице 2 мерный куб квадрат, а также 2 мерный куб с обозначением членов СДНФ и эквивалентная таблица для группировки термов В случае функции трх переменных приходится иметь дело с трхмерным кубом. Это сложнее и менее наглядно, но технически возможно. На рисунке в качестве примера показана таблица истинности для булевой функции трх переменных и соответствующий ей куб. Как видно из рисунка, для трхмерного случая возможны более сложные конфигурации термов. Например, четыре терма, принадлежащие одной грани куба, объединяются в один терм с поглощением двух переменных В общем случае можно сказать, что 2. K термов, принадлежащие одной Kмерной грани гиперкуба, склеиваются в один терм, при этом поглощаются K переменных. Для упрощения работы с булевыми функциями большого числа переменных был предложен следующий удобный прим. Куб, представляющий собой структуру термов, разворачивается на плоскость как показано на рисунке. Таким образом появляется возможность представлять булевы функции с числом переменных больше двух в виде плоской таблицы. При этом следует помнить, что порядок кодов термов в таблице 0. Аналогичным образом можно работать с функциями четырх, пяти и более переменных. Примеры таблиц для N4 и N5 приведены на рисунке. Для этих таблиц следует помнить, что соседними являются клетки, находящиеся в соответственных клетках крайних столбцов и соответственных клетках верхней и нижней строки. Для таблиц 5 и более переменных нужно учитывать также, что квадраты 4х. Карта Карно может быть составлена для любого количества переменных, однако удобно работать при количестве переменных не более пяти. По сути Карта Карно это таблица истинности составленная в 2 х мерном виде. Благодаря использованию кода Грея в ней верхняя строка является соседней с нижней, а правый столбец соседний с левым, т. На пересечении строки и столбца проставляется соответствующее значение из таблицы истинности. После того как Карта заполнена, можно приступать к минимизации. Если необходимо получить минимальную ДНФ, то в Карте рассматриваем только те клетки которые содержат единицы, если нужна КНФ, то рассматриваем те клетки которые содержат нули. Сама минимизация производится по следующим правилам на примере ДНФ Объединяем смежные клетки содержащие единицы в область, так чтобы одна область содержала 2n n целое число 0. Берм следующую область, выполняем то же самое что и для первой, и т. Конъюнкции областей объединяем дизъюнкцией. Напримердля Карт на 2 ве переменные. Для КНФ вс то же самое, только рассматриваем клетки с нулями, не меняющиеся переменные в пределах одной области объединяем в дизъюнкции инверсии проставляем над единичными переменными, а дизъюнкции областей объединяем в конъюнкцию. На этом минимизация считается законченной. Так для Карты Карно на рис. ДНФ будет иметь вид.