Inhaltsverzeichnis
2. Algorithmisches Erkennen bestimmter Strukturmerkmale von Mechanismen

2.1. Theoretische Grundlagen

2.1.1. Assur-Gruppen

• Definition: Basistyp
  Als Basistyp wird der zweigliedrige MT bezeichnet, bestehend nur aus dem Gestell und dem durch ein Gelenk mit ihm verbundenen Antrieb.

Als Mittel zur Strukturanalyse von Mechanismen wird in dieser Arbeit vor allem das Zerlegen in Gruppen verwendet. Aus der strukturellen Beziehung der verschiedenen Gruppen zueinander lassen sich Eigenschaften wie Bewegungsabhängigkeit von Gliedern und Eigentlichkeit eines Mechanismus erkennen.

• Definition 1: Erweiterungsgruppe
  Eine Gruppe von mit Gelenken verbundenen Gliedern heißt Erweiterungsgruppe, wenn
  (1) die Glieder zusammenhängend sind und
  (2) einige von ihnen als Verbindungsglieder ausgezeichnet sind.

• Definition 2: Erweiterung und Reduktion um eine Erweiterungsgruppe
  Eine Ausgangsgruppe (z.B. ein Mechanismen-Typ) von mit Gelenken verbundenen Gliedern wird um eine Erweiterungsgruppe erweitert, indem jedes Verbindungsglied der Erweiterungsgruppe durch je ein zusätzliches Gelenk mit einem beliebigen Glied der Ausgangsgruppe verbunden wird. Insgesamt müssen dabei mindestens zwei Glieder der Ausgangsgruppe verbunden werden.

  Der umgekehrte Vorgang, also das Entfernen aller Glieder und Gelenke, die aus einer Erweiterung um eine Erweiterungsgruppe entstanden sein könnten, wird als Reduktion um diese Erweiterungsgruppe bezeichnet.

Welche Eigenschaften wünscht man sich nun für solche Erweiterungsgruppen, um ein mächtiges Mittel zur Strukturanalyse von MTen zu erhalten? Die Erweiterung um solche Gruppen sollte folgende Merkmale aufweisen:

• Vollständigkeit, d.h. jeder MT lässt sich in den Basismechanismus und solche Gruppen zerlegen.
• Korrektheit, d.h. jede Struktur, die sich aus diesen Gruppen aufbauen lässt, ist ein MT.
• Eindeutigkeit der Zerlegung.

Allgemeine Erweiterungsgruppen nach Definition 1 werden diesen Wünschen nicht gerecht, denn außer Vollständigkeit erfüllt die Erweiterung um sie keine der Vorgaben. Es werden spezielle Erweiterungsgruppen mit einer strengeren Definition benötigt, die Korrektheit und Eindeutigkeit sicher stellt, ohne dass dabei die Vollständigkeit verloren geht. Solche Gruppen wurden 1952 von Assur vorgeschlagen. Wie im Anschluss gezeigt wird, weisen diese Assur-Gruppen tatsächlich alle gewünschten Eigenschaften auf.

• Definition 3: Assur-Gruppe
  Eine Erweiterungsgruppe heißt Assur-Gruppe, wenn ein Mechanismen-Typ existiert, der sich so um diese Gruppe erweitern lässt, dass wiederum ein Mechanismen-Typ entsteht, ohne dass sich diese Erweiterung in schrittweise Teilerweiterungen über dritte Mechanismen-Typen unterteilen lässt.

Notation:
Erweitert eine AG einen MT A auf einen MT B, so wird sie fortan als "A→B" notiert.

Dass die Erweiterung um diese Gruppen immer noch vollständig ist, ergibt sich unmittelbar aus ihrer Definition:

• Satz 1: Vollständigkeit der Erweiterung um Assur-Gruppen
  Jeder Mechanismen-Typ kann aus dem Basistyp durch Erweiterung um Assur-Gruppen abgeleitet werden.

