Kurs:Syllogismen

Gegenstand

Der Kurs behandelt Syllogismen, also Schlussregeln in der Aussagenlogik, welche immer nach dem gleichen Muster aufgebaut sind. Jeweils zwei Prämissen, auch Obersatz und Untersatz genannt, führen zu einer Konklusion.

Der Wikipediaartikel über Syllogismen behandelt die Schlussregeln unter Hervorhebung des philosophischen Charakters: Wesentliche Passagen des dortigen Artikels implizieren nicht leere Mengen und führen so auch zu den schwachen Syllogismen. Diese sind Gegenstand der Philosophie und nicht der axiomatischen Aussagenlogik.

Strukturen der Syllogismen

Syllogismen erlauben Aussagen über Elemente aus Mengen. Die einzelnen Elemente besitzen Eigenschaften, die sie der entsprechenden Menge zugehörig machen. So kann z.B. die Menge aller Autos mit weniger als vier Rädern durchaus als RadAb bezeichnet werden. Auf die Menge aller Fahrzeuge trifft diese Bezeichnung jedoch nur unter größten Vorbehalten zu. Ein Syllogismus verknüpft nun drei Mengen miteinander und gewinnt durch diesen Vorgang eine neue Aussage über die Beziehungen zwischen zwei beteiligter Mengen. Das klassische Beispiel:

Alle Menschen sind sterblich.

Alle Griechen sind Menschen.

Folglich sind alle Griechen sterblich.

In diesem Beispiel wurden die Beziehungen zu der Menge aller Menschen entfernt und durch die Beziehung der Menge aller Griechen und die aller Sterblichen ersetzt. Damit ist auch bereits alles Wesentliche über die Aufgaben von Syllogismen gesagt - es sind Schlussregeln.

Grundlagen der Syllogismen

Allgemein verbinden Syllogismen zwei Aussagen zu einer neuen. Diese Verbindung unterliegt natürlich gewissen Regeln, auf die nun etwas genauer eingegangen wird. Die beiden Aussage werden als Prämissen bezeichnet, die sich ergebende neue Aussage als Konklusion. Damit ist die Aufgabe der Syllogismen bereits über die Namensgebung der beteiligten Elemente deutlich; es handelt sich um eine Schlussregel.

Nun ist es eine Besonderheit der Syllogismen, ausschließlich mit der Bildung von Teilmengen zu arbeiten. Der Mittelbegriff M wird entfernt und eine neue Aussage wird erzeugt. Die beiden ursprünglichen Aussagen sind prädikativ und werden Prämissen genannt, die Schlussaussage ist natürlich ebenfalls prädikativ und wird Konklusion genannt. Der Mittelbegriff tritt in beiden Prämissen als Subjekt oder als Prädikat auf. In der Konklusion fehlt er. Die Konklusion enthält also nur die nicht gemeinsamen Satzteile als Subjekt bzw. Prädikat.

Die Prämissen und die Konklusion basieren auf vier elementaren Aussageformen, die einfach Formen genannt werden. Es sind:

Form	sprachliche Aussage
SaP	alle S sind P
SiP	einige S sind P
SeP	kein S ist P
SoP	einige S sind nicht P

Insgesamt existieren vier Möglichkeiten die Satzteile zweier Prämissen anzuordnen. Dabei werden Subjekt S und Prädikat P mit einem Mittelbegriff so verknüpft, dass der Mittelbegriff für den Schlusssatz (Konklusion) überflüssig wird. Diese verschiedenen Anordnungen werden gemeinhin als Figuren bezeichnet und sind in folgender Tabelle aufgelistet.

Dabei stehen x, y, und z für die jeweilige Relation oder Form. Weil alle hier verwendeten Formen auf die Bestimmung von Teilmengen hinauslaufen, bleiben als Variationsmöglichkeiten nur Positionen der Mengen. Es ergeben sich vier Kombinationen, die als Figuren bezeichnet werden.

	Figur-1	Figur-2	Figur-3	Figur-4
Prämisse-1	M x P	P x M	M x P	P x M
Prämisse-2	S y M	S y M	M y S	M y S
Konklusion	S z P	S z P	S z P	S z P

Die Zeichen x, y und z stellen eine der Formen a, i, e oder o dar, womit sich für eine Figur insgesamt $4\cdot 4\cdot 4=64$ Möglichkeiten ergeben. Die Möglichkeiten aller Figuren belaufen sich demnach also auf insgesamt $64\cdot 4=256$. Es existieren tatsächlich 256 Syllogismen, allerdings lassen nur 19 logisch einwandfreie Aussagen zu und bilden die Modi der klassischen Logik. Diese 19 Syllogismen erhielten Namen, um darin die Regeln zu codieren.

Die Altvorderen ersannen einen Satz, der eben diese Namen enthält und gleichzeitig den entsprechenden Figuren zuordnet. Die betonten Vokale der Namen geben die Folge der Formen (a, i, e, o) an.

Barbara, Celarent, Darii, Ferioque, prioris

Cesare, Camestres, Festino, Baroco, secundae

tertia Darapti, Disamis, Datisi, Felapton, Bocardo, Ferison habet

quarta insuper addit Bamalip, Calemes, Dimatis, Fesapo, Fresison

Übersetzt bedeutet es:

Barbara, Celarent, Darii, Ferio, sind der Ersten (Figur zugehörig)

Cesare, Camestres, Festino, Baroco, gehören zur Zweiten (Figur)

die Dritte (Figur) hat Darapti, Disamis, Datisi, Felapton, Bocardo, Ferison

die Vierte (Figur) fügt außerdem hinzu(:) Bamalip, Calemes, Dimatis, Fesapo, Fresison

Das Beispiel der sterblichen Griechen ist also die Anwendung des Modus barbara auf die Mengen Menschen, Sterbliche (Menschen) und (menschliche) Griechen gewesen.

Es sollte noch kurz auf die Namensgebung der Formen selbst eingegangen werden. Sie haben ihre Wurzeln ebenfalls im Lateinischen und sind einfach die Vokale der Worte: affirmo, nego. Mit den Bedeutungen affirmo für bejaend und nego für verneinend. So ist eine o-Aussage die Verneinung einer a-Aussage und eine i-Aussage die Verneinung einer e-Aussage.

Aussage	Original	Verneinung
alle S sind P	SaP	SoP
kein S ist P	SeP	SiP
einige S sind P	SiP	SeP
einige S sind nicht P	SoP	SaP

Die Modi werden jetzt in tabellarischer Darstellung noch den Figuren zugeordnet, womit ein erster Überblick erreicht ist.

Figur	Namen der Modi	bereinigte Modi
1	Barbara, Celarent, Darii, Ferio	aaa, eae, aii, eio
2	Cesare, Camestres, Festino, Baroco	eae, aee, eio, aoo
3	Darapti, Disamis, Datisi, Felapton, Bocardo, Ferison	aai, iai, aii, eao, oao, eio,
4	Bamalip, Calemes, Dimatis, Fesapo, Fresison	aai, aee, iai, eao, eio

Von entscheidender Wichtigkeit hinsichtlich der Übertragbarkeit vorhandener Systeme auf Syllogismen ist die Zuordnung bestimmter Tripels zu den Figuren. Eine Figur ordnet praktisch die ersten beiden Formen (die Prämissen) so um einen Mittelbegriff, dass eine korrekte Konklusion allein aus Subjekt und Prädikat herauskommt.

Figur1	Figur2	Figur3	Figur4
aaa
	aoo
		oao
eae	eae
aii		aii
	aee		aee
		aai	aai
		eao	eao
		iai	iai
eio	eio	eio	eio

Mengen und Syllogismen

Sämtliche Aussagen, seien es Prämissen oder Konklusionen, in Syllogismen beziehen sich auf Elemente von Mengen. Immer wenn Mengen miteinander in Beziehung gebracht weden, sind Mengenrelationen beteiligt. Es sich prinzipiell um die Klärung der Frage, ob Elemente der einen Menge auch einer anderen zugehörig sind. Derartige Fragen werden über die Bildung von Teilmengen geklärt. Das Beispiel kann nun von der natürlichen Sprache in die Mathematik überführt werden. Wieder wird das Beispiel der sterblichen Menschen aus Griechenland herangezogen.

• Prämisse-1: Alle Menschen sind sterblich.
• Prämisse-2: Alle Griechen sind Menschen.
• Konklusion: Alle Griechen sind sterblich.

Mit den Abstraktionen

M = Menge aller Menschen.

S = Menge all Dessen was sterblich ist.

G = Menge aller Griechen mit der Eigenschaft Menschen zu sein.

Können die beiden Prämissen auch als

• Prämisse-1 legt fest, dass M eine Teilmenge von S ist.
• Prämisse-2 legt fest, dass G eine Teilmenge von M ist.

formuliert werden. Und es kann gleich in einer etwas mathematischeren Schreibeise weiter abstrahiert werden zu:

aus   $M\subseteq S$

und   $G\ \subseteq M$

folgt $G\;\subseteq S$

Die Konklusion wird hier über die Konjunktion der beiden Prämissen gewonnen. Sie liefern jedoch nur einfache Wahreitswerte im Sinne von "stimmt / stimmt nicht", "ja / nein" oder "wahr / falsch". Bis jetzt kann nur mit den Mitteln der Aussagelogik die Konklusion ermittelt werden. Damit wird aus dem Modus Barbara:

$\left(\left(M\subseteq S\right)\land \left(G\subseteq M\right)\right)\Rightarrow \left(G\subseteq S\right)$

Ob diese Formulierung korrekt ist, kann nur über einen Beweis erfolgen. Um diesen Beweis zu führen, nuss noch viel über die Syllogismen in Erfahrung gebracht werden. Die folgenden Punkte werden den erforderlichen Erfahrungsschatz liefern.

Vorbereitung auf die erforderlichen Algebren

Als Erstes werden die Formen und die entsprechenden Mengenrelationen einander gegenübergestellt. Die folgende Tabelle zeigt die drei Bedeutungen:

Form	sprachliches Äquivalent	Mengenrelation
SaP	alle S sind P	$S\subseteq P$
SiP	einige S sind P	$\neg \left(S\subseteq \neg P\right)$
SeP	kein S ist P	$S\subseteq \neg P$
SoP	einige S sind nicht P	$\neg \left(S\subseteq P\right)$

Auffällig sind Formulierungen wie alle, einige oder kein. Die Aussagen betreffen entweder die Mengen als Gesamtheit oder die Elemente als Partikel.

a ist allgemein bejahend

e ist allgemein verneinend

i ist partikulär bejahend

o ist partikulär verneinend

Bei den Formen wird kein Wert im Sinne einer Zahl oder Anzahl benötigt. Es werden nur Feststellungen über alle oder zumindest einige Elemente getroffen. Derartige Aussagen haben in der Mathematik die Bezeichnung Quantoren.

$\forall$ ist ein Quantor der alle Elemente meint.

$\exists$ ist ein Quantor der einige Elemente meint.

Wenn nur einige Elemente gemeint sind, dann ist die kleinste denkbare Anzahl 1, somit die Existenz mindestens eines Elements. Die Formen lassen sich weiter umformulieren und die ersten Schritte zur Prädikatenlogik sind gemacht:

Form	sprachlich	prädikativ
SaP	alle (Elemente x aus) S sind (Elemente von) P	$\forall x|x\in S\land x\in P$
SeP	kein (Element x aus) S ist (Element von) P	$\forall x|x\in S\land x\notin P$
SiP	es existiert mindestens ein Element in S, das auch in P ist	$\exists x|x\in S\land x\in P$
SoP	es existiert mindestens ein Element in S, das nicht in P ist	$\exists x|x\in S\land x\notin P$

Offenbar ist immer nur die zweite Menge von Nichtenthaltensein betroffen. Eine andere sprachliche Variante der Ausdrücke nennt die Menge S auch Subjekt und die Menge P Prädikat. Prinzipiell ist diese Bezeichnung zwar erst in den Figuren erlaubt, aber sie tritt bei jeder Figur in der Konklusion auf.

Es kann also zunächst festgehalten werden, dass die Formen immer rein subjektive Ausdrücke darstellen, denn die Menge S dient als Quelle der zu betrachtenden Elemente.

Diese Subjektivität ist aus den ersten Auflistungen nicht sofort ersichtlich, zumal an den Mengenrelationen auch negierte Mengen beteiligt sind. Eine negierte Menge besitzt verblüffende Eigenschaften, hinsichtlich ihrer Elemente. Angenommen die Menge S ist {1, 2, 3, 4} und die Aussage SeP behauptet, dass kein Element aus S in P sei. Was kann dann mit Sicherheit über die Menge P gesagt werden?

Diese Menge enthält zweifellos alle im letzen Jahr geplatzten Reifen und natürlich auch alle Zeitungsenten und noch eine ganze Anzahl weiterer Elemente. Es wäre müßig, die Elemente aus P aufzuzählen. Von der Menge P kann nur eine sinnvolle Aussage gemacht werden, nämlich dass P genau die Elemente aus S nicht enthält.

Immer wenn das Negationszeichen vor einer Menge steht, kann nur auf Elemente geschlossen werden, die nicht in ihr enthalten sind. Keinesfalls kann eine Aussage über den Inhalt als Ganzes gemacht werden. Ein Beispiel mit bekannten Mengen wird etwas mehr Klarheit bringen.

Welche Menge ergibt sich aus der Negation von $\mathbb {Z}$? Spontan wird die Antwort wohl auf die "Menge der gebrochenen Zahlen" hinauslaufen. Der Beweis steht allerdings noch aus. Ein wenig präziser muss die Frage aber noch formuliert werden.

