Skript Logik Teil 1 PDF - Theoretische Informatik 1

Theoretische Informatik 1 Markus Kaupp 2024 1  2 ▪ Das Titelbild der Vorlesung wurde von der generativen KI Microsoft Wie entstand das Designer erstellt....

Theoretische Informatik 1 Markus Kaupp 2024 1  2 ▪ Das Titelbild der Vorlesung wurde von der generativen KI Microsoft Wie entstand das Designer erstellt. Der Prompt für die Erzeugung Titelbild? ▪ lautete: Erstelle ein Bild zum Thema "Theoretische Informatik", das Studierende motiviert, sich mit dem Thema auseinanderzusetzen… Bevor es los geht... Particify ▪ Mit Particify können Sie mir während der Vorlesung anonymes Feedback zum Vorlesungstempo geben oder Ihre Fragen formulieren, bevor sie verloren gehen. ▪ Ich werde die Plattform auch nutzen, um Ihnen Verständnisfragen zu stellen. https://partici.fi/33103264 3 Einführung 4 Was macht gute Informatiker*innen aus? ▪ Auch wenn sich die Inhalte der Informatik ständig ändern, bleiben zwei Fähigkeiten zentral: ▪ Abstraktionsvermögen: Komplexe Zusammenhänge erfassen und auf das Wesentliche reduzieren. ▪ Logisches Denken: Probleme strukturiert und effizient lösen. 5 Theoretische Informatik: „In der Informatik geht es genauso wenig um Computer Ihre Vorteile wie in der Astronomie um Teleskope.“ ▪ Was Sie aus der Vorlesungsreihe „Theoretische Informatik“ mitnehmen sollen: ▪ Zugriff auf das Wissen und die Erkenntnisse vieler kluger Informatiker*innen. ▪ Erwerb zeitloser Konzepte und Fähigkeiten, die über konkrete Programmiersprachen und Technologien hinausgehen. ▪ Warum das wichtig ist: ▪ Die Konzepte sind unabhängig von Rechenmaschinen oder Plattformen anwendbar. Edsger W. Dijkstra (Informatiker, ▪ Sie helfen uns, Probleme effizient und flexibel zu lösen. Gewinner des Turing-Award) 6 Was ist theoretische Informatik? ▪ Die rasante Entwicklung der Computertechnik ist eng mit der Informatik verbunden. ▪ Die Informatik hat sich von einer Nischendisziplin zu einer eigenständigen Wissenschaft entwickelt. ▪ Die Informatik hat im Wesentlichen folgende vier Teilbereiche: ▪ Technische Informatik ▪ Theoretische Informatik ▪ Praktische Informatik ▪ Angewandte Informatik [Hoff22] 7  Die vier Säulen der Informatik Informatik Entscheidbarkeit Software-Engineering Rechnerarchitekturen Formale Sprachen Betriebssysteme Assistenzsysteme Hardware-Entwurf Berechenbarkeit Compilerbau Signalverarbeitung Prozessoren Algorithmentheorie Verteilte Systeme Medieninformatik Schaltwerke Komplexität Programmieren Künstliche Intelligenz Relationen Datenstrukturen Logische Schaltungen Computergrafik Logik Algorithmen Technische Theoretische Praktische Angewandte Informatik Informatik Informatik Informatik Vgl. [Hoff22] 8 Grundlagen der Logik 9 Was ist Logik? ▪ Logik (aus dem Altgriechischen: „Kunst des Denkens“) bezieht sich allgemein auf das vernünftige Schlussfolgern und speziell auf dessen Lehre – die Schlussfolgerungs- oder Denklehre. Sie analysiert die Struktur von Argumenten auf ihre Gültigkeit, unabhängig vom Inhalt der Aussagen. In diesem Zusammenhang spricht man auch von „formaler Logik“. [Logi24] ▪ Der englische Philosoph und Politiker John Locke (1632–1704) bezeichnete die Logik als „Anatomie des Denkens“. Im engeren Sinne versteht man unter Logik die Theorie, die sich mit den Gesetzmäßigkeiten befasst, wie aus bestimmten Voraussetzungen korrekte Schlussfolgerungen gezogen werden. Ihre Wurzeln liegen in der Antike bei Aristoteles, der erste Konzepte entwickelte, um aus sprachlichen Prämissen logische Regeln abzuleiten. [Staa12] 10  Alle Also ist Menschen Sokrates ist Sokrates Was ist sind ein Mensch. sterblich. sterblich. Logik? Aristoteles entwickelte vor über 2400 Jahren wesentliche Grundideen der Logik. 11 Was ist Logik? ▪ Logisches Denken bedeutet, aus bestehenden Erkenntnissen durch korrekte Verknüpfungen neue Schlussfolgerungen zu ziehen. ▪ Ein gutes Beispiel ist die Kriminalistik, wo wir in Filmen oft von lückenlosen Beweisketten beeindruckt sind, die die Schuld von Beschuldigten zweifelsfrei beweisen – was oft zu einem Geständnis führt. [Staa12] 12  Was ist Logik? ▪ Es gibt sehr viele Logiken, z.B. ▪ Aussagenlogik ▪ Prädikatenlogik erster Stufe ▪ Prädikatenlogik zweiter Stufe ▪ Beschreibungslogiken (Wissensrepräsentation und KI) ▪ Temporallogiken (z.B. Verifikation zeitlicher Abläufe) ▪ Logikprogramme (Answer Set Programming, Prolog,... ) ▪ Nicht-klassische Logiken (z.B. intuitionistische Logik) ▪ Mehrwertige Logiken (z.B. probabilistische Logik) ▪... und viele andere mehr [Kröt21] 13 Was ist Logik?: Ein Kriminalfall ▪ Eine Kommissarin und ihr Assistent treffen am Tatort ein: Robert van Oyen, ein erfolgreicher Fernsehproduzent, wurde erschossen in seiner Villa aufgefunden. Die Haushälterin, die den Fund gemacht und die Polizei alarmiert hatte, berichtet, dass sie am Vorabend ein Buffet für vier Gäste vorbereitet hatte: die Schauspielerin Verena, ihren Ehemann Max sowie die Nachwuchsschauspieler Uwe und Kay, die beide um eine Hauptrolle konkurrierten. ▪ Die Haushälterin kommt als Täterin nicht in Frage. Zudem hätte van Oyen einem Fremden nie die Tür geöffnet. Es gibt keine Anzeichen für einen Einbruch. Selbstmord wird ausgeschlossen. Also muss der Mörder einer der Gäste gewesen sein. ▪ Auf Nachfrage der Kommissarin erklärt die Haushälterin, dass Verena nur zusammen mit ihrem Mann Max gekommen wäre, da dieser extrem eifersüchtig ist. Ein früherer Streit zwischen Max und Kay hatte dazu geführt, dass Kay Partys mit Max mied. Uwe hingegen brachte immer auch Verena und Kay mit. Außerdem habe der Manager von Uwe und Kay mitgeteilt, dass mindestens einer der beiden kommt. ▪ Der Assistent ist frustriert und fragt sich, wer an diesem Abend tatsächlich da war. Die Kommissarin lächelt und sagt: „Ich weiß genau, wer da war. Fahr den Wagen vor!“ [Staa12] 14 Logik in der Informatik ▪ Die Logik ist in der Informatik an vielen Stellen relevant: ▪ Programmierung: Bedingte Ausführung und Wiederholung von Programmteilen ▪ Verifikation von Software: Logik als Spezifikationssprache gewünschter Eigenschaften. ▪ Künstliche Intelligenz: Logik als Lehre vom folgerichtigen Denken. ▪ Optimierung: Logisches Schließen als Suche nach Lösungen komplexer Probleme. ▪ Datenverwaltung: Logik als eindeutig definiertes Format für Daten und Anfragen. ▪ Wissensrepräsentation: Logik zur Darstellung und Anwendung von menschlichem Wissen in Form von Regeln, Taxonomien und Ontologien. 15 [Kröt21] Aussagenlogik 16 Aussagenlogik: Atomare Aussagen ▪ Die Grundbausteine der Aussagenlogik sind atomare Aussagen, kurz „Atome“. Atomare Aussagen sind Behauptungen, die klar als „wahr“ oder „falsch“ bewertet werden können. ▪ Welches sind Aussagen? a) Berlin ist die Hauptstadt von Deutschland. b) Paris ist die Hauptstadt von Italien. c) Horb wird irgendwann Hauptstadt von Deutschland werden. [Kröt21, Staa12] 17 Aussagenlogik: Atomare Aussagen ▪ Im weiteren Verlauf der Vorlesung benennen wir Atome mit Kleinbuchstaben (𝑎, 𝑏, 𝑐, …). ▪ Atome können die Wahrheitswerte „wahr“ (abgekürzt mit w oder 1) oder „falsch“ (abgekürzt mit f oder 0) annehmen. ▪ Mit den Werten der Atome können wir rechnen. [Staa12] 18 Aussagenlogik: Verknüpfungen ▪ Aussagen können durch logische Operatoren wie UND, ODER und Junktor Operatorzeich Bezeichnung NICHT miteinander verknüpft. en ▪ Die logischen Operatoren nennt man UND ∧ Konjunktion Junktoren. ODER ⋁ Disjunktion ▪ Durch den Einsatz von Junktoren erhalten wir verknüpfte Aussagen. NICHT ¬ Negation ▪ Auch verknüpfte Aussagen haben einen Wahrheitswert. Dieser lässt sich aus den Operanden ableiten. [Kröt21, Staa12] 19 Aussagenlogik: UND- Verknüpfung ▪ Mit UND können wir zwei Aussagen 𝑎 und b verknüpfen. ▪ Wir schreiben: 𝑎 ∧ 𝑏 ▪ Beispiel: Wir verwenden wieder unsere Aussagen (a) Berlin ist die Hauptstadt von Deutschland. (b) Paris ist die Hauptstadt von Italien. Dann bedeutet 𝑎 ∧ 𝑏 : „Berlin ist die Hauptstadt von Deutschland und Paris ist die Hauptstadt von Italien.“ ▪ Die Aussage ist als Ganzes falsch, weil eine der Teilaussagen falsch ist. ▪ Die Aussage wird auch nicht richtig, wenn wird die Reihenfolge der Teilaussagen umdrehen, also b ∧ 𝑎. [Staa12] 20 Aussagenlogik: UND- Verknüpfung: Wahrheitstafel 𝑎 𝑏 𝑎∧𝑏 ▪ Eine Wahrheitstafel zeigt, welche Wahrheitswerte ein logischer Ausdruck abhängig von den Wahrheitswerten f f f der Teilaussagen annimmt. f w f ▪ Die Verknüpfung 𝑎 ∧ 𝑏 ist nur dann wahr, wenn beide Teilaussagen 𝑎 und 𝑏 wahr sind. w f f ▪ Diese Regel entspricht weitgehend der Verwendung des w w w Wortes „und“ in der Alltagssprache. [Staa12] Wahrheitstafel der und-Verknüpfung 21 Aussagenlogik: ODER- Verknüpfung ▪ Wenn wir zwei Aussagen mit ODER verknüpfen, schreiben 𝑎 𝑏 𝑎∨𝑏 wir: 𝑎 ∨ 𝑏 ▪ Beispiel: Berlin ist die Hauptstadt von Deutschland oder f f f Paris ist die Hauptstadt von Italien. f w w ▪ Die Aussage ist als Ganzes wahr, weil mindestens eine der Teilaussagen wahr ist. w f w ▪ Achtung: w w w ▪ Das logische ODER weicht manchmal vom umgangssprachlichen oder ab. Oft meint man mit „oder“ ein Wahrheitstafel der oder-Verknüpfung „entweder… oder“. ▪ Beispiel: Ich esse Döner oder Pizza. [Staa12] 22 Aussagenlogik: NICHT- Junktor Der Junktor NICHT (¬) negiert eine einzelne ▪ Aussage. 𝑎 ¬𝑎 Negieren bedeutet, dass der Wahrheitswert w f ▪ umgekehrt wird. ▪ Es ist ein unärer Operator. Wir haben also nur einen Operanden. f w ▪ Beispiel: Bezeichnen wir die Aussage „Paris ist die Hauptstadt von Italien“ mit 𝑎, wäre damit ¬𝑎 wahr. Wahrheitstafel des nicht-Operators [Staa12] 23 Quiz https://partici.fi/33103264 24 Fragen? 25 Aussagenlogik: Implikation (wenn … dann) ▪ Das Beispiel mit dem Kriminalfall thematisiert das logische Folgern. ▪ Das Folgern von einem Sachverhalt auf einen anderen formuliert man sprachlich oft mit „wenn … dann“. ▪ Beispiel: „Wenn es regnet, dann wirst du nass“. ▪ Um dies zu formalisieren, identifizieren wir die Aussagen: ▪ (a) Es regnet (b) Du wirst nass ▪ In der Logik wird die „wenn … dann“-Beziehung als Implikation dargestellt: 𝒂→𝒃 ▪ Man sagt: „Aus 𝑎 folgt 𝑏.“ oder „𝑎 impliziert 𝑏.“ [Staa12] 26  Aussagenlogik: Beispiel: ▪ Wir betrachten folgende Aussage: „Wenn es regnet, Implikation: dann wird die Straße nass“. ▪ Wir haben darin die beiden Atome: Wahrheitstafel ▪ (a) Es regnet. ▪ (b) Die Straße wird nass. 𝑎 𝑏 𝑎→𝑏 ▪ Wenn 𝑎 falsch ist, kann die Straße entweder trocken f f w bleiben (f→f = w) oder durch andere Ursachen nass f w w werden, z. B. durch einen Sprinkler (f → w = w). Dies erklärt die ersten beiden Zeilen der Wahrheitstafel. w f f ▪ Ist 𝑎 wahr, muss auch 𝑏 wahr sein, da Regen die Straße w w w nass macht (w → w = w). Wenn 𝑏 falsch wäre, wäre die Wahrheitstafel der Implikation Aussage falsch (w → f = f). 27 [Staa12]  Aussagenlogik: Äquivalenz (Genau dann, wenn…) 𝑎 𝑏 𝑎 𝑏 ▪ Die logische Äquivalenz ist immer dann erfüllt, f f w wenn die Wahrheitswerte der beiden Teilaussagen übereinstimmen. f w f ▪ Bei der Formulierung mathematischer Sätze wird w f f Äquivalenz mit „genau dann, wenn“ übersetzt. ▪ Der Äquivalenzoperator ist der Doppelpfeil: w w w Wahrheitstafel der Äquivalenz 28 [Staa12]  Quiz https://partici.fi/33103264 29 [Staa12] Fragen? 30 Aussagenlogik: Richtiges Schlussfolgern Folgert der Student korrekt? [Staa12] 31 Aussagenlogik: Richtiges Schlussfolgern ▪ Zunächst identifizieren wir die Teilaussagen: 𝑎 𝑏 𝑎→𝑏 ¬𝑎 ¬𝑏 ¬𝑎 → ¬𝑏 ▪ (a) Die Person lernt täglich mindestens eine Stunde Logik. f f w w w w ▪ (b) Die Person besteht die Klausur. f w w w f f ▪ Die formale Darstellung lautet: 𝑎 → 𝑏 w f f f w w ▪ Der Student schließt offensichtlich daraus, dass das gleichbedeutend ist mit: ¬𝑎 → ¬𝑏 w w w f f w ▪ Die Wahrheitstafel zeigt aber, dass die Aussagen nicht gleichbedeutend sind! 32 [Staa12] Aussagenlogik: Ich habe die Klausur nicht Dann haben Sie nicht mindestens eine Richtiges bestanden. Stunde Logik gelernt. Schlussfolgern Ist die Folgerung des Dozenten korrekt? 33 Aussagenlogik: Richtiges 𝑎 𝑏 𝑎→𝑏 ¬𝑎 ¬𝑏 ¬𝑏 → ¬𝑎 Schlussfolgern f f w w w w ▪ Die Wahrheitstafel zeigt, dass f w w w f w tatsächlich gilt: 𝑎 → 𝑏 ¬𝑏 → ¬𝑎 w f f f w f w w w f f w [Staa12] 34 Übung Wir erstellen die Wahrheitstafel des Ausdrucks ¬𝑎 ∨ ¬𝑏. Das könnte z.B. bedeuten „Ich war nicht zuhause oder ich habe die Klingel nicht gehört.“ 35 Übungsaufgaben 36 37 Fragen? 38 Aussagenlogik: Syntax und Semantik Eine Logik ist definiert durch: Syntax: Die Sprache der Logik, typischerweise bestehend aus Formeln mit logischen Operatoren. Semantik: Die Bedeutung dieser Formeln, d.h., worauf sie sich beziehen und unter welchen Bedingungen sie wahr oder falsch sind. Ein zentrales Ziel der Logik ist das Schlussfolgern: Welche logischen Schlüsse lassen sich aus einer oder mehreren Formeln ableiten? Die korrekten Schlussfolgerungen sollten sich aus der Semantik ergeben. In der Praxis ist die Berechnung solcher Schlussfolgerungen oft komplex. [Kröt21] 39  Syntax der Aussagenlogik Sei 𝑃 die abzählbar unendliche Menge aller Aussagenlogik: atomaren Aussagen. Dann ist die Menge aller aussagenlogischer Syntax Formeln wie folgt induktiv definiert: Jedes Atom 𝑝 ∈ 𝑃 ist eine aussagenlogische Formel. Sind 𝐹 und 𝐺 aussagenlogische Formeln, dann sind auch 𝐹 ∧ 𝐺, 𝐹 ∨ 𝐺, 𝐹 → 𝐺 und 𝐹 𝐺 Hinweis: Wir verzichten im logische Formeln. Sprachgebrauch oft auf Ist 𝐹 eine aussagenlogische Formel, dann ist „aussagenlogisch“ und sprechen in diesem Zusammenhang einfach von auch ¬𝐹 eine aussagenlogische Formel. „Formeln“. [Kröt21, Staa12] 40 Aussagenlogik: Syntax ▪ Syntaktisch korrekte ▪ Syntaktisch nicht Formeln sind: korrekte Formeln sind: ▪ 𝑝 ▪ 𝑝¬ ∨ 𝑞 ▪ 𝑥1 ∧ 𝑥2 ∨ ¬𝑥3 ▪ x1 ∨ 𝑥2 ∧ ▪ ¬ 𝑝 ∧ 𝑞 ∨ (𝑟 ∧ 𝑠) ▪ 𝑝 ∧∨ 𝑞 [Staa12] 41 Aussagenlogik: Semantik ▪ Sei 𝐹 𝑥1 , … 𝑥𝑛 eine aussagenlogische Formel mit 𝑥1 , … 𝑥𝑛 ∈ 𝑃. Dann ist eine Belegung eine Abbildung 𝐵: 𝑃 → {f, w}, die jeder der Das macht natürlich auch Sinn. Die meisten Aussagenvariablen 𝑥1 , … 𝑥𝑛 einen Wahrheitswert, also w oder f Funktionswerte sind zuordnet. abhängig von den Eingangswerten. ▪ Für ein Atom 𝑥 ∈ 𝑃 und eine Belegung 𝐵, ist 𝐵 𝑥 der Wahrheitswert der 𝑥 durch 𝐵 zugeordnet wird. ▪ Ist 𝐹 eine aussagenlogische Formel und 𝐵 eine Belegung. Dann ist der Wahrheitswert 𝑊𝐵 (𝐹) von 𝐹 abhängig von der Belegung 𝐵. [Kröt21, Staa12] 42 Aussagenlogik: Semantik 𝑎 𝑏 𝑎∨𝑏 In der Wahrheitstabelle enthält jede Zeile eine Belegung samt der resultierenden f f f Wahrheitswerte für eine oder mehrere aussagenlogische Formeln. f w w w f w w w w 43  Aussagenlogik: Semantik Semantik von Junktoren Ergebnis elementarer Aussagen Sind 𝐹 und 𝐺 logische Formeln, dann gilt: Sei 𝑥 ein Atom und 𝐵 eine Belegung, dann w, falls 𝑊𝐵 𝐹 = w und 𝑊𝐵 𝐺 = w 𝑊𝐵 𝐹 ∧ 𝐺 = ቊ gilt: f, sonst 𝑊𝐵 𝑥 = w, falls 𝐵 𝑥 = w w, falls 𝑊𝐵 𝐹 = w oder 𝑊𝐵 𝐺 = w 𝑊𝐵 𝑥 = f, falls 𝐵 𝑥 = f 𝑊𝐵 𝑓 ∨ 𝐺 = ቊ f, sonst w, falls 𝑊𝐵 𝐹 = f 𝑊𝐵 ¬𝐹 = ቊ f, sonst [Staa12] 44 Aussagenlogik: Erfüllbarkeit, Tautologie, Widerspruch ▪ Eine Belegung 𝐵 erfüllt eine aussagenlogische Formel 𝐹, wenn gilt: WB 𝐹 = w. ▪ Erfüllt eine Belegung 𝐵 eine aussagenlogische Formel 𝐹, dann schreiben wir 𝐵 ⊨ 𝐹. Andernfalls schreiben wir 𝐵 ⊭ 𝐹. ▪ Eine aussagenlogische Formel 𝐹 heißt erfüllbar, wenn es eine Belegung 𝐵 gibt mit 𝐵 ⊨ 𝐹. ▪ Eine aussagenlogische Formel 𝐹 heißt widerlegbar, wenn es eine Belegung 𝐵 gibt mit 𝐵 ⊭ 𝐹. ▪ Es gibt zwei Sonderfälle: ▪ Ist 𝐹 für jede Belegung wahr, dann ist 𝐹 allgemeingültig. Ein allgemeingültige Formel heißt auch Tautologie. ▪ Ist 𝐹 für kein Belegung wahr, dann ist 𝐹 unerfüllbar. ▪ Beispiel für eine Tautologie: „Das Licht ist an oder es ist nicht an.“ (𝐹 = 𝑎 ∨ ¬𝑎) ▪ Beispiel für eine unerfüllbare Formel: „Das Licht ist an und es ist nicht an.“ (𝐹 = 𝑎 ∧ ¬𝑎) [Kröt21, Staa12] 45  Was ist das SAT-Problem? Ziel: Entscheiden, ob eine aussagenlogische Formel erfüllbar ist. SAT-Solver: Automatische Lösung des SAT-Problems Aussagenlogik: SAT-Solver sind Algorithmen, die das SAT-Problem automatisch lösen. Sie prüfen systematisch, ob es eine Belegung gibt, die die Erfüllbarkeit: Formel wahr macht. SAT-Problem Anwendungsbereiche von SAT-Solvern Verifikation von Hardware und Software Künstliche Intelligenz: Planungs- und Optimierungsprobleme Automatische Beweisführung: Beweise für logische Theoreme zu finden. 46 Aussagenlogik: Logische Konsequenz Modelle von Formeln und Mengen Logische Konsequenz ▪ Eine Belegung 𝐵 heißt Modell einer Sei ℱeine Menge aussagenlogischer aussagenlogischen Formel 𝐹, wenn Formeln. Eine aussagenlogische Formel 𝐺 𝐵 ⊨ 𝐹. ist eine logische Konsequenz aus ℱ, ▪ Ist ℱ eine (möglicherweise unendliche) wenn jedes Modell von ℱ auch ein Modell Menge aussagenlogischer Formeln, von 𝐺 ist. Wir schreiben dann ℱ ⊨ 𝐺. dann ist 𝐵 ein Modell der Menge ℱ, wenn 𝐵 ⊨ 𝐹 für alle 𝐹 ∈ ℱ. In diesem ▪ 𝐺 ist also eine logische Konsequenz, wenn gilt: Fall schreibt man 𝐵 ⊨ ℱ. Immer wenn die Formeln aus wahr ℱ sind, ist auch 𝐺 wahr. Die logischen Schlussfolgerungen aus einer ▪ Umgangssprachlich ist eine logische Konsequenz „etwas, was in diesen Fällen zusätzlich gilt“. Formel(menge) basieren auf ihren Modellen. ▪ Die Menge der Modelle von ℱ ist eine Teilmenge [Kröt21] der Modelle von 𝐺. 47 Aussagenlogik: Tautologie und Unerfüllbarkeit Satz Beweis: (1) Eine Tautologie ist die logische (1) Eine Tautologie hat jede Belegung 𝐵 als Modell. Konsequenz jeder beliebigen Somit auch alle Modelle jeder Formelmenge. □ Formel(menge). (2) Eine unerfüllbare Formel(menge) hat keine Modelle. (2) Eine unerfüllbare Formel(menge) Somit ist jede aussagenlogische Formel immer impliziert jede andere Formel als mindestens die null Modelle, der unerfüllbaren logische Konsequenz. Formel. □ Der Effekt von (2) zeigt sich auch in der Alltagssprache: „Wenn das stimmt, bin ich der Kaiser von China!“ Dies verdeutlicht, dass aus einer falschen Annahme alles abgeleitet [Kröt21] werden kann, selbst wenn es offensichtlich unwahr ist. 48 Modelltheorie: Intuition ▪ Die Modelltheorie einer Logik beschreibt auf Modelle ⊨ Formeln abstrakte Weise, auf welchen 𝐹1 𝐵1 Gegenstandsbereich sich die Aussagen der Logik beziehen: 𝐵2 𝐹2 ▪ Formeln: Aussagen, die als wahr oder falsch bewertet werden können. 𝐵3 𝐹3 ▪ Modelle: Denkbare "Welten" oder Strukturen, in 𝐵4 𝐹4 denen bestimmte Aussagen zutreffen und andere nicht. [Kröt24] 49 Modelltheorie: Tautologien und Widersprüche Modelle ⊨ Formeln ▪ Mit den Modellen können wir 𝐵1 𝐹1 erfüllbar, widerlegbar auch die Begriffe rund um die 𝐵2 𝐹2 erfüllbar, allgemeingültig Erfüllbarkeit veranschaulichen: 𝐵3 𝐹3 erfüllbar, widerlegbar 𝐵4 𝐹4 unerfüllbar, widerlegbar [Kröt24] 50 Modelltheorie: Logische Konsequenz Modelle ⊨ Formeln ▪ Was folgt aus 𝐹3 ? 𝐵1 𝐹1 ▪ Modelle von 𝐹3 sind die Belegungen 𝐵2 und 𝐵3. 𝐵2 𝐹2 ▪ Die Belegungen 𝐵2 und 𝐵3 sind auch Modelle von 𝐹2. 𝐵3 𝐹3 → Immer wenn 𝐹3 wahr ist, ist auch 𝐹2 wahr. 𝐵4 𝐹4 ▪ Es folgt also: 𝐹3 ⊨ 𝐹2 [Kröt24] 51 Modelltheorie: Logische Konsequenz ▪ Gilt auch: 𝐹2 ⊨ 𝐹3 ? ▪ Warum? 52 Modelltheorie: Logische Konsequenz Modelle ⊨ Formeln ▪ Bei Formelmengen gehen wir von den 𝐵1 𝐹1 Modellen aus, für die alle Formeln der Menge 𝐵2 𝐹2 erfüllt sind. ▪ Beispiel: Die Menge ℱ = {𝐹1 , 𝐹3 } hat als 𝐵3 𝐹3 gemeinsames Modell nur 𝐵2. Da 𝐵2 die 𝐵4 𝐹4 Formel 𝐹2 erfüllt, gilt ℱ ⊨ 𝐹2. 53 Quiz https://partici.fi/33103264 54 Fragen? 55 Aussagenlogik: Logische Gesetzmäßigkeiten 𝑎 𝑏 𝑎→𝑏 ¬𝑎 ¬𝑎 ∨ 𝑏 ▪ Die Operatoren Implikation (→) und Äquivalenz ( ) sind bei der Definition der Semantik nicht aufgetaucht. Das ist nicht nötig, weil man sie auch f f w w w mit UND, ODER und NICHT ausdrücken kann. f w w w w ▪ Es gilt: a → 𝑏 lässt sich ausdrücken als ¬a ∨ 𝑏 und umgekehrt. Dementsprechend gilt immer w f f f f (a → 𝑏) (¬𝑎 ∨ 𝑏). w w w f w ▪ Man kann auch sagen: „(a → 𝑏) (¬𝑎 ∨ 𝑏) ist eine Tautologie“. Wahrheitstafel für 𝑎 → 𝑏 und ¬𝑎 ∨ 𝑏 ▪ Wir beweisen das per Wahrheitstafel. [Staa12] 56 Aussagenlogik: Logische Gesetzmäßigkeiten ▪ Wir haben formal bewiesen, dass gilt: (a → 𝑏) (¬𝑎 ∨ 𝑏) ▪ Ist diese Aussage tatsächlich auch umgangssprachlich plausibel? ▪ Wir betrachten die Aussage: „Wenn du auf die heiße Herdplatte greifst, dann verbrennst du dir die Hand.“ ▪ Hier haben wir wieder zwei atomare Aussagen: ▪ (a) Du greifst auf die heiße Herdplatte. ▪ (b) Du verbrennst dir die Hand. ▪ Die Aussage ¬𝑎 ∨ 𝑏 würde lauten: „Greife nicht auf die heiße Herdplatte, oder du verbrennst dir die Hand.“ [Staa12] 57 Aussagenlogik: Logische Gesetzmäßigkeiten ▪ Wir können auch die Äquivalenz mit ∨, ∧ und ¬ ausdrücken. ▪ Es gilt: a 𝑏 lässt sich immer ausdrücken durch a ∧ 𝑏 ∨ (¬𝑎 ∧ ¬𝑏) und umgekehrt. ▪ Dementsprechend ist a 𝑏 a ∧ 𝑏 ∨ (¬𝑎 ∧ ¬𝑏) eine Tautologie. ▪ Beweisen Sie das mit einer Wahrheitstafel. [Staa12] 58 Übungsaufgaben 59 60 Fragen? 61 Aussagenlogik: Unser Mordfall ▪ Mit unserem neuen Wissen lösen wir jetzt unseren Mordfall. ▪ Es gab ja folgende Aussage: „Auf Nachfrage ▪ Wir definieren hierfür folgende der Kommissarin erklärt die Haushälterin, dass Aussagevariablen: Verena nur zusammen mit ihrem Mann Max ▪ 𝑣 sei die Aussage „Verena war am Tatort.“ gekommen wäre, da dieser extrem eifersüchtig ist. Ein früherer Streit zwischen Max und Kay ▪ 𝑚 sei die Aussage „Max war am Tatort.“ hatte dazu geführt, dass Kay Partys mit Max ▪ 𝑢 sei die Aussage „Uwe war am Tatort.“ mied. Uwe hingegen brachte immer auch ▪ 𝑘 sei die Aussage „Kay war am Tatort.“ Verena und Kay mit. Außerdem habe der Manager von Uwe und Kay mitgeteilt, dass mindestens einer der beiden kommt.“ [Staa12] 62  Die einzig mögliche 𝑣 𝑚 𝑢 𝑘 ¬𝑘 𝑘 ∧ 𝑣 𝑣→𝑚 𝑚 → ¬𝑘 𝑢 → 𝑘∧𝑣 𝑢∨𝑘 Belegung ist, dass Kay alleine dort war. f f f f w f w w w f Aussagenlogik: f f f w f f w w w w Unser Mordfall f f w f w f w w f w f f w w f f w w f w f w f f w f w w w f ▪ Die Frage ist nun, welche Belegungen Modelle f w f w f f w f w w folgender Formelmenge sind: f w w f w f w w f w ℱ = 𝑣 → 𝑚 , 𝑚 → ¬𝑘 , 𝑢 → 𝑘 ∧ 𝑣 , 𝑢 ∨ 𝑘 f w w w f f w f f w ▪ Mit ein bisschen Fleißarbeit kann man eine w f f f w f f w w f Wahrheitstafel für alle Möglichkeiten erstellen. w f f w f w f w w w w f w f w f f w f w w f w w f w f w w w w w f f w f w w w f w w f w f w w f w w w w w f w f w w f w [Staa12] w w w w f w w f w w 63 Fragen? 64 Aussagenlogik: Denkaufgabe Wer lügt? Bianca lügt! Cäsar lügt! Amina und Bianca lügen! Amina Bianca Cäsar [Kröt21] 65  Amina: „Bianca lügt!“ Bianca: „Cäsar lügt!“ Cäsar: „Amina und Bianca lügen!“ 66 Übungsaufgaben 68 69 Fragen? 70 Aussagenlogik: Operatorvorrang ▪ Aus der Mathematik kennen wir Vorrangregeln wie „Punktrechnung vor Strichrechnung“, die das Weglassen von Klammern ermöglichen. Oft wird auch das Beispiele: Multiplikationszeichen weggelassen, z.B. schreiben wir 2𝑥 2 + 3𝑥 statt 2 ⋅ 𝑥 2 + 3 ⋅ 𝑥. 𝑎 ∧ 𝑏 = 𝑎𝑏 ▪ Solche Regeln gelten auch für logische Ausdrücke: 𝑎 ∨ 𝑏 ∧ 𝑐 = 𝑎 ∨ 𝑏𝑐 ▪ Klammern „( )“ werden zuerst ausgewertet. ¬𝑎 ∧ 𝑏 ∨ 𝑎 ∧ ¬𝑏 = ¬𝑎𝑏 ∨ 𝑎 ¬𝑏 ▪ Negation „¬“ hat Vorrang vor „∧“ (UND), das wiederum stärker bindet als „∨“ (ODER). ▪ Das „∧“-Zeichen kann weggelassen werden, ähnlich wie das Multiplikationszeichen. ▪ Bei gleichen Operatoren wird von links nach rechts ausgewertet. [Staa12] 71  ▪ Zwei logische Formeln 𝐹 und 𝐺 sind äquivalent, wenn für jede Belegung 𝐵 gilt: W𝐵 𝐹 = W𝐵 𝐺. Man schreibt 𝐹 ≡ 𝐺. ▪ Logisch äquivalente Formeln liefern also Aussagenlogik: für jede mögliche Eingabe jeweils das gleiche Ergebnis. Logische Äquivalenz ▪ Beispiel: 𝑎 ∨ 𝑏 ¬𝑎 ≡ ¬𝑎𝑎 ∨ ¬𝑎𝑏 ≡ f ∨ ¬𝑎𝑏 ≡ ¬𝑎𝑏 Wir sehen also, dass wir logische Formeln unterschiedlich darstellen können. 72 [Kröt21, Staa12] Aussagenlogik: Logische Äquivalenz: Beispiel 𝒂 𝒃 𝒂→𝒃 ¬𝒂 ¬𝒂 ∨ 𝒃 Wir zeigen mit einer f f w w w Wahrheitswertetabelle, dass gilt f w w w w 𝑎 → 𝑏 ≡ ¬𝑎 ∨ 𝑏. w f f f f w w w f w [Kröt21] 73 Aussagenlogik: ▪ Für die folgenden Betrachtungen sei ℒ die Menge aller aussagenlogischer Formeln. Logische ▪ Äquivalenzrelationen haben drei wesentliche Eigenschaften: Äquivalenz: ▪ Reflexivität: Es gilt 𝐹 ≡ 𝐹 für alle 𝐹 ∈ ℒ. Eigenschaften ▪ ▪ Symmetrie: Es gilt F ≡ 𝐺 ⇒ 𝐺 ≡ 𝐹 für alle 𝐹, 𝐺 ∈ ℒ. Transitivität: Aus 𝐹 ≡ 𝐺 und 𝐺 ≡ 𝐻 folgt 𝐹 ≡ 𝐻 (1) für alle 𝐹, 𝐺, 𝐻 ∈ ℒ. [Kröt21] 74  Aussagenlogik: Logische Äquivalenz: Eigenschaften (2) Satz Satz (1) Alle Tautologien sind logisch Zwei Formeln sind genau dann logisch äquivalent. äquivalent, wenn jede eine logische (2) Alle unerfüllbaren Formeln sind Konsequenz der anderen ist. logisch äquivalent. 𝐹 ≡ 𝐺 gilt genau dann, wenn gilt 𝐹 ⊨ 𝐺 und 𝐺 ⊨ 𝐹. [Kröt21] 75 Aussagenlogik: Name Definition Weitere Junktoren NAND 𝐹 ↑ 𝐹 ≡ ¬(𝐹 ∧ 𝐺) NOR 𝐹 ↓ 𝐹 ≡ ¬(𝐹 ∨ 𝐺) Wir können uns auch weitere Wahrheit ⊤ ≡ 𝑝 ∨ ¬𝑝 (für 𝑝 ∈ 𝑃) nützliche Junktoren definieren. Falschheit ⊥≡ 𝑝 ∧ ¬𝑝 (für 𝑝 ∈ 𝑃) [Kröt21] 76  Name Äquivalenz Idempotenzgesetze 𝐹∧𝐹 ≡𝐹 Aussagenlogik: Kommutativgesetze 𝐹∨𝐹 ≡𝐹 𝐹∧𝐺 ≡𝐺∧𝐹 Rechengesetze Assoziativgesetze 𝐹∨𝐺 ≡𝐺∨𝐹 (𝐹 ∧ 𝐺) ∧ 𝐻 ≡ 𝐹 ∧ (𝐺 ∧ 𝐻) (𝐹 ∨ 𝐺) ∨ 𝐻 ≡ 𝐹 ∨ (𝐺 ∨ 𝐻) ▪ Wir sind jetzt in der Lage, Absorptionsgesetze 𝐹 ∧ (𝐹 ∨ 𝐺) ≡ 𝐹 beliebig komplexe 𝐹 ∨ (𝐹 ∧ 𝐺) ≡ 𝐹 aussagenlogische Formeln zu formulieren. Distributivgesetze 𝐹∧ 𝐺∨𝐻 ≡ 𝐹∧𝐺 ∨ 𝐹∧𝐻 𝐹 ∨ 𝐺 ∧ 𝐻 ≡ 𝐹 ∨ 𝐺 ∧ (𝐹 ∨ 𝐻) ▪ Diese Formeln lassen sich auch umformen. Doppelte Negation ¬(¬𝐹) ≡ 𝐹 ▪ Hierzu gibt es einige DeMorgansche Regeln ¬ 𝐹 ∧ 𝐺 ≡ ¬𝐹 ∨ ¬𝐺 Rechenregeln, die leicht über ¬ 𝐹 ∨ 𝐺 ≡ ¬𝐹 ∧ ¬𝐺 Wahrheitstafeln bewiesen Neutralelementgesetze 𝐹∧⊤≡𝐹 werden können. 𝐹 ∨⊥≡ 𝐹 [Kröt21, Staa12] 77 Quiz https://partici.fi/33103264 78 Fragen? 79 Übungsaufgaben 80 81 Fragen? 82  Aussagenlogik: Normalformen ▪ Wir haben gesehen, dass eine logische Funktion durch unterschiedlich aussehende, aber äquivalente logische Ausdrücke dargestellt werden kann. ▪ Um Funktionen zu vergleichen, brauchen wir eine einheitliche Darstellung. ▪ Die Theorie der Normalformen besagt, dass jede logische Formel in eine standardisierte Form gebracht werden kann. [Staa12] 83 Aussagenlogik: Disjunktive und konjunktive Normalform Definition: Literal Definition: Konjunktions- und Disjunktionsterm Seien 𝑎1 , 𝑎2 , … 𝑎𝑛 ∈ 𝑃 paarweise Seien 𝑥1 , 𝑥2 , … 𝑥𝑛 paarweise verschiedene verschiedene atomare Aussagen. Sei 𝑥𝑖 Literale. Dann heißt der Ausdruck 𝑥1 ∧ 𝑥2 ∧ ⋯ ∧ 𝑥𝑛 eine negierte oder nicht negierte 𝑛-stelliger Konjunktionsterm (oder Monom) und atomare Aussage, also 𝑥𝑖 = 𝑎𝑖 oder der Ausdruck 𝑥1 ∨ 𝑥2 ∨ ⋯ ∨ 𝑥𝑛 heißt 𝑛-stelliger 𝑥𝑖 = ¬𝑎𝑖 für 𝑖 ∈ 1, 2,.. 𝑛 , dann Disjunktionsterm (oder Klausel). nennen wir 𝑥𝑖 ein Literal. [Kröt21, Staa12] 84 Aussagenlogik: Disjunktive und konjunktive Normalform Die disjunktive Normalform ist also ▪ eine ODER-Verknüpfung von UND- Ausdrücken, während die konjunktive Definition: Konjunktive und disjunktive Normalform eine UND-Verknüpfung Normalformen von ODER-Ausdrücken ist. Seien 𝐾1 , 𝐾2 , … , 𝐾𝑚 paarweise verschiedene Konjunktionsterme und 𝐷1, 𝐷2, … , 𝐷𝑚 paarweise verschiedene Disjunktionsterme, Jede aussagenlogische Formel lässt sich dann heißt in eine disjunktive und in eine 𝐾1 ∨ 𝐾2 ∨ ⋯ ∨ 𝐾𝑚 disjunktive konjunktive Normalform umformen. Normalform (DN) und Man braucht nur zwei Junktoren, um 𝐷1 ∧ 𝐷2 ∧ ⋯ ∧ 𝐷𝑚 konjunktive alles auszudrücken, was man Normalform (KN). aussagenlogisch ausdrücken kann. 85 [Kröt21, Staa12] Aussagenlogik: Disjunktive und konjunktive Normalform: Beispiele ▪ Beispiele für disjunktive Normalformen mit den drei logischen Variablen 𝑎, 𝑏, 𝑐 ∈ 𝑃: ▪ 𝐹1 = 𝑎¬𝑏𝑐 ∨ ¬𝑎𝑏 ∨ 𝑎𝑏𝑐 ▪ 𝐹2 = ¬𝑎𝑏𝑐 ∨ 𝑎¬𝑏𝑐 ∨ 𝑎𝑏¬𝑐 ∨ 𝑎¬𝑏¬𝑐 ▪ Beispiele für konjunktive Normalformen mit den drei logischen Variablen 𝑎, 𝑏, 𝑐: ▪ 𝐹3 = 𝑎 ∨ 𝑏 ∨ 𝑐 ¬𝑎 ∨ 𝑏 ∨ 𝑐 𝑎 ∨ 𝑏 ▪ 𝐹4 = ¬𝑎 ∨ ¬𝑏 ∨ ¬𝑐 ¬𝑎 ∨ 𝑏 ∨ ¬𝑐 ¬𝑎 ∨ ¬𝑏 ∨ ¬𝑐 ▪ Weder DN noch KN sind: ▪ 𝐹5 = ¬ 𝑎𝑏 ∨ 𝑐 ▪ 𝐹6 = 𝑎¬ 𝑏(𝑏 ∨ 𝑐) [Staa12] 86 Quiz https://partici.fi/33103264 87 Fragen? 88  Aussagenlogik: Algorithmus zur Erzeugung von Normalformen 1. Negationen eliminieren: Wende die DeMorgan’schen Regeln an, bis Negationen nur noch bei Variablen stehen. 2. Distributivgesetz anwenden: Wähle das passende Distributivgesetz je nach Ziel (DNF oder KNF). 3. Terme zusammenfassen: Doppelte Terme gemäß Idempotenzgesetz entfernen. 4. Neutralelemente streichen: ⊤ und ⊥ nach den Neutralelementgesetze eliminieren. 89 [Staa12] Wir bringen die Formel 𝐹 = ¬ 𝑎¬ 𝑏𝑐 ∨ ¬ 𝑎𝑏 𝑐 in eine disjunktive Normalform. 90 [Staa12] Übungsaufgaben 92 Fragen? 93  Aussagenlogik: Kanonische Normalformen ▪ Die bisher gefundenen Normalformen sind nicht eindeutig – es existieren verschiedene äquivalente Terme für dieselbe Funktion. ▪ Beispiel: Für 𝑭 = ¬ 𝒂¬ 𝒃𝒄 ∨ ¬ 𝒂𝒃 𝒄 ist sowohl ¬𝒂¬𝒄 ∨ 𝒂𝒃𝒄 als auch ¬𝒂𝒃¬𝒄 ∨ ¬𝒂¬𝒃¬𝒄 ∨ 𝒂𝒃𝒄 eine disjunktive Normalform. ▪ Im nächsten Schritt erfolgt die Vereinheitlichung durch kanonische disjunktive und kanonische konjunktive Normalformen. 94 [Staa12]  Aussagenlogik: Kanonische Normalformen ▪ Seien 𝐾1, 𝐾2 , … , 𝐾𝑛 paarweise verschiedene Konjunktionsterme und 𝐷1 , 𝐷2 , … , 𝐷𝑛 paarweise verschiedene Disjunktionsterme. Beispiel ▪ Wir nennen die disjunktive Normalform 𝐷𝑁 = 𝐾1 ∨ 𝐾2 ∨ ⋯ ∨ 𝐾𝑛 Der Term ¬𝑎¬𝑐∨𝑎𝑏𝑐 ist nicht bzw. die konjunktive Normalform 𝐾𝑁 = 𝐷1 ∧ 𝐷2 ∧ ⋯ ∧ 𝐷𝑛 kanonisch, weil im ersten kanonisch, kurz kDN bzw. kKN, wenn jeder Konjunktionsterm Konjunktionsterm das Atom 𝑏 bzw. jeder Disjunktionsterm alle atomaren Aussagen der fehlt. logischen Funktion enthält. ▪ Die entsprechenden Konjunktionsterme nennen wir dann Minterme. ▪ Die entsprechenden Disjunktionsterme nennen wir Maxterme. 95 [Staa12]  Aussagenlogik: Kanonische Normalformen ▪ Jede DN oder KN lässt sich in eine kDN oder kKN überführen, indem fehlende Variablen ohne Verfälschung des Terms hinzugefügt werden. ▪ Grundidee der Umformung: ▪ Sei 𝐹 = 𝑎 eine aussagenlogische Formel mit den Atomen 𝑎, 𝑏 ∈ 𝑃. ▪ 𝐹 ist nicht in kDN, weil der Term die Variable 𝑏 nicht enthält. ▪ Wir wissen, dass gilt: 𝑎 ≡ 𝑎 ∧ ⊤. Die Tautologie können wir jetzt mit dem fehlenden Atom ausdrücken als ⊤ ≡ 𝑏 ∨ ¬ 𝑏. ▪ Es gilt also: 𝑎 ≡ 𝑎 ∧ ⊤ ≡ 𝑎 ∧ 𝑏 ∨ ¬𝑏 ▪ Mit dem Distributivgesetz ergibt sich: 𝐹 ≡ 𝑎𝑏 ∨ 𝑎¬𝑏. Das ist die kDN. 96 [Staa12]  Aussagenlogik: Algorithmus zur Erzeugung der kanonischen disjunktiven Normalform (kDN) oder kanonischen konjunktiven Normalform (kKN) einer aussagenlogischen Formel 𝐹: Kanonische 1. Startpunkt: Beginne mit einer DN oder KN der Formel 𝐹. Prüfe, ob alle Min- bzw. Maxterme jedes Atom enthalten. Falls ja, Normalformen: haben wir bereits die gewünschte kDN/kKN. 2. Identifikation fehlender Variablen: Falls noch Variablen in Algorithmus Termen fehlen, wähle den ersten Konjunktionsterm 𝐾 (bzw. Disjunktionsterm 𝐷), in dem nicht alle Variablen vorkommen und ein fehlendes Atom 𝑎. 3. Erweiterung des Terms: Ersetze 𝐾 durch 𝐾 ∧ (𝑎 ∨ ¬𝑎) (bzw. Disjunktionsterm 𝐷 durch 𝐷 ∨ 𝑎 ∧ ¬𝑎 ). Wende anschließend das Distributivgesetz an. 4. Zusammenfassen gleicher Terme: Während des Prozesses können identische Terme entstehen. Wende das Idempotenzgesetz an, um gleiche Terme zusammenzufassen. 97 [Staa12]  Aussagenlogik: Beispiel: Wir bringen 𝐹 = ¬𝑎 ∨ ¬𝑏𝑐 in die kDN. Kanonische ¬𝑎 ∨ ¬𝑏𝑐 ≡ ¬𝑎 𝑏 ∨ ¬𝑏 ∨ ¬𝑏𝑐 𝑎 ∨ ¬𝑎 ≡ ¬𝑎𝑏 ∨ ¬𝑎¬𝑏 ∨ 𝑎¬𝑏𝑐 ∨ ¬𝑎¬𝑏𝑐 ≡ Normalformen: ¬𝑎𝑏 𝑐 ∨ ¬𝑐 ∨ ¬𝑎¬𝑏 𝑐 ∨ ¬𝑐 ∨ 𝑎¬𝑏𝑐 ∨ ¬𝑎¬𝑏𝑐 ≡ ¬𝑎𝑏𝑐 ∨ ¬𝑎𝑏¬𝑐 ∨ ¬𝑎¬𝑏𝑐 ∨ ¬𝑎¬𝑏¬𝑐 ∨ 𝑎¬𝑏𝑐 ∨ ¬𝑎¬𝑏𝑐 ≡ Algorithmus ¬𝑎𝑏𝑐 ∨ ¬𝑎𝑏¬𝑐 ∨ ¬𝑎¬𝑏𝑐 ∨ ¬𝑎¬𝑏¬𝑐 ∨ 𝑎¬𝑏𝑐 ∨ ¬𝑎¬𝑏𝑐 ≡ ¬𝑎𝑏𝑐 ∨ ¬𝑎𝑏¬𝑐 ∨ ¬𝑎¬𝑏𝑐 ∨ ¬𝑎¬𝑏¬𝑐 ∨ 𝑎¬𝑏𝑐 ≡ 98 [Staa12]  ▪ Die kanonischen Normalformen sind jetzt bis auf die Reihenfolge der Min-/Maxterme und die Reihenfolge der Aussagenlogik: Atome innerhalb der Terme gleich. Es gilt z.B. ¬𝑎𝑐𝑏 ∨ ¬𝑎𝑏¬𝑐 ∨ ¬𝑎¬𝑏𝑐 ∨ ¬𝑏¬𝑎¬𝑐 ∨ 𝑐𝑎¬𝑏 ≡ Kanonische ¬𝑎¬𝑏¬𝑐 ∨ ¬𝑎¬𝑏𝑐 ∨ ¬𝑎𝑏¬𝑐 ∨ ¬𝑎𝑏𝑐 ∨ 𝑎¬𝑏𝑐 Normalformen: ▪ Für die Vergleichbarkeit ist es jetzt natürlich schön, wenn wir auch hier eine einheitliche Regelung haben. Deswegen gelten folgende Regeln: Reihenfolge der ▪ Atom-Anordnung: Innerhalb der Terme werden die Atome in alphabetisch bzw. mit aufsteigenden Indizes Terme angeordnet. ▪ Anordnung der Min-/Maxterme: Bestehen die Min- /Maxterme jeweils aus 𝑛 Atomen. An ersetzen wir jedes negierte Atom durch eine 0, die unnegierten durch 1. So entsteht für jeden Term eine 𝑛–stellige Binärzahl. Die Terme werden innerhalb der Formel aufsteigend nach dieser Binärzahl sortiert. 99 [Staa12]  Aussagenlogik: Kanonische Normalformen: Reihenfolge der Terme: Beispiel ¬𝑎𝑏𝑐 ∨ ¬𝑎𝑏¬𝑐 ∨ ¬𝑎¬𝑏𝑐 ∨ ¬𝑎¬𝑏¬𝑐 ∨ 𝑎¬𝑏𝑐 Sortierte Form mit eindeutiger Anordnung ¬𝑎¬𝑏¬𝑐 ∨ ¬𝑎¬𝑏𝑐 ∨ ¬𝑎𝑏¬𝑐 ∨ ¬𝑎𝑏𝑐 ∨ 𝑎¬𝑏𝑐 100 [Staa12] Quiz https://partici.fi/33103264 101 Wir bringen die Formel 𝐹(𝑎, 𝑏) = ¬(𝑎¬𝑏)(𝑎¬𝑏 ∨ ¬𝑎) in die kanonische disjunktive Normalform. 102 [Staa12] Fragen? 104 Aussagenlogik: Kanonische Normalformen: Vorteile Vereinheitlichung Ermöglichen den Vergleich von logischen Ausdrücken. und Leicht zu prüfen, ob zwei Ausdrücke logisch äquivalent sind. Vergleichbarkeit Vereinfachung der Klar strukturierte Form macht logische Ausdrücke leichter auswertbar. Auswertung Besonders nützlich in Algorithmen und Schaltkreisen. 105  Hardwareentwurf Logische Ausdrücke lassen sich in Logikgattern umsetzen. KNF und DNF erleichtern den Entwurf von digitalen Schaltungen. Aussagenlogik: KNF wird häufig zur Umsetzung von NAND-Gattern genutzt. Kanonische Algorithmik Normalformen: SAT-Solver nutzen häufig die konjunktive Normalform (KNF) für die Prüfung der Erfüllbarkeit. Anwendung Automatisierung von logischen Entscheidungsproblemen. DNF hilft, verschiedene Erfüllbarkeitsmöglichkeiten einer logischen Formel aufzulisten. 106 Übungsaufgaben 107 108  Aussagenlogik: Resolution: Entstehung der KI ▪ Mit den ersten elektronischen Rechenanlagen kam der Begriff „Elektronengehirn“ auf. ▪ Dies markierte den Beginn der Forschung zur „Künstlichen Intelligenz“ (KI), englisch „Artificial Intelligence“ (AI). ▪ Frühe Hoffnungen: Computer könnten menschliche Intelligenz nachahmen oder sogar übertreffen. ▪ Viele prognostizierte Szenarien der KI-Forschung traten bisher nicht ein. ▪ Dennoch gibt es heute KI-Technologien, die in spezialisierten Anwendungsbereichen intelligentes Verhalten zeigen. 109 [Staa12]  Aussagenlogik: Resolution: Ziele der KI ▪ Eine präzise Definition menschlicher Intelligenz bleibt schwierig. ▪ Fokus: Die Fähigkeit, logisch korrekte Schlussfolgerungen aus gegebenen Voraussetzungen zu ziehen. ▪ Ziel: Ein automatisierbarer Schlussfolgerungsmechanismus, der auf Computern implementierbar ist. ▪ Das Verfahren „Resolution“ ermöglicht dies und wird im Kontext der Aussagenlogik und KI- Programmiersprachen wie PROLOG erläutert. 110 [Staa12]  Aussagenlogik: Resolution ▪ Beispiel: Wenn aus einem Sachverhalt a 𝒂 𝒃 𝒄 𝒂→𝒃 𝒃 →c 𝒂 → 𝒃 ∧ (𝒃 → 𝒄) 𝒂→c 𝑭 der Sachverhalt b folgt und aus b f f f w w w w w wiederum c folgt, dann kann man auch f f w w w w w w von a auf c schließen. f w f w f f w w ▪ Diese Schlussfolgerungskette können wir f w w w w w w w so darstellen: w f f f w f f w 𝐹 = 𝑎 → 𝑏 ∧ 𝑏 → 𝑐 → (𝑎 → 𝑐) w f w f w f w w w w f w f f f w ▪ Mit der Wahrheitstafel zeigen wir, das w w w w w w w w diese Formel für jede Belegung wahr ist. 111 [Staa12] Aussagenlogik: Resolution ▪ Für Schlussfolgerungen haben wir bereits die Logische Konsequenz logische Konsequenz kennengelernt. Sei ℱeine Menge aussagenlogischer ▪ In unserem Fall ist ℱ = { a → 𝑏 , (𝑏 → 𝑐) } und Formeln. Eine aussagenlogische 𝐺 = (𝑎 → 𝑐) Formel 𝐺 ist eine logische Konsequenz aus ℱ, wenn jedes ▪ Wir haben gezeigt, dass gilt ℱ ⊨ 𝐺, also Modell von ℱ auch ein Modell von 𝐺 { a → 𝑏 , (𝑏 → 𝑐) } ⊨ (𝑎 → 𝑐) ist. Wir schreiben dann ℱ ⊨ 𝐺. ▪ Jedes Modell (also jede Belegung), das beide Formeln aus ℱ wahr macht, macht auch 𝐺 wahr. 112  Aussagenlogik: Resolution ▪ In unserem Fall gilt: { a → 𝑏 , (𝑏 → 𝑐) } ⊨ (𝑎 → 𝑐) ▪ Dann ist klar, das die Negation der Folgerung also ¬(𝑎 → 𝑐) im Widerspruch zu den Voraussetzungen stehen muss. ▪ Dementsprechend muss der Ausdruck 𝑎 → 𝑏 ∧ 𝑏 → 𝑐 ∧ ¬(𝑎 → 𝑐) unerfüllbar, also immer falsch sein. ▪ Das ist das Grundprinzip der Resolution: Wenn wir beweisen wollen, dass für ℱ = 𝐹1 , … , 𝐹𝑛 , und eine Formel 𝐺 gilt ℱ ⊨ 𝐺, dann zeigen wir, dass 𝐹1 ∧ ⋯ ∧ 𝐹𝑛 ∧ ¬𝐺 unerfüllbar ist. 113 [Staa12]  ▪ Wir haben bereits gesehen, dass ein 𝑛- stelliger Disjunktionsterm 𝑥1 ∨ 𝑥2 ∨ ⋯ ∨ 𝑥𝑛 auch Klausel genannt wird. ▪ Der Term (𝑎 ∨ 𝑏 ∨ ¬𝑐) ist also eine Klausel. ▪ Das Resolutionsverfahren beginnt mit der Umwandlung des gegebenen Ausdrucks in die konjunktive Normalform. Diese besteht Aussagenlogik: aus einer Menge von Klauseln, die ausschließlich durch UND verknüpft sind. Resolution 114  Aussagenlogik: Resolution: Verfahren ▪ Wir zeigen { a → 𝑏 , (𝑏 → 𝑐) } ⊨ (𝑎 → 𝑐) indem wir die Unerfüllbarkeit der Formel 𝑎 → 𝑏 ∧ 𝑏 → 𝑐 ∧ ¬(𝑎 → 𝑐) aufzeigen. ▪ Ausgangspunkt des Resolutionsverfahrens ist die Umwandlung eines Ausdrucks in die Konjunktive Normalform. Wir formen also zuerst die Formel in KN um: 𝑎 →𝑏 ∧ 𝑏 →𝑐 ∧¬ 𝑎 →𝑐 ≡ ¬𝑎 ∨ 𝑏 ∧ ¬𝑏 ∨ 𝑐 ∧ ¬ ¬𝑎 ∨ 𝑐 ≡ ¬𝑎 ∨ 𝑏 ∧ ¬𝑏 ∨ 𝑐 ∧ ¬¬𝑎 ∧ ¬𝑐 ≡ ¬𝑎 ∨ 𝑏 ∧ ¬𝑏 ∨ 𝑐 ∧ 𝑎 ∧ ¬𝑐 ▪ Wir erhalten die Klauselmenge { ¬𝑎 ∨ 𝑏 , ¬𝑏 ∨ 𝑐 , 𝑎, ¬𝑐} 115 [Staa12]  Aussagenlogik: Resolution: Resolvente ▪ Betrachten wir die Klauseln ¬𝑎 ∨ 𝑏 und ¬𝑏 ∨ 𝑐 : ▪ Hier tritt die Variable 𝑏 in widersprüchlicher Form auf (einmal negiert, einmal nicht negiert). ▪ In einer Belegung, die die gesamte KN wahr macht, kann 𝑏 keine Rolle spielen. Dass beide Klauseln gleichzeitig wahr werden, hängt also nur von 𝑎 und 𝑐 ab. ▪ Wir stellen diesen Sachverhalt dar, indem wir die beiden Klauseln zu einer neuen Klausel (¬𝑎 ∨ 𝑐) zusammenfassen („resolvieren“). ▪ Die neu entstandene Klausel heißt Resolvente. ▪ Die Resolvente ist nicht äquivalent zu den ursprünglichen Klauseln! Ihre Bedeutung liegt darin, dass die ursprünglichen Klauseln nur dann gleichzeitig erfüllbar sind, wenn auch die Resolvente erfüllbar ist; dies stellt eine notwendige Bedingung dar. ▪ Wenn es gelingt, die leere Klausel zu bilden, die immer unerfüllbar ist, beweist dies die Unerfüllbarkeit der gesamten Formel. 116 [Staa12]  Aussagenlogik: Resolution: Weiterführung des Verfahrens ▪ Die Resolvente (¬𝑎 ∨ 𝑐) wird mit der Klausel 𝑎 kombiniert. ▪ Dadurch ergibt sich 𝑐 als weitere Resolvente. ▪ Übrig bleiben zwei Klauseln: ▪ 𝑐 (aus den bisherigen Schritten) ▪ ¬𝑐 (eine bisher nicht verwendete Klausel) ▪ Da (𝑐 ∧ ¬𝑐) immer falsch ist, leiten wir die sogenannte leere Klausel (□) ab. ▪ Die leere Klausel sagt aus, dass wir einen Widerspruch haben. Somit ist die Klauselmenge unerfüllbar. 117 [Staa12]  Aussagenlogik: Resolution: Ergebnis ▪ Wir haben gezeigt, dass gilt: 𝑎 →𝑏 ∧ 𝑏 →𝑐 ∧¬ 𝑎 →𝑐 ⊨□ ▪ Wir haben also aus der negierten Schlussfolgerung einen Widerspruch abgeleitet. ▪ Das bedeutet, dass die Schlussfolgerung { a → 𝑏 , (𝑏 → 𝑐) } ⊨ (𝑎 → 𝑐) korrekt ist. 118 [Staa12]  Aussagenlogik: Resolution: Vereinfachungen ▪ Weglassen der UND-Verknüpfung: ▪ Statt der KN (¬𝑎 ∨ 𝑏) ∧ (¬𝑏 ∨ 𝑐) ∧ 𝑎 ∧ ¬𝑐 schreiben wir direkt die Klauselmenge: {(¬𝑎 ∨ 𝑏), (¬𝑏 ∨ 𝑐), 𝑎, ¬𝑐}. ▪ Mengenschreibweise: ▪ Innerhalb einer Klausel wird das ∨ weggelassen. ▪ Literale werden durch Kommata getrennt. ▪ Beispiel: { ¬𝑎, 𝑏 , ¬𝑏, 𝑐 , 𝑎 , ¬𝑐 } 119 [Staa12]  Aussagenlogik: ▪ Resolvente von zwei Klauseln Resolution: ▪ Voraussetzung: Klausel 𝐴 enthält das Literal 𝑎. Resolventenbildung ▪ ▪ Klausel 𝐵 enthält das Literal ¬𝑎. ▪ Resolvente: ▪ Das Ausführen eines einzelnen Resolutionsschritts wird mit dem Operator res dargestellt. ▪ res{𝐴, 𝐵} enthält alle Literale aus 𝐴 und 𝐵, außer 𝑎 und ¬𝑎. ▪ Formulierung in Mengenalgebra: ▪ res{𝐴, 𝐵} = 𝐴\{𝑎} ∪ 𝐵\{¬𝑎} 120 [Staa12]  Aussagenlogik: ▪ Behauptung: ▪ Folgende Behauptung soll mittels Resolution bewiesen Resolution: Beispiel oder widerlegt werden: (𝑏 → (¬𝑎 ∨ 𝑐)) ∧ (¬𝑐 → 𝑎) ∧ 𝑐 ⊨ ¬𝑏 ▪ Klauselmenge: ▪ Nach Umwandlung in KN erhalten wir die Klauselmenge: ▪ {{¬𝑏, ¬𝑎, 𝑐}, {𝑐, 𝑎}, {𝑐}, {𝑏}} ▪ Resolution-Schritte: ▪ Wir versuchen, durch Resolution die leere Klausel abzuleiten. 1. res{{¬𝑏, ¬𝑎, 𝑐}, {𝑐, 𝑎}} = {¬𝑏, 𝑐} 2. res{{¬𝑏, 𝑐}, {𝑏}} = {𝑐} Keine leere Klausel ableitbar ⇒ Behauptung ist falsch. 121 [Staa12] Quiz https://partici.fi/33103264 122 Übungsaufgaben 123 124  Logelei ▪ In einem abgelegenen Inselreich gibt es zwei Gruppen von Menschen: ▪ Die einen (Typ W) sagen immer die Wahrheit. ▪ Die anderen (Typ L) lügen immer. ▪ Wir besuchen einige Inseln und fragen die Bewohner*innen, welchem Typ die Einheimischen angehören. ▪ Auf Insel A sagen alle Bewohner*innen: „Wir sind hier alle vom gleichen Typ.“ ▪ Ist diese Aussage korrekt? Und falls ja, welchem Typ gehören die Einheimischen an? ▪ Auf Insel B sagen alle Bewohner*innen: „Auf dieser Insel gibt es sowohl Menschen vom Typ W als auch vom Typ L.“ ▪ Was verrät uns diese Aussage über die Einheimischen von Insel B? 125 [Kröt24] Fragen? 126 Prädikatenlogik 127 Präsikatenlogik: Unterscheid zur Aussagenlogik ▪ Die Prädikatenlogik gibt atomaren Aussagen eine innere Struktur: ▪ aus „𝑝Sokrates ist ein Mensch“ wird „istMensch(sokrates)“. ▪ So können mehrere Objekte dieselbe Eigenschaft teilen: ▪ istMensch(sokrates), istMensch(anton), istMensch(zahra). ▪ Für allgemeine Aussagen über Objekte, die eine bestimmte Eigenschaft besitzen, stehen zwei Quantoren zur Verfügung: ▪ Existenzquantor (∃): Es gibt mindestens ein Objekt mit dieser Eigenschaft. ▪ Allquantor (∀): Alle Objekte besitzen diese Eigenschaft. [Kröt24] 128  Prädikatenlogik: Beispiele ▪ „Alle Menschen sind sterblich.“ ∀𝑥. istMensch 𝑥 → istSterblich 𝑥 ▪ „Es ist nicht alles Gold was glänzt“. ∃𝑥. (glänzt 𝑥 ∧ ¬istGold 𝑥 ) ▪ „Null ist eine natürliche Zahl und jede natürliche Zahl hat einen Nachfolger, der ebenfalls eine natürliche Zahl ist“. NatNum null ∧ ∀𝑥. NatNum 𝑥 → ∃𝑦. succ 𝑥, 𝑦 ∧ NatNum 𝑦 [Kröt24] 129  Prädikatenlogik: Syntax: Grundelemente ▪ In der Aussagenlogik haben wir alles aus einer unendlichen Menge von Atomen aufgebaut. ▪ In der Prädikatenlogik betrachten wir mehrere Mengen ▪ Eine Menge 𝑉 von Variablen 𝑥, 𝑦, 𝑧, … Atom ▪ Eine Menge 𝐶 von Konstanten 𝑎, 𝑏, 𝑐, … Ein prädikatenlogisches Atom ▪ Eine Menge 𝑃 von Prädikatensymbolen 𝑝, 𝑞, 𝑟, … Dabei hat jedes ist ein Ausdruck 𝑝 𝑡1, … , 𝑡𝑛 für Prädikat eine Stelligkeit ≥ 0. ein 𝑛-stelliges Variablen und Konstanten bezeichnet man auch mit dem Überbegriff Prädikatensymbol 𝑝 ∈ 𝑃 und Terme. Terme 𝑡1 , … , 𝑡𝑛 ∈ 𝑉 ∪ 𝐶. Die Mengen 𝑉, 𝐶 und 𝑃 sind ▪ abzählbar unendlich, ▪ disjunkt (Es ist also immer eindeutig , zu welcher Menge ein Symbol gehört) 130 [Kröt24]  Prädikatenlogik: Syntax: Formeln ▪ Die Formeln werden wie in der Aussagenlogik aus Atomen aufgebaut. ▪ Wir definieren die Menge der prädikatenlogischen Formeln 1. Ordnung wie folgt: ▪ Jedes Atom 𝑝 𝑡1 , … , 𝑡𝑛 ist eine prädikatenlogische Formel. ▪ Ist 𝑥 ∈ 𝑉 ein Variable und sind 𝐹 und 𝐺 prädikatenlogische Formeln, dann sind auch folgende Ausdrücke prädikatenlogische Formeln: ▪ ¬𝐹: Negation ▪ (𝐹 ∧ 𝐺): Konjunktion Wir haben also alle aus der ▪ (𝐹 ∨ 𝐺): Disjunktion Aussagenlogik bekannten Junktoren ▪ (𝐹 → 𝐺): Implikation ▪ (𝐹 𝐺): Äquivalenz ▪ ∃𝑥. 𝐹: Existenzquantor („Es gibt ein 𝑥, für das 𝐹 gilt.“) ▪ ∀𝑥. 𝐹: Existenzquantor („Für alle 𝑥 gilt 𝐹.“) 131 [Kröt24, Staa12]  Prädikatenlogik: Konventionen und Vereinfachungen ▪ Wir vereinfachen die Syntax durch folgende Regeln: 1. Weglassen von Klammern bei nullstelligen Prädikaten: z. B. 𝑝 → 𝑞 statt 𝑝() → 𝑞() 2. Weglassen der äußeren Klammern: z.B. 𝑝 → 𝑞 statt (𝑝 → 𝑞) 3. Vereinfachung bei Konjunktionen/Disjunktionen: z.B. 𝑝 ∧ 𝑞 ∧ 𝑟 statt 𝑝 ∧ (𝑞 ∧ 𝑟) 4. Zusammenfassen gleicher Quantoren: ∀𝑥, 𝑥 ′. ∃𝑦, 𝑦 ′. (𝑝 𝑥, 𝑥 ′ → 𝑝 𝑦, 𝑦 ′ ) statt ∀𝑥. ∀𝑥 ′. ∃𝑦. ∃𝑦 ′. (𝑝 𝑥, 𝑥 ′ → 𝑝 𝑦, 𝑦 ′ ) [Kröt24] 132 Quiz https://partici.fi/33103264 133 Übungsaufgaben 134 135  Prädikatenlogik: Teilformeln ▪ Teilformeln einer Formel sind sämtliche Teilausdrücke, die ebenfalls Formeln sind. Die Menge dieser Teilformeln ist eindeutig bestimmt, wenn man die formale Definition der Formel zugrunde legt. ▪ Beispiel: Die Teilformeln von ∀𝑥. 𝑝 𝑥 ∨ 𝑞 𝑥 ∧ 𝑟 𝑥 sind: 𝑝 𝑥 ∨ 𝑞 𝑥 ∧𝑟 𝑥 , 𝑞 𝑥 ∧𝑟 𝑥 ,𝑝 𝑥 ,𝑞 𝑥 ,𝑟 𝑥 und die komplette Formel selber. Aber nicht 𝑝 𝑥 ∨ (𝑞(𝑥) oder ∀𝑥. (𝑝(𝑥). 136 [Kröt24]  Prädikatenlogik: Freie und gebundene Variablen ▪ Jede Variable kann in einer Formel entweder frei oder gebunden vorkommen. ▪ Freie Variable: ▪ Kommt in einer Formel vor, ohne von einem Quantor eingeschränkt zu sein. ▪ Ihr Wert ist nicht festgelegt und kann beliebig sein. ▪ Beispiel: In 𝑝(𝑥) ist 𝑥 frei. ▪ Gebundene Variable: ▪ Steht im Geltungsbereich eines Quantors (∀, ∃). ▪ Ihr Wert ist durch den Quantor festgelegt. ▪ Beispiel: In ∀𝑥. 𝑝(𝑥) ist 𝑥 gebunden durch ∀. 137 [Kröt24]  Prädikatenlogik: Offene und geschlossene Formeln Geschlossene Formel Offene Formel Formeln, in denen keine freien Formeln, in denen freien Variablen vorkommen, heißen Variablen vorkommen, heißen geschlossene Formeln oder offene Formeln. Sätze. Hinweis: ▪ Eigentlich möchte man sich auf Sätze beschränken, da diese geschlossene Aussagen darstellen. ▪ Jedoch ist es notwendig, auch offene Formeln zu betrachten, da diese auftreten, sobald man Teilformeln einer geschlossenen Formel untersucht – was in vielen Definitionen und Beweisen geschieht. 138 [Kröt24]  Prädikatenlogik: Semantik ▪ Grundidee: Der Wahrheitswert von Formeln ▪ Dazu müssen drei Fragen geklärt werden: soll sich aus den Wahrheitswerten der Was bedeutet 𝒑? atomaren Bestandteile ergeben, wie in der Prädikatssymbole repräsentieren Relationen einer Aussagenlogik. bestimmten Stelligkeit. ▪ Beispiel: Wir haben ein Atom 𝑝(𝑎, 𝑥) mit einer Was bedeutet 𝒂? Konstanten 𝑎 ∈ 𝐶 und einer Variablen 𝑥 ∈ 𝑉. Konstanten stehen für feste Elemente, die in Wie kann man diesem Ausdruck einen Relationen auftreten können. Wahrheitswert zuordnen? Was bedeutet 𝒙? Variablen stehen ebenfalls für Elemente, aber sie können je nach Vorkommen für unterschiedliche Elemente stehen. Ein Atom 𝑝(𝑎, 𝑥) ist also wahr, wenn die Relation 𝑝 zwischen dem Element 𝑎 und dem [Kröt24] Element 𝑥 besteht. 139  Prädikatenlogik: Interpretationen ▪ Die Belegung der Aussagenlogik wird durch Interpretationen und Variablenzuweisungen ersetzt. Interpretation Zuweisung Eine Interpretation ℐ ist ein Paar Δℐ ,.ℐ , bestehend aus Eine Zuweisung 𝒵 für eine Interpretation ℐ einer nichtleeren Grundmenge Δℐ (der Domäne) und einer ist eine Funktion 𝑍: 𝑉 → Δℐ , die Variablen Interpretationsfunktion.ℐ , die: auf Elemente der Domäne abbildet. Für 𝑥 ∈ jede Konstante 𝑎 ∈ 𝐶 auf ein Element aℐ ∈ Δℐ und 𝑉 und 𝛿 ∈ Δℐ 𝑣erwenden wir die Notation jedes 𝑛-stellige Prädikatensymbol 𝑝 ∈ 𝑃 auf eine 𝑍 𝑥 ↦ 𝛿 für die Zuweisung, die 𝑥 auf 𝛿 𝑛 Relation 𝑝 ℐ ⊆ Δℐ abbildet und alle anderen Variablen y ≠ 𝑥 abbildet. auf 𝑍 𝑦. 140 [Kröt24]  Prädikatenlogik: Interpretationen: Beispiel ▪ „Null ist eine natürliche Zahl und jede natürliche Zahl hat einen Nachfolger, der ebenfalls eine natürliche Zahl ist“. NatNum null ∧ ∀𝑥. NatNum 𝑥 → ∃𝑦. succ 𝑥, 𝑦 ∧ NatNum 𝑦 ▪ Wir betrachten die Interpretation ℐ mit ▪ Δℐ = ℝ , die Menge der reellen Zahlen. ▪ null ℐ = 0 ▪ NatNumℐ = ℕ ⊆ ℝ, Menge der natürlichen Zahlen ▪ succ ℐ = 𝑑, 𝑒 |𝑑, 𝑒 ∈ ℝ, 𝑑 < 𝑒 Unter dieser Interpretation ist das Atom NatNum null wahr, da null ℐ ∈ NatNumℐ gilt. Wir schreiben daher: NatNum null = 1. 141 [Kröt24]  Prädikatenlogik: Interpretationen: Beispiel (Fortsetzung) ▪ Wir betrachten nun für die Interpretation ℐ die Zuweisung 𝒵 mit ▪ 𝒵 𝑥 = 47 ▪ 𝒵 𝑦 = 11 Unter dieser Interpretation und Zuweisung ist das Atom succ(𝑥, 𝑦) falsch, da 𝒵 𝑥 , 𝒵 𝑦 ∉ succ ℐ gilt. In diesem Fall schreiben wir succ 𝑥, 𝑦 ℐ,𝒵 = 0 Hinweis: Bei Interpretationen und Zuweisungen werden nur die Belegungen angegeben, die für die Auswertung einer bestimmten Formel relevant sind. Es ist also nicht erforderlich, 𝒵 für alle 𝑥 ∈ 𝑉 zu definieren. 142 [Kröt24]  Prädikatenlogik: Atome interpretieren ▪ Wir ermitteln die Wahrheit von Atomen entsprechend einer gegebenen Interpretation und Zuweisung. Wichtig: Wir nutzen Interpretationen ▪ Sei ℐ eine Interpretation und 𝒵 eine Zuweisung für ℐ. und Zuweisungen auf zwei Ebenen, die ▪ Für jede Konstante 𝑐 ∈ 𝐶 definieren wir 𝑐 ℐ,𝒵 = 𝑐 ℐ nicht verwechselt werden dürfen: ▪ Für jede Variable 𝑥 ∈ 𝑉 definieren wir 𝑥 ℐ,𝒵 =𝒵(𝑥) 1. Zur Abbildung von Termen 𝑡 auf Elemente 𝑡 ℐ,𝒵 ∈ Δℐ Für ein Atom 𝑝(𝑡1 , … , 𝑡𝑛 ) setzen wir: 2. Zur Abbildung von Atomen 𝑝 auf ▪ 𝑝(𝑡1 , … , 𝑡𝑛 )ℐ,𝒵 = 1, falls 𝑡1ℐ,𝒵 , … , 𝑡𝑛ℐ,𝒵 ∈ 𝑝 ℐ und Wahrheitswerte 𝑝 ℐ,𝒵 ∈ 0,1 ▪ 𝑝(𝑡1 , … , 𝑡𝑛 )ℐ,𝒵 = 0, falls 𝑡1ℐ,𝒵 , … , 𝑡𝑛ℐ,𝒵 ∉ 𝑝 ℐ. 143 [Kröt24]  Prädikatenlogik: Formeln interpretieren ▪ Eine Interpretation ℐ und 𝒵 eine Zuweisung für ℐ, erfüllen eine Formel 𝐹, kurz ℐ, 𝒵 ⊨ 𝐹 , wenn eine der folgenden rekursiven Bedingungen zutrifft: Formel 𝑭 𝓘, 𝓩 ⊨ 𝑭 , wenn 𝓘, 𝓩 ⊭ 𝐹 , wenn 𝑝 Atom 𝑝 ℐ,𝒵 = 1 𝑝 ℐ,𝒵 = 0 ¬𝐺 ℐ, 𝒵 ⊭ 𝐺 ℐ, 𝒵 ⊨ 𝐺 (𝐺1 ∧ 𝐺2) ℐ, 𝒵 ⊨ 𝐺1und ℐ, 𝒵 ⊨ 𝐺2 ℐ, 𝒵 ⊭ 𝐺1 oder ℐ, 𝒵 ⊭ 𝐺2 (𝐺1 ∨ 𝐺2) ℐ, 𝒵 ⊨ 𝐺1oder ℐ, 𝒵 ⊨ 𝐺2 ℐ, 𝒵 ⊭ 𝐺1 und ℐ, 𝒵 ⊭ 𝐺2 (𝐺1 → 𝐺2 ) ℐ, 𝒵 ⊭ 𝐺1oder ℐ, 𝒵 ⊨ 𝐺2 ℐ, 𝒵 ⊨ 𝐺1 und ℐ, 𝒵⊭𝐺2 (𝐺1 𝐺2) ℐ, 𝒵 ⊨ 𝐺1 und ℐ, 𝒵 ⊨ 𝐺2 ℐ, 𝒵 ⊭ 𝐺1 und ℐ, 𝒵 ⊨ 𝐺2 oder oder ℐ, 𝒵 ⊭ 𝐺1 und ℐ, 𝒵 ⊭ 𝐺2 ℐ, 𝒵 ⊭ 𝐺1 und ℐ, 𝒵 ⊨ 𝐺2 ∀𝑥. 𝐺 ℐ, 𝒵 𝑥 ↦ 𝛿 ⊨ 𝐺 für alle 𝛿 ∈ Δℐ ℐ, 𝒵 𝑥 ↦ 𝛿 ⊭ 𝐺 für mindestens ein 𝛿 ∈ Δℐ ∃𝑥. 𝐺 ℐ, 𝒵 𝑥 ↦ 𝛿 ⊨ 𝐺 für mindestens ein 𝛿 ∈ Δℐ ℐ, 𝒵 𝑥 ↦ 𝛿 ⊭ 𝐺 für alle 𝛿 ∈ Δℐ 144 [Kröt24]  Prädikatenlogik: Formeln interpretieren: Beispiel ▪ „Null ist eine natürliche Zahl und jede natürliche Zahl hat einen Nachfolger, der ebenfalls eine natürliche Zahl ist“. 𝐹 = NatNum null ∧ ∀𝑥. NatNum 𝑥 → ∃𝑦. succ 𝑥, 𝑦 ∧ NatNum 𝑦 ▪ Wir betrachten die Interpretation ℐ mit ▪ Δℐ = ℝ , die Menge der reellen Zahlen. ▪ null ℐ = 0 ▪ NatNumℐ = ℕ ⊆ ℝ, Menge der natürlichen Zahlen ▪ succ ℐ = 𝑑, 𝑒 |𝑑, 𝑒 ∈ ℝ, 𝑑 < 𝑒 Notation: Bei der Interpretation von Sätzen (Formeln ohne freie Variablen) Dann gilt ℐ ⊨ 𝐹. sind Zuweisungen irrelevant. Daher werden sie in diesem Fall auch nicht angegeben. 145 [Kröt24]  Prädikatenlogik: Logik auf Sätzen ▪ In vielen Fällen konzentrieren wir uns auf Sätze: In den meisten Anwendungen wird ausschließlich mit Sätzen gearbeitet. Daher reicht es aus, nur Interpretationen zu betrachten. Zuweisungen dienen in diesem Kontext lediglich als technisches Hilfsmittel zur Definition der Bedeutung von Sätzen. ▪ Eine Sammlung von Sätzen wird oft als Theorie bezeichnet. 146 [Kröt24]  Prädikatenlogik: Übergang von Umgangssprache zur Prädikatenlogik ▪ Wir haben gesehen, dass Umwandlung von umgangssprachlichen Aussagen in die Sprache der Prädikatenlogik nicht immer klar ist. Dieses Phänomen haben wir fast immer eine Modellbildung. ▪ Beispiel: Wir betrachten die Aussage: „Es gibt keinen Menschen, der weiter als 20m springt“. Die könnte man formulieren als: ¬∃𝑥. (istMensch 𝑥 ∧ springtWeiter 𝑥, 20 ). ▪ Wenn allerdings bereits klar ist, dass unsere Domäne Δℐ die Menge aller Menschen ist, kann das Prädikat istMensch 𝑥 entfallen. Es wäre dann ja eine Tautologie. ▪ Man könnte anstelle des zweistelligen Prädikats springtWeiter 𝑥, 𝑦 auch ein weniger flexibles einstelliges Prädikat springtWeiter 𝑥 verwenden. ▪ … 147 [Staa12]  Prädikatenlogik: Anwendungen ▪ Anwendungsbereich: Die Prädikatenlogik 1. Ordnung wird in vielen Bereichen der Informatik genutzt, speziell in der Künstlichen Intelligenz und wissensbasierten Systemen. ▪ Wissensmodellierung: Sie ermöglicht die Modellierung von Wissen über bestimmte Themenbereiche durch Fakten und Regeln. ▪ Inferenzmechanismen: Durch automatisierte Schlussfolgerungsmechanismen (Inferenzmechanismen) können aus vorhandenem Wissen neue Erkenntnisse gewonnen werden. ▪ Expertensysteme: Systeme, die Benutzerfragen ähnlich wie menschliche Experten beantworten, werden als Expertensysteme bezeichnet. ▪ Zentrale Herausforderungen: ▪ Repräsentationsproblem: Wissen der realen Welt in geeigneter Form repräsentieren. ▪ Inferenzproblem: Schlussfolgerungen aus dem Wissen maschinell ziehen. 148 [Staa12] Fragen? 149 Logisches Programmieren 150  Definition: Logisches Programmieren ist Programmierparadigma, das auf Logik und Mathematik basiert. Ziel: Probleme durch logische Schlussfolgerungen statt durch explizite Anweisungen lösen Logisches Programmieren: Deklarative Natur: Beschreibt was gelöst werden soll, nicht wie. Grundidee Prinzipien: Regeln und Fakten: Wissen wird durch Regeln und Fakten modelliert Beispielsprachen: PROLOG (Programming in Logic), Datalog 151  Fakten: Stellen Wissen über die Welt dar (z.B., "Sokrates ist ein Mensch.") Regeln: Logisches Drücken Bedingungen aus (z.B., "Wenn jemand ein Mensch ist, ist er sterblich.") Programmieren: Ziele und Fragen: Zentrale Konzepte Durch Abfragen können neue Informationen abgeleitet werden Inferenzmechanismen: Nutzen logische Schlussfolgerung (z.B., Resolution), um Wissen zu verarbeiten und Antworten abzuleiten 152  Logisches Programmieren PROLOG (Programming in Repräsentationsproblem: Inferenzproblem: Resolution als Logic): Inferenzmechanismus: Programmiersprache auf Wissen über reale Maschinelles Ableiten von Automatisierbare Basis der Prädikatenlogik 1. Gegenstandsbereiche neuen Erkenntnissen aus Schlussfolgerungstechnik Ordnung. strukturiert und maschinell bestehendem Wissen. der Aussagenlogik. Eignet sich zur interpretierbar darstellen. Nutzung von Auch auf die Repräsentation von Wissen Ermöglicht die Modellierung Schlussfolgerungsmechani Prädikatenlogik übertragbar und zur automatisierten komplexer Sachverhalte. smen zur und grundlegend für Verarbeitung von Wissensverarbeitung. Inferenz in PROLOG. Schlussfolgerungen. 153 [Staa12]  PROLOG: Hornklauseln Grundlage von PROLOG: PROLOG basiert auf speziellen logischen Formeln, die als Hornklauseln bezeichnet werden. Hornklauseln und konjunktive Normalform (KN): Hornklauseln sind eine Sonderform der konjunktiven Normalform (KN). Die konjunktive Normalform ist eine Konjunktion von Klauseln. Beispiele konjunktiver Normalform: Term A1: 𝐴1 = (𝑎 ∨ 𝑏 ∨ ¬𝑐) ∧ (¬𝑎 ∨ 𝑏 ∨ ¬𝑒) ∧ (𝑎 ∨ 𝑏 ∨ ¬𝑓) Term A2: 𝐴2 = (𝑎 ∨ ¬𝑏 ∨ ¬𝑐) ∧ (¬𝑎 ∨ 𝑏 ∨ ¬𝑒) Merkmal von Hornklauseln: Eine Klausel wird als Hornklausel bezeichnet, wenn höchstens ein Literal nicht negiert ist. In Term 𝐴2 erfüllen alle Klauseln dieses Merkmal. Wichtig: Hornklauseln sind für PROLOG grundlegend, da sie eine strukturierte und vereinfachte Form der logischen Darstellung bieten. 154 [Staa12] PROLOG: Hornklauseln ▪ Einfach ausgedrückt ist ein PROLOG-Programm nichts anderes als eine konjunktive Normalform (KN), die nur aus Hornklauseln besteht. ▪ Die Schreibweise erfolgt anders, ist jedoch am Beispiel leicht zu erklären. ▪ Wir formen folgenden Ausdruck um: 𝐴2 = (𝑎 ∨ ¬𝑏 ∨ ¬𝑐) ∧ (¬𝑎 ∨ 𝑏 ∨ ¬𝑒) ▪ Umformung: ▪ In jeder Klausel ziehen wir die negierten Variablen nach vorne: 𝐴2 = (¬𝑏 ∨ ¬𝑐 ∨ 𝑎) ∧ (¬𝑎 ∨ ¬𝑒 ∨ 𝑏) ▪ Anwendung des DeMorganschen Gesetzes: 𝐴2 = (¬(𝑏 ∧ 𝑐) ∨ 𝑎) ∧ (¬(𝑎 ∧ 𝑒) ∨ 𝑏) ▪ Vereinfachung unter Verwendung des Implikationsoperators: 𝐴2 = ((𝑏 ∧ 𝑐) → 𝑎) ∧ ((𝑎 ∧ 𝑒) → 𝑏) ▪ Das ist schon sehr nahe an der Syntax von PROLOG. 155 [Staa12]  PROLOG: Regeln ▪ Wir treffen weiter noch folgende Vereinbarungen: 1. Die durch ∧ verbundenen einzelnen Hornklauseln werden in einem PROLOG-Programm untereinander geschrieben. 2. Jede Klausel wird mit einem Punkt beendet. 3. Kommt ∧ innerhalb einer Klausel vor, so verwenden wir hierfür ein Komma. 4. Der Implikationspfeil → wird durch -: ersetzt, und die Pfeilrichtung der Implikation wird umgedreht. Statt 𝑎 → 𝑏 schreiben wir also 𝑏 ← 𝑎 bzw. b :- a ▪ Mit diesen Vereinbarungen würde unter Term 𝐴2 = ((𝑏 ∧ 𝑐) → 𝑎) ∧ ((𝑎 ∧ 𝑒) → 𝑏) in PROLOG so aussehen: a :- b, c. b :- a, e. 156 [Staa12]  PROLOG: Regeln ▪ Wir betrachten den Code: a :- b, c. b :- a, e. ▪ Der vordere Teil der Programmklausel wird als Klauselkopf bezeichnet, der hintere Teil heißt Klauselrumpf. 157 [Staa12] PROLOG: Fakten ▪ Neben den Regeln, die die Gültigkeit einer Variablen in Abhängigkeit von anderen Variablen ausdrücken, kann in einem PROLOG-Programm auch reines Faktenwissen formuliert werden. ▪ Faktenwissen wird wie folgt angegeben: ▪ Ein Faktum, das als gültig (wahr) betrachtet wird, wird gefolgt von einem Punkt. ▪ Dies entspricht einer Klausel ohne Rumpf, also einem Klauselkopf. ▪ Gilt 𝑎 und 𝑏, wäre die entsprechende Formulierung in PROLOG: a. b. [Staa12] 158 PROLOG: Programme als Wissensbasis Ein PROLOG-Programm somit nichts anderes als eine Wissensbasis. Was ist ein PROLOG- Programm? Es beinhaltet Wissen in Form von Fakten und Regeln über einen bestimmten Gegenstandsbereich. (1) d. Beispiel eines (2) a :- c, b. vollständiges (3) a :- f, g. PROLOG-Programma im Kontext der (4) g. Aussagenlogik (5) c :- d. (6) f. [Staa12] 159 Quiz https://partici.fi/33103264 160 Übungsaufgaben 161 162  Wissensbasis in PROLOG Die Wissensbasis ist nur ein Teil eines PROLOG- Programms bzw. eines Expertensystems. Wir benötigen noch einen Mechanismus, der in der Lage ist, mithilfe des vorhandenen Wissens auf neue Erkenntnisse zu schließen. Anfragen verifizieren oder falsifizieren PROLOG: Sachverhalte, die als Anfrage an das PROLOG-Programm gestellt werden, müssen verifiziert oder falsifiziert Schlussfolgerungen werden. Resolution in PROLOG: Dies geschieht mithilfe der Resolution , die im Abschnitt Aussagenlogik behandelt wurde. Verifizierung von Anfragen: Soll eine Anfrage verifiziert werden, wird die Negation des angefragten Sachverhalts zur Klauselmenge hinzugefügt. Es erfolgt eine Überprüfung der gesamten Formelmenge auf Widerspruch. 163 [Staa12]  Unser PROLOG-Programm PROLOG: Schlussfolgerungen entspricht der folgenden Klauselmenge: ▪ Folgt nun 𝑎 aus unserer Klauselmenge?