Розглянуто двоетапний метод мінімізації булевих функцій для проєктування цифрових комбінаційних схем. На першому етапі здійснюють пошук простих кон’юнктермів методом побітового розбиття множини вихідних кон’юнктермів. Тавтологія не виникає, кон’юнктерми низького рангу виявляються без здійснення проміжних склеювань. На другому етапі виконується пошук мінімальної множини простих кон’юнктермів методом ланцюгового покриття таблиці простих кон’юнктермів. У циклічній частині віднаходять фрагменти ланцюгових функцій, покриття яких відбувається доволі просто. Для зменшення обчислювального навантаження в точках розгалуження ланцюгів можна прийняти рішення про входження чи вилучення відповідного простого кон’юнктерма з кінцевої множини на підставі розрахунку коефіцієнта складності в околі розгалуження. Запропонований метод є евристичним.
[1] McCluskey E. J. Minimization of Boolean Functions. Bell System Technical Journal, 1956, 35, pp. 1417–1444.
[2] Quine W.V. The Problem of Simplifying Truth Functions. American Mathematical Monthly, 1952, 59, pp. 521–531.
[3] Закревский А. Д. Алгоритмы синтеза дискретных автоматов. М.: Наука, 1971. 512 с.
[4] Hwa Н. R. A method for generating prime implicants of a boolean expressions. IEEE Transactions on Electronic Computers. New York: The Institute of Electrical and Electronics Engineers, Inc., Jun. 1974. Vol. C-23, No. 6, pp. 637–641.
[5] Svoboda A. Ordering of implicants. IEEE Transactions on Electronic Computers. New York: The Institute of Electrical and Electronics Engineers, Inc., Feb. 1967, Vol. EC-16, No. 1, pp. 100–105.
[6] Рицар Б. Є. Мінімізація булових функцій методом розчеплення кон’юнктермів. Управляющие системы и машины, 1998, № 5, С. 14–22.
[7] Рицар Б. Є., Мінзюк В. В. Теоретико-множинна модифікація мінімаксного методу покриття булових функцій. Управляющие системы и машины, 2005, № 5, С. 43–47.
[8] Мінзюк В. В. Спосіб спрощення задачі покриття булових функцій. Вісник Національного університету “Львівська політехніка” Радіоелектроніка та телекомунікації, 2005, № 534, С. 24–28.
[9] Мінзюк В. В. Спосіб синтезування кон’юнктермів булових функцій. Вісник Національного університету “Львівська політехніка” Радіоелектроніка та телекомунікації, 2004, № 508, С. 256–262.
[10] Мінзюк В. В. Спосіб сортування цілих чисел для задач мінімізації булових функцій. Вісник Національного університету “Львівська політехніка” Радіоелектроніка та телекомунікації, 2011, № 705, С. 135–137.
[11] Мінзюк В. В. Модифікація методу порозрядного вирощування простих кон’юнктивних термів булових функцій. Збірник наукових праць Інституту проблем моделювання в енергетиці ім. Г. Є. Пухова. К.: ІПМЕ ім. Г. Є. Пухова НАН України, 2012, Вип. 65, С. 129–134.
[12] Мінзюк В. В. Метод пошуку простих кон’юнктивних термів булових функцій побітовим розбиттям множини. Збірник наукових праць Інституту проблем моделювання в енергетиці ім. Г. Є. Пухова. К.: ІПМЕ ім. Г. Є. Пухова НАН України, 2013, Вип. 66, С. 95–103.