Keine der bekannten Zahlenmengen erfüllt $\neg \mathbb {Z}$ eindeutig. Es wurde noch nicht einmal verlangt, dass es sich überhaupt um eine Zahlenmenge handeln soll. Hier wird jetzt diese Einschränkung getroffen. Auch das ist noch nicht ausreichend. Die Forderung wird weiter eingeschränkt und es wird nach der kleinst möglichen Zahlenmenge $\neg \mathbb {Z}$ gesucht, die aus den vorhandenen Zahlenmengen gebildet werden kann.

Damit müssen erst einmal die möglicherweise beteiligten Zahlenmengen und deren Hierarchie betrachtet werden. Es sind

$\mathbb {N} \subset \mathbb {Z} \subset \mathbb {Q} \subset \mathbb {R}$

Die nächst mächtigere Zahlenmenge von $\mathbb {Z}$ ist $\mathbb {Q}$ und deshalb werden auch diese beiden Mengen etwas näher betrachtet. Zweifellos ist jedes Element der ganzen Zahlen auch in der Menge der rationalen Zahlen enthalten.

Es ist die Form $\mathbb {Z} \,\mathbf {a} \,\mathbb {Q}$ vorhanden und somit ist $\forall x|x\in \mathbb {Z} \land x\in \mathbb {Q}$

Umgekehrt sind einige (natürlich sind es unendlich viele) Elemente aus $\mathbb {Q}$ auch in $\mathbb {Z}$ vorhanden. Interessant ist nun die Frage, welche Elemente. Diese Frage entspricht der Form

$\mathbb {Q} \,\mathbf {i} \,\mathbb {Z}$ und damit $\exists x|x\in \mathbb {Q} \land x\in \mathbb {Z}$

Unter den gemachten Voraussetzungen ist $\neg \mathbb {Z}$ die Zahlenmenge, die $\mathbb {Z}$ zunächst enthält und von der dann $\mathbb {Z}$ entfernt wurde. Die Menge ist also einfach

$\mathbb {Q} \setminus \mathbb {Z}$

Jetzt ist auch sichergestellt, dass $\mathbb {Q}$ keine Teilmenge von $\mathbb {Q} \setminus \mathbb {Z}$ ist. Nichts anderes als $\neg \left(S\subseteq \neg P\right)$ wird in der Mengenrelation verlangt. Die Negation einer Menge ist gelungen.

Bei der Negation der ganzen Zahlen handelt es sich tatsächlich um die Menge aller Brüche ohne den trivialen Nenner 1.

Zugegeben, ein sehr mühsamer und beschwerlicher Weg, aber für die Existenz von Modi wie darapti unbedingt erforderlich.

Eine sehr wichtige Feststellung wurde im vorletzten Absatz getroffen. Die Umkehrung einer Form. Es ist bemerkenswert, dass die Form SiP die Umkehrung von SaP ist und SoP die Verneinung von SeP. Eine Tabelle schafft immer etwas Übersicht und deshalb folgt hier eine mit Umkehrungen, Verneinungen und Synonymen der Formen.

Aussage	Original	Umkehrung	Synonym	Negation
alle S sind P	SaP	PiS	Se¬P	SoP
kein S ist P	SeP	PeS	Sa¬P	SiP
einige S sind P	SiP	PiS	So¬P	SeP
einige S sind nicht P	SoP		Si¬P	SaP

Eine Umkehrung der o-Form ist sinnlos. Der Vollständigkeit halber wurde zur Umkehrung noch ein Synonym angegeben, das die zweite Menge in negierter Form enthält. Erwähnenswert ist hier nur das Synonym von SiP, das besagt: “Einige S sind nicht (o-Form) nicht P (P-Negation)”. Es handelt sich um eine doppelte Negation, die einfach entfallen kann, wie die ursprüngliche i-Form ja auch aussagt.

Algebra der Mengen und der Aussagelogik

Grundlage der Syllogismen sind die De Morganschen Gesetze, die keinesfalls auf die Aussagelogik begrenzt sind. Die Anwendung dieser Gesetze innerhalb der Mengentheorie wird der Anwendung in der Aussagelogik gegenübergestellt. Zunächst müssen die vorkommenden Argumente und ihre möglichen Belegungen definiert werden. Dabei wird von einer Bezugsmenge M ausgegangen, das als Menge aller möglichen Belegungen der Argumente (A, B) dient. Wer sich lieber rein sprachlich orientiert, mag den Begriff "Kontext" (nicht zu verwechseln mit Konsens) als entsprechende Assoziation verwenden.

Aufgabe:

Frage zum Mittelbegriff. Parallelen zu Z und Q

Nun können die möglichen Argumentinhalte festgelegt werden. Dabei wird der sprachliche Gehalt nicht unbedingt auf mathematische Korrektheit festzulegen sein.

Sprachlich	Mengentheorie	Aussagelogik
A ist ...	$A\subseteq W$	$A\subseteq W$
A ist nicht ...	$\neg A=\left(W\setminus A\right)$	$\neg A=\left(W\setminus A\right)$

Das scheint ja nicht gerade schwierig zu sein. Die Negation von A ist gleich der Menge, die übrig bleibt wenn aus der Bezugsmenge A entfernt wird. Stimmt das? Liegt dann Gleichheit vor?

Was ist Gleichheit?

Die Mathematik hat sich mit der Definition des Gleiheitsbegriffs schwer getan. Die sehr allgemeine Fassung von Gleichheit lautet:

$\left(A=B\right)\Leftrightarrow \neg \left(A\subset B\right)\land \neg \left(B\subset A\right)$

Hier steht, dass A nicht echte Teilmenge von B ist und B nicht echte Teilmenge von A ist. Wird die Negation der beiden Terme durchgeführt, lautet die Gleichheitsrelation:

$\left(A=B\right)\Leftrightarrow \left(A\supseteq B\right)\land \left(B\supseteq A\right)$

Eine kleine Äquivalenzumformung führt dann zu der allgemein bekannten Relation:

$\left(A=B\right)\Leftrightarrow \left(A\subseteq B\right)\land \left(B\subseteq A\right)$

Das sieht doch sehr nach einem Syllogismus aus.

Aufgabe:

Bestimmen des Syllogismus.

Die Gesetze

Bis jetzt sind keine Unterschiede der beiden Gebiete zu erkennen. Störend mag die Konjunktion in der Definition von Gleichheit sein, aber auch sie wird nun näher betrachtet. Erst einmal die Aussagelogik von der Mengenalgebra getrennt.

Operation	Mengentheorie	Aussagelogik
Konjunktion	$\left(A\cap B\right)\subseteq M$	$A\land B$
Disjunktion	$\left(A\cup B\right)\subseteq M$	$A\lor B$

Damit in den folgenden Ausführungen nicht immer der Zusatz "ist Teilmenge der Bezugsmenge" angegeben werden muss, wird diese Tatsache hier erwähnt und in Zukunft einfach weggelassen. Der gute Wille sei nun bei allen Interessierten vorausgesetzt. Die Gegenüberstellung vereinfacht sich so zu

Operation	Mengentheorie	Aussagelogik
Konjunktion	$A\cap B\$	$A\land B$
Disjunktion	$A\cup B\$	$A\lor B$

In beiden Systemen müssen Gesetze existieren, die Kombinationen der Operatoren zulassen und so den Aufbau von Termen gestatten. Die drei elementarsten Gesetze sind Kommutativ-, Assoziativ- und Distributivgesetz. In der folgenden Tabelle sind alle wesentlichen, auch die De Morganschen, Gesetze, vertreten.

Idempotenz	Menge	$A\cap A=A\$	$A\cup A=A$
	Logik	$A\land A=A$	$A\lor A=A$
Kommutativ	Menge	$A\cap B=B\cap A\$	$A\cup B=B\cup A$
	Logik	$A\land B=B\land A$	$A\lor B=B\lor A$
Assoziativ	Menge	$A\cap \left(B\cap C\right)=\left(A\cap B\right)\cap C$	$A\cup \left(B\cup C\right)=\left(A\cup B\right)\cup C$
	Logik	$A\land \left(B\land C\right)=\left(A\land B\right)\land C$	$A\lor \left(B\lor C\right)=\left(A\lor B\right)\lor C$
Distributiv	Menge	$A\cap \left(B\cup C\right)=\left(A\cap B\right)\cup \left(A\cap C\right)$	$A\cup \left(B\cap C\right)=\left(A\cup B\right)\cap \left(A\cup C\right)$
	Logik	$A\land \left(B\lor C\right)=\left(A\land B\right)\lor \left(A\land C\right)$	$A\lor \left(B\land C\right)=\left(A\lor B\right)\land \left(A\lor C\right)$
De Morgan	Menge	$\neg \left(A\cap B\right)=\neg A\cup \neg B$	$\neg \left(A\cup B\right)=\neg A\cap \neg B$
	Logik	$\neg \left(A\land B\right)=\neg A\lor \neg B$	$\neg \left(A\lor B\right)=\neg A\land \neg B$
Doppelnegation	Menge	$\neg \neg A=\neg \left(\neg A\right)=A$
	Logik

Es scheint keinen Unterschied zwischen der Mengentheorie und der Aussagelogik zu geben, wenn in beiden Fällen von einer diskreten, zweielementigen Bezugsmenge ausgegangen wird. Die Doppelnegation ist jedoch ein Punkt, der oft auf Probleme stößt, insbesonders wenn die eben erwähnte Bezugsmenge als Grundlage dient. Hier muss noch weiter untersucht werden.

Mit

$M=\left\{wahr,\,falsch\right\};\ A=\left\{wahr\right\}$

ergibt sich die Negation aus

${\begin{aligned}\neg A&=M\setminus A\\&=\left\{wahr,\,falsch\right\}\setminus \left\{wahr\right\}\\&=\left\{falsch\right\}\end{aligned}}$

Die Negation einer Aussage macht offenbar keinerlei Probleme. Aber oft muss eine negierte Aussage negiert werden, was einer doppelten Negation gleichkommt. Unter den gleichen Voraussetzungen ergibt sich nun

${\begin{aligned}\neg \neg A&=\neg \left(\neg A\right)\\&=M\setminus \left(\neg A\right)\\&=M\setminus \left\{M\setminus A\right\}\\&=\left\{wahr,\,falsch\right\}\setminus \left\{\left\{wahr,\,falsch\right\}\setminus \left\{wahr\right\}\right\}\\&=\left\{wahr,\,falsch\right\}\setminus \left\{\left\{falsch\right\}\right\}\\&=\left\{wahr\right\}\end{aligned}}$

Auch hier sollten nun keine Probleme mehr bestehen. Aber eine interessante Möglichkeit eröffnet sich. Die vorhandene Bezugsmenge kann noch weiter eingeschränkt werden. Es umfasst zwar die Elemente wahr und falsch, aber mathematisch ausreichend ist es wenn überhaupt nur zwei Möglichkeiten zur verfügung stehen. Die hier verwendete Bezugsmenge bietet aber mehr Möglichkeiten eine Variable wie A zu belegen, auch wenn sie nicht sofort ersichtlich sind.

AUFGABE: Finden aller Belegungen.

Potenzielle Möglichkeiten der Belegung

Alle Möglichkeiten der Belegung einer Variablen bezogen auf eine Menge entspricht der Frage was potenziell sein kann. Das ist nichts weiter als die Ermittlung der Potenzmenge. Die Potenzmenge P einer Menge M ist die Menge aller möglichen Teilmengen.

$P\left(M\right)=P\left(\left\{wahr,\,falsch\right\}\right)=\left\{\left\{\right\},\,\left\{wahr\right\},\,\left\{falsch\right\},\,\left\{wahr,\,falsch\right\}\right\}$

Alle diese Möglichkeiten stehen bereit. Um Fehlbelegungen zu verhindern müssen also stets Vereinbarungen getroffen werden. Wünschenswert ist eine Übereinstimung von möglichen Belegungen mit den Elementen aus der Potenzmenge der Bezugsmenge.

Aufgabe:

Wieviele Elemente darf die Potenzmenge haben, um eine duale Logik zu ermöglichen?

Hier wird deutlich, warum eine Aussagelogik mit der Bezusmenge M = { wahr, falsch } die Operanden normieren muss. Wird das Element falsch mit 0 und ds Element wahr mit 1 assoziiert, liegt eine Normierung vor. Die Potenzmenge stellt aber zu viele Möglichkeiten bereit, weshalb die Auswahl auf die zwei genannten begrenzt werden muss.

Herleitung einer minimalen Bezugsmenge

Sprachliche Assoziationen zu Gegebenheiten in der Mathematik sollten möglichst ebenso knapp gehalten werden wie es die Mathematik ermöglicht. Dafür müssen oft viele Definitionen gemacht werden. Hier verhält es sich nicht anders, wie die bisher gemachten Ausführungen zeigen. Jedoch soll jetzt der Weg einmal umgekehrt werden. Prinzipiell genügen nur zwei Festlegungen, um die Bezugsmenge zu spezifizieren.

1. Die Wertemenge enthält alle Elemente die eine Aussage annehmen kann.
2. Für alle Aussagen gilt, dass sie entweder wahr oder nicht wahr sind.

Zu beachten ist hier, dass der Begriff "falsch" mit "nicht wahr" umschrieben wird. Die Verndung des Begriffs "falsch" ist in der Mathematik äußerst heikel, denn es sagt nichts anderes aus als die Verneinung von "wahr".

