RUS  ENG
Full version
JOURNALS // Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki // Archive

Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2014 Volume 156, Book 3, Pages 123–131 (Mi uzku1272)

Several conditions for uniformity of a finite system of many-valued logic

P. B. Tarasov

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics, Moscow, Russia

Abstract: We consider the relation between depth and complexity of many-valued logic functions over finite functional systems. The functional system $A$ is called quasi-uniform if there exist constants $c$ and $d$ such that for an arbitrary function $f$ from the closure of $A$ the inequality $D_A(f)\leq c\log_2^2L_A(f)+d$ holds, where $D_A(f)$ and $L_A(f)$ are the depth and the complexity of realization of the function $f$ by formulas over the finite system $A$. In this paper we provide some conditions for the quasi-uniformity of systems of functions of many-valued logic that take two values $0$ and $1$ and are monotone on the partially ordered set $\{0,\ldots,k-1\}$, where $1>0$ and all other elements are incomparable.

Keywords: many-valued logic, depth, complexity, uniformity, parallelizing.

UDC: 519.716

Received: 29.07.2014



© Steklov Math. Inst. of RAS, 2024