DIE VERTAUSCHBAREN FUNKTIONEN DER k-WERTIGEN LOGIK UND EIN BASISPROBLEM von W. HARNAU in Rostock (DDR) Einfuhrung Diese Arbeit baut inhaltlich auf dem Artikel [I] auf. Dort wurde eine Definition der F7ertauschbarkeit von Funktionen der k-wertigen Logik gegeben. I n dieser Srbeit wird nun, nachdem im ersten Paragraphen die benotigten Hilfsmittel bereitgestellt werden, im zweiten Paragraphen die Menge (P:) der vertauschbaren Funktionen der k-wertigen Logik definiert und untersucht, welche prtivollstandigen Klassen in Py enthalten sind. Der dritte Paragraph schlieljlich beschaftigt sich mit der Frage, welche V&, zur Erzeugung von P : notwendig sind, das heiljt, dalj ihre Vereinigungsmenge gleich P : ist. V7eiter wird gezeigt, dalj die minimalen Mengen (Basen) der f ( x ) , deren V;,,, als Vereinigung P; ergeben, im wesentlichen gleich sind und da13 alle V;,,,, die durch eine solche Basis erzeugt werden, maximale Elemente der Struktur @/& von [I] sind. Nicht versaumen mochte ich es, insbesondere den Herren W. B. KUDRJAWZEW (Moskau) und G. BUROSCH (Rostock) fur wertvolle Hinweise zu dieser Arbeit zu danken. 5 1. Vorbereitende Betrachtungen Ale Begriffe und Bezeichnungen, die in dieser Arbeit benutzt, aber nicht definiert werden, findet man in [l] definiert oder zumindest dort einen Vermerk dariiber, wo sie definiert sind (zumeist wird es [Z] sein). In [S] gab M. I. ROSENBERG erstmals alle pravollstandigen Klassen der k-wertigen Logik an und kam bei ihrer Klassifikation mit sechs Typen aus. Diese Typen werden wir wie in [3] mit M , S, L, U , C nnd B bezeichnen. Zur Definition der pravollstandigen Klassen vom Typ X (Selbstdualitat) und U (die Klassen Uhl,M2,.., M,) vergleiche man z. B. [I] oder [ 2 ] . Sei r eine reflexive Halbordnungsrelation (sr) auf E/,. Seien a,, b, E E/, fur i = 1 , 2 , . . . , n. 13% schreiben dann: (1) ( a ~> ~Z , * -* , a n ) S r ( b l j b , > * -. > 4 t ) , wenn a, sr b, fur i = 1 , 2 , . . . , n ist. Es liege f (x,, x,, . . . , xn) E Pk genau dann in M Px , wenn fiir alle Paare von n-Tupeln mit der Eigenschaft (1)
/(a19 a29 * * Y an) s r f ( b , , b2, . f . , 4 , ) gilt. Nun bewies W. W. MARTINJUK in [5] den S a t z 1.1. M' ist genau dann prtivollstandig und wird vom T y p M genannt, wenn die reflexive Halbordnun~srelntio.II. r auf E,, genau ein maximales und ein minimales Element besitzt.