In dieser Spezifikation ist nur ein Wert sprachlich assoziiert, es ist "wahr". Dieses Element wird also in der Bezugsmenge vorhanden sein.

Sei

$M=\left\{wahr\right\}$

dann ist

$P\left(M\right)=P\left(\left\{wahr\right\}\right)=\left\{\left\{\right\},\,\left\{wahr\right\}\right\}$

Die möglichen Belegungen sind nun mit der Potenzmenge von M "abgesichert". Damit gilt für Variablen

$\left(\left(A\subseteq M\right)\land \left(M\subset P\left(M\right)\right)\right)\Rightarrow \left(A\subset P\left(M\right)\right)$

Die Mengenrelationen "Teilmenge und echte Teilmenge sind sehr wichtig. Es ist stets gegeben, dass eine Menge M nur echte Teilmenge seiner Potenzmenge ist. Daraus folgt unmittelbar, dass jede Teilmenge von M echte Teilmenge der Potenzmenge von M ist. Eigentlich trivial, aber eben sehr wichtig für die weiteren Ausführungen. In jedem Fall sind die aufgestellten Forderungen erfüllt, es gibt keine weiteren Möglichkeiten zur Belegung.

Aufgabe:

Was kann über die Mächtigkeiten (Beträge) der beteiligten Mengen gesagt werden?

Mengen haben die grundsaätzliche Eigenschaft der Mächtigkeit. Ohne die Elemente zu betrachten, steht diese Eigenschaft immer bereit. Wird also eine einelementige Bezugsmenge wie M = { wahr } benutzt, ergibt sich die Normierung direkt aus den Beträgen. Als angenehmer Nebeneffekt ergibt außerdem, dass die Potenzmengenur güötige Möglichkeiten zur Auswahl enthält.

Logische Werte

Werte sind verbunden mit Größen. Für den Umgang mit diesen beiden Begriffen wurde die Arithmetik "erfunden". In diesem Abschnitt wird der "berechnende" Umgang mit logischen Werten besprochen. Es werden die Grundlagen geschaffen wie auch komplexe Ausdrücke der Aussagenlogik einfach berechnet werden können. Parallel werden die aufgestellten Gesetze bewiesen.

Der kleinste Wert

„Klein“ muss auf irgend etwas bezogen sein. Dieser Begriff hat nur Sinn, wenn er einen Maßstab besitzt. So könnte "klein im Verhältnis zu ..." ein derartiger Bezug sein. Jedoch ist diese Formulierung gefährlich denn sie verlangt nach der Division (Verhältnis). Wenn "klein" mit 0 (Null) assoziiert ist, ist ein Verhältnis sinnlos. Besser, weil unverfänglicher, ist die Formulierung "klein bezogen auf ...".

Den einzige Bezug stellt die Bezugsmenge dar. Sie hat die Kardinalität (Mächtigkeit) 1, denn sie enthält genau ein Element. Statt Kardinalität kann auch "Betrag" benutzt werden. Das hat außerdem den Vorteil, eine Formulierung zu besitzen.

$M=\left\{wahr\right\};\;|M|=1$

Jede Variable kann entweder das Element "wahr" enthalten, oder sie ist leer. Im ersten Fall entspricht ihr Betrag dem der Bezugsmenge, also 1. Ist sie leer, enthält also kein Element, so gilt

$A=\left\{\right\};\;|A|=0$

Trotzdem ist sie Teilmenge der Bezugsmenge, denn die leere Menge ist Teilmenge jeder Menge.

${\begin{aligned}A=\left\{\right\};&\;A\subseteq M\\A=\left\{wahr\right\};&\;A\subseteq M\end{aligned}}$

Der kleinste Wert ist also 0, der größte 1.

Trichotomie

Jetzt ist ein echter Größenvergleich von Aussagen möglich. Weil jede Aussage einer Menge mit genau einem Element aus der Potenzmenge der Bezugsmwenge ist, gibt es nur die beiden Beträge 0 und 1. Weil 0 der Betrag einer leeren Menge ist, gilt zweifellos dass eine leere Menge kleiner als eine nicht leere ist.

${\begin{aligned}A=\left\{\right\};\;B=\left\{\right\};\;A=B\lor A\leq B\\A=\left\{\right\};\;B=\left\{wahr\right\};\;A<B\lor A\leq B\\A=\left\{wahr\right\};\;B=\left\{\right\};\;B<A\lor B\leq A\\A=\left\{wahr\right\};\;B=\left\{wahr\right\};\;B=A\lor B\leq A\end{aligned}}$

Statt den willkürlichen Zuordnungen "falsch=0" und "wahr=1" herrscht jetzt Gewissheit. Nun können die Formen der Syllogismen mit allen Belegungen dargestellt werden, die für die Aussagenlogik relevant sind.

Die Negation mit Werten

Die Negation ist nun eine Subtraktion. Sie war es zwar bereits in der reinen Mengenalgebra über die Bildung der Differenzmenge, aber jetzt kann sie arithmetisch formuliert werden.

$\neg A=|M|-|A|=1-|A|$

Weil der Betrag der Menge A entweder 0 oder 1 ist, liegt die erste arithmetische Formulierung in dem neuen Zusammenhang vor. Es werden weitere folgen, aber zunächst müssen die Formen der Syllogismen komplettiert werden.

Die Formen mit allen Belegungen

Es genügt, die vier Formen einach in Tabellen darzustellen und ihre Aussagen zu bestätigen. Wichtig: $S,\,P\subseteq \left\{wahr\right\}$

Die Form SaP behauptet: Alle Elemente aus S sind auch in P. $S\subseteq P$

SaP
$\,S\,$	$\,P\,$	$S\subseteq P$	$s\,=\,|S|$	$p\,=\,|P|$	$s\,\leq \,p$
$\left\{\right\}$	$\left\{\right\}$	$\left\{wahr\right\}$	$\,0\,$	$\,0\,$	$\,1\,$
$\left\{\right\}$	$\left\{wahr\right\}$	$\left\{wahr\right\}$	$\,0\,$	$\,1\,$	$\,1\,$
$\left\{wahr\right\}$	$\left\{\right\}$	$\left\{\right\}$	$\,1\,$	$\,0\,$	$\,0\,$
$\left\{wahr\right\}$	$\left\{wahr\right\}$	$\left\{wahr\right\}$	$\,1\,$	$\,1\,$	$\,1\,$

Die Behauptung ist richtig, denn wenn S Teilmenge von P ist, dann muss die Mächtigkeit von S kleiner oder gleich der von P sein.

Die Form SoP behauptet: Einige Elemente aus S sind nicht in P. $\neg \left(S\subseteq P\right)$

SoP
$\,S\,$	$\,P\,$	$\neg \left(S\subseteq P\right)$	$s\,=\,|S|$	$p\,=\,|P|$	$\neg \left(s\,\leq \,p\right)$
$\left\{\right\}$	$\left\{\right\}$	$\left\{\right\}$	$\,0\,$	$\,0\,$	$\,0\,$
$\left\{\right\}$	$\left\{wahr\right\}$	$\left\{\right\}$	$\,0\,$	$\,1\,$	$\,0\,$
$\left\{wahr\right\}$	$\left\{\right\}$	$\left\{wahr\right\}$	$\,1\,$	$\,0\,$	$\,1\,$
$\left\{wahr\right\}$	$\left\{wahr\right\}$	$\left\{\right\}$	$\,1\,$	$\,1\,$	$\,0\,$

Die Behaupting ist richtig, denn wenn einige Elemente aus S nicht in P sind, dann muss die Mächtigkeit von S größer der von P sein.

Die Form SeP behauptet: Kein Element aus S ist in P. $S\subseteq \neg P$

SeP
$\,S\,$	$\,P\,$	$S\subseteq \neg P$	$s\,=\,|S|$	$p\,=\,|\neg P|$	$\neg \left(s\,\leq \,p\right)$
$\left\{\right\}$	$\left\{\right\}$	$\left\{wahr\right\}$	$\,0\,$	$\,1\,$	$\,1\,$
$\left\{\right\}$	$\left\{wahr\right\}$	$\left\{wahr\right\}$	$\,0\,$	$\,0\,$	$\,1\,$
$\left\{wahr\right\}$	$\left\{\right\}$	$\left\{wahr\right\}$	$\,1\,$	$\,1\,$	$\,1\,$
$\left\{wahr\right\}$	$\left\{wahr\right\}$	$\left\{\right\}$	$\,1\,$	$\,0\,$	$\,0\,$

Die Behauptung ist richtig, denn wenn kein Element aus S in P ist, dann muss S Teilmenge der negierten Menge P sein.

Die Form SiP behauptet: Einige Elemente aus S sind in P. $\neg \left(S\subseteq \neg P\right)$

SiP
$\,S\,$	$\,P\,$	$\neg \left(S\subseteq \neg P\right)$	$s\,=\,|S|$	$p\,=\,|\neg P|$	$\neg \left(s\,\leq \,p\right)$
$\left\{\right\}$	$\left\{\right\}$	$\left\{\right\}$	$\,0\,$	$\,1\,$	$\,0\,$
$\left\{\right\}$	$\left\{wahr\right\}$	$\left\{\right\}$	$\,0\,$	$\,0\,$	$\,0\,$
$\left\{wahr\right\}$	$\left\{\right\}$	$\left\{\right\}$	$\,1\,$	$\,1\,$	$\,0\,$
$\left\{wahr\right\}$	$\left\{wahr\right\}$	$\left\{wahr\right\}$	$\,1\,$	$\,0\,$	$\,1\,$

Die Behauptung ist richtig, denn wenn Einige Elemente aus S in P sind, dann kann S nicht Teilmenge der negierten menge P sein.

Offensichtlich sind in den jeweils rechten Spalten der Tabellen die einfachen, gewohnten Darstellungen mit 0 und 1 vorhanden. Für die Aussagelogik genügt diese Darstellung, zumal ja die Korrektheit dieser Belegung der Variablen in den vorherigen Abschnitten bewiesen wurde.

So können die Formen der Syllogismen in die Aussagelogik überführt werden. Dabei darf niemals vergessen werden, dass es sich um Mengen unterschiedlicher Mächtigkeiten handelt. Es ist jetzt eine Abstraktion vorhanden, die Wahrheiten auf Beträge zur arithmetischen Bearbeitung reduziert.

Eine abschließende Tabelle zeigt die vereinfachte Darstellung der Formen und eröffnet den Einstieg in die Aussagelogik. Statt der Mengenrelationen sind die offensichtlichen logischen Funktionen gleich eingesetzt.

SaP			SoP			SeP			SiP
S	P	$S\,\leq \,P$	S	P	$S\,>\,P$	S	P	$\neg \left(S\,\land \,P\right)$	S	P	$S\,\land \,P$
0	0	1	0	0	0	0	0	1	0	0	0
0	1	1	0	1	0	0	1	1	0	1	0
1	0	0	1	0	1	1	0	1	1	0	0
1	1	1	1	1	0	1	1	0	1	1	1

Damit stehen vier logische Funktionen als Synonyme der vier Formen fest. Es sind:

• SaP = $\neg S\lor P$ Implikation
• SoP = $S\land \neg P$ Inhibition
• SeP = $\neg \left(S\land P\right)$ Nicht-Und (NAND)
• SiP = $S\land P$ Konjunktion (AND)

Aufgabe:

1. Wie werden die Werte der möglichen Aussagen ermittet?
2. Welche(s) Kriteri(en/um) der beteiligten Mengen wird/werden für die Ermittlung der Werte herangezogen?

Übergang zur Aussagelogik

Intime Kenner der Boolschen Algebra werden nun sofort erkennen, dass sich aus diesen Funktionen genau 16 mögliche Verknüpfungen (also 12 weitere) ergeben. Der Vollständigkeit halber sei hier das (vollständige) System zweier Wahrheitswerte dargestellt und die Positionen der vier Formen gekennzeichnet.

S	P	Beträge der möglichen Verknüpungen
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
Nr.		0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
Form			i	o											a	e

Sehr schön zu erkennen ist die Symmetrie in den Positionen der Formen.

Aufgabe:

Ist die Tabelle vollständig?

Hinweis: Nicht die Anzahl der möglichen Verküpfungen ist gemeint.

Einstieg in die Aussagelogik

Die jetzt herausgearbeiteten Formen, mit den Beträgen (Mächtigkeiten) der minimalen Mengen, ist die Basis für die vielen Programme zur sog. regelbasierten künstlichen Intelligenz. Die Sprache Prolog (PROgramming in LOGic) ist wohl der populärste Vertreter.

In den folgenden Abschnitten werden die gültigen Syllogismen (Schlussregeln) benutzt, um die Aussagelogik zu beweisen. Danach werden die Grundlagen für allgemeine Beweissysteme gelegt. So wird das Verständnis der deklarativen Programmierung direkt über die zugrunde liegenden Horn-Klauseln erleichtert.

Die bekannten Probleme bei der Aufstellung der erforderlichen Axiome und der darauf basierenden Beweise bildet den Abschluss. Ein möglicher Ausweg wird ebenfalls skizziert, jedoch ist die Mathematik hier erst am Anfang.

Syllogismen als binäre Verknüpfungen

Die Syllogismen werden hier noch einmal in einer binären Formulierung dargestellt. Für die Operanden der Formen gilt die minimale Bezugsmenge. Der Mittelbegriff bei den Syllogismen "M" ist mit der Bezugsmenge bei der Mengenalgebra "M" identisch.

