К рассмотрению предлагается одна из возможных реализаций алгоритма минимизации логических (булевых) функций (ЛФ) заданных в виде совершенной дизъюнктивной нормальной формы (СДНФ) методом КвайнаМак-Класки (далее просто Мак-Класки) и проблемы, выявленные при её тестировании. В исследуемом варианте алгоритм Мак-Класки реализован на языке C# с использованием Generic-коллекций библиотеки .NET.
Хотелось бы отметить, что задача минимизации ЛФ, по моему мнению, незаслуженно обходится стороной в тематике алгоритмов машинного обучения, т. к. по своему смыслу она реализует процедуру обучения с учителем для определённого набора входных терм (простых конъюнкций), на которых оптимизируемая функция принимает истинное (true) значение. Следовательно, этот набор входных терм, из общего их возможного числа $inline$2^N$inline$, где N – количество двух классовых категориальных (двоичных) переменных в термах, является обучающей выборкой для задачи обучения с учителем с известным (данном случае истинным) выходным значением целевой функции. Для всех остальных возможных терм, не входящих в обучающую выборку, минимизированная ЛФ должна принимать ложное (false) значение.
Одним из легко реализуемых для любого количества входных переменных алгоритмов минимизации ЛФ является метод Мак-Класки. Согласно теории метод Мак-Класки состоит из двух основных этапов:
Читать полностью »
