zbMATH — the first resource for mathematics

Complexity of formula realization of a sequence of 4-valued logic functions. (Russian, English) Zbl 1084.03019
Vestn. Mosk. Univ., Ser. I 2004, No. 3, 52-55 (2004); translation in Mosc. Univ. Math. Bull. 59, No. 3, 41-44 (2004).
The author presents an example of a sequence of 4-valued logic functions whose complexity in the class of formulas over an incomplete finite system has double exponential growth in the number of variables. Earlier, the author showed that such effect is not possible in two-valued logic [A. B. Ugol’nikov, Sov. Math., Dokl. 37, No. 1, 287–290 (1988); translation from Dokl. Akad. Nauk SSSR 298, No. 6, 1341–1344 (1988; Zbl 0683.03011)].

03B50 Many-valued logic