Figur-1
1. Prämisse	2. Prämisse	Konjunktion	Konklusion	Modus
$\neg M\lor P$	$\neg S\lor M$	$\left(\neg M\lor P\right)\land \left(\neg S\lor M\right)$	$\neg S\lor P$	barbara
$\neg \left(M\land P\right)$	$\neg S\lor M$	$\neg \left(M\land P\right)\land \left(\neg S\lor M\right)$	$\neg \left(S\land P\right)$	celarent
$\neg M\lor P$	$S\land M$	$\left(\neg M\lor P\right)\land \left(S\land M\right)$	$S\land P$	darii
$\neg \left(M\land P\right)$	$S\land M$	$\neg \left(M\land P\right)\land \left(S\land M\right)$	$S\land \neg P$	ferio

Figur-2
1. Prämisse	2. Prämisse	Konjunktion	Konklusion	Modus
$\neg \left(P\land M\right)$	$\neg S\lor M$	$\neg \left(P\land M\right)\land \left(\neg S\lor M\right)$	$\neg \left(S\land P\right)$	cesare
$\neg P\lor M$	$\neg \left(S\land M\right)$	$\left(\neg P\lor M\right)\land \neg \left(S\land M\right)$	$\neg \left(S\land P\right)$	camestres
$\neg \left(P\land M\right)$	$S\land M$	$\neg \left(P\land M\right)\land \left(S\land M\right)$	$S\land \neg P$	festino
$\neg P\lor M$	$S\land \neg M$	$\left(\neg P\lor M\right)\land \left(S\land \neg M\right)$	$S\land \neg P$	baroco

Figur-3
1. Prämisse	2. Prämisse	Konjunktion	Konklusion	Modus
$\neg M\lor P$	$M\land S$	$\left(\neg M\lor P\right)\land \left(M\land S\right)$	$S\land P$	datisi
$\neg \left(M\land P\right)$	$M\land S$	$\neg \left(M\land P\right)\land \left(M\land S\right)$	$S\land \neg P$	feriso
$M\land P$	$\neg M\lor S$	$\left(M\land P\right)\land \left(\neg M\lor S\right)$	$S\land P$	disamis
$M\land \neg P$	$\neg M\lor S$	$\left(M\land \neg P\right)\land \left(\neg M\lor S\right)$	$S\land \neg P$	bocardo

Figur-4
1. Prämisse	2. Prämisse	Konjunktion	Konklusion	Modus
$\neg P\lor M$	$\neg \left(M\land S\right)$	$\left(\neg P\lor M\right)\land \neg \left(M\land S\right)$	$\neg \left(S\land P\right)$	calemes
$\neg \left(P\land M\right)$	$M\land S$	$\left(\neg P\lor M\right)\land \left(M\land S\right)$	$S\land \neg P$	fresison
$P\land M$	$\neg M\lor S$	$\left(P\land M\right)\land \left(M\land S\right)$	$S\land P$	dimatis

Es fehlen vier Syllogismen. Sie sind mit den hier verwendeten Operationen nicht direkt nachzuvollziehen und werden deshalb gesondert behandelt. Es sind aus der Figur-3 die Modi darapti, felapton und aus Figur-4 die Modi bamalip, fesapo. Für eine nähere Betrachtung dieser Modi müssen zunächst die bereits gezeigten Gesetze einschließlich der Trichotomie näher betrachtet werden. Es fehlt nämlich noch der Beweis dieser 15 Syllogismen. Für die Beweise müssen unwiderlegbare Fakten , die Axiome bereitstehen. Die Grundlage bildet der Modus barbara, denn er kann allein über Größenvergleiche (Trichotomie) sehr leicht nachvollzogen werden.

Beweis der Gültigkeit

Den Ausgangspunkt bildet der Modus barbara. Dieser Modus wird deshalb hier sehr detailliert dargestellt.

In der folgenden Tabelle gilt:

$S,\;P\subseteq M;\ m=|M|;\ s=|S|;\ p=|P|$

	Mengenrelation	Größenrelation	Werterelation
1. Prämisse	${\boldsymbol {M}}\subseteq P$	${\boldsymbol {|M|}}\leq |P|$	${\boldsymbol {m}}\leq p$
2. Prämisse	$S\,\,\subseteq {\boldsymbol {M}}$	$|S|\,\leq {\boldsymbol {|M|}}$	$s\,\leq {\boldsymbol {m}}$
Konklusion	$S\,\,\subseteq P$	$|S|\,\leq |P|$	$s\ \leq p$

Dieser Modus ist sehr einfach in allen drei Darstellungen nachzuvollziehen. Die Bezugsmenge, die Bezuggröße und der Bezugswert ist in jeder Spalte fett dargestellt. Es wird jeweils nur der Bezug für Subjekt S und Prädikat P bereitgestellt. Weil die beiden Prämissen nun einen gemeinsamen Bezug haben, ist dieser Bezug in der Konklusion nicht erforderlich.

Am Ende des Abschnitts "Vorbereitung auf die erforderlichen Algebren" wurde auf mögliche Synonyme, die Nagation und die Umkehrung von Formen eingegangen. Mit diesen Möglichkeiten kann jede Figur in eine andere gewandelt werden, ohne die Konklusion zu ändern.

Ein Beispiel:

Der Modus festino aus der zweiten Figur hat in der Konklusion die o-Form. In der ersten Figur hat ferio die gleiche Konklusion.

	ferio	festino
Prämisse-1	MeP	PeM
Prämisse-2	SiM	SiM
Konklusion	SoP	SoP

Die Mittelbegriffe sind fett dargestellt, um die unterschiedlichen Positionen deutlich zu machen. Abgesehen von diesen Positionen ähneln sich die beiden Syllogismen. Jedoch handelt es sich bei den ersten Prämissen um völlig verschiedene Relationen.

Der Modus festino muss in die erste Figur überführt werden. Damit ist eine Umkehrung der ersten Prämisse nötig. Entsprechend der angeführten Tabele im Abschnitt "Vorbereitung auf die erforderlichen Algebren" gilt:

$P\ {\boldsymbol {e}}\ M\ =\ M\ {\boldsymbol {e}}\ P$

Die e-Form ist ihre eigene Umkehrung? Das muss überprüft werden. Die Mengenrelation lautet:

$M\subseteq \neg P\ \equiv \ P\subseteq \neg M$

Die beiden folgenden Tabellen zeigen die Korrektheit der Behauptung:

$M\$	$\neg P$	$M\subseteq \neg P$
$\{\}\$	$\{wahr\}\$	$\{wahr\}\$
$\{\}\$	$\{\}\$	$\{wahr\}\$
$\{wahr\}\$	$\{wahr\}\$	$\{wahr\}\$
$\{wahr\}\$	$\{\}\$	$\{\}\$

$P\$	$\neg M\$	$P\subseteq \neg M$
$\{\}\$	$\{wahr\}\$	$\{wahr\}\$
$\{wahr\}\$	$\{wahr\}\$	$\{wahr\}\$
$\{\}\$	$\{\}\$	$\{wahr\}\$
$\{wahr\}\$	$\{\}\$	$\{\}\$

Der Modus festino kann also durch einfaches Umdrehen der ersten Prämisse in den Modus ferio gewandelt werden. Es sei hier festgestellt, dass alle Figuren auf die gezeigte Art und Weise wandelbar sind. Diese Tatsache für jeden Syllogismus darzustellen würde allerdings wenig zum weiteren Verständnis beitragen.

Die Syllogisman können statt als Mengenrelationen auch in ihrer Booleschen Notation formuliert werden. Die wichtigste Form, die allen Syllogismen zugunde liegt, ist die a-Form.

$P\subseteq M;\ p\leq m;\ \neg p\lor m;\ p\Rightarrow m$

Die beiden letzten Relationen sind entscheidend. Es handelt sich um eine Horn-Klausel, oder um die Implikation. Sie bildet die Grundlage für die logische Programmierung in Systemen wie Prolog.

Aufgabe:

Nachweis der Äquivalenz der Formen PeM und MeP nur unter Verwendung von Wertrelationen.

Ein Hinweis auf Horn-Klauseln

Eine Hornformel ist gegeben, wenn die einzelnen Terme Disjunktionen sind und konjunktiv verknüpft werden. In den Disjunktionen darf nur ein Operand nicht negiert sein. Diese Disjunktionen sind Hornklauseln. Damit ist gesagt, dass eine Hornformel nur aus konjunktiv verknüpften Hornklauseln besteht.

Folgende Formel ist eine Hornformel:

$H=\left(\neg c\lor \neg a\lor d\right)\land \left(a\lor \neg b\right)$

Die Formel scheint nicht die genanten Kriterien zu erfüllen. Das ist allerdings nur auf den ersten Blick so. Einige algebraische Umformungen liefern tatsächlich die geforderten Disjunktionen.

${\begin{aligned}H=&\left(\neg c\lor \neg a\lor d\right)\ \left(Zusammenfassen\ von\ \neg c\lor \neg a\right)\\\land &\left(a\lor \neg b\right)\ \ \ \ \ \ \ \ \left(Vertauschen\ von\ a\ und\ \neg b\right)\\\end{aligned}}$

Die Umsetzung der in den "Kommentaren" angegebenen Hinweise führt zu den Hornklauseln

$H=\left(\neg \left(c\land a\right)\lor d\right)\land \left(\neg b\lor a\right)$

Jetzt kann die asymmetrische Notation der Horn-Klauseln angewendet werden und es ergibt sich eine sehr übersichliche Hornformel.

${\begin{aligned}H=\left(\left(c\land a\right)\Rightarrow d\right)\land \left(b\Rightarrow a\right)\end{aligned}}$

Mit diesen Hornformeln, die aus Hornklauseln aufgebaut sind, ist der Schritt von den Syllogismen zur Aussagelogik möglich. Zwei Kornklauseln stellen die Prämissen dar, das Ergebnis die Konklusion. Letztere hat zwar nur einen Wert und keine Form wie bei den Syllogismen, aber das ist im Augenblick noch nicht so wichtig. Hier musste gezeigt werden, dass Größenvergleiche die gleichen Resultate ergeben wie Verknüpfungen. Hornklauseln sind sowohl Größenvergleich als auch "wenn - dann"-Aussagen.

Es muss nun noch die Berechenbarkeit der bewiesen werden, um endgültig die 16 binären Grundfunktionen der dualen Aussagelogik mit 1 und 0 zu erhalten.

Aufgabe:

In der Hornformel H werden zwei Prämissen konjunktiv verknüpft.

Welchem Modus entspricht die angegebene Hornformel H?

Arithmetisierung der Logik

Arithmetisierung hat etwas mit Berechnen zu tun. Es müssen also die Gesetze der Arithmetik (z.B. Punt- vor Strichrechnung) für die Berechnungen gelten. Im Abschnitt "Die Gesetze" wurden ähnliche Prioritäten für die Logik und die Mengen bereits dargestellt. Nun muss die Arithmetik damit in Einklang gebracht werden. Zunächst werden die Zahlenmengen für Definitions- und Wertebereich festgelegt.

• Defintionsbereich = { 0, 1 }. Nicht das Intervall [ 0...1 ] ist gemeint!
• Wertebereich = Definitionsbereich

Berechnung der Negation

Die erste Operation in diesen Betrachtungen ist die Negation. Weder ihr Argument (zu negierende Aussage) noch das Ergebnis darf die Bereiche verlassen. Der Betrag der Bezusmenge bildet die Basis.

$M=\left\{wahr\right\};\ |M|=1;\ m=|M|=1$

Für jede Aussage A gilt

$A\subseteq M;\ |A|=\left\{0,\,1\right\};\ a=|A|$

Die Negation wurde bisher über die Bildung der Differenzmenge M\A durchgeführt. Eine Differenz sollte also auch bei der Berechnung über die Beträge vorhanden sein.

$\neg a=m-a=|M|-|A|$

Es ergeben sich also genau zwei Möglichkeiten, deren Werte nun genau auf Einhaltung der Bereiche untersucht werden.

$|M|\$	$|A|\$	$|M|-|A|\$
$1\$	$0\$	$1\$
$1\$	$1\$	$0\$

Weder der Definitions- noch der Wertebereich wird verlassen. Die Negation ist arithmetisiert.

Es empfiehlt sich, die Negation in dieser Formulierung stets als Klammerterm

$\neg a=\left(m-a\right)=\left(1-a\right)$

zu werwenden. So wird vermieden, dass versehentlich die Bezugsmenge M an einem Ausdruck A negiert wird. Es sollte einleuchtend sein, dass Formulierungen wie

$\neg m=\left(a-m\right)$

unzulässig sind. Der Wertebereich kann mit dieser Operation verlassen werden.

Berechnung der Konjunktion

Die Konjunktion ist hinsichtlich ihrer Priorität eine "Punktoeration". Das ergibt sich aus dem Abschnitt "Die Gesetze", denn dort ist sie von eindeutig höherer Priorität als die Disjunktion. Es liegt also nahe, bei der Berechnung einer Konjunktion die Multiplikation heranzuziehen.

$A,\;B\subseteq M;\ a=|A|;\ b=|B|$

$a\$	$b\$	$a\cdot b\$
$0\$	$0\$	$0\$
$0\$	$1\$	$0\$
$1\$	$0\$	$0\$
$1\$	$1\$	$1\$

Wieder hat sich die Vermutung als richtig erwiesen. Auch die Konjunktion ist arithmetisiert.

Berechnung der Disjunktion

