Positively closed classes of partial Boolean functions. (English. Russian original) Zbl 1160.03042
Mosc. Univ. Comput. Math. Cybern. 32, No. 3, 147-151 (2008); translation from Vestn. Mosk. Univ. 2008, No. 3, 30-33 (2008).
Let \(P_2^*\) be the set of partial functions of any arity on \(\{0,1\}\). A language Pos is defined whose terms are built from variable symbols and symbols of functions from \(P_2^*\). The semantics associated with Pos uses the truth values T (true), F (false), and * (undetermined). The positive closure of a class \(Q\subseteq P_2^*\) consists of the functions \(f\) such that there is a formula \(\Phi\) of Pos such that for all \(x_1,\dots,x_n,y\), the truth values of \(\Phi(x_1,\dots,x_n,y)\) and \(f(x_1,\dots,x_n)=y\) coincide. The authors prove that there are ten positively closed classes, among which three are precomplete. In each case a positive basis is established.
Reviewer: Sergiu Rudeanu (Bucureşti)
References:
| [1] | R. V. Freivald, ”Completeness Criterion for Partial Functions of Algebra of Logic and Multivalued Logics,” Dokl. Akad. Nauk SSSR 167(6), 1249–1250 (1966). |
| [2] | R. V. Freivald, ”Functional Completeness for Incompletely Defined Functions of Algebra of Logic,” Diskret. Analiz, No. 8, 55–68 (1966). |
| [3] | V. B. Alekseev and A. A. Voronenko, ”On Certain Closed Classes in Partial Two-Valued Logic,” Diskret. Mat. 6(4), 58–79 (1994). · Zbl 0818.06013 |
| [4] | A. V. Kuznetsov, ”On Means for Detecting Nonderivability and Inexpressibility,” in Logical Derivation (Nauka, Moscow, 1979), pp. 5–33 [in Russian]. |
| [5] | S. S. Marchenkov, ”On Expressibility of Functions of Multivalued Logic in ertain Logic-Functional Languages,” Diskret. Mat. 11(4), 110–126 (1999). · doi:10.4213/dm400 |
| [6] | S. S. Marchenkov, ”Criterion of Positive Completeness in Three-Valued Logic,” Diskret. Analiz Issledovanie Operatsii, Ser. 1 13(3), 27–39 (2006). · Zbl 1249.03016 |
| [7] | S. S. Marchenkov, Closed Classes of Boolean Functions (Fizmatlit, Moscow, 2000) [in Russian]. · Zbl 0965.03074 |
| [8] | S. V. Yablonskii, Introduction to Discrete Mathematics (Nauka, Moscow, 1986) [in Russian]. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
