Jürgen Ernst, Dipl.-Ing.(FH) HomepageKontaktInformationLinksNews
Hard- & Software-EntwicklungInformation: Software-Patente unter der Lupe [4.2]
 

Information: Software-Patente unter der Lupe [4.2]



4.2 Mathematische Beweisführung

Inhaltsverzeichnis

1 Teile und herrsche
2 Mathematische Grundlagen
3 Turing-Maschinen und -Kalkül
4 Beweise über Software
5 Analysen
5.1 Analyse von Aussage a)
5.2 Analyse von Aussage b)
5.3 Analyse von Aussage c)
5.4 Analyse von Aussage d)
6 Schlussfolgerung
7 Literatur

1 Teile und herrsche

Die Entstehung des Patentwesens fußte im 19. Jahrhundert (dt. Patentgesetz von 1877) zwangsläufig auf den damaligen wissenschaftlichen Möglichkeiten und Kenntnissen. Ein epistemologisches Paradigma war, dass man das Wissen über die Welt in voneinander unabhängige Kategorien einteilen kann, z.B. Mathematik, Physik, Chemie, Biologie, Soziologie, Astronomie etc. und in diesen Wissensgebieten sollte es immer weitere feinere unabhängige Unterteilungen geben. Diesen Ansatz nennt man Divide and Conquer ("Teile und herrsche").

Viel später musste man feststellen, dass dieser Ansatz nicht so funktionierte wie man es sich zuerst gedacht hatte. Mathematischer ausgedrückt war die Annahme von Kategorien, eine Gruppierung von Elementen in zueinander disjunkte Mengen (Baumstruktur) falsch. Die moderne Sichtweise geht heute von sich überlappenden Mengen (Netzwerkstruktur) aus. Das wissenschaftliche Weltbild hatte besonders durch die Quantentheorie (1925-1928) eine grundlegende Änderung erfahren, die in ihrem Kern eine nichtlokale Theorie darstellt, was besagt, dass alles mit allem verbunden ist. Dies führte auch zu interdisziplinären Ansätzen: Biochemie, Bioinformatik, Wirtschaftsinformatik, physikalische Chemie, angewandte Mathematik etc.

Trotz aller wissenschaftlichen Erkenntnisse der letzten 125 Jahre, basiert das Patentwesen heute immer noch implizit auf dem überholten kategorischen Ansatz:

a) Alle Ideen sind gegeneinander abgrenzbar und es gibt unendlich viele davon.
In der Abbildung rechts soll dies durch farbige Kreise symbolisiert sein. Freie Ideen sind "blau" dargestellt und patentierte "rot". Ideen, die auf anderen Ideen basieren bzw. andere Ideen enthalten, sollen abgeleitete Ideen heißen (siehe Punkt c).
b) Zu einer Idee gibt es eine Unzahl von Realisierungen dieser Idee. Realisierungen unterschiedlicher Ideen sind voneinander verschieden.
In der Abbildung rechts sollen die weissen Kreise unterhalb der Ideen für deren konkrete Realisierungen stehen. Die roten Kästen stehen jeweils für ein Patent. Es ist wie ein Zaun um ein Grundstück. Gemeinsam genutzter Boden gibt es nicht. Jedes Patent hat somit seinen eigenen Geltungsbereich.
c) Ein Patent deckt auch die Ableitung einer Idee bzw. die Ableitung der Realisierung einer Idee ab.
Eine Ebene unter den konkreten Realisierungen sind, mit Pfeilen erreichbar, davon abgeleitete Realisierungen gezeichnet. Wenn z.B. Idee 1 das "Rad" wäre, dann könnte x für einen Schubkarren stehen. Wenn z.B. Idee 2 eine "Bremse" wäre, dann könnte z für einen Seilzug mit Bremse stehen. Der Fall einer Patentverletzung stellt y dar, wenn z.B. y ein Fahrrad mit Bremse wäre. Der Patentinhaber argumentiert, dass derjenige, der y baut sich seiner Idee bedient habe. Man sieht, dass sich der Anspruchsbereich des Patents beliebig ausdehnt, wenn die patentierte Idee in der Ableitung mit enthalten ist.
d) Es gibt noch genug freie Ideen und Realisierungen von Ideen, sodass die Menge der patentierten Ideen nicht stark störend wirkt.

Formulieren wir nun die obigen Aussagen aus dem Patentwesen um, so dass sie auf den Bereich der Software passen. Hierzu setzen wir Idee mit Funktion (bzw. Abbildung) und die Realisierung einer Idee mit einem Programm (bzw. Algorithmus) gleich:

a) Alle Funktionen sind gegeneinander abgrenzbar und es gibt unendlich viele davon.