Die Disjunktion sollte also einer Strichoperation entsprechen. Weil die Subtraktion bereits bei der Negation verwendet wurde, bleibt die Addition übrig.

$A,\;B\subseteq M;\ a=|A|;\ b=|B|$

$a\$	$b\$	$a+b\$
$0\$	$0\$	$0\$
$0\$	$1\$	$1\$
$1\$	$0\$	$1\$
$1\$	$1\$	$\color {Red}2\$

Der Wertebereich wird verlassen. Die Addition ist für die Bildung der Disjunktion nicht geeignet. Was tun? Was nicht getan wird ist: Schwellenwert einbeziehen, modulo 2 Addition, "Normierung" und Ähnliches. Es muss mit den bisherigen Operationen funktionieren!

Die De Morganschen Gesetze schaffen Abhilfe. Aus Konjunktion und Negation kann die Disjunktion gebildet werden. Die Negation der Argumente und die Negation des Ergebnsses macht aus der Operation "Schnittmenge bilden" die Operation "Vereinigungsmenge bilden". Die Bildung der Schnittmenge entpricht in ihrer Priorität der Multiplikation. Das wurde bereits bei der Konjunktion gezeigt.

$a\$	$b\$	$\neg \left(\neg a\cdot \neg b\right)$	Berechnung
$0\$	$0\$	$0\$	$1-\left(\left(1-0\right)\cdot \left(1-0\right)\right)$
$0\$	$1\$	$1\$	$1-\left(\left(1-0\right)\cdot \left(1-1\right)\right)$
$1\$	$0\$	$1\$	$1-\left(\left(1-1\right)\cdot \left(1-0\right)\right)$
$1\$	$1\$	$1\$	$1-\left(\left(1-1\right)\cdot \left(1-1\right)\right)$

Auch die Disjunktion kann berechnet werden. Auch Horn-Klauseln sollten kein Problem sein. Es fehlen noch drei unäre Funktionen, die über binäre Verknüpfungen hergeleitet werden.

Aufgabe:

Zeigen, dass die Disjunktion von a und b arithmetisch als

$a+b-a\cdot b$

darstellbar ist

Berechnung der Tautologie

Eine Tautologie ist die Verknüpfung mehrerer (also mindestens zwei) Aussage zu einem Ergebnis, das immer wahr ist.

"Es regnet oder es regnet nicht.

Ist eine Tautologie, gebildet aus den Wahrheitsgehalten der Aussagen "es regnet" und "es regnet nicht". Es handelt sich in Wirlichkeit nur um eine Aussage, denn die zweite ist die Negation der ersten. Die disjunktive Verknüpng ergibt also stets wahr.

$a\$	$\neg a\$	$a\lor \neg a\$	Berechnung
$0\$	$1\$	$1\$	$1-\left(\left(1-0\right)\cdot \left(1-1\right)\right)$
$1\$	$0\$	$1\$	$1-\left(\left(1-1\right)\cdot \left(1-0\right)\right)$

Das ist nichts weiter als die Hornklausel

$a\Rightarrow a$

Trivial, aber jetzt eben berechnbare Trivialität. Diese "Operation" kann auch als die funktionale Bereitstellung der 1 angesehen werden. Wenn die 1 über eine Operation ermittelt werden kann sollte das auch mit der 0 (Null) funktionieren.

Berechnung der Kontradiktion

Die Negation der Tautologie ist die Kontradiktion. Die Verneinung der im letzten Abschnitt Aussage über eventuellen Regen lautet:

"Es regnet nicht und es regnet.

Aus der Disjunktion wurde eine Konjunktion und die entsprechende Hornklausel ist

$\neg \left(a\Rightarrow a\right)$

Sprachlich ist diese negierte Implikation schwer zu deuten. Es geht einfacher ber den Größenvergleich.

$\neg \left(a\Rightarrow a\right)\equiv \neg \left(a\leq a\right)\equiv \left(a>a\right)$

Diese Relation ist sicher nicht wahr. Die Berechnung zeigt denn auch

$a\$	$\neg a\$	$a\cdot \neg a\$	Berechnung
$0\$	$1\$	$0\$	$\left(1-0\right)\cdot \left(1-1\right)$
$1\$	$0\$	$0\$	$\left(1-1\right)\cdot \left(1-0\right)$

Herleitung weiterer Grundfunktionen

Die Konstanten 1 und 0 können also auch über Relationen bereitgestellt werden. Deshalb werden Tautologie und Kontradiktion zu den unären Funktionen gezählt.

Aufgabe:

Bitte erst diese Aufgabe lösen und dann weiterlesen.

Ermitteln der Anzahl aller möglichen unären Funktionen in der hier vorhandenen Aussagelogik.

Die letzte unäre Funktion ist die Identität. Für sie gilt allgemein:

$f(a):=a\$

Hinweis: Zur Vermeidung von Fehlinterpretationen wird bei Funktionen die Trennung von linker und rechter Seite über die Kombination ":=" vorgenommen. Im Beispiel rot dargestellt. $y\ {\color {Red}:=}\ f(x)$ Das einfache Zeichen "=" ist weiterhin die Äquivalenz.

Um endgültig alle relevanten Funktionen der Aussagelogik auch in Tabellenform zu haben, die die entsprechende Wahrheitstabelle:

$a\$	$f(a)\$
$0\$	$0\$
$1\$	$1\$

Diese Funktion ist die Negation der Negation. So trivial diese Feststellung ist, so wichtig ist die Lösung der folgenden Aufgabe:

Aufgabe:

Bitte erst diese Aufgabe lösen und dann weiterlesen.

1. Herleitung der Identität über die Implikation.
2. Herleitung der Negation über die Implikation.

Hinweis: Es hilft, $\neg a=1-a$ in einem Term zu benutzen.

Nicht weniger wichtig, für das Verständnis der Aussagelogik und der des "normalen" Sprachgebrauchs ist die Lösung dieser

Aufgabe:

Warum ist in der Aussagelogik

$\neg a\lor b$

1. eine asymmetrische Relation
2. eine Implikation mit der sprachlichen Aussage: "wenn a, dann b."

Es genügt, jeweils die Wahrheitstabelle entsprechend zu kommentieren.

Beide Aufgaben hängen mit den bereits erwähnten Hornformeln zusammen. Ihre Antworten zeigen, dass die einzige "Konstante" in der hier hergeleiteten Aussagelogik die Bezugsmenge M ist.

Die bereits bekannte Tabelle

S	P	Beträge der möglichen Verknüpungen
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
Nr.		0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
Form			i	o											a	e

wird hier noch einmal benötigt. Die Verknüpfungen (n Zukunft auch "binäre Funktionen" oder einfach "Funktionen" genannt) an den Positionen 0 und 15 wurden bereits über die Kontradiktion und die Tautologie hergeleitet. Um die noch fehlenden Funktionen herzuleiten, müssen noch 5 weitere bestimmt werden.

Aufgabe:

Warum genügen nur 4 Funktionen um die Tabelle zu füllen?

Die Identitäten

Es sind tatsächlich zwei Identitätsfunktionen vorhanden. Weil alle Funktionen in der Tabelle binär erklärt sind (sie haben stets zwei Argumente), muss es je eine Identität pro Argument geben. Die Positionen sind

• Nr. 3 für die S-Identität.
• Nr. 5 für die P-Identität.

Der Ansatz für die S-Identität - I(S) - sei

$I(S):=\left(P\land \neg P\right)\lor S$

Das Argument P wird in eine Kontradiktion eingebettet und liefert stets 0. Dieser Wert ist das neutrale Element der Disjunktion, womit nun erreicht ist, dass die Funktion vereinfacht werden kann zu

$I(S):=0\lor S$

Weil alle Funktionen als Implikation (Hornklausel) formuliert werden sollen, muss das erste Argument in negierter Form vorhanden sein. Das ist mit

$I(S):={\boldsymbol {\neg 1}}\lor S$

schnell gemacht. Mit dem Implikationsoperator lautet die Identität von S also einfach

$I(S):=1\Rightarrow S\$

Für jede Identität I(a) gilt:

Aus 1 folgt a.

Nun sind auch die Funktionen Nr. 3 und Nr. 5 geklärt. Es handelt sich um die Identitätsfunktionen der Operanden.

Die Negationen

Wenn es für jeden Operanden eine Identitätsfuntion gibt, dann muss es auch für jeden eine Negation geben. Die Negation des Operanden S ist mit der Funktion Nr. 12 schnell gefunden. Die Formulierung lautet

$\neg S:=\neg I(S):=\neg \left(\left(P\land \neg P\right)\lor S\right)$

Nach Auflösung der der Klammern und ein wenig "De Morgan" ergibt sich

$\neg S:=\neg S\lor 0:=S\Rightarrow 0$

Für jede Negation $\neg a$ gilt:

Aus a folgt 0.

Die Negation des P-Operanden ist Funktion Nr. 10.

Die Implikationen

Auch hier gibt es deren zwei. Es sollte leicht zu verstehen sein, denn wenn aus S P folgt, dann muss es auch möglich sein, dass aus P S folgt. Die Funktion Nr. 13 ist ja die Implikation

$S\Rightarrow P\$

Nr. 11 ist die gesuchte Funktion

$P\Rightarrow S\$

Damit die Tabelle auch für die Formen vollständig ist, muss in Spalte 11 ebenfalls die a-Form eingetragen werden.

Die Inhibitionen

Bekanntlich ist die Verneinung der Implikation eine Inhibition. Allgemein formuliert:

$\neg \left(S\leq P\right)\equiv \left(S>P\right)$

Damit ist die Funktion Nr. 4 geklärt. Es handelt sich hier ebenfalls um eine o-Form, die aus der Negation der Implikation an Position 11 entsteht. Die Relation lautet

$P>S\$

Die Antivalenz

Die Gleichheit wurde bereits angesprochen (siehe "Was ist Gleichheit?"). Es handelt sich um die konjunktive Verknüpfung der Mengenrelationen

$\left(A=B\right)\Leftrightarrow \neg \left(A\subset B\right)\land \neg \left(B\subset A\right)$

Die Verneinung der Gleichheit ist die Antivalenz. Im vorliegenden Fall also

$\left(A\neq B\right)\Leftrightarrow \left(A\subset B\right)\lor \left(B\subset A\right)$

Weil die beteiligten Mengen bereits normiert wurden, ihre Beträge sind stets entweder 0 oder 1, kann die Gleichheit auch als

$\left(a\neq b\right)\Leftrightarrow \left(a<b\right)\lor \left(b<a\right)$

Die Größenrelation "kleiner" ist auch die Konjunktion je eines "normalen" und eines negierten Opearnden formulierbar. Um bei den Syllogismen zu bleiben: es ist die o-Form. Die o-Form ist die Verneinung der a-Form, die ja ihrerseits die Implikation verkörpert. Damit gilt

$\left(a\neq b\right)\Leftrightarrow \neg \left(a\leq b\right)\lor \neg \left(b\leq a\right)$

Ohne den Relationsoperator zu verwenden ergibt sich

$\left(a\neq b\right)\Leftrightarrow \neg \left(\neg a\lor b\right)\lor \neg \left(\neg b\lor a\right)$

Nach Negation der beiden Terme ergibt sich die bekannte Formulierung

$\left(a\neq b\right)\Leftrightarrow \left(a\land \neg b\right)\lor \left(b\land \neg a\right)$

Damit ist auch Funktion Nr. 6 abgeschlossen.

Die Äquivalenz

Die Negation der Antivalenz ist - wie bereits gezeigt - die Äquivalenz. Es genügt, nur die Formulierungen zu zeigen.

$\left(a=b\right)\Leftrightarrow \neg \left(\left(a\land \neg b\right)\lor \left(b\land \neg a\right)\right)$

$\left(a=b\right)\Leftrightarrow \left(\neg a\lor b\right)\land \left(\neg b\lor a\right)$

$\left(a=b\right)\Leftrightarrow \left(a\Rightarrow b\right)\land \left(b\Rightarrow a\right)$

Diese Relation wird auch als "genau dann wenn" oder einfach "gdw" bezeichnet. In der operativen Schreibweise

$\left(a\Leftrightarrow b\right)\Leftrightarrow \left(a\Rightarrow b\right)\land \left(b\Rightarrow a\right)$

Etwas viel "genau dann wenn", aber hier nicht zu vermeiden. Jedenfalls ist jetzt Funktion Nr. 9 erledigt.

Die Disjunktion

Die einfache Disjunktion ist unter Funktion Nr. 7 zu finden. Die dazugehörige Negation muss dann mit Nr. 8 gegeben sein. Es scheint keine Form (a, e, i, o) zu geben, aus der die Disjunktion einfach abzuleiten ist. Aber es ist eben nur Schein. Könnte die Reihenfolge der Ergebnisse von Funktion Nr. 14 "umgekehrt" werden, wäre die Disjunktion gegeben. Damit rückt die e-Form in den Fokus der Betrachtung. Dort war sie schon mal, denn PeM ist ja das Gleiche wie MeP.

Kann eine Relation die keine Gleichheit bzw. Ungleichheit feststellt denn überhaupt symmetrisch sein?

$AeB:=A\subseteq \neg B$

Werden die normierten Beträge der Mengen A und B mit a und b angenommen, gilt:

$f(a,b):=a\leq \neg b:=\neg a\lor \neg b$

Die Wahrheitstabelle zeigt, dass es sich tatsächlich um eine Disjunktion mit negierten Operanden handelt.

