Mathematische Logik mit Diagrammen - dr-dau.net · Venn modiﬁzierte Eulers System zu einem ausdrucksst¨arkeren System. Venn hat aber keinen Venn hat aber keinen Mechanismus bereitgestellt,

TU Dresden WS 2005Dr. Frithjof Dau

Mathematische Logik mit Diagrammen

Arbeitsunterlagen (kein Skript)

Frithjof Dau

Version vom 23. November 2005

ii

Inhaltsverzeichnis

1 A Short History of ... 3

1.1 Start . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2 Historische Systeme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2.1 Euler Kreise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2.2 Venn-Diagramme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.2.3 Venn-Peirce-Diagramme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.2.4 Freges Begriffsschrift . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.2.5 Peirces Existentielle Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.3 Zeitgenossiche Systeme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.3.1 Spider- und Contraints-Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.3.2 Begriffliche Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.4 Ubersicht . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.5 Literatur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2 Venn-Diagramme 11

2.1 Start . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.2 Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.3 Semantik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.4 Kalkul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.5 (Endliche) Vollstandigkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

2.6 Starke Vollstandigkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.7 Definierbare Mengensysteme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.8 Ein heterogenes System von Diagrammen und FOL-Formeln . . . . . . . . . . . . . . . 30

2.9 Probleme bei Hammer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

iii

INHALTSVERZEICHNIS 1

3 Techniken des Diagrammatic Reasoning (Bsp: Alpha-Graphen) 37

3.1 Was sind Diagramme? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3.1.1 2-Dimensionalitat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3.1.2 Klassifizierung der Zeichen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3.2 Problems with Existential Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

3.3 The First Approach to Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

3.4 Linear Representations of First Order Predicate Logic . . . . . . . . . . . . . . . . . . 46

3.5 The Second Approach to Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

2 INHALTSVERZEICHNIS

Kapitel 1

A Short History of ...

1.1 Start

Hammers Beispiel: Landkarte

Beispiele fur Diagramme in der Mathematik:

1. Graphen

2. Hasse-Diagramme

3. Kategorientheorie

Fokus in dieser Vorlesung: ‘Logik’.

Die heutige symbolische Logik hat ihren Anfang mit diagrammtischen Systemen! Spater –Beginn des20.ten Jahrhunderts– hat sich symbolische Logik durchgesetzt. Gute Ubersicht: Shin 1995.

1.2 Historische Systeme

In diesem Abschnitt sollen kurz einige historische Systeme vorgestellt werden.

1.2.1 Euler Kreise

• Von Euler (1707–1783) ca. 1762 entwickelt.

• Mengen werden durch Kreise dargestellt.

• Wenn eine Menge leer ist, dann wird die entsprechende Region im Diagramm weggelassen.

• Positiv: leicht lesbar und verstandlich

• Negativ: sehr geringe Ausdrucksstarke

3

4 KAPITEL 1. A SHORT HISTORY OF ...

Beispiel:

Tiger

KatzenHunde

• Jeder Tiger ist eine Katze, und

• keine Katze ist ein Hund (gleichbedeutend mit: kein Hund ist eine Katze)

1.2.2 Venn-Diagramme

• Von John Venn (1834–1923) ca. 1880 entwickelt.

• Jede Mengenkombination muß reprasentiert sein.

• Es werden nun Schattierungen benutzt, um leere Mengen anzuzeigen.

• Positiv: hohere Ausdrucksstarke

• Negativ: ‘Kombinatorische Explosion’, schlechtere Lesbarkeit

Katzen

Tiger

Hunde

Selbe Information wie bei Euler.

Wie soll man in Euler A ⊆ B ∪ C und B ∩ C = ∅ ausdrucken? Geht in Venn:

B

A

C

Mit Euler ginge das nur mit Kurven, die sich uberlappen (was man nicht als wohlgeformt ansieht):

A

BC

1.2. HISTORISCHE SYSTEME 5

Noch schwieriger: A ⊆ B, A ⊆ C und B ∩ C = ∅ (woraus A = ∅ folgt): Geht in Venn:

B

A

C

Geht uberhaupt nicht in Euler.

1.2.3 Venn-Peirce-Diagramme

• Charles Sanders Peirce (1839–1914) hat die Diagramme von Venn erweitert. Statt Schattierungenbenutzt er ein ‘o‘, und ein ‘X’ zeigt an, dass eine Menge nicht leer ist. Diese Symbole konnenmit Linien, die eine Dsijunktion darstellen, verbunden werden.

• Es gibt, obwohl sie Zeitgenossen warn, erstaunlicherweise keine Korrespondenz zwischen Peirceund Venn!

• Das Venn-Peirce-System wurde von Shin aufgegriffen.

Beispiel:Katzen

Tiger

Hunde

o

o

o

o

X

X

X o

Zusatzliche Information:

• Es gibt einen Hund oder einen Tiger, und

• es gibt eine Katze oder keinen Hund.

1.2.4 Freges Begriffsschrift

• Von Frege (1848–1925) um 1879 vorgestellt.

• Erste Formalisierung der heutigen Logik erster Stufe (mehr oder weniger)

• Die grundsatzlichen und philosophischen Betrachtungen von Frege zur Logik haben ihn zum‘Vater der modernen Logik’ gemacht. Richtungsweisend.

• Nachteile: Die Notation der Begriffsschrift ist schlecht lesbar und wurde außer von Frege vonniemanden benutzt.


• Anekdote: In den ‘Grundgesetzen der Arithmetik’ steckt ein Widerspruch. Aus Freges ’AxiomV’ folgt, dass jeder Begriff eine Extension hat, und ermoglicht damit die Russelsche Antinomie.Das efuhr Frege in einem Brief von Russell, als er gerade (am 16. Juni 1902) den zweiten Bandvom Druck abholte ...

Notation:

Die Beispielex

P(x)

s(x) x s(x)

P(x)

sagen aus: ‘jede Person ist sterblich’ bzw. es gibt eine sterbliche Person.

1.2.5 Peirces Existentielle Graphen

• Von Peirce ab Ende des 19.ten Jahrhunderts bis zu seinem Tod entwickelt.

• Drei Systeme:

– Alpha: Entspricht der heutigen Aussagenlogik– Beta: Entspricht (viel mehr als Freges Begriffsschrift) der heutigen Logik erster Stufe– Modale Logik, higher order logic, selbstreferentiell . . . Nie vollendet.

Beispiele fur Alpha:

Es ist kalt, es regnet, und es ist sturmisch:

it rains it is stormy it is cold

Es ist nicht wahr, das es regnet und kalt ist:

it rains it is cold

Wenn es regnet und sturmisch ist, dann ist es kalt:

it rains it is stormy it is cold

1.3. ZEITGENOSSICHE SYSTEME 7

Beispiel fur Beta: Es gibt einen Peterbilt, der ein trailer truck ist und jedee trailer truck hat 18 Rader:

has 18 wheels

trailer truckPeterbilt

trailer truck

Beispiel fur Gamma (modaler Teil): Du kannst ein Pferd zum Wasser fuhren, aber Du kannst es nichtzum Trinken bringen.

to

is a person is water

makes drink

is a horse

leads

1.3 Zeitgenossiche Systeme

Es gibt (aus meiner Sicht) zwei wesentliche Strange von zeitgenossischen, mathematisch ausgearbei-teten, diagrammtischen Logiksystemen. Diese beiden Strange sollen kurz vorgestellt werden.

1.3.1 Spider- und Contraints-Diagrams

• Herkunft: Formalisierung von UML (unified markup language)

• Formalisiert und erganzt Euler- und Venn-Diagramme

• Wird hauptsachlich von der ‘Visual Modelling Group’ unter der Leitung von John Howse an derUniversitat von Brighton erforscht.

• Andere Semantik als bei Venn-Peirce: Verschiedene Spider stehen ur verschiedene Elemente(unique name assumption).

Beispiel:B

A

C

Hier:


• B(∩C)\A enthalt genau ein Element a

• B\C enthalt mindestes ein Element b.

• A enthalt mindestens ein Element c, und wenn c in A ∩B liegt, dann ist A\B leer.

• a, b und c sind paarweise verschieden.

1.3.2 Begriffliche Graphen

• Herkunft: Peirce’s existentielle Graphen, wieder aufgegriffen von John Sowa.

• Einsatz in NLP und KR.

• Nicht genugend von Sowa formalisiert! Siehe dazu die Arbeiten von

– Chein/Mugnier et al

– Wille et al

• Homepage Sowa: www.jfsowa.com

Beispiele: Die Katze Yoyo sitzt auf einer Matte:

*onCAT: YoyoCAT: Yoyo MAT:

Tom glaubt, dass Mary einen Seemann heiraten will:

: *

SITUATION:marry SAILOR: *

PERSON: Tom believe

PROPOSITION:

PERSON: Mary want

1.4 Ubersicht

Venn Diagramme

Venn Peirce Diagramme

Peirces Existentielle Graphen

Euler Diagramme

Conceptual Graphs

>1880

1880

1772

Freges Begriffsschrift

>1890

historisch aktuell

Concept Graphs

ConstraintdiagramsSpider Diagrams

1879

1.5. LITERATUR 9

1.5 Literatur

Literatur:

• J. F. Sowa: MS514

• Gwen Kerdiles

• A Survey on based on Euler and Venn ...


Kapitel 2

Venn-Diagramme

Dieses Kapitel ist –bis auf leichte Modifikationen– dem Buch von Hammer ([Ha95]) entnommen. Esentspricht dem System Venn-I von Shin.

Die Vorgehensweise von Hammer ist nicht die, die ich wahlen wurde und fuhrt in der Tat zu einigenProblemen. Einige dieser Probleme sind durch Modifikationen der Arbeit von Hammer behoben, aberdurch die meines Erachtens falsche Vorgehensweise ist das nur ‘Flickschusterei’. In letzen Teilkapitelgehe auch die Probleme etwas genauer ein, und es wird an den entsprechenden Stellen im Text, wo inHammers Original Probleme auftauchen, auf dieses Teilkapitel verwiesen.

John Venn (1834–1923), englischer Mathematiker, Cambridge.Mehr als 30 Jahre Professor fur Logik und Naturphilosophie in Cambridge. Hat sich hauptsachlich mitLogik (unter dem Einfluss der Werke von Auguste de Morgan, George Boole und John Stuart Mill) undWahrscheinlichkeitstheorie beschaftigt. Hat 1880 mit den Venn-Diagrammen das System der Eulerkreiseweiterentwickelt.

2.1 Start

In Venn-Diagrammen werden Mengen durch geschlossene Linien dargestellt. Um beispielsweise dieMenge A darzustellen, zeichnen wir

A

Der Bereich (spater Region genannt) innerhalb des Kreises reprasentiert die Menge A, der Bereichaußerhalb des Kreises das Komplement von A.

Um zwei Mengen A und B darzustellen, zeichnen wir

A B

Der Bereich, wo sich die Kreise schneiden, reprasentiert A∩B, der halbmondformige Bereich innerhalbdes linken, aber außerhalb des rechten Kreises reprasentiert A\B, etc.

11

12 KAPITEL 2. VENN-DIAGRAMME

Es ist wichtig, dass in Venn-Diagrammen alle moglichen Kombinationen von Mengen reprasentiertwerden, ansonsten ist die Anordnung und Form der Linien, die Mengen darstellen, beliebig. Daslinke Diagramm ist eine andere mogliche Darstellung von A und B, die das mittlere und das rechteDiagramm hingegen sind keine Venn-Diagramme.1

B

A

,

BA

und

BA

Ab und zu bietet es sich an, das ‘Universe of Discourse’ durch ein Rahmenrechteck darzustellen. Also:Mit Rahmen:

Y

A B

Der Bereich im Rechteck, aber außerhalb der Kreise reprasentiert die Objekte, die weder in A noch inB liegen.

Um anzuzeigen, dass eine Menge nichtleer ist, wird das Zeichen X benutzt.

A B

X

A B

X

A B

X

Diese Diagramme bedeuten also:

1. ∃x : x ∈ A ∧ x ∈ B, also A ∩B 6= ∅.

2. ∃x : x ∈ A ∧ x /∈ B, also A\B 6= ∅.

3. ∃x : x /∈ A ∧ x /∈ B, also U\(A ∪B) 6= ∅ (wobei U fur ‘Universe (of Discourse)’ steht).

Mit einzelnen X-Zeichen kann nur dargestellt werden, dass ein minimaler Bereich nicht leer ist. Furgroßere Bereiche kann man die X-Zeichen mit Linien zu X-Folgen verbinden.

A B

X X

A B

X XX


1. ∃x : x ∈ A, also A ∩B 6= ∅.1Das mittlere und das rechte Diagramm sind aber Euler-Diagramme.

2.1. START 13

2. ∃x : x ∈ A ∨ x ∈ B, also A ∪B 6= ∅.

Um umgekehrt darustellen, dass ein Bereich leer ist, wird er schattiert.

A B A B


1. ∀x : x /∈ A\B ∧ ∀x : x /∈ B\A, also (A\B) ∪ (B\A) = ∅.

2. ∀x : x /∈ U\(A ∪B) ∧ ∀x : x /∈ A ∩B, also (A ∩B) ∪ U\(A ∪B) = ∅.

Alternativ kann man ein o in den Bereich eintragen. Also sind folgende Diagramme zu den beidenletzten gleichbedeutend:

A B

o o

A B

o

o

In Venn-Diagrammen sind beliebige Kombinationen von X-Folgen und Schattierungen erlaubt. Dasfolgende Diagramm ist also ein wohlgeformtes Venn-Diagramm.

A B

X X

X

X

X

X X

Zur Entwicklung des Systems:

1. Die wesentliche Autoren sind: Euler, Venn, Peirce (historisch) sowie Shin und Hammer (zeit-genosssisch).

2. Euler hat das System der Euler-Kreise entwickelt.

3. Venn modifizierte Eulers System zu einem ausdrucksstarkeren System. Venn hat aber keinenMechanismus bereitgestellt, mit dem existentielle Quantifikation ausgedruckt werden kann.

4. Peirce hat zu dem System X-Folgen hinzugefugt. Auch die noch folgenden Herleitungsregelngehen im wesentlichen auf ihn zuruck.

5. Shin hat 1995 ein eigenes Werk zu Venn-Diagrammen geschrieben, das sowohl die philosophischeund historische Aspekte der Diagramme untersucht, als auch den Versuch unternommen, Venn-Diagramme als formales System im heutigen Verstandnis zu definieren und zu untersuchen.

6. Hammer hat in einigen Arbeiten das System von Shin leicht modifiziert und erweitert. Unter-schied zu Shin: Einfuhrung von Bezeichnern (statt einer ‘counterpart’ relation bei Shin). DiesesSystem hat dieselbe Expressivitat wie das von Shin.


2.2 Syntax

Wir definieren als erstes formal die Menge der Bezeichnern.2