b) Zu einer Funktion gibt es eine Unzahl von Realisierungen (Programme). Programme unterschiedlicher Funktionen sind voneinander verschieden.

c) Ein Patent deckt auch die Ableitung einer Funktion bzw. die Ableitung des Programmes zu einer Funktion ab.

d) Es gibt noch genug freie Funktionen und Programme, sodass die Menge der patentierten Funktionen nicht stark störend wirkt.

Aufgrund unserer Alltagserfahrungen halten wir alle diese Aussagen intuitiv für richtig und es scheinen nähere Beweise, die die Richtigkeit eindeutig nachweisen, überflüssig zu sein. Wir möchten nun aber in diesem Text die entsprechenden Beweise nach und nach entwickeln. Es wird sich herausstellen, dass die obigen Aussagen widersprüchlich und unangemessen sind.


2 Mathematische Grundlagen

In der Mathematik leitet man Relationen aus der Mengenlehre ab. Kommt es auf die Reihenfolge zweier Elemente x1 , x2 an, so wird der Begriff des geordneten Paares oder 2-Tupel ( x1 , x2 ) verwendet. Eine mengentheoretische Definition des geordneten Paares wäre folgende:

Definition (1)

( x1 , x2 ) { x1 , x2 } wegen { x1 , x2 } = { x2 , x1 }
aber:
( x1 , x2 ) := { { x1 } , { x1 , x2 } }

Eine andere Möglichkeit zur Bildung von 2-Tupeln besteht darin Zahlen zur Strukturierung von Zahlen zu verwenden (Gödelisierung).

Mit geordneten Paaren kann man das karthesische Produkt definieren. Es dient einerseits der Konstruktion neuer mathematischer Gebilde, andererseits zur Definition des Relationsbegriffs.

Definition (2)

M1 ... Mn := { ( x1 , ... , xn ) | xi Mi } heißt karthesisches Produkt der Mengen M1 , ... , Mn.
Die Menge M1 M2 := { ( x1 , x2 ) | x1 M1 x2 M2 } heißt auch Paarmenge.

Definition (3)

Jede Teilmenge R M1 ... Mn heißt n-stellige Relation.

Relationen stellen meist keine eindeutigen Beziehungen zwischen Mengen her, d.h. einem Element können durchaus mehrere Elemente zugeordnet sein. Wenn es aber um Eindeutigkeit geht, benutzt man den Begriff der Abbildung bzw. Funktion.

Definition (4)

Eine linkstotale, rechtseindeutige Relation f M N heißt Abbildung (Funktion).

Anschaulich kann man sich eine Funktion als Menge von 2-Tupeln vorstellen, wobei ein Tupel jeweils eine eindeutige Zuordnung vermittelt. Mit den obigen Definitionen haben wir jetzt eine abstrakte Beschreibung der Objekte um die es in diesem Text gehen soll: Funktionen.


3 Turing-Maschinen und -Kalkül

In den Jahren 1936-1941 wurde von Alonzo Church [CHU36, CHU41] der -Kalkül zur Formalisierung des Funktionenbegriffs entwickelt. Er ist ein abstraktes Modell von Berechenbarkeit, basierend ausschließlich auf Funktionsdefinition und Funktionsanwendung. Später erkannte man, dass der -Kalkül ein effizientes Mittel zur Beschreibung von Programmiersprachen darstellt. 1960 diente er McCarthy als Basis zur Entwicklung der Programmiersprache LISP. Schon 1937 bewies Alan Turing in [TUR37], dass der -Kalkül und die Turing-Maschine alternative Beschreibungen ein und derselben Sache sind: unseres Verständnisses davon was berechenbar ist. Turing-Maschinen sind heutzutage allgegenwärtig, denn jeder existierende Computer bzw. PC ist eine Turing-Maschine.

Es folgt eine Definition, was unter einem Kalkül zu verstehen ist:

Definition (5)

  • Ein Alphabet ist eine Menge von Symbolen.
  • Die Menge aller möglichen Worte über dem Alphabet A soll durch A* beschrieben sein.
  • Eine Sprache K über einem Alphabet A ist dann eine Teilmenge aller möglichen Worte über dem Alphabet, somit: K A*.
  • Ein Kalkül ist eine Sprache mit einer Menge von Transformationsregeln, die auf der Menge der Worte der Sprache definiert sind.

Ausgehend von (5) wird die folgende Definition des -Kalküls verständlich:

Definition (6)

Es sei V eine abzählbare Menge von Variablen. Die Sprache L der -Terme ist über dem Alphabet V { ( , ) , } induktiv wie folgt definiert:

x V x L
M , N L ( M N ) L                   Applikation
x V M L ( x M ) L         Abstraktion