$a\$	$b\$	$\neg a\lor \neg b$	$a\lor b\$
$0\$	$0\$	$1\$	$0\$
$0\$	$1\$	$1\$	$1\$
$1\$	$0\$	$1\$	$1\$
$1\$	$1\$	$0\$	$1\$

Die Relation ist tatsächlich symmetrisch.

Es genügt also, die Operanden von Funktion Nr. 14 zu negieren, um die normale Disjunktion zu erhalten.

Hinweis: Die Disjunktion kann nicht als Hornklausel formuliert werden. Es fehlt ein negierter Operand.

Die Peirce-Funktion oder NOR

Die gleiche Vorgehensweise, wie sie für die Disjunktion angewebndet wurde, wird auch hier benutzt. Die Operanden der Funktion Nr. 1 werden negiert und die Spalte Nr. 8 ist das Ergebnis.

$a\$	$b\$	$a\land b$	$\neg a\land \neg b\$
$0\$	$0\$	$0\$	$1\$
$0\$	$1\$	$0\$	$0\$
$1\$	$0\$	$0\$	$0\$
$1\$	$1\$	$1\$	$0\$

Auch diese Operation ist symmetrisch,

Zwischenbilanz

Die Aussagelogik wurde erfolgreich über die einelementige Bezusmenge hergeleitet. Die Syllogismen bildeten die Basis und konnten ebenfalls mit der gleichen Bezugsmenge (Mittelbegriff) nschvollzogen werden. Die "fehlenden" Modi aus Figur-3 darapti, felapton und aus Figur-4 bamalip und fesapo sind nicht im System der Aussagelogik mit einelementiger Bezugesmenge enthalten, werden aber noch genau besprochen.

Alle 16 Funktionen der binären Booleschen Algebra wurden sowohl über die beteiligten Mengen und die Mengenalgebra, als auch über die äußeren Eigenschaften der Mengen (Mächtigkeiten) bestätigt. Die arithmetische Behandlung verwendete als Definitions- und Wertebereich ebenfalls nur die Mächtigkeit der Bezugsmenge.

Weil die Aussagelogik nicht nur aus binären Verknüpfungen besteht, sondern beliebig viele Operanden verknüpft werden können, müssen diese auch allgemein betrachtet werden. Der nächste Abschnitt wird sich also mit den "Normalformen" auseinandersetzen.

Normalformen

Grundsätzlich gibt es zwei Normalformen. Die disjunktive Normalform (DNF) und die konjunktive (KNF). Verschiedene Möglichkeiten existieren, die Normalformen zu bestimmen. Am übersichtlichsten ist wieder die Bestimmung über eine Wahrheitstabelle. Weil bisher viel von Arithmetik die Rede war soll auch sie für ein erstes Beispiel herangezogen werden.

Die Addition dient als Grundlage. Es wird nur die Summe einer Stelle ermittelt (also kein Übertrag), trotzdem wird der eventuelle Übertrag der vorherigen Stelle in die Addition einbezogen. Die beiden Summanden sind a und b, der Übertrag der vorangehenden Stelle ist c. Der $\oplus$-Operator verkörpert eine "modulo 2"-Addition, die sich ja aus der Aufgabenstellung ergibt.

$c\$	$b\$	$a\$	$a\oplus b\oplus c\$
$0\$	$0\$	$0\$	$0\$
$0\$	$0\$	$1\$	$1\$
$0\$	$1\$	$0\$	$1\$
$0\$	$1\$	$1\$	$0\$
$1\$	$0\$	$0\$	$1\$
$1\$	$0\$	$1\$	$0\$
$1\$	$1\$	$0\$	$0\$
$1\$	$1\$	$1\$	$1\$

Die Farben in der Ergebnisspalte dienen der Unterscheidung zwischen

• Disjunktiver  Normalform
• Konjunktiver Normalform

Ermitteln der disjunktiven Normalform

Die Vorgehensweise ist schematisch und zeigt bereits einen algorithmischen Charakter.

Für alle Zeilen der Wahrheitstabelle:

• Wenn in der Ergebnisspalte eine 1 steht,

dann

• Wenn in der Spalte des Operanden eine 0 steht,

dann negierten Operand übernehmen,

sonst Operand direkt übernehmen.

• Alle Operanden, negiert oder nicht, zu einem Konjunktionsterm zusammenfasen.

Alle Konjunktionsterme disjunktiv verknüpfen.

Die Konjunktionsterme sind also:

• $\neg c\land \neg b\land a$
• $\neg c\land b\land \neg a$
• $c\land \neg b\land \neg a$
• $c\land b\land a$

Die ganze DNF lautet somit

$a\oplus b\oplus c:=(\neg c\land \neg b\land a)\lor (\neg c\land b\land \neg a)\lor (c\land \neg b\land \neg a)\lor (c\land b\land a)$

Ermitteln der konjunktiven Normalorm

Die Vorgehensweise ist fast so, wie bei der DNF.

Für alle Zeilen der Wahrheitstabelle:

• Wenn in der Ergebnisspalte eine 0 steht,

dann

• Wenn in der Spalte des Operanden eine 1 steht,

dann negierten Operand übernehmen,

sonst Operand direkt übernehmen.

• Alle Operanden, negiert oder nicht, zu einem Disjunktionsterm zusammenfasen.

Alle Disjunktionsterme konjunktiv verknüpfen.

Die Disjunktionsterme sind also:

• $c\lor b\lor a$
• $c\lor \neg b\lor \neg a$
• $\neg c\lor b\lor \neg a$
• $\neg c\lor \neg b\lor a$

Die ganze KNF lautet also

$a\oplus b\oplus c:=(c\lor b\lor a)\land (c\lor \neg b\lor \neg a)\land (\neg c\lor b\lor \neg a)\land (\neg c\lor \neg b\lor a)$

Äquivalenz von DNF und KNF

Die Normalformern DNF und KNF sind äquivalent. Sie liefern also gleiche Ergebnisse bei gleichen Belegungen der Operanden. Die möglichen Belegungen sind über den Spalten der Wahrheitstabelle gegeben. Handelt es sich um eine signifikante Zeile (abhängig vom Inhalt der Ergebnisspalte und der Normalform), so ist das Ergebnis "wahr" oder eben 1. Es sollte also möglich sein, aus einer in DNF gegebenen Formel eine KNF zu machen und umgekehrt.

Achtung! In den folgenden Darstellungen handelt es sich bei $\bigvee _{}^{}$ und $\bigwedge _{}^{}$ nicht um Quantoren sondern um die Operatoren für Dis- und Konjunktion.

Allgemein gilt für jede DNF:

$D:=\bigvee _{i=1}^{n}\left(\bigwedge _{j=1}^{m}a_{i,j}\right)$

Für jede KNF gilt demnach:

$K:=\bigwedge _{i=1}^{n}\left(\bigvee _{j=1}^{m}a_{i,j}\right)$

Die antivalente Normalform

Es gibt eine weitere Normalform in der dualen Logik, die in letzter Zeit wieder in den Fokus rückt, die antivalente Normalform. Dabei handelt es sich um die konsequente Anwendung der bis jetzt hergeleiteten berechenbaren Logik. Der Mathematiker Iwan Shegalkin entwickelte 1928 einen entsprechenden Ansatz als Polynom. Für eine Funktion mit n Variablen (Argumenten) gilt:

$f(x_{1,...n})=a_{0}+\sum _{i=1}^{n}{a_{i}\cdot x_{i}}+\sum _{j=2}^{n}\sum _{i=1}^{j-1}{a_{ij}\cdot x_{i}\cdot x_{j}}+\sum _{k=3}^{n}\sum _{j=2}^{k-1}\sum _{i=1}^{j-1}{a_{ijk}\cdot x_{i}\cdot x_{j}\cdot x_{k}}+...+{a_{123...n}\cdot x_{1}\cdot x_{2}\cdot x_{3}\cdot ...\cdot x_{n}}$

Die von Shegalkin verwendete Addition ist modulo-2. Diese Operation ist eine symmetrische Relation der dualen Booleschen Algebra. Es handelt sich um die Antivalenz (xor-Verknüpfung). Deshalb werden die von Shegalkin entwickelten Polynome antivalente Normalform genannt. Sie ist nicht so bekannt wie die konjunktive oder disjunktive Normalform, bietet aber viel mehr Felxibiität, wie die folgenden Ausführungen zeigen.

Shegalkin-Polynome

Die gezeigten Polynome der antivalenten Normalform erfuhren eine entscheidende Weiterentwicklung sind durch die Arbeiten von Prof. Dr. Franke . Er verallgemeinerte die Shegalkin-Polynome zu rein arithmetischen Polynomen. Die Einsatzgebiete gehen nun weit über die von Franke betrachteten Gebiete, binäre und fuzzy Automatisierung, hinaus. Neueste Arbeiten auf der durch Franke erweiterten Basis reichen bis in die Gentechnik.

Aufbau

Alle Werte sind ganze Zahlen. Insbesondere gilt für die Koeffizienten

$a_{ijk...}\in \mathbb {Z} \;;i,j,k,...\in \mathbb {N}$.

Für die Variablen

$x_{i}\in \left\{0,1\right\}\;;i\in \mathbb {N}$.

Aus der Beschränkung für die Variablen folgt für deren Potenzierung

$x_{i}^{n}=x_{i}\;;i,n\in \mathbb {N}$

Damit ist Shegalkins Ansatz "multilinear", woraus sich die Polynome in der Form der antivalenten Normalform ergeben.

Prinzip

Wenn die Shegalkin-Polynome gülig sind, muss auch die Berechnung einer asymmetrischen Relation möglich sein. Deshalb wird hier die Implikation $x_{1}\rightarrow x_{2}\$ gezeigt.

Es ist $\left(x_{1}\rightarrow x_{2}\right)=\left(\neg x_{1}\lor x_{2}\right)$

Wegen Definitionsbereich = Wertebereich = $m=\left\{0,1\right\}\$ ist

$\neg x_{i}=\left(m\setminus x_{i}\right)\;;\ i\in \mathbb {N}$

Damit ist

$\left(x_{1}\rightarrow x_{2}\right)=\left(\neg x_{1}\lor x_{2}\right)=\left(\left(m\setminus x_{1}\right)\lor x_{2}\right)$

Aus den De Morganschen Gesetzen folgt

$\left(m\setminus x_{1}\right)\lor x_{2}=m\setminus \left({\left(m\setminus \left(m\setminus x_{1}\right)\right)}\land {\left(m\setminus x_{2}\right)}\right)$

Der $\oplus \$-Operator wird als Modulo-2-Addition (xor-Verknüpfung) verwendet. Die Konjunktion wird durch die arithmetische Multiplikation ersetzt, deren Gültigkeit ja bereits gezeigt wurde. Dadurch vereinfacht sich Ausdruck zu

$\left(m\setminus x_{1}\right)\lor x_{2}=m\setminus \left({\left(m\setminus \left(m\setminus x_{1}\right)\right)}\land {\left(m\setminus x_{2}\right)}\right)=a_{0}\oplus \left({\left(a_{0}\oplus \left(a_{0}\oplus x_{1}\right)\right)}\cdot {\left(a_{0}\oplus x_{2}\right)}\right)$

Die Herleitung des Shegalkin-Polynoms erfolgt nun über

$f(x_{1,2})=a_{0}\oplus \left({\left(a_{0}\oplus \left(a_{0}\oplus x_{1}\right)\right)}\cdot {\left(a_{0}\oplus x_{2}\right)}\right)$

$f(x_{1,2})=a_{0}\oplus \left({\left(a_{0}\oplus a_{0}\oplus x_{1}\right)}\cdot {\left(a_{0}\oplus x_{2}\right)}\right)$

$f(x_{1,2})=a_{0}\oplus \left(a_{0}^{2}\oplus a_{0}^{2}\oplus x_{1}\cdot a_{0}\oplus x_{2}\cdot a_{0}\oplus x_{2}\cdot a_{0}\oplus x_{1}\cdot x_{2}\right)$

$f(x_{1,2})=a_{0}\oplus a_{0}^{2}\oplus a_{0}^{2}\oplus x_{1}\cdot a_{0}\oplus x_{2}\cdot a_{0}\oplus x_{2}\cdot a_{0}\oplus x_{1}\cdot x_{2}$

Wegen $a_{0}=1\$ ist $a_{0}^{2}=a_{0}\$ folgt

$f(x_{1,2})=a_{0}\oplus a_{0}\oplus a_{0}\oplus x_{1}\cdot a_{0}\oplus x_{2}\cdot a_{0}\oplus x_{2}\cdot a_{0}\oplus x_{1}\cdot x_{2}$

$f(x_{1,2})=a_{0}\oplus a_{0}\oplus a_{0}\oplus x_{1}\oplus x_{2}\oplus x_{2}\oplus x_{1}\cdot x_{2}$

Der $\oplus \$ -Operator ist ein "Strichoperator", wie die herkömmliche Addition. Seine wiederholte Anwendung kommt also einer Bündelung im Sinne eines "Punktoperators" gleich. Für den hier eingeführten $\odot \$-Operator werden diese Eigenschaften erst einmal angenommen. Unter dieser Annahme gilt:

$f(x_{1,2})=\left(a_{0}\oplus a_{0}\oplus a_{0}\right)\oplus x_{1}\oplus \left(x_{2}\oplus x_{2}\right)\oplus x_{1}\cdot x_{2}=3\odot a_{0}\oplus x_{1}\oplus 2\odot x_{2}\oplus x_{1}\cdot x_{2}$

