RUS  ENG
Full version
JOURNALS // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika // Archive

Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2013 Number 2, Pages 61–64 (Mi vmumm398)

This article is cited in 3 papers

Short notes

Uniformity of a certain systems of functions of many-valued logic

P. B. Tarasov

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: For any finite system $A$ of functions of many-valued logic taking values in the set $\{0,1\}$ such that a projection of $A$ generates the class of all monotone boolean functions, it is prooved that there exists constants $c$ and $d$ such that for an arbitrary function $f\in [A]$ the depth $D(f)$ and the complexity $L(f)$ of $f$ in the class of formulas over $A$ satisfy the relation $D(f)\leq c\log_2 L(f)+d$.

Key words: uniform systems, many-valued logic, monotone functions, polynomially equivalent.

UDC: 511

Received: 12.09.2012


 English version:
Moscow University Mathematics Bulletin, Moscow University Måchanics Bulletin, 2013, 68:2, 126–129

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024