Мультипликативная сложность некоторых функций алгебры логикистатья

Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАК
Дата последнего поиска статьи во внешних источниках: 19 сентября 2015 г.

Работа с статьей


[1] Селезнева С. Н. Мультипликативная сложность некоторых функций алгебры логики // Дискретная математика. — 2014. — Т. 26, № 4. — С. 100–109. Мультипликативной (или конъюнктивной) сложностью функции алгебры логики f(x1,…,xn) (соответственно, системы функций алгебры логики F={f1,…,fm}) называется минимальное число элементов конъюнкции в схемах из функциональных элементов в базисе {x&y,x⊕y,1}, каждая из которых реализует функцию f (соответственно, все функции из системы F). Мультипликативную сложность функции f (системы функций F) будем обозначать через μ(f) (через μ(F)). В работе доказано, что μ(f)=n−1, если функция f(x1,…,xn) представима в виде x1x2…xn⊕q(x1,…,xn), где q – функция степени два (n≥3). В работе также доказано, что μ(f)≤n−1, если функция f(x1,…,xn) представима в виде суммы по модулю 2 двух мультиаффинных функций. Кроме того, в работе показано, что μ(F)=n−1, если F={x1x2…xn,f(x1,…,xn)}, где f – или функция степени два, или мультиаффинная функция. [ DOI ]

Публикация в формате сохранить в файл сохранить в файл сохранить в файл сохранить в файл сохранить в файл сохранить в файл скрыть