Zeitschr. i . moth. Logik und Urundlngen d. Math. Rd. 12 , S. 13-22 (1866)

DAS SYNTHESEPROBLEM DER SCHALTALGEBRA UND SEINE MATHEMATISCHE FORMULIERUNG

von H. ROHLEDER in Leipzig

Herrn Prof. Dr. Karl Schroter zum 60. Geburtstag gewidmot

Bekanntlich konnen die verschiedensten Schaltungsarten, die aus Schaltelementen mit zwei stabilen Zustanden aufgebaut sind, durch aussagenlogische Ausdriicke in Negation, Konjunktion und Alternative beschrieben werden.l) Ausdriicke sind dabei spezielle Zeichenreihen aus den Grundzeichen 0 , 1 , a( (i natiirliche Zahl), N, A , v, ( , ) . Die Beschreibung wird durch eine eineindeutige Abbildung vermittelt, durch die jeder geeigneten2) Schaltung eine bestimmte Zeichenreihe und jedem2) Ausdruck eine bestimmte Schaltung effektiv zugeordnet wird.

Bei dem normalerweise verwendeten Aufbau der Theorie kann bewiesen werden, daR zwei Schaltungen genau dann elektrisch gleichwertig sind, wenn die zugeordneten Ausdriicke (semantisch) aquivalent (bzw. Wertverlaufsgleich) sind. Das Problem der Synthese einer zweckmal3igen Schaltung ist deshalb im wesentlichen gelost, wenn es gelingt, zu jedem gegebenen Ausdruck H einen Bquivalenten zu ermitteln, der optimal ist. Der Begriff o.ptimaler Ausdruck ist dabei an eine durch die jeweilige Schaltungsart festgelegte Langenfunktion gekniipft, die jedem zur Beschreibung verwendeten Ausdruck H eine bestimmte natiirliche Zahl (evtl. einschlieBlich 0 ) L,(H) zuordnet. L,(H) ist ein Ma13 fur die Kosten, die beim Aufbau der dem Aus- druck H zugeordneten Schaltung verursacht werden. (Bei den Reihenparallelschal- tungen aus Bontakten ist L,(H) z. B. die Anzahl der Zeichenreihenplatze, auf denen Variablen stehen.) Ein Ausdruck H kann vorlaufig als optimal bezeichnet werden, wenn es keinen aquivalenten Ausdruck zu ihm gibt, der eine kleinere Llinge als H hat. Die zu einem optimalen Ausdruck gehorige Schaltung hat dann die Eigenschaft, daR es keine elcktrisch gleichwertige gibt, die mit geringeren Kosten aufgebaut werden kann.

l) Die meisten der folgenden Uberlegungen lassen sich leicht fur den Fall, daIl man beliebige andere Grundverknupfungen zugrunde legt, verallgemeinern.

2, Im allgemeinen ist nur eine geeignet gewahlte Teilmenge der Menge aller Schaltungen aus bestimmten Schaltelementen einer direkten Beschreibung zugiinglich (z. B. die Menge der Reihenparallelschaltungen als Teilmenge der Kontaktschaltungen), und e8 wird auch nur eine Teilmenge aus der Menge aller Ausdriicke (z. B. die Menge der verneinungstechnischen Normal- formen) zur Beschreibung herangezogen. Auf diese bekannten Zusammenhange und ihre Ver- allgemeinerungen sol1 nicht naher eingegangen werden.

14 H. RORLEDER

Fur eine einheitliche mathematische Behandlung des Problems, zu H ayuivalente optimale Ausdriicke zu suchen, ist es nun auRerordentLich storend, da13 praktisch jede Schaltungsart eine andere Langenfunktion nach sich zieht und deshalb fur jede Art von Schaltungeii eiiie spezielle Optimalisierungstheorie, welche auf die beson- deren Eigenarten der Schaltungen Riicksicht nimmt, entwickelt werden mu13te. Dieser Nachteil kann vermieden werden, wenn iiber der Menge der Zeichenreihen eine geeignete Halbordnungsrelation eingefuhrt wird (man vergleiche such [5 ] ) . Es wird dann namlich moglich, sich eine ffbersicht uber die zu weitgehend beliebiged) Schaltungsarten gehorigen optimalen Ausdriicke zu verschaffen, indem die mini- malen Elemente der Mengen YJH aufgesucht werden. Dabei ist YRH die Menge aller init H aquivalenten Ausdrucke.

