informИнформатикаInformatics1816-03012617-6963UIIP NASBinform-820Research ArticleМАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕMATHEMATICAL MODELINGДЕКОМПОЗИЦИЯ СИСТЕМ ПОЛНОСТЬЮ ОПРЕДЕЛЕННЫХ БУЛЕВЫХ ФУНКЦИЙ ПО ИХ ЗАДАНИЮ В ВИДЕ КОМПАКТНЫХ ТАБЛИЦПоттосинЮ. В.ШестаковЕ. А.Объединенный институт проблем информатики НАН БеларусиBelarusОбъединенный институт проблем информатики НАН БеларусиBelarus20040502201902(02)3544Copyright © Поттосин Ю.В., Шестаков Е.А., 20192019Поттосин Ю.В., Шестаков Е.А.Поттосин Ю.В., Шестаков Е.А.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/820

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

ReferencesHartmanis J., Stearns R.E. Algebraic Structure Theory of Sequential Machines. – Prentice-Hall, Englewood Cliffs, NJ, 1966.Hartmanis J., Stearns R.E. Algebraic Structure Theory of Sequential Machines. – Prentice-Hall, Englewood Cliffs, NJ, 1966.Бибило П.Н., Енин С.В. Синтез комбинационных схем методом функциональной декомпозиции. – Мн.: Наука и техника, 1987. – 189 с.Бибило П.Н., Енин С.В. Синтез комбинационных схем методом функциональной декомпозиции. – Мн.: Наука и техника, 1987. – 189 с.Ashenhurst R.L. The decomposition of switching functions // Proceedings of on International Symposium on the Theory of Switching. April 2-5, 1957. – V.29. – Harvard Univ., 1959. – P. 74-116.Ashenhurst R.L. The decomposition of switching functions // Proceedings of on International Symposium on the Theory of Switching. April 2-5, 1957. – V.29. – Harvard Univ., 1959. – P. 74-116.Curtis H.A. Generalized tree circuit – the basic building block of an extended decomposition theory // J. Assoc. Comput. Mach. – 1963. – № 10. – P. 562 581.Curtis H.A. Generalized tree circuit – the basic building block of an extended decomposition theory // J. Assoc. Comput. Mach. – 1963. – № 10. – P. 562 581.Curtis H.A. Simplified decomposition of Boolean function // IEEE Trans. on Comput. – V. 25, October 1967. – P. 1033 1044.Curtis H.A. Simplified decomposition of Boolean function // IEEE Trans. on Comput. – V. 25, October 1967. – P. 1033 1044.Karp R.M. Functional decomposition and switching circuit design // J. Soc. Industr. Appl. Math. – 1963. – V. 11. – №. 2. – P. 291 335.Karp R.M. Functional decomposition and switching circuit design // J. Soc. Industr. Appl. Math. – 1963. – V. 11. – №. 2. – P. 291 335.Закревский А.Д. Логический синтез каскадных схем. – М.: Наука, 1981. – 416 с.Закревский А.Д. Логический синтез каскадных схем. – М.: Наука, 1981. – 416 с.Шестаков Е.А. Декомпозиция системы полностью определенных булевых функций по покрытию аргументов // АВТ. – 1994. – №1. – C.12 20.Шестаков Е.А. Декомпозиция системы полностью определенных булевых функций по покрытию аргументов // АВТ. – 1994. – №1. – C.12 20.Поттосин Ю.В., Шестаков Е.А. Декомпозиция системы частичных булевых функций по ее табличному заданию // АВТ. – 1999. – №3. – С.36 47.Поттосин Ю.В., Шестаков Е.А. Декомпозиция системы частичных булевых функций по ее табличному заданию // АВТ. – 1999. – №3. – С.36 47.Шестаков Е.А. О декомпозиции систем полностью определенных булевых функций методом тождественных отображений // Идентификация образов. – Мн.: Ин-т техн. кибернетики НАН Беларуси, 1999. – С. 129 148.Шестаков Е.А. О декомпозиции систем полностью определенных булевых функций методом тождественных отображений // Идентификация образов. – Мн.: Ин-т техн. кибернетики НАН Беларуси, 1999. – С. 129 148.Saucier G., Duff C., Poirot F. State assignment using a new embedding method based on an intersecting cube theory // Proceedings of the Design Automation Conference, June 1989. – P. 321-326.Saucier G., Duff C., Poirot F. State assignment using a new embedding method based on an intersecting cube theory // Proceedings of the Design Automation Conference, June 1989. – P. 321-326.Goldberg E.I. Methods of Boolean encoding of predicate arguments values. – Minsk, 1991. – 26 p. (Preprint / Inst. of engineering cybernetics, the Academy of Sciences of Belarus; № 3).Goldberg E.I. Methods of Boolean encoding of predicate arguments values. – Minsk, 1991. – 26 p. (Preprint / Inst. of engineering cybernetics, the Academy of Sciences of Belarus; № 3).Goldberg E.I. Face embedding by componentwise construction of intersecting cubes. – Minsk, 1995. – 43 p. (Preprint / Inst. of Engineering Cybernetics, the Academy of Sciences of Belarus; № 1).Goldberg E.I. Face embedding by componentwise construction of intersecting cubes. – Minsk, 1995. – 43 p. (Preprint / Inst. of Engineering Cybernetics, the Academy of Sciences of Belarus; № 1).Кардаш С.Н. Декомпозиция системы булевых функций методом тождественных отображений // Проектирование систем логического управления: Сб. науч. тр. – Мн.: Ин-т техн. кибернетики АН БССР, 1986. – С. 22-31.Кардаш С.Н. Декомпозиция системы булевых функций методом тождественных отображений // Проектирование систем логического управления: Сб. науч. тр. – Мн.: Ин-т техн. кибернетики АН БССР, 1986. – С. 22-31.Шестаков Е.А. О декомпозиции систем булевых функций методом тождественных отображений. – Мн., 1988. – 16 с. (Препринт / Ин-т техн. кибернетики АН БССР; № 42).Шестаков Е.А. О декомпозиции систем булевых функций методом тождественных отображений. – Мн., 1988. – 16 с. (Препринт / Ин-т техн. кибернетики АН БССР; № 42).Гольдберг Е.И. Декомпозиция ПЛМ. – Мн., 1991. – 32 с. (Препринт / Ин-т техн. кибернетики АН БССР; № 6).Гольдберг Е.И. Декомпозиция ПЛМ. – Мн., 1991. – 32 с. (Препринт / Ин-т техн. кибернетики АН БССР; № 6).Brzozowski J.A., Luba T. Decomposition of Boolean functions specified by cubes // Research Report CS-97-01. – Waterloo, Canada: University of Waterloo, 1997. – 36 p.Brzozowski J.A., Luba T. Decomposition of Boolean functions specified by cubes // Research Report CS-97-01. – Waterloo, Canada: University of Waterloo, 1997. – 36 p.Brzozowski J.A., Lou J.J. Blanket algebra for multiple-valued function decomposition // Proceedings of the International Workshop on Formal Languages and Computer Systems. – Kyoto, Japan, March 18–21, 1997.Brzozowski J.A., Lou J.J. Blanket algebra for multiple-valued function decomposition // Proceedings of the International Workshop on Formal Languages and Computer Systems. – Kyoto, Japan, March 18–21, 1997.Pottosin Yu.V., Shestakov E.A. Decomposition of system of completely specified Boolean functions using their compact table representation // 4th International Workshop «Boolean Problems». – Freiberg (Sachsen), 2000. – P. 135-142.Pottosin Yu.V., Shestakov E.A. Decomposition of system of completely specified Boolean functions using their compact table representation // 4th International Workshop «Boolean Problems». – Freiberg (Sachsen), 2000. – P. 135-142.Поттосин Ю.В., Шестаков Е.А. О табличном задании систем полностью определенных булевых функций // Информатика. – № 1. – 2004. – С. 139-147.Поттосин Ю.В., Шестаков Е.А. О табличном задании систем полностью определенных булевых функций // Информатика. – № 1. – 2004. – С. 139-147.Закревский А.Д. О минимальном дизъюнктивном коде // Докл. АН БССР. – 1978. – Т.22. – № 6. – С. 516-518.Закревский А.Д. О минимальном дизъюнктивном коде // Докл. АН БССР. – 1978. – Т.22. – № 6. – С. 516-518.Кардаш С.Н. Алгоритм решения задачи о минимальном дизъюнктивном коде // Логическое проектирование дискретных устройств: Сб. науч. тр. – Мн.: Ин-т техн. кибернетики АН БССР, 1984. – С. 68-72.Кардаш С.Н. Алгоритм решения задачи о минимальном дизъюнктивном коде // Логическое проектирование дискретных устройств: Сб. науч. тр. – Мн.: Ин-т техн. кибернетики АН БССР, 1984. – С. 68-72.

The authors declare that there are no conflicts of interest present.