Um die angenommenen Eigenschaften des $\odot \$-Operators zu festigen, muss die Modulo-2-Addition berücksichtigt werden. Es gilt:

$n\mod 2={\begin{cases}0,&{\text{wenn }}n{\text{ gerade}}\\1,&{\text{wenn }}n{\text{ ungerade}}\end{cases}}$

So ergibt sich abschließend, mit 0 als neutralem Element der $\oplus \$-Operation:

$f(x_{1,2})=3\odot a_{0}\oplus x_{1}\oplus 2\odot x_{2}\oplus x_{1}\cdot x_{2}=1\odot a_{0}\oplus x_{1}\oplus 0\odot x_{2}\oplus x_{1}\cdot x_{2}=a_{0}\oplus x_{1}\oplus x_{1}\cdot x_{2}$

Arithmetisierung nach Franke

In logischen Schaltkreisen wird der Übergang von 0 nach 1 oder umgekehrt oft als sprunghaft angesehen. Diese Sichtweise ist aber keineswegs zwingend, womit auch eine lineare Betrachtung der Negation zulässig ist. Die beiden Versionen zeigt die folgende Abbildung für gleiche Zeiten (horizontal).

Sprunghaft	Linear

Der lineare Verlauf bildet die Grundlage der allgemeinen Arithmetisierung nach Franke. In beiden Fällen sind Anfangs- und Endzustand gleich. der Unterschied besteht nur im Übergang selbst.

Der 1-0-Übergang

Hier ist die Geradengleichung der Form

$f(x)=m\cdot x+b$

vorhanden. Sie kann auch als Polynom zu

$f(x)=a_{0}+a_{1}\cdot x$

formuliert werden.

Die Bestimmung der Koeffizienten $a_{0}\;,a_{1}\$ erfolgt über eine Kombination aus Wahrheitstabelle und Gleichungssystem. Die Negation hat die Wahrheitstabelle

x	y
0	1
1	0

Der lineare 1-0-Übergang wird durch $y=a_{0}+a_{1}\cdot x$. Zur Bestimmung der Koeffizienten ergibt sich das Gleichungssystem:

$a_{0}+a_{1}\cdot x^{\left(0\right)}=y^{\left(0\right)}\ \ {\text{ mit Zeile-0}}\ \ a_{0}+a_{1}\cdot {0}={1}$

$a_{0}+a_{1}\cdot x^{\left(1\right)}=y^{\left(1\right)}\ \ {\text{ mit Zeile-1}}\ \ a_{0}+a_{1}\cdot {1}={0}$

Die hochgestellten Indizes bezeichnen die Zeilennummern der Wahrheitstabelle. Die Lösung des Gleichungssystems liefert $a_{0}=1\$ und $a_{1}=-1\$. Dieser Ansatz wird auf alle unären Funktionen der dualen Booleschen Algebra erweitert.

Unäre Funktionen

In der Aussagenlogik existieren vier unäre Funktionen. Es sind Identitität, Negation, Tautologie und Kontradiktion. Die Negation in ihrer linearen Interpretation lieferte den gezeigten Ansatz. Franke verallgemeinerte zunächst diese vier Funktionen in Matrix/Vektor-Schreibweise zu

${\begin{pmatrix}1&0\\1&1\end{pmatrix}}\cdot {\begin{pmatrix}a_{0}\\a_{1}\end{pmatrix}}={\begin{pmatrix}y^{\left(0\right)}\\y^{\left(1\right)}\end{pmatrix}}$

Durch Invertierung der Matrix ergibt sich der Lösungsvektor ${\vec {a}}\$ aus

${\begin{pmatrix}a_{0}\\a_{1}\end{pmatrix}}={\begin{pmatrix}y^{\left(0\right)}\\y^{\left(1\right)}\end{pmatrix}}\cdot {\begin{pmatrix}1&0\\1&1\end{pmatrix}}^{-1}={\begin{pmatrix}y^{\left(0\right)}\\y^{\left(1\right)}\end{pmatrix}}\cdot {\begin{pmatrix}1&0\\-1&1\end{pmatrix}}$

Damit ergeben sich die einzelnen Komponenten des Vektors aus

$a_{0}=y^{\left(0\right)}\$

$a_{1}=-y^{\left(0\right)}+y^{\left(1\right)}\$

Damit stehen die unären Funktionen fest. Ausgedrückt über die Frankschen- Polynome:

• Kontradiktion

x	y
0	0
1	0

$y=f(x)=a_{0}+a_{1}\cdot x=y^{\left(0\right)}+\left(-y^{\left(0\right)}+y^{\left(1\right)}\right)\cdot x=0+\left(-0+0\right)\cdot x=0$

• Identität

x	y
0	0
1	1

$y=f(x)=a_{0}+a_{1}\cdot x=y^{\left(0\right)}+\left(-y^{\left(0\right)}+y^{\left(1\right)}\right)\cdot x=0+\left(-0+1\right)\cdot x=x$

• Negation

x	y
0	1
1	0

$y=f(x)=a_{0}+a_{1}\cdot x=y^{\left(0\right)}+\left(-y^{\left(0\right)}+y^{\left(1\right)}\right)\cdot x=1+\left(-1+0\right)\cdot x=1-x$

• Tautologie

x	y
0	1
1	1

$y=f(x)=a_{0}+a_{1}\cdot x=y^{\left(0\right)}+\left(-y^{\left(0\right)}+y^{\left(1\right)}\right)\cdot x=1+\left(-1+1\right)\cdot x=1$

Es besteht eine große Ähnlichkeit zu den Shegalkin-Polynomen. Jedoch ist bei Franke die Addition arithmetisch und nicht modulo-2, wie bei Shegalkin. Abschließend ergibt sich mit der Matrix (der hochgestellte Index meint hier die Anzahl der Variablen)

$\Psi ^{\left(1\right)}={\begin{pmatrix}1&0\\1&1\end{pmatrix}}$

für alle unären Funktionen

${\vec {a}}={\vec {y}}\cdot \left(\Psi ^{\left(1\right)}\right)^{-1}$.

Binäre Funktionen

Der Ansatz erfolgt wieder über die Kombination aus Wahrheitstabelle und Gleichungssystem.

$x_{2}\$	$x_{1}\$	$y\$
$0\$	$0\$	$y^{\left(0\right)}\$
$0\$	$1\$	$y^{\left(1\right)}\$
$1\$	$0\$	$y^{\left(2\right)}\$
$1\$	$1\$	$y^{\left(3\right)}\$

Die Gleichung folgt aber einem bilinearen Ansatz der Form

$y=a_{0}+a_{1}\cdot x_{1}+a_{2}\cdot x_{2}+a_{12}\cdot x_{1}\cdot x_{2}$

Franke folgt auch hier der Arbeit Shegalkins, vermeidet aber wieder die Modulo-2-Addition. Mit der Tabelle ergeben sich für die Bestimmung der Koeffizienten folgende Gleichungen:

$a_{0}+a_{1}\cdot x_{1}^{\left(0\right)}+a_{2}\cdot x_{2}^{\left(0\right)}+a_{12}\cdot x_{1}^{\left(0\right)}\cdot x_{2}^{\left(0\right)}=y^{\left(0\right)}\$

$a_{0}+a_{1}\cdot x_{1}^{\left(1\right)}+a_{2}\cdot x_{2}^{\left(1\right)}+a_{12}\cdot x_{1}^{\left(1\right)}\cdot x_{2}^{\left(1\right)}=y^{\left(1\right)}\$

$a_{0}+a_{1}\cdot x_{1}^{\left(2\right)}+a_{2}\cdot x_{2}^{\left(2\right)}+a_{12}\cdot x_{1}^{\left(2\right)}\cdot x_{2}^{\left(2\right)}=y^{\left(2\right)}\$

$a_{0}+a_{1}\cdot x_{1}^{\left(3\right)}+a_{2}\cdot x_{2}^{\left(3\right)}+a_{12}\cdot x_{1}^{\left(3\right)}\cdot x_{2}^{\left(3\right)}=y^{\left(3\right)}\$

Die resultierende Koeffizientenmatrix (hochgestellt wieder die Anzahl der Variablen) ist

$\Psi ^{\left(2\right)}={\begin{pmatrix}1&0&0&0\\1&1&0&0\\1&0&1&0\\1&1&1&1\end{pmatrix}}$

Dem System lassen sich drei Vektoren

${\vec {a}}^{T}=\left(a_{0},a_{1},a_{2},a_{12}\right)$

${\vec {y}}^{T}=\left(y^{\left(0\right)},y^{\left(1\right)},y^{\left(2\right)},y^{\left(3\right)}\right)$

${{\vec {\phi }}_{\left(x\right)}}^{T}=\left(1,x_{1},x_{2},x_{1}\cdot x_{2}\right)$

entnehmen.

Als Nachweis der Funktionsfähigkeit sollen hier genügen

• Disjunktion

$x_{2}\$	$x_{1}\$	$y\$
$0\$	$0\$	$0\$
$0\$	$1\$	$1\$
$1\$	$0\$	$1\$
$1\$	$1\$	$1\$

$y=f(x_{1},\,x_{2})=a_{0}+a_{1}\cdot x_{1}+a_{2}\cdot x_{2}+a_{12}\cdot x_{1}\cdot x_{2}=0+1\cdot x_{1}+1\cdot x_{2}+-1\cdot x_{1}\cdot x_{2}=x_{1}+x_{2}-x_{1}\cdot x_{2}$

• Antivalenz

$x_{2}\$	$x_{1}\$	$y\$
$0\$	$0\$	$0\$
$0\$	$1\$	$1\$
$1\$	$0\$	$1\$
$1\$	$1\$	$0\$

$y=f(x_{1},\,x_{2})=a_{0}+a_{1}\cdot x_{1}+a_{2}\cdot x_{2}+a_{12}\cdot x_{1}\cdot x_{2}=0+1\cdot x_{1}+1\cdot x_{2}+-2\cdot x_{1}\cdot x_{2}=x_{1}+x_{2}-2\cdot x_{1}\cdot x_{2}$

Es besteht wieder die starke Ähnlichkeit zu den Shegalkin-Polynomen. Der bilineare Ansatz ist erweiterbar auf eine beliebige Anzahl von Variablen.

Allgemeine Koeffizientenmatrix

Die Koeffizientenmatrix $\Psi ^{\left(n\right)}$ kann direkt aus der Wahrheitstabelle ermittelt werden. Die 1-Positionen prinzipiell durch die Bitkombinationen der dual kodierten Zeilennummern bestimmt. Dabei sind die Potenzmengen der 1-Bits ausschlaggebend. Hier der Aufbau für drei Variablen:

Zeile	3	2	1	Potenzmenge	1-Positionen
$0\$	0	0	0	$\left\{\left\{\right\}\right\}\$	$0\$
$1\$	0	0	1	$\left\{\left\{\right\},\left\{2^{0}\right\}\right\}\$	$0,1\$
$2\$	0	1	0	$\left\{\left\{\right\},\left\{2^{1}\right\}\right\}\$	$0,2\$
$3\$	0	1	1	$\left\{\left\{\right\},\left\{2^{0}\right\},\left\{2^{1}\right\},\left\{2^{0},2^{1}\right\}\right\}\$	$0,1,2,3\$
$4\$	1	0	0	$\left\{\left\{\right\},\left\{2^{2}\right\}\right\}\$	$0,4\$
$5\$	1	0	1	$\left\{\left\{\right\},\left\{2^{0}\right\},\left\{2^{2}\right\},\left\{2^{0},2^{2}\right\}\right\}\$	$0,1,4,5\$
$6\$	1	1	0	$\left\{\left\{\right\},\left\{2^{1}\right\},\left\{2^{2}\right\},\left\{2^{1},2^{2}\right\}\right\}\$	$0,2,4,6\$
$7\$	1	1	1	$\left\{\left\{\right\},\left\{2^{0}\right\},\left\{2^{1}\right\},\left\{2^{0},2^{1}\right\},\left\{2^{2}\right\},\left\{2^{0},2^{2}\right\},\left\{2^{1},2^{2}\right\},\left\{2^{0},2^{1},2^{2}\right\}\right\}\$	$0,1,2,3,4,5,6,7\$

In dieser Tabelle sind alle wesentlichen Informationen für das Gleichungssystem enthalten. Die Spalten neben der Zeilennummer enthalten die entsprechenden Bits. Aus deren Stellen können die Indizes für Variablen x und Koeffizienten a direkt entnommen werden. Die 1-Elemente k der Matrix werden durch die Spalten "Zeile" z und "1-Positionen" s über $k_{\left(k+1\right)\left(s+1\right)}$ zugeordnet.

Eigenschaften der Koeffizientenmatrix

Die Matrix $\Psi \$ hat bemerkenswerte Eigenschaften. Es ist untere Dreiecksform vorhanden und die die Hauptdiagonale ist mit 1 besetzt. Damit ist sie regulär und es existiert eine Inverse.

Derartige Matrizen definieren bijektive lineare Abbildungen. Daraus folgt, dass alle logische Funktionen als bijektiven linearen Abbildung aufgefasst werden können. Bild- und Urbildraum sind dabei gleich $\left[0,1\right]^{2}\$. Die Addition und die Multiplikation sind so formuliert, dass diese Menge einen Vektorraum bildet.

Aufbau der Koeffizientenmatrix

Der Matrizenaufbau über Potenzmengen ist rekursiv. Genau betrachtet ergibt sich ein alternativer Aufbau das Kronecker-Produkt.

