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

Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2013 Number 5, Pages 41–46 (Mi vmumm437)

This article is cited in 1 paper

Mathematics

Certain sufficient conditions of uniformity for 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 $k$-valued logic taking values in the set $E_s={\{0,1,\ldots, s-1\}}$, $k\geq s\geq2$, such that the closed class generated by restriction of functions from $A$ on the set $E_s$ contains a near-unanimity function, it is proved that there exists constants $c$ and $d$ such that for an arbitrary function $f \in [A]$ the depth $D_A(f)$ and the complexity $L_A(f)$ of $f$ in the class of formulas over $A$ satisfy the relation ${D_A(f) \leq c\log_2 L_A(f)+d}$.

Key words: uniform systems, many-valued logic, polynomially equivalent, near-unanimity function.

UDC: 511

Received: 22.02.2013


 English version:
Moscow University Mathematics Bulletin, Moscow University Måchanics Bulletin, 2013, 68:5, 253–257

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024