Том 20, номер 6, 2013 г., Стр. 77-94

УДК 519.714.7
Чухров И. П.
О мерах сложности комплексов граней в единичном кубе

Аннотация:
Рассматривается проблема доказательства минимальности комплексов граней в единичном кубе. Сформулированы достаточные условия, которые позволяют доказывать минимальность комплексов граней на основе порядковых свойств функционала меры сложности и структурных свойств булевых функций. Это позволило расширить множество комплексов граней, для которых доказана минимальность относительно мер сложности, удовлетворяющих определённым свойствам. Доказано строгое включение для множеств комплексов граней: ядровых, минимальных для любой меры сложности и минимальных для любой меры сложности, инвариантной относительно замены граней изоморфными гранями.
Ил. 2, библиогр. 10.

Ключевые слова: грань, комплекс граней в единичном кубе, булева функция, мера сложности, минимальный комплекс граней.

Чухров Игорь Петрович ¹
1. Институт автоматизации проектирования РАН,
ул. 2-я Брестская, 19/18, 123056 Москва, Россия
е-mail: chip@icad.org.ru

Статья поступила 9 ноября 2012 г.

Литература

[1] Васильев Ю. Л., Глаголев В. В. Метрические свойства дизъюнктивных нормальных форм // Дискретная математика и математические вопросы кибернетики. Т. 1. - М.: Наука, 1974. - С. 99–148.

[2] Вебер К. О различных понятиях минимальности дизъюнктивных нормальных форм // Пробл. кибернетики. - 1979. - № 36. - С. 129–158.

[3] Журавлев Ю. И. О различных понятиях минимальности д.н.ф. // Сиб. мат. журн. - 1960. - Т. 1, № 4. - С. 609–611.

[4] Журавлев Ю. И. Алгоритмы построения минимальных дизъюнктивных нормальных форм для функций алгебры логики // Дискретная математика и математические вопросы кибернетики. Т. 1. - М.: Наука, 1974. - С. 67–98.

[5] Лин Син-Лян. О сравнении сложностей минимальных и кратчайших дизъюнктивных нормальных форм для функций алгебры логики // Пробл. кибернетики. - 1967. - № 18. - С. 11–44.

[6] Сапоженко А. А., Чухров И. П. Минимизация булевых функций в классе дизъюнктивных нормальных форм // Итоги науки и техники. Сер. Теория вероятности. Мат. статистика. Теорет. кибернетика. - 1987. - Т. 25. - С. 68–116.

[7] Чухров И. П. Оценки числа минимальных дизъюнктивных нормальных форм для поясковой функции // Методы дискретного анализа в исследованиях функциональных систем. - Новосибирск: Ин-т математики СО АН СССР, 1981. - № 36. - С. 74–92.

[8] Чухров И. П. О ядровых и кратчайших комплексах граней в единичном кубе // Дискрет. анализ и исслед. операций - 2011. - Т. 18, № 2. - С. 75–94.

[9] Чухров И. П. О минимальных комплексах граней в единичном кубе // Дискрет. анализ и исслед. операций. - 2012. - Т. 19, № 3. - С. 79–99.

[10] Яблонский С. В. Введение в дискретную математику. - М.: Высш. шк., 2003. - 384 с.