|
ИСТИНА |
Войти в систему Регистрация |
ФНКЦ РР |
||
О мультипликативной сложности квазиквадратичных функций алгебры логикистатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАКСтатья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 24 января 2020 г.
- Автор: Селезнева С.Н.
- Журнал: Вестник Московского университета. Серия 15: Вычислительная математика и кибернетика
- Номер: 1
- Год издания: 2015
- Издательство: Изд-во Моск. ун-та
- Местоположение издательства: М.
- Первая страница: 23
- Последняя страница: 29
- Аннотация: Мультипликативной сложностью μ(f) функции алгебры логики f(x1,…,xn) называется минимальное число элементов конъюнкции в схемах из функциональных элементов в базисе {&,⊕,1}, каждая из которых реализует функцию f. Функция алгебры логики f(x1,…,xn) называется квазиквадратичной, если она может быть представлена в виде φ(x1,…,xk)⊕q(x1,…,xn), где φ - произвольная функция, q - квадратичная функция (т.е. функция степени два), k≤n. В настоящей работе исследуется мультипликативная сложность квазиквадратичных функций при k=3 и произвольных n. Мы доказываем, что если f(x1,…,xn) - квазиквадратичная функция алгебры логики, где k=3, n≥k, то μ(f)≤⌈(n+1)/2⌉, где ⌈a⌉ обозначает наименьшее целое число, не меньшее числа a. Кроме того, мы описываем одну последовательность квазиквадратичных функций алгебры логики fn(x1,…,xn), k=3, n=5,6,…, для которой доказываем, что μ(fn)=⌈(n+1)/2⌉.
- Добавил в систему: Селезнева Светлана Николаевна