Eine genauere Erläuterung ersparen wir uns hier, da dies der interessierte Leser in der vielfältigen Literatur zum -Kalkül nachlesen kann. Die ausreichende Kenntnis des -Kalküls sei aber für die weitere Lektüre dieses Textes vorausgesetzt.

Anmerkung

Es sei hier noch auf einen Widerspruch des Patentrechts hingewiesen, wenn Software patentierbar wird. Im Patentrecht hat man mathematische Formeln ausdrücklich von der Patentierung ausgeschlossen. Wie wir aber gesehen haben ist Programmieren nichts anderes als Mathematik, wenn man den -Kalkül o.ä. verwendet und Programme sind mathematische Formeln. Dass dies auch in der Praxis funktioniert zeigen funktionale Programmiersprachen wie LISP, ML, Miranda, Haskell, Scheme, Clean etc.


4 Beweise über Software

Beweise über Eigenschaften von Programmen zu führen ist ein schwieriges Unterfangen, da es in der Informatik viele Problemstellungen gibt, von denen bewiesen ist, dass sie unlösbar sind.

Das bekannteste Problem ist sicher das Halteproblem. Beim Halteproblem geht es um die Frage, ob es ein Programm gibt, das für jedes Programm entscheiden kann ob dieses anhält bzw. terminiert. Diese Frage ist unlösbar. Ein solches Programm existiert nicht.

Es kommt aber noch schlimmer: Rice [RIC53] hat 1953 bewiesen, dass praktisch alle interessanten Aussagen über Programme im Allgemeinen nicht entscheidbar sind (siehe auch [RIC56] oder alternativ [HOP79]).

Satz von Rice

"Jede nicht triviale semantische Eigenschaft von Algorithmen ist nicht entscheidbar."

Eine Eigenschaft nennt man in diesem Zusammenhang trivial, wenn entweder jede oder keine berechnete Funktion sie besitzt. Somit sind beispielsweise nicht entscheidbar,

  • ob die berechnete Funktion total, überall undefiniert, injektiv, surjektiv oder bijektiv usw. ist,
  • ob zwei gegebene Algorithmen dieselbe Funktion berechnen,
  • ob ein gegebener Algorithmus korrekt zu einer gegebenen Funktion ist, d.h. es wird nie ein Programm zur allgemeinen Software-Verifikation geben.

Auf der einen Seite ist es schon entmutigend, wenn man den Satz von Rice liest, aber auf der anderen Seite kann man der Tatsache auch etwas positives abgewinnen. Wenn es nämlich gelingt einen Beweis zu führen, dann beweist man immer eine triviale Eigenschaft von Algorithmen, die uneingeschränkt für alle gilt. Natürlich schränkt der Satz von Rice die Möglichkeiten ein. Er gibt aber auch Hinweise wie man Beweise zu konstruieren hat bzw. wo man suchen sollte.


5 Analysen

5.1 Analyse von Aussage a)

a) Alle Funktionen sind gegeneinander abgrenzbar und es gibt unendlich viele davon.

Wir präzisieren die Aussage, indem wir nachweisen, dass es überabzählbar viele Funktionen gibt und dass nur abzählbar unendlich viele davon berechenbar sind.

Definition (7)

Eine Funktion heißt berechenbar, wenn eine abstrakte Maschine existiert, die die Funktion berechnet (ausführt).

Wenn wir prüfen wollen, ob es Funktionen gibt, die sich nicht durch Algorithmen berechnen lassen, dann hilft uns folgende allgemeine Eigenschaft von Algorithmen:

Jeder Algorithmus läßt sich durch einen endlichen Text über einem festen, endlichen Alphabet beschreiben.

Sei A ein Alphabet A = { a1 , ... , an } dem eine alphabetische Ordnung a1 < a2 < ... < an zugrunde liegt, dann ist bekanntlich A* die Menge aller Texte bzw. Wörter über A:

A* = { , a1 , ... , an , a1a1 , a1a2 , ... , a4a1a6a2a1 , ... }

Das Zeichen soll hierbei für das Wort mit der Länge 0 stehen.
Nun kann die Menge A* zunächst der Länge nach aufgelistet werden, d.h. zu jeder Länge m gibt es nm verschiedene Wörter über A (also endlich viele); dann sortiert man noch innerhalb der Wörter gleicher Länge lexikographisch, also bei b1b2 ... bm < c1c2 ... cm gilt b1 < c1 (b1 = c1 b2 < c2) ... (b1 = c1 ... bm-1 = cm-1 bm < cm). Damit haben wir eine Ordnung auf A* eindeutig bestimmt und es folgt daraus: A* ist abzählbar.

