3.0 VU Formale Modellierung Gernot Salzer ArbeitsbereichTheoretischeInformatikundLogik InstitutfürComputersprachen SS 2016 1 Inhalt 0. Überblick 1. Organisatorisches 2. Was bedeutet Modellierung? 3. Aussagenlogik 3.1. Was ist Logik? 3.2. Aussagenlogische Funktionen 3.3. Syntax und Semantik der Aussagenlogik 3.4. Von der Funktion zur Formel 3.5. Normalformen 3.6. Das Erfüllbarkeitsproblem 3.7. House 3.8. Dualität von Funktionen, Operatoren und Formeln 3.9. Gone Maggie gone 4. Endliche Automaten 5. Reguläre Sprachen 6. Kontextfreie Grammatiken 7. Prädikatenlogik 8. Petri-Netze 2 Was ist Logik? Neulich in der U-Bahn „Stell dir vor, die Julia hat mit dem Mike Schluss gemacht!“ „Logisch, er hat ja was mit der Laura angefangen.“ Was daran ist logisch? Es ist nicht logisch, dass Mike mit Laura anbandelt oder dass man bei Untreue Schluss machen muss oder dass sich Julia von Mike trennt. Diese Aussagen können zutreffen oder auch nicht, sie sind aber nicht „logisch“. 3 Falls man aber akzeptiert, dass Mike untreu war und dass Untreue zur Trennung führt dann ist es logisch schlüssig, dass sich Julia von Mike trennt. Mike ist Julia untreu. x Wenn Untreue, dann Trennung. Wenn x, dann y. Julia trennt sich von Mike. y Die Logik untersucht allgemeine Prinzipien korrekten Schließens. 4 Schlussfolgerungen (Inferenzen) ) Alle Menschen sind sterblich. Prämissen, Annahmen Sokrates ist ein Mensch. Sokrates ist sterblich. Konklusion, Folgerung ClipartcourtesyFCIT Die Prämissen sind durch „und“ verbunden. Die Linie bedeutet „daher“. Wahre Prämissen, wahre Konklusion. Gültige Inferenz: Die Konklusion folgt logisch aus den Prämissen. Alle geraden Zahlen sind durch 2 teilbar. 4 ist eine gerade Zahl. 4 ist durch 2 teilbar. wahre Prämissen, wahre Konklusion gültige Inferenz Inferenzmuster identisch mit vorigem Beispiel 5 Alle US-Präsidenten sind in der USA geboren. Schwarzenegger ist US-Präsident. Schwarzenegger ist in der USA geboren. eine wahre und eine falsche Prämisse falsche Konklusion trotzdem korrekte Inferenz! Zugrundeliegende Inferenzregel Alle x sind y. x ... Mensch, US-Präsident, gerade Zahl z ist ein x. y ... sterblich, in USA geboren, durch 2 teilbar z ist y. z ... Sokrates, Schwarzenegger, 4 x, y, z: Platzhalter (Variablen) für Eigenschaften, Individuen, ... Die Logik befasst sich mit den Inferenzregeln. Das Anwendungsgebiet bestimmt den Wertebereich der Variablen und die Wahrheit der elementaren Aussagen. 6 Gültigkeit von Inferenzregeln Unzulässige Inferenzen Alle Menschen sind sterblich. Sokrates ist ein Mensch. Sokrates ist sterblich. Sokrates ist sterblich. Sokrates ist ein Mensch. Alle Menschen sind sterblich. wahre Prämissen wahre Konklusionen aber trotzdem keine zulässigen Inferenzen! Kriterium für die Gültigkeit von Inferenzregeln Immer wenn alle Prämissen wahr sind, ist auch die Konklusion wahr. Äquivalentes Kriterium (Umkehrung) Immer wenn die Konklusion falsch ist, ist mindestens eine Prämisse falsch. 7 Alle Menschen sind sterblich. Alle x sind y. Sokrates ist sterblich. Inferenzregel: z ist y. Sokrates ist ein Mensch. z ist ein x. Diese Regel erfüllt nicht das Kriterium. Gegenbeispiel: x = Ball, y = rund, z = Sonne Alle Fußbälle sind rund. wahr Die Sonne ist rund. wahr Die Sonne ist ein Fußball. falsch Die Inferenzregel ist daher nicht gültig, obwohl sie gelegentlich zu wahren Konklusionen führt. Aber eben nicht immer! 8 Logische Junktoren (Operatoren, Konnektive, Funktionen) ... ermöglichen die Bildung zusammengesetzter Aussagen, so wie Addition und Subtraktion bei arithmetischen Ausdrücken. Wenn Feiertag ist oder der Professor krank ist, findet die Vorlesung nicht statt. „es ist Feiertag“ (x), „Prof ist krank“ (y), „VO findet statt“ (z) ... elementare Aussagen aus dem Uni-Milieu Logische Struktur: „Wenn x oder y, dann nicht z“ Junktoren: wenn-dann, oder, nicht Weitere Junktoren in ... der Aussagenlogik: und, entweder-oder, genau dann-wenn, ... Zeitlogiken: morgen, gestern, im nächsten Moment, bis, ... Modallogiken: notwendigerweise, möglicherweise, ... ... 9 Quantoren ... ermöglichen Aussagen über die Anzahl betroffener Individuen, Zeitpunkte etc. Jeder Mann liebt eine Frau. Wertebereiche: Männer (x) , Frauen (y) Logische Struktur: „Für alle x gibt es mindestens ein y, sodass x y liebt." Quantoren: für alle, mindestens ein Weitere Quantoren: einige, viele, mindestens fünf, höchstens drei, immer, manchmal, irgendwann später, ... 10