Bevor auf die enhprechenden Halbordnungsrelationen naher eingegangen wird, sollen einige allgemeine Bemerkungen uber den Bereich der Zeichenreihen gemacht werden. Zwei endliche Folgen von Grundzeichen (auch Zeichenreihen genannt) 2, und Z , werden verkettet, und es entsteht dadurch die neue Zeichenreihe Z,Z,, indem die beiden Folgen hintereinander geschrieben und als eine Zeichenfolge be- trachtet werden. Zwei Zeichenreihen Z, und Z , sind gleich, und dieser Sachverhalt wird durch Z, = Zz2) zum Ausdruck gebracht, wenn dieselben Zeichen fur Zeichen iibereinstimmen. Z = (2, v 2,) bedeutet also z. B., daB die Zeichenreihe Z ent- steht, indem hintereinander geschrieben werden :

1. die Zeichenreihe, die nur aus dem einen Zeichen ( besteht, 2. die Zeichenreihe Z,, 3. die Zeichenreihe (aus dem einen Grundzeichen) V,

4. die Zeichenreihe Z, und 5. die Zeichenreihe ).

Als Zeichen fur die leere Zeichenreihe, welche iiberhaupt kein Grundzeichen enthalt, sol1 7 verwendet werden. Es ist dann also 7 Z E Z O I = Z (7 ist kein Grundzeichen des Kalkuls, sondern Bezeichnung fur eine spezielle Zeichenreihe, die mit Z ver- kettet werden kann).3)

Von einer Zeichenreihe Z* wird nun gesagt, sie ist in der Zeichenreihe Z enthalten, wenn Z* dadurch aus Z entsteht, da13 einige (beliebig viele) Teilstiicke von 8, die das Zeichen N nicht enthalten, durch die leere Zeichenreihe 7 ersetzt (also einige Grundzeichen von Z ausgeloscht) werden.

s. 16). 1) Die Langenfunktion muB nur eine fast immer erfullte Monotonieforderung erfiillen (8. auch

2) In friiheren Veroffentlichungen wurde die Gleichheit von Zeichenreihen mit = bezeichnet. Es scheint jedoch zweckmiiBig, das Gleichheitszeichen = fur die Aquivalenz zu reservieren.

3) Man kann sich iiberlegen, daB die Menge der Zeichenreihen in bezug auf die Verkettungs- operation eine freie Halbgruppe mit Einselementen ist. Die Menge der Grundzeichen ist ein freies Erzeugendensystem derselben. Alle im folgenden formulierten Satze uber Eigenschaften von Zeichenreihen konnten und multen &us dem entsprechenden Axiomensystem hergeleitet werden. Da jedoch alle hier benutzten Eigenschaften anschaulich evident sind, wird darauf verzichtet werden. (Man vergleiche auch K. SCHROTER [8] bzw. G. ASSER [l].)

DAS SYNTHESEPROBLEM DER SCELALTALCEBRA UND SEINE MATREMATISCHE FORMULIERUNG 15

Defini t ion. Z enthiilt Z* (in Zeichen Z* C Z ) , wenn es ein k 2 0 und Zeichen- reihen z,, z:, z, , zi, 2, , . . . , z:, zk so gibty daf3 gilt : Z = & , ~ ~ z l z ~ ~ , . . . z;zk, z* = ~,z,z2. . . z k sowie 2: f und enthalt nicht das Zeichen - fur alle i mit 1 2 i 5 k . (Fur k = 0 ist 2 = 2, = Z* mit in die Definition eingeschlossen.)

Defini t ion. Z* heiDt echt enthalten in 2, wenn Z* 2 - Z und Z* $E Z ist. Beispiele: (a A c ) C ( ( a v b ) A c) und die zuerst aufgefuhrte Zeichenreihe ist auch

echt in der zweiten enthalten. Dagegen sind (a A b) und ((a v b) A c ) unvergleichbar. Zur einfacheren Formulierung gewisser Zusammenhange soll aul3erdem eine

,,Langenfunktion" L (2) eingefuhrt werden, die nicht unmittelbar durch eine be- stimmte Schaltungsart nahegelegt wird, aber als Beweishilfsmittel eine wichtige Rolle spielt. 1st Z eine beliebige Zeichenreihe, so ist L ( Z ) die Anzahl der Platze von 2, auf denen je ein von - verschiedenes Grundzeichen steht.

Beispiel: L(7) = 0, L(-(a,v ma,)) = 5.

Satz . Wenn 2.2 - 2 , 90 ist L(Z*) Satz . Wenn Z* echt in Z enthalten ist, so gilt: L(Z*) < L(2) . Beide Behauptungen sind anschaulich klar, und aus der zweiten folgt, wie sehr

