Zeitsehr. 1. math. Logik und Grtoidlngen d. Math. Bd . 23, S. 4 0 1 - 4 0 4 (1977)

EIK VOLLSTaDIGER ABLEITUNGSBEGRIFF FOR DIE BQUIVALENZ I N EIKEM FUNKTIONELL UNVOLLSTBNDIGEN

DREIWERTIGEPU' AUSSAGENKALKOL

von H. ROHLEDER in Leipzig (DDR)

Ausgegangen wird von den uber der Menge M = (0, l /2 , l} definierten Funktionen non, et , t d , seq, up, die daclurch festgelegt sind, daB fur alle x, y E W gilt: non,(z) = 1 - x, et(x, y) = RZin(x, y), wel(x. y) = &fax(x, y), seq(x, y) = Max(1 - x, y) und uq(x, y) = = Rlin(sPq(x, y), seq(y, x)) . ' ) Zur Beschreibung der zusammengesetzten Funktionen, die durch wiederholte Anwendung derselben entst,ehen, wird ein Kalkul benutzt, des- sen iZusdriicke man erhalt, wenn beginnend rnit den Ausdriicken 0-ter Stufe F , U , W , p,, p , , p, , . . . die Ausdrucke ( i + 1)-ter Stufe in der iiblichen2) Weise mit Hilfe der Funktoren -, A, v, +, t, und der technischen Zeichen ( , ) aus den Ausdriicken i-ter Stufe zusammengesetzt, werden. Jedem Xusdruck H wird bei jeder Belegung f der Variablen p,! p , , p , , . . . mit Werten aus M eindeutig ein mit Wert(H, f ) bezeichneter Wert aus M zugeordnet. Dabei gilt, bei jeder Belegung f : Wert(F, f ) = 0, Wert( r 7 , f ) = 1/2 und 1Vert( W , f ) = 1. Die Bewertung der ubrigen (zusanimengesetzten) Ausdrucke erfolgt wortlich genauso wie im klassischen Fa11.3)

Der so gegebene dreiwertige Aussagenkalkul ist funktionell unvollstandig, denn fur jeden nicht konstanten Ausdruck H gilt' Wert(H, f l L ) = 1/2, falls f u alle Variablen mit, 112 belegt.. Deshalb ist z. B. schon jede einstellige Funktion, die dem Argumentwert 1/2 den Funktionsuert 1 zuordnet,, ,nicht mit Hilfe der aufgenommenen Grundfunktionen darst,ellbar. Derselbe iat, jedoch eine echte Erweiterung des klassischen zweiwertigen Aussagenkalkuls, denn ist, f k eine beliebige Belegung, die keiner Variablen den Wert 1 / 2 zuordnet (d. h., jede Variable hat entweder den Wert 0 oder l), so stinimt Wert(H, f k ) fur jeden Xusdruck H , in dem die Konstant'e U nicht vorkommt (der also formal auch ein Ausdruck des klassischen zweiuertigen Aussagenkalkiils isto, rnit der klassischen Interpretation iiberein. Fur zweiwertige Variablen, die aus irgendeinem Grund den Wert 1 / 2 riicht annehmen, sind also vollstandige Verknupfungsmoglichkeiten ~orhanden .~ )

l) Die Funktionen non, e t , oeE wurden von J. LIJKASIEWICZ, 0 logice tr6jwartbsciowej, Ruch filo- zificny 5 (1920), 169- 121, eingefiihrt. Die damit definierbaren Funktionen seq und uq bringen nichts wesentlich Keues. Die Aufnahme der hier nicht eliminierbaren Konstanten bleibt jedoch nicht ohne Folgen.

*) Man vgl. etwa G. ASSER, Einfiihrung in die Mathamatische Logik, Teil I, B. 0. Teubner, Leipzig 1959.

