|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
Сложность систем функций алгебры логики и систем функций трехзначной логики в классах поляризованных полиномиальных формстатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАКДата последнего поиска статьи во внешних источниках: 19 сентября 2015 г.
- Автор: Селезнева С.Н.
- Журнал: Дискретная математика
- Том: 27
- Номер: 1
- Год издания: 2015
- Издательство: ФГБУ "Издательство "Наука"
- Местоположение издательства: Москва
- Первая страница: 111
- Последняя страница: 122
- DOI: 10.4213/dm1319
- Аннотация: Поляризованная полиномиальная форма (ППФ) (по модулю k) – это сумма по модулю k произведений переменных x1, . . . , xn или их отрицаний Поста, причем число отрицаний каждой переменной определяется вектором поляризации этой ППФ. Длиной ППФ называется число ее попарно различных слагаемых. Длиной функции k-значной логики f(x1, . . . , xn) в классе ППФ называется минимальная длина среди всех ППФ, реализующих эту функцию. В работе построена такая последовательность симметрических функций трехзначной логики fn(x1, . . . , xn), что длина каждой из функций fn в классе ППФ не меньше, чем ⌊3n+1/4⌋, где ⌊a⌋ обозначает наибольшее целое число, не превосходящее число a. Сложностью системы ППФ, имеющих один и тот же вектор поляризации, называется число попарно различных слагаемых, встречающихся во всех этих ППФ. Сложностью L(F) системы F = {f1, . . . , fm} функций k-значной логики, зависящих от переменных x1, . . . , xn, в классе ППФ называ- ется минимальная сложность среди всех таких систем ППФ {p1, . . . , pm}, что все ППФ p1, . . . , pm имеют один и тот же вектор поляризации, и ППФ pj ре- ализует функцию fj , j = 1, . . . ,m. Пусть L_k(m, n) = max L(F), где индекс F пробегает по всем системам, содержащим m функций k-значной логики, зависящих от переменных x1, . . . , xn. Понятно, что при простых k верна оценка L_k(m, n) ⩽ k^n. В работе доказано, что L_2(m, n) = 2^n и L_3(m, n) = 3^n для всех m ⩾ 2, n = 1, 2, . . . . Более того, доказано, что оценки остаются такими же, если рассматривать только системы симметрических функций.
- Добавил в систему: Селезнева Светлана Николаевна