Definition 2.1 (Alphabet) Gegeben sei eine Menge {Ai | i ∈ N} von Bezeichnern. Wir werdenauch die Buchstaben aus dem Anfang des Alphabets, also A,B, C, fur Bezeichner benutzen.

Venn-Diagramme werden aus folgenden Bestandteilen zusammengesetzt:

1. Rechtecke. Innerhalb dieser Rechtecke werden alle weiteren Elemente eines Venn-Diagrammesgezechnet.

2. Geschlossene Kurven (doppelpunktfrei, differenzierbar, nicht notwendigerweise konvex).

3. Bezeichner, also Elemente des Alphabets.

4. Das Zeichen X.

5. Linien, um X-Zeichen zu verbinden.

6. Das Symbol o bzw. Schattierungen.

Um Venn-Diagramme zu definieren, muß zunachst der Begriff einer Region eingefuhrt werden.

Eine Basisregion ist entweder das gesamte Rechteck, oder der gesamte Bereich, der von einer ge-schlossenen Kurve eingeschlossen ist. Es werden nun Regionen wie folgt definert:

1. Jede Basisregion ist eine Region.

2. Ist r eine Region, so ist der Bereich innerhalb des Rechteckes, aber außerhalb von r, eine Region.Sie wird mit r bezeichnet.

3. Sind r und s zwei Regionen, die sich uberlappen, so ist der Bereich, wo sich r und s schneiden,auch eine Region. Sie wird mit r ∩ s bezeichnet.

4. Sind r und s zwei Regionen, so ist Zusammenfassung der Bereiche r und s eine Region. Sie wirdmit r ∪ s bezeichnet.

5. Sind r und s zwei Regionen, so ist der Bereich, der zu r, aber nicht zu s gehort, auch eine Region.Sie wird mit r − s bezeichnet.

6. Nichts anderes ist eine Region.

Teilregionen und echte Teilregionen werden kanonisch verstanden. Eine minimale Regionoder Zone ist eine Region, die keine echte Teilregion enthalt. Beispielsweise enthalt das folgendeDiagramm zwei Basisregionen A und B, vier Zonen und 16 Regionen.

A B

2Diese Definition taucht bei Hammer nicht auf. Das ist aber kein wirkliches Problem, sondern nur eine kleine, syn-taktische Lucke.

2.2. SYNTAX 15

Bevor wir Venn-Diagramme definieren, soll zunachst die Intuition vergestellt werden. Wie bereitserwahnt ist es wichtig, dass in Venn-Diagrammen alle moglichen Kombinationen von Mengen, alsoalle Regionen, reprasentiert werden. Wir haben bereits das Venn-Diagramm fur zwei Mengen A undB gesehen. Um eine dritte Menge C zu reprasentieren, muß eine entsprechende geschlossene Kurve zudem A,B-Diagramm hinzugefugt werden. In den beiden folgenden Diagrammen wurde das so getan,dass nicht alle Mengenkombinationen reprasentiert werden, weswegen sie keine Venn-Diagramme sind.

A B

C

A BC

Aus Grunden der Lesbarkeit fordern wir weiterhin, dass alle Regionen in Venn-Diagrammen konvexsind. Aus diesem Grund werden die folgenden Diagramme auch nicht als Venn-Diagramme akzeptiert.

A BC

A BC

Eine richtige Moglichkeit hingegen ist:

A B

C

Definition 2.2 (Venn-Diagramm) Venn-Diagramme werden wie folgt rekursiv definiert:

1. Jedes (unbezeichnete) Rechteck ist ein Venn-Diagramm, und zwar ohne Schattierungen oder X-Folgen.

2. Jedes (unbezeichnete) Rechteck, das eine geschlossene Kurve mit einem Bezeichner enthalt, istein Venn-Diagramm, und zwar ohne Schattierungen oder X-Folgen.

3. Ist D ein Venn-Diagramm ohne Schattierungen oder X-Folgen, so ist das Diagramm, das ausD durch Hinzufugen einer geschlossenen Kurve mit einem neuen Bezeichner, die gemaß der‘partial overlapping rule’ hinzugefugt wird, ein Venn-Diagramm. Die ‘partial overlapping rule’besagt, dass die neue Kurve einen echten Teil jeder Zone von D uberlappen muß, und das genaueinmal.3

4. Ist D ein Diagramm ohne Schattierungen oder X-Folgen, so durfen beliebige Zonen schattiertwerden (bzw., in beliebigen minimalen Regionen darf ein o eingefugt werden, wobei aber keineZone mehr als ein o enthalten darf).

3Hammer fordert weiterhin, dass die neue Kurve jede vorhandene Kurve genau zweimal schneiden muß. Aber dasvon ihm selbst angefuhrte Beispiel eines Diagrammes mit vier Kurven erfullt diese Anforderung nicht. Wichtig ist —und abgedeckt durch die Forderung, dass die neue Kurve jede Zone genau einmal uberlappt —, dass alle Regionenzusammenhangend sind. Siehe Teilkapitel 2.9.


5. Ist D ein Diagramm, dann darf eine X-Folge hinzugefugt werden. Dabei muß jedes X der Folgevollstandig in eine Zone fallen, aber keine Zone darf mehr als ein X der neuen Folge enthal-ten. Weiterhin erlauben wir keine Diagramme mit zwei X-Folgen, deren X-Symbole in genaudenselben minimalen Regionen liegen.

6. Sonst ist nichts ein Venn-Diagramm.

Es stellt sich nun die Frage: Gibt es fur jede (endliche) Anzahl von Mengen uberhaupt ein Venn-Diagramm, das diese Mengen darstellt? Antwort: Ja. More hat 1959 eine Prozedur vorgestellt, umVenn-Diagramme mit einer beliebigen (naturlich endlichen) Anzahl geschlossener Kurven zu konstru-ieren. Beispiel:

1b

2a

3b

3a4a

2b4b

1a

1b1a 2a

2b3a3b

4a4b

1a1b 1b

1a 2a2b

3a3b

4a4b

1a1b

Fur vier Mengen ergibt sich damit das folgende Diagramm:

Abbildung 2.1: Ein Venn-Diagramm fur vier Mengen

Wir haben bereits gesehen, dass es verschieden Moglichkeiten gibt, ein Diagramm zu zeichnen. Bei-spielsweise sind bei den folgenden Beispielen die die linke und die mittlere Zeichnung letzlich ver-schiedene Zeichnungen desselben Diagrammes (es liegt nur eine Anderung von Formen sowie eineAnderung der ‘Reihenfolge bei X-Folgen’ vor), wogegen die rechte Zeichnung ein anderes Diagrammdarstellt. Man sagt auch, dass die linke und die mittlere Zeichnung verschiedene Tokens (konkreteReprasentationen) desselben Typs (desselben ‘abstrakten’ Diagrammes) sind.4

C

B A

X

X

X

XX

C

A

B

X

X

X

XX

C

B A

X

X

X

o

4Diesem Gesichtspunkt von Diagrammen werden wir uns spater genauer zuwenden.

2.2. SYNTAX 17

Um zu erfassen, wann zwei Zeichnungen verschiedene Tokens desselben Diagrammes sind, fuhren wireine Gegenstuck-Relation zwischen den Regionen zweier Diagramme ein.

Definition 2.3 (Gegenstuck-Relation) Die Gegenstuck-Relation isi eine Aquivalenzrelationauf den Regionen, die wie folgt definiert ist:

1. Zwei Basisregionen sind Gegenstucke, wenn sie entweder beide Rechtecke sind, oder wenn beidegeschlossene Kurven sind, die den gleichen Bezeichner tragen, und

2. sind r, s zwei Regionen in einem Diagramm D und sind r′, s′ zwei Regionen in einem DiagramD′, und sind r und r′ bzw. s und s′ Gegenstucke, so sind auch r ∩ s und r′ ∩ s′ Gegenstucke,r ∪ s und r′ ∪ s′ sind Gegenstucke, und r und r′ sind Gegenstucke.

Es ist zu beachten, dass verschiedene Diagramme verschiedene Bezeichner haben konnen! Beispiel:

A B

C

A B

D

A B

• Die Region A ∩ B des linken Diagrammes besteht aus zwei minimalen Regionen. Sie hat einGegenstuck im mittleren Diagramm, das auch aus zwei minimalen Regionen besteht, und einGegenstuck im rechten Diagramm, das eine Zone ist.

• Die Region A ∩ C des linken Diagrammes hat kein Gegenstuck in den anderen Diagrammen.

Fur den Fall, dass zwei Diagramme dieselben Bezeichner haben, hat aber jede Region in einem Dia-gramm ein Gegenstuck im anderen Diagramm.

Wir sagen, dass eine Region r in einem Diagramm eine X-Folge hat, wenn das Diagramm eineX-Folge enthalt, so dass jede minimale Teilregion von r ein X dieser Folge enthalt, aber keine andereZone ein X der Folge enthalt.

Definition 2.4 (Verschiedene Zeichnungen desselben Diagrammes) Zwei gezeichnete Diagram-me sind gezeichnete Reprasentationen desselben Diagrammes, falls

1. sie dieselben Bezeichner haben,

2. wenn eine Region in einer Zeichnung genau dann schattiert ist, wenn ihr Gegenstuck in deranderen Zeichnung schattiert ist, und

3. eine Region genau dann eine X-Folge hat, wenn ihr Gegenstuck in der anderen Zeichnung eineX-Folge hat.

Man sagt auch, dass die Zeichnungen (aquivalente) Tokens desselben Typs sind.


2.3 Semantik

In diesem Teilkapitel wird die Semantik fur Venn-Diagramme eingefuhrt. Wir beginnen mit der Defi-nition der Modelle.

Definition 2.5 (Modell) Ein Modell ist ein Paar M := (U, I) (U : Universum, I: Interpretation),wobei I eine Abbildung ist, die jeder Region eine Teilmenge von U zuordnet, so dass gilt:

1. I(r) = U , wenn r eine Basisregion ist, die von einem Rechteck eingeschlossen ist,

2. I(r) = I(s), wenn r und s zwei Basisregionen in zwei (verschiedenen, sonst trivial) Diagrammensind, die denselben Bezeichner haben,

3. sind r und s Regionen in einem (!) Diagramm D, so gilt I(r∪s) = I(r)∪I(s), I(r∩s) = I(r)∩I(s)(falls r ∩ s eine Region ist, d.h., falls sich r und s uberlappen), und

4. ist r eine Region in einem Diagramm D, so gilt I(r) = U\I(r).

Da Basisregionen in veschiedenen Diagrammen auf dieselbe Teilmenge von D abgebildet werden, daRegionen aus Basisoperationen mit den Operationen r∪s, r∩s und r gebildet werden und da Modellediese Operationen erhalten, ist die Abbildung I unabhangig von Diagrammen. Genauer gilt folgendesLemma (das man Kanonisch uber den Aufbau von Regionen beweisen kann):

Lemma 2.6 (Interpretationen in Modellen hangen nicht von Diagrammen ab) Ist (U, I) einModell und sind zwei Regionen r, s Gegenstucke (in verschiedenen Diagrammen), so gilt I(r) = I(s).

Venn-Diagramme werden nun in Modellen zu ‘wahr’ oder ’falsch’ ausgewertet.

Definition 2.7 (Gultigkeit, Logische Konsequenz) Sei (U, I) ein Modell und D ein Diagramm.Wir sagen, dass D in (U, I) gultig ist und schreiben dafur (U, I) |= D, falls

1. I(r) 6= ∅ fur jede Region r von D gilt, die eine X-Folge hat, und

2. falls I(r) = ∅ fur jede schattierte Region r von D gilt.

Ist D ein Venn-Diagramm, so dass (U, I) |= D fur jedes Modell (U, I) gilt, so nennt man D (allge-mein)gultig. Ist D ein Venn-Diagramm, so dass (U, I) 6|= D fur jedes Modell (U, I) gilt, so nenntman D widerspruchlich. Ist D ein Venn-Diagramm, so dass (U, I) |= D fur ein Modell (U, I) gilt,so nennt man D erfullbar.

Sei ∆ eine Menge von Venn-Diagrammen und sei D ein Venn-Diagramm. Wir sagen, dass D einelogische Konsequenz von ∆ ist oder das D aus ∆ folgt, wenn D in jedem Modell gultig ist, indem alle Venn-Diagramme von ∆ gultig sind.

Die Definition von Modellen ist in gewisser Hinsicht redundant, da Modelle bereits durch die Bilderder Basisregionen bestimmt sind. Dazu definieren wir zunachst Mengenzuweisung auf Basisregionenwie folgt: Eine Mengenzuweisung auf Basisregionen ist ein Paar (U, g), wobei g jeder Basisregioneine Teilmenge von U zuordnet. Dabei wird gefordert, dass Basisregionen mit dem gleichen Bezeichnerauf die gleiche Teilmenge von U abgebildet werden, und dass Basisregionen eines Rechteckes auf Uabgebildet werden. Es gilt nun:

2.4. KALKUL 19

Lemma 2.8 (Erweiterung von Mengenzuweisungen auf Basisregionen zu Modellen) Es sei(U, g) eine Mengenzuweisung auf Basisregionen. Dann existiert ein eindeutig bestimmtes Modell (U, I),so dass I eingeschrankt auf die Basisregionen gerade g ist.

Man kann ahnlich argumentieren, dass Modelle bereits durch Mengenzuweisungen auf minimalen Re-gionen bestimmt ist. Hier ist aber zu beachten, dass der Begriff einer minimalen Region im Gegensatzzum Begriff einer Basisregion abhangig vom betrachteten Diagramm ist.5

Lemma 2.9 (Erweiterung von Mengenzuweisungen auf min. Regionen zu Modellen) SeiD ein Venn-Diargamm und sei (U, g) eine Mengenzuweisung auf den minimalen Regionen von D.Dann existierenen Modelle (U, I), so dass I eingeschrankt auf die minimalen Regionen von D geradeg ist, und je zwei Modelle (U, I) und (U, I ′) mit dieser Eigenschaft stimmen auf allen Regionen vonD uberein.

Man kann das letzte Lemma naturlich so verstehen, dass –wie in Lemma 2.8– ein eindeutig bestimmtesModell auf den Regionen von D existiert, das g fortsetzt. Diese Bedingung ist keine Einschrankung,wie das folgende einfache Lemma zeigt.

Lemma 2.10 (Gultigkeit hangt nur von Regionen im Diagramm ab) Sei D ein Diagramm undseien (U, I) und (U, I ′) zwei Modelle mit I(r) = I ′(r) fur alle in D vorkommenden Regionen r. Danngilt: (U, I) |= D ⇐⇒ (U, I ′) |= D.

2.4 Kalkul