Eine Matrix für zwei Variablen ergibt sich mit

$\Psi ^{\left(2\right)}={\begin{pmatrix}1&0&0&0\\1&1&0&0\\1&0&1&0\\1&1&1&1\end{pmatrix}}={\begin{pmatrix}{\boldsymbol {1}}\cdot {\begin{pmatrix}1&0\\1&1\end{pmatrix}}&{\boldsymbol {0}}\cdot {\begin{pmatrix}1&0\\1&1\end{pmatrix}}\\\\{\boldsymbol {1}}\cdot {\begin{pmatrix}1&0\\1&1\end{pmatrix}}&{\boldsymbol {1}}\cdot {\begin{pmatrix}1&0\\1&1\end{pmatrix}}\end{pmatrix}}$

Der Aufbau aus $\Psi ^{\left(1\right)}={\begin{pmatrix}1&0\\1&1\end{pmatrix}}$ , sowohl als subMatrix als auch als skalare Elemente (fett) ist gegeben. Allgemein gilt:

$\Psi ^{\left(2\right)}={\begin{pmatrix}\Psi _{11}^{\left(1\right)}\cdot \Psi ^{\left(1\right)}&\Psi _{12}^{\left(1\right)}\cdot \Psi ^{\left(1\right)}\\\Psi _{21}^{\left(1\right)}\cdot \Psi ^{\left(1\right)}&\Psi _{22}^{\left(1\right)}\cdot \Psi ^{\left(1\right)}\end{pmatrix}}={\begin{pmatrix}\Psi _{11}^{\left(1\right)}\cdot {\begin{pmatrix}\Psi _{11}^{\left(1\right)}&\Psi _{12}^{\left(1\right)}\\\Psi _{21}^{\left(1\right)}&\Psi _{22}^{\left(1\right)}\end{pmatrix}}&\Psi _{12}^{\left(1\right)}\cdot {\begin{pmatrix}\Psi _{11}^{\left(1\right)}&\Psi _{12}^{\left(1\right)}\\\Psi _{21}^{\left(1\right)}&\Psi _{22}^{\left(1\right)}\end{pmatrix}}\\\\\Psi _{21}^{\left(1\right)}\cdot {\begin{pmatrix}\Psi _{11}^{\left(1\right)}&\Psi _{12}^{\left(1\right)}\\\Psi _{21}^{\left(1\right)}&\Psi _{22}^{\left(1\right)}\end{pmatrix}}&\Psi _{22}^{\left(1\right)}\cdot {\begin{pmatrix}\Psi _{11}^{\left(1\right)}&\Psi _{12}^{\left(1\right)}\\\Psi _{21}^{\left(1\right)}&\Psi _{22}^{\left(1\right)}\end{pmatrix}}\end{pmatrix}}$

Die Multiplikation führt dann zu

$\Psi ^{\left(2\right)}={\begin{pmatrix}\Psi _{11}^{\left(1\right)}\cdot \Psi _{11}^{\left(1\right)}&\Psi _{11}^{\left(1\right)}\cdot \Psi _{12}^{\left(1\right)}&\Psi _{12}^{\left(1\right)}\cdot \Psi _{11}^{\left(1\right)}&\Psi _{12}^{\left(1\right)}\cdot \Psi _{12}^{\left(1\right)}\\\Psi _{11}^{\left(1\right)}\cdot \Psi _{21}^{\left(1\right)}&\Psi _{11}^{\left(1\right)}\cdot \Psi _{22}^{\left(1\right)}&\Psi _{12}^{\left(1\right)}\cdot \Psi _{21}^{\left(1\right)}&\Psi _{12}^{\left(1\right)}\cdot \Psi _{22}^{\left(1\right)}\\\Psi _{21}^{\left(1\right)}\cdot \Psi _{11}^{\left(1\right)}&\Psi _{21}^{\left(1\right)}\cdot \Psi _{12}^{\left(1\right)}&\Psi _{22}^{\left(1\right)}\cdot \Psi _{11}^{\left(1\right)}&\Psi _{22}^{\left(1\right)}\cdot \Psi _{12}^{\left(1\right)}\\\Psi _{21}^{\left(1\right)}\cdot \Psi _{21}^{\left(1\right)}&\Psi _{21}^{\left(1\right)}\cdot \Psi _{22}^{\left(1\right)}&\Psi _{22}^{\left(1\right)}\cdot \Psi _{21}^{\left(1\right)}&\Psi _{22}^{\left(1\right)}\cdot \Psi _{22}^{\left(1\right)}\end{pmatrix}}={\begin{pmatrix}1\cdot 1&1\cdot 0&0\cdot 0&0\cdot 0\\1\cdot 1&1\cdot 1&0\cdot 0&0\cdot 0\\1\cdot 1&1\cdot 0&1\cdot 1&1\cdot 0\\1\cdot 1&1\cdot 1&1\cdot 1&1\cdot 1\end{pmatrix}}={\begin{pmatrix}1&0&0&0\\1&1&0&0\\1&0&1&0\\1&1&1&1\end{pmatrix}}$

Für alle Generationen $g>1\$ gilt:

$\Psi ^{\left(g\right)}={\begin{pmatrix}\Psi _{11}^{\left(1\right)}\cdot \Psi ^{\left(g-1\right)}&\Psi _{12}^{\left(1\right)}\cdot \Psi ^{\left(g-1\right)}\\\Psi _{21}^{\left(1\right)}\cdot \Psi ^{\left(g-1\right)}&\Psi _{22}^{\left(1\right)}\cdot \Psi ^{\left(g-1\right)}\end{pmatrix}}$

Aufbau der inversen Matrix

Auch die inverse Matrix ist selbstähnlich. Statt zwei müssen aber drei Untermatrizen beachtet werden.

Die kleinste invertierte Matrix ergibt sich aus dem Gleichungssystem der unären Funktionen mit

$\left(\Psi ^{\left(1\right)}\right)^{-1}={\begin{pmatrix}1&0\\-1&1\end{pmatrix}}$

Das ist die erste Untermatrix für Funktionen mit mehreren Variablen. Die zweite Untermatrix ergibt sich aus

$-1\cdot \left(\Psi ^{\left(1\right)}\right)^{-1}=-1\cdot {\begin{pmatrix}1&0\\-1&1\end{pmatrix}}={\begin{pmatrix}-1&0\\1&-1\end{pmatrix}}$

Auch hier ergibt sich der rekursive wieder Aufbau über das Kronecker-Produkt. Für alle Generationen $g>1\$ gilt:

$\left(\Psi ^{\left(g\right)}\right)^{-1}={\begin{pmatrix}\left(\left(\Psi ^{\left(1\right)}\right)^{-1}\right)_{11}\cdot \left(\Psi ^{\left(g-1\right)}\right)^{-1}&\left(\left(\Psi ^{\left(1\right)}\right)^{-1}\right)_{12}\cdot \left(\Psi ^{\left(g-1\right)}\right)^{-1}\\\left(\left(\Psi ^{\left(1\right)}\right)^{-1}\right)_{21}\cdot \left(\Psi ^{\left(g-1\right)}\right)^{-1}&\left(\left(\Psi ^{\left(1\right)}\right)^{-1}\right)_{22}\cdot \left(\Psi ^{\left(g-1\right)}\right)^{-1}\end{pmatrix}}$

Selbstähnlichkeit

Das Verhältnis von 1-Elementen zu allen Elementen der Koeffizientenmatrix ist stets ${\frac {3}{4}}\$. Diese Konstante ist auch im Sierpinski Dreieck vorhanden. Bei jedem Iterationsschritt verringert sich die Fläche um den Faktor ${\frac {3}{4}}\$, weshalb das Sierpinski Dreieck die Fläche 0 (Null) anstrebt.

Das Sierpinski Dreieck hat große Ähnlichkeit mit dem Pascalschen Dreieck. wird allein die Parität der Elemente im Pascalschen Dreieck betrachtet, ergibt sich das selbstähnliche Sierpinski Dreieck. Diese Selbstähnlichkeit resultiert aus der Kombinatorik. Letzterer sind auch die Elemente der Koeffizientenmatrix $\Psi ^{\left(g\right)}\$ unterworfen. Die Koeffizientenmatrix kann auch einem Pascalschen Dreieck entnommen werden.

Das folgende Sierpinski Dreieck entspricht einer Koeffizientenmatrix für 64 Variablen. Dabei entspricht ein schwarzer Punkt einer 1. Das gleichseitige Dreieck müsste noch in ein rechtwinkliges gewandelt werden, dass die Hypotenuse der Diagonalen des umgebenden Quadrats entspricht.

Der Aufbau noch einmal detailliert. Die einzelnen Zellen sind der Indizierung von Matrizen unterworfen:

$D={\begin{pmatrix}{\boldsymbol {1}}&8&36&120&330&792&1734&3468\\{\boldsymbol {1}}&{\boldsymbol {7}}&28&84&210&462&924&1734\\{\boldsymbol {1}}&6&{\boldsymbol {21}}&56&126&252&462&792\\{\boldsymbol {1}}&{\boldsymbol {5}}&{\boldsymbol {15}}&{\boldsymbol {35}}&70&126&210&330\\{\boldsymbol {1}}&4&10&20&{\boldsymbol {35}}&56&84&120\\{\boldsymbol {1}}&{\boldsymbol {3}}&6&10&{\boldsymbol {15}}&{\boldsymbol {21}}&28&36\\{\boldsymbol {1}}&2&{\boldsymbol {3}}&4&{\boldsymbol {5}}&6&{\boldsymbol {7}}&8\\{\boldsymbol {1}}&{\boldsymbol {1}}&{\boldsymbol {1}}&{\boldsymbol {1}}&{\boldsymbol {1}}&{\boldsymbol {1}}&{\boldsymbol {1}}&{\boldsymbol {1}}\end{pmatrix}}\;;\ \ \Psi ^{\left(3\right)}={\begin{pmatrix}{\boldsymbol {1}}&0&0&0&0&0&0&0\\{\boldsymbol {1}}&{\boldsymbol {1}}&0&0&0&0&0&0\\{\boldsymbol {1}}&0&{\boldsymbol {1}}&0&0&0&0&0\\{\boldsymbol {1}}&{\boldsymbol {1}}&{\boldsymbol {1}}&{\boldsymbol {1}}&0&0&0&0\\{\boldsymbol {1}}&0&0&0&{\boldsymbol {1}}&0&0&0\\{\boldsymbol {1}}&{\boldsymbol {1}}&0&0&{\boldsymbol {1}}&{\boldsymbol {1}}&0&0\\{\boldsymbol {1}}&0&{\boldsymbol {1}}&0&{\boldsymbol {1}}&0&{\boldsymbol {1}}&0\\{\boldsymbol {1}}&{\boldsymbol {1}}&{\boldsymbol {1}}&{\boldsymbol {1}}&{\boldsymbol {1}}&{\boldsymbol {1}}&{\boldsymbol {1}}&{\boldsymbol {1}}\end{pmatrix}}$

Für die Elemente der beiden Matrizen gilt die Berechugsvorschrift:

$d_{ik}=d_{i\left(k-1\right)}+d_{\left(i-1\right)k}\;;\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \psi _{ik}=\left(\psi _{i\left(k-1\right)}+\psi _{\left(i-1\right)k}\right)\mod 2$

Das Verfahren entspricht dem des Pascalschen Dreiecks. Indizes außerhalb der Grenzen führen zu "0-Elementen". Wird die Modulo- 2-Addition benutzt, ergibt sich die gewünschte Koeffizientenmatrix.

Interessant ist ebenfalls die Beziehung zu den zellulären Automaten, die von Toffoli und Wolfram eingehend untersucht wurden.

Interdisziplinäre Anwendungen

Neue Forschungsarbeiten bringen die Shegalkin Polynome mit der theoretischen Physik und der Gentechnik zusammen. Dabei werden mehrere Sierpinski Dreiecke zunächst in höherdimensionale Körper überführt und dann als einzelne Objekte zu einem größeren zusammengesetzt. Dadurch wird Komplexität reduziert und es entstehen neue Objekte mit ähnlichen aber erweiterten Eigenschaften.

Ein Beispiel aus der Gentechnik verwendet gleich die invertierte Koeffizientenmatrix als Tetraedergitter, um die redundante Codierung vieler Aminosäuren in der Doppelhelix zu erklären. Die Arbeiten hierzu sind beschrieben im "Open Wet Ware"-Wiki (Unverstität Manchester) unter "Set theoretical and algebraic model for redundancies in the genetic code" und als Abstract im PDF-Format hier.

Siehe auch

Aussagenlogik

Sierpinski Dreieck

Pascalschen Dreieck

Tetraederzahlen

Literatur

Autor	Titel	Verlag	Jahr	ISBN
Shegalkin	Die Arithmetisierung der symbolischen Logik	Mat. co.	1928
Franke	Sequentielle Systeme	Vieweg	1994	3-528-06527-3
Deiser	Einführung in die Mengenlehre	Springer	2002	3-540-42948-4
Ebbinghaus, Flum, Thomas	Einführung in die Mathematische Logik	Spektrum	2007	978-3-8274-1691-9
Schöning	Logik für Informatiker	Spektrum	1995	3-86025-684-X
Schöning	Theoretische Informatik - kuzgefasst	Spetrum	1995	3-86025-711-0
Basieux	Die Architektur der Mathematik	Rowohlt	2000	3-499-61119-8
Steinacker	Das kann doch nicht wahr sein	Hanser	2007	3-446-40715-4

wird fortgesetzt