МИНИМИЗАЦИЯ ЛОГИЧЕСКИХ ВЫРАЖЕНИЙ Е. В. Сидоров, С. Б. Карпов Пермский государственный национальный исследовательский университет, 614990, Пермь, Букирева, 15. Введение. Учитывая то, что одну и ту же логическую функцию можно представить различными выражениями, перед реализацией функции в виде логической схемой весьма важным является выбор из всех возможных выражений, соответствующих данной функции, самого простого. Решить эту проблему можно за счет использования процедуры минимизации логического выражения. Минимизацией называют преобразование заданной логической функции с целью уменьшения общего числа переменных и операций. Процесс минимизации имеет важное значение при технической реализации дискретных устройств, так как при этом уменьшается общее количество элементов, увеличивается надежность и устройства становятся боле экономичными. Постановка задачи. Необходимо разработать алгоритм и программу, которая производила бы минимизацию произвольной логической функции, заданной в виде СДНФ. Количество переменных задается пользователем. Наиболее подходящим методом минимизации для программной интерпретации является метод Квайна. К основным достоинствам которого можно отнести то, что всѐ представлено в виде чисел, с которыми легко оперировать. В качестве языка программирования я выбрал С++ поскольку это универсальный высокоуровневый объектно-ориентированный язык программирования пригодный для задач любой сложности. Обзор существующих решений. Можно разделить способы на те, что осуществляются с помощью программ, и те, которые человек выполняет самостоятельно. Из множества методов минимизации наиболее часто используется минимизация методом Квайна. В качестве исходной формы представления логического выражения используется СДНФ (1) и (2). (1) f x1 ,x2 ,x3 ,x4 0,1,4,5,7,8,10,12,14,15 1 f x1 ,x2 ,x3 ,x4 x1 x2 x3 x4 x1x2 x3 x4 x1x2 x3 x4 x1x2 x3 x4 (2) x1 x2 x3 x4 x1 x2 x3 x4 x1x2 x3 x4 x1x2 x3 x4 x1x2 x3 x4 x1x2 x3 x4 Метод Квайна выполняется два этапа. Первый этап имеет своей целью получение тупиковой формы, представляющую собой дизъюнкцию (Сокр. ДНФ), в качестве слагаемых которой используются конъюнкции, каждая из которых не склеивается ни с одной другой конъюнкцией, входящей в это выражение: 162