Beweis: Es wird bewiesen, dass sich jede Erweiterung eines MTs A auf einen MT B auch als Erweiterung um eine oder mehrere AGn durchführen lässt. Wird für A der Basismechanismus eingesetzt, ergibt sich sofort die Behauptung. Der Beweis erfolgt als vollständige Induktion über die Differenz der Gliederzahlen |B|-|A| = d. Der Fall n=2 ist trivial, denn eine Erweiterung um zwei Glieder lässt sich nicht schrittweise durchführen (Mechanismen-Typen gibt es nur mit gerader Anzahl von Gliedern) und ist demnach immer selbst eine Erweiterung um eine AG. Für den Induktionsschritt kann vorausgesetzt werden, dass die Aussage für Paare von MTen mit |B|-|A| < d gilt. Lässt sich die Erweiterung von A auf B nicht in Teilschritte über dritte MTen unterteilen, dann ist die Erweiterungsgruppe selbst eine AG. Lässt sich die Erweiterung dagegen auf diese Art unterteilen, dann ist bei jedem der Erweiterungsschritte die Differenz der Gliederzahlen von Ausgangs- und Ergebnismechanismus kleiner als d. Jede einzelne Erweiterungen lässt sich also auch mit AGn vornehmen, und damit auch die gesamte Erweiterung.

Bevor nun die weiteren geforderten Eigenschaften bewiesen werden, erfolgt zunächst die numerische Analyse von AGn: Anhand welches Kriteriums kann ein maschinengerechter Algorithmus zweifelsfrei unterscheiden, welche Erweiterungsgruppe eine AG ist und welche nicht? Diese Untersuchung ist sowieso notwendig, um die hier entwickelten theoretischen Methoden automatisieren zu können, und möglicherweise sind die dabei gewonnenen Erkenntnisse bei den noch offen stehenden Beweisen hilfreich. Gesucht ist also eine numerische Aussage für AGn, die gleichzeitig notwendig und hinreichend ist, sozusagen eine alternative Definition. Dazu als Erstes ein einfacher Zusammenhang zwischen Glieder- und Gelenkzahl einer AG, der sich aus der Zwangläufigkeit schlussfolgern lässt:

• Satz 2: Glieder- und Gelenkzahl einer Assurgruppe
  Wenn n die Anzahl der Glieder, k die Anzahl der Gelenke und c die Anzahl der Verbindungsglieder einer Assur-Gruppe ist, dann gilt 3n = 2(k+c).

Beweis: Folgt aus der Zwanglaufbedingung. Die AG sei M0→M1. Die beiden MTen sind zwangläufig: (1) 3(n0-1)-2k0 = 1 (2) 3(n1-1)-2k1 = 1 Bei der Erweiterung kommen die n Glieder und k Gelenke der Gruppe dazu, zusätzlich ein neues Gelenk für jedes Verbindungsglied: (3) n1 = n0+n (4) k1 = k0+k+c also (2),(3),(4) = (5) 3(n0+n-1)-2(k0+k+c) = 1 (5)-(1) = Behauptung

• Satz 3: Numerische Definition für Assur-Gruppen
  Eine Erweiterungsgruppe mit n Gliedern, k Gelenken und c Verbindungsgliedern ist genau dann eine Assur-Gruppe, wenn gilt:
  (1) 3n = 2(k+c)
  (2) 3n' > 2(k'+c') für alle echten Untermengen sowie
  (3) 3n' ≥ 2(k'+2) für alle echten Untermengen mit mindestens drei Gliedern,
  wobei n' die Anzahl der Glieder der Untermenge, k' die Anzahl der sie verbindenden Gelenke und c' die Anzahl der enthaltenen Verbindungsglieder ist.

