×

Uniqueness of minimal coverings of maximal partial clones. (English) Zbl 1232.08003

Author’s abstract: “A partial function \(f\) on a \(k\)-element set \(E_{k }\) is a partial Sheffer function if every partial function on \(E_{k }\) is definable in terms of \(f\). Since this holds if and only if \(f\) belongs to no maximal partial clone on \(E_{k }\), a characterization of partial Sheffer functions reduces to finding families of minimal coverings of maximal partial clones on \(E_{k }\). We show that, for each \(k \geq 2\), there exists a unique minimal covering.”

MSC:

08A55 Partial algebras
03B50 Many-valued logic
08A40 Operations and polynomials in algebraic structures, primal algebras
Full Text: DOI

References:

[1] Freivald R.V.: Completeness criteria for partial functions of the algebra of logic and many-valued logics. Dokl. AN SSSR 167, 1249–1250 (1966) (Russian)
[2] Haddad L., Lau D.: Some criteria for partial Sheffer functions in k-valued logic. Mult.-Valued Logic and Soft Computing 13, 415–446 (2007) · Zbl 1143.08003
[3] Haddad L., Rosenberg I.G.: Maximal partial clones determined by the areflexive relations. Discrete Appl. Math 24, 133–143 (1989) · Zbl 0695.08010 · doi:10.1016/0166-218X(92)90279-J
[4] Haddad L., Rosenberg I.G.: Partial Sheffer operations. Eur. J. Comb 12, 9–21 (1991) · Zbl 0724.08005 · doi:10.1016/S0195-6698(13)80003-0
[5] Haddad L., Rosenberg I.G.: Completeness theory for finite partial algebras. Algebra Universalis 29, 378–401 (1992) · Zbl 0771.08001 · doi:10.1007/BF01212439
[6] Haddad L., Rosenberg I.G., Schweigert D.: A maximal partial clone and a Slupecki-type criterion. Acta Sci. Math 54, 89–98 (1990) · Zbl 0717.08003
[7] Lau D.: Function algebras on finite sets. A basic course on many-valued logic and clone theory. Springer Monographs in Mathematics. Springer, Berlin (2006) · Zbl 1105.08001
[8] Romov B.A.: The algebras of partial functions and their invariants. Cybernetics 17, 157–167 (1981) · Zbl 0466.03026 · doi:10.1007/BF01069627
[9] Rosenberg I.G.: La structure des fonctions de plusieurs variables sur un ensemble fini. C. R. Acad. Sci., Paris 260, 3817–3819 (1965) (French) · Zbl 0144.01002
[10] Rosenberg I.G.: Über die funktionale Vollständigkeit in den mehrwertigen Logiken. Rozpravy Československe Akad. Ved. Řada Mat. Přirod. Věd 80, 3–93 (1970) (German) · Zbl 0199.30201
[11] Rosenberg I.G.: Composition of functions on finite sets, completeness and relations, a short survey. In: Rine, D. (eds) Multiple-valued Logic and Computer Science, 2nd edn., pp. 150–192. North-Holland, Amsterdam (1984)
[12] Rousseau G.: Completeness in finite algebras with a single operation. Proc. Amer. Math. Soc 18, 1009–1013 (1967) · Zbl 0157.04103 · doi:10.1090/S0002-9939-1967-0217002-1
[13] Schofield P.: Independent conditions for completeness of finite algebras with a single generator. J. Lond. Math. Soc 44, 413–423 (1969) · Zbl 0192.33702 · doi:10.1112/jlms/s1-44.1.413
[14] Schölzel, K.: Ein Kriterium für partielle Sheffer-Funktionen in 4-wertiger Logik. Diploma thesis, University of Rostock (2008) (German)
[15] Schölzel, K.: Counting the maximal partial clones on a finite set. Mult.-Valued Logic and Soft Computing (in press) · Zbl 1236.08010
[16] Schölzel, K.: A Sheffer-criterion for partial 4-valued logic. Mult.-Valued Logic and Soft Computing (in press) · Zbl 1236.08011
[17] Sheffer H.M.: A set of five independent postulates for Boolean algebras, with application to logical constants. Trans. Amer. Math. Soc 14, 481–488 (1913) · JFM 44.0076.01 · doi:10.1090/S0002-9947-1913-1500960-1
[18] Webb, D.L.: Generation of an n-valued logic by one binary operation. Bull. Amer. Math. Soc. 41 (1935) · JFM 61.0062.07
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.