|
ИСТИНА |
Войти в систему Регистрация |
Интеллектуальная Система Тематического Исследования НАукометрических данных |
||
Complexity of systems of functions of Boolean algebra and systems of functions of three-valued logic in classes of polarized polynomial formsстатья
Информация о цитировании статьи получена из
Web of Science,
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 26 сентября 2016 г.
- Автор: Selezneva S.N.
- Журнал: Discrete Mathematics and Applications
- Том: 26
- Номер: 2
- Год издания: 2016
- Издательство: de Gruyter
- Местоположение издательства: Germany
- Первая страница: 115
- Последняя страница: 124
- DOI: 10.1515/dma-2016-0009
- Аннотация: A polarized polynomial form (PPF) (modulo k) is a modulo k sum of products of variables x1, . . . , xn or their Post negations, where the number of negations of each variable is determined by the polarization vector of the PPF. The length of a PPF is the number of its pairwise distinct summands. The length of a function f(x1, . . . , xn)of k-valued logic in the class of PPFs is the minimum length among all PPFs realizing the function. The paper presents a sequence of symmetric functions fn(x1, . . . , xn)of three-valued logic such that the length of each function fn in the class of PPFs is not less than ⌊3n+1/4⌋, where ⌊a⌋ denotes the greatest integer less or equal to the number a. The complexity of a system of PPFs sharing the same polarization vector is the number of pairwise distinct summands entering into all of these PPFs. The complexity L_k(F) of a system F ={f1,..., fm} of functions of k-valued logic depending on variables x1,..., xn in the class of PPFs is the minimum complexity among all systems of PPFs {p1,...,pm}such that all PPFs p1,...,pm share the same polarization vector and the PPF pj realizes the function fj, j = 1,...,m. Let L_k(m,n) = max_{F}L_k(F), where F runs through all systems consisting of m functions of k-valued logic depending on variables x1,..., xn. For prime values of k it is easy to derive the estimate L_k(m,n) ≤ k^n. In this paper it is shown that L_2(m,n) = 2^n and L_3(m,n) = 3^n for all m ≥ 2, n= 1, 2, . . . Moreover, it is demonstrated that the estimates remain valid when consideration is restricted to systems of symmetric functions only.
- Добавил в систему: Селезнева Светлана Николаевна