Mod - 4.1 4 Logik 4.1 Aussagenlogik Kalkül zum logischen Schließen. Grundlagen: Aristoteles 384 - 322 v. Chr. Aussagen: Sätze, die prinzipiell als wahr oder falsch angesehen werden können. z. B.: "Es regnet.", "Die Straße ist nass." aber "Dieser Satz ist falsch." ist in sich widersprüchlich, ist keine Aussage. Junktoren verknüpfen Aussagen: "Es regnet nicht, oder die Straße ist nass." Aussagenlogische Formeln als Sätze einer formale Sprache: z. B. regen arrowright straßeNass arrowboth logicalnot regen logicalor straßeNass Belegung der Aussagen mit f w f w Wahrheitswerten: Interpretation der Formel w w liefert Wahrheitswert: w w Formales Schließen im Gegensatz zur empirischen Beurteilung, z. B. ob "die Straße nass ist." Aus "Wenn es regnet, ist die Straße nass." und "Es regnet." folgt "Die Straße ist nass." Aussagen in der Spezifikation, in der Modellierung von Aufgaben (c) 2007 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 401 Ziele: Einführung in der Vorlesung: Begriffe erläutern nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 4.1.1 -------------------------------------------------------------------------------- Mod - 4.2 Vorschau auf Begriffe * Aussagenlogische Formeln definiert durch Signatur der booleschen Algebra * Belegung von Variablen mit Wahrheitswerten * Interpretation aussagenlogischer Formeln * Gesetze der booleschen Algebra zur Umformung von Formeln * erfüllbare und allgemeingültige Formeln * logischer Schluss: Folgerung aus einigen Annahmen (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 402 Ziele: Übersicht in der Vorlesung: Zusammenhang der Begriffe zeigen -------------------------------------------------------------------------------- Mod - 4.3 Beispiel: Aussagenlogik in der Spezifikation Unfall durch fehlerhafte Spezifikation: Airbus A320, Warschau (1993). Der zuständige Rechner blockiert bei der Landung die Aktivierung von Schubumkehr und Störklappen, wodurch das Flugzeug über das Landebahnende hinausschießt. Es herrschen starker Wind von schräg hinten und Aquaplaning auf der Landebahn. Beabsichtigte Spezifikation Tatsächliche Spezifikation der Störklappenfreigabe: der Störklappenfreigabe: Die Störklappen dürfen Störklappen freigeben benutzt werden * im Reise- und Sinkflug oder (Bremswirkung) * nach der Landung (Vernichtung des Auftriebes Stellung der Räder schneller und und Bremswirkung) Landeklappen als 133 km/h (72 kt) < 35ring Sie dürfen nicht benutzt und werden Höhe < 3m * im Endanflug (gefährlicher Auftriebsverlust) Gewicht auf Gewicht auf linkem Fahrwerk > x rechtem Fahrwerk >x (c) 2007 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 403 Ziele: Einfaches Beispiel für verknüpfte Aussagen in der Vorlesung: * Begründung der Spezifikation * Erläuterung der Unfallursache Verständnisfragen: Schlagen Sie eine Korrektur der Spezifikation vor. -------------------------------------------------------------------------------- Mod - 4.4 Aussagenlogische Formeln Aussagenlogische Formeln sind korrekte Terme mit Variablen zur Signatur der booleschen Algebra: false: -> Bool falsch, f true: -> Bool wahr, w logicaland : Bool x Bool -> Bool Konjunktion logicalor : Bool x Bool -> Bool Disjunktion logicalnot : Bool -> Bool Negation Erweiterung: arrowright : Bool x Bool -> Bool Implikation p arrowright q für logicalnot p logicalor q arrowboth : Bool x Bool -> Bool Äquivalenz p arrowboth q für (p arrowright q) logicaland (q arrowright p) Operatoren (Junktoren) in fallender Präzedenz: logicalnot logicaland logicalor arrowright arrowboth Variable, sowie false und true (Konstante) sind atomare Aussagen, die übrigen Formeln sind zusammengesetzt. Für Variable schreiben wir meist kleine Buchstaben p, q, ... für allgemeine Formeln große Buchstaben F, G, H, ... . Die Definition der Struktur der Formeln heißt Syntax der Aussagenlogik. (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 404 Ziele: Syntax der Aussagenlogik in der Vorlesung: * Term: nur Struktur; * Formel: Term plus Bedeutung durch Regeln der Interpretation * Signatur bestimmt Struktur der Terme und Formeln * Beispiele * Präzedenz und Klammerung nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 4.1.1 -------------------------------------------------------------------------------- Mod - 4.5 Interpretation aussagenlogischer Formeln Eine passende Belegung ordnet allen Variablen, die in einer Menge von Formeln F vorkommen, jeweils einen Wahrheitswert w oder f (für wahr oder falsch) zu. Die Belegung kann als Substitution angegeben werden, z.B. sigma = [ p / w, q / f ]. Eine Interpretation Ifraktur sigma einer aussagenlogischen Formel F bildet F auf einen Wahrheitswert ab: * Für Variable ist die Interpretation Ifraktur sigma durch die Belegung sigma definiert. * Für zusammengesetzte Formeln wird sie durch folgende Wahrheitstafeln erweitert: Ifraktur (false)=f Ifraktur (F) Ifraktur (logicalnot F) Ifraktur (F) Ifraktur (G) Ifraktur (Flogicaland G) Ifraktur (Flogicalor G) Ifraktur (Farrowright G) Ifraktur (Farrowboth G) w f w w w w w w Ifraktur (true)=w f w w f f w f f f w f w w f f f f f w w Eine Interpretation Ifraktur sigma mit einer Belegung sigma für eine Formel F bestimmt einen Wahrheitswert der Formel F: Ifraktur sigma (F) Wenn Ifraktur sigma (F) = w gilt, heißt Ifraktur sigma auch ein Modell der Formel F. (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 405 Ziele: Wahrheitswerte zu aussagenlogischen Formeln in der Vorlesung: * Belegung erläutern * Wir gehen davon aus, dass wir passende Belegungen zu der Menge der Formeln wählen, die wir gerade untersuchen. * logische Verknüpfungen zeigen * Interpretation: Belegung plus Verknüpfungen * Beispiele dazu * Bei n Variablen 2 hoch n verschiedene Belegungen nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 4.1.1 -------------------------------------------------------------------------------- Mod-4.6 Vorsicht beim Formalisieren umgangssprachlicher Aussagen Vorsicht bei Implikationen; mit Belegungen prüfen, was gemeint ist: 1. Wenn es regnet, benutze ich den Schirm. regnet arrowright schirm 2. Ich benutze den Schirm, wenn es regnet. regnet arrowright schirm 3. Ich benutze den Schirm, nur wenn es regnet. schirm arrowright regnet "Oder" kann fast immer in das nicht-ausschließende logicalor übersetzt werden: 4. Hast Du einen Euro oder zwei Fünfziger? euro logicalor zwei50er 5. Morgen fahre ich mit dem Zug oder mit dem Auto nach Berlin. zug logicalor auto 6. x ist kleiner y oder x ist gleich y. x F nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 4.1.2 Übungsaufgaben: Mit logischen Aussagen Eigenschaften des Getränkeautomaten, seiner Bedienung und seiner Zustände beschreiben. Prüfen, ob die Aussagen erfüllbar sind. --------------------------------------------------------------------------------