3, Die fur die Eindeutigkeit der Wertdefinition unbedingt notwendigen ayntaktischen Eigen- schaften dcr Ausdriicke erhalt man fast genau wie dort. (Man vgl. etwa H. ROHLEDER, Uber einige Probleme bei der mathematisth exakten Definitim dcr Semantik einer Programmiersprache, EIK 11 (1975), 206-213. Durch die zusatzliche Anfnahme der Konstanten F, U, W andert sich nur der Hilfssatz 1 in naheliegender IVeise).

4, Man vgl. auch die von S. C. KLEENE, Introduction to Metamathematics, North-Holland Publish- ing Po.. Anifiterdam 1952, angegehene Begriindung zur Fentlegung der Funkt,ionen. Der Kalkul wurde in H. HOHLEDER, Uber cine Theorie einiger Klamen von elektrischen Schaltungen, diese Zeitschr. 3 (1957), 225 -291, nachtraglich aus dem funktionell voll&andigen dreiwertigen Kalkiil ausgesondert (mit den hier durchgefiihrten Uberlegungen wird dieeer Umweg iiberflussig). Er wird aber auch yon TH. QKOLEM, A set. theory based on a certain3-valued logic, Mathernatica Scandinavica 8 (196l?), 127 - 136, im Zusammenhang mit einer neuartigen Fundierung der Mengenlehre verwendet.

402 KANSROHLEDER

In der mehrwertigen Logik ist es iiblich,l) eine Menge A (mit A E M ) von aus- gezeichneten Wahrheitswerten einzufiihren und einen Ausdruck H ( A - ) allgemeingiiltig zu nennen - fur H ist A-allgemeingiiltig, wird im folgenden kurz Aag H geschrie- ben -, wenn fur jede Belegung f gilt: Wert(H, f ) E A. Entsprechend heiBt H (A-) erfiillbar - kurz Aef H - , wenn es eine Belegung f gibt, so daB Wert(H, f ) E A. AuBer- dem werden im folgenden zwei Ausdriicke H, und H, senmntisch aquivalent genannt - kurz H , A'qsem H , -, wenn bei jeder Belegung f gilt: Wert(H,, f ) = TYert(H,, f ) . Offenbar gilt fur die normalerweise benutzten Mengen A = (1) bzw. A^ = (1, 1/2} von ausgezeichneten Werten :

Aag H genau dann, wenn H Aqsem W .

Aag H genau dann, wenn UH Aqsem U .

AefH genau dann, wenn nicht J a g - H. Aef H genau dann, wenn nicht Aa,g N H .

Weil von allen aufgefiihrten Begriffsbildungen die der semantischen Aquivalenz am starksten ist (in dem Sinn, daB alle anderen damit ausgedriickt werden konnen - die Umkehrung gilt hier jedoch nicht) und weil in die Definition derselben keine spezielle Menge A eingeht, wird im folgenden nur noch diese betrachtet.

Die zweistellige Relation der semantischen Aquivalenz kann rein semiotisch-syntak- tisch (ohne Bezugnahme auf die Semantik) mit Hilfe eines Ableitungsbegriffs charak- terisiert werden. Dazu wird zunachst der Begriff der Ausdrucksgleichung N ie folgt eingefiihrt: Sind H I und H , Ausdriicke, so heiBt das Wort H , = H, (welches man erhalt, wenn das Wort H, mit dem Zeichen = und das so entstandene Wort mit H , verkett,et w i d ) eine (Ausdrucks-) Gleichung.2) Bei der Niederschrift spezieller Glei- chungen werden die darin vorkommenden Ausdriicke in der iiblichen Weise abgekiirzt. AuDerdem aird das Konjunktionszeichen A in den Ausdriicken weggelassen. Beispiele fiir Gleichungen: 3 = p , pq = qp, ( p q p = p(qr), p v q = ?s, q, ( p v q ) p = p , ( p v q ) r = p r v q r , F p = P , W p = p , U = U , U ( F v p ) = U , p + q = p v q , p ++ q = ( p + q ) (q + p ) . Die angegebenen Gleichungen zeichnen sich alle dadurch nus. daB die links und rechts voin Gleichheitszeichen stehenden Ausdrucke mitein- nnder semantisch aquivabit s i n ~ l . ~ )