Beweis (Hinrichtung): Es muss gezeigt werden, dass sich ein MT so um die Gruppe erweitern lässt, dass wiederum ein MT entsteht. An dieser Stelle wird gleich eine starke Verallgemeinerung bewiesen: Jede Erweiterung eines MTs um eine Erweiterungsgruppe mit diesen numerischen Eigenschaften ist wieder ein MT. Das ist gleichzeitig auch der gesuchte Nachweis der Korrektheit (Satz 4). Die richtige Anzahl von Gelenken für den entstehenden MT M1 lässt sich auf folgende Art aus der Zwanglaufbedingung folgern. Der zu erweiternde MT M0 ist zwangläufig: (4) 3(n0-1)-2k0 = 1 Bei der Erweiterung kommen die n Glieder und k Gelenke der Gruppe dazu, zusätzlich ein neues Gelenk für jedes Verbindungsglied: (5) n1 = n0+n (6) k1 = k0+k+c (7) 3(n1-1)-2k1 = 3(n0+n-1)-2(k0+k+c) = 3(n0-1)-2k0 +3n-2(k+c) also wegen (1) und (4): (8) 3(n1-1)-2k1 = 1 Nun ist zu zeigen, dass der gebildete MT keine starren Teilstrukturen enthält; dass sich also für alle Untermengen ein Freiheitsgrad ≥1 ergibt. Bei einer zu untersuchenden Untermenge mit n' Gliedern und k' Gelenken bezeichne Index M die Glieder, die zum Ursprungsmechanismus gehören, und Index E die zur Erweiterungsgruppe gehörigen: Fall 1: nM = 0 Die Untermenge enthält ausschließlich Glieder aus der Erweiterungsgruppe. Bedingung (3) stellt ausreichende Freiheit sicher. Fall 2: nM = 1 Die Untermenge enthält neben Gliedern aus der Erweiterungsgruppe genau ein Glied des Ausgangsmechanismus. Fall 2a: nE = n Alle Glieder der Erweiterungsgruppe sind in der Untermenge enthalten. Nach Definition einer Erweiterung dürfen nicht alle Verbindungsglieder mit dem gleichen Glied verbunden werden. Da aber nur ein Glied des Ausgangsmechanismus in der Untermenge enthalten ist, gibt es mindestens ein Verbindungsglied, das bei der Erweiterung kein neues Gelenk innerhalb der Untermenge erzeugt. (9) k' ≤ kE+cE-1 (10) -2(k'-kE-cE) ≥ 2 (11) 3(nM-1)-2(k'-kE-cE) ≥ 2 (da nM = 1) Hier weiter wie in Fall 3. Fall 2b: nE < n (9) k' ≤ kE+cE (an jedem Verbindungsglied kann maximal ein neues Gelenk entstehen) (10) -2(k'-kE-cE) ≥ 0 (11) 3(n'-nE-1)-2(k'-kE-cE) ≥ 0 (denn n'-nE = nM = 1) (12) 3(n'-1) -2k'-3nE+2kE+2cE ≥ 0 (13) 3nE - 2(cE+kE) > 0 (wegen (2)) (12)+(13) = (14) 3(n'-1)-2k' > 0 Das ist gerade der Freiheitsgrad der untersuchten Untermenge. Fall 3: nM > 1 (9) 3(nM-1)-2kM ≥ 1 (da ursprünglicher MT keine starren Teilstrukturen enthält) (10) k' ≤ kM+kE+cE (an jedem Verbindungsglied kann maximal ein neues Gelenk entstehen) (9),(10) = (11) 3(nM-1)-2(k'-kE-cE) ≥ 1 (12) 3(n'-nE-1)-2(k'-kE-cE) ≥ 1 (13) 3(n'-1) -2k'-3nE+2kE+2cE ≥ 1 (14) 3nE ≥ 2(cE+kE) (wegen (1) wenn nE = n, sonst wegen (2)) (13),(14) = (15) 3(n'-1)-2k' ≥ 1 Das ist wieder der Freiheitsgrad der Untermenge. Zuletzt muss noch bewiesen werden, dass sich die Erweiterung nicht in schrittweise Teilerweiterungen über dritte MTen unterteilen lässt. Wäre dies möglich, dann könnten diese Erweiterungen nach Satz 1 auch mit AGn durchgeführt werden. Für die AG, um die dabei als erste erweitert wird, müsste nach Satz 2 gelten: 3n' = 2(k'+c'). Das widerspricht aber Bedingung (2).

Beweis (Rückrichtung): Bedingung (1) ist Satz 2. Bedingung (3) lässt sich ebenfalls aus der Zwanglaufgleichung ableiten. Laut Definition existiert ein MT, der sich so um diese Gruppe erweitern lässt, dass wieder ein MT entsteht. Da jede der Untermengen der Gruppe auch Untermenge des so gebildeten MTs ist, muss ihr Freiheitsgrad ≥ 1 sein, und das ist gerade Bedingung (3): (4) 3(n'-1)-2k' ≥ 1 oder 3n' ≥ 2(k'+2) Um noch die erste Ungleichung, Bedingung (2), zu zeigen, wird diejenige Teilstruktur des entstehenden MTs betrachtet, die genau aus den Gliedern einer zu untersuchenden Untermenge der AG und allen Gliedern des ursprünglichen MTs besteht: (5) n' = n0+nE (6) k' = k0+kE+cE (an jedem Verbindungsglied entsteht ein neues Gelenk) Da die Teilstruktur nicht starr sein kann, gilt wieder: 3(n'-1)-2k' ≥ 1 (7) 3(n0+nE-1)-2(k0+kE+cE) ≥ 1 (wegen (5) und (6)) Für den ursprünglichen gilt MT die Zwanglaufbedingung: (8) 3(n0-1)-2k0 ≥ 1 (7)-(8) = (9) 3nE ≥ 2(kE+cE) Hier muss nur noch der Fall der Gleichheit ausgeschlossen werden. Angenommen, es gäbe echte Untermengen der AG mit 3n' = 2(k'+c'). Für die Kleinste von diesen würde gelten: 3n'' ≠ 2(k''+c'') für alle echten Untermengen, eben da sie die Kleinste ist 3n'' ≥ 2(k''+c'') für alle echten Untermengen, laut (9) also (10) 3n'' > 2(k''+c'') für alle echten Untermengen sowie (11) 3n' = 2(k'+c') (laut Annahme) (12) 3n''-2k'' ≥ 4 für alle echten Untermengen mit mindestens drei Gliedern, laut (4) Mit (10), (11) und (12) wäre diese Untermenge laut Hinrichtung des Satzes aber selbst eine AG. Der ursprüngliche MT ließe sich schrittweise erweitern: Zuerst um diese Untergruppe und anschließend um den Rest der AG. Das ist nach Definition der AGn aber nicht möglich. Die Annahme muss also falsch sein; die zweite Ungleichung ist vollständig.

Im Beweis der Hinrichtung ist zu sehen, dass die in der Definition geforderte Unteilbarkeit der Erweiterung um AGn, die später auch für die Eindeutigkeit der Zerlegung (Satz 6) benötigt wird, einzig und allein aus einem Teil von Bedingung (2) folgt; nämlich dem Gelten von 3n' ≠ 2(k'+c') für alle echten Untermengen. Gleichzeitig ist diese Ungleichheit aber auch unabdingbar für die Korrektheit, da sonst in Fall 2b beim untersuchten Freiheitsgrad die Gleichheit mit 0 eintreten könnte. Korrektheit der Erweiterung um und Eindeutigkeit der Zerlegung in AGn sind also untrennbar miteinander verbunden.

So ist es beispielsweise nicht möglich, unter Zulassen der Gleichheit in Bedingung (2) zwangläufige Erweiterungsgruppen zu definieren, die sich von den AGn nur dadurch unterscheiden, dass ein MT nicht eindeutig in sie zerlegt werden kann. Denn nicht jede Erweiterung um eine solche Gruppe wäre ein korrekter MT, wie folgendes Beispiel zeigt:

Beispiel 1: Die Gruppe enthält eine Unterstruktur, für die die Gleichheit in Bedingung (2) eintritt (nämlich die linken beiden Glieder), besitzt aber sonst alle numerischen Eigenschaften einer AG. Es existieren auch MTen, die sich um diese Gruppe auf einen anderen MT erweitern lassen, z.B. erweitert die Gruppe den Basistyp auf Allerdings erweitert sie ihn auch auf und das ist offensichtlich kein MT.

• Satz 4: Korrektheit der Erweiterung um Assurgruppen
  Jede Erweiterung eines Mechanismen-Typs um eine Assur-Gruppe ist wiederum ein Mechanismen-Typ.

Beweis siehe Beweis von Satz 3.

Nun gilt es noch, die mit den Assur-Gruppen angestrebte eindeutige Zerlegung von MTen nachzuweisen. Dazu muss zunächst ein anderer Zusammenhang gezeigt werden:

• Satz 5: Operationen auf Teilstrukturen
  Sind A und B Teilstrukturen eines Mechanismen-Typs C, die bezüglich Antrieb und Gestell von C jeweils selbst ein Mechanismen-Typ sind, dann sind auch
  (a) A∪B (Vereinigung) sowie
  (b) A∩B (Durchschnitt) MTen,
  wobei die Mengenoperationen auf die Glieder angewandt und alle Gelenke verwendet werden, die diese Glieder innerhalb von C verbinden.

Beweis (a): Die Bewegung eines Gliedes der durch die Vereinigung entstehenden Teilstruktur kann nicht unterbestimmt sein, da sie ja bereits durch einen Teil der Glieder (A bzw. B) ausreichend festgelegt ist. Andererseits kann die durch die entstehende Teilstruktur aber auch keine starre Teilkette enthalten, da eine solche auch innerhalb von C starr wäre.

Beweis (b): Da A ein korrekter MT ist, genügen die Glieder aus A, um eine zwangläufige Bewegung aller Glieder von A zu definieren, also auch der Glieder aus A∩B. Die restlichen Glieder von C dürfen die Bewegung dieser Glieder nun nicht weiter einschränken, d.h. die Zwangläufigkeit der Glieder von A∩B ist unabhängig von allen Gliedern, die in C\A enthalten sind. Analog ist sie natürlich ebenso unabhängig von allen Gliedern in C\B. Es genügen also die Glieder C\(C\A)\(C\B), um eine zwangläufige Bewegung aller Glieder aus A∩B zu gewährleisten - das sind aber gerade diese Glieder selbst.

Beispiel 2: C A B A∪B A∩B

• Satz 6: Eindeutigkeit der Zerlegung eines Mechanismen-Typs in Assur-Gruppen Ein Mechanismen-Typ kann nicht so auf verschiedene Weisen aus Assur-Gruppen zusammengesetzt werden, dass ein bestimmtes Glied dabei mit unterschiedlichen anderen Gliedern eine Assur-Gruppe bildet.

Beweis (indirekt): Angenommen, es existiert ein MT mit einem Glied X, das in mindestens zwei echt verschiedenen AGn auftritt. Diese beiden AGn seien A→A' und B→B'. Nach Satz 5 gilt nun: A∪(A'∩B) ist MT A∪(A'∩B') ist MT Die Ableitungskette A → A∪(A'∩B) → A∪(A'∩B') → A' darf nicht über andere MT als A und A' führen, da A→A' eine AG ist. Nur eine der drei Erweiterungen in der Kette kann demnach eine echte sein; die beiden anderen dürfen keine Glieder hinzufügen. Die echte Erweiterung ist aber immer die mittlere, denn dort wird das Glied X angefügt. Also gilt für die Mengen der Glieder: A'\A = (A∪(A'∩B')) \ (A∪(A'∩B)) = (A∪(A'∩B')) \ A \ (A'∩B) = (A'∩B') \ A \ B Analog lässt sich zeigen, dass B'\B = (A'∩B') \ A \ B, also A'\A = B'\B. Das sind aber gerade die Gliedermengen der beiden Assur-Gruppen, die laut Annahme verschieden sein sollen.

Diese Tatsache bedeutet aber nicht, dass ein MT nur in einer einzigen Reihenfolge aus den enthaltenen AGn zusammengesetzt werden kann. Dieser Umstand spielt beim Erkennen von eigentlichen Getrieben eine wichtige Rolle, denn Bewegungsabhängigkeit und damit auch Eigentlichkeit lassen sich gut mit Hilfe von AGn beschreiben.

2.1.2. Bewegungsabhängigkeit