leicht indirekt zu bestatigen ist : Wenn Z* C - Z und L ( Z * ) = L (2) , so ist Z* = 2 .

S a tz . Die <-Relation ~~ fu r Zeichenreihen ist eine (reflexive) Halbordnungsrelation, d . h. es gilt:

1. Fur jede Zeichenreihe Z ist: Z C 2. 2. Weniz Z,EZ, und 2, C Z 3 , so ist Z, C, 2,. 3. W e n n Z , C Z , u n d Z , ~ Z , , s o i s t Z , = Z , .

L ( Z ) .

Zum Beweis von 3. ware zu sagen: Aus 2,s 2, und Z,c 2, folgt nach den obigen Satzen L(Z,) 5 L(Z,) und L(Z,) 2 L ( Z , ) , also L(Z,) = L(Z,) , und deshalb gilt, weil z. B. 2, CZ,, auch 2, = 2,.

Erse tzba rke i t s theo rem. Ist Z* C Z und entsteht 2, aus Z , , indem an einigen oder an allen Stellen von 2, , an denen 2 in 2, vorkommt, die Zeichenreihe Z durch Z* ersetzt wird, so ist 2,s 2,.

Die Behauptung ist anschaulich klar und kann offenbar auch verscharft werden, indem uberall ,,ist enthalten" durch , ,ist echt enthalten" ersetzt wird.

Fur das folgende sei L, (2) eine beliebige Langenfunktion, die zumindest uber einer Teilmenge der Menge aller Zeichenreihen erklart sein soll, und die im folgenden betrachteten Mengen !Dl von Zeichenreihen seien so gewahlt, daB fur jedes Element Z aus W die Lange L,(Z) erklart ist.

Defini t ion. Eine Langenfunktion L,(Z) heiI3t monoton, falls fur beliebige Zei- chenreihen Z, und Z,, fur die L, erklart ist, gilt: Wenn 2, echt enthalten ist in Z?,

Beispiel. L , ( Z ) (die Anzahl der Platze von 2, auf denen Variablen stehen) ist, eine monotone Langenfunktion. Die Eigenschaft der Monotonie diirfte bei allen Langenfunktionen, die im Zusammenhang mit irgendeiner Schaltungsart auftreten, vorhanden sein.

so folgt: L,(Z,) (= L,(Z,).

16 H. ROHLEDER

Nach diesen Vorbereitungeii kann der Begriff der Optimalitat., der auf Scite 13 provisorisch erklart worden war, prazise gefal3t werden.

Def in i t ion . Eine Zeichenreihe Z heil3t optimales Element der Menge W beziiglich der Langenfunktion L, , wenn Z € W ist, und wenn fur jede Zeichenreihe Z* mit Z* E W gilt:

1. L,(Z) 5 L,(Z*). 8. Wenn L,(Z) = L,(Z*), so ist Z* nicht echt in Z enthalten.

Diese Definition unterscheidet sich von der vorlaufigen Erlrlarung dadurch, daB unter den Zeichenreihen gleicher Lange nur diejenigen als optimal bczeichnet wer- den, die kein anderes Element von YJl echt enthalten (zu denen es also kein beziig- lich anderer monotoner Langenfunktionen gunsbigeres Element von W gibt).

Def in i t ion . Eine Zeichenreihe 2 heil3t ein minimales Element der Menge m, wenn Z E ist und wenn es kein Element Z* von YJl gibt, welches echt in Z ent- hahen ist,.

S a t z. Ist L, eine monotone Langenfzcrakt.ion imd Z bezqlich L, optimales Element von YJl, so ist Z nainimales Element won W .

Beweis. (Indirekt) Angenommen, es gabe ein Z* init Z* ist echt enthslten in 2, so ware, weil L, monoton ist, L,(Z*) 5 L,(Z). Da jedoch Z optimales Element, von 'YJl, also Ls(Z) 5 L,(Z*) ist, folgt L,(Z) = L,(Z*). Es wiiire also eine Zeichen- reihe Z* vorhanden, fur die gilt: Z*E m, L s ( Z ) = L,(Z*) und Z* ist echt in Z enthalten. Das ist jedoch ein Widerspruch zur Voraussetzung (Bedjngung a), dal3 Z bezuglich L , optimales Element von YJl sein sollte.

Vermoge dieses Satzes genugt es, eine Ubersicht uber alle minimalen Elemente einer beliebigen Menge W zu haben, um alle bezuglich einer monotonen Langen- funktion optimalen Elemente von W iibersehen zu konnen. Da es z . B. nur endlich viele minimalen Elernente der Menge W H (die alle mit dem Ausdruck H aquivalen- ten Ausdrucke enthalt) gibt, konnen, falls alle diese minimalen Elemente bekannt sind, die optimalen Elemente von BH bezuglich jecler monotonen Langenfunktion aufgesucht werden, indem zu jedem minimalen Element die Lange ermittelt und so die minimalen Elemente kleinster Lange bestimmt werden. Die eingefuhrte <-Rela- tion und die minimalen Elemente von Ausdrucksmengen haben alle Eige,nschaften, die in [6] benotigt wurden, urn ein Verfahrenl) zum Aufsuchen der minimalen Ele- ment8e von WH, H* angeben zu konnen. Man beachte insbesondere auch den letzten Abschnitt von [5]. Alle wesentlic,hen dort gemachten Aussagen bleiben giiltig ocler sind nur geringfugig zu modifizieren, wenn das Zeicheii C durch C ersetzt wird.2) Da die Menge W H , der beziiglich H* mit H iiquivalenten Ausdrucke fur den Mpezialfall H* = 0 mit WB ubereinstimmt, ist damit auch ein allgemeines Verfahren bekannt, um die minimalen Elemente von Y,Jlfi z i i ermitteln.