- -

Im folgenden sol1 aus der Menge aller Gleichungen die Menge AG der ableitbaren Gleic,hungen ausgesondert werden. Damit die SchluBregeln in der gewohnten Form erscheinen, wird dabei fiir H , = H, E =1G zur Abkiirzung I-H, = H , geschrieben. AuI3erdem wird die Menge der im letzteii Abschnit,t angegebenen speziellen Gleichungen als Axiomensystem bezeichnet,.

Defini t ion. Die Menge der ableitbaren Gleichungen AG ist die kleinste Menge, die 1. das Axiomensystem umfaBt,

1) J. B. ROSSER and A. R. TURQUETTE, Many-valued logics. Xorth-Holland Publishing Co.,

2) Die Gleichungen gehoren nicht zum Kalkiil, sondern sind Elemente der Metasprache. Sie sind

3, Das kann man leicht bestatigen, indern fur alle Belegungen der vorhandenen Variablen die Werte

Amsterdam 1852. I

jedoch Worter uber einem Alphabet und konnen deshalb Objekte eines Ableitungsbegriffs sein.

der Ausdriicke ermittelt und verglichen werden.

AQUIVALENZ IN EINEM DREIWERTIGEN AUSSAGENKALKWL 403

2. symmetrisch, transitiv, algebraisch sowie gegeniiber Einsetzungen abgeschlossen

3. abgeschlossen ist gegenuber der folgenden Schlu5regel:

ist,')

Wenn F-UH, = U H , und t U H , = U H , , so F-H, = H,.2)

Im folgenden werden fur den so eingefiihrten Ableitungsbegriff einige Eigenschaften formuliert. Die Beweise fur die angegebenen Satze verlaufen weitgehend analog zu den entsprechenden Beweisen fur den klassischen zweiwertigen Aussagenkalkul. Auf die Angabe derselben wird deshalb verzichtet. Nur an einigen wenigen Stellen wird auf Besonderheiten, die sich aus der Dreiwertigkeit ergeben, hinge~iesen.~)

Sa tz (Widerspruchsfreiheit des Ableitungsbegriffs). Wenn t H , = H,, so sind die Ausdriicke H , und H , semantisch aquivalent.

Der Be w ei s dieser Behauptung erfolgt induktiv iiber die Ableitbarkeitsstufe der Gleichung H , = H,. Beim Induktionsschritt und wenn H , = H , mit Hilfe der SchluBregel 3. abgeleitet worden ist, wird benotigt : Wenn U H , A'qsem U H , und UH, A'qsem U H , , so ist H , A'qsem H,. Das kann wie folgt hergeleitet werden : Wenn U H , Aqsem UH,, so gilt bei jeder Belegung f : Wert(H,, f ) = 0 genau dann, wenn Wert(H,, f ) = 0, denn Wert(UH,, f ) = et(1/2, Wert(H,, f ) = 0 genau dann, wenn TYert(H,, f ) = 0 und fur H , gilt entsprechendes. Aus U H , A'qsem U H , folgt also: H , und H , haben bei denselben Belegungen den Wert 0. Entsprechend erhalt man aus CH, A'qsem UH,: H , und H , haben bei denselben Belegungen den Wert 1. H , und H , miissen also, da es nur drei Werte gibt, auch bei denselben Belegungen den Wert 112 haben und sind deshalb aquivalent.

Erse tzbarke i t s theorem. Ist t H , = H,, und entsteht H , aus H,, i dem in H , an einigen beliebig gewahlten Stellen der Teilausdruck H , durch H,, ersetzt wird, so gilt: F-H, = H,.

Vol ls tandigkei t ssa tz . We7171 H , A'qsern H,, so ist t H , = H,.

Be we is. Derselbe kann wie im klassischen Fa11 mit HiIfe einer Normalformtheorie erfolgen. Hier sind jedoch die vier Ausdriicke UH,, U H , , U H , und U R , aquivalent in kanonische alternative Normalformen K , .,, Kl,2, K2,1 bzw. K,,, umzuwandeln, so daB gilt: t U H , = K1,,, t U H , = K,,,, FUR, = I<,,, und tUl7 , = K ,,,. Aus