In diesem Teilkapitel soll ein adaquater (d.h., korrekter und vollstandiger) Kalkul fur Venn-Diagrammevorgestellt werden. Vor den Regeln soll allerdings folgende grundlegende Konvention vereinbart werden:Eine Regel darf nur so angewendet werden, dass sie von einem wohlgeformten Venn-Diagramm zueinem wohlgeformten Venn-Diagramm fuhrt. Ein Beispiel dieser Konvention soll in de nachtsten Regelvorgestellt werden.

1. Teilweises Loschen einer X-Folge Ist D ein Venn-Diagramm, und enthalt D eine X-Folge, sokann jedes X dieser X-Folge, das in eine schattierte Region fallt, geloscht werden. Dabei werdendie verbleibenden Halften der X-Folge (wenn das geloschte X sich nicht am Rand der X-Folgebefand) wieder verbunden. Beispiele:

A B

X XX

`

A B

XX

A B

X XX`

A B

XX

5Das hat Hammer in [Ha95] ubersehen. Siehe Teilkapitel 2.9.


Bemerkung: Diese Regel ist mit der aufgrund der nachsten Regel umkehrbar.

Die Konvention, dass nur wohlgeformte Venn-Diagramme aus den Regeln abgeleitet werdendurfen, erlaubt beispielsweise folgende Herleitung nicht :

A B

XX

XX X`

A B

XX

XX

2. Erweitern einer X-Folge Ist D ein Venn-Diagramm, und enthalt D eine X-Folge, so kanndiese Folge um weitere X-Zeichen in jeder Region, die nicht bereits ein X der Folge enthalt,erganzt werden. Beispiel:

A B

X`

A B

XX X

Diese Regel ist (im allgemeinen) nicht umkehrbar.

3. Loschen Sei D ein Venn-Diagramm. Dann darf man folgende Bestandteile von D loschen:

(a) Eine komplette X-Folge,

(b) eine Schattierung, oder

(c) eine geschlossene Kurve. In diesem Fall ist folgendes zu beachten:

In dem resultierenden Diagram D′ hat eine Region r′ eine X-Folge F ′ genau dann, wennes in D eine X-Folge F gibt dergestalt, dass deren X-Zeichen genau in den Gegenstuckender minimalen Teilregionen m′ von r′ liegen. (Dabei beachte man, dass jede Region in D′

ein Gegenstuck in D hat, aber zu jeder minimalen Region m′ in D′ besteht das Gegenstuckin D aus zwei minimalen Regionen. Folglich reicht es aus, dass zur X-Folge F ′ und einerminimalen Region m′ einer der beiden Teilregionen des Gegenstuckes von m′ ein X-Zeichenvon F enthalt). Weiterhin ist in D′ eine Region genau dann schattiert, wenn das Gegenstuckin D schattiert ist. 6

Beispiel: AusA B

C

X

X X

6Diese Formulierung der Regel ist gegenuber Hammers Formulierung geandert, da Hammers Originalformulierungnicht zu den folgenden, von Hammer selbst bereitgestellten Beispielen passt. Siehe Teilkapitel 2.9.

2.4. KALKUL 21

erhalten wir durch Loschen einer Schattierung bzw. einer X-Folge

A B

C

X

X X

bzw.

A B

C

X

und durch Loschen der mit A, B bzw. C bezeichneten Kurven

B

C

X

X X

,

A

C

X

X X

bzw.

A B

X

X


Es ist bei dieser Regel zu beachten, dass das Loschen einer Kurve aus einer Zeichnung zu einemnicht wohlgeformten Diagramm fuhren kann. Beispielsweise fuhrt das Loschen der oberen beidenKreise aus dem Diagramm von Bild 2.1 zu einem Diagramm mit zwei Kurven, deren Regionennicht zusammenhangend sind. In diesem Fall muss man das resultierende Diagramm neu zeich-nen, d.h., man muss ein anderes Token fur denselben Typ wahlen. Siehe auch Teilkapitel 2.9.

4. Einfugen einer neuen Mengenkurve Ist D ein Venn-Diagramm, so darf zu D eine neuegeschlossene Kurve mit einem neuen Bezeichner hinzugefugt werden. Ist D′ das resultierendeDiagramm, so muß dabei folgendes beachtet werden:

(a) Eine Region r in D hat genau dann eine X-Folge (ist genau dann schattiert), wenn r in D′

ein Gegenstuck r′ hat, das eine X-Folge hat (das schattiert ist).

(b) Eine Region r′ in D′ hat genau dann eine X-Folge (ist genau dann schattiert), wenn r′ inD ein Gegenstuck r hat, das eine X-Folge hat (das schattiert ist).

Beispiel:A B

X

X

`

A B

C

XX

X

X

Diese Regel ist umkehrbar (durch Anwenden der letzten Regel).

5. Inkonsistenz Ist D ein Diagramm mit einer Region r, die sowohl schatiert ist als auch eine X-Folge hat, so darf aus D jedes andere Diagramm D′ hergeleitet werden. Beispiel: Aus folgendem


Diagramm darf man jedes Diagramm herleiten.

A B

XX


6. Unifizierung Seien D1 und D2 zwei Venn-Diagramme. Dann darf man folgendes Venn-DiagrammD aus D1 und D2 herleiten:

(a) Die Menge der Bezeichner von D ist die Vereinigung der Bezeichner von D1 und D2.

(b) Ist eine Region in D1 oder D2 schattiert, so ist ihr Gegenstuck in D schattiert. Ist umgekehrteine Region in D schattiert, so existiert ein Gegenstuck in D1 oder D2, das schattiert ist.

(c) Hat eine Region in D1 oder D2 eine X-Folge, so hat ihr Gegenstuck in D eine X-Folge. Hatumgekehrt eine Region in D eine X-Folge, so existiert ein Gegenstuck in D1 oder D2, daseine X-Folge hat.

Beispiel: Die Unifizierung von

A B

X und

CB

X

ergibtA B

C

X

X

X X

Diese Regel ist im folgenden Sinne umkehrbar: Aus D kann man sowohl D1 als auch D2 herleiten.

Definition 2.11 (Herleitbarkeit, Beweis, Konsistenz) Sei ∆ eine Menge von Venn-Diagrammenund sei D ein Venn-Diagramm. Wir sagen, dass D aus ∆ herleitbar ist und schreiben ∆ ` D,wenn es eine Folge D1, . . . , Dn−1, Dn mit Dn = D gibt, so daß jedes Element der Folge

1. ein Element von ∆ oder das leere Diagramm (das Diagramm, dass nur aus dem Rechteck besteht)ist, oder

2. aus aus einem fruheren Element der Folge mit einer der ersten funf Regeln herleitbar ist, oder

3. aus aus zwei fruheren Elementen der Folge mit der sechsten Regel (Unif.) herleitbar ist, oder

4. identisch zu einem fruheren Element der Folge ist.7

7Die Moglichkeit, ein Diagramm zu verdoppeln, taucht bei Hammer nicht auf und ist strenggenommen (da es um-kehrbare Regeln gibt) nicht notwendig, aber im spateren Beweis der Vollstandigkeit hilfreich.

2.4. KALKUL 23

Man nennt ∆ konsistent, wenn man aus ∆ nicht jedes andere Venn-Diagramm herleiten kann.

Bemerkung: Offensichtlich ist eine Menge ∆ genau dann konsistent, wenn aus ∆ kein Diagramm Dherleitbar ist, das eine schattierte Region enthalt, die eine X-Folge hat.

Man kann nun zeigen, dass der Kalkul korrekt ist. Es gilt also:

Lemma 2.12 (Der Kalkul ist korrekt) Sei ∆ eine Menge von Venn-Diagrammen und sei D einVenn-Diagramm. Dann gilt:

∆ ` D =⇒ ∆ |= D

Der Beweis wird fur jede Regel separat gefuhrt. Im folgenden seien, wenn nicht anders erwahnt, Dein Diagramm, D′ das Diagramm, das durch Anwendung der entsprechenden Regel aus D gewonnenwird, und (U, I) sei ein Modell mit (U, I) |= D (es ist dann (U, I) |= D′ zu zeigen).

• Teilweises Loschen einer X-Folge Seien m1, . . . ,mn die minimalen Regionen, die die X-Zeichen der Folge enthalten, von der ein X geloscht wird, und o.B.d.A. werde das X aus m1

geloscht. Wegen (U, I) |= D existiert ein mi mit I(mi) 6= ∅, und da m1 schattiert ist, giltweiterhin I(m1) = ∅. Wir erhalten i 6= 1, und (U, I) erfullt damit auch die Gultigkeitsbedingungfur die gekurzte Folge.

• Erweitern einer X-Folge Seien m1, . . . ,mn die minimalen Regionen, die die X-Zeichen derFolge enthalten, die erweitert wird. Dann existiert ein mi mit I(mi) 6= ∅, und da die X-Folgeerweitert wird, gilt damit auch (U, I) |= D′.

• Loschen Offensichtlich sind beim Loschen einer X-Folge oder einer Schattierung fur D′ wenigerGultigkeitsbedingungen zu prufen, woraus sofort (U, I) |= D′ folgt. Wenn eine geschlossene Kurvegeloscht wird, gilt: Fur eine Region r′ in D′, die schattiert ist, ist das Gegenstuck in D schattiert,womit I(r) = ∅ und damit auch I(r′) = ∅ gilt. Fur X-Folgen kann man ahnlich argumentieren.

• Einfugen einer neuen Mengenkurve Hier wird ahnlich wie im letzten Fall argumentiert.

• Inkonsistenz Klar, da es kein Modell (U, I) mit (U, I) |= D geben kann.

• Unifizierung Sei hier (U, I) |= D und (U, I) |= D′, und es sei D′′ das Diagramm, das durchUnifizierung aus D und D′ gewonnen wird. Sei r′′ eine schattierte Region in D′′. O.B.d.A.existiere ein Gegenstuck r in D, das schattiert ist. Es folgt I(r) = ∅, also auch I(r′′) = ∅. FurX-Folgen wird analog argumentiert. 2

Nutzlich ist auch festzuhalten, dass die Unifizierung zweier Diagramme der logischen Konjunktionentspricht.

Lemma 2.13 (Unifizierung entspricht Konjunktion) Seien D1 und D2 zwei Venn-Diagramme,sei D die Unifizierung von D1 und D2, und sei (U, I) ein Modell. Dann gilt:

(U, I) |= D1 und (U, I) |= D2 ⇐⇒ (U, I) |= D


2.5 (Endliche) Vollstandigkeit

Shin hat in [Sh94] den Beweis angeben, dass der Kalkul auch vollstandig ist. Die von Shin bewieseneVersion der Vollstandigkeit benutzt aber nur zwei Diagramme. Im nachsten Teilkapitel wird diesesResultat benutzt, um auch die sog. starke Vollstandigkeit des Kalkuls zu beweisen. Weiterhin ist derhier vorgestellte Beweis eine modifizierte Version von Shins Beweis.hide

Satz 2.14 (Der Kalkul ist (endlich) vollstandig) Seien D,D′ zwei Venn-Diagramme. Dann gilt:

D |= D′ =⇒ D ` D′ .

Beweis: O.B.d.A. sei D erfullbar. Die Vollstandigkeit wird bewiesen, indem konstruktiv ein formalerBeweis von D′ aus D angegeben wird.

Wie bereits bei ihrer Beschreibung angegeben, kann die Anwendung Regel ’Einfugen einer neuen Men-genkurve’ durch die Regel ’Loschen einer Mengenkurve’ wieder ruckgangig gemacht werden. Damitkann man jedes Diagramm um beliebige Mengenkurven mit neuen Bezeichnern zu einem beweisbaraquivalenten Diagramm erweitern. Folglich nehmen wir o.B.d.A. an, dass D und D′ dieselben Bezeich-ner haben.

Weiterhin kann man eine das teilweise Loschen einer X-Folge mit der Regel ‘Erweitern einer X-Folge’umkehren. Deswegen kann man jedes Diagramm in ein beweisbar aquivalentes Diagramm umformen,in dem es keine X-Zeichen in schattierten Regionen gibt. Folglich nehmen wir o.B.d.A. an, dass dassweder D noch D′ X-Zeichen in schattierten Regionen haben.

Strenggenommen brauchen wir auch die Regeln ’Loschen’ und ’Unifizierung’. Es kann namlich der Fall autreten, dasswir nicht wir nicht alle X-Zeichen einer X-Folge, die in schattierten Regionen liegen, loschen durfen, weil wir dann einnicht wohlgeformtes Diagramm erhalten wurden. Das soll an einem Beispiel erlautert werden. Wir betrachten:

D1 := X

A B

X X

X

Nur mit ’Teilweise Loschen einer X-Folge’ und ‘Erweitern einer X-Folge’ laßt sich zeigen, daß es beweisaquivalent ist zu:

D2 :=

A B

X X

Anders sieht es bei folgendem Diagramm aus:

D3 :=X X

X

A B

X X

X

X

Auch D3 ist beweisaquivalent zu D2. Der Nachweis von D3 ` D2 benotigt die Regeln ’Loschen (einer X-Folge)’ und

’Teilweise Loschen einer X-Folge’. Fur den Beweis D2 ` D3 wird zunachst eine Kopie D′2 von D2 erstellt –deswegen

haben wir den Beweisbegriff gegenuber Hammer leicht erweitert–, in D2 und D′2 kann man die X-Folgen erweitern, und

die Resultate werden dann unifiziert.

Es gilt nun, dass zu jeder schattierten Region in D′ ist ihr Gegenstuck in D auch schattiert ist. Umdas zu sehen, betrachten wir folgendes Modell: Jeder nicht schattierten, minimalen Region r von D

2.6. STARKE VOLLSTANDIGKEIT 25

weisen wir ein Objekt or zu. Das Universum U bestehe aus diesen Objekten, und die InterpretationI weise jeder nichtschattierten, minimalen Region von D das Objekt or zu (dieses Modell existiertaufgrund von Lemma 2.9). Offensichtlich gilt (U, I) |= D, also auch (U, I) |= D′. Damit kann es keineminimale Region in D′ geben, die schattiert ist, so dass ihr Gegenstuck in D nicht schattiert ist.