Da es nicht mehr berechenbare Funktionen als berechnende Algorithmen gibt und nicht mehr Algorithmen als die sie beschreibenden Texte geben kann, gilt offenbar: Die Menge der berechenbaren Funktionen ist abzählbar.

Funktionen gibt es aber weit mehr. Betrachten wir hierzu die auf der Menge der natürlichen Zahlen definierten Funktionen f, die als Ergebnisse nur die Werte 0 oder 1 liefern; jede davon definiert eine Teilmenge Mf derjenigen Zahlen m , für die f(m) = 1 ist. Umgekehrt gibt es für jede Teilmenge M eine solche Funktion fM, die charakteristische Funktion der Menge M. Die Menge der Teilmengen M ist aber überabzählbar, ebenso also die Menge ihrer charakteristischen Funktionen; und damit die Menge aller Funktionen erst recht.

Die Folgerung daraus ist, daß es nicht berechenbare Funktionen geben muss.

Anhand dieser Ergebnisse kann man zwar sagen, dass es mehr Funktionen gibt, als man berechnen kann, aber die Aussage unter a) ist dennoch wahr.

5.2 Analyse von Aussage b)

b) Zu einer Funktion gibt es eine Unzahl von Realisierungen (Programme). Programme unterschiedlicher Funktionen sind voneinander verschieden.

Wir wissen, dass Funktionen durch Programme berechnet werden können. Wenn es um eine konkrete Funktion f geht, dann kann man sie als Abbildung f: A B schreiben, d.h. f bildet die Menge der Eingabewerte A auf die Menge der Ausgabewerte B ab.

Funktionen können wie anfangs gezeigt als Menge von 2-Tupeln aufgefasst werden. Die einfachsten Funktionen, die man sich vorstellen kann wären jene, die nur ein 2-Tupel enthalten. Kompliziertere Funktionen lassen sich aufbauen, indem einfach weitere 2-Tupel hinzu genommen werden. Um nicht alle Tupel explizit aufzählen zu müssen, gibt es auch zahllose Möglichkeiten die Tupel-Belegung zu berechnen.

Beispiele

f(x) = { 1234 für x=1
g(x) = { 1234 für x=1 und 48 für x=2 und 543 für x=3
h(x) = { 1234 für x=1 und 0 sonst
k(x) = x2 - 2x + 1

Betrachten wir nun drei spezielle Funktionen f1, f2 und f3:

f1(x) = { 0 für x=0 und 1 für x=1
f2(x) = x
f3(x) = x2

f1 besteht aus zwei 2-Tupeln, d.h. der Definitionsbereich und der Wertebereich sind nur für 2 Werte definiert. Im Gegensatz dazu seien f2 und f3 über ganz definiert. Wenn wir nun festlegen, dass für unsere Rechnungen bei allen drei Funktionen nur zwei Punkte (0 und 1) im Definitionsbereich verwendet werden sollen, sehen wir, dass alle drei Berechnungen dieselben Werte liefern.

Hinweis: Beim Programmieren benutzt man Typendeklarationen zur Eingrenzung des Definitions- und Wertebereichs.

Man kann daher sagen, dass x und x2 ebenfalls gleichwertige Algorithmen zur Berechnung von f1 darstellen und man kann sagen, dass f2 und f3 Ableitungen von f1 sind, da sie f1 komplett beinhalten. Umgekehrt gilt dies nicht.

Diese Eigenschaft von Funktionen ist kein Zufall. Es liegt daran, dass Relationen als Teilmenge definiert wurden. Siehe Definition (3).

Bei der Programmierung eines Computers ist man noch stärker eingeschränkt. So lässt sich z.B. f3(x) = x2 gar nicht wirklich berechnen. Wegen begrenztem Speicher und Rechengeschwindigkeit können Programme meist nur Näherungen von Funktionen ausrechnen, d.h. man berechnet nur eine Teilmenge der eigentlichen Funktion. Ein eingeschränkter Definitions- oder Wertebereich stellt aber strenggenommen eine andere Funktion dar.

Damit haben wir gezeigt, dass ein Programm durchaus für mehrere Funktionen die korrekte Abbildung berechnen kann, ja dies sogar zwingend tun muss, sonst könnten Programme überhaupt keine Ergebnisse liefern.

Dies steht im Gegensatz zur Aussage b), dass Programme nur einer Funktion zugerechnet werden können, was ja Voraussetzung im kategorischen Ansatz war.
Aussage b) ist somit falsch.

Anmerkung

Man vergleiche Mehrdeutigkeit und Resourcenbeschränkungen bei der Funktionsberechnung durch Programme mit der Folgerung, aus dem Satz von Rice, nach der es nicht entscheidbar ist, ob zwei gegebene Algorithmen dieselbe Funktion berechnen.

5.3 Analyse von Aussage c)

c) Ein Patent deckt auch die Ableitung einer Funktion bzw. die Ableitung des Programmes zu einer Funktion ab.