l) Der offengebliebene Teil (die minimalen Ausdrucke zu ermitteln, wenn alle Prinifaktoren bzw. Priinsummanden eines Ausdrucks bekannt sind) ist inzwischen unabhangig von [GI durch E. W. SAMSON und L. CALABI beschrieben worden 171.

z, Anstelle der dort beniitzten LLnge L,(H) ist die hier eingefuhrte LLnge L ( H ) zu verwenden.

DAS SYNTHESEPROBLEM DER SCH~LTALGEBU UND SEINE MATHEMATISCHE BORMULIERUNG 17

Das soeben angedeutete Verfahren kann fur den Fall, da13 nicht die Menge FntH der mit H Bquivalenten Ausdriicke, sondern nur %=, die Menge der mit H aqui- valenten (alterna tiven oder konjunktiven) Normalformen betrachtet und die Frage nach deren minimalen Elementen gestellt wird, so spezialisiert werden, daB die iiblichen hfinimalisierungsverfahren (man vergleiche z. B. W. V. QUINE [2] und [3]) entstehen. Ein wesentlicher Unterschied, auf den im folgenden genauer eingegangen werden soll, ist dabei allerdings vorhanden.

Bei der iiblichen Minimalisierungstheorie wird im allgemeinen zwischen Aus- driicken, die durch Vertauschen von Alternativ- bzw. Konjunktionsgliedern und assoziatives Umklammern ineinander iiberfiihrt werden konnen, nicht unterschieden. Das heiot, es werden genau genommen nicht die Ausdriicke (als Zeichenreihen), sondern gewisse Bquivalenzklassen von Ausdriicken betrachtet. Die zugrunde liegende Aquivalenzrelation kann dabei folgendermaoen charakterisiert werden :

Zwei Ausdriicke H, und H, heil3en bis auf Umordnung gleich (in Zeichen HI 22 H,), wenn H, aus H , mit Hilfe der ublichen Umformungsregeln (Symmetrie sowie Transiti- vitat der Zg-Relation, Einsetzungsregel und Ersetzbarkeitstheorem) erhalten wer- den kann, wobei alsAxiomensystem dieMenge von Gleichungen a 22 a , a v b 22 b v a , ab 22 ba, (a v b ) v c 2s a v (b v c ) und (ab) c 22 a(bc) zu verwenden ist. (Diese Bqui- valenzrelation ist in [5] ausfiihrlich diskutiert und sowohl semantisch als auch syntaktisch charakterisiert worden.) Fur die Ausdriicke H, = rib v 65 v acd und H , = $5 v udc v bii gilt z. B. H, 22 H,.

Dadurch, daB bis auf Umordnung gleiche Ausdriicke nicht voneinander unter- schieden werden, reduziert sich die Anzahl der minimalen Elemente von !JtH ganz betrachtlich. (Die soeben als Beispiele angegebenen Ausdriicke H, und H , sind in diesem Sinne, da sie zur gleichen Bquivalenzklasse gehoren, als eine minimale Normalform zu zahlen.) Die zuletzt angewandte Betrachtungsweise ist allerdings nicht ganz unproblematisch, weil die bisher verwendete Halbordnungsrelation (2) mit der eingefiihrten Aquivalenzrelation (22) unvertraglich ist. So gehort z. B. zu (a A c) die Bquivalenzklasse $jl = {(a A c ) , ( c A a)} , wahrend die durch ((a A b) v c ) erzeugte Bquivalenzklasse @, = { ( (a A b ) v c ) , ( ( b A a) v c ) , (c v (a A a ) ) , (c v ( b A a))} ist. Es ist nun (a A c ) C ( (a A b ) v c ) , wogegen der Ausdruck ( ( b A a) v c ) , der eben- falls in @, ist, keinen Reprasentanten von im Sinne der <-Relation enthalt. Die C-Relation kann deshalb nicht reprasentantenweise auf die lquivalenzklassen aus- gedehnt werden.

Dagegen ist folgende Verallgemeinerung moglich: (Man beachte, daB die uber- legungen keinen Gebrauch von den speziellen Eigenschaften der 22-Relation machen. Beniitzt wird nur : Die 2L-Beziehung ist eine Aquivalenzrelation, und es gibt eine beziiglich der C-Relation echtl) monotone Liingenfunktion L, so daB gilt: Wenn H , 22 H,. SO ist L(HJ = L(H,).)

l) L heiBt echt monoton, falls aus Z* ist echt enthalten in 2 sogar L(Z*) < L(Z) gefolgert

