|
|
Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika, 2013, Number 2, Pages 61–64
(Mi vmumm398)
|
|
|
|
This article is cited in 3 scientific papers (total 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.
Received: 12.09.2012
Citation:
P. B. Tarasov, “Uniformity of a certain systems of functions of many-valued logic”, Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2013, no. 2, 61–64; Moscow University Mathematics Bulletin, 68:2 (2013), 126–129
Linking options:
https://www.mathnet.ru/eng/vmumm398 https://www.mathnet.ru/eng/vmumm/y2013/i2/p61
|
|