Nach Aussage c) verletzen alle Funktionen eine patentierte Funktion, wenn sie eine Ableitung davon darstellen. Im vorigen Abschnitt hatten wir schon eine Art von Ableitung kennengelernt, die darauf basiert, dass eine abgeleitete Funktion genau die 2-Tupel der patentierten Funktion enthält.

Es gibt aber auch Funktionen, die nach außen keine oder nur sehr wenige gemeinsame Tupel besitzen, aber dennoch ist die eine Funktion komplett in der anderen enthalten, um eine Berechnung zu realisieren. Somit liegt auch eine Ableitung vor.

Wir wollen nun das Enthaltensein einer Funktion in einer anderen Funktion genauer untersuchen.

Zur Veranschaulichung betrachten wir Darstellungen von Relationen als Matrizen. Es sei immer eine Funktion f: A B gemeint und es gelte: a0 , a1 , ... , aN A und b0 , b1 , ... , bM B. Weiterhin bezeichnen N und M die Mächtigkeit der Mengen, also N = card(A) und M = card(B).

Wie man sieht, gibt es nur drei Fälle. Da wir uns auf Funktionen beschränken wollen, also rechtseindeutige Relationen, entfällt Fall 3) und sei hier nur der Vollständigkeit halber gezeigt. Jedes Kreuz steht für ein Tupel. Als Charakteristik können wir die Anzahl der Kreuze pro Zeile bzw. pro Spalte bestimmen.

Fall 1)   Fall 2)   Fall 3)
Zeilensumme  1 1 2,...,M
Spaltensumme  2,...,N 1 1

Da die Matrizen nur wirklich vorhandene Tupel darstellen (in der Abbildung bitte über die Ungenauigkeit im variablen "..." Bereich hinwegsehen) muss jede Zeile oder Spalte immer mit mindestens einem Kreuz belegt sein.

Im Fall 2), d.h. N = M, sind alle Summen gleich 1. Es wird also jeder Eingangswert auf einen anderen Ausgangswert abgebildet. Wir können sagen, dass die Abbildung in diesem Fall eineindeutig ist, also bi = f ai und ai = f-1 bi.

Im Fall 1), d.h. N > M, gibt es Spaltensummen, die größer als 1 sind. Es werden so mehrere Eingangswerte auf denselben Ausgangswert abgebildet. Es gilt nur noch bi = f ai. Die Umkehrfunktion gilt nicht, da sie mehrere Werte liefern müsste, was wir ja ausgeschlossen haben. Dennoch können wir auch hier die eineindeutige Abbildung finden.

Satz (1)

Jede Funktion f: A B besitzt eine innere eineindeutige Kernfunktion KQ mit Q = card(B).

Beweis (1)

Wegen des Aufbaus der 2-Tupel erzwingt eine Anzahl von M = card(B) Ausgabewerten auch M Eingabewerte. Da Funktionen rechtseindeutig sind, müssen die Eingabewerte alle verschieden sein. Diese 2-Tupel bilden die Funktion KQ (bzw. die quadratische Matrix KQ) mit Q = M = card(B). Q ist die Anzahl der Zeilen bzw. Spalten dieser Matrix. Falls die Anzahl N = card(A) der Eingabewerte größer als Q ist, müssen N-Q Eingabewerte redundant sein und auf Werte abbilden, die schon von KQ erreicht wurden. Für N = Q = M gilt: f = KQ.qed

Da KQ immer existiert, können wir nun jede Funktion basierend auf ihrer charakteristischen Kernfunktion KQ darstellen.

Satz (2)

Jede Funktion f kann als Kombination einer Mappingfunktion qa und der Kernfunktion KQ ausgedrückt werden.

Beweis (2)

Aus Satz (1) wissen wir, dass jede Funktion f: A B eine Kernfunktion KQ mit Q = card(B) enthält. Wir bestimmen zwei neue Mengen Aq und Bq für die Abbildung KQ: Aq Bq. Es gelte: Bq = B und Aq A. Wir schließen die Lücke zwischen A und Aq mit einer Mappingfunktion qa: A Aq.

Die Funktion f lässt sich dann im -Kalkül schreiben als f = x . KQ ( qa x ).

Im Fall card(A) = Q müssen wir nur qa = I (Identität) setzen.
Prüfung: f = x . KQ ( qa x ) = x . KQ ( I x ) = x . KQ x = KQ.

