2. Mathematische und informatische Grundlagen

Mathematische Grundlagen wichtig für Modellierung der Realität und für die Informationsverarbeitung

Grundlagen der • Mengenlehre• Formalen Logik• Graphentheorie

2.1 Mengentheoretische Grundbegriffe Mengen zur Bildung und Selektion von

Geoobjektklassen

Unter einer Menge A versteht man eine Zusammenfassung von bestimmten wohlunterschiedenen Objekten unserer Anschauung oder unseres Denkens zu einem Ganzen; diese Objekte werden Elemente a der Menge A genannt.

Schreibweise: a A "a ist Element der Menge A" b A "b ist nicht Element der Menge A"

Die Festlegung einer Menge A kann erfolgen explizit durch Angabe aller Elemente,

z.B. M = {a, b,..., z}; dies ist nur bei einer endlich grossen Menge möglich.

implizit durch Angabe eines Prädikates, d.h. einer charakteristischen Eigenschaft aller Elemente dieser Menge, z.B. M = { x x Z und x > 0; Z = Menge der ganzen Zahlen } Auf diese Weise kann man auch unendlich grosse Mengen definieren.

Die Anzahl M der Elemente einer Menge Mheisst Kardinalität von M.

Beziehungen zwischen Mengen

• Gleichheit: A = B jedes Element von A ist Element von B und umgekehrt; anderenfalls ist A B

• Teilmenge: A B (x A x B) für alle x A A B A B und A B (echte Teilmenge)

• Transitivität: A B und B C A C

A = B

Spezielle Mengen

• Leere Menge: = { }

• Potenzmenge: P(A) = { X X A } Menge aller Teilmengen von A Beispiel: A={1,2} P(A)={, {1}, {2}, {1,2}}

• Produktmenge (Kartesisches Produkt): A B := {(x,y) x A und y B} Menge aller geordneten Paare (a,b) mit a A und b B

Allgemein: ABC usw.

Mengenalgebraische Verknüpfungen

• Durchschnitt: A B = { x x A und x B} A und B sind disjunkt, wenn A B = Schnittmenge

• Vereinigung: A B = { x x A oder auch x B}Vereinigungsmenge

• Differenzmenge: A \ B = { x x A und x B} "A ohne B"

Einige Gesetze ('Rechenregeln') der Mengenalgebra