I ) AG ist symmetrisch, transitiv, algebraisch und gegeniiber Einsetzungen abgeschlossen, falls gilt: a ) Wenn t H , = H,, so k H , = H,. b) Wenn t H , = H und kH = H,, so t H , = H,. c ) Wenn FH, = H,, so I-R, = H2. d ) \Venn k H i = H ; und Hi' = HY, so ist k ( H i o Hi ' ) = ( H ; o Hi') , falls o ein beliebiger zwei-

stelliger Funktor des Kalkiils ist. e) Wenn t H , = H,, so gehort auch jede daraus durch (siniultane) Einsetzung (bei der fur Variablen

Ausdriicke eingesetzt werden) entstehende Gleichung wieder zu AG. 2 ) Ohne 3. entsteht der in der Algebra allgemein iibliche Ableitungsbegrz. Da aber alle Axioine

auch im n-u-ertigen richt.ige semantische Aquivalenzen sind, ist zu vermuten, daB derselbe nicht vollstandig ist.

E k e ausfuhrliche Darstellung findet sich bei E. HEInIucH, Ein dreiwertiger Aussagenkalkiil in Segation, Konjunktion und Alternative, Diplomarbeit, Leipzig 1968.

404 HANSROHLEDER

H , AqsenL H , folgt dann U H , A'qsem U H , sowie UH, Aqsern lJH, und daraus ahnlich wie im klassischen Fall : Die kanonischen alternativen Normalformen K,,, und K 1 , , - sowie auch K2,1 und K2.2 - stimmen Zeichen fur Zeichen iiberein. Deshalb gilt I-UH, = Kl,l sowie k U H , = K 2 , , . Also erhiilt ma.n wegen der Symmetrie uiid der Transit>ivitat k U H , = U H , bzw. tug, = U a , und daraus schlieBlich mit Hilfe der SchluBregel 3. die Behauptung.

Auch beim AufstJellen einer kanonischen ahernativen Normalform zu einem Sus- druck 6'11 ergeben sich einige Besonderheit,en.l) Die beim , ,Ausmultiplizieren" einer verneinungstechnischen Normalform entstehenden ,,Faktoren" pip i miissen namlich, weil sie im dreiwertigen Kalkiil nicht mit F semantisch aquivalent sind, stehenbleiben, so da.13 eine Variable p , in einer Fundarrieiit'alkoiijuiiktion auBer in unnegierter und negiert'er Form auch in der Form p , p i auftreten kann. Im folgenden wird fur p,p i zur Abkiirzung gi geschrieben. Au13erdem gilt: t U = U ( p i v pi) sowie !-pi = ?;, v p , und k p i = jj, v $;. Wegen der ersten Beziehung kann d a m zwar in jeder Fundamental- konjunktion von U H jede fehlende Variable erganzt und dadurch zu Elementar- konjunktionen iibergegangen werden, es gibt hier aber (im Gegensatz zum klassischen Fall) zu einem Ausdruck U H iIn allgenieinen verschiedene aquivalente alternative Normalformen, deren samtliche Alt,ernativglieder Elementarkonjunktionen sind, denn es gilt z. B. : k p q = ( p v $) (q v 4) = pq v & v Pq v @j. Deshalb muB bei der kanoni- schen alternet'iven Normalform eine zusatzliche Normierung erfolgen, z. B. dadurch, dal3 verlangt wird : Alle Elementarkon junkt'ionen, die Alt,ernat8ivglieder eein konnen (ohne die dquivalenz zu gefahrden), treteii in einer kanonischen albernativen Normal- form auch ale Alternat'ivglieder auf.

l) Ahnliche Betrachhngen findct nian bei J. N. MARTIN, A syntactic characterization of Kleene's st,rong connectives with two designated values, diese Zeitschr. 21 (1975). 181 - 184.

(Eingegangen am 23. biovember 1975)