Im Fall card(A) > Q müssen wir qa so wählen, dass jene Q Elemente aus A, die KQ bilden, direkt auf Aq gemappt werden. Die redundanten Eingangswerte bleiben übrig und werden so auf Aq gemappt, dass sich nach Durchlauf durch KQ der gleiche Ergebniswert ergibt als hätte man direkt in B abgebildet. Man mappt quasi die redundanten Eingangswerte auf einen Repräsentanten in Aq. Dieses Mapping ist immer ohne Probleme möglich.qed

In Beweis (2) haben wir Bq = B festgelegt. Dies hätten wir auch anders machen können. Indem wir eine weitere Mappingfunktionen qb: Bq B einführen und qb = I setzen, erhalten wir dasselbe Ergebnis. Wir können dies wieder verallgemeinern und damit dann die Kernfunktion KQ: Aq Bq durch die Identitätsfunktion IQ: {1,2,...,Q} {1,2,...,Q} ersetzen. Die Aufgabe von IQ ist es einfach gesagt, das Intervall 1,2,...,Q der natürlichen Zahlen auf sich selbst abzubilden. Je nach Wert von Q ergibt sich eine andere Identitätsfunktion I1 , I2 , I3 , ...

Satz (3)

Jede Funktion f kann als Kombination von zwei Mappingfunktionen qa und qb und einer für f charakteristischen Identitätsfunktion IQ ausgedrückt werden.

Beweis (3)

Im Beweis (2) haben wir eine Funktion f als f = x . KQ ( qa x ) geschrieben. Nun wandeln wir diesen Ausdruck leicht ab in f = x . q'b ( KQ ( q'a x ) ) und denken uns q'b = I und q'a = qa. Wir sehen, dass sich dadurch die Aussage nicht ändert.
Da KQ eine eineindeutige Abbildung vermittelt, ist KQ: Aq Bq isomorph zu IQ: {1,2,...,Q} {1,2,...,Q}. Es sei IQ die Identitätsmatrix der Größe Q. Wir nutzen für die isomorphe Abbildung wiederum zwei Mappingfunktionen ma: Aq {1,2,...,Q} und mb: {1,2,...,Q} Bq. Damit schreiben wir den Ausdruck für f nun als f = x . q'b ( mb ( IQ ( ma ( q'a x ) ) ) ). Es macht keinen großen Sinn zwei Mappingfunktionen hintereinanderzuschalten, wenn eine Mappingfunktion dieselbe Abbildung leisten kann. Wir definieren qb = x .( q'b ( mb x ) ) und qa = x .( ma ( q'a x ) ) und haben damit dann f = x . qb ( IQ ( qa x ) ).qed

In Beweis (3) konnten wir nachweisen, dass in jede Funktion f eine Identitätsfunktion IQ mit Q = card(B) einbettbar ist. Die Identitätsfunktion bzw. die Zahl Q ist dabei ein wichtiges Klassifikationsmerkmal. Man kann die Beziehungen, die f = x . qb ( IQ ( qa x ) ) ausdrückt auch grafisch darstellen.

Man erkennt sehr schön in der Grafik, dass es zwei Wege gibt, wie man A auf B abbilden kann.

Nun sind wir an einem Punkt wo wir unsere Überlegungen auf die Zusammenhänge zwischen zwei beliebigen Funktionen f1 und f2 ausdehnen können.
Es seien dabei folgende Abbildungen gemeint:
      f1: A1 B1 und f2: A2 B2.
Die Kardinalitäten erfassen wir mit:
      N1 = card(A1), N2 = card(A2), M1 = card(B1) und M2 = card(B2).
Es gelten die Bedingungen:
      N1 >= M1 und N2 >= M2.
Die Identitätsfunktionen seien:
      IQ1 mit Q1 = M1 und IQ2 mit Q2 = M2.

Wir bilden jetzt Äquivalenzklassen über die Differenzen N1-N2 und M1-M2. Damit können wir Funktionen miteinander vergleichen. Die Idee, die dahinter steckt ist folgende: Es ist unwichtig wie groß die Matrizen sind. Wichtig ist nur um wieviele Zeilen oder Spalten sie sich voneinander unterscheiden.

Beispiele

N1 M1 N2 M2 N1-N2 M1-M2
5 4 5 4 0 0
12 12 12 12 0 0
6 4 3 3 3 1
8 6 5 5 3 1
12 12 10 8 2 4

Die Differenzen N1-N2 und M1-M2 lassen sich in ein 2-dimensionales Koordinatensystem eintragen. Damit werden die Beziehungen wesentlich anschaulicher. Da wir immer die Mächtigkeiten von f2 abziehen ist f2 unser Bezugssystem. Der Koordinatenursprung drückt somit die Identität zu f2 aus, d.h. alle Funktionen, die gleich große Matrizen zu f2 haben kommen im Punkt (0;0) zu liegen.