2 Ztschr. I. math. Logik

werden kann.

18 R. ROHLEDER

Defini t ion. Sind Q1 und Q2 Bquivalenzklassen von Ausdriicken beziiglich der &Relation, so heiRt Q1 enthalten i n @,(@, 2 @,)l), wenn es zu jedem Element H , von 8, ein Element H I von Q, gibt, so daR H , C H, gilt. (Die oben als Beispiele angegebenen Klassen und Q, sind nach dieser Definition also nicht ineinander enthalten.)

Sat z. Die 2-Relation fiir Bquivalenzklassen ist eine Halbordnungsrelation.

Beweis. Fur jede Aquivalenzklasse @ gilt 8 2 @, denn jedes Element von 8 ist im Sinne der 2-Relation in sich aelbst enthalten. 1st Ql 2 @, und Q, 2 @,, so gibt es zu jedem H , E Q, ein H , E Q, mit H , C H,, und zu jedem H , E Q, gibt es ein H , E 8, mit H , 2 H , . Wegen der Transitivitat der C-Relation ist dann auch H , C H,, d. h., zu jedem H3 E $5, gibt es ein H I E Q, rnit HI C H 3 , wodureh auch die Transitivi- tZit der 2-Relation fur Bquivalenzklassen gesichert ist.

Es bleibt noch zu zeigen: Wenn Q, 2 $3, und Q, 2 8, , so ist = @, (wobei natiir- lich die mengentheoretische Gleichheit gemeint ist) : Wegen der ersten Voraus- setzung gibt es zu jedem H , E @, ein H , E 8, mit H , C H,, und weil auch @, 5 @, ist, kann zu H , ein H b E Q, mit H,* C H I gefunden werden. Es ist also auch H,* C H , . Behauptung: Es gilt sogar H,* = H , , denn angenommen, das ware nicht der Pall, so ware H,* echt in H2 enthalten und deshalb L (H,*) < L ( H , ) . Das ist aber, weil H,* und H , beide aus @, sind, also H,* 22 H , gilt, unmoglich. Aus H , C H , und H , H , folgt H , 3 H , . Also ist jedes Element von @, auch Element von 8,. Die umgekehrte Richtung des letzten Satzes ergibt sich, indem die Rollen von 8, und @, vertauscht werden.

Durch die soeben fiir den Bereich der dquivalenzklassen eingefiihrte 2-Relation ist auch fur beliebige Ausdriicke eine zweistellige (quasi Halbordnungs-) Relation festgelegt .

und $3, sowie Q, diejenigen dquivalenzklassen mit H I E Defini t ion. Fur zwei Ausdriicke H , und H , gilt H , 2 H,,) , wenn @, 8, ist

bzw. H , E 8, sind.

Diese Relation ist mit der 22-Relation vertriiglich, d. h., es gilt der folgende

Satz . H , 22 H , genau dann, wenn H , 2 H , und H , 2 H I .

Beweis. Wenn H , 22 H,, so ist 8, = a,, also @, 2 @, und $j2 5 @,. Falls dagegen HI 2 H , und H , 2 H , gilt, so folgt nach der Definition @, 2 Q, und 8, 2 @,, also weil die 2-Relation fiir Aquivalenzklassen eine Halbordnung ist, auch @, = @,.