Es gilt weiterhin, dass zu jeder Region r′ von D′, die eine X-Folge hat, ihr Gegenstuck r in D eineTeilregion r besitzt, die eine X-Folge hat. Das beweisen wir indirekt und nehmen an, dass D′ eineX-Folge F ′ hat, die diese Aussage nicht erfullt. Sei R′ die Menge der minimalen Regionen in D′, indenen die X-Zeichen von F liegen. Dann existiert zu jeder X-Folge F in D eine minimale Region rF ,die ein X von F enthalt, und deren Gegenstuck nicht in R′ liegt. Jeder dieser Regionen rF weisen wirnun ein Objekt or zu. Das Universum U bestehe aus diesen Objekten, und die Interpretation I weisejeder der Regionen rF das Objekt or zu (dieses Modell existiert aufgrund von Lemma 2.9. Wieder siehtman, dass (U, I) |= D gilt, womit auch (U, I) |= D′ gelten muss. Andererseits erhalten wir I(r′) = ∅,obwohl r′ eine X-Region hat. Damit ist die erste Bedingung von Def. 2.7 fur r′ verletzt, womit wir(U, I) 6|= D′ erhalten. Widerspruch.

Wir konnen nun D′ aus D wie folgt herleiten: Zunachst werden mit der Regel ’Loschen’ alle Schat-tierungen von minimalen Regionen in D, deren Gegenstucke in D′ nicht schattiert sind, geloscht (imresultierenden Diagramm D′′ ist folglich eine Region genau dann schattiert, wenn das fur ihr Ge-genstuck in D′ der Fall ist, d.h., D′ und D′′ unterscheiden sich nur in den X-Folgen). Aus D′′ konnenwir Damit konnen wir schließlich D′ mit der Regel ’Erweitern einer X-Folge’ herleiten (und der Unifi-zierung, da eventuell einige X-Folgen in D erst –ahnlich wie oben– erst vervielfacht werden mussen).Somit haben wir einen formalen Beweis fur D ` D′ konstruiert. 2

Aufgrund der Unifizierungsregel und Lemma 2.13 kann man zunachst den Satz von Shin auf endlicheMengen ∆ verallgemeinern.

Korollar 2.15 (Vollstandigkeit) Sei ∆ eine endliche Menge von Venn-Diagrammen, sei D Venn-Diagramm. Gilt ∆ |= D, so gilt auch ∆ ` D.

Der Beweis von Shins Satz ist konstruktiv. Damit ergibt sich auch die Konsequenz, dass die Fragender logischen Konsequenz, Erfullbarbeit oder Gultigkeit entscheidbar sind.

Korollar 2.16 (logische Konsequenz, Erfullbarbeit, Gultigkeit sind entscheidbar) Seien Dund D′ zwei Venn-Diagramme. Dann sind die Probleme, ob D |= D′ gilt, ob D erfullbar ist, und obD allgemeingultig ist, entschedbar.

Weiterhin ergibt der Beweis von Shins Satz das folgende Interpolationslemma.

Korollar 2.17 (Interpolationslemma) Seien D,D′′ Venn-Diagramme mit D |= D′′. Dann existiertein Venn-Diagramm D′, so dass jeder Bezeichner in D′ sowohl in D als auch in D′′ auftaucht, undfur das D |= D′ |= D′′ gilt.

hide

2.6 Starke Vollstandigkeit

In diesem Teilkapitel soll die starke Vollstandigkeit des Kalkuls gezeigt werden, d.h., es soll

∆ |= D =⇒ ∆ ` D


fur beliebige (statt endliche) Mengen ∆ bewiesen werden. Die Beweisidee orientiert sich dabei groban den gangigen Vollstandigkeitsbeweisen in der Logik, d.h., ∆ wird zu einer maximal konsistentenMenge ∆′ erweitert, und es wird gezeigt, dass maximal konsistente Mengen Modelle besitzen.

Wir benotigen zunachst einige Definitionen.

Definition 2.18 (Positive und negative Diagramme, Negation von Diagrammen) Ein posi-tives Venn-Diagramm ist ein Venn-Diagramm, das keine Schattierungen und genau eine X-Folgeenthalt. Ein negatives Venn-Diagramm ist ein Venn-Diagramm, das keine X-Folgen und eineschattierte Region enthalt.

Ist D ein positives Venn-Diagramm. Ersetzt man die X-Folge durch eine Schattierung (d.h. ist r dieRegion, die in D die X-Folge hat, betrachtet man das negative Diagramm D′, das dieselben Bezeichnerwie D hat und in dem r schattiert ist), so heißt das resultierende Diagramm die Negation von D undwird mit ¬D bezeichnet. Sei analog D ein negatives Venn-Diagramm. Ersetzt man die Schattierungdurch eine X-Folge, so heißt das resultierende Diagramm die Negation von D und wird mit ¬Dbezeichnet.

Sei D ein beliebiges Venn-Diagramm. Jedes positive oder negative Diagramm, das aus D durch Loschenvon X-Folgen oder Schattierungen entsteht, heißt direktes Teildiagramm von D.

Sei ∆ eine maximal konsistente Menge (d.h., ∆ ist konsistent, aber es gibt kein konsistentes ∆′ ) ∆).Ist D ∈ ∆, so laßt sich jeder direkte Teildiagramm von D aus D herleiten und muß folglich zu ∆gehoren. Andererseits ist jedes Diagramm die Unifizierung seiner direkten Teildiagramme. Damit giltoffensichtlich: Ein Diagramm D ist genau dann ein Element von ∆, wenn jedes direkte Teildiagrammvon D zu ∆ gehort.hide

Lemma 2.19 (X-Folgen-Lemma) Sei D ein Diagramm. Sei r die Region, die die X-Folge F hat,und sei r die Vereinigung der minimalen Regionen r1, . . . , rn. Mit Di werde das positive Diagrammbezeichnet, das aus D durch Loschen von X und durch Hinzufugen eines einzelnen X in die Regionri entsteht. Ist nun ∆ eine Menge von Diagrammen, so dass ∆ ∪ {D} konsistent ist, so ist ∆ ∪ {Di}konsistent fur ein i = 1, . . . , n.

Beweis: Wir fuhren den Beweis zunachst fur den Spezialfall, dass D ein positives Diagramme D ist.Annahme: Jede Menge ∆∪{Di}, i = 1, . . . , n, ist inkonsistent. Dann existiert eine endliche Teilmenge∆0 ⊂⊂ ∆, so dass jede Menge ∆0 ∪ {Di} inkonsistent ist. Aufgrund der Korrektheit des Kalkulsist damit jede Menge ∆0 ∪ {Di} unerfullbar, d.h. es gilt ∆0 |= ¬{Di} fur jedes i. Da aber ¬D dieUnifizierung der ¬{Di} ist, folgt auch ∆0 |= ¬{D}. Mit der endlichen Vollstandigkeit erhalten wir∆0 ` ¬{D}, also auch ∆ ` ¬{D}. Damit ist ∆ ∪ {D} inkonsistent. Widerspruch.

Sei nun D ein beliebiges Diagramm. Wir zerlegen D in zwei direkte Teildiagramme D′ und D′′, wobeiD′ das positive Diagramm ist, das aus D durch Loschen aller Schattierungen und von F verschiedenenX-Folgen entsteht, und D′′ sei das Diagramm, das durch Loschen von F entsteht. Offensichtlich istD die Unifizierung von D′ und D′′, insbesondere ist ∆ ∪ {D′, D′′} konsistent. Weiterhin ist D′ einpositives Diagramm. Fur i = 1, . . . , n sei D′

i das positive Diagramm mit denselben Bezeichnern wieD′, das nur ein X in der Region ri hat. Dann ist, wie zu Beginn bewiesen, ∆ ∪ {D′

i, D′′} konsistent

fur ein i = 1, . . . , n. Da Di die Unifizierung von D′i und D′′ ist, ist auch ∆ ∪ {Di} konsistent. 2

Um zu zeigen, dass eine maximal konsistente Menge ∆ von Diagrammen ein Modell hat, reicht esaus, die positiven und negativen Diagramme in ∆ zu betrachten. Weiterhin besagt das letzte Lemma,dass ein positives Diagramm D genau dann zu ∆ gehort, wenn mindestens eines seiner ’Summanden’

2.6. STARKE VOLLSTANDIGKEIT 27

Di zu ∆ gehort. Im folgenden werden wir positive Diagramme, die nur ein einzelnes X enthalten,als atomare positive Diagramme bezeichnen. Analog werden wir Diagramme ohne X-Folgen, indenen eine minimale Region schattiert ist, als atomare negative Diagramme bezeichnen. Die obigeDiskussion kann nun in folgendem Lemma zusammengefasst werden:

Lemma 2.20 (Beschrankung auf atomare Graphen in maximal konsistenten Mengen) Sei∆ eine maximal konsistente Menge von Diagrammen und sei (U, I) ein Modell. Dann gilt (U, I) |= ∆genau dann, wenn (U, I) |= D fur alle atomaren Graphen D ∈ ∆ gilt.

Im folgenden werden wir ein Modelle M = (U, I) fur maximal konsistente Mengen ∆ konstruieren.Die Prozedur ist wie ublich bei derartigen Beweisen. Die Menge der Objekte U wird gerade aus denatomaren Diagramme in ∆ bestehen (davon gibt es maximal abzahlbar viele). Ein positives atomaresDiagramm Dp muß einen sog. Zeugen im Modell besitzen, der Dp erfullt. Als Zeuge werden wirnaturlich gerade Dp selber nehmen, das Element in geeigneten Mengen I(r) sein muß. Es soll aberzunachst bemerkt werden, dass Dp alleine nicht ausreicht um zu bestimmen, in welchen Regionen Dp

liegt. Betrachten wir dazu das positive Diagramm

Dp :=

A

X

Um dieses Diagramm zu erfullen, genugt es, den Zeugen Dp der mit A bezeichneten Region zuzuordnen.Es kann aber ∆ beispielsweise auch das negative atomare Diagramm

A B

enthalten. Nur mit der Zuweisung von Dp zur Region von A wird dieses Diagramm nicht gultig: Wirmussen Dp offensichtlich auch der Region von B zuordnen. Enthalt ∆ weiterhin das negative atomareDiagramm

A C

so muß Dp auch der Region von C zugeordnet werden. Wir mussen also, um die ‘korrekte’ Zuweisungvon Dp zu Regionen zu erhalten, sowohl Dp als auch samtliche negativen Diagramme von ∆ betrachten.Diese Beweisidee wird im Beweis des folgenden Satzes prazisiert.

Satz 2.21 (Maximal konsistente Mengen sind erfullbar (Hammer und Danner)) Sei ∆ ei-ne Menge von Venn-Diagrammen und sei D ein Venn-Diagramm.

Beweis: Sei D1, D2, . . . eine Aufzahlung aller positiven atomaren Diagramme von ∆ und sei N1, N2, . . .eine Aufzahlung aller negativen atomaren Diagramme von ∆. Fur das zu konstruierende Modell M :=(U, I) setzen wir zunachst U := {Di | i ∈ N}. Es reicht gemaß Lemma 2.8, I nur auf den Basisregionenzu definieren. Dazu definieren wir sukzessive zu jedem n eine Interpretation In, so dass (U, In) |= Dn

und (U, In) |= Ni fur jedes i gilt, und so dass I0 ⊆ I1 ⊆ I2 . . . gilt.

Fur jedes n sei zunachst


1. E0n := Dn

2. Ek+1n sei die Unifizierung von Ek

n und Nk, wobei die X-Folge gemaß Lemma 2.19 auf ein einzelnesX gekurzt wurde

Es ist jedes Diagramm Ekn ein Element von ∆, und es genugt, ein Modell fur alle Ek

n zu konstruieren.

Wir setzen I0 := ∅. Es wird nun In konstruiert fur n ≥ 1, und wir setzen voraus, dass In−1 bereitsdefiniert ist. Sei I0

n := In−1(r) ∪ {Dn} fur jede Basisregion r, so dass das X von Dn in r liegt, undI0n := In−1(r) sonst. Analog sei Ik+1

n := In−1(r)∪{Dn} fur jede Basisregion r, so dass das X von Ek+1n

in r liegt, und I0n := In−1(r) sonst. Wir setzen In :=

⋃k∈N Ik

n.

Klar ist, dass ist (U, In0 ), also auch (U, In), also auch (U, I) ein Modell von Dn ist. Es kann weiterhin

gezeigt werden, dass (U, In) ein Modell fur jedes Diagramm Ni ist (der Nachweis ist straight forward,aber technisch). Wir setzen nun I :=

⋃n∈N In. Damit ist auch (U, I) ein Modell fur jedes Ni. Insgesamt

ist damit (U, I) ein Modell von ∆. 2

Es kann jede konsistente Menge auf die ubliche Art zu einer maximal konsistenten Menge erweitertwerden. Damit erhalten wir:

Korollar 2.22 (Konsistente Mengen von Diagrammen sind erfullbar) Sei ∆ eine Menge vonVenn-Diagrammen. Ist ∆ konsistent, so besitzt ∆ ein Modell.

Mit diesem Korollar kann nun die starke Vollstandigkeit des Kalkuls bewiesen werden. Das Standar-dargument solcher Beweise ist: Man nimmt ∆ 6` D an, benutzt die Konsistenz von ∆ ∪ {¬D}, umein Modell von ∆ ∪ {¬D} zu konstruieren, woraus ∆ 6|= D folgt. Dieses Argument muß bei VennDiagrammen aber etwas erweitert werden, da keine Negation von Diagrammen zur Verfugung steht.

Korollar 2.23 (Starke Vollstandigkeit) Sei ∆ eine Menge von Venn-Diagrammen und sei D einVenn-Diagramm. Gilt ∆ |= D, so gilt auch ∆ ` D.

Beweis: Wir nehmen ∆ 6` D an. Seien D1, . . . , Dn die direkten Teildiagramme von D. Wir zeigenzunachst indirekt, dass es ein i gibt, so dass ∆ ∪ {¬Di} konsistent ist. Sei also kein ∆ ∪ {¬Di}konsistent. Dann existiert ein endliches ∆0 ⊆ ∆, so dass jedes ∆0 ∪ {¬Di} inkonsistent, also auchunerfullbar ist. Es folgt ∆0 |= Di fur jedes i, also auch ∆0 |= D. Damit folgt ∆0 ` D aufgrund derendlichen Vollstandigkeit (Kor. 2.15), also auch ∆ ` D, im Widerspruch zur Annahme. Es ist also∆ ∪ {¬Di} fur ein i konsistent und besitzt damit gemaß Kor. 2.22 ein Modell M . Da M kein Modellvon Di ist, ist es auch kein Modell von D. Es folgt ∆ 6|= D; ein Widerspruch. 2

2.7 Definierbare Mengensysteme

Wir nennen eine Klasse K von Modellen definierbar genau dann, wenn es ein Venn-Diagramm Dgibt mt K = {M | M |= D}. In diesem Teilkapitel soll gezeigt werden, dass die definierbaren Klassenweder unter Komplementbildung noch unter Vereinigung abgeschlossen sind. Damit gibt es in Venn-I weder die Moglichkeit, die Negation von Diagrammen, noch die Moglichkeit, die Disjunktion vonDiagrammen auszudrucken.

Satz 2.24 (Definierbare Klassen) Die definierbaren Klassen sind weder unter Komplementbildungnoch unter Vereinigung abgeschlossen.

2.7. DEFINIERBARE MENGENSYSTEME 29

Beweis: Wir zeigen zunachst, dass die Klasse

K := {(U, I) | I(r) = ∅ ∨ (U\I(r)) = ∅}

durch kein Diagramm D definiert wird. Der Beweis wird indirekt gefuhrt, sei also D ein Diagramm,das K definiert. Dann gilt:

1. D muß eine mit A bezeichnete Kurve enthalten.

2. Weiterhin darf D keine X-Folge enthalten (denn sonst ist das Modell M ∈ K, das jeder Regiondie leere Menge zuordnet, kein Modell von D).

3. Schließlich muß entweder die gesamte Region innerhalb der A-Kurve oder die gesamte Regionaußerhalb der A-Kurve schattiert sein (denn sonst gabe es ein Modell M von D, in dem zubeiden Regionen eine nichtleere Menge zugeordet wird, und M /∈ K).

Ist nun aber die die gesamte Region innerhalb der A-Kurve schattiert, dann wird in jedem Modell Mvon D der Region r die leere Menge zugeordnet, womit die Klasse der Modelle, die D erfullen, eineechte Teilklasse von K ist. Analog kann nicht die gesamte Region außerhalb der A-Kurve schattiertsein. Damit wird K durch kein Diagramm D definiert.

Wir betrachten nun das Diagramm

X

A

X

Mit r bezeichnen wir die mit A bezeichnete Region. Die Klasse der Modelle, die dieses Diagrammerfullen, ist

K¬ := {(U, I) | I(r) 6= ∅ ∨ (U\I(r)) 6= ∅}also das Komplement von K. Da K¬ durch ein Diagramm beschrieben wird, K aber nicht, sind diedefinierbaren Klassen nicht unter Komplementbildung abgeschlossen.

Analog konnen wir die folgenden beiden Diagramme betrachten.

A

und

A

Die Klasse der Modelle, die das erste oder das zweite erfullen, ist

K∨ := {(U, I) | I(r) 6= ∅} ∪ {(U, I) | (U\I(r)) 6= ∅} = {(U, I) | I(r) 6= ∅ ∨ (U\I(r)) 6= ∅}

Wie im ersten Fall ist K∨ das Komplement von K, womit die definierbaren Klassen nicht unterVereinigung abgeschlossen sind. 2

Man beachte aber, dass die Unifizierung von Diagrammen der Konjunktion entspricht, womit diedefinierbaren Klassen unter Schnittbildung abgeschlossen sind (womit auch klar ist, dass es ausgereichthatte, nur eine der beiden Aussagen von Satz 2.24 zu beweisen).

Der Beweis von Satz 2.24 laßt sich leicht so modifizieren, dass man sogar die Diagramme klassifizierenkann, die einer Negation bzw. einer Disjunktion anderer Diagramme entsprechen. Es gelten folgendeSatze (die hier nicht bewiesen werden sollen):


Satz 2.25 (Klassifikation der Diagramme, die einer Negation entsprechen) Sei D ein Dia-gramm. Dann ist das Komplement der durch D definierten Klasse von Modellen definierbar genaudann, wenn D entweder

1. positiv ist,

2. negativ ist,

3. widerspruchlich ist, oder

4. allgemeingultig ist.

Satz 2.26 (Klassifikation der Diagramme, die einer Disjunktion entsprechen) Seien D,D′

Diagramme. Dann ist die Vereinigung der durch D definierten Klasse und der von D′ definiertenKlasse definierbar genau dann, wenn

1. D = D′ gilt,

2. D gultig ist,

3. D′ gultig ist,

4. D widerspruchlich ist,

5. D′ widerspruchlich ist,

6. D und D′ positiv sind,

7. D aus D′ durch Hinzufugen geschlossener Kurven gewonnen werden kann, oder

8. D′ aus D durch Hinzufugen geschlossener Kurven gewonnen werden kann.

2.8 Ein heterogenes System von Diagrammen und FOL-Formeln

Man kann diagrammatische Logiksysteme auf verschiedene Arten mit der ‘klassischen’ symbolischenLogik verbinden. Ein Ansatz ist, Ubersetzungen zwischen dem diagrammatischen System und einemgeeigneten Fragment der Logik erster Stufe (first oder logic, FOL) bereitzustellen. In diesem Teilkapitelsoll ein anderer Ansatz vorgestellt werden: Ein System, dass sowohl die Venn-Diagramme als auch FOL-Formeln umfasst. Dieser Ansatz wird in diesem Skript fur die folgenden diagrammatischen Systemenicht mehr benutzt werden. Er soll aber trotzdem vorgestellt werden; unter anderem deshalb, weil ervon der Idee dem Hyperproof--System von Barwise und Etchmendy entspricht.

Wir definieren zunachst Syntax und Semantik der FOL-Formeln.

Definition 2.27 (FOL-Formeln) Gegeben sei eine Menge A := {Ai | i ∈ N} von Bezeichnern sowieeine Menge V ar := {x1, x2, . . .} von Variablen. Die FOL-Formeln uber A sind wie folgt induktivdefiniert:

1. ist xi eine Variable und Aj ein Bezeichner, so ist Aj(xi) eine FOL-Formel.

2. Sind f und g Formeln, so auch (f ∨ g), (f ∧ g), und ¬f .

2.8. EIN HETEROGENES SYSTEM VON DIAGRAMMEN UND FOL-FORMELN 31

3. ist f eine Formel und ist xi eine Variable, so sind auch ∃xi.f und ∀xi.f Formeln.

Ein Satz ist eine Formel ohne freie Variablen.

Wir benutzen die ublichen Klammerregeln.

Definition 2.28 (FOL-Modelle) Ein FOL-Modell ist ein Paar M := (U, I), wobei I eine Abbil-dung ist, die jedem Bezeichner Ai eine Teilmenge von U zuordnet.

Eine (Variablen-)Belegung auf U ist eine Abbildung v : V ar → U . Ist v eine Belegung und u ∈ U ,so bezeichnet v(xi/u) die Belegung, die auf V ar\{xi} mit v ubereinstimmt und die xi auf u abbildet.

Eine Formel f gilt in einem Modell M unter der Belegung v, geschrieben M |= f [v], falls:

1. M |= Aj(xi)[v] gdw. v(xi) ∈ I(Aj)

2. M |= f ∧ g gdw. M |= f und M |= g.

3. M |= f ∨ g gdw. M |= f oder M |= g.

4. M |= ¬f gdw. M 6|= f .

5. M |= ∃xi.f gdw. M |= f [v(xi/u)] fur ein u ∈ U .

6. M |= ∀xi.f gdw. M |= f [v(xi/u)] fur alle u ∈ U .

Ist F eine Menge von Formeln und f eine Formeln, so setzten wir F |= f genau dann, wenn f injedem Modell gilt, in dem alle alle Formeln von F gelten.

Wir konnen nun auf naheliegende Weise jeder Region und dann auch jedem Diagramm eine Formelmit einer freien Variablen zuordnen:

1. Ist r eine mit Ai bezeichnete Basisregion, so setzen wir Φ(r) := Ai(xj).

2. Sind r und s Regionen und haben Φ(r) und Φ(s) die gemeinsame freie Variable xj , so setzen wirΦ(r ∩ s) := Φ(r) ∧ Φ(s), Φ(r ∪ s) := Φ(r) ∨ Φ(s), und Φ(r) := ¬Φ(r).

Diese Zuordnung ordnet, genau genommen, jeder Region eine Menge von Formeln zu. Ist beispielsweisedas Diagramm

A B

C

gegeben, so wird der Region, die dem Schnitt der Basisregionen von A, B und C entspricht, unteranderem folgende Formeln zugeorndet:

A(x1) ∧B(x1) ∧ C(x1) , A(x5) ∧B(x5) ∧ C(x5) , C(x3) ∧A(x3) ∧B(x3)


Um kenntlich zu machen, welche Variable benutzt wird, schreiben wir auch f(x) statt f .

Sei nun D ein Diagramm. Seien r1, . . . , rn die Regionen von D, die eine X-Folge haben, und sei r dieschattierte Region von D. Seien f1(x) = Φ(r1), . . . , fn(x) = Φ(r1) und f(x) = Φ(r). Wir setzen nun

Φ(D) := ∃x.(f1(x) ∧ . . . ∧ fn(x)) ∧ ∀x.¬f(x)

Wir fuhren nun Diagramme und Formeln zusammen. Eine logische Darstellung ist entweder eineFormel oder ein Diagramm. Die Modelle fur Darstellungen sind wie folgt definiert:

Definition 2.29 ((Heterogene) Modelle) Ein Paar M := (U, IV , IFOL) ist ein (heterogenes)Modell, wenn (U, IV ) ein Modell fur Diagramme ist (gemaß Def. 2.5), (U, IFOL) ein FOL-Modellist, und wenn IV (r) = IFOL(Ai) fur jede mit Ai bezeichnete Basisregion r gilt.

Fur Diagramme D und Formeln f setzen wir naturlich

(U, IV , IFOL) |= D :⇐⇒ (U, IV ) |= D und (U, IV , IFOL) |= f :⇐⇒ (U, IFOL) |= f

Ist E eine Menge von Darstellungen und ist e eine Darstellung, E |= e genau dann, wenn e in jedemModell gilt, in dem alle alle Darstellungen von E gelten.

Lemma 2.30 (Zusammenhang zwischen Interpretation von Diagrammen und Formeln) SeiM := (U, IV , IFOL) ein Modell. Ist r eine Region und f(x) := Φ(r), so gilt:

I(r) = {u ∈ U | (U, IFOL) |= f [v] fur eine Belegung v mit v(x) = u}

Ist D ein Diagramm, so gilt:M |= D ⇐⇒ M |= Φ(D)

Der Beweis wird kanonisch uber den Aufbau von Regionen gefuhrt.

Wir haben bereits einen korrekten und vollstandigen Kalkul fur Venn-Diagramme bereitgestellt. Wirnehmen weiterhin an, dass wir einen korrekten und vollstandigen Kalkul fur FOL zur Verfugung haben(beispielsweise einen Sequenzenkalkul oder Natural Deduction).8 Wir werden nun Regeln bereitstel-len, die Beweise mit Darstellungen erlauben, also Beweise, die sowohl Diagramme als auch Formelnenthalten.

∃-Beobachtung Sei D ein Diagramm mit einer Region r, sei f(x) = Φ(r). Hat r eine X-Folge, sodarf man ∃x.f herleiten.

∀-Beobachtung Sei D ein Diagramm mit einer Region r, sei f(x) = Φ(r). Ist r schattiert, so darfman ∀x.¬f herleiten.

∃-Anwendung Ist eine Formel ∃x.f sowie ein Diagramm D, das eine Region r enthalt mit f = Φ(r),so darf man in r eine X-Folge eintragen (vorausgesetzt, dass r nicht bereits eine X-Folge hat).

∀-Anwendung Ist eine Formel ∀x.¬f sowie ein Diagramm D, das eine Region r enthalt mit f = Φ(r),so darf man r schattieren.

8Man beachte aber, dass diese beiden Systeme nicht die gleiche Ausdrucksstarke haben: Das System der Venn-Diagramme ist offensichtlich schwacher als das (entscheidbare) FOL-Fragment, das nur auf monadischen (d.h., einstelli-gen) Relationsnamen aufbaut und keine Funktionsnamen oder Konstanten enthalt.

2.9. PROBLEME BEI HAMMER 33

Ein Beweis mit Darstellungen wird nun kanonisch definiert: Ist E eine Menge von Darstellungenund ist e eine Darstellung, so ist ein Beweis von e aus E eine Folge von Darstellungen aus E ∪ {e},so dass jede Darstellung aus der Folge ein Axiom ist oder aus fruheren Darstellungen mit einer derRegeln fur Diagramme, fur Formeln, oder einer der eben angegebenen Regeln herleitbar ist, und sodass das letzte Element der Folge e ist. Wir schreiben dann E ` e.

Man beachte, dass aufgrund dieser Regeln fur jedes Diagramm D nun folgendes gilt:

Φ(D) ` D und D ` Φ(D) (2.1)

Dieser heterogene Kalkul ist adaquat, wie der folgende Satz zeigt.

Satz 2.31 (Korrektheit und Vollstandigkeit des heterogenen Kalkuls) Sei E∪{e} eine Men-ge von Darstellungen. Dann gilt:

E ` e ⇐⇒ E |= e

Beweis: ‘⇒’: Es ist nur die Korrektheit der neuen Regeln ∃-Beobachtung, ∀-Beobachtung, ∃-Anwendungund ∀-Anwendung zu zeigen. Wir beginnen mit der ∃-Beobachtung. Sei dazu D ein Diagramm miteiner Region r, die eine X-Folge hat, sei f(x) := Φ(r). Sei M := (U, IV , IFOL) ein (heterogenes) Modellmit M |= D. Dann gilt IV (r) 6= ∅. Gemaß Lemma 2.30 gilt

{u ∈ U | (U, IFOL) |= f [v] fur eine Belegung v mit v(x) = u} 6= ∅ .

Aus der Definition der Gultigkeit von Formeln in Modellen folgt M |= ∃x.f . Damit ist die ∃-Anwendung korrekt.

Die Korrektheit der verbleibenden drei Regeln wird analog gezeigt.

‘⇐’: Sei E ∪ {e} eine Menge von Darstellungen mit E |= e. Wir konnen nun gemaß Gleichung 2.1jedes Diagramm D ∈ E durch Φ(D) ersetzen. Analog konnen wir e durch Φ(e) ersetzen, sofern e einDiagramm ist. Da der FOL-Kalkul vollstandig ist, konnnen wir nun e (falls e eine Formel ist) bzw.Φ(e) (falls e ein Diagramm ist) herleiten. Im letzen Fall konnen wir, wiederum gemaß Gleichung 2.1,auch e aus E herleiten. 2

2.9 Probleme bei Hammer

Bei Hammer tauchen mehrere Probleme auf. Viele liegen darin begrundet, dass er Diagramme alsgraphische Systeme und nicht als abstrakte mathematische Strukturen, die graphisch reprasentiertwerden konnen, ‘formalisiert’. Mit anderen Worten: Viele Definitionen –beispielsweise die Syntax oderdie Regeln des Kalkuls– finden auf der Tokenebene statt, obwohl sie auf der Typebene formalisiertwerden mussten (aber die Typebene ist gar nicht vernunftig bei Hammer eingefuhrt worden).

• Proposition 2 bei Hammer lautet wie folgt: ’If (U, g) is a set assigment to minmal regions, thenthere is a unique model such that I extends g.’

Diese Proposition ist in dieser Form nicht korrekt, da der Begriff der minimalen Region nur furein gegebenes Diagramm Sinn macht. Deswegen wurde diese Proposition in dieser Arbeit durchdie Kombination der Lemmata 2.9 und 2.10 ersetzt.


• Die ‘partial overlapping rule’ besagt, dass die neue Kurve einen echten Teil jeder Zone von Duberlappen muß, und das genau einmal. Weiterhin fordert Hammer, dass die neue Kurve jedevorhandene Kurve genau zweimal schneiden muß. Aber das von ihm selbst angefuhrte Beispieleines Diagrammes mit vier Kurven erfullt diese Anforderung nicht. Diese Anforderung ist auchdurch Diagramme, in der sich hochstens zwei Kurven in einem Punkt schneiden (d.h., es gibtnicht drei oder mehr Kurven, die sich in eienm Punkt schneiden) nicht erfullbar. Begrundung:Wenn zu dem Diagramm

A B

C

eine weitere Kurve hinzugefugt werden soll, die genau einmal durch jede minimale Region geht,liegen an jeder minimalen Region genau zwei Schnittpunkte an. Jeder Schnittpunkt wird doppeltgezahlt, also gibt es genausoviel Schnittpunkte wie minimale Regionen. Also muss in unseremFall die neue Kurve insgesamt genau acht Schnittpunkte mit den vorhandenen Kurven haben.Erlaubt waren aber nur sechs, wenn die neue Kurve jede vorhandene Kurve genau zweimalschneiden soll.

• Damit liegt es nahe, das obige Diagramm mit vier Kurven zu erlauben. Aber was passiert, wennwir mit der Loschregel die Kurven A und B loschen? Im unteren Bild sind sie grau markiert.

BA

DC

Wir sehen, dass die verbleibenden zwei Kurven nicht zusammenhangende Regionen haben! Damitfuhrt die naive Anwendung der Loschregel von wohlgeformten zu nicht wohlgeformten Diagram-men. In der Tat musste man die Regel auf der Typ- und nicht auf der Token-Ebene formalisieren,und dazu die Bemerkung machen, dass teilweise ein neues Zeichnen des Diagrammes notig ist(ein Entfernen grafischer Komponenten aus der Zeichnung reicht nicht aus).

• Hammer beschreibt die Regel ‘Loschen einer geschlossenen Kurve’ wie folgt:

In einem Venn-Diagramm D darf man eine geschlossene Kurve loschen. Dabei ist zu beachten:

In dem resultierenden Diagram D′ hat eine Region eine X-Folge genau dann, wenn das Ge-genstuck in D eine X-Folge hat, und in D′ ist eine Region genau dann schattiert, wenn dasGegenstuck in D schattiert ist. Man beachte, dass jede Region in D′ ein Gegenstuck in D hat,aber zu jeder minimalen Region in D′ besteht das Gegenstuck in D aus zwei minimalen Regionen.

Die von Hammer bereitgestellten Beispiele erfullen aber diese Form der Regel nicht. Wir wieder-holen dazu das von Hammer bereitgestellte Beispiel. Unsere Aufmerksamkeit richten wir dabeiauf die X-Folge mit den zwei X-Zeichen in D und deren ‘Bild’ in D′. Die jeweile Regionen inD′, die das ’Bild’ der X-Folge enthalten, sowie ihre Gegenstuck in D sind schraffiert dargestellt.

2.9. PROBLEME BEI HAMMER 35

Hammer erhalt durch Loschen der mit A, B bzw. C bezeichneten Kurven

A B

C

X

X X,

C

A B

C

X

X X,

A B

C

X

X X

jeweils die Diagramme

C

B

C

X

X X,

A

C

X

X X,

A B

X

X

Wir sehen aber, dass in keinem dieser Beispiele die schraffierte Region (die Gegenstucke derentsprechenden Regionen in D′) eine X-Folge hat. Aus diesem Grund sind die Beispiele keineResultate von Hammers Formulierung der Regel. Stattdessen wurde Hammers Formulierung derRegel Diagramme ergeben, die gar keine X-Folgen enthalten.

Es soll aber erwahnt werden, dass auch Hammers Formulierung der Regel, die den Informations-gehalt eines Diagrammes starker abschwacht als unsere neue Formulierung, trotzdem ausreicht,um einen adaquaten (korrekten und vollstandigen) Kalkul zi erhalten.

• Bei den Regeln, beispielsweise ’Teilweises Loschen einer X-Folge’ und ’Erweitern einer X-Folge’,achtet Hammer nicht darauf, ob man Diagramme erhalt, die zwei X-Folgen enthalten, derenX-Zeichen in genau denselben minimalen Regionen liegen.

• Nicht wirklich ein Problem, aber trotzdem unglucklich finde ich, dass die Reihenfolge der X-Zeichen bei X-Folgen nicht thematisiert wird. Betrachten wir

A B

X

XX

und

A B

X

XX

Gemaß 2.4 sind das verschiedene Tokens desselben Types.

Es soll aber erwahnt werden, dass auch bei den vernunftig formalisierten Spiderdiagrammen vonHowse et al., die den hier gezeigten Venn-Diagrammen sehr ahnlich sind, analog vorgegangenwird. Die X-Folgen der Venn-Diagramme sind dort sog. Spinnen (spider), die X-Zeichen sinddie Fusse (feet) der Spinnen. Spinnen werden auf der Type-Ebene im wesentlichen formalisiertdurch die Angabe der minimalen Regionen (Zonen), in der die Fusse der Spinne liegen. In dergraphischen Reprasentation werden dann die Fusse miteinander durch Linien verbunden (zueinem Baum), aber es wird nicht thematisiert, auf welche Art die Fusse verbunden werdensollen.


Kapitel 3

Techniken des DiagrammaticReasoning (Bsp: Alpha-Graphen)

3.1 Was sind Diagramme?

3.1.1 2-Dimensionalitat

Erste Idee: Diagramme sind keine lineare, sondern 2-dimensionale Darstellung.

Noh, reicht nicht.

Einerseits:Erde—Mond———————————Mars

ist Diagramm, obwohl eindimensional.

Andererseits: Nicht jede zweidim. Darstellung ist Diagramm. Beispiel: Tabellen, Listen.

3.1.2 Klassifizierung der Zeichen

Heterogenitat: Mischen von Text und ikonischen Darstellungen

Types/Tokens

Index/Ikon/Symbol

In this paper, we consider the Alpha- and Beta-part of existential graphs. Alpha is a system whichcorresponds to the propositional calculus of mathematical logic. Beta builds upon Alpha by introducingnew symbols to Alpha, and it corresponds to first order predicate logic (FOPL), that is first orderlogic with predicate names, but without object names and without function names.

We start with the description of Alpha. The EGs of Alpha consist only of predicate names of arity0, which Peirce called medads, and of closed, double-point-free curves which are called cuts andused to negate the enclosed subgraph. Medads can be considered as (atomar) propositions, i.e., theycorrespond to propositional variables in propositional logic. Propositions can be written down on anarea (Peirce used the term ‘scribing’ instead of ‘writing‘), and writing down a proposition is to assertit. The area where the proposition is written on is what Peirce called the sheet of assertion. It may be

37

38 KAPITEL 3. TECHNIKEN DES DIAGRAMMATIC REASONING (BSP: ALPHA-GRAPHEN)

a sheet of paper, a blackboard or any other surface. Writing several propositions next to each other(this operation is called a juxtaposition) asserts the truth of each proposition, i.e. the juxtapositioncorresponds to the conjunction of the juxtaposed propositions. For example, writing the propositions‘it rains’ and ‘it is cold‘ next to each other yields the graph

it rains it is cold

which means ‘it rains and it is cold’.

Encircling a proposition is to negate it. The line which is used to encircle a proposition is called a cut,the space within a cut is called its close or area. For example,

it rains it is cold

has the meaning ‘it is not true that it rains and that it is cold’, i.e. ‘it does not rain or it is not cold’.Cuts may not overlap, but they may be nested. The next graph has two nested cuts.

it rains it is cold

This graph has the meaning ‘it is not true that it rains and that it is not cold’, i.e. ‘if it rains, then it iscold’. The device of two nested cuts is called a scroll. From the last example we learn that a scroll canbe read as an implication. A scroll with nothing on its first area is called double cut (it correspondsto a double negation). As mentioned before, the space within a cut is called the area of the cut. Inthe example above, we therefore have three distinct areas: All the space outside the outer cut, i.e. thesheet of assertion, the space between the outer and the inner cut, which is the area of the outer cut,and the space inside the inner cut, which is the area of the inner cut. An area is oddly enclosed if itis enclosed by an odd number of cuts, and it is evenly enclosed if it is enclosed by an even number ofcuts.

We have the possibility to express conjunction and negation of propositions, thus Alpha has theexpressiveness of propositional logic. Peirce also provided a set of five derivation rules for EGs. ForAlpha, these rules are:

• Erasure: Any evenly enclosed subgraph may be erased.

• Insertion: Any graph may be scribed on any oddly enclosed area.

• Iteration: If a subgraph G occurs on the sheet of assertion or in a cut, then a copy of G may bescribed on the same or any nested area which does not belong to G.

• Deiteration: If a subgraph G could be the result of iteration, then it may be erased.

• Double Cut: Any double cut may be inserted around or removed from any graph of any area.

This set of rules is sound and complete. In the following, a simple example of a proof is provided(which will be an instantiation of modus ponens in EGs).

Let us start with the graph on theright. It has the meaning ‘it rains,and if it rains, then it is cold’.

it rains it is coldit rains

3.1. WAS SIND DIAGRAMME? 39

The inner instance of ‘it rains’may be considered a copy of theouter instance of ‘it rains’. Hencewe can erase the inner instanceof ‘it rains’ using the deiteration-rule.

it rains it is cold

This graph contains a double cut,which now may be removed.

it rains it is cold

Finally we erase the proposition‘it rains’ with the erasure-rule.

it is cold

So the graph with the meaning ‘it rains, and if it rains, then it is cold’ implies the graph with themeaning ‘it is cold’.

If we go from the part Alpha of EGs to the part Beta, predicate names of arbitrary arity may beused, and a new syntactical item, the line of identity (LI), is introduced. LIs are used to denote boththe existence of objects and the identity between objects. They are attached to predicate names anddrawn bold. Consider the following graph:

man loves woman

It contains two LIs, hence it denotes two (not necessarily different) objects. The first LI is attached tothe unary predicate ‘man’, hence the first object denotes a man. Analogously the second LI denotes awoman. Both lines are attached to the dyadic predicate ‘loves’, i.e. the first object (the man) standsin the relation ‘loves’ to the second object (the woman). The meaning of the graph is therefore ‘thereare a man and a woman such that the man loves the woman‘, or in short: A man loves a woman.

LIs may cross cuts.1 Consider the following graphs:

man man man

The meaning of the first graph is clear: it is ‘there is a man’. The second graph is built from the firstgraph by drawing a cut around it, i.e. the first graph is denied. Hence the meaning of the second graphis ‘it is not true that there is a man’, i.e. ‘there is no man’. In the third graph, the LI begins on thesheet of assertion. Hence the existence of the object is asserted and not denied. For this reason themeaning of the third graph is ‘there is something which is not a man’.

Now we have the possibility to express existential quantification, predicates of arbitrary arities, con-junction and negation. Hence we see that the part Beta of EGs corresponds to FOPL.

Essentially, the rules of the calculus for Beta are extensions of the five rules for Alpha such thatthey now encompass the properties of the lines of identity. For example, the erasure-rule and theinsertion-rule are now formulated as follows:

• Erasure: Any evenly enclosed graph and any evenly enclosed portion of a LI may be erased.1This is not fully correct: Peirce denies that a LI may cross a cut (a corollary in [Pe03] states ’It follows that no line of

identity can cross a cut.’), Roberts allows it, and it is not clear whether Shin allows it or not. In Peirce’s view, the thirdgraph has two lines of identity which ‘meet’ at the cut. But the discussion of this needs a much deeper understanding ofEGs and shall therefore be omitted here.


• Insertion: Any graph may be scribed on any oddly enclosed area, and two LIs (or portions oflines) oddly enclosed on the same area, may be joined.

For the formulation of the remaining three rules we refer to [Ro73] (we have taken the other formula-tions of the rules from this source).

3.2 Problems with Existential Graphs

To illustrate some of the problems which may occur in the handling of diagrams, we focus on theEGs as they are described in the book of Shin ([Sh01]), but we will refer to other authors like Peirce,Zeman or Roberts as well. For our discussion, it is sufficient to consider the definitions Shin providesfor Beta graphs. It is labelled ‘Non-Math.(ematical) Definition’ to distinguish it from mathematicaldefinitions as they will appear later in this paper.

Definition 3.1 (Alpha Graphs)

The set of Alpha graphs, Gα, is the smallest set satisfying the following:

1. An empty space is in Gα.

2. An sentence symbol is in Gα.

3. Juxtaposition closure If G1 is in Gα, . . ., and Gn is in Gα, then the juxtaposition of these ngraphs, i.e. G1, . . . , Gn, (we write ’G1 . . . Gn’ for juxtaposition) is also in Gα.

4. Cut closure If G is Gα, then a single cut of G (we write ’[G]’ following Peirce’s linear notion)is also in Gα.

Definition 3.2 (Beta Graphs)

The set of beta graphs, Gβ, is the smallest set satisfying the following:

1. An empty space is in Gβ.

2. A line of identity is in Gβ.

3. Juxtaposition closure If G1 is in Gβ, . . ., and Gn is in Gβ, then the juxtaposition of these ngraphs, i.e. G1, . . . , Gn, (we write ’G1 . . . Gn’ for juxtaposition) is also in Gβ.

4. Predicate closure If G is in Gβ, then a graph with an n-ary predicate symbol written at thejoint of n loose ends in G is also in Gβ.

5. Cut closure If G is in Gβ, then a graph in which a single cut is drawn in any subpart of Gwithout crossing a predicate symbol is also in Gβ.

6. Branch closure If G is in Gβ, then a graph in which a line of identity in G branches is also inGβ.

There are two points remarkable in this definition:

3.2. PROBLEMS WITH EXISTENTIAL GRAPHS 41

1. Although some mathematical terms are used, the definitions are formulated more or less incommon spoken language and cannot be seen as mathematical definitions.

2. EGs are considered to be graphical entities (this can particularly seen in the cut closure rule forBeta graphs).

This approach, particularly the two points mentioned above, yields different kinds of problems whichshall be elaborated in this section. We start with problems caused by the use of common language.

First of all, many important technical terms are defined either in an insufficient way or not at all. Forexample, the terms sentence symbol, juxtaposition or single cut (this holds already for Shin’s definitionof Alpha graphs) as well as the terms lines of identity, loose ends or branching of LIs are not defined.Even if we have some pre-knowledge on terms like ‘single cut’ (e.g. we know that a single cut is a closed,double-point-free curve on the plane) or LIs, these definitions leave some issues open. E.g., is it notclear whether two cuts may touch, cross, intersect, or partly overlap, or whether a LI may terminateon a cut. For example, we might ask which of the following diagrams are well-defined diagrams of Betagraphs:

P PQ P Q

Examining the first three examples, in Shin’s book we do not find any example of an Beta graph wherea LI terminates on a cut. But, in contrast, this case is explicitly investigated in Peirce’s manuscriptsor in the book of Roberts. The fourth example is not explicitly excluded by Shin, but it is implicitlyexcluded based on the background a reader should have of EGs. Considering the fifth example, Peirceused to draw to nested cuts, i.e., scrolls, as follows: . So it seems that a touching of cuts is allowed.But we can raise the question whether scrolls should be handled as own syntactical devices, or whetherPeirce’s drawing is a sloppy version of two nested cuts which do not touch, i.e. of . So we haveto make a decision whether cuts may touch or not.

Answering these question is not only about deciding whether a diagram is an EG or not. It is evenmore important to have rigor definitions for all technical terms when transformation rules, e.g. therules of a calculus, are applied to EGs. An important example for this is the in most publicationsundefined term subgraph. A rule in the calculus allows us to scribe a copy of a subgraph in the samecut (this is a special case of the iteration-rule), which occurs in the treatises of Peirce, Shin, Roberts,and later on in this paper.

To get an impression of the problems, we rai-se some simple questions on subgraphs. Con-sider the Alpha graph on the right:

Gα := A AB

In order to know how the iteration-rule can be applied, it must be possible to answer the following

questions: Is B a subgraph of Gα? Is A A a subgraph of Gα? Do we have one

or two subgraphs A of Gα (this is a question which corresponds to the distinction betweensubformulas and subformula instances in FOPL)?

For Beta, it is important to know how LIs arehandled in subgraphs. Consider the followingBeta graph:

Gβ := QPR

We might ask which of the following diagrams are subgraphs of Gβ:

QPR

Q PR

QPR


Shin (and other authors) does not offer a definition for subgraphs: The answer of the questions aboveis left to the intuition of the reader. From the discussion above, we draw a first conclusion:

Thesis 1: The definitions of Shin (and other authors) are insufficient for a precise under-standing and handling of existential graphs.

If EGs are considered as graphical entities, a new class of difficulties has to be coped with. Consideragain Gα. Remember that the iteration-rule should allow us to draw a copy of the subgraph A intothe outer cut. But if we want to understand EGs and subgraphs as (graphical) diagrams, then this isobviously not possible, because in the outer cut, there is simply not enough space left for another copyof A . But, of course, this is not intended by the rule, and everybody who is familiar with EGs will

agree that A A AB is a result of a valid application of the iteration-rule. Why that? The

idea behind is that we may change the shape of LIs or cuts to a ’certain degree’ without changing themeaning of an EG. For this reason it is evident that any attempt which tries to define EGs as purelygraphical entities runs into problems.

For a discussion of the term ’certain degree’, consider the three Alpha graphs in Figure 3.1. From

A AB A AB A AB

Abbildung 3.1: Diagrams of Alpha graphs

the left to the right, we decrease the size of the outer cut. Thus there are obviously visual differencesbetween these three diagrams. The question is whether the differences between the first two diagramsare comparable to the differences between the last two diagrams. We have already seen that the shapeof a cut is – in some sense – of no relevance. The only thing we have to know is which other items ofa graph are enclosed by the cut and which are not. Thus we see that the first two diagrams are (insome sense) the same graph, particularly they have the same meaning. In contrast to that the thirddiagram has a different meaning and has therefore to be treated differently.

If we – due to the visual differences – treat the first two diagrams to be syntactically different, wewould get a syntax which is much too fine-grained. Any kind of equivalence between graphs wouldbe postponed to the semantical level. Furthermore, we would need transformation rules which allowto transform the first graph into the second graph (and vice versa). This syntax would become verycomplicated and nearly unusable. Thus we see that any appropriate syntax should not distinguishbetween the first two diagrams.

Now the question arises which properties of the first two diagrams cause us to identify them. Shouldwe syntactically identify graphs when they have the same meaning? This would inappropriately mixup syntax and semantics. For example, the empty sheet of assertion and the graph have thesame meaning, but they should obviously be syntactically distinguished.

In defining a reasonable syntax for the graphs, we see that we have to prescind from certain graphicalproperties of the diagrams (e.g. the form of a cut), while other properties are important (e.g. thenumber of cuts and other items, or whether an item of the diagram is enclosed by a cut or not).Particularly, EGs should not be understood as graphical entities at all. Instead of this, we haveto distinguish between graphs and the diagrams which represent the graphs. This is according toPeirce’s view. He says: ’A graph [. . .] is a symbol, and, as such, general, and is accordingly to bedistinguished from a graph-replica.’ Thus, Peirce distinguishes between graphs, which are so-to-speak

3.3. THE FIRST APPROACH TO DIAGRAMS 43

abstract structures, and their representations. Due to this understanding, the first two diagrams inFigure 3.1 are not different graphs with the same meaning, but different representations, i.e., diagrams,of the same graph, and the third diagram is a representation of a different graph. Peirce explicitly saidthat arbitrary features of the diagrams may vary, as long as they represent the same diagram. At thebeginning of [Pe03] he says:

Convention No. Zero. Any feature of these diagrams that is not expressly or by previousconventions of languages required by the conventions to have a given character may bevaried at will. This convention is numbered zero, because it is understood in all agreements.

For LIs, he says even more explicit in [Pe03] that ‘its shape and length are matters of indifference.’

The distinction between graphs and graph-replicas obviously corresponds to the distinction betweentypes (graphs) and tokens (graph replicas), as it is known from philosophy. The type-token issue if farfrom being settled; nonetheless, this important distinction helps us to draw our next conclusion:

Thesis 2: EGs should not be defined as graphical entities. Instead of that, we need adefinition of EGs which copes exactly the crucial features of EGs, and the diagrams shouldbe understood as (mere) representations of an underlying EG.

Roughly sketched, we now have the following situation:

Type

Token

Ex. Graph

Ex. Graph Replica

Math. Structure

Diag. Represent.

Semiotics Peirce︸︷︷︸︸︷︷︸︸︷︷︸

This Paper

represents represents represents

corresponds to

corresponds to

corresponds to

corresponds to� -

� -

� -

� -

666

3.3 The First Approach to Diagrams

One of the most important features of mathematics is its preciseness. The preciseness of mathematicsis based on a very strict understanding of mathematical definitions and proofs. We have seen thatthe informal definitions of EGs lead to problems in their understanding and handling. I claim thatmathematics is the best language to cope with problems of these kind, i.e.:

Thesis 3: Mathematics provides the highest level of precision available for definitions andproofs.

Thus, in my view, mathematics turns out to be the best instrument for coping the problems discussed inSec. 3.2. Particularly, EGs should be defined as mathematical structures (and these structures prescindcertain graphical features from diagrams), and the diagrams are representations for these structures.Nonetheless, the last thesis raises the question whether the graph replicas, i.e., the diagrams of EGs,should be defined mathematically as well. This approach shall be discussed in this section.

Let us assume we want to define the graphical representations of Alpha or Beta graphs mathematically.Then we would have two different kinds of objects: Mathematical structures which model EGs, and


mathematical structures which model the representations of EGs, i.e., the diagrams. Let us call thefirst structures type-structures and the second structures token-structures. In finding a definition forthe token-structures, we have two fundamental problems to cope with: First to find a definition forthe token-structures which encodes the informally given diagrams as best as possible. Secondly, wehave to show how the type-structures are represented by the token-structures. It should be possibleto show that each token-structure represents uniquely a type-structure, and that each type-structureis represented by at least one token-structure. Let us call these two principal problems representationproblem.

An obvious approach is to model the lines of an EG (i.e., the cuts and the LIs) as families of curves inthe Euclidean plane R2. For example, we can model each LI by a smooth, double-point-free curve andeach cut by a by a smooth, double-point-free and closed curve.2 Consider the fist two graphs of Figure3.1. They are two different tokens of the same type. Diagrams like these shall be called type-equivalent(this term is adopted from [HS02]).

If we define type-equivalence, we have to refer to the relationship between types and tokens. But thediagrams can be compared directly as well. If we consider again the first two graphs of Figure 3.1, wesee that we have mappings from the cuts resp. the occurences of propositional variables from the firstgraph to the second which fulfill certain conditions. For example, the mappings are bijective and thepreserve some entailment-relations (e.g. if an occurence of a propositional variable or a cut is enclosedby a cut, then this holds for the images as well). In some sense, we can say that the first graph canbe topologically transformed into the second graph. Graphs like this shall be called diagrammaticallyequivalent (again, this term is adopted from [HS02]). If we have found adequate definitions for thetype- and token-structures as well as for the relation ‘a token-structure represents a type-structure’, itshould be mathematically provable that being type-equivalent and being diagrammatically equivalentmeans the same.

In any description of the diagrams, particularly if we provide a mathematical definition for them, wehave to decide some of the bordercases we have discussed in Sec. 3.2. For example, we have to decidewhether (and how often) LIs may touch cuts, or whether cuts may touch or even intersect each other.But in no (reasonable) mathematical definition, we can encode all graphical properties of a diagramdirectly (e.g. by curves). This is easiest to see for letters or words, i.e. the occurences of propositionalvariables in Alpha graphs or for the relation names in Beta graphs. Of course the location of theoccurence of a propositional variable in an Alpha graph is important, but neither the size or the fontof the propositional variable will be of relevance. Similar considerations hold for relation names inBeta graphs. As the shape of propositional variables or relation names should not be captured bythe definition of the diagrams, it is reasonable to handle these items in a different way. The questionarises how much of the properties of these items has to captured by a definition of the diagrams. Forexample, the occurences of propositional variables in an Alpha graph could be modelled by points orspots of the Euclidean plane to which we assign the variables. We see that even in the definition forthe diagrams, we have to prescind certain graphical features from diagrams.

The order of the LIs which are attached to a relation name is important as well. Consider the followingthree graphs:

Cat on Mat Cat on MatCat on Mat1 2 12

2It should be noted that Peirce’s understanding of EGs depends on his understanding of the continuum, and thisunderstanding is very different from the set R. Nevertheless a mathematization of the diagrams as a structure of lines andcurves in R2 is convenient as R2 is the standard mathematization of the Euclidean plane in contemporary mathematics.

3.3. THE FIRST APPROACH TO DIAGRAMS 45

The first graph would be intuitively read as ‘a cat is on a mat’. But the relation ‘on’ is not symmetric,thus if we have two objects in relation ‘on’, we have to make clear which of these objects comes first.This is done by labelling the LIs which are attached to the relation name. So, the second graph hasthe same meaning as the first graph, while the meaning of the third graph is different: ‘A mat is on acat’. The first graph is intuitively understood right for the following reason: We can read read it likea text from left to right to get the meaning a cat is on a mat’ which seems – due to our knowledgeof the world – much more natural than the alternative meaning ‘a mat is on a cat’. How should

onMat Cat be read?

These problems we discussed above, i.e., how the representation of propositional variables or relationnames is handled, or how we can mathematically describe that LIs are attached to a relation name,may seem minor. Nonetheless, it is worth to note that – similar to a definition of the type-structures– in any (reasonable) definition of the token-structures, we have to prescind from certain graphicalproperties the diagrams.

On the other hand: If we try to capture graphical properties of diagrams, some of the items of adiagram will probably be overspecified. For example, how should a simple line of identity – i.e.,– be modelled mathematically? We already said that LI could be modelled by a curve in the Euclideanplane. But when a diagram is given, it is usually drawn without providing a coordinate system. Thus,which length should this curve have? Where in the Euclidean plane is it located? Again we see thatwe cannot capture a diagram exactly by a mathematical definition.

Finally, it is worth to note that we have a couple of (unconscious) heuristics in drawing diagrams forEGs. A simple example is that pending edges should be drawn ‘far away enough’ from any relation-signs. To see this, consider the following diagrams:

P Q QP QQ PP

The leftmost diagram should be understood as ‘There is thing which is P which is in relation Q toanother thing’, The rightmost diagram should be understood as ‘There is thing which is P and thereis thing which is Q’. But the meaning of the diagrams in the middle is not clear. So, one will avoiddrawing diagrams like these.

Similar considerations have to be taken into account if we think about how the diagrams are handledfurther. For example, we have to be careful in the definition of the relation ‘being diagrammaticallyequivalent’. To see this, consider the following simple example which consists of two triples of diagrams:

, , and , , .

Peirce treated point on a cut to be placed outside a cut. Thus the first three diagrams are in Peirce’s un-derstanding different representations of the same graph, while the last three diagrams are pairwise nottype-equivalent. Hence a good definition should yield that the first three graphs are diagrammaticallyequivalent, while the last three graphs are not.

Another heuristic is to draw a diagram as simple as possible. Furthermore, although we have seen thatneither the size or the font of the propositional variable or a relation name will be of relevance, it isclear that the choice of a font and its size is not arbitrary if a diagram is drawn in a convenient way.This should became clear with the following three diagrams:


smallbluesmallblue blue small

Although all diagrams are representations of the same graph (with the meaning ‘there exists somethingwhich is blue, but not small), it is clear that the left-most diagram is the best representation of thesethree diagrams. Conventions like these cannot by captured by any mathematical definition.

Moreover, we have to think how any operations with graphs (i.e., with the type-structures) are reflectedby their representations. Examples for operations are the juxtapostion of graphs or all transformationrules of a calculus. Shall these operations be defined on the type- or on the token-level? The discussionin Sec. 3.2 (see the discussion of Figure 3.1) shows that a definition on the type-level is more convenient.Nonetheless the question remains how a operation on the type-level is represented on the token-level.

Remember that the reason for finding mathematical definitions for diagrams was to solve the re-presentation problem. We wanted to grasp the distinction between non well-formed and well-formeddiagrams, as well as the relationship between graphs and their diagrams, as best as possible. We havealready seen that we cannot capture all graphical features of a diagram by a mathematical definition(the more graphical properties are encompassed by a definition, the more technical overhead has tobe expected). Now the final question is how a mathematically defined diagram is related to a concretedrawing of a diagram on a sheet of paper. This is a crucial last step from mathematical objects toobjects of the real world. Thus, even if we provide mathematical definitions for the diagrams, westill have a representation problem. The initial representation problem between mathematically de-fined graphs and mathematically defined diagrams has shifted to a representation problem betweenmathematically defined diagrams and diagrams – i.e., drawings – in the real world. A mathematicaldefinition for diagrams can clarify a lot of ambiguities, but it cannot solve the representation problemfinally.

3.4 Linear Representations of First Order Predicate Logic

In the last section we have raised some questions concerning the representation problem, and wehave seen that mathematics alone is not enough to solve these problems. It is likely the often unclearrelationship between diagrams and represented structures which causes mathematicians to believe thatdiagrams cannot have a proper place in mathematical argumentation, esp. proofs. It is argued thatonly a symbolic system for logic can provide the preciseness which is needed in mathematical proofs(for a broader discussion of this see [Sh01]). It seems that the problems we have discussed in the lastsection simply do not occur in mathematics, esp. mathematical logic. In this section we will have acloser look on this. We start with a definition of the well-formed formulas of FOPL.

Definition 3.3 The alphabet for first order logic consists of the following signs:

• Variables: x1, x2, x3, . . . (countably many)

• Relation symbols: R1, R2, R3, . . . (countably many). To each predicate symbol Ri we assign anarity ar(Ri) ∈ N.

• Constant symbols: c1, c2, c3, . . . . . . (countably many)

3.4. LINEAR REPRESENTATIONS OF FIRST ORDER PREDICATE LOGIC 47

• Connectives: ∧,¬,∃

• Auxiliary Symbols: ., , , (, )

Definition 3.4 The formulas of FOPL are inductively defined as follows:

1. Each variable and each constant name is a term.

2. If R is a predicate symbol with arity n and if t1, . . . , tn are terms, then f := R(t1, . . . ,tn) is aformula.

3. If f ′ is a formula, then f := ¬f ′ is a formula.

4. If f1 and f2 are formulas, then f := (f1∧f2) is a formula.

5. If f ′ is a formula and α is a variable, then := ∃α.f ′ is a formula.

It is easy to capture the idea behind this definitions: First, we fix a set of signs, and a formula is asequence of these signs which has been composed according to certain rules.

Let us consider the following two strings (the relation name R1 has arity 2):

∃x1.∃x2.R1(x1, x2)∃x1. ∃x2. R1(x1, x2)

Although these two strings are written in different places and although they look slightly different,they clearly represent the same formula. For our considerations, it is worth to raise the question whichsteps a reader has to pass from the perception of a string to the identification of a formula whichis represented by the string. Roughly spoken, if a reader reads the two strings above, she passes thefollowing steps:

1. The region on the paper (the blackboard, . . .) must be identified where the representation of theformula is written on. In the example above, this is possible because we have written the twodifferent strings into two different lines.

2. In this region, we must be able to identify representations of the signs which may occur ina formula (e.g. the sign ‘∃’, which appears twice, or the sign ‘R1’, which appears only once).Nothing else may occur.

3. The representations of the signs must be assembled in a way such that we are able to identifytheir ordering on the region. That is: We must be able to identify the sequence. For our examples,we identify the ordering of the instances of signs by reading them from left to right.

4. Finally, after we have reconstructed the sequence of signs (internally), we can check whether thissequence is a well-defined formula, i.e., whether it is composed with the rules of Definition 3.4.

In the following, we will use the label (∗) to refer to these four steps. The process (∗) yields the sameresult for the two strings above: In both cases, the lines represent the same sequence of signs, whichis in fact a well-formed formula. Thus every mathematician would (hopefully) agree that these twostrings represent the same (well-defined) formula.


We want to stress that the process of perceiving a representation of a formula is not ‘deterministic’:It is not clear without ambiguity for each string whether it represents a formula or not. To see this,consider the following strings (the ‘type-setting problems’ are intended). The question is: Which ofthese strings represents a well-defined formula?

∃x1∃.x2.R1(x1,x2) (3.1)

∃x1

.∃x2

.:

R1(x1

,x2

) (3.2)

∃x1.∃♥.R1(x1, x2) (3.3)),∃..R1x1∃x1(x2x2 (3.4)∃x1 .∃x2 .R1(x1, x2) (3.5)∃x1.∃x2.R1(x1,x2) (3.6)∃x1.∃x2.R1(x1, x2) (3.7)∃x1. ∃x2 .R1( x1, x2) (3.8)∃ x1. ∃x2.R1( x1, x2) (3.9)

In line 3.1, we are neither able to identify the signs, nor to identify their ordering. That is we cannotpass the steps (2) and (3) of (∗), thus this line does not represent a formula. In line 3.2, we are ableto identify the signs, but we are not able to identify their ordering. That is we cannot pass the step(3) of (∗), thus this line does not represent a formula as well. Moreover, it may be doubted whetherstep 1 of (∗) can be passed without problems. In line 3.3, we are able to identify the signs, but oneof these signs does obviously not belong to our alphabet of first order logic, thus this line does notrepresent a formula. In line 3.4, we are able to identify the signs, all of them belong to to our alphabetof first order logic, and we are able to identify their ordering, that is we reconstruct a sequence ofsigns of our alphabet. But we see that this sequence is not build according to our rules (we cannotpass the step (4) of (∗). ). Thus this line does not represent a formula. In the remaining lines, it is notuniquely determined whether the lines represent a formula or not. In line 3.5, the font for the variableshas changed. In mathematical texts, different fonts are often used to denote mathematical entities ofdifferent kinds, but this is not a general rule. So it depends on the context whether lines 3.5 or 3.6 areaccepted to represent formulas. Using different sizes of a font is usually driven by a specific purpose.The same holds for the use of significantly different distances between signs. It is hardly conceivableto find a purpose for using different font sizes or significantly different distances in formulas. Thus itis possible, but not sure, that the lines 3.7–3.9 are not accepted by a mathematician to represent aformula.

In standard books on logic, usually only the last step of (∗) is discussed. The main reason for thisis the following: The linear notion of formulas corresponds the way ordinary text is written: Text isassembled of letters which are written side by side and which are read from left to right. As we areused to read texts, we are trained as well to read strings which shall represent formulas. Thus the firstthree steps of (∗) are unconsciously executed when we perceive a representation of a formula.

But as soon we perceive an unfamiliar representation (like in the strings 3.1-3.9), we become awareof the whole process described by (∗). We realize that mathematical structures need representations,and in mathematics we have a clear separation between structures and their representations. Therepresentations rely on conventions, either implicit or explicit, based on common cultural backgroundas well as on mathematical socialization, and they are not fully explicated. Nonetheless, this usuallyposes no problems: Although these conventions can never be fully explicated, as long as we providerepresentations of mathematical structures in accordance to these conventions, they are strong enoughto provide a secure transformation from the external representation of a structure (e.g. on a sheet ofpaper or on a blackboard) into an internal representation of any mathematician, i.e., they refer to the

3.5. THE SECOND APPROACH TO DIAGRAMS 49

represented structures in a clear and and non-ambiguous way (as Barwise says in a broader discussionof representations: ’Every representation indicates a genuine possibility’ [Ba93]).

The next thesis claims that this approach can be adopted for diagrammatic systems.

Thesis 4: In a mathematical theory, the mathematical structures need representations. Arigor mathematical theory can be developed without providing mathematical definitions forthe representations. Instead of that, it is sufficient if we have conventions – either implicit orexplicit — which describe the representations, as well as the relationship between structuresand their representations, in a clear and non-ambiguous way.

3.5 The Second Approach to Diagrams

In Sec. 3.2, we have argued that in literature, EGs are described in an informal and insufficient way(Thesis 1). Furthermore, we should not mix up graphs and their representations. Particularly, EGsshould be defined as formal structures and not as graphical entities (Thesis 2). Thesis 3 claims thatmathematics is the best method to describe formal structures. From this we can conclude that EGsshould be defined as mathematical structures. Nonetheless, we haven’t already solved the questionwhether the representations should be defined mathematically as well.

In Sec. 3.3, we presented some difficulties when we try to define the diagrams mathematically. Thearguments of Sec. 3.3 are not strong enough to claim that a mathematical definition of diagrams willalways run into problems. In contrast: Finding a appropriate mathematical definition for the diagramsshould clarify the points mentioned in Sec. 3.2. That is a mathematical definition would make clearwithout ambiguities which diagrams should be considered to be well-formed diagrams of EGs, andwhich not. Furthermore, the relation between graphs and their representations can be elaboratedmathematically as well. But providing mathematical definitions for the diagrams may result in atechnical overhead or overspecification of the formalization of EGs and their representations, andnone mathematical definition can solve the representation problem finally.

On the other hand, as seen in Sec. 3.4, mathematical logic is a mathematical theory, although therepresentations of the types in logic, i.e., formulas, are not fully explicated, but they rely on differentconventions.

In contrast to the attempt to capture the representations by mathematical definitions, we have seenthat logic is a rigor mathematical theory, although representations are only captured not fully expli-cated conventions. This works because these conventions are mainly based on a common and solidcultural background, namely the form how text is presented. For diagrams, we have a lack of conven-tions.

Thus, in both approaches, we have to provide a set of conventions on how diagrams are written.Particularly for EGs, we have to make clear without ambiguities which diagrams shall be consideredto be well-formed diagrams of EGs. In the first approach, these conventions are provided informallyin common language. In the second approach, these conventions are described by a mathematicaldefinition. Thus, the mathematical definition should capture as best as possible the informally providedconventions of the first approach. The advantage of a mathematical definition is its preciseness, butwe gain this preciseness for the cost of a technical overspecification of the diagrams. Furthermore, wehave seen that a mathematical definition cannot capture exactly the diagrams.

As already said above, arguments like these are not strong enough to generally discard mathematicaldefinitions for the token-structures. It has to be estimated whether a mathematical definition is really


needed, or whether the conventions for drawing diagrams and for the relationship between representingdiagrams and represented structures can be captured sufficiently by descriptions in common language.If the latter is possible, we are able to gain the rigorousness and preciseness of a mathematical theorywithout a technical overspecification of the diagrams. Thus, in this case, I claim that this approachshould be preferred.

This approach has to be applied to Peirce’s Alpha graphs, i.e.:

We have to define EGs as mathematical structures. Particularly, we distinguish bet-ween EGs, which are abstract mathematical structures, and their graphical representations(diagrams). We have to provide a set of conventions for drawing a diagram of an EG, andwe have to describe the relationship between EGs and their diagrams. Due to these conven-tions and descriptions, we will show that each diagram uniquely determines an representedEG, and that each EG can be represented by a diagram.

We have already mentioned that the Alpha system of EG is said to be equivalent to propositionallogic, the Beta system of EG is said to be equivalent to first order predicate logic. In fact, we findgood arguments for that in the books of Zeman, Roberts or Shin. But, as EGs are described informaland insufficiently, these argumentation cannot be seen as (mathematical) proofs. With our approach,we can solve these problems: If we define EGs as mathematical structures, we are now able to provemathematically the equivalences between the Alpha system and the Beta system to propositional andfirst order predicate logic, respectively.

In the following section, we exemplify this approach for Alpha graphs. Of course this is a fairlysimple example. Its advantage is that we can work out the definitions of Alpha and the proof ofthe equivalence to propositional logic on a couple of pages. Its disadvantage is that the problems wediscussed in Sec. 3.2 appear much stronger in Beta, thus the benefit of a mathematical foundation ofgraphs cannot be seen that clearly for Alpha. An elaboration of this approach for the Beta system isin progress (a first step towards Beta can be found in [Da03]).

Literatur:

• J. Howse, F. Molina, S. Shin, J. Taylor: On Diagram Tokens and Types

• F. Dau: Types and Tokens for for Logic with Diagrams

http://cmis.mis.brighton.ac.uk/Research/vmg/index.htm

Literaturverzeichnis

[Ba93] John Barwise: Heterogenous reasoning, in G. W. Mineau, B. Moulin, J. F. Sowa (Eds.): Con-ceptual Graphs for Knowledge Representation. LNAI 699, Springer Verlag, Berlin–New York2000, 64–74.

[Bu91] R. W. Burch: A Peircean Reduction Theses: The Foundations of Topological Logic. Texas TechUniversity Press, 1991.

[Da00] F. Dau: Negations in Simple Concept Graphs, in: B. Ganter, G. W. Mineau (Eds.): ConceptualStructures: Logical, Linguistic, and Computational Issues. LNAI 1867, Springer Verlag, Berlin–New York 2000, 263–276.

[Da01] F. Dau: Concept Graphs and Predicate Logic, in: H. S. Delugach, G. Stumme (Eds.): Con-ceptual Structures: Broadening the Base. LNAI 2120, Springer Verlag, Berlin–New York 2001,72–86.

[Da02] F. Dau: An Embedding of Existential Graphs into Concept Graphs with Negations. In: D. Cor-bett, U: Priss (Eds.): Conceptual Structures: Integration and Interfaces, LNAI, Springer Verlag,Berlin–Heidelberg 2002.

[Da03] F. Dau: The Logic System of Concept Graphs with Negation (And Its Relationship to PredicateLogic). LNAI, Vol. 2892, Springer, Berlin–Heidelberg–New York, 2003.

[Ha95] E. M. Hammer, Logic and Visual Information. CSLI Publications, Stanford, California, 1995.

[Ha98] E. M. Hammer, Semantics for Existential Graphs. Journal Philosohpical Logic, Vol. 27, 1998,489–503.

[HS02] J. Howse, F. Molina, S. Shin, J. Taylor: On Diagram Tokens and Types

[Pe98] C. S. Peirce: Reasoning and the Logic of Things. The Cambridge Conferences Lectures of 1898.Ed. by K. L. Kremer, Harvard Univ. Press, Cambridge 1992.

[PS09] C. S. Peirce, J. F. Sowa: Existential Graphs: MS 514 by Charles Sanders Peirce with commen-tary by John F. Sowa

http://users.bestweb.net/∼sowa/peirce/ms514.htm

[Pe03] C. S. Peirce: Existential graphs. 1903. Partly published in the collected papers of Peirce.Complete german translation in:

Helmut Pape: Charles Sanders Peirce: Phanomen und Logik der Zeichen. Suhrkamp Taschen-buch Wissenschaft, 1983.

[Ro73] D. D. Roberts: The Existential Graphs of Charles S. Peirce. Mouton, The Hague, Paris, 1973.

51

52 LITERATURVERZEICHNIS

[Ro92] D. D. Roberts: The Existential Graphs. Computers Math. Applic., Vol. 23, No. 6–9, 1992,639–63.

[Sh94] S. Shin: The Logical Status of Diagrams. Cambridge University Press, 1994.

[Sh99] S. Shin: Reconstituting Beta Graphs into an Efficacious System. Journal of Logic, Languageand Information, Vol. 8, No. 3, July 1999.

[Sh01] S. Shin: The Iconic Logic of Peirce’s Graphs. Bradford Book, Massachusetts, 2002.

[So84] J. F. Sowa: Conceptual Structures: Information Processing in Mind and Machine. The SystemProgramming Series. Adison-Wesley, Reading 1984.

[So92] J. F. Sowa: Conceptual Graphs Summary, in: T. E. Nagle, J. A. Nagle, L. L. Gerholz,P. W. Eklund (Eds.): Conceptual Structures: current research and practice, Ellis Horwood,1992, 3–51.

[So97] J. F. Sowa: Logic: Graphical and Algebraic, Manuskript, Croton-on-Hudson 1997.

Documents

Mathematische Logik mit Diagrammen - dr-dau.net · Venn modiﬁzierte Eulers System zu einem ausdrucksst¨arkeren System. Venn hat aber keinen Venn hat aber keinen Mechanismus bereitgestellt,