|
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.
Received: 29.07.2014
Citation:
P. B. Tarasov, “Several conditions for uniformity of a finite system of many-valued logic”, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 156, no. 3, Kazan University, Kazan, 2014, 123–131
Linking options:
https://www.mathnet.ru/eng/uzku1272 https://www.mathnet.ru/eng/uzku/v156/i3/p123
|
|