Wenn f2 eine patentierte Funktion ist, können wir sagen, dass jede Funktion f1, wenn sie auf (0;0) abgebildet wird, eine Patentverletzung von f2 darstellt.

Beweis (4)

N1-N2=0 und M1-M2=0 bedeutet gleich große Matrizen. Die Identitätsmatrizen haben die gleiche Größe wegen Q1=M1=M2=Q2. Es gibt auch gleich viele redundante Eingangswerte wegen N1-M1=N2-M2. Umgeformt: N1-N2=M1-M2, also 0=0. Damit existiert ein eineindeutiges Mapping zwischen den beiden Funktionen. f1 x kann als qb ( f2 ( qa x ) ) dargestellt werden.qed

Wir zeigen nun, dass alle Funktionen f1 mit M1-M2=0 und N1-N2>0 eine Patentverletzung von f2 darstellen.

Beweis (5)

M1-M2=0 bedeutet gleich große Identitätsmatrizen wegen Q1=M1=M2=Q2. Da N1-N2>0 sein soll, bedeutet dies, dass f1 mehr redundante Eingangswerte als f2 hat. Redundante Eingangswerte lassen sich aber immer durch eine Mappingfunktion auf einen Repräsentanten reduzieren, siehe Beweis (2). Sei f'1 x' = qb ( f2 ( q'a x' ) ) eine Funktion wie unter Beweis (4) welche in (0;0) zu liegen kommt. Mit einer Mappingfunktion ma bilden wir die redundanten Werte x auf ihre Repräsentanten in x' ab. Also: x' = ma x und somit f1 x = qb ( f2 ( q'a ( ma x ) ) ). Da man zwei Mappingfunktionen zu einer vereinigen kann, können wir mit qa x = q'a ( ma x ) auch wieder f1 x = qb ( f2 ( qa x ) ) schreiben.qed

Wenden wir den Beweis (5) umgekehrt an, können wir sagen, dass wir von f2 aus durch Hinzufügen von redundanten Eingangswerten jede Funktion auf der Achse N1-N2>=0 erreichen können. Aus der Sicht der Matrizen bedeutet dies ein Hinzufügen von Zeilen.

Wir können aber auch Spalten hinzufügen und es ergibt sich eine neue Achse. Auch hier zeigen wir, dass alle Funktionen f1, die auf dieser Achse liegen eine Patentverletzung von f2 darstellen.

Beweis (6)

Wir beweisen konstruktiv, indem wir von f2 ausgehen. Beim Hinzufügen von Spalten müssen wir beachten, dass wir das nicht unabhängig von den Zeilen tun können. Da wir nur Funktionen zugelassen haben, erzwingt jede neue Spalte auch eine neue Zeile. Wäre dies nicht so, gäbe es mehrere Ausgangswerte und das ist dann keine Funktion mehr. Wir wandern somit auf einer 45°-Achse. Damit ist eigentlich schon alles bewiesen. Da wir von f2 ausgingen ist f2 auch nach dem Hinzufügen weiterhin in der neuen Matrix als Untermatrix enthalten. Da f2 nicht alle Werte von f1 berechnen kann, können wir dies mit einer anderen Funktion f3 und einer Fallunterscheidung tun. f1 x kann z.B. einfach als qb ( ( if ( zusatz x ) f3 f2 ) ( qa x ) ) dargestellt werden, mit if = p x y . p x y und zusatz als Funktion, die true = x y . x dann liefert, wenn x ein neuer hinzugefügter Wert ist und sonst false = x y . y. Dies wählt dann entweder die Funktion f3 oder f2 zur weiteren Berechnung aus.qed

Da eine 45°-Achse für die weitere Fallunterscheidung nicht sehr anschaulich ist, ändern wir unser Koordinatensystem ein wenig ab. Wir können eine Koordinatentransformation machen, indem wir einfach N1-N2 subtrahieren, d.h. unsere waagerechte Achse sei nun (M1-M2)-(N1-N2). Damit sind Änderungen an den Matrizen bzgl. Spalten- oder Zeilenzahl ein Wandern parallel zu den Achsen.

Die Ergebnisse von Beweis (5) und (6) lassen sich kombinieren. Eine beliebige Funktion f1 ist erreichbar, wenn man von (0;0) ausgeht und auf der waagerechten Achse solange nach rechts läuft bis man denselben Koordinatenwert erreicht hat. Dann läuft man auf der vertikalen Achse nach oben bis man auch hier denselben Koordinatenwert erreicht hat. Damit kann nun der ganze erste Quadrant erreicht werden.

Wir leiten nun die Patentverletzung für den zweiten Quadranten ab. Dies ist etwas schwieriger, da f1 weniger Tupel als f2 besitzt. Da man aber davon ausgehen darf, dass innerhalb von f1 eine Berechnung über mehr Tupel gemacht werden kann und nur nach aussen weniger sichtbar sind bzw. genutzt werden, dann ist das folgende sofort einsichtig.

Beweis (7)

Eine Funktion f1, die im zweiten Quadranten zu liegen kommt, hat weniger Tupel als die einzubettende Funktion f2. Wir erzeugen nun eine Funktion f3, die wir aus f1 gewinnen, in dem wir weitere Tupel hinzufügen. Dies bedeutet eine waagerechte Verschiebung nach rechts, was wir solange tun, bis wir auf die vertikale Achse N1-N2 treffen. Diese Position ist bestimmt durch (M1-M2)-(N1-N2)=0 bzw. (M1-M2)=(N1-N2). Aus Beweis (5) wissen wir, dass eine Funktion, die auf dieser Achse liegt eine Patentverletzung von f2 darstellt. Diese Funktion hat auch genug Tupel, um f2 total zu überdecken. Wir betten f3 nun in f1 ein. Dies ist kein Kunstgriff, wie wir in der Analyse von Aussage b) gesehen haben, sondern aktuelle Praxis. Dort hatten wir eine Funktion mit nur 2 Tupeln mit Funktionen beschrieben, die über ganz definiert waren. Aufgrund von Beweis (6) muss man alle Funktionen, die durch Rechtsverschieben erzeugt wurden als Ableitung ansehen. Die Funktion f3 ist somit Ableitung sowohl von f1 als auch von f2. Es kann deshalb von beiden Seiten eine Patentverletzung angemahnt werden.qed

Damit haben wir eine Überdeckung der ersten beiden Quadranten nachgewiesen. Die Patentverletzung haben wir für f1 in Bezug auf f2 gezeigt.

Man kann aber auch den Bezugspunkt wechseln und die Patentverletzung für f2 in Bezug auf f1 betrachten. Tun wir dies, dann ändert sich die Beschriftung der Achsen, da nun N2-N1 und (M2-M1)-(N2-N1) berechnet werden. Formt man diese Terme um in -(N1-N2) und -(M1-M2)+(N1-N2), also -((M1-M2)-(N1-N2)), sieht man, dass nur ein Vorzeichenwechsel stattfindet.

Wenn man für einen beliebigen Punkt in diesem Koordinatensystem das Vorzeichen beider Achsen wechselt, so ist das gleichbedeutend mit einer Hintereinanderausführung von Spiegelungen an beiden Achsen bzw. einer Punktspiegelung am Koordinatenursprung. Die obere Halbebene klappt dadurch komplett auf die untere Halbebene um. Es kann so die gesamte Fläche überdeckt werden.

Wir müssen folgern, dass der Anspruchsbereich von Aussage c) vollkommen überzogen ist. Durch die Wandelbarkeit von Funktionen kann fast jede beliebige Patentverletzung erzielt werden. Aussage c) muss in Bezug auf Software als ungültig erklärt werden.