• Kommutativität: A B = B A (gilt ebenso für

• Assoziativität: (A B) C = A (B C) (gilt ebenso für

• Distributivität: A (B C) = (A B) (A C); A (B C) = (A B) (A C)

Anwendungsbeispiele

• Zeige alle Biotope, die höchste Schutzpriorität haben

• Zeige alle Straßen, die verkehrsberuhigt aber nicht in Ortschaften liegen

• Zeige alle Waldflächen und Grünflächen in Berlin.

• Zeige alle Waldfläche ohne geschützte die Waldflächen

Relationen

Unter einer Relation R einer Menge M versteht man die Beziehung, die zwischen je zwei Elementen von M besteht oder nicht besteht.

Z.B. a<b, b<c

Eine mittels bestimmter Eigenschaften definierte Teilmenge R XY der Produktmenge X Y heisst eine zweistellige (binäre) Relation R zwischen den beiden Mengen X und Y. Ist (a,b) R, d.h. die Relation R trifft auf (a,b) zu => aRb

Analog definiert man n-stellige Relationen.

• Beispiel 1: "<" ist eine binäre Relation im R2: (x,y) "<" bzw. x < y

• Beispiel 2: "liegt auf" = { (a, b, c) a, b, c G und c ist ein Punkt auf der Geraden g(a, b)} ist eine dreistellige Relation R GGG für Punkte eines 2-dim. Gebietes G.

Relationstypen Äquivalenzrelation

Beispiele:g, h sind parallele Geraden

A, B haben selbe Nationlität a-d = b-c sind differenzgleiche Paare

Mittels Äquivalenzrelationen kann man Partitionen (Klasseneinteilungen) in einer Menge bilden.

Ordnungsrelation

z.B. a < b.

Ordnungsrelationen sind z.B. für das größenmäßige Sortieren von Daten wichtig.

Anwendungsbeispiele

• Sortiere alle Grundstücke entsprechend ihrer Größe / ihres Wertes

• Sortiere die Länder der Erde nach ihren Ausgaben für Bildung im Verhältnis zu Rüstungsausgaben

• Gruppiere die Gewässer entsprechend ihrer Gewässergüte

2.2 Grundbegriffe der formalen Logik

Hauptaufgabe der formalen Logik ist die Unter-suchung des formalen Denkens und Schließens.

Unter einer Aussage versteht man ein natürlich-sprachiges Konstrukt, dem man einen der beiden Wahrheitswerte WAHR (W) oder FALSCH (F) zuordnen kann.

• Bei der logischen Bewertung einer Aussage kommt es nicht auf die Syntax sondern auf die Semantik an. Die Bewertung erfolgt nach dem Prinzip entweder W oder F.

• Eine Verallgemeinerung dieser zweiwertigen Logik stellt die fuzzy-logic dar, nach der Aussagen auch "etwas falsch" und zugleich "etwas wahr" sein dürfen; Sie spielt heute eine wichtige Rolle bei Entscheidungsproblemen (z.B. bei der Zuordnung von Objekten zu Klassen).

Beispiele

"Die Lufttemperatur liegt unterhalb von Null Grad Celsius" ist eine Aussage, die W oder F sein kann.

"Regnet es immer noch?" ist keine Aussage.

• Enthält ein sprachliches Konstrukt anstelle eines konkreten Subjektes nur einen Platzhalter (Variable), so handelt es sich um eine Aussageform.

Beispiel: "X < 0 C" ist eine Aussageform, die keinen Wahrheitswert besitzt.

• Erst nachdem man die Variable X an ein konkretes Subjekt gebunden hat, entsteht eine wahre/falsche Aussage.

Beispiel: "Die Lufttemperatur ist < 0 C" kann W oder F sein.

• Von besonderer Bedeutung sind Aussageformen, die bei jeder Bindung der Variablen eine wahre Aussage ergeben = Tautologien.

• Beispiel: "X < 0C oder X > 0C oder X = 0 C"

Aussagenverknüpfungen

• In der Umgangssprache werden Aussagen auf vielfältige Weise miteinander zu komplexeren Aussagen verknüpft.

Beispiel: "Wenn die Lufttemperatur unter 0C liegt und Niederschlag fällt, dann ist dies Schnee"

• In der formalen Logik begnügt man sich mit einigen wenigen, aber dafür eindeutig bestimmten Verknüpfungsoperationen (Junktoren):

Verknüpfungsoperationen

Verknüpfung Benennungnicht Negationund Konjunktionoder Alternativewenn...,so Implikationgenau dann..., wenn Äuquivalenz

Implikationen sind eine wichtige Grundlage für die Schlussregeln in der Wissensverarbeitung.

Eine Schlussregel ist eine Vorschrift, die angibt, wie man aus wahren Aussagen neue, ebenfalls wahre Aussagen gewinnen kann.

Beispiel:• wenn a < b, so ist 2a < 2b• Wenn Sonnabend ist, will ich frische Brötchen essen. Wenn ich

frsiche Brötschen essen will, muß ich früh zum Bäcker. Also: Wenn Samstag ist, muß ich früh zum Bäcker.

Um die reale Welt besser modellieren zu können, benötigt man neben solchen Formeln der Aussagenlogik noch weitere Operatoren, z.B.:

• All-Quantor x: Für alle x gilt die Aussage P(x)• Existenz-Quantor x: Es existiert mindestens

ein x, für das P(x) gilt

2.3 Grundbegriffe der Graphentheorie

Die Graphentheorie ist eine mathematische Theorie, durch die sich komplexe Sachverhalte sowie räumliche Strukturen und Beziehungen leichter visualisieren und analysieren lassen.

Bedeutung für die Geoinformatik z.B. Abbildung von Straßen-, Kommunikations-

netzen

Ein Graph besteht aus Kanten und Knoten, wobei eine Kante durch zwei Knoten gebildet wird.

Ein Graph ist eine Zusammenfassung zweier Mengen, der Menge X der Knotenpunkte x und der Menge U der Kanten u sowie einer auf U erklärten Funktion f, der Inzidenzfunktion (Inzidenz=Punkt liegt auf Geraden). Diese ordnet jeder Kante u U genau ein geordnetes oder ein ungeordnetes Paar von Knotenpunkten zu; dementsprechend unterscheidet man gerichtete bzw. ungerichtete Graphen.

Zwei Knoten heissen adjazent (benachbart), wenn sie zu einer gemeinsamen Kante gehören; diese beiden Knoten heissen dann inzident zur betreffenden Kante.

Beispiel zur Notation: G = (V, E) mit V = {v1, v2, v3} und E = {e1, e2, e3}, wobei e1 = (v1, v2); e2 = (v2, v3); e3 = (v3, v1)

Eine einfache (aber redundante) Form der DV-adäquaten Darstellung von Graphen mit n Knoten ist die Adjazenzliste

Beispiel: Adjazentliste für abgebildten Graphen:

{ [v1, v2, v3], [v2, v3, v1], [v3, v1, v2] }

v = vertice (Knoten)e = edge (Kante)

Typen von Graphen

• vollständiger Graphwenn alle Knotenpaare adjazent sind

• zusammenhängender Graphwenn für je zwei verschiedene Knotenstets ein Weg von x nach y existiert.

• Gerichteter Graph wenn alle Kanten aus geordneten Knoten-Paaren bestehen, d.h. mit Vorgänger-Knoten und Nachfolger-Knoten.

Typen von Graphen II

Baum-Graphein zusammenhängender, schleifenloser, gerichteter Graph. – Wurzelbaum– Binärbaum

Typen von Graphen III

• Wurzelbaum ist ein Baum, der genau einen Knoten ohne Vorgänger-Knoten besitzt; dieser heisst die Wurzel des Baumes. Alle anderen Knoten besitzen genau einen Vorgänger-Knoten ('Vater').

Ein Knoten, der keinen Nachfolger-Knoten ('Sohn') besitzt, heisst ein Blatt.

In der Informatik werden Bäume stets mit der Wurzel nach oben dargestellt.

Typen von Graphen IV

• Binärbaum, wenn jeder Knoten höchstens zwei Söhne besitzt und diese in linken und rechten Sohn unterschieden werden. Binärbäume spielen eine sehr wichtige Rolle z.B. bei Suchvorgängen.

Anwendungsbeispiele

• Modellierung von Straßennetzen für KFZ-Navigation

• Modellierung von Flußsystemen• Modellierung von Versorgungsnetzen (Wasser,

Gas, Strom)• Berechnung des „Handlungsreisenden-Problem“

(Wegoptimierung)

Aufgaben

Aufgabe 1: Verdeutlichen Sie sich am Beispiel von Fluß-Einzugsgebieten die Teilmengen-Beziehung und die Transitivität dieser Beziehung.

Aufgabe 2: Auf einem Kartenblatt wird die Menge P aller Punkte innerhalb eines Untersuchungsgebietes G betrachtet. Beschreiben Sie formal mit Hilfe des Begriffes der Produktmenge die Menge aller möglichen (horizontalen) Untersuchungsprofile, die nicht die Länge Null besitzen.

Aufgabe 3: Autobahnabfahrt B liegt zwischen Abfahrt A und C. Schreiben Sie dies formal als Relation

Aufgabe 4: Beschreiben Sie mit Hilfe graphentheoretischer Grundbegriffe ein Fließgewässer-System in einem Einzugsgebiet.