Transcript
Institut für Theoretische Informatik
ITI
Dr. J¨ urgen Koslowski
Einfu ¨ hrung in die Logik Aufgabenblatt 1, 2016-04-18
¨ Ubungsaufgabe 6 Eine weitere Logelei zum Warmwerden, vor einer Woche in einer Gruppe aus dem Ged¨achnis nicht korrekt wiedergegeben: Sie sollen in die Zaubererschule von Hogwards aufgenommen werden. Doch neuerdings gibt es neben dem ber¨ uhmten “Sorting Hat” noch eine Aufnahmepr¨ ufung. Dazu zeigt Professor Snape Ihnen und zwei weiteren Kandidaten f¨ unf spitze Zaubererh¨ ute, drei rote und zwei schwarze, und sagt: Ich werde jetzt jedem von Ihnen einen der H¨ ute durch Magie so aufsetzen, dass Sie Ihren ” eigenen Hut nicht sehen k¨ onnen. Die u ute lasse ich verschwinden. Danach m¨ ussen Sie ¨brigen H¨ herausfinden was f¨ ur einen Hut Sie selbst tragen.“ Gesagt, getan, die f¨ unf H¨ ute verschwinden pl¨ otzlich und Sie sehen auf den K¨ opfen ihrer Mitbewerber je einen der roten H¨ ute erscheinen. F¨ ur einige Minuten lang herrscht betretenes Schweigen. Pl¨otzlich haben Sie die Erleuchtung und sagen: Ich trage einen roten Hut!“ Der Zauberer lobt Sie f¨ ur die richtige Antwort und ” sagt: Nun erweisen Sie sich aber auch als w¨ urdig und erkl¨aren uns, wie Sie darauf gekommen ” sind!“ Also wie haben Sie es gemacht? L¨ osungsvorschlag: Wesentlich ist hier der Zeit-Aspekt, der in der Aussage F¨ ur einige Minuten lang herrscht ” betretenes Schweigen.“ steckt. Jeder Teilnehmer, der zwei schwarze H¨ ute sieht, kann sofort sagen, sein Hut sei rot. Da dies nicht passiert, sind keine zwei schwarze H¨ ute zu sehen. Falls Sie, genannt A, einen schwarzen Hut tragen, m¨ ussen die anderen beiden Protagonisten, B und C, je einen roten Hut tragen, und somit je einen roten und einen schwarzen Hut sehen. Aus der Tatsache, dass weder B noch C sofort seinen eigenen Hut als rot bezeichnet, k¨onnen B und C schließen, dass sie selbst keinen schwarzen Hut tragen, sollten also nach einer gewissen Bedenkzeit ihre jeweiligen H¨ ute als rot bezeichnen. Da auch dies nicht geschieht, bleibt nur die M¨oglichkeit u ¨brig, dass Sie, A, auch einen roten Hut tragen. ¨ Ubungsaufgabe 7 Warum gibt es keine unendlichen Formeln? Diese Frage kam am Ende der 2. Vorlesung auf. Daher m¨ ussen wir formalisieren, was es bedeutet, W¨ orter u ¨ber einem Alphabet zu bilden. Definition Unter einem Alphabet verstehen wir eine abz¨ahlbare Menge. In der Theorie formaler Sprachen beschr¨ankt man sich meist auf endliche Mengen, aber hier geht das nicht, denn das Alphabet der Aussagenlogik ist gegeben durch A := ATM ∪ {¬, ∧, ∨, ( , ) }. Als Vereinigung einer abz¨ ahlbar unendlichen mit einer endlichen Menge, ist es wieder abz¨ahlbar unendlich. Definition Die Menge X ∗ aller W¨ orter u ¨ber einem Alphabet X ist die (disjunkte) Vereinigung
aller cartesischen Produkte X n , n ∈ IN = {0, 1, 2 . . . }, wobei X n die Menge aller n-Tupel (= W¨ orter der L¨ ange n) aus Elementen der Menge X bezeichnet: X X ∗ := Xn n∈IN
Insbesondere haben alle W¨ orter u ¨ber X endliche L¨ange, allerdings sind die erlaubten L¨angen unbeschr¨ ankt. Um auch abz¨ ahlbar unendliche Tupel, oder Streams, betrachten zu k¨onnen, ist die Menge X IN aller Abbildungen von IN nach X hinzuzuf¨ ugen. (a) Geben Sie, ausgehend von F0 = ATM ∪ {⊥} eine iterative Beschreibung von FRM , die zeigt, dass FRM ⊆ A∗ gilt (folglich sind alle Formeln endlich). (b) Wieviele W¨ orter der L¨ ange 0 gibt es, und warum? L¨ osungsvorschlag: (a) Behauptung: Mit der Definition Fn+1 := Fn ∪ { F : F = (¬G) oder F = (G ∧ H) oder F = (G ∨ H) mit G, H ∈ Fn } erhalten wir FRM =
[
Fn
n∈IN
Die Inklusion ⊇ ist nach Definition von FRM klar. F¨ ur die umgekherte Inklusion ⊆ betrachte den Syntaxbaum von F ∈ FRM . Seine Tiefe t(F ) gibt an, in welchem Iterationsschritt F erreicht wird: F ∈ Ft(F ) . X; diese kann man (b) F¨ ur jede Menge U bezeichnet X U die Menge aller Abbildungen U auch als U -Tuple bezeichnen. Speziell realisieren wir die Zahl n ∈ IN als die Menge ihrer Vorg¨ anger in IN , d.h. n = {0, 1, . . . , n − 1} Ein n-Tuple in X ist somit eine Abbildung von {0, 1, . . . , n − 1} nach X. Das funktioniert auch f¨ ur n = 0: in obiger Sichtweise stimmt die Zahl 0 mit der leeren Menge ∅ u ¨berein, da 0 keine Vorg¨ anger in IN hat. Ein 0-Tuple u X. Von ¨ber X ist somit eine Funktion ∅ dieser Sorte gibt es nur genau eine, die leere Inklusionsabbildung nach X.
Aufgabe 8 [12 PUNKTE] Definieren Sie die formale Semantik einer erweiterten Aussagenlogik, bei der Atome neben den Wahrheitswerten 1 ( wahr“) und 0 ( falsch“) auch den Wahrheitswert 0.5 ( vielleicht“) ” ” ” annehmen k¨ onnen. Aufgabe 9 [12 PUNKTE] ¨ Fortsetzung von Aufgabe 5: Ubersetzen Sie die drei Aussagen Donalds in aussagenlogische Formeln, speziell solche in FRM . Legen Sie dazu passende Variablen f¨ ur atomare Aussagen ¨ fest. Uberpr¨ ufen Sie ihr damaliges Ergebnis nunmehr formal. Aufgabe 10 [8 PUNKTE] Sind die folgenden Aussagen wahr oder falsch? (a) Wenn 1 + 1 = 2 gilt, dann gibt es ein viereckiges Dreieck. (b) Wenn es ein viereckiges Dreieck gibt, dann gilt 1 + 1 = 2.
(c) Wenn es ein viereckiges Dreieck gibt, dann gilt 1 + 1 = 3. (d) Ein Dreieck hat drei oder vier Ecken.
Abgabe bis Montag, 2016-04-25, im Kasten neben IZ 343
