Uniformity of a certain systems of functions of many-valued logic |
| |
Authors: | P B Tarasov |
| |
Institution: | 16264. Faculty of Mechanics and Mathematics, Moscow State University, Leninskie Gory, Moscow, 119991, Russia
|
| |
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 proved that there exists constants c and d such that for an arbitrary function f ε A] the depth D(f) and the complexity L(f) of f in the class of formulas over A satisfy the relation D(f) ≤ clog2 L(f) + d. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|