5.4 Analyse von Aussage d)

d) Es gibt noch genug freie Funktionen und Programme, sodass die Menge der patentierten Funktionen nicht stark störend wirkt.

Nach dem Ergebnis von Aussage c) kann Aussage d) nicht mehr aufrechterhalten werden. Softwarepatente stellen eine starke Störung dar und es gibt keine Ausweichmöglichkeiten.

Aussage d) ist somit falsch.


6 Schlussfolgerung

Wir konnten zeigen, dass zwischen zwei Funktionen immer eine Patentverletzungs-Situation herrscht. Wenn man dies auf mehr als zwei Funktionen ausdehnt, kann man sagen, dass hierbei immer die trivialste Funktion gewinnt, da sie stets als in den komplexeren Funktionen enthalten angegeben werden kann, während dies umgekehrt nicht immer gilt. Dies zeigt nun aber ganz konkret wie gefährlich Trivialpatente sind.

Da wir nachgewiesen haben, dass eine Patentverletzung immer vorliegt, ist die Bedrohung durch Softwarepatente nicht mehr hypothetisch. Jeder, der sich Programmierer oder Informatiker nennt, kann hiernach nicht mehr ruhigen Gewissens dem Spiel der Patentlobby zusehen.

Auch, wer glaubt, dass ihm eigene Patente einen Vorteil verschaffen, muss nun einsehen, dass dies im Bereich der Software nicht möglich ist. Praktisch jedes Softwareprojekt ist ständig der Gefahr einer Patentverletzung ausgesetzt. Es ist nur eine Frage von Zeit und Geld, die man investieren möchte, um eine Patentverletzung zu konstruieren.