ПДМ. 2013. № 2(20).
ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ПРИКЛАДНОЙ
ДИСКРЕТНОЙ МАТЕМАТИКИ
5–13
Горшков С. П. О некоторых свойствах слабо положительных и слабо отрицательных булевых
функций // ПДМ. 2013. № 2(20). C. 5–13.
14–18
Горшков С. П., Двинянинов А. В. Нижняя и верхняя оценки порядка аффинности преобразований
пространств булевых векторов // ПДМ. 2013. № 2(20). C. 14–18.
19–25
Смышляев С. В. О связях между некоторыми параметрами совершенно уравновешенных булевых
функций // ПДМ. 2013. № 2(20). C. 19–25.
26–38
Черемушкин А. В. Аддитивный подход к определению степени нелинейности дискретной
функции на циклической группе примарного порядка // ПДМ. 2013. № 2(20). C. 26–38.
МАТЕМАТИЧЕСКИЕ МЕТОДЫ КРИПТОГРАФИИ
39–49
Зубов А. Ю. Код аутентификации с секретностью на основе проективной геометрии // ПДМ. 2013.
№ 2(20). C. 39–49.
МАТЕМАТИЧЕСКИЕ ОСНОВЫ ИНФОРМАТИКИ И
ПРОГРАММИРОВАНИЯ
50–58
Тарков М. С. Отображение параллельных программ на многоядерные компьютеры
рекуррентными нейронными сетями // ПДМ. 2013. № 2(20). C. 50–58.
ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ В ДИСКРЕТНОЙ
МАТЕМАТИКЕ
59–70
Алексейчук А. Н., Грязнухин А. Ю. Быстрый алгоритм восстановления истинного решения
фиксированного веса системы линейных булевых уравнений с искажённой правой частью // ПДМ.
2013. № 2(20). C. 59–70.
71–77
Стр.1
Гоцуленко В. В. Формула для числа сочетаний с повторениями при ограничениях и её применение
// ПДМ. 2013. № 2(20). C. 71–77.
78–90
Костюк Ю. Л. Эффективная реализация алгоритма решения задачи коммивояжёра методом
ветвей и границ // ПДМ. 2013. № 2(20). C. 78–90.
91–100
Мурин Д. М. Модификация метода Лагариаса — Одлыжко для решения обобщённой задачи о
рюкзаке и систем задач о рюкзаках // ПДМ. 2013. № 2(20). C. 91–100.
101–114
Яхонтов С. В. Эффективное по времени и памяти вычисление логарифмической функции
вещественного аргумента на машине Шёнхаге // ПДМ. 2013. № 2(20). C. 101–114.
ДИСКРЕТНЫЕ МОДЕЛИ РЕАЛЬНЫХ ПРОЦЕССОВ
115–122
Емеличев В. А., Шацов Р. П. Инвестиционная булева задача Марковица в условиях
неопределённости, многокритериальности и риска // ПДМ. 2013. № 2(20). C. 115–122.
Стр.2
ПРИКЛАДНАЯ ДИСКРЕТНАЯ МАТЕМАТИКА
2013
Теоретические основы прикладной дискретной математики
ТЕОРЕТИЧЕСКИЕ ОСНОВЫ
ПРИКЛАДНОЙ ДИСКРЕТНОЙ МАТЕМАТИКИ
УДК 519.7
О НЕКОТОРЫХ СВОЙСТВАХ СЛАБО ПОЛОЖИТЕЛЬНЫХ
И СЛАБО ОТРИЦАТЕЛЬНЫХ БУЛЕВЫХ ФУНКЦИЙ
С. П. Горшков
Институт криптографии, связи и информатики, г. Москва, Россия
E-mail: spg54@bk.ru
Исследуются некоторые свойства слабо положительных (антихорновских) и слабо
отрицательных (хорновских) булевых функций. В частности, оценивается сложность
задачи построения привед¨
eнных представлений этих функций, показывается,
что нет ограничений на вес таких функций, оценивается возможная длина
записи рассматриваемых функций.
Ключевые слова: слабо положительная (антихорновская) булева функция,
слабо отрицательная (хорновская) булева функция, вычислительная сложность.
1.
Некоторые известные свойства исследуемых функций
ление f в виде следующей КНФ:
f ≡
в виде следующей КНФ:
Определение 1. Булева функция f(x1, . . . ,xn), n 1, называется:
1) слабо положительной (антихорновской), если f ≡ 1 или существует представ(xαisi1
i=1
t
∨
xsi2
∨ . . . ∨ xsiki
),
где αi ∈ {0, 1}, i = 1, . . . , t;
2) слабо отрицательной (хорновской), если f ≡ 1 или существует представление f
f ≡ i=1
(xαisi1
t
∨ ¯
xsi2
∨ . . . ∨ ¯
xsiki
),
где αi ∈ {0, 1}, i = 1, . . . , t.
Множество всех слабо положительных (слабо отрицательных) функций обозначим
WP (WN). Указанные записи соответственно функций классовWP,WN называются
привед¨
eнными представлениями. Функции из классов WP, WN, зависящие от k переменных,
обозначим WPk, WNk.
Актуальность задачи изучения указанных функций отмечена в работе [1].
Обозначим:
Vk —множество двоичных k-мерных векторов;
V (i)
k = {α ∈ Vk : α = i}, где i ∈ {0, . . . , k} (слой векторов веса i);
c—целая часть действительного числа c.
№2(20)
Стр.3