Die so eingefiihrte zweistellige Relation fur beliebige Ausdriicke hat vieles mit der in [5] eingefuhrten ,,Halbordnungsrelation" (diese sol1 hier rnit H I 2 H , be-

zeichnet werden) gemeinsam. (Es gilt z. B. auch H , 22 H , genau dann, wenn [61

1) Die Bezeichnungsw eise ist &was problematisch. Die mengentheoretische Enthaltemeins-

2) Das Zeichen C ist von C .. wohl zu unterscheiden. Beziehung fiir G1 und Q2 wird im folgenden jedoch nicht benotigt.

~

DAS SYNTHESEPROBLEM DER SCHALTALGEBRA UND SEINE MATHEDZATISCHE FORMULIERUNO 19

H I H , sowie H , 2 H,, und beide haben dieselbe echt monotone Langenfunk-

tion L.) Die neue Halbordnung ist aber ,,starker'' als die alte in dem Sinne, dal3 gilt: Wenn H, 2 H , , so ist H , 5 H,. Diese Behauptung kann leicht induktiv iiber

die Stufe der Richtigkeit von H , 2 H, bestiitigt werden. Die Umkehrung ist dagegen

falsch, denn es ist ab $ ax v ay v bz.

151 [51

L.51

151

Die 2-Relation hat zusatzlich die Eigenschaft, mit den beiden zweistelligen

,,Operationen" fur Ausdriicke ,,v" und , ,A" vertraglich zu sein. Es gilt namlich: [51

1. AUS H, = ( H , 0 H)') folgt H , 5 H,. 151

2. Sind die beiden Ausdriicke H, und Ha gegeben durchl) H , = ( H : o HY) bzw. H , = ( H i 0 H i ) , und gelten die Relationen H: 2 H ; sowie HY 2 HY, so ist auch Hi 2 H2. [51 [51

[51

Aus dieser Vertraglichkeit kann unter wenig einschneidenden Voraussetzungen2) auf das Ersetzbarkeitstheorem geschlossen werden. Sie ist jedoch fur die 2-Relation nicht gewahrleistet. Gegenbeispiel: ab 2 ax v ay v bz und c c, dagegen ist ab v c nicht in ax v ay v bz v c enthalten, denn ax v ay v c v hs enthalt keinen mit ab v c bis auf Umordnung gleichen Ausdruck.

Da bei dem in [S] geschilderten Verfahren diese Vertraglichkeit der Halbordnungs- relation benotigt wird, kommt nur die 2-Relation fur die entsprechenden Uber-

151 legungen in Frage. Weil jedoch alle bezuglich der 2-Relation minimalen Elemente einer beliebigen Menge unter den bezuglich der 2-Relation minimalen Elementen

von 92 enthalten sind (denn angenommen, es gabe ein H* mit H* E 8l und H* 2 H ,

so ware auch H* 2 H ) , erhalt man dadurch zwar unter Umstanden einige zusatzliche minimale Elemente, aber auf jeden Fall alle die, welche zum Auswahlen der opti- malen Elemente erforderlich sind. Der ubergang, welcher dem von der 2-Relation zur $-Relation entspricht, ist ziemlich allgemein auch fur den Fall moglich, daB

eine von der 2L-Relation verschiedene Aquivalenzrelation zugrunde gelegt wird. Die Definition der Halbordnung, die der C_-Relation entspricht, kann z. B. wie in

[5] S. 43 erfolgen, nur ist statt der 2L-Relation die gerade betrachtete Aquivalenz zu beniitzen.

Durch die bisherigen Ausfiihrungen wird es nahegelegt, nach weiteren moglichst ,,starrkeren" Aquivalenzrelationen zu suchen, urn durch eine zugehorige dann eben- falls .,starkere" Halbordnungsrelation sicherzustellen, daB die Anzahl der in Be- tracht lrommenden minimalen Elemente (z. B. dcr Mengen %RH, herabgedriickt,

I ) Fur das Zeichen o darf nacli Belieben (aber an allen Stellen des Satzes einheitlich) v bzw. A

?) Man vergleiche den in [5] S. 34 angegebenen Beweis. Als Voraussetzung sind die in der

2*

r51

[51

151

[51

gesetzt werden.

FuDnote von S. 29 aufgefuhrten Satze zu betrachten.

20 I€. ROHLEDER

werden kann. Wenn die Anzahl der moglichen Losungen f iir eine Aufgabenstellung reduziert wird, ist niimlich auch ein Absinken des Arbeitsaufwandes zu erwarten, der benotigt wird, um dieselben zu konstruieren. (Im Verlauf des Konstruktions- algorithmus diirften, weil weniger Objekte auseinandergehalten werden miissen, auch weniger Fallunterscheidungen auftreten.)

Fur diesen Zweck bieten sich zunachst einmal die wohl zuerst in [9] betrachteten Eingangstransformationen an. Viele Ausdriicke H haben Symmetrien in dem Sinnc, daB es eine Gruppe kY von Eingangstransformationen derart gibt, daB 8 ( H ) 2 mH ist, wobei unter @ ( H ) die Menge von Ausdrucken verstanden wird, die entsteht, wenn eine beliebige Transformation am 63 auf H angewendet wird. Die Bedingung @ ( H ) 2 llJZH ist, weil 8 die identische Transformation als Einselement enthalt, gleichwertig mit 8(llJZH) = !EH. l ) Gilt nun sowohl a('%,) = YJtH als auch @(!EH*) = !En,*, SO folgt 8(!JJlH, H * ) = mH, H I , und die minimalen Elemente von (3 (%RE, ,*) stimmen dann natiirlich mit den von ! J J I H , iiberein. h d e r t sich dariiber hinaus beim Anwenden einer Transformation aus 8 auch die Lange des betrach- teten Ausdrucks nicht, was in den meisten Fallen gewahrleistet ist, so scheint fol- gende Festsetzung sinnvoll :

Defini t ion. Zwei Ausdriicke H I und H , heiBen beziiglich @ typengleich (in Zei- chen H , H , ) , wenn es eine Transformation 91 E (35 gibt rnit % ( H I ) 2s H , . ,)

(3

Die durch diese Bquivalenzrelation festgelegte Halbordnungsrelation, welche j e nach dem speziellen H und H* unterschiedlich ist, beriicksichtigt die Symmetrien der gerade betrachteten Ausdriicke H sowie H* und vermeidet uberfliissige Unter- scheidungen, ohne die Menge der Ausdriicke, cleren minimale Elemente gesucht sind, zu vergrol3ern. Die angedeutete Betrachtungsweise diirfte besonders wirkungs- voll sein, wenn nur die mit H (beziiglich H*) aquivalenten alternativen bzw. kon- junktiven Normalformen zur Debatte stehen, denn gerade bei Ausdriicken mit vielen Symmetrien sind die bisher bekannten Verfahren hierfiir recht ungunstig.

Nimmt man eine VergroBerung der Menge, aus welcher die minimalen Elemente auszuwahlen sind, in Kauf, so kann die Typengleichheit beziiglich der Gruppe aller Eingangstransformationen als Bquivalenzrelation in Betracht gezogen werden. Diese Relation fiihrt im allgemeinen aus der Menge der mit H beziiglich H* aquivalenten Ausdriicke hinaus, und es sind deshalb die minimalen Elemente aus der Menge der rnit H bezuglich H* typenaquivalenten Ausdriicke aufzusuchen. Das so entstehende Verfahren diirfte trotzdem gunstiger sein als das fruher geschilderte, welches nur die Bquivalenz ausniitzt, denn selbst wenn das Problem uberhaupt keine Symmetrien aufweist, ist die Zahl der als Losung in Frage kommenden minimalen Elemente nicht groBer als im Falle der Aquivalenz, denn alle nicht iiquivalenten Ausdriicke lassen sich durch Eingangstransformationen in aquivalente umwandeln und sind

l) @(%TI) unifadt alle Ausdriicke, die entstehen, wenn ein Element von OI auf ein Element

2, Fur den Fall, dad % ( H I ) nur mit H , aquivalent ist, wird man H , und H , zweckmiidiger- von XR angewendet wird.

weise typeruiquiuabnt bezuglich (3 nennen.

DAS SYNTIIESEPROBLEM DER SCHALTALQEBRA UND SEINE MATHEMATISCHE FORMULIERUNa 21

deshalb im Sinne der zugehorigen dquivalenzrelation nicht zu unterscheiden. Sind dagegen Symmetrien vorhanden, so fallen auch untereinander aquivalente minimale Elemente im Sinne der Aquivalenzrelation noch zusammen, und dadurch wird die Anzahl der zu unterscheidenden minimalen Elemente kleiner. Die Anzahl der in den betrachteten Mengen enthaltenen Ausdriicke wird also zwar grofier, die Anzahl ihrer dquivalenzklassen jedoch und die der Ergebnisse wird im allgemeinen kleiner.

Stammte die Problemstellung von einer gelosten Aufgabe aus der Autometen- theorie ab (handelt es sich also darum, moglichst einfache Schaltkreise zu ermitteln, welche die Verbindung zwischen den verschiedenen Zwischenelementen des gesuchten Schaltwerks herstellen), so kann die Gruppe der Eingangstransformationen noch verallgemeinert werden. Jede Zuordnung von ,,Elementarkonjunktionen der Zwi- schenvariablen" zu bestimmten ,,Zustiinden des Schaltwerks" kann namlich durch eine der in [4] angegebenen Transformationen aus einer beliebigen festgehaltenen solchen Zuordnung erzeugt werden. La& man also zu, daB die Wahl der Zuordnung erst bei der Festlegung der Schaltkreise erfolgt und so vorgenommen wird, daR die Schaltkreise moglichst einfach werden, so wird man auf eine Aquivalenzrelation gefiihrt , bei der statt der Eingangstransformationen allgemeinere Transformationen verwendet werden konnen, die aber sonst entsprechend wie die Typengleichheit zu bilden ist.

Diese allgemeineren Transformationen gestatten f iir die Eingnngsvariablen des Schaltwerks beliebige Permutationen und Negationen (genau wie die Eingangs- transformationen), wahrend fur die Zwischenvariablen des Schaltwerks (deren Elementarkonjunktionen eineindeutig den inneren Zustanden desselben zugeordnet sind) die Transformationen von [4] (welche eine beliebige Permutation der Elementar- konjunktionen aus den Zwischenvariablen erlauben) angewendet werden durfen. Wird auch die Codierung der dem Schaltwerk von aulJen zugefuhrten Signale noch freigelassen, so erweitern sich auch die Transformationsmoglichkeiten fur die Ein- gangsvarinblen entsprechend.

Es gilt hier sinngemaR dasselbe, was uber die Eingangstransformationen gesagt wurde. Dadurch, daIJ die Anzahl der Bquivalenzklassen nicht vergroRert, durch die allgemeineren Transformationen aber eine starkere Aquivalenzrelation induziert wird, ist ein Absinken des Arbeitsaufwandes bei der Konstruktion der minimalen Elemente zu erwarten. Dadurch gelingt es, das Niitzliche mit dem Angenehmen zu verbinden, denn die voraussichtlich einfacher zu konstruierenden optimalen Schalt- kreise legen zugleich die zweckmal3ige Wahl der Zuordnung von ,,Zustanden des Schaltwerks" und , ,Elementarkonjunktionen der Zwischenvariablen" mit fest.

Anmerkung be i der K o r r e k t u r : Man vergleiche hierzu auch [lo].

22 H. ROHLEDER

Literatur

[I] G. ASSER, Einfuhrung in die mathematische Logik. Leipzig 1959. [2] W. V. QUINE, The problem of simplifying truth functions. The American Mathematical

[3] W. V. QUINE, A way to simplify truth functions. The American Mathematical Monthly 62

[4] H. RORLEDER, Zur Umformung einer speziellen Klasse von Rechenverfahren. Diese Zeitschr. 8

[5] H. ROHLEDER, Eine Halbordnung im Aussagenkalkiil. Diese Zeitschr. 9 (19ed), 21 -52. [6] H. ROHLEDER, Ein Verfahren zum Aufsuchen minimaler Ausdrucke. Diese Zeitschr. 9

E7] E. W. SAMSON and L. CALABI, On the theory of Boolean formulas: minimal including sums

[S] K. SCHROTER, Ein allgemeiner Kalkiilbegriff. Forsch. Logik Grundl. exakt. Wiss. N. F. 6

191 Staff of the Computation Laboratory, Synthesis of electronic computing and control circuits.

N a c h t r a g : 1101 S. GERBER und H. ROELEDEE, Ober eine einheitliche Formalisierung von Automaten und

Algorithmen. Wird erscheinen in : Kolloquium iiher Automatentheorie 19. -22. Oktober 1965, Hannover.

Monthly 59 (1952), 521-531.

(1955), 627-631.

(1962), 201-246.

(19G3), 125-140.

I, 11. J. Soc. industr. appl. Math. 11 (1963), 212-223 und 224-234.

(1941).

The Annals of the Cornputation Laboratory of Havard University 27 (1951).

(Eingegangen am 27. Miirz 1965)