Hochschule RheinMain Algorithmen und Datenstrukturen Sommer 2015 Informationsblatt – Symbole 31. März 2015 Motivation Um Sachverhalte klar zu beschreiben werden häufig Symbole verwendet, die es erlauben Aussagen formal, präzise und nachvollziehbar zu treffen. Eine natürlichsprachliche Formulierung vieler Aussagen mag eventuell leichter zu lesen sein, bietet aber leider oft einen Interpretationsspielraum. Nur durch die Verwendung von Symbolen mit klar festgelegter Bedeutung sind formal nachvollziehbare Aussagen möglich. Wir werden einige Symbole und deren Verwendung anhand eines Beispiels kennen lernen und listen danach die wichtigsten Symbole und deren Bedeutung auf. Damit sollte hoffentlich “Was ist denn das umgedrehte A (∀)?” und “Sie haben das E falsch geschrieben (∃)” der Vergangenheit angehören. Ein Beispiel – Euklid Wir üben formale Aussagen anhand der Definition und Berechnung des größten gemeinsamen Teilers. Der Algorithmus von Euklid (ca. 300 v. Chr.) berechnet den größten gemeinsamen Teiler (ggT ) für zwei positive ganze Zahlen (natürliche Zahlen) x und y. Eine natürliche Zahl z = ggT (x, y) ist der größte gemeinsame Teiler zweier Zahlen x und y, wenn z die Zahl x teilt, z die Zahl y teilt und keine andere Zahl existiert, die x und y teilt und größer als z ist. Diese natürlichsprachliche Beschreibung übersetzen wir nun in eine formale Aussage. z = ggT (x, y) gdw x, y, z ∈ N ∧ z | x ∧ z | y ∧ @z 0 : z 0 > z ∧ z 0 | x ∧ z 0 | y (1) Die formale Aussage (1) erscheint (auf den ersten Blick) schwierig zu lesen. Dies ist aber nur Gewöhnung. Im Prinzip liest sich die Aussage genau so wie die natürlichsprachliche Formulierung. Ein Zahl z ist der größte gemeinsame Teiler von zwei Zahlen x und y (z = ggT (x, y)) genau dann, wenn • x, y und z natürliche Zahlen sind (x, y, z ∈ N) und (∧) • z ein Teiler von x ist (z | x) und (∧) • z ein Teiler von y ist (z | y) und (∧) • keine andere Zahl z 0 existiert (@z 0 ), so dass (:) – z 0 echt größer z ist (z 0 > z) und (∧) – z 0 auch die Zahl x teilt (z 0 | x) und (∧) Prof. Dr. Peter Barth Design Informatik Medien 1 Medieninformatik Hochschule RheinMain Algorithmen und Datenstrukturen Sommer 2015 – z 0 auch die Zahl y teilt (z 0 | y) Wir haben bisher nur die Tatsache, dass eine Zahl der größte gemeinsame Teiler zweier Zahlen ist, formuliert. Zum Berechnen müssen wir uns weitere Eigenschaften zunutze machen. Der Algorithmus von Euklid nutzt die folgenden Zusammenhänge. • Der größte gemeinsame Teiler von x und y ist gleich dem größten gemeinsamen Teiler von y und x. • Der größte gemeinsame Teiler von x und y ist gleich dem größten gemeinsamen Teiler von x − y und y, wenn x größer als y ist. Wieder formal formuliert erhalten wir folgendes. ∀x, y ∈ N : ggT (x, y) = ggT (y, x) (2) ∀x, y ∈ N, x > y : ggT (x, y) = ggT (x − y, y) (3) Diese formale Aussage können wir wieder zurückübersetzen in natürlichsprachliche Aussagen. • (2) Für alle natürlichen Zahlen x und y (∀x, y ∈ N) gilt, dass der größte gemeinsame Teiler von x und y gleich dem größten gemeinsamen Teiler von y und x ist (ggT (x, y) = ggT (y, x)). • (3) Für alle natürlichen Zahlen x und y, wobei x echt größer als y ist (∀x, y ∈ N, x > y) gilt, dass der größte gemeinsame Teiler von x und y gleich dem größten gemeinsamen Teiler von x − y und y ist (ggT (x, y) = ggT (x − y, y)). Um daraus einen lauffähigen Algorithmus zumachen, braucht man noch ∀x ∈ N : ggT (x, x) = x (4) was als Abbruchbedingung dient und etwas nachdenken, wann man welche der Gleichungen (2), (3) oder (4) in welche Richtung anwendet. Dies soll uns hier aber nicht weiter interessieren. Wir haben also gesehen, wie man natürlichsprachliche Aussagen formalisiert und dass man diese auch einfach wieder zurückübersetzen kann. Vorteile der formalen Notation sind die kompaktere Darstellung und eine klare Bedeutung der verwendeten Symbole. Im folgenden sammeln wir einige wichtige, häufig benutzten Symbole und ein paar typische Aussagen, die diese Symbole verwenden. Prof. Dr. Peter Barth Design Informatik Medien 2 Medieninformatik Hochschule RheinMain Algorithmen und Datenstrukturen Sommer 2015 Übersicht häufiger Symbole und Abkürzungen Mengen Symbole und unendlich Symbol N Z Q R C ∞ Bedeutung Menge der natürlichen Zahlen {1, 2, 3, . . .} Menge der ganzen Zahlen {0, 1, −1, 2, −2, . . .} , . . .} Menge der rationalen Zahlen {0, 1, 12 , −1 2 Menge der irrationalen Zahlen√π, . . . Menge der komplexen Zahlen −1, . . . unendlich Einige griechische Buchstaben Werden für alles mögliche verwendet, wie zum Beispiel ten, Funktionen, Mengen, etc. α alpha β beta γ gamma δ delta ε λ lambda ξ xi π pi % rho σ χ chi ψ psi Γ Gamma ∆ Delta Θ Φ Phi Ψ Psi Ω Omega als Bezeichnungen für Konstanepsilon θ sigma ϕ Theta Σ theta phi Sigma Mathematische Symbole Binäre Beziehungen1 Symb. Bedeutung Symb. < echt kleiner > ≤ kleiner oder gleich ≥ | teilt = ⊂ echte Untermenge ⊆ ⊇ Obermenge ∩ ∈ Element von ∈ / Berechnungen Symbol Bedeutung + Addition x , ÷, / Division y P Summe Bedeutung Symb. echt größer 6< größer oder gleich 6≤ gleich 6= Untermenge ⊃ Schnittmenge ∪ nicht Element von ] Symbol Bedeutung Symbol ∗,√ ·, × Multiplikation − Wurzel xy Q Produkt bxc, dxe Bedeutung nicht kleiner weder kleiner noch gleich ungleich echte Obermenge Vereinigungsmenge disjunkte Vereinigung Bedeutung Subtraktion Exponent nächstkleinere, -größere Ganzzahl Variablen und Indizes x, y, z meist Variablen a, b, c meist Konstanten xi das i.te aus einer Sequenz xij das i.te aus einer Sequenz und aus dieser Sequenz das j.te 1 Negationen per durchstreichen ist üblich für die meisten binären Symbole Prof. Dr. Peter Barth Design Informatik Medien 3 Medieninformatik Hochschule RheinMain Algorithmen und Datenstrukturen Sommer 2015 Symbole für logische Aussagen Quantoren Symbol Bedeutung ∀ für alle ∃ es existiert @ es existiert kein Logische Operatoren Symbol Bedeutung ∧ und ∨ ¬ 6 gdw, ⇔ oder nicht nicht genau dann wenn ⇒ impliziert Beispiel ∀n ∈ N : n2 ≥ n Übersetzung Für alle natürlichen Zahlen n ist Ihr Quadrat größer gleich sie selbst ∃n ∈ N : n2 = n Es gibt eine natürliche Zahl n deren Quadrat mit sich selbst identisch ist ∀n > 2 @ a, b, c, n ∈ N : Der (inzwischen) Satz von Feran + b n = c n mat. Beispiel n=1∧n∈N Pn ∨n<0 i = n·(n+1) 2 ¬π∈Q π 6∈ Q ∀n ∈ N : n2 = n gdw n = 1 i=0 ∀z ∈ Z : z = 1 ⇒ z 2 = z ∀z ∈ Z : z 2 = z ⇒ z = 1 Übersetzung n ist die Zahl 1 und n ist eine natürliche Zahl Gauß oder n < 0 π ist keine rationale Zahl π ist keine rationale Zahl Ein natürliche Zahl ist gleich Ihrem Quadrat, genau dann wenn die Zahl 1 ist Wenn eine ganze Zahl 1 ist, dann ist Ihr Quadrat gleich sie selbst Wenn eine ganze Zahl im Quadrat sie selbst ist, dann ist es 1 (diese Aussage ist natürlich falsch! 02 ist auch 0). Definition von Mengen Mengen werden definiert durch {Ausdruck | Bedingung}. Die definierte Menge beinhaltet genau die Elemente, deren Wert dem Ausdruck entspricht, falls die Bedingung gilt. Beispiel Bedeutung {x | x ∈ N ∧ @y ∈ N, 1 < y < x : y|x} Die Menge der Primzahlen. {x ∈ N | @y ∈ N, 1 < y < x : y|x} Wieder Primzahlen, man kann die Grundmenge auch an den Ausdruck schreiben. a Rationale Zahlen. Variablen im Ausdruck Q = { b | a ∈ Z, b ∈ N} müssen nicht quantifiziert werden. C = {a + ib | a, b ∈ R, i2 = −1} Komplexe Zahlen. Prof. Dr. Peter Barth Design Informatik Medien 4 Medieninformatik