Logik1 - users.informatik.haw-hamburg.deklauck/LoBe/lbskript.pdf · 1.1.1.1 Elemente von Prolog In diesem Abschnitt werden zunächst die wesentlichsten Elemente von Prolog präsentiert,

Logik1

4. Auflage 2014

1Dieses Skript versteht sich als Stichwortsammlung des in der Vorlesung präsentier-ten Stoffes.

2

Inhaltsverzeichnis

Inhaltsverzeichnis 2

1 Klassische Logik 51.1 Logische Programmierung: Prolog . . . . . . . . . . . . . . . . . . 6

1.1.1 SWI-Prolog . . . . . . . . . . . . . . . . . . . . . . . . . . 71.1.1.1 Elemente von Prolog . . . . . . . . . . . . . . . . 91.1.1.2 Der Interpreter . . . . . . . . . . . . . . . . . . . 141.1.1.3 Abarbeitungsstrategie . . . . . . . . . . . . . . . 141.1.1.4 Backtracking . . . . . . . . . . . . . . . . . . . . 171.1.1.5 Abarbeitungsmodell: Vierportmodell . . . . . . . 181.1.1.6 Eine kleine Anwendung . . . . . . . . . . . . . . 191.1.1.7 Die Türme von Hanoi . . . . . . . . . . . . . . . 201.1.1.8 Der Cut . . . . . . . . . . . . . . . . . . . . . . . 221.1.1.9 Negation . . . . . . . . . . . . . . . . . . . . . . 25

1.1.2 Prolog: Unifikation und Resolution . . . . . . . . . . . . . 271.1.2.1 Unifikation . . . . . . . . . . . . . . . . . . . . . 281.1.2.2 Resolution . . . . . . . . . . . . . . . . . . . . . . 30

1.1.3 Prolog: Programmieren mit Listen . . . . . . . . . . . . . . 321.1.3.1 Abarbeitung . . . . . . . . . . . . . . . . . . . . 321.1.3.2 Top-Down Verfahren . . . . . . . . . . . . . . . . 321.1.3.3 Bottom-Up Verfahren . . . . . . . . . . . . . . . 33

1.1.4 Anwendung: Sortierverfahren . . . . . . . . . . . . . . . . 341.1.4.1 Bubblesort . . . . . . . . . . . . . . . . . . . . . 341.1.4.2 Quicksort . . . . . . . . . . . . . . . . . . . . . . 35

1.1.5 Prolog und Prädikatenlogik 1-ter Stufe . . . . . . . . . . . 351.1.5.1 Prolog und Prädikatenlogik: Syntax . . . . . . . . 361.1.5.2 Prolog und Prädikatenlogik: Semantik . . . . . . 361.1.5.3 Prolog und Prädikatenlogik: Beispiel . . . . . . . 37

1.2 Boole’sche Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . 391.2.1 Boole’sche Terme . . . . . . . . . . . . . . . . . . . . . . . 401.2.2 Schaltalgebra . . . . . . . . . . . . . . . . . . . . . . . . . 41

1.3 Aussagenlogik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411.3.1 Syntax der Aussagenlogik . . . . . . . . . . . . . . . . . . 42

3

4 INHALTSVERZEICHNIS

1.3.2 Semantik der Aussagenlogik . . . . . . . . . . . . . . . . . 431.3.3 Tableaukalkül der Aussagenlogik . . . . . . . . . . . . . . 471.3.4 Resolution der Aussagenlogik . . . . . . . . . . . . . . . . 511.3.5 Tableau- und Resolutionskalkül . . . . . . . . . . . . . . . 581.3.6 Hornlogik . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

1.4 Prädikatenlogik 1-ter Stufe . . . . . . . . . . . . . . . . . . . . . . 601.4.1 Syntax der Prädikatenlogik . . . . . . . . . . . . . . . . . 621.4.2 Semantik der Prädikatenlogik . . . . . . . . . . . . . . . . 651.4.3 Unifikation . . . . . . . . . . . . . . . . . . . . . . . . . . 671.4.4 Resolution . . . . . . . . . . . . . . . . . . . . . . . . . . . 681.4.5 Tableau . . . . . . . . . . . . . . . . . . . . . . . . . . . . 691.4.6 Prolog und Prädikatenlogik . . . . . . . . . . . . . . . . . 71

1.4.6.1 Syntax . . . . . . . . . . . . . . . . . . . . . . . . 711.4.6.2 Semantik . . . . . . . . . . . . . . . . . . . . . . 72

2 Nichtklassische Logik 73

A Übungsaufgaben 75A.1 Übungen Prolog . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75A.2 Übungen Klassische Logik . . . . . . . . . . . . . . . . . . . . . . 90A.3 Übungen Nichtklassische Logik . . . . . . . . . . . . . . . . . . . 129A.4 Übungen Berechenbarkeit . . . . . . . . . . . . . . . . . . . . . . 135

Literaturverzeichnis 135

Kapitel 1

Klassische Logik

Logik untersucht

• Verknüpfung von Aussagen

• ziehen von formalen Schlüssen

• durchführen von Beweisen

Die Logik beschäftigt sich mit dem Grundsätzlichen, die Informatik bzw. dieLogik innerhalb der Informatik mit dem Machbaren.

Die Logik ist bestimmt durch die konsequente Trennung von

syntaktische Begriffe Zeichenreihen und „Grammatik“

semantische Begriffe Bewertung und Interpretation

Folgende Definition ist [KK06] entnommen.

Definition 1.1 Ein logisches System besteht aus den nachfolgenden Teilen.

• Gewisse formale Ausdrücke werden als atomare Formeln bezeichnet. DieSyntax des logischen Systems legt fest, wie man die atomaren Formelnmit Hilfe gewisser Junktoren oder Operatoren zu komplexen Formeln zu-sammenfügen darf. Die sich ergebenden logischen Formeln sind dabei ersteinmal nur nach gewissen Regeln erstellte Zeichenketten ohne „Inhalt-“ oder„Bedeutung“.

• Die Semantik des logischen Systems besteht aus einer Reihe von Regeln,die festlegen, wie die Formeln mit Wahrheitswerten versehen werden kön-nen. Dadurch erhalten die Formeln eine gewisse „Bedeutung-“ oder „Inter-pretation“. Eine Belegung der atomaren Formeln mit Wahrheitswerten, fürdie eine Gesamtformel F den Wert „wahr“ ergibt, nennt man ein Modellfür F. Besitzt F kein Modell, so hei�t F eine unerfüllbare Formel. Liefert

5

6 KAPITEL 1. KLASSISCHE LOGIK

F bei jeder Belegung den Wert „wahr“, also besitzt F alle möglichen Modelle,so hei�t F eine Tautologieoder eine allgemein gültige Formel. Besitzt Fmindestens ein Modell und nicht alle möglichen Modelle (also eine möglicheBelegung ist kein Modell für F), so hei�t F erfüllbare Formel.

• Optional gibt es für ein logisches System auch ein logisches Kalkül (odereinfach Kalkül). Ein Kalkül besteht aus einer Reihe von mechanisch anzu-wendenden, starren Regeln für die Umformung von Formeln. Das Ziel derAnwendung eines logischen Kalküls ist es, die Unerfüllbarkeit einer vorgege-benen Formel nachzuweisen oder ein Modell für sie zu konstruieren. Kalküleeignen sich meist für die algorithmische Implementierung im Computer.

Dazu ein Beispiel aus der Mathematik. Die Semantik würde 6∗5∗33∗2 = 15 auswerten,

also den Wert der Aussage berechnen. Ein Kalkül würde den Ausdruck 6∗5∗33∗2 =

2∗3∗3∗52∗3 = 3 ∗ 5 umformen.

Eine notwendige Bedingung ist eine unersetzbare Voraussetzung, ohnedie eine bestimmte Wirkung nicht eintritt; allerdings erfolgt die Wirkung nichtzwangsläufig durch das Eintreten der Voraussetzung. Als Beispiel: „Wer in diesemStudiengang eingeschrieben ist, kann an den Prüfungen teilnehmen.“ ist eine not-wendige Bedingung, die alleine aber nicht unbedingt ausreicht. Umgekehrt kannman aber folgern, dass jemand, der an einer Prüfung teilgenommen hat, in demzugehörigen Studiengang eingeschrieben ist.

Eine hinreichende Bedingung ist eine ersetzbare Voraussetzung, bei derenErfüllung eine bestimmte Wirkung zwangsläufig eintritt und keine weiteren Vor-aussetzungen benötigt werden; allerdings kann das Vorliegen der Wirkung auchandere Ursachen haben. Als Beispiel: „Wenn es regnet, ist die Straße nass.“ isteine hinreichende Bedingung. Jedoch kann aus der Situation, dass die Straße nassist, nicht gefolgert werden, dass es geregnet hat. Vielleicht wurde sie Straße miteinem Schlauch nass gespritzt.

Wenn A eine hinreichende Bedingung für B ist, dann ist B eine notwendigeBedingung für A.

1.1 Logische Programmierung: PrologDer klassische Stil des Programmierens wird häufig durch die Adjektive prozedu-ral oder imperativ gekennzeichnet . Der Grund dafür ist, daß beim Programmie-ren die Arbeitsweise eines Algorithmus durch Angabe von Befehlen und Proze-duren auf detaillierte Weise beschrieben wird. Etwas genauer besehen geht dieserProzeß schrittweise vor sich. Zuerst hat man gewöhnlich eine informell gestellteAufgabe vor sich, die man dann sinngemäß in eine formale Spezifikation über-führt. Darunter versteht man eine formale Beschreibung der Eingabegrößen, derAusgabegrößen und ihrer wechselseitigen Beziehungen. Hier liegen häufig schonFehlerquellen, weil die informelle Beschreibung oft in der Umgangssprache mit

1.1. LOGISCHE PROGRAMMIERUNG: PROLOG 7

all ihren Kontextabhängigkeiten und die Spezifikation meist in einem davon ganzverschiedenen Formalismus notiert werden. Für die Spezifikation wird dann häufigerst nach weiteren Transformationen das Programm geschrieben, und man kanndann sagen, ob dieses bzgl. der Spezifikation korrekt ist oder nicht. In der Praxisist das Programm selbst sehr oft die erste formale Spezifikation des Programms!Die höheren Programmiersprachen enthalten nun Elemente, die bestimmte kom-plexere Operationen direkt ausführen, den Programmierer also von den sonst an-fallenden Details entlasten. Derart einmal auf den Geschmack gekommen, fragtman sich nun, wie weit man solch einen Service treiben kann. Am bequemstenwäre es natürlich, nur noch die Spezifikation anzugeben und den ganzen Restdem System zu überlassen. Das ist in der Tat die Grundidee des deklarativenProgrammierens.

Die Informationen (bzw. das Wissen), die es einem System erlauben, eineAusgabe aus einer Eingabe zu erzeugen, können auf zweierlei Weisen dem Systemmitgeteilt werden.

• Zum einen kann das System generell mit bestimmten Fähigkeiten versehenwerden, wie etwa der Möglichkeit, rekursive Funktionen abzuarbeiten oderder Möglichkeit die Erfüllbarkeit von logischen Formeln zu beweisen.

• Zum anderen könnte der Benutzer dem System situationsbedingte Informa-tionen (als Ersatz für das Programm) mitteilen.

Auf diese Weise ist die Prädikatenlogik zur Programmiersprache geworden. Dadie allgemeine Prädikatenlogik jedoch zu ineffizient ist, wurde ein (geeignetes)Fragment der Prädikatenlogik entwickelt, um die skizzierte Vorgehensweise zurealisieren. Nach Bob Kowalski besteht demnach ein Algorithmus aus Logik undKontrolle.

Ein weiteres Argument, das meist aus den Kreisen der logischen Program-mierung zitiert wird, ist, das der Beginn der Logik mit dem Beginn des wissen-schaftlichen Denkens verbunden wird. Die Logik bietet eine präzise Sprache zurFormulierung von Zielen, Wissen und Annahmen; sie bietet die Grundlage zur Ab-leitung von Konsequenzen aus Prämissen, zur Untersuchung von Wahrheit oderFalschheit von Aussagen, wenn die Wahrheit oder Falschheit anderer Aussagenbekannt ist, zum Beweis der Konsistenz von Forderungen und zur Verifikationder Gültigkeit von Argumenten.

1.1.1 SWI-Prolog

Für die Bereiche logische Programmierung werden wir den Standard SWI-Prologverwenden1. Diese Sprache scheint besonders geeignet zu sein, da ihre formalenEigenschaften in kürzester Zeit vermittelt werden können. Nach kurzer Zeit sind

1Als Literatur sei [CM94] empfohlen.


auch hier die eigentlich nicht vorhandenen syntaktischen Details der Sprache inden Hintergrund getreten, so daß wir uns den eigentlichen Problemen widmenkönnen mittels der logischen Programmiermethode.

Die Anfang der siebziger Jahre von A. Colmerauer (Marseille) und R. Ko-walski (Edinburgh) entwickelte, auf der Prädikatenlogik erster Stufe beruhen-de Programmiersprache Prolog2 hat mit der Entscheidung, im japanischen FifthGeneration Computer Systems Project (FGCS) logische Programmiersprachenzu verwenden, in den achtziger Jahren einen starken Aufschwung erlebt. Pro-log wird vor allem für Probleme in der Künstlichen Intelligenz (KI) verwendet.Sie fand kommerzielle Anwendung in Expertensystemen, etwa für Boing, AT&T.Microsoft Windows NT verwendet einen kleinen Prolog-Interpreter, um optima-le Konfigurationen für Netzwerke automatisch zu erzeugen. Eines der meistver-kauften CASE-Werkzeuge3 – KnowledgeWare’s Application Development Work-bench (ADW) – enthält etwa eine viertel Million Prolog-Programmzeilen. DieFirma vermutet, daß das Programm in C fast zehnmal so groß geworden wäre,mit entsprechender Beeinträchtigung der Wartbarkeit. Jedoch muß auch erwähntwerden, daß derzeit die kommerzielle Nachfrage nach Prolog stagniert; dies istjedoch nicht damit gleichzusetzen, daß der Programmierstil bzw. die Denkweisestagniert.

Der Programmierstil von Prolog besteht in der Angabe von Fakten und Regelnbzw. Axiomen, die die Beziehungen zwischen Objekten definieren. Als Verarbei-tungsmodell wird das Beweisermodell4 verwendet, das auf der logischen Dedukti-on basiert; das Programm entspricht den Axiomen bzw. Regeln und Fakten, derRechner „beweist“ die Gültigkeit von logischen Formeln bzw. leitet neue Formelnab. Prolog führt den Beweis jedoch als einen Widerspruchsbeweis, d.h. es versuchtdie negierte Anfrage bzw. die dort geäusserte Hypothese zu widerlegen.

Die Programmierung in Prolog erfolgt hauptsächlich durch

• Angabe von Fakten über Objekte und deren Beziehungen,

• Angabe von Regeln über Objekte und deren Beziehungen, und

• stellen von Fragen über Objekte und deren Beziehungen.

2französische Abkürzung für „Programmation en Logique“.31995 ca. 60 000 Lizenzen weltweit.4Konventionelles Verarbeitungsmodell (von Neumann Maschine): verarbeitet Folgen von An-

weisungen durch schrittweises Auslösen von Aktionen, die den Maschinenzustand verändern;Funktionales Verarbeitungsmodell: basiert auf dem mathematischen Funktionsbegriff. Funk-tionen sind eindeutige Abbildungen von einem Definitionsbereich in einen Wertebereich. DerRechner erhält den Funktionsnamen und die Argumente und liefert einen Wert; RelationalesVerarbeitungsmodell: basiert auf dem mathematischen Relationenbegriff. Dem Rechner wer-den Relationsname und die zugehörigen Argumente zur Aktivierung übermittelt. Werden alleArgumente übergeben, so wird das Vorhandensein des einen so spezifizierten Tupels geprüft.Andernfalls werden alle Tupel geliefert, die der Spezifikation entsprechen.


Die Kunst der Logikprogrammierung ist das Schreiben kurzer und eleganter Pro-gramme, die die beabsichtigte Bedeutung haben.

Folgende SWI-Prolog Versionen stehen z.Z. zur Verfügung:

1. SWI-Prolog Version 2.8.2 unter Windows NT/95. Der Pfadname des „wor-king directories“ kann gesetzt werden durch ?-chhdir(“D:“).. Dateienwerden dann mittels ?-consult(FLCodeP). oder ?-[FLCodeP] geladen.Wurde eine Anfrage mit Variablen gestartet, kann durch drücken von derTaste r, ; oder n (u.U. mit <CR>) die nächste mögliche Belegung der Va-riablen ermittelt werden. Um direkt eine kleine Datenbank im Interpretereinzugeben, kann [user] verwendet werden.

2. SWI-Prolog Version unter Linux

1.1.1.1 Elemente von Prolog

In diesem Abschnitt werden zunächst die wesentlichsten Elemente von Prologpräsentiert, die zum Schreiben einfacher Programme notwendig sind: Konstanten,Variablen, Listen, Fakten, Regeln und Fragen.

Konstanten Konstanten werden in Prolog durch einen Kleinbuchstaben am An-fang gekennzeichnet. Beispiele sind george, harry, pooh. Mit der vorde-finierten Relation atomic kann geprüft werden, ob etwas eine Konstanteist, etwa atomic(konstante).. Sind Konstanten durch Hochkommata „’“geklammert, können sie beliebiger Gestalt sein, etwa ’Keine-Variable’.Ebenfalls zu den Konstanten werden die Zahlen gerechnet. Ob etwas eineZahl ist, kann mit dem Prädikat number geprüft werden, etwa number(42.88)..

Variablen Variablen beginnen mit einem Großbuchstaben oder einem Unter-strich. Beispiele sind Variable, _x, _y, X. Da Prolog ein Fragment derPrädikatenlogik erster Stufe ist, stehen die Variablen für Funktionen. Esgibt keine Variablen für Prädikate! Der Sichtbarkeitsbereich einer Variablenerstreckt sich auf einen Fakt bzw. auf eine Regel, oder salopp formuliert,wird der Sichtbarkeitsbereich durch die Punkte „.“ beschränkt. Die Variable_ wird als „Dummy“ verwendet, d.h. auf deren Bindung wird nicht zuge-griffen. Ein Mehrfachvorkommen dieser „anonymous“ Variable innerhalb desgleichen Sichtbarkeitsbereiches wird als jeweils unterschiedliche Variable in-terpretiert, d.h. ihr Sichtbarkeitsbereich ist sie selbst. Die Vorkommen derVariablen innerhalb eines Fakts oder einer Regel sind immer allquantifi-ziert! Mit der vordefinierten Relation var kann geprüft werden. ob etwaseine Variable ist, etwa var(X)..

Listen Listen werden durch eckige Klammern dargestellt. Beispiel ist [1,2,3,4].Wenn in einer Regel auf eine Liste im allgemeinen zugegriffen wird, wirddie Form [Kopf|Rest] verwendet. Bei einer Bindung wird an die Variable


Kopf das erste Element einer Liste gebunden, z.B. 1, und an die VariableRest der Rest der Liste, z.B. [2,3,4]. Da keine Typisierung besteht, kanneine Liste auch Elemente unterschiedlichen Typs beinhalten.

Strukturen Strukturen sind Schachtelungen von Prädikaten. Eine einfache Vi-sualisierung komplexer Strukturen kann durch eine Baumdarstellung vor-genommen werden. Eine einfache Struktur ist z.B.eltern(charles,elizabeth,philip). Eine komplexere Struktur ist z.B.buch(mobby_dick,autor(herman,melville)) oder eine Satzstruktur istz.B. satz(substantiv(X),verb_phrase(verb(Y),substantive(Z))).

Fakten Fakten sind fundamentale Aussagen über Objekte und deren Beziehun-gen. Die Klötzchenwelt in Abbildung 1.1 (Seite 10) würde wie folgt alsFakten dargestellt werden.

block(block1).block(block2).block(block3).block(block4).tisch(tisch).auf(block3,block1).auf(block4,block2).auf(block1,tisch).auf(block2,tisch).

Tisch

Block1 Block2

Block3 Block4

Abbildung 1.1: Ein Beispiel, die sogenannte Klötzchenwelt

Folgende Dinge sind dabei wichtig:

• Die Relation steht am Anfang des Ausdrucks und die Objekte werdeninnerhalb von runden Klammern durch Kommata getrennt aufgeführt.<Relation>(<Objekt1>,...,<ObjektN>).


• Am Ende von Fakten steht immer der Punkt „.“.• Bei gewissen Relationen wird eine gewisse Ordnung implizit vorausge-

setzt, etwa bei der Relation auf. Diese Ordnung kann bzw. wird vondem Programmierer gewählt und muß dann streng eingehalten wer-den. Im allgemeinen besteht keine Ordnung auf den Argumenten vonRelationen.• Bei universellen Fakten können auch Variablen eingesetzt werden, so

etwa bei dem Fakt, daß ein Element in einer Liste vorhanden ist, wennes der Kopf der Liste ist: contains([Kopf|_],Kopf).• Variablen in Fakten sind immer allquantifiziert, d.h. in der Prädika-

tenlogik hat eben aufgeführter Fakt die Bedeutung:∀Kopf : contains([Kopf |_], Kopf).• Ein Fakt ist wie folgt als Regel darstellbar: A ⇒ 0 ∨ A ⇒ (¬1) ∨ A⇒ 1→ A⇒ A← 1⇒ A : −true.⇒ A.

Eine Ansammlung von Fakten wird häufig auch als Datenbank bezeichnet.

Regeln Regeln werden in Prolog verwendet um auszudrücken, daß ein Fakt aufanderen Fakten basiert bzw. um einen Fakt zu definieren. In diesem Sinnesind Regeln generelle Aussagen über Objekte und deren Relationen. Bezo-gen auf das Beispiel in Abbildung 1.1 (Seite 10) können folgende generelleAussagen getroffen werden: Etwas ist oberhalb von etwas anderem, wennes auf diesem ist oder (Transitivität) wenn es auf etwas steht, daß oberhalbdiesem anderen ist.

oberhalb(X,Y) :- auf(X,Y).oberhalb(X,Z) :- auf(X,Y),oberhalb(Y,Z).

Für das contains in einer Liste gilt, wenn das Element nicht der Kopf derListe ist, ist es in der Liste enthalten, wenn es im Rest der Liste enthaltenist:contains([_|Rest],Element) :- contains(Rest,Element).

Folgende Dinge sind dabei wichtig:

• Regeln sind im allgemeinen von der Form: <Kopf> :- <Rumpf>.. DasSymbol :- wird dabei gelesen als „falls“, d.h. der <Kopf> ist wahr,falls der <Rumpf> (die Prämissen) wahr ist. Jede Regel wird, wie Fak-ten, durch einen Punkt „.“ abgeschlossen. In den aufgeführten Bei-spielen besteht der Kopf jeweils aus dem zu definierenden Fakt, z.B.oberhalb(X,Y). Der Rumpf besteht aus den Fakten, die den Kopfdefinieren. Mehrere Fakten werden durch ein Komma getrennt. DasKomma ist als logisches und zu lesen. Später werden weitere Möglich-keiten aufgeführt werden, wie der Rumpf aussehen kann.


• Fakten und Regeln werden als Klauseln bezeichnet. Der Kopf einer Re-gel bzw. die linke Seite besteht aus einem Literal, der Rumpf bestehtaus mehreren Literalen. Ein Literal kann ein positiver oder negativerFakt sein. Betrachtet man die Lesbarkeit einer Implikation A und Bund C impliziert D als nicht(A) oder nicht(B) oder nicht(C)oder D, so zeichnen sich die Regeln in Prolog durch ein positives Li-teral und einige negative Literale aus. Diese Regeln werden auch alsHorn-Klauseln bezeichnet.

• Alternativen bei einer Definiton bzw. das logische oder wird durchmehrere Regeln ausgedrückt. SWI-Prolog bietet eine weitere Möglich-keit an, Alternativen darzustellen. Diese Darstellung wird z.B. danninteressant, wenn die indirekt bestehende Ordnung von Prädikatenaufeghoben werden soll:

oberhalb(X,Z) :- (auf(X,Y) ; auf(Y,X)),oberhalb(Y,Z).

Dieses Beispiel entspricht den beiden Regeln:

oberhalb(X,Z) :- auf(X,Y),oberhalb(Y,Z).oberhalb(X,Z) :- auf(Y,X),oberhalb(Y,Z).

• Variablennamen sind innerhalb einer Regel bzw. einem Fakt eindeutig,d.h. sie stehen für das gleiche Objekt. Variablennamen einer Regelhaben keine Bedeutung in anderen Regeln oder Fakten. In dem Beispielist die Variable X in der ersten Regel zu oberhalb ein anderes X, als inder zweiten Regel! Die spezielle Variable _ ist immer unterschiedlich,d.h. die Sichtbarkeit beschränkt sich auf die Stelle ihres Vorkommen.

• Die Variablen in Regeln sind immer allquantifiziert. Aufgeführte Bei-spiele sind in der Schreibweise der Prädikatenlogik erster Stufe zu lesenals:

– ∀X∀Y : auf(X,Y )→ oberhalb(X, Y )∀X∀Y ∀Z : auf(X, Y ) ∧ oberhalb(Y, Z)→ oberhalb(X, Y )

– ∀Rest∀Element : contains(Rest, Element)→contains([_|Rest], Element)

• Regeln können auch rekursiv aufgebaut werden, d.h. die Relation derlinken Seite kann auch auf der rechten Seite verwendet werden.

Fragen Wenn die Datenbank in Prolog mit Fakten und/oder Regeln gefüllt wur-de, können an das System Anfragen gestellt werden. Dies wird durch denPrompt des Prolog-Interpreters ?- verdeutlicht. Wenn Prolog eine Anfrageerhält, prüft es, ob es die Anfrage mit einem Fakt oder einer linken Seiteeiner Regel unifizieren kann. Je nach Art der Anfrage, ob mit oder ohneVariablen, unterscheidet Prolog zwei Arten von Antworten.


1. Ja/Nein-Antworten:Wurden keine Variablen in der Anfrage angegeben, überprüft Prolog,ob es diese Aussage (im Sinne einer Hypothese) direkt als Fakt vorfin-det und damit bewiesen hat. Beispiel wäre die Anfrage?-auf(block4,block2).. Prolog liefert die Antwort yes, da es dieHypothese beweisen konnte. Findet Prolog keinen Fakt, wird versucht,mittels Regeln und Fakten einen Beweis für die Hypothese zu finden.Beispiel wäre die Anfrage oberhalb(block4,tisch).. Hier muß derProlog-Interpreter alle Regeln einsetzen, um den Beweis zu finden.Auch hier wird Prolog als Resultat die Ausgabe yes erzeugen. In ei-nem Vergleich von Fragen zu Regeln, können Fragen auch als Regelnohne linke Seite aufgefaßt werden, also ?-auf(block4,block2). hatdie Bedeutung :- auf(block4,block2)..Aus Sicht der Prädikatenlogik ist hier an Prolog die Frage gestellt, obeine Aussage Φ (die Anfrage) sich aus einer gegebenen FormelmengeΓ (das Programm) ableiten läßt.

2. Substitutions-Antworten:Werden in der Anfrage Variablen verwendet, führt Prolog ebenfallseinen Beweis durch. Das Programm liefert jedoch alle möglichen Bin-dungen der Variablen in der Anfrage, für die die Anfrage wahr ist. Bei-spiel wäre die Anfrage ?-oberhalb(Was,tisch).. Hier liefert Prologalle möglichen Bindungen für die Variable Was, die es herleiten kann,hier also block1, block2, block3, block4. Prolog erlaubt auch ge-schachtelte Fragen, also durch „ ,“, dem logischen und, getrennte Lite-rale. Beispiel wäre ?-oberhalb(block4,X),block(X)., also die An-frage, über welchen Blöcken sich block4 befindet.Aus Sicht der Prädikatenlogik ist hier an Prolog die Aufgabe gestellt,die Variablensubstitutionen σ (SUB) für eine Aussage Φ (die Anfrage)zu finden, für die sich σ(Φ) aus einer gegebenen Formelmenge Γ (dasProgramm) ableiten läßt.

Eine Frage ist wie folgt als Regel darstellbar: (¬A) ⇒ (¬A) ∨ 0 ⇒ A → 0⇒ 0 ← A ⇒ 0 : −A. ⇒? − A. Das verdeutlicht, warum Prolog einenWiderspruchsbeweis führt.

Operatoren Manchmal ist es günstiger bzw. lesbarer, die Infixschreibweise fürRelationen zu verwenden, vor allem dann, wenn sie von operationalem Cha-rakter sind. Beispiel sind die arithmetischen Operatoren +, -, /, *, div,mod. Prolog erlaubt nun bei diesen Operatoren die Infixschreibweise, etwa3 + 4. Zu beachten ist, daß Prolog hier keine Auswertung vornimmt! DerAusdruck 3 + 4 ist für Prolog normalerweise nicht gleich 7, sondern nur derAusdruck selbst. Die Anfrage ?- X = 3 + 4. führt daher auch nicht zu ei-ner Auswertung, sondern zu der Bindung der Variablen X an den Ausdruck


3 + 4.

Zu den Operatoren zählen auch die Vergleichsoperatoren. Für arithmeti-sche Ausdrücke gibt es =<, >=, =:=, =/= (kleiner gleich, grösser gleich,gleich, ungleich). Im allgemeinen gibt es noch =. Der Ausdruck wird alswahr bewiesen, wenn die beiden Seiten unifiziert werden können. Beispielist a(b,C,d(e,F,g(h,i,j))) = a(B,c,d(E,f,X))., wobei dann folgendeBindungen vorgenommen werden: B = b, C = c, E = e, F = f und X =g(h,i,j)5.

Zuweisung Zuweisungen sind vor allem bei der Arithmetik wichtig, wenn derAusdruck ausgewertet werden soll. So kann mittels dem Operator = eineZuweisung bzw. Bindung einer Variablen vorgenommen werden, etwa X =[1,2,3]., aber eine Auswertung findet nicht statt. X = 1 + 2. führt zu derBindung von 1 + 2 an X. Der Ausdruck X is 1 + 2 führt jedoch zu derBindung von X an 3. Der Operator is ist auch wie = als Vergleichsoperatorzu verwenden. Der Unterschied ist, daß links eine Zahl bzw. eine Variablestehen muß und rechts ein Ausdruck, der ausgewertet, eine Zahl ergebenmuß. In diesem Sinne ist is als Zuweisung interpretierbar. Genau genom-men wird auch hier nach der Auswertung des Ausdrucks auf der rechtenSeite die Unifikation verwendet.

Wichtig ist, dass Regeln, die in ihrem Rumpf eine Zuweisung haben, zu-nächst ihren relationalen Charakter verlieren, d.h. 3 is X + 1. kann nichtevaluiert werden. Letztlich liegt dies daran, dass is selbst keine Relationmehr ist, sonder eher im Sinne einer Funktion arbeitet.

1.1.1.2 Der Interpreter

Das grobe Modell der Arbeitsweise von Prolog ist in Abbildung 1.2 (Seite 15)dargestellt. Der Interpreter wird durch eine Inferenzmaschine realisiert, die vor-wiegend die Unifikation und die Resolution für die Beweisführung verwendet.Der Programmierer formuliert die Axiome in der sogenannten Hornlogik. Die er-ste Frage, die sich stellt ist, wie die Inferenzmaschine die Regeln bzw. Fakten ausder Menge der Axiome auswählt.

1.1.1.3 Abarbeitungsstrategie

Die von Prolog gewählte Strategie zur Auswahl der Fakten und Regeln ist dieDepth-First – Left-Right – Top-Down Strategie. Diese Strategie umfaßt auch die

5Zu beachten ist, daß keine Varaiblen für Prädikatsnamen bzw. Relationsnamen zugelassensind! Ein Ausdruck der Form g(i,j) = X(i,j). gibt es in Prolog nicht, d.h. Prolog wird indiesem Fall die Unifikation abbrechen, da sich die Relationsnamen unterscheiden.


Logik-Beweiser (Inferenzmaschine)Unifikation und Resolution

Logische Axiome (Fakten und Regeln)Hornklauseln

Abbildung 1.2: Modell des Prolog-Interpreters

Behandlung von Konfliktfällen, wenn also mehrere Regeln bzw. Fakten gleichzei-tig anwendbar wären. Durch diese Strategie verliert Prolog zunächst den nicht-determinismus logischer Programmierung: die Inferenzmaschine wählt nicht eineRegel oder einen Fakt aus, sondern die Strategie legt klar fest, welche Regel bzw.welcher Fakt als nächstes zu verwenden ist.

Die Abarbeitungsstrategie soll an folgendem kleinem Beispiel erläutert wer-den. Gegeben sei folgende Datenbank:

a :- d.d.b :- d.

In folgender Tabelle wird nun aufgezeigt, wie Prolog auf die Anfrage ?- a, b.reagiert.


Ziel geprüfte Regel/Fakt Kommentar:- a, b. Left-Right: Die Ziele a und b werden

von links nach rechts abgearbeitet.a :- d.

:- d, b. Depth-First: Das aktuelle Ziel wird durch diePrämissen der angewendeten Regel ersetzt. Prologbeginnt nun bei der linkesten dieser Prämissenmit der Abarbeitung.

a :- d.d.

:- b. Top-Down: Die Regeln/Fakten werden von obennach unten bzw. in der Reihenfolge, in der siein der Datei aufgeführt sind, ausgewählt.

a :- d.d.b :- d.

:- d.a :- d.d.

:-

Die Reihenfolge kann somit eine entscheidende Bedeutung für die Terminie-rung von Programmen erhalten. Gegeben sei etwa

p(X) :- q(X).q(X) :- p(X).q(a).

Dieses Programm terminiert bei einer Anfrage ?- p(a). nicht, da die Stra-tegie niemals den Fakt q(a). erreicht. Dagegen terminiert folgendes Programmschon:

p(X) :- q(X).q(a).q(X) :- p(X).

Für die Terminierung eines Prolog-Programms ist daher die Reihenfolge derRegeln und Fakten innerhalb des Programms und die Reihenfolge der Literallenbzw. Prämissen innerhalb des Rumpfes einer Regel von entscheidender Bedeu-tung.


1.1.1.4 Backtracking

Was passiert bei alternativen Regeln/Fakten bzw. bei mehreren Möglichkeiten,Variablen zu binden ? Dazu sei auf folgendes Beispiel aus der Klötzchenwelt zu-rückgegriffen. Aus technischen Gründen wird das Prädikat oberhalb hier abkür-zend mit ober bezeichnet. Blöcke werden statt mit block kurz mit bl bezeichnet.

ober(X,Y) :- auf(X,Y). /* Regel 1 */ober(X,Z) :- auf(X,Y),ober(Y,Z). /* Regel 2 */

Auch hier soll die Arbeitsweise anhand der Anfrage ?-ober(bl4,W),tisch(W).bzgl. der Situation in Abbildung 1.1 (Seite 10) in einer Tabelle veranschaulichtwerden.

Ziel geprüfte Regel/Fakt Nr.:- ober(bl4,W),tisch(W).

ober(bl4,W) :- auf(bl4,W).:- auf(bl4,W),tisch(W). 1.

auf(bl4,bl2).:- tisch(bl2).

∅ 2.:- auf(bl4,W),tisch(W).

∅ 3.:- ober(bl4,W),tisch(W).

ober(bl4,W) :- auf(bl4,Y),ober(Y,W).:- auf(bl4,Y),ober(Y,W),tisch(W)

auf(bl4,bl2).:- ober(bl2,W),tisch(W)

auf(bl2,tisch).:- tisch(tisch)

tisch(tisch).:-

1. Zu beachten ist, daß durch die Vorgehensweise bei der Unifikation die Va-riablen in einem Ausdruck direkt durch eine Bindung ersetzt werden, wennihr erstes Vorkommen gebunden wurde.

2. Da Prolog tisch(block2) nicht beweisen kann, ist dieser Beweisversuchzunächst einmal fehl geschlagen. Prolog merkt sich diese Versuche. Um nunevtl. doch noch einen Beweis zu finden, wird das Backtracking aktiviert.Dieses Verfahren sorgt zunächst dafür, daß die zuletzt durchgeführte Bin-dung einer Variablen aufgehoben wird.


3. Prolog merkt sich, welche Bindungen bereits vorgenommen wurden. An die-ser Stelle schlägt der Beweis fehl, da keine weitere Bindung für die VariableWas gefunden werden kann. Also wird das Backtracking aktiviert. Diesmalkann jedoch keine Bindung aufgehoben werden. Das Backtracking über-prüft nun, ob eine weitere Regel oder ein weiterer Fakt in der Datenbankvorhanden ist, der bisher noch nicht verwendet wurde, und versucht mitdieser neuen Regel bzw. dem neuen Fakt einen Beweis zu finden.

Dieses Beispiel verdeutlicht die wesentliche Leistung des Backtrackings: Varia-blenbindungen können aufgehoben werden, um ggf. alternative Belegungen vor-nehmen zu können, und alternative Regeln/Fakten können verwendet werden.Das Backtracking merkt sich dabei alle durchgeführten Versuche, um keinen Ver-such zweimal durchzuführen (Terminierung!).

1.1.1.5 Abarbeitungsmodell: Vierportmodell

Prolog kommt mit einem einfachen Abarbeitungsmodell aus, daß nur aus vierAufruf- bzw. Rückgabearten besteht.

Call Ein Ziel Z wird auf Beweisbarkeit geprüft.

• Falls ein Fakt F das Ziel direkt beweist (Ziel und Fakt sind unifizier-bar), dann antworte mit Exit.

• Falls jedoch eine Regel K :- P1,P2,...,Pn zum Beweis verwendetwerden muß (Ziel und Kopf der Regel sind unifizierbar), dann rufeCall rekursiv für die Prämissen P1,P2,...,Pn auf.

• Falls kein Fakt oder keine Regel für den Beweis gefunden werden kann,antworte mit Fail.

• Falls mehrere Fakten oder Regeln zur Auswahl stehen, wähle die ersteRegel bzw. den ersten Fakt.

Exit Ein Ziel wurde erfolgreich bewiesen. Beweise nun die noch u.U. nicht be-wiesenen Ziele.

Fail Ein Beweis für ein Ziel ist fehlgeschlagen. Gehe zu Redo, falls es Alternativengibt.

Redo Suche nun nach Alternativen (Variablenbelegung oder Fakten/Regeln).Prüfe u.U. ob es alternative Ziele gibt. Wende die gefundene Alternativedurch betreten von Call an.

Die vier Begriffe werden von Prolog verwendet, wenn mittels der Relation traceeine Beobachtung der Abarbeitung aktiviert wurde.


[trace] 2 ?- member( 3, [1,2,3,4,5]).> Call: (7) member(3, [1, 2, 3, 4, 5])> Call: (8) member(3, [2, 3, 4, 5])> Call: (9) member(3, [3, 4, 5])> Exit: (9) member(3, [3, 4, 5])> Exit: (8) member(3, [2, 3, 4, 5])> Exit: (7) member(3, [1, 2, 3, 4, 5])> Yes

1.1.1.6 Eine kleine Anwendung

Als eine kleine Anwendung, an der die Arbeitsweise verdeutlicht werden soll, wirdin diesem Abschnitt ein Programm entwickelt, daß zwei Listen konkateniert.

Das Prädikat hat folgende Gestalt:konk(<Liste 1>,<Liste 2>,<Konkatenation von Liste 1 und Liste 2>) undwird durch folgende Fakten und Regeln definiert:

konk([],List,List).konk([X|List1],List2,[X|List3]) :- konk(List1,List2,List3).

Die folgenden Beispiele sollen nun zeigen, wie dieses Prädikat je nach Art derAnfrage, unterschiedliche Aufgaben bewältigen kann. Wesentlich dabei ist, das dieArgumente des Prädikates Informationen in zwei Richtungen – den Richtungen„input“ und „output“ – Informationen fließen lassen können.

Zerlegung ?- konk(L1,L2,[a,b,c]).Als Ausgabe werden alle durch das Programm beschriebenen Möglichkeitender Zerlegung aufgeführt.

L1 = []L2 = [a, b, c] ;

L1 = [a]L2 = [b, c] ;

L1 = [a, b]L2 = [c] ;

L1 = [a, b, c]L2 = [] ;

no

Die Reihenfolge wird durch das Programm und die Abarbeitungsstrategieerzeugt. Nach jeder Bindung wird das Backtrackingverfahren aktiviert, umdie restlichen Möglichkeiten aufzulisten.


Zerlegung bzgl. ausgewählter Elemente ?- konk(Vorher,[mai|Nachher],[jan,feb,mrz,apr,mai,jun,jul,aug,sep,okt,nov,dez]).Es gibt nur genau eine mögliche Lösung:

Vorher = [jan, feb, mrz, apr]Nachher = [jun, jul, aug, sep, okt, nov, dez]

yes

Vorgänger/Nachfolger ?- konk(_,[Vorgaenger,mai,Nachfolger|_],[jan,feb,mrz,apr,mai,jun,jul,aug,sep,okt,nov,dez]).Auch hier gibt es nur genau eine Lösung bzw. Belegung der beiden unge-bundenen Variablen, die die Aussage/Anfrage war macht.

Vorgaenger = aprNachfolger = jun

yes

Abschneiden ?- LIn = [a,b,c,x,x,x,d,e,f],konk(LOut,[x,x,x|_],LIn).Diese Form des Aufrufes zeigt die Verwendung des Unifikators = als Zuwei-sung. Durch die Unifikation wird der Wert an das Prädikat konk übergeben.Resultat des Aufrufes ist:

LIn = [a, b, c, x, x, x, d, e, f]LOut = [a, b, c]

yes

member Die Definition eines Prädikates member über das Prädikat konk würdewie folgt aussehen:

member(Element,Liste) :- konk(_,[Element|_], Liste).

Ein Element ist in einer Liste enthalten, falls diese Liste sich so in zweiListen zerlegen läßt (unter Beibehaltung der Reihenfolge der Elemente),daß dieses Element das erste Element der zweiten Liste ist.

1.1.1.7 Die Türme von Hanoi

Die „Türme von Hanoi“ ist ein mit drei Stangen und einem Satz von Scheibengespieltes Spiel. Die Scheiben werden nach ihrem Durchmesser geordnet und aufdie Stangen mittels eines durch das Zentrum von jeder Scheibe gebohrten Lochs


aufgesteckt. Das Ziel des Spiels ist, alle Scheiben von der linken Stange auf diemittlere Stange zu versetzen. Die rechte Stange kann als eine „Ersatz-“Stange -eine temporäre Stelle für die Scheiben - benutzt werden.

Jedes Mal, wenn eine Scheibe von einer Stange auf eine andere versetzt wird,müssen zwei Regeln beachtet werden:

1. Nur die oberste Scheibe auf einer Stange kann versetzt werden, und

2. keine Scheibe kann auf eine kleinere Scheibe gesetzt werden.

Viele Leute, die dieses Spiel spielen, entdecken tatsächlich nie die ziemlicheinfache Strategie, die das Spiel der „Türme von Hanoi“ mit drei Stangen und NScheiben sicher spielt. Hier des Rätsel Lösung:

• Das Spielende ist, wenn keine Scheiben mehr auf der linken Stange steckenund alle Scheiben auf der mittleren Stange sind.

• 1. Sonst sind N -1 Scheiben von der linken Stange (Quelle) auf die rechteStange (Hilfsplatz) mit Hilfe der mittleren Stange (Ziel) zu versetzen.Dies ist eine rekursive Strategie!

2. Die N-te einzelne Scheibe kann dann von der linken Stange auf diemittlere Stange gesetzt werden.

3. Schließlich müssen die N -1 Scheiben von der rechten Stange auf diemittlere Stange mit Hilfe der linken Stange versetzt werden.

Das Prolog Programm, das diese Strategie implementiert, wird wie folgt defi-niert: Ein Prädikat hanoi wird so definiert, daß hanoi(N) die Ausgangssituationbeschreibt, in der N Scheiben auf der linken Stange (Quelle) stecken. Von denzwei Klauseln move beschreibt die erste das Spielende und die zweite Klauselimplementiert den rekursiven Fall. Bei dem Spielende genügt es, die Anzahl derScheiben auf der linken Stange zu prüfen, da die zweite Klausel einen komplet-ten Spielzug beschreibt, also alle Scheiben von der linken Stange auf die mittlereStange aufsteckt. Das Prädikat move hat vier Argumente: Das erste Argumentist die Anzahl von zu bewegenden Scheiben. Die anderen Drei stellen die Poledar: die Quelle, der Zielort und der Hilfsplatz. Das Prädikat inform, daß writeverwendet, um die Namen der Pole auszudrucken, realisiert das Versetzen einerScheibe.

% Tuerme von Hanoihanoi(N) :- move(N,left,middle,right).

% Spielregeln/-strategiemove(0,_,_,_) :- !.move(I,Q,Z,Tmp) :- J is I - 1,


move(J,Q,Tmp,Z),inform(Q,Z),move(J,Tmp,Z,Q).

% Ausgabe Funktioninform(X,Y) :- write([move,a,disc,from,the,X,pole,to,the,Y,pole]),nl.

Ein kleiner Beispielaufruf erzeugt dann nachfolgende Ausgaben.

6 ?- hanoi(1).[move, a, disc, from, the, left, pole, to, the, middle, pole]

Yes

7 ?- hanoi(2).[move, a, disc, from, the, left, pole, to, the, right, pole][move, a, disc, from, the, left, pole, to, the, middle, pole][move, a, disc, from, the, right, pole, to, the, middle, pole]

Yes

8 ?- hanoi(3).[move, a, disc, from, the, left, pole, to, the, middle, pole][move, a, disc, from, the, left, pole, to, the, right, pole][move, a, disc, from, the, middle, pole, to, the, right, pole][move, a, disc, from, the, left, pole, to, the, middle, pole][move, a, disc, from, the, right, pole, to, the, left, pole][move, a, disc, from, the, right, pole, to, the, middle, pole][move, a, disc, from, the, left, pole, to, the, middle, pole]

Yes

1.1.1.8 Der Cut

Der Cut, notiert als !,ist ein ganz spezielles Prädikat in Prolog, daß dem Program-mierer erlaubt, den Ablauf des Interpreters zu steuern. Mittels diesem Konstruktkann der Programmierer Prolog mitteilen, welche Möglichkeiten des Backtrackingnicht verfolgt werden müssen bzw. welche nicht verfolgt werden sollen. Für denEinsatz des Cut’s sprechen zwei wesentliche Gründe.

• Das Programm wird schneller ablaufen, da keine Zeit verwendet wird, Zielezu beweisen, die nicht zu beweisen sind.

• Der Speicherplatzbedarf sinkt, da einige Aufsetzpunkte für das Backtrackingnicht mehr gespeichert werden müssen.


Gegen den Einsatz des Cut’s spricht die Lesbarkeit und Überschaubarkeit einesProgramms. Allzuschnell werden richtige Lösungen abgeschnitten. Letztendlichbeeinträchtigt der Cut die deklarative Natur von Prologprogrammen und solltedaher nur verwendet werden, wenn es unbedíngt erforderlich ist.

Der Cut wird als normales Prädikat in Prolog behandelt. Die Abarbeitung istimmer erfolgreich und bewirkt den folgenden Seiteneffekt: Alle Aufsetzpunkte fürdas Backtracking, die für die links vom Cut stehenden Prämissen (bzw. die dortmöglichen alternativen Variablenbindungen) und für die Regel (bzw. Alternativenfür diese Regel), in der der Cut aufgeführt ist, werden gelöscht. Mit anderenWorten: Für den links vom Cut stehenden Teil einer Regel gibt es nur genau eineBelegung bzw. dieser Teil gilt als bewiesen und alle Alternativen werden gelöscht,wenn der Cut abgearbeitet wurde.

Bei dem Einsatz des Cut’s werden die folgenden zwei Arten unterschieden.

grüner Cut : dient der Effektivierung der Abarbeitung, d.h. Alternativen wer-den „entfernt“, die zu keiner Lösung führen. Das Entfernen dieser Cut’swirkt sich nur auf die Laufzeit des Programms aus, jedoch nicht auf dieLösungen!

roter Cut : dient der Erhaltung der Semantik eines Prädikates. Das Entfernendieser Cut’s wirkt sich sowohl auf die Laufzeit wie auch die Lösungen desProgramms aus!

Beispiel 1.1 Nachfolgend wird für die Funktion

f(x) :=

0, falls x < 32, falls 3 ≤ x < 64, falls 6 ≤ x

ein Beispiel aufgezeigt, wie die unterschiedlichen Arten des Cut verwendet werdenkönnen.

kein Cut Zur Implementierung der Funktion wird das Prädikat f(<Input>,<Output>)verwendet. Jede Alternative der Funktion muß durch eine eigene Regel de-finiert werden.

f(X,0) :- X < 3.f(X,2) :- 3 =< X, X < 6.f(X,4) :- 6 =< X.

In der nachfolgenden Tabelle ist die Abarbeitung für die Anfrage ?- f(1,Y),2<Yaufgezeigt.


Ziel geprüfte Regel/Fakt Kommentar:- f(1,Y), 2<Y. Ist f(1)>2 ?

f(X,0) :- X<3. Bindungen: X=1, Y=0:- 1<3, 2<0.:- 2<0.

Fehlschlag: Backtracking! Backtracking nicht notwendig!f(X,2) :- 3=<X, X<6. Bindungen: X=1, Y=2

:- 3=<1, 1<6, X < 62<2. Fehlschlag: Backtracking! Backtracking nicht notwendig!

f(X,4) :- 6=<X. Bindungen: X=1, Y=4:- 6=<1, 2<4.

Fehlschlag!no

Nachdem f(1) berechnet wurde, wurde zweimal das Backtracking aktiviert,obwohl dies zu keiner Lösung führen kann. Dies liegt hier daran, daß dieFallunterscheidungen der Funktion f disjunkt sind.

grüner Cut In dieser Variante wird der Quellcode so erweitert, daß die unnö-tigen Backtrackingschritte entfallen.

f(X,0) :- X < 3,!.f(X,2) :- 3 =< X, X < 6,!.f(X,4) :- 6 =< X.

In der nachfolgenden Tabelle ist die Abarbeitung für die Anfrage ?- f(1,Y),2<Yaufgezeigt.

Ziel geprüfte Regel/Fakt Kommentar:- f(1,Y), 2 < Y. Ist f(1) > 2 ?

f(X,0) :- X < 3,!. Bindungen: X = 1, Y = 0:- 1 < 3, !, 2 < 0.:- !, 2 < 0.

alle Aufsetzpunkte für dasBacktracking sind gelöscht

:- 2 < 0.Fehlschlag! Backtracking nicht möglich!

no

roter Cut In dieser Variante werden einige Ziele entfernt, da durch Kenntnisüber den Ablauf und Einsatz des Cut’s klar ist, das diese nicht bewiesenwerden müssen.


f(X,0) :- X < 3,!.f(X,2) :- X < 6,!.f(_,4).

In der nachfolgenden Tabelle ist die Abarbeitung für die Anfrage ?- f(1,Y),2<Yaufgezeigt. Dabei wird nun demonstriert, wieso es sich hier um einen rotenCut handelt, indem der Ablauf für die Variante des roten Cut ohne dieseCut’s durchgeführt wird. Bei dem grünen Cut ist klar, daß die Lösungen ge-genüber der Variante ohne Cut gleich bleiben. Nur die Laufzeit ändert sich,wie die Ablauftabelle zeigt.

Ziel geprüfte Regel/Fakt Kommentar:- f(1,Y), 2 < Y. Ist f(1) > 2 ?

f(X,0) :- X < 3. Bindungen: X = 1, Y = 0:- 1 < 3, 2 < 0.:- 2 < 0.

Fehlschlag: Backtracking! Backtracking nicht erlaubt!f(X,2) :- X < 6. Bindungen: X = 1, Y = 2

:- 1 < 6, 2 < 2.:- 2 < 2. Falsche Semantik von f!

Fehlschlag: Backtracking! Backtracking nicht erlaubt!f(X,4). Bindungen: X = 1, Y = 4

:- 2 < 4.Y = 4 Erfolg!yes

Dieser Ablauf zeigt, daß ohne die Cut’s die Semantik des Programms sichgewaltig geändert hat. Die Cut’s sind also notwendig, damit das Programmdie Funktion f realisiert.

1.1.1.9 Negation

Die Leitmotive beim klassischen Wahrheitsbegriff waren „die Aussage ist entwe-der wahr oder falsch“ (Dichotomie) und „die Wahrheit einer zusammengesetztenAussage hängt nur von der Wahrheit der Teilaussagen und nicht von deren Bedeu-tung ab“ (Extensionalität). Im Prinzip ist dann die Wahrheit als eine rekursiveFunktion (über den Aufbau der Aussagen) erklärt und jede Aussage hat bei jederInterpretation (Belegung aller Variablen) einen wohlbestimmten Wahrheitswert.In dieser Hinsicht stellt die Behandlung der Negation ein schwieriges Unterfangendar, da es um die Wahrheit einer negierten Aussage geht. Im wesentlichen lassensich folgende drei Arten der Negation unterscheiden:


Open World Assumption (OWA): Ein Sachverhalt wurde genügend model-liert. Über das, was nicht modelliert wurde, kann keine Aussage gemachtwerden.„Wer nicht im Telefonbuch steht, kann ein Telefon haben oder nicht.“

Closed World Assumption (CWA): Ein Sachverhalt wurde erschöpfend mo-delliert. Alles was nicht modelliert wurde, gilt dementsprechend nicht.„Wer nicht im Telefonbuch steht, hat auch kein Telefon.“

Negation-as-Failure (NaF): Die Naf ist ein Spezialfall der CWA. Für eine Aus-sage, für die alle Beweisversuche mit einem Beweisverfahren scheitern, wirddie Negation als wahr angenommen.„Wenn nicht bewiesen werden kann, das jemand ein Telefon hat, dann hater kein Telefon.“

In den folgenden Beispielen wird die Idee des NaF verdeutlicht, da Prolog die-se Art von Negation verwendet. Dazu wird das Prädikat fail benötigt. DiesesPrädikat hat keine Argumente und dessen Beweis scheitert immer. Das Prädikatnot sei noch nicht verfügbar. Am Ende der Beispiele wird die Realisierung diesesPrädikates aufgeführt.

Beispiel 1.2 Die Aussage „Mary liebt alle Tiere außer Schlangen“ soll in Prologformuliert werden. Um die Idee des NaF zu verwenden, wird die Aussage wiefolgt umgewandelt: „Wenn etwas eine Schlange ist, ist Mary liebt dieses etwasnicht wahr; sonst, wenn dieses etwas ein Tier ist, liebt Mary dieses etwas.“ InProlog erhält diese Aussage folgende Gestalt:

liebt(mary, X) :- schlange(X), !, fail.liebt(mary, X) :- tier(X).

Wenn also der Beweis für schlange(X) gelungen ist, wird der Beweis für liebt(mary,X) durch die Kombination !, fail zum scheitern gebracht. Das Cut sorgt dafür,daß kein Backtracking für das Ziel aktiviert wird. Dieser Cut ist ein roter Cut,da ohne ihn die Semantik des Programms verändert wird!

Beispiel 1.3 Das Prädikat ungleich ist zu realisieren. Mit der Idee des NaF istder erfolgreiche Beweis ungleich(X,X) zu verhindern.

ungleich(X, X) :- !, fail.ungleich(_, _).

Auch hier wird durch die Kombination eines roten Cut und dem Prädikat faildas gewünschte Ziel erreicht.

Das Prädikat not kann nun, sofern nicht vorhanden, ähnlich den Beispielenwie folgt realisiert werden.


not(X) :- X, !, fail.not(_).

Wenn also X bewiesen werden kann, darf not(X) nicht beweisbar sein. Ist X nichtzu beweisen, wird über das Backtracking not(X) bewiesen.

Diese Art der Negation ist mit Vorsicht zu verwenden. Gegeben sei nachfol-gendes Beispiel, zu dem die Anfrage ?- not(p(b)) gestellt wird.

p(b) :- not(q(a)).q(a).

Bei der Abarbeitung dieser Anfrage wird zuerst p(b) versucht zu beweisen. Diesführt dazu, daß not(q(a)) und damit q(a) bewiesen werden sollen. Da q(a)beweisbar ist, schlägt der Beweis für not(q(a)) fehl. Dies führt wiederum da-zu, daß der Beweis für p(b) fehl schlägt und damit not(p(b)) bewiesen wurde.Das „Fehlschlagen des Fehlschlagens“ der Beweissuche einer Behauptung die ur-sprüngliche Behauptung impliziert, war eigentlich nicht ausgemacht. In diesemSinne ist zwar mit der Regel eine Implikation ausgedrückt worden. Durch die Artder Negation wird daraus jedoch eine Äquivalenzbeziehung.

Gegeben sei nun nachfolgendes Beispiel, zu dem die Anfrage ?- not(r(a))gestellt wird.

r(a) :- not(q(X)),p(X).q(a).p(b).

Im Verlauf der Abarbeitung wird der Aufruf von q(X) mit der Bindung von X ana bewiesen, womit die Beweise von not(q(X)) und r(a) scheitern und somit dieursprüngliche Behauptung not(r(a)) als bewiesen gilt. Wenn nun aber die Regelsemantisch äquivalent in r(a) :- p(X),not(q(X)) umscheiben, würde die Ab-arbeitung von p(X) zu der Bindung von X an b führen. Dies wiederum führt zumScheitern des Beweises von q(b), also dem erflogreichen Nachweis von not(q(b))und damit dem erfolgreichen Nachweis von r(a), womit die ursprüngliche Anfra-ge als gescheitert gilt!

Die hier aufgeführten Probleme liegen aber schon in der Natur der CWA, diezu Inkonsistenzen führen kann. Dies betrifft auch eine allgemeine Kritik an derklassischen Logik, die dahin geht, daß es sinnlos sei zu behaupten, „etwas sei so“,wenn man es nur indirekt beweisen könne, und daß man nur von Dingen redensolle, die man konkret konstruieren kann.

1.1.2 Prolog: Unifikation und Resolution

Die Unifikation und die Resolution stellen einen wesentlichen Bestandteil desInterpreters von Prolog dar. Deshalb wird an dieser Stelle eine allgemeine Be-trachtung dieser beiden Teile vorgenommen. Für diesen Abschnitt wird eine Ver-trautheit mit der Prädikatenlogik vorausgesetzt.


1.1.2.1 Unifikation

In Prolog stellt sich während einer Abarbeitung zunächst die Frage, welche Regeloder welcher Fakt zum Beweis des aktuellen Zieles verwendet werden kann. DiesesProblem wird gelöst, indem versucht wird, das aktuelle Ziel und den Kopf einerRegel bzw. ein Fakt in die gleiche syntaktische Form zu transformieren. Habenbeide Terme keine Variablen, ist das Problem einfach: beide müssen syntaktischexakt übereinstimmen. Kommen jedoch in den Termen Variablen vor, müssen Be-legungen für diese Variablen gefunden werden, um die beiden Terme syntaktischgleich zu machen. Für dieses Problem ist die Unifikation zuständig.

Die Unifikation ist ein Prozeß zur Überprüfung, ob zwei Terme durch einegeeignete Substitution ihrer Variablen syntaktisch identisch werden. Unter einerSubstitution wiederum wird eine Menge von Zuordnungen zwischen Variablenund Termen verstanden, geschrieben als (<Variable>|<Term>), in denen jedeVariable höchstens einem Term zugeordnet wird. Nach Möglichkeit darf keineVariable in dem Term vorkommen, der ihr zugeordnet ist. Dies wird auch alsoccur-check bezeichnet.

Beispiel 1.4 (Substitution) Gegeben sei die Substitution σ1 = {(X|b), (Y |b)}.Angewendet auf den Term g(X, h(Y )) ergibt dies σ1(g(X, h(Y ))) = g(b, h(b)).

Sei eine weitere Substitution gegeben, mit σ2 = {(X|f(Y )), (Y |g(X))}. Dannergibt die Anwendung der Konkatenation σ1 ◦ σ2 auf diesen Term, also σ1 ◦σ2(g(X, h(Y ))), die Form σ1(σ2(g(X, h(Y )))) = σ1(g(f(Y ), h(g(X)))) = g(f(b), h(g(b))).

Mittels der Substitution läßt sich nun für zwei Terme die Unifikation beschrei-ben durch: Suche eine Substitution σ, so daß für zwei gegebene Terme s, t gilt:σ(s) = σ(t). Dabei ist = die syntaktische Gleichheit. Für die Substitution gilt dieEinschränkung, daß eine Variable nicht in dem ihr zugeordneten Term vorkom-men darf.

Ein Match hingegen ist wie folgt beschrieben: Suche eine Substitution σ, sodaß für zwei gegebene Terme s, t gilt: σ(s) = t.

Beispiel 1.5 (Unifikation) Gegeben seien die beiden Terme s = f(X, g(a, b))und t = f(g(Y, b), X). Dann gilt mit der Substitution σ = {(X|g(a, b)), (Y |a)},daß σ(s) = σ(t).

Gegeben seien die beiden Terme s = X und t = Y . Dann gilt mit der Substi-tution σ = {(X|Y )}, daß σ(s) = σ(t).

In dem zweiten Beispiel hätte auch die Substitution σ = {(X|42), (Y |42)} zumgewünschten Resultat geführt.

In Prolog wird mittels Unifikation bestimmt, welche Regel bzw. Fakt zum Be-weis verwendet werden soll. Beim Fehlschlagen wird ein Backtracking aktiviert,daß nach alternativen Belegungen für Variablen schaut oder nach alternativen Re-geln/Fakten. Sehr aufwendig für den Prozeß wäre, wenn das Backtracking auch


noch nach alternativen Unifikatoren fragen müsste. Dieses Problem wird umgan-gen, indem der allgemeinste Unifikator bestimmt wird. Dieser umfaßt alle mög-lichen Unifikatoren, denn ein Unifikator σ ist ein allgemeinster Unifikator, wennes für alle anderen Unifikatoren ω es einen Unifikator ξ gibt, so daß ξ ◦ σ = ω.

Beispiel 1.6 (Allgemeinster Unifikator) Gegeben seien die beiden Terme s =f(X,Y ) und t = f(Z, Y ). Ein Unifikator wäre ω = {(X|ah), (Z|ah)}. Ein all-gemeinster Unifikator ist σ = {(X|Z)}. Es gilt z.B. mit ξ = {(Z|ah)}, daßξ ◦ σ = ω.

Ein allgemeinster Unifikator ist bis auf Namensumbenennungen von Variableneindeutig bestimmt. Die Frage ist nun nach einem Algorithmus für die Unifikation,also läßt sich der allgemeinste Unifikator immer finden ? Im folgenden wird einevereinfachte Version dieses Algorithmus aufgeführt.

Algorithmus 1.1 (unifiziere(<Term1>,<Term2>,<Substitution>)) Seiens, t die zu unifizierenden Terme und σ = ∅. Dann unifiziere(s, t, σ)

1. Wende σ auf s und t an: t := σ(t); s := σ(s).

2. Wenn s = X = t eine Variable ist, dann gehe zu 5.

3. Wenn s = X eine Variable und t =< Term > ein Term, dann ...Wenn t = X eine Variable und s =< Term > ein Term, dann ...

• X kommt in < Term > vor (negativer occur-check), gehe nach 6.

• sonst, erweitere die Substitution: σ := ((X| < Term >) ◦ σ) ∪ {(X| <Term >)}. Gehe nach 5.

4. Wenn s = f(s1, s2, . . . , sn), t = g(t1, t2, . . . , tm) und f = g und n = m,dann rufe für alle 1 ≤ i ≤ n σi := unifiziere(si, ti, σi−1) auf, wobei σ0 = ∅und σ := σn. Falls die Iteration erfolgreich war,

• gehe nach 5.

• Sonst, gehe nach 6.

5. Die beiden Terme sind unifizierbar. Gebe σ zurück.

6. Die beiden Terme sind nicht unifizierbar. Breche den Algorithmus ab.

In den meisten Interpretern von Prolog wird der sehr aufwendige occur-checknicht durchgeführt. Wird die Unifikation durch das Symbol = direkt verwendet,wird die Verantwortung in die Hände des Programmierers gelegt. Bei der Unifi-kation von aktuellem Ziel mit Köpfen der Regeln bzw. Fakten nimmt Prolog eineUmbenennung der Variablen in den beiden Termen vor, d.h. die Variable X ineinem Ziel ist ungleich einer Variablen X in einem Fakt oder in dem Kopf einer


Regel. Die abprüfung der Stelligkeit führt zu dem Effekt, daß Prolog Prädikatemit gleichem Namen aber unterschiedlicher Stelligkeit zuläßt. Daher begründetsich auch die Schreibweise <Name>/<Stelligkeit>, wie etwa not/1. So sind z.B.reverse/2 und reverse/3 für Prolog zwei unabhängige Funktionen.

Im folgenden wird eine vereinfachte Version des occur-check Algorithmus auf-geführt.

Algorithmus 1.2 (occur-check(<VAR>,<Term>)) Sei X die Variable undt der Term. Dann occur-check(X,t)

1. Wenn t eine Variable ist, dann falls X ungleich t ist,

• gehe nach 3.,

• sonst gehe nach 4.

2. Wenn t = g(t1, t2, . . . , tm) ein Term ist, dann rufe für alle 1 ≤ i ≤ nsequentiell occur-check(X,ti) auf. Falls die Iteration erfolgreich war, gehenach 3. Sonst, gehe nach 4.

3. Breche den Algorithmus ab, X kommt nicht in t vor.

4. Breche den Algorithmus ab, X kommt in t vor.

1.1.2.2 Resolution

Die Resolution ist ein indirektes Beweisverfahren. Um eine Formel bzw. eineHypothese Φ zu beweisen, wird versucht, ihre Negation ¬Φ zu widerlegen. Da dieResolution nur auf Klauseln6 arbeitet, muß eine allgemeine Formel zunächst inKlauselform transformiert werden. Dies kann i.allg. nur so gemacht werden, daßdie neue Formel Ψ die Eigenschaft hat: „Wenn Ψ widersprüchlich ist, dann warauch schon Φ widersprüchlich.“

Die Resolution ist nun in dem Sinne vollständig, daß sie alle Widersprücheals solche erkennt, d.h. von allen möglichen Folgerungen der Formel Φ erkenntdie Resolution die Widersprüche mit Sicherheit. Daher ist dieses Verfahren alsonicht ein allgemein vollständiges Beweisverfahren, sondern nur ein widerlegungs-vollständiges Beweisverfahren.

Die Resolution verwendet folgende zwei Regeln, die iterativ auf die Menge derEingabeklauseln angewendet werden. Dabei seien

• C und D zwei Klauseln

• l1 ∈ C und ¬l2 ∈ D zwei Literale

• σ ein allgemeinster Unifikator mit σ(l1) = σ(l2).6Eine Atomformel ist von der Form p(< Term1 >,< Term2 >, . . . , < Termn >). Ein Literal

ist eine Atomformel oder eine negierte Atomformel. Eine Klause ist eine Menge von Literalen.


Regel 1 Die wesentliche Regel ist die Resolventenregel

C,D

((σ(C) \ σ(l1)) ∪ ((σ(D) \ σ(¬l2))

Mit anderen Worten, die Regel streicht komplementäre Literale aus denvorgelegten Klauseln.

Regel 2 Für eine Klausel wird die Faktorenregel angewendet:

C

σ(C)

Beispiel 1.7 Die Resolventenregel ist eine Verallgemeinerung eines klassischenlogischen Schlusses: der Regel des modus ponens. Diese Regel

A,A→ B

B

hätte folgende Gestalt:{A}, {¬A,B}

{B}

Das Reolutionsverfahren wird nun durch nachfolgenden Algorithmus beschrie-ben. Dabei gilt der Beweis als erfolgreich geführt, wenn die leere Klauselmengeabgeleitet wurde.

Algorithmus 1.3 Gegeben sei die Klauselmenge K = {K1, . . . , Kn}.

1. Wähle zwei Klauseln Ki, Kj ∈ K mit i, j beliebig.

2. Resolviere Ki, Kj zu R.

(a) Falls keine Resolution möglich, gehe zu 4.

(b) sonst, K := K ∪ {R} und falls {} ∈ K gehe zu 3.

3. K ist widersprüchlich.

4. K ist erfüllbar.

Prolog verwendet eine spezielle Art der Resolution, die sogenannte SLD-Resolution:Ein Prolog Programm ist eine Menge von Klauseln. Die Unifikation von Klau-seln wird dabei auf die Unifikation des Kopfes bei Regeln beschränkt. In Schritt1. werden nicht beliebige Klauseln gewählt. Eine Klausel ist immer die der An-frage, also der aktuellen Ziele, die andere wird durch die Abarbeitungsstrategieausgewählt. Bei der Unifikation mit einer Regel wird die Klausel der Anfrage mo-difiziert. Danach wird für diese Klausel das Verfahren wieder aufgesetzt. Ziel istnun, die Anfrageklausel zu leeren und damit die getroffene Aussage zu beweisen.


Beispiel 1.8 Gegeben sei folgende kleine Datenbank

mutter(sibille,gregor).elternteil(X,Y) :- mutter(X,Y).

Wir betrachten die Anfrage ?- elternteil(sibille,gregor). Nach Wahl derRegel wird nun resolviert:

{¬elternteil(sibille, gregor)}, {elternteil(X,Y ),¬mutter(X, Y )}{¬mutter(sibille, gregor)}

Das zu beweisende Ziel wird verändert und der Fakt ausgewählt. Die Resolutionergibt:

{¬mutter(sibille, gregor)}, {mutter(sibille, gregor)}{}

Die Anfrage konnte also belegt werden, da ihre Negation zusammen mit der Da-tenbank widersprüchlich ist.

1.1.3 Prolog: Programmieren mit Listen

Listen stellen eine elementare Datenstruktur in Prolog dar. Daher werden zu-nächst elementare Vorgehensweisen bei der Behandlung von Listen aufgeführt.Zwei Sortieralgorithmen dienen dann als exemplarische Anwendungen.

1.1.3.1 Abarbeitung

Es gibt prinzipiell zwei Arten, Listen zu bearbeiten bzw. aufzubauen.

1.1.3.2 Top-Down Verfahren

Dieses Verfahren zeichnet sich durch folgende Punkte aus.

• Die Erweiterung der Liste erfolgt nach „rechts“ in die Tiefe.

• In der Abbruchbedingung der Rekursion steht als „Ergebinsparameter“ eineListe.

• In der rekursiven Regel steht im Kopf als „Ergebnisparameter“ eine Listeder Form [Element|Liste], wobei Element das neue Element und Listedie noch zu erzeugende (Rest-)Liste kennzeichnet.

• Im Körper der rekursiven Regel steht im rekursiven Aufruf an der Positiondes „Ergebnisparameters“ die noch zu erzeugende (Rest-)Liste Liste.

• Auf die bisher erzeugte Liste kann während der Rekursion nicht zugegriffenwerden; sie steckt in dem rekursiven Aufruf.


Beispiel 1.9 Als Beispiel eines Aufbaus einer Liste nach diesem Verfahren seidie Konkatenation von zwei Listen, wie sie bereits schon einmal aufgeführt wurde.

/* konk(<Liste 1>,<Liste 2>,<Konkatenation von Liste 1 und Liste 2>) */konk([],List,List).konk([X|List1],List2,[X|List3]) :- konk(List1,List2,List3).

Der „Ergebnisparameter“ ist hier an Position drei. In der Abbruchbedingung wirddie zweite Liste direkt an die Position drei kopiert. Unter Variablen List3 istkeine Liste zu finden. Diese wird erst aufgebaut.

1.1.3.3 Bottom-Up Verfahren

Dieses Verfahren zeichnet sich durch folgende Punkte aus.

• Die Erweiterung der Liste erfolgt nach „links“ in die Höhe.

• In der Abbruchbedingung der Rekursion steht als „Ergebinsparameter“ bzw.zusätzlichem Parameter entweder die gleichen Variablen (häufigster Fall)oder Strukturen, die die gleichen Ausdrücke enthalten, um z.B. eine ab-schließende Linkserweiterung vorzunehmen.

• In der rekursiven Regel steht im Kopf eine Variable als zusätzlicher Para-meter und eine von allen anderen verschiedene Variable als „Ergebnispara-meter“.

• Im Körper der rekursiven Regel steht im rekursiven Aufruf eine Liste vonder Form [Element|Liste], wobei Element das neue Element und Listedie bisher ermittelte Liste kennzeichnet.

• Auf die bisher erzeugte Liste kann während der Rekursion zugegriffen wer-den.

• Der Aufruf erfolgt mit der leeren Liste an der Stelle des zusätzlichen Para-meters.

Beispiel 1.10 Als Beispiel sei das Umdrehen eine Liste aufgeführt.

% drehen/2 (reverse)drehen(Liste,GedrehteL) :- drehen(Liste,[],GedrehteL).%drehen/3drehen([],Liste,Liste).drehen([X|Rest],Liste,Erg) :- drehen(Rest,[X|Liste],Erg).

Zunächst wird zur Hilfe ein dreistelliges Prädikat definiert, das in der Mitte denzusätzlichen Parameter hat. Der „Ergebnisparameter“ steht ganz rechts. In demzusätzlichen Argument wird die gedrehte Liste aufgebaut und am Ende an diePosition des „Ergebnisparameters“ kopiert. Unter der Variablen Liste ist diebisher aufgebaute Liste zu finden.


1.1.4 Anwendung: Sortierverfahren

Die beiden im folgenden beschriebenen Sortierverfahren sind wohlbekannt. Daherwerden sie an dieser Stelle nicht eingeführt. In den nachfolgenden Abschnittenwird ihre Realisierung besprochen. Da der Leserin/dem Leser sicherlich Realisie-rungen in Sprachen anderer Denkweisen bekannt sind, kann ein Vergleich die Artund Weise der logischen Programmierung verdeutlichen.

1.1.4.1 Bubblesort

Bubblesort geht zur Sortierung einer Liste Liste – verbal beschrieben – wie folgtvor:

• Finde zwei benachbarte Elemente X und Y (X links von Y) in Liste, so daßX > Y gilt; vertausche die beiden Elemente und sortiere die so entstandeneListe.

• Gibt es kein Paar X,Y in Liste mit X > Y, so ist diese Liste sortiert.

Diese Beschreibung versucht quasi eine Definition der Funktion Bubblesort vor-zunehmen und Regeln bzw. Fakten zu beschreiben, die in bestimmten Situationengelten. Diese werden nun in Prolog formal beschrieben, d.h. die etwas informal be-schriebene Definition muß nun in eine formale Repräsentation überführt werden.Das Resultat ist folgendes Programm.

% bubblesort/21 bubblesort(ListeIN, ListeOUT) :- findePaar(ListeIN,ListeZW),2 !,3 bubblesort(ListeZW,ListeOUT).4 bubblesort(ListeOUT,ListeOUT).5 findePaar([X,Y|Rest],[Y,X|Rest]) :- X > Y.6 findePaar([X|RestIN],[X|RestZW]) :- findePaar(RestIN,RestZW).

Das Prädikat findePaar sucht nach einem Unterscheidungspaar. Dieses Prädikatdarf nur erfolgreich bewiesen werden, wenn ein solches Paar existiert. Daher istkein Abbruch etwa der Form findePaar([],[]). vorgesehen. Das Abbruchkri-terium hier ist in Zeile 5: es gibt ein solches Paar.

Wenn ein solches Paar gefunden wurde (Zeile 1), wird die Ergebnisliste weitersortiert (Zeile 3). Der Cut in Zeile 2 ist dabei ein roter Cut. Sollte die rekursiveSortierung nicht erfolgreich sein, darf kein Backrtaking einsetzen: Sonst würdeeine nur partiell sortierte Liste als sortierte Liste aufgefaßt werden! Wenn keinPaar gefunden wurde (Scheitern in Zeile 1), ist die Liste sortiert (Zeile 4).


1.1.4.2 Quicksort

Quicksort geht zur Sortierung einer nicht leeren Liste Liste – verbal beschrieben– wie folgt vor:

• Lösche ein (beliebiges) Element X aus der Liste und Teile den Rest der Listein zwei Listen Kleiner und Groesser auf, so daß alle Elemnte aus Listedie größer sind als X in der Liste Groesser enthalten sind und sonst in derListe Kleiner.

• Sortiere die Liste Kleiner. Ergebnis ist die Liste KleinerOK.

• Sortiere die Liste Groesser. Ergebnis ist die Liste GroesserOK.

• Ergebnis ist die Konkatenation der Liste KleinerOK [X|GroesserOK].

Auch hier versucht diese Beschreibung eine Definition der Funktion Quicksort.Diese werden nun analog zu Bubblesort in Prolog formal beschrieben. Das Re-sultat ist folgendes Programm.

01 % quicksort/202 quicksort([],[]).03 quicksort([X|Liste],Resultat) :-

teileAuf(Liste,X,Kleiner,Groesser),04 quicksort(Kleiner,KleinerOK),05 quicksort(Groesser,GroesserOK),06 konk(KleinerOK,[X|GroesserOK],Resultat).07 % teileAuf/408 teileAuf([],_,[],[]).09 teileAuf([Y|Rest],X,[Y|Kleiner],Groesser) :- X >= Y,10 teileAuf(Rest,X,Kleiner,Groesser).11 teileAuf([Y|Rest],X,Kleiner,[Y|Groesser]) :- X < Y,12 teileAuf(Rest,X,Kleiner,Groesser).

Das löschen des Elementes wird durch die Unifikation mit [X|Liste] in Zeile 03vorgenommen. Die resultierende Liste Liste wird nun aufgeteilt. Die Zeilen 04– 06 entsprechen ziemlich genau den oben aufgeführten Punkten. Dabei wird inZeile 06 das bereits früher definierte Prädikat konk für die Konkatenation zweierListen verwendet. Die Aufteilung der Liste in den Zeilen 07 – 12 wird nach Top-Down Methode vorgenommen. Deshalb ist das Abbruchkriterium in Zeile 08 vonder Aussage, daß die Aufteilung einer leeren Liste nur leere Listen ergibt.

1.1.5 Prolog und Prädikatenlogik 1-ter Stufe

Wie bereits am Anfang erwähnt, ist mittels Prolog die Prädikatenlogik zur Pro-grammiersprache geworden. Da die allgemeine Prädikatenlogik jedoch zu ineffizi-ent ist, wurde ein (geeignetes) Fragment der Prädikatenlogik entwickelt, um die


skizzierte Vorgehensweise zu realisieren. Nach Bob Kowalski besteht demnach einAlgorithmus aus Logik und Kontrolle.

In diesem Abschnitt werden die Unterschiede explizit angesprochen.

1.1.5.1 Prolog und Prädikatenlogik: Syntax

Prädikatsymbole, z.B. P k, Ql, werden in Prolog als Funktor, z.B. p/k, q/l dar-gestellt.

Funktionssymbole, z.B. fk, gl, werden in Prolog als Funktor, z.B. f/k, g/ldargestellt. Dies liegt daran, dass die Prädikatenlogik nur Wahrheitswerte ver-rechnet, also insbesondere keine Funktionen auswertet. In Prolog kann aber insolchen Fällen nicht der Anwender vor dem Computer befragt werden. Prolog hatdaher die Auswertung von Funktionen integriert, die einmal durch Relationen,d.h. y = f(x) wird realisiert als f(x, y), oder Schnittstellen zu anderen Pro-grammiersprachen, d.h. hinter dem Funktor verbirgt sich z.B. ein Aufruf einerFunktion in der Programmiersprache C, umgesetzt wird.

Logiksymbole, z.B. ∧,∨,¬,→ (Junktoren) und ∀,∃ (Quantoren), werden inProlog wie folgt umgesetzt: , für ∧, (; ) für ∨, bzw. zwei (oder mehr) Regeln, notbzw. \+ für ¬ und :- für →, wobei hier die Richtung geändert wird, also :-entspricht logisch ←.

(Funktions-)Variablen, z.B. xi, werden in Prolog als Prolog Variablen Xi dar-gestellt.

Terme, z.B. fk(t1, . . . tk), werden in Prolog als Strukturen, z.B. f(t1, . . . , tk, Out),dargestellt.

Formeln, z.B. P (x, y)∧Q(z)→ Q(x), werden in Prolog als Regeln, z.B. q(X):- p(X,Y),q(Z)., dargestellt.

Normalformen, geschlossene Formel, etc. , werden in Prolog als bereinigte Prä-nexformel in Skolemform einer Hornlogikformel dargestellt, d.h. Prolog arbeitetnur auf einem Fragment der Prädikatenlogik!

1.1.5.2 Prolog und Prädikatenlogik: Semantik

Das Universum der Prädikatenlogik: Konstanten in Prolog, die in Fakten oderRegeln vorkommen bzw. Werte, die über externe Schnittstellen geliefert werden;sie werden in Prolog nicht explizit aufgeführt.

Die Abbildungen der Prädikatenlogik: Prolog hat im Kern nur Prädikate, de-ren Semantik durch Regeln und Fakten beschrieben werden bzw. durch externeSchnittstellen. Für Terme müssen Prädikate verwendet werden, die einen wei-teren (out-) Parameter für den Rückgabewert der zugehörigen Funktion haben.Die Berechnung erfolgt ebenfalls durch Regeln und Fakten bzw. durch externeSchnittstellen (siehe auch die Bemerkung im vorangegangenen Abschnitt).

Die Interpretation der Prädikatenlogik: Prolog bestimmt nicht direkt denWahrheitsgehalt einer Formel, sondern sucht mittels Resolution indirekt nach


einer Tautologie. Die Variablenbindungen geben dann quasi im Nachhinein dafürdas zugehörige Modell an.

1.1.5.3 Prolog und Prädikatenlogik: Beispiel

Wir geben ein Beispiel für die Eingabe einer prädikatenlogischen Formel in Prologund ein Beispiel für die Eingabe in dem erwähnten Interpreter für die Prädika-tenlogik.

Beispiel 1.11 Hier das Beispiel für Prolog: Formulieren Sie die nachfolgen-den Aussagen über die Bewohner von Transsylvanien (die Mensch oder Vampirsind) als prädikatenlogische Formeln. Bestimmen Sie dazu zunächst die elementa-ren/atomaren Elemente (im Sinne von Prädikaten und Funktionen) und ordnenSie diesen Buchstaben als Abkürzung zu. Versuchen Sie die Anzahl dieser Elemen-te klein zu halten (Denken Sie an die in den Formeln verwendbare Negation!).

Hier nun die Lösung:

1. „Alle geisteskranken Vampire sagen die Wahrheit.“Formal: ∀x : ((V (x) ∧G(x))→ W (x))Prolog: w(X) :- v(X),g(X).

2. „Ist ein Mensch geistig gesund, so ist mindestens einer seiner Elternteilegeistig gesund.“Formal: ∀x : ((¬V (x) ∧ ¬G(x))→ (¬G(v(x)) ∨ ¬G(m(x))))Hier ist zunächst eine Transformation notwendig wegen den ¬ und der ne-gation as failure von Prolog:

∀x : ((¬V (x) ∧ ¬G(x))→ (¬G(v(x)) ∨ ¬G(m(x)))) ≡

∀x : (¬(¬V (x) ∧ ¬G(x)) ∨ (¬G(v(x)) ∨ ¬G(m(x)))) ≡∀x : ((V (x) ∨G(x)) ∨ ¬(G(v(x)) ∧G(m(x)))) ≡∀x : (¬(G(v(x)) ∧G(m(x))) ∨ (V (x) ∨G(x))) ≡∀x : ((G(v(x)) ∧G(m(x)))→ (V (x) ∨G(x)))

v(X) :- vFKT(X,Out_v),g(Out),mFKT(X,Out_m),g(Out_m).g(X) :- vFKT(X,Out_v),g(Out),mFKT(X,Out_m),g(Out_m).

3. „Vampire heiraten nur Vampire.“Formal: ∀x : ((V (x) ∧ P (x, y))→ V (y))Polog: v(Y) :- v(X),p(X,Y).

4. „Alle geisteskranken Vampire haben mindestens ein Kind.“Formal: ∀x : ((V (x) ∧G(x))→ (∃y : (K(y, x))))Polog: k(Y,X) :- v(X),g(X).


Die elementaren/atomaren Elemente (im Sinne von Prädikaten und Funktionen)werden durch Angabe der Interpretation vorgenommen.

• Es sei U = { Menge der Bewohner von Transylvanien },

• I(v) := U → U ; mit f(x) = y, falls y ist Vater von x;

• I(m) := U → U ; mit f(x) = y, falls y ist Mutter von x;

• I(V ) := {x ∈ U |x ist Vampir },

• I(G) := {x ∈ U |x ist geisteskrank },

• I(W ) := {x ∈ U |x sagt die Wahrheit },

• I(P ) := {(x, y) ∈ U2|x ist mit y verheiratet },

• I(K) := {(x, y) ∈ U2|x ist Kind von y}.

Das Universum würde in Prolog nicht explizit angegeben, die Interpretationenwerden in Prolog je nach Kenntnisstand über die reale Situation durch Angabenvon Fakten oder Regeln angegeben, etwa (als nicht vollständiges) Beispiel fürFakten:

vFKT(vamp1,papavamp1).mFKT(vamp1,mamavamp1).v(vamp2).g(vamp2).w(vamp7).p(papavamp1,mamavamp1).k(vamp1,papavamp1).

Beispiel 1.12 Hier das Beispiel für den Interpreter: Gegeben sei folgende prä-dikatenlogische Formel G:

G ≡ (∀x : ∃y : R(x, y)) ∧ (∀x : ∃y : ¬R(x, y))∧

(∀x : ∀y : ∀z : (R(x, y) ∧R(y, z)→ R(x, z)))

Die Formel G ist erfüllbar. Geben Sie von allen Strukturen, die ein Modell vonG sind, eine Struktur A = (UA, IA) an, bei der die Anzahl der Elemente desUniversums minimal ist. Achtung: das Universum darf nicht leer sein!

Zeigen Sie, dass Ihre gewählte Struktur tatsächlich ein Modell der Formel Gist!

Hier nun die Lösung: A = (UA, IA), wobei UA = {a, b}, RA = {(a, a), (b, b)}.In unserem Interpreter würde dies wie folgt implementiert:

1.2. BOOLE’SCHE ALGEBRA 39

domain(i9, [a,b]).interpretation(i9,[r -> [(a,a),(b,b)]]).

Die Formel würde in unserem Interpreter wie folgt implementiert:

example_F(f(5), (forall(X,exists(Y,r(X,Y))) &forall(X,exists(Y,~ r(X,Y)))) &forall(X,forall(Y,forall(Z,

(r(X,Y) & r(Y,Z)) > r(X,Z))))).

Die angegebene Lösung kann nun wie folgt geprüft werden:

3 ?- test(f(5),i9).Die Formelforall($VAR(0),exists($VAR(1),r($VAR(0),$VAR(1))))&forall($VAR(0),exists($VAR(1),~r($VAR(0),$VAR(1))))&forall($VAR(0),forall($VAR(1),forall($VAR(2),

(r($VAR(0),$VAR(1))&r($VAR(1),$VAR(2)))>r($VAR(0),$VAR(2)))))ist in der Domaene [a, b]unter der Interpretation [r->[ (a, a), (b, b)]]und der Variablenbelegung []erfuellt.true

∀x : ∃y : R(x, y) kann erfüllt werden, da man zu jedem x y = x wählt.∀x : ∃y : ¬R(x, y) kann erfüllt werden, da man zu jedem x y = x wählt. Da

das Universum zwei Elemente beinhaltet, ist dies möglich.∀x : ∀y : ∀z : (R(x, y) ∧ R(y, z) → R(x, z) kann erfüllt werden, da für die

Voraussetzung der Implikation nur der Fall R(x, y) = R(y, z), also x = y = z inder zugehörigen Struktur möglich ist. Damit ist die Folgerung erfüllt, da so auchR(x, y) = R(y, z) = R(x, z) gilt.

Somit ist die gegebene Struktur für die gesamte Formel G ein Modell.

1.2 Boole’sche AlgebraHistorischer Ausgangspunkt war das Bestreben, die über zweitausend Jahre altenGesetze der klassischen logik mit mathematischen Mitteln in den Griff zu bekom-men. Dem englischen Mathematiker G. Boole (1815-1864) gelang es als erstem,diesen Prozeß der algebraischen Formalisierung einzuleiten. Die Boole’sche Alge-bra ist heute ein unentbehrliches Hilfsmittel beim Entwurf logischer Schaltungendigitaler Rechenanlagen.

Definition 1.2 Als Boole’sche Algebra (B; ∗; +;K) bezeichnen wir eine al-gebraische Struktur mit mindestens zwei Elementen (Null, Eins) auf der zwei


zweistellige Verknüpfungen ∗,+

B2 → B : mit (a, b)→ a ∗ b ∈ B

B2 → B : mit (a, b)→ a+ b ∈ B

und eine einstellige Verknüpfung K

B→ B : mit K(a)→ a−1 ∈ B

so erklärt sind, dass sie den folgenden Axiomen genügen:

1. ∗ und + sind kommutativ

2. ∗ und + sind wechselseitig distributiv:

∀a,b,c∈B a ∗ (b+ c) = a ∗ b+ a ∗ c ∧ a+ (b ∗ c) = a+ b ∗ a+ c

3. Eins (bezeichnet auch mit der Zahl 1) ist neutrales Element für ∗ und Null(bezeichnet auch mit der Zahl 0) ist neutrales Element für +

4. a−1 ist komplementär zu a in der folgenden Weise

∀a∈B∃a−1∈B a ∗ a−1 = 0 ∧ a+ a−1 = 1

Satz 1.1 Jede endliche Boole’sche Algebra (B; ∗; +;K) ist isomorph (= bijektiveAbbildung) einer Mengenalgebra (P (M);∩;∪;K), wobei die Eins die Menge Mselbst ist und die Null die leere Menge ∅.

1.2.1 Boole’sche Terme

Jede Zeichenkette aus 0, 1, Namen für boole’sche Variablen und den boole’schenVerknüpfungszeichen, die mittels den nachfolgenden Regeln erstellt wurde, nen-nen wir einen boole’schen Term. Die Regeln sind:

BTerm = 0 oder 1 oder boole’scher Variablenname

BTerm = (BTerm+BTerm) oder (BTerm ∗BTerm) oder (BTerm)−1

Schreibweise (nach Vereinfachung durch das Assoziativgesetz), z.B.: T (x, y, z) =(x ∗ y) + (x ∗ z) + (x ∗ y ∗ z) + y + z−1 + (0 ∗ 1).

Die konjunktive Normalform (KNF) ist die konjunktive Verknüpfung vondisjunktiven Verknüpfungen über boole’schen Variablen. Beispiel: T (x1, x2, . . . , xn) =(x1 + x2) ∗ (x1 + . . .+ xn) ∗ (x−1

1 + xn). Die KNF wird als kanonisch bezeichnet,wenn in jedem disjunktiven Teilterm stets alle Variablen vorkommen. Die Regelnsind:

AtomTerm = 0 oder 1 oder boole’scher Variablenname

1.3. AUSSAGENLOGIK 41

DisTerm = (DisTerm+ AtomTerm) oder AtomTerm

KNFTerm = (KNFTerm ∗DisTerm) oder DisTerm oder AtomTerm

Die disjunktive Normalform (DNF) ist die disjunktive Verknüpfung vonkonjunktiven Verknüpfungen über boole’schen Variablen. Beispiel: T (x1, x2, . . . , xn) =(x1∗x2)+(x1∗ . . .∗xn)+(x−1

1 ∗xn). Die DNF wird als kanonisch bezeichnet, wennin jedem konjunktiven Teilterm stets alle Variablen vorkommen. Die Regeln sind:

KonTerm = (KonTerm ∗ AtomTerm) oder AtomTerm

DNFTerm = (DNFTerm+KonTerm) oder KonTerm oder AtomTerm

1.2.2 Schaltalgebra

In der Schaltalgebra arbeitet man im wesentlichen mit der Konjunktion ∧, Diskjunk-tion ∨ und Negation ¬. Die Identität id wird aus praktischen Gründen benötigt.Mittels einer Verknüpfungstabelle werden die Schaltungen definiert.

x1 x2 x1 ∧ x2 x1 ∨ x2 ¬x1 idx1

0 0 0 0 1 00 1 0 1 1 01 0 0 1 0 11 1 1 1 0 1

Für aus diesen Verknüpfungen definierte höhere Verknüpfungen bzw. Schaltun-gen werden ggf. eigene Symbole eingeführt. Zu beachten in der Schaltalgebra ist,das jedes Schaltelement mit Takten geschaltet wird. Die Schaltbilder werden alsparallel geschaltet betrachtet, d.h. alle Schaltelemente bekommen das Schaltsi-gnal - der Takt - gleichzeitig. Den drei Basisverknüpfungen wird die Schaltzeit1 zugeordent. Für die aus diesen zusammengesetzten Schaltungen addieren sichentsprechend die Schaltzeiten. Aus praktischen Gründen wird dann auch eineVerzögerung notwendig: die Identität. Auch ihr wird die Schaltzeit 1 zugeord-net. Bei der Schaltzeit handelt es sich um eine Zeiteinheit; von der konkretenZeitausprägung wird abstrahiert.

1.3 AussagenlogikEine Aussage im Sinne der Aussagenlogik ist ein atomares sprachliches Gebilde,das eindeutig „wahr“ oder „falsch“ ist (Bivalenzprinzip). Die Aussagenlogik be-trachtet nun einfache Verknüpfungen zwischen atomaren Sprachlichen Gebilden,also Aussagen. „Das Ganze besteht nur aus der Summe der Teile“: Extensionali-tätsprinzip.

Beispiel: A = „Paris ist die Hauptstadt von Frankreich“ und B = „Mäuse jagenElefanten“ Gilt A ∧B oder A ∨B oder ¬B oder . . . ?


Die A und B sind keine Variablen im klassischen Sinne, sondern aussagen-logische Variablen im Sinne von Konstanten oder nullstelligen mathematischenFunktionen, d.h. einmal an einen Wert gebunden, ändert der sich nie und bevorjemand darauf zugreift, muss der Wert gebunden sein.

Aus der Wahrheit oder Falschheit einer Aussage kann nicht auf die Wahrheitoder Falschheit einer anderen Aussage geschlossen werden: Prinzip der logischenUnabhängigkeit.

In Prolog wird ein Interpreter für die Aussagenlogik zur Verfügung gestellt,der aus folgenden vier Dateien besteht:

main.pl Ist das Hauptmodul mit zwei Prädikaten zum Testen: test/1 als In-terpreteroberfläche zum testen von Formeln oder vorgegebenen Beispielen.test_tt/1 gibt zusätzlich noch die Wahrheitstafel der verwendeten Formelaus.

examples.pl Spezifikation der Aussagensymbole und einiger Formelbeispiele.

formulae.pl syntaktische Beschreibung: hier wird die Wohlgeformtheit von For-meln geprüft. Zudem gibt es Prolog-Prädikate, die syntaktische Informatio-nen liefern, etwa aussagensymbole_L/2.

modelCheckerAL.pl Ein aussagenlogischer Modell-Prüfer: hier wird die Seman-tik beschrieben. Zudem gibt es Prolog-Prädikate, die semantisch interessan-te Aspekte prüfen, etwa tautologie/1 oder erfuellbar/1.

Zu Beginn der Dateien findet man Anweisungen, z.B. :- op(800,yfx,user:(&)).% conjunction, die dazu dienen, Operatoren für den aussagenlogischen Inter-preter einzuführen. Das liegt daran, dass viele für den Interpreter notwendigeAufgaben direkt durch Prolog durchgeführt werden.

In den nachfolgenden Abschnitten wird nun auf Teile dieses Paketes verwiesen.Dies soll helfen, praktisch in SWI-Prolog die Aussagenlogik bearbeiten zu können,z.B. durch Erweiterungen im Interpreter oder einfach nur durch Arbeiten mitFormeln.

1.3.1 Syntax der Aussagenlogik

Eine atomare Formel hat die Form Ai, (i = 1, 2, 3, . . .). Formeln werden durchfolgenden induktiven Prozeß definiert:

• Alle atomare Formeln sind Formeln

• Für alle Formeln F und G sind (F ∧G) und (F ∨G) Formeln

• Für jede Formel F ist (¬F ) eine Formel


¬ heißt Negation, ∧ Konjunktion, ∨ Disjunktion. F ist Teilformel einer FormelG, falls F Teil von G ist.

Die Definition von Formeln ist eine induktive Definition: es werden zu-nächst die einfachsten Formeln definiert (die atomaren Formeln). Dann wird er-klärt, wie aus einfachen Formeln (schrittweise) kompliziertere Formeln aufgebautwerden können. Dieses Indunktionsprinzip wird nun auch zur Definition der Se-mantik der Aussagenlogik verwendet, wie auch später zur Definition von Syntaxund Semantik der Prädikatenlogik (erster Stufe). Dieses Prinzip kann aber auchzu Beweisen verwendet werden: Um zu beweisen, dass eine Behauptung B(F ) fürjede Formel F gilt, genügt es, folgende Schritte durchzuführen:

1. Man zeige, es gilt B(Ai) für jede atomare Formel Ai.

2. Man nehme an, dass B(F ) und B(G) für zwei (beliebige) Formeln gelte.

3. Man zeige, dass B(¬F ),B(F ∧G),B(F ∨G) gelten.

In der Datei formulae.pl ist die Syntax direkt umgesetzt. Nehmen wir alsBeispiel die Vorgabe: Für alle Formeln F und G sind (F∧G) und (F∨G) Formeln.Dies wird implementiert durch:

% Konjuktionwff(Formula1 & Formula2):- !,

wff(Formula1),wff(Formula2).

% Disjunktionwff(Formula1 v Formula2):- !,


1.3.2 Semantik der Aussagenlogik

Die Elemente von B = {0, 1} heißen Wahrheitswerte und stellen die einzig mögli-che Semantik dar, d.h. die für die Menschen inhaltliche Bedeutung interessiert inder Aussagenlogik nicht; hier geht es ausschließlich um den Wahrheitsgehalt einerAussage! Eine Belegung ist eine Funktion A und eine Interpretation/Bewertungist eine Funktion A mit

• A : D → B, wobei D Teilmenge der atomaren Formeln ist.

• A : E → B, wobei E ⊇ D Menge aller Formeln über D ist.

Dabei ist


• A eine Verbindung zur „Aussenwelt“, in der geklärt wird, ob eine atomareFormel, also eine elementare Aussage wahr oder falsch ist. Dies kann vonder Aussagenlogik nicht geleistet werden, da sie dazu die Semantik derAussagen im Sinne natürlicher Sprachen (und weiteres mehr) betrachtenmüsste.

• A eine Funktion innerhalb der Aussagenlogik ist, in der der Wahrheitsgehaltkomplexer aussagenlogischer Formeln bestimmt wird.

A und A sind wie folgt definiert:

1. Für jedes F ∈ D: A(F ) = A(F )

2.

A(F ∧G) =

{1 falls A(F ) = 1 und A(G) = 10 sonst

3.

A(F ∨G) =

{1 falls A(F ) = 1 oder A(G) = 10 sonst

4.

A(¬F ) =

{1 falls A(F ) = 00 sonst

„Praktisch“ wird zwischen der Belegung und der Bewertung kein Unterschiedgemacht.

Eine Belegung/Bewertung wird für eine Formel F als passend bezeichnet,wenn die Belegung für alle atomaren Formeln von F definiert ist. Ansonsten kannder Wahrheitsgehalt der Formel F nicht bestimmt werden!

A |= F := A(F ) = 1 heißt, F gilt unter der Belegung A bzw. A ist ein Modellfür F .

Eine Formel F ist erfüllbar, wenn es mindestens eine passende Belegungfür F gibt, die ein Modell für F ist. Eine Formel F ist falsifizierbar, wenn esmindestens eine passende Belegung für F gibt, die kein Modell für F ist. EineFormel F ist kontingent, wenn sie sowohl erfüllbar wie auch falsifizierbar ist.

F ist gültig (eine Tautologie) wenn jede zu F passende Belegung ein Modellfür F ist. F ist ungültig / unerfüllbar (ein Widerspruch / Kontradiktion)wenn jede zu F passende Belegung kein Modell für F ist.

Satz 1.2 Eine Formel F ist eine Tautologie genau dann, wenn ¬F unerfüllbarist.


F und G sind semantisch äquivalent, falls für alle Belegungen A gilt:A(F ) = A(G), d.h. wenn die Formel F ↔ G eine Tautologie ist! G ist z.B.eine Folgerung von F , wenn F → G eine Tautologie ist. Wenn von Mengenvon Formeln die Rede ist, also z.B. {F1, F2, F3, . . .}, aus denen etwas folgern solloder zu denen etwas semantisch äquivalent ist, dann wird deren konjunktive Ver-knüpfung verwendet, also hier im Beispiel F1 ∧ F2 ∧ . . .. Somit können diese hierangesprochenen Beziehungen zwischen Formeln auf eine Formel zurück geführtwerden, die eine Tautologie sein muß.

Die Definition von semantisch äquivalent macht besonders deutlich, dass dieSemantik hier ausschließlich durch die beiden Wahrheitswerte gebildet wird!

Für aussagenlogische Formeln F,G,H gelten die folgenden Äquivalenzen:

Idempotenz (F ∧ F ) ≡ F sowie (F ∨ F ) ≡ F

Kommutativität (F ∧G) ≡ (G ∧ F ) sowie (F ∨G) ≡ (G ∨ F )

Assoziativität ((F∧G)∧H) ≡ (F∧(G∧H)) sowie ((F∨G)∨H) ≡ (F∨(G∨H))

Absorption (F ∧ (F ∨G)) ≡ F sowie (F ∨ (F ∧G)) ≡ F

Distributivität (F ∧ (G ∨H)) ≡ ((F ∧G) ∨ (F ∧H)) sowie (F ∨ (G ∧H)) ≡((F ∨G) ∧ (F ∨H))

Doppelnegation ¬¬F ≡ F

de Morgan ¬(F ∧G) ≡ (¬F ∨ ¬G) sowie ¬(F ∨G) ≡ (¬F ∧ ¬G)

Tautologie Ist F eine Tautologie, so gilt (F ∨G) ≡ F sowie (F ∧G) ≡ G.

Unerfüllbarkeit Ist F unerfüllbar, so gilt (F ∨G) ≡ G sowie (F ∧G) ≡ F .

Zu beachten ist, dass die letzten beiden Äquivalenzen von „semantischer Natur“sind, wogegen alle anderen von „syntaktischer Natur“ sind. Natürlich müssen alledie Semantik erhalten. Um die letzten beiden Äquivalenzen anwenden zu können,muss aber neben der Syntax auch die Semantik (hier der Wahrheitsgehalt von F)betrachtet werden! Dies ist bei allen anderen Äquivalenzen nicht der Fall. Hiergenügt eine rein syntaktische Betrachtung der Formel!

Satz 1.3 (Ersetzungssatz) Sei F1 ≡ F2 und sei G1 eine Formel, die F1 alsTeilformel enthält, und sei G2 die Formel, die sich aus der Ersetzung von F1 mitF2 in G1 ergibt, dann gilt G1 ≡ G2

In Abhängigkeit der Fragestellung gibt es nun verschiedene Methoden, denWahrheitsgehalt einer Formel und damit deren Semantik „zu berechnen“. Nach-folgend seien einige gebräuchliche Methoden aufgeführt:

• Eine Formel und eine passende Belegung seien gegeben:


1. Die in diesem Abschnitt definierte Bewertungsfunktion A wird ver-wendet und A(F ) gemäß deren Definition berechnet.

2. Eine Wahrheitstafel wird verwendet und nur in genau der Zeile „aus-gefüllt“, die mit der vorgegebenen Belegung übereinstimmt.Wahrheitstafeln haben für jede aussagenlogische Variable der Formeleine Spalte, für die Formel F selbst und für eine geeignete Anzahl anTeilformeln der Formel F. „Geeignet“ heisst die Berechnung erleich-ternt.

• Eine Formel sei gegeben und es wird nach prinzipieller Erfüllbarkeit odernicht Erfüllbarkeit gefragt:

1. Eine Wahrheitstafel wird verwendet und vollständig „ausgefüllt“,d.h. alle mögliche Situationen werden explizit ausgerechnet. So kanndie Formel eindeutig als Widerspruch oder Tautologie eingestuft wer-den. Besonders gut ist sie, um Fragen zu klären, bei denen man kei-ne Tautologie oder keinen Widerspruch „erzeugen“ kann, sondern einekontingente Formel untersuchen muss.

2. Eine Äquivalente Umformung, d.h. eine Transformation mittelsden fundamentalen Äquivalenzen, wird verwendet, um Formeln für ei-ne weitere Verwendung/Berechnung zu „vereinfachen“ (im Sinne dieserweiteren Verwendung). Bei der Verwendung für Tautologien oder Wi-dersprüche muss solange transformiert werden, bis wahr bzw. falschübrig bleibt.

3. Kalküle sind geprüfte Beweisverfahren, um einen Widerspruch zu er-kennen. Sie eignen sich insbesondere bei der Analyse von Formeln aufTautologie oder Widerspruch.

– Semantische Tableaus: Idee ist hier, einen Baum zu erstellen, derin keinem Weg von Wurzel zu einem Blatt einen Widerspruchenthalten darf. Wege sind konjunktive Verknüpfungen, Verzwei-gungen sind disjunktive Verknüpfungen. Um den Baum möglichstklein zu halten, sollten ∨-Teilformeln möglichst spät in dem Baumexpandiert werden, um die Verzweigungsrate des Baums klein zuhalten. Der Baum wird gemäß induktivem Aufbau der Formel auf-gebaut.

– Die Resolution (vorgestellt im Nachfolgenden): Im Unterschied zuden semantischen Tableaus wird hier die Formel in eine Normal-form überführt (die quasi die Rolle des Baum’s hat) und dannnach einer bestimmten Regel - der Resolution - ausgewertet, bisein Widerspruch auftritt oder nicht. Dies korrespondiert mit derPrüfung, ob in einem Weg im Baum ein Widerspruch enthaltenist.


4. Verbales Argumentieren ist ein ungeprüftes Verfahren: wann sindwir bei welcher Argumentationsweise sicher ? Können wir diese Ar-gumentationsweise implementieren ? Diese Vorgehensweise ist also imAllgemeinen nicht gut geeignet, insbesondere ist sie definitiv für Neu-linge in dem Gebiet absolut ungeeignet, auch wenn gerade Neulingediese lieber verwenden, als eines der formalen (geprüften) Verfahren.

In der Datei modelCheckerAL.pl ist die Semantik direkt umgesetzt. Nehmen wirals Beispiel die Vorgabe:

A(F ∧G) =

{1 falls A(F ) = 1 und A(G) = 10 sonst

Dies wird implementiert durch:

% KonjuktionevaluateAsF(Formula1 & Formula2, AsBelegung, true):-

evaluateAsF(Formula1, AsBelegung, true),evaluateAsF(Formula2, AsBelegung, true), !.

% Bivalenz-Prinzip der zweiwertigen Logik:% Eine Formel ist unter einer Interpretation genau dann falsch,% wenn sie nicht wahr ist.evaluateAsF(F, B, false) :-

\+ evaluateAsF(F, B, true).

Die letzte Formel hier bearbeitet von allen Konstrukten den Fall, dass auf falsegeprüft wird und ersetzt hier im konkreten Fall die beiden Regeln:

evaluateAsF(Formula1 & _Formula2, AsBelegung, false):-evaluateAsF(Formula1, AsBelegung, false),!.

evaluateAsF(_Formula1 & Formula2, AsBelegung, false):-evaluateAsF(Formula2, AsBelegung, false),!.

In AsBelegung befindet sich eine passende Belegung.

1.3.3 Tableaukalkül der Aussagenlogik7 Die Anwendung semantischer Tableaus beruht auf der wichtigen Strategie,dass man die Konklusion einer Begründung (also den then-Teil eines if-then-Ausdrucks) negiert und dann prüft, ob das Ergebnis im Widerspruch (inkonsistentist) zu den Voraussetzungen steht. Die Idee dabei ist, nachzuprüfen, ob es für ei-ne vermutete Folgerung (Konklusion) möglich ist, den Wert falsch anzunehmen,

7Dieser Abschnitt ist im Wesentlichen [KJ00] entnommen.


wenn alle Voraussetzungen wahr sind. Wenn das nicht möglich ist, d.h. wenn dieKonklusion wahr sein muss, falls die Voraussetzungen wahr sind, sagt man, dieKonklusion ist durch die Voraussetzungen semantisch bedingt.

Im Grunde genommen ist ein Tableau eine Folge von Aussageformeln, dienach gewissen Regeln gebildet und üblicherweise in Form eines Baums dargestelltwerden. Dabei wird die konjuktive Erweiterung in dem Baum als auf einanderfolgende Äste dargestellt und die disjunktive Erweiterung in dem Baum alseine Verzweigung (Gabelung) von Ästen dargestellt. Ein Pfad durch den Baumstellt also eine konjunktive Verknüpfung aussagenlogischer Formeln dar.

Werfen wir zunächst einen Blick auf diese Regeln. Wir stellen sie in Tabellendar und verwenden jeweils als Spaltenüberschrift Konjunktiv und Disjunktiv, umdie jeweilige Erweiterung anzugeben. Zeichnet man den Baum nach, sind dieDisjunktiven alle als Verzweigung darzustellen, wogegen die Konjunktiven alleauf einander folgend darzustellen sind (also als Pfad).

Regel 1 : A ∧BWenn ein Tableau A ∧ B enthält, kann man es zu einem neuen Tableauerweitern, indem man bei dem Ast, der A ∧ B enthält, sowohl A als auchB hinzufügt. Dies lässt sich kurz folgendermaßen darstellen:

Nr. Muster Konjunktiv Disjunktiv1 A ∧B A B

Regel 2 : A ∨BWenn ein Tableau A∨B enthält, wird es zu einem neuen Tableau erweitert,indem man zwei neue Äste hinzufügt, wobei der eine A und der andere Benthält. Dies lässt sich kurz folgendermaßen darstellen:

Nr. Muster Konjunktiv Disjunktiv2 A ∨B A B

Die weiteren (und bisher genannten) Regeln werden in einer Tabelle zusam-mengefasst.

Nr. Muster Konjunktiv Disjunktiv1 A ∧B A B2 A ∨B A B3 ¬¬A A4 ¬(A ∧B) ¬A ¬B5 ¬(A ∨B) ¬A ¬B

Sofern weitere Symbole eingeführt wurden, lassen sich auch dazu Regeln for-mulieren. Dies erspart eine Transformation der Regeln in die Darstellung ihrerDefinition und ermöglicht somit eine direkte Anwendung des Tableaukalküls aufeine aussagenlogische Formel.


Nr. Muster Konjunktiv Disjunktiv6 A→ B ¬A B7 A↔ B ¬A ∨B ¬B ∨ A8 ¬(A→ B) A ¬B9 ¬(A↔ B) A ∧ ¬B ¬A ∧B

Regel 10 : Diese letzte und besonders wichtige Regel besagt, dass immer dann,wenn bei einem Ast eines Tableaus sowohl die logische Form A als auch ihreNegation ¬A erscheint, ein Widerspruch bei diesem Ast vorliegt. Man nenntihn (den Ast) dann (ab-)geschlossen, d.h. er wird nicht mehr erweitert.Das liegt daran, dass A und ¬A nicht gleichzeitig wahr sein können.

Wenn alle Äste eines semantischen Tableaus geschlossen sind, stehen die logi-schen Ausdrücke, aus denen das Tableau erstellt wurde, im Widerspruch zuein-ander, d.h. sie können nicht alle gleichzeitig wahr sein.

Bemerkung 1.1 Als Faustregel zur Anwendung der Regeln des Tableaukalkülswähle man immer zuerst die Regeln, die zu keiner Verzweigung führen, also dienur eine konjunktive Erweiterung besitzen, bevor man Regeln anwendet, die zuVerzweigungen führen, also die eine disjunktive Erweiterungen besitzen.

Die Bemerkung macht indirekt klar: Das Tableaukalkül ist nichtdeterministisch.Es ist nicht festgelegt, welche Formel, d.h. welcher Knoten bzw. mit welcher Regel,expandiert wird.

Definition 1.3 Ein Tableau-Beweis für die Formel A ist ein abgeschlossenesTableau zu ¬A. A ist genau dann ein Theorem des Tableaukalkuls, wenn A einenTableau-Beweis besitzt.

Im Wesentlichen ist die Tableau-Methode also ein direkter Versuch, Widersprüchein einer Menge logischer Ausdrücke aufzudecken, indem sie zueinander in Kon-flikt stehende Paare von Ausdrücken A und ¬A aufdeckt. Wenn alle Äste einesTableaus wegen der Existenz solcher sich widersprechender Paare abgeschlossensind, so ist damit nachgewiesen, dass sich die ursprünglichen Formeln an derWurzel (am Anfang) des Tableaus gegenseitig widersprechen. Wenn am Ende derTableau-Entwicklung nur ein Ast nicht abgeschlossen bleibt, so zeigt dies einenmöglichen Zustand an, bei dem die ursprünglichen Ausdrücke alle gleichzeitigwahr sein können und daher gegenseitig widerspruchsfrei sind.

Bei einem nicht abgeschlossenen Ast ist es einfach, Wahrheitswerte so zuzu-ordnen, dass die Ausdrücke alle wahr werden. Mit anderen Worten: Es ist einfach,ein Modell zu bilden: Man weise in jedem nicht abgeschlossenen Ast jeder ato-maren Aussage,d.h. A oder ¬A, als Ganzes den Wert „wahr“ zu.

Nachfolgend ein aussagenlogischer Tableauvervollständigungsalgorithmus.


Algorithmus 1.4 Sei F eine aussagenlogische Formel. Wir konstruieren einenbinären Baum (K;N).

1. Am Anfang sei K = {F}.

2. Wähle einen noch nicht markierten Knoten G, der weder ein Aussagensym-bol noch die Negation eines Aussagensymbols ist. Markiere G und wendeeine der folgenden fünf Tableauregeln an. Gibt es keinen solchen Knotenmehr, so heißt das Ergebnis ein vollständiges Tableau und wird ausge-geben.

3. Ist G von der Form G = ¬¬H, so erweitere am Ende eines jeden bei Gbeginnenden Pfads den Baum gemäß Regel 3. Fahre dann mit 2. fort.

4. Ist G von der Form G = H1∧H2, so erweitere am Ende eines jeden bei Gbeginnenden Pfads den Baum gemäß Regel 1. Fahre dann mit 2. fort.

5. Ist G von der Form G = H1∨H2, so erweitere am Ende eines jeden bei Gbeginnenden Pfads den Baum gemäß Regel 2. Fahre dann mit 2. fort.

6. Ist G von der Form G = ¬(H1 ∧ H2), so erweitere am Ende eines jedenbei G beginnenden Pfads den Baum gemäß Regel 4. Fahre dann mit 2. fort.

7. Ist G von der Form G = ¬(H1 ∨ H2), so erweitere am Ende eines jedenbei G beginnenden Pfads den Baum gemäß Regel 5. Fahre dann mit 2. fort.

Sei T = (K,N) ein Tableau.

• Ein Pfad in T heißt geschlossen, wenn er sowohl ein Aussagensymbol Aals auch seine Negation ¬A als Knoten enthält. In diesem Fall markierenwir das Blatt am Ende des Pfads mit ⊥.

• Das Tableau T heißt geschlossen (oder widersprüchlich), wenn seine ma-ximalen Pfade alle geschlossen sind. Ein Pfad heißt dabei maximal, wenner mit der Wurzel beginnt und mit einem Blatt endet.

• Das Tableau T heißt erfüllbar, wenn es einen maximalen Pfad in T gibt,so dass für die Formeln an den Knoten des Pfads ein gemeinsames Modellexistiert.

• Ein Pfad in T heißt vollständig, wenn alle Formeln an seinen Kantenabgearbeitet sind, d.h. wenn sie markiert sind oder Aussagensymbole odernegierte Aussagensymbole sind.

• Das Tableau T heißt vollständig, wenn jeder seiner maximalen Pfade voll-ständig oder geschlossen ist.


Der Algorithmus könnte nun so erweitert werden, dass er geschlossene Pfade nichtmehr expandiert.

Bemerkung 1.2 Man sollte nicht auf die Idee kommen, einen direkten Beweismit dem Tableaukalkül zu führen. Betrachtet man z.B. die Formel (A→ A)∨(B∧¬B), so sind nach Erstellung des Tableaus nicht alle Äste nicht geschlossen, d.h.es gibt mindestens einen geschlossenen Ast! Dagegen sind bei der Betrachtungvon ¬((A→ A) ∨ (B ∧ ¬B)) alle Äste geschlossen.

Ein Tableau kann also nur zwischen „erfüllbar“ (Erfüllbar oder Tautologie)und „unerfüllbar“ (Widerspruch) unterscheiden.

1.3.4 Resolution der Aussagenlogik

Ein Literal ist eine atomare Formel oder eine Negation einer atomaren Formel.Eine konjunktive Normalform (KNF) ist die Konjunktion von Disjunktionen vonLiteralen. Eine disjunktive Normalform (DNF) ist die Disjunktion von Konjunk-tionen von Literalen. Eine Negationsnormalform (NNF) ist eine Formel, bei derdie Negation nur noch direkt vor den atomaren Formeln steht, bzw. eine Formel,bei die Negation nur noch in Literalen vorkommt.

Mittels dem nachfolgenden Algorithmus kann eine KNF erzeugt werden. Dieverwendeten Regeln gehen dabei zunächst von den „Basissymbolen“ ¬,∧,∨ aus,d.h. ggf. sind andere Symbole zunächst durch ihre Definitionen zu ersetzen.

In den Schritten 1. bis 4. wird eine Negationsnormalform erzeugt. Dieser Teildes Algorithmus kann auch zur Erzeugung anderer Normalformen verwendet wer-den, etwa einer DNF.

Algorithmus 1.5 Gegeben sei eine Formel F. Führe die folgenden Schritte durch:

1. Ersetze in F jede Teilformel der Form ¬¬G durch G.

2. Ersetze in F jede Teilformel der Form ¬(G∧H) durch (¬G∨¬H). Entstehthierdurch eine Teilformel der Form ¬¬K, so wende Schritt 1. an.

3. Ersetze in F jede Teilformel ¬(G∨H) durch (¬G∧¬H). Entsteht hierdurcheine Teilformel der Form ¬¬K, so wende Schritt 1. an.

4. Wiederhole die Schritte 2. und 3. so oft wie möglich. Resultat ist eine NNF.

5. Ersetze in F jede Teilformel der Form (G∨(H∧I)) durch ((G∨H)∧(G∨I)).

6. Ersetze in F jede Teilformel der Form ((G∧H)∨I)) durch ((G∨I)∧(H∨I)).

7. Wiederhole die Schritte 5. und 6. so oft wie möglich.

Die resultierende Formel ist dann in KNF. Möchte man eine DNF erzeugen, sinddie Schritte 5. bis 7. durch folgende Anweisungen zu ersetzen:


1. Ersetze in F jede Teilformel der Form (G∧(H∨I)) durch ((G∧H)∨(G∧I)).

2. Ersetze in F jede Teilformel der Form ((G∨H)∧I)) durch ((G∧I)∨(H∧I)).

3. Wiederhole die Schritte (1.) und (2.) so oft wie möglich. Resultat ist einedisjunktive Normalform (DNF).

Eine Formel F kann auch in der Mengenschreibweise dargestellt werden.

F = (L1,1 ∨ . . . ∨ L1,n) ∧ (L2,1 ∨ . . . ∨ L2,n) ∧ . . . ∧ (Lm,1 ∨ . . . ∨ Lm,n)

kann geschrieben werden als

F = {{L1,1, . . . , L1,n}, {L2,1, . . . , L2,n}, . . . , {Lm,1, . . . , Lm,n}}

Diese Schreibweise verwenden wir hier nur für die Resolution! Ein Disjunktions-glied wird in dem Zusammenhang als Klausel bezeichnet.

Festlegung:

L =

{A falls L = ¬A¬A sonst

Sei K eine Klausel.

• Kommt in K ein positives und kein negatives Literal vor, d.h. ist K eineAussage, so heisst K eine Tatsachenklausel. Wahr → G; A:-. oder A.

• Kommt in K genau ein positives und mindestens ein negatives Literalvor, so heisst K eine Prozedurklausel oder Regel. (E ∧ F ) → G; A:-B1,B2,...,Br.

• Eine negative Klausel, also eine Klausel ohne positives Literal, heisst auchZielklausel oder Frageklausel. (E ∧ F )→?; ?- A1,A2,...,Ak.

• Eine nicht negative Klausel heisst eine Programmklausel oder eine defi-nite Klausel.

• Eine Menge von Klauseln heisst ein Logikprogramm oder ein Klausel-programm.

Programmlauf :(Tatsachenklausel∧Prozedurklausel)→ Frageklausel; Tat-sachenklausel ∧ Prozedurklausel sind wahr (sofern korrekt modelliert). Fra-ge: Lässt die Gültigkeit der Frageklausel sich aus ihnen ableiten?

Tautologie :(Tatsachenklausel ∧ Prozedurklausel) → Frageklausel ist Tau-tologie, wenn sich die Frageklausel ableiten lässt.

Widerspruch : ¬((Tatsachenklausel ∧ Prozedurklausel)→ Frageklausel) ≡Tatsachenklausel ∧ Prozedurklausel ∧ ¬Frageklausel ist Widerspruch,wenn sich die Frageklausel ableiten lässt.


Ein wichtiger Punkt ist die Beweisführung. Ein Schritt kann durch das Resolu-tionkalkül durchgeführt werden. Für ein so komplexes Verfahren wie ein Kalkül istdie Korrektheit des Kalküls wichtig: Erfüllbarkeit (oder Unerfüllbarkeit) musskorrekt entscheidbar sein (aber evtl. nicht für alle Formeln entscheidbar). Zudemspielt die Vollständigkeit eines Kalküls den zweiten wichtigen Punkt: Für jedesyntaktische richtige Formel kann die Erfüllbarkeit (oder Unerfüllbarkeit) ent-schieden werden (aber evtl. nicht korrekt!, d.h. alle erfüllbaren Formeln werdenals Erfüllbar klassifiziert, aber evtl. werden nicht erfüllbare Formeln auch als Er-füllbar klassifiziert). Für genügend komplexe Kalküle gelten die beiden Punktenicht. Das Resolutionskakül der Ausagenlogik beweist die Unerfüllbarkeit undist korrekt und vollständig. Bei nicht so komplexen Algorithmen wird die Kor-rektheit und Vollständigkeit stillschweigend erfüllt. Bei komplexen Algorithmenspricht man diese Punkte explizit an, da man meist auf eines von beiden oder garbeide verzichten muss.

Seien K1, K2, R Klauseln (also Disjunktionsglieder). R wird als Resolventevon K1, K2 bezeichnet, falls: Es gibt ein Literal L ∈ K1 mit L ∈ K2, so dassR = (K1 \ {L}) ∪ (K2 \ {L}).

Satz 1.4 Wenn F in KNF, K1, K2 ∈ F , R Resolvente von K1, K2. Dann giltF ≡ F ∪ {R}.

Bezeichnung:

• Res1(F ) = F ∪ {R|R ist Resolvente zweier Klauseln von F}.

• Resn(F ) = Res1(Resn−1(F )) mit Res0(F ) = F .

• Res∞(F ) =∪

n Resn(F ), wobei |Res∞(F )| <∞.

Algorithmus 1.6 Gegeben sei eine aussagenlogische Formel F in KNF.

1. Bilde die Klauselmenge K(F ) (Menge der Disjunktionsglieder von F).

2. Für n = 1, 2, 3, . . . berechne Resn(K(F )) solange, bis gilt:

• ∅ ∈ Resn(K(F )) oder

• Resn(K(F )) = Resn−1(K(F )), also, bis Res∞(F ) bestimmt wurde.

3. Im ersten Fall gib „F ist unerfüllbar“ aus,

4. im zweiten Fall gib „F ist erfüllbar“ aus und

5. stoppe.


Beispiel 1.13 Die Resolution kann z.B. angewendet werden, um Regeln zu „ver-arbeiten“. Gegeben seien die beiden Regeln A→ B ∧B → C, die wie folgt in dieMengendarstellung transformiert werden können:

A→ B ∧B → C ≡ (¬A ∨B) ∧ (¬B ∨ C) ≡ {{¬A,B}, {¬B,C}}

Hier kann nun die Resolution angewendet werden mittels B,¬B und man erhältdie Resolvente

{¬A,C} ≡ (¬A ∨ C) ≡ A→ C

Dies kann man in dem Sinne als Anwendung der Regel B → C auf die RegelA→ B sehen oder die Herleitung der transitiven Hülle von →.

Wir wollen uns auch noch die einfachste Schlußfolgerung anschauen, den Mo-dus Ponens: Wenn eine Regel A → B gegeben ist und A beobachtet wird, d.h. Agilt, dann kann gefolgert werden (Schluß), dass B gilt. Also

A→ B ∧ A ≡ (¬A ∨B) ∧ A ≡ {{¬A,B}, {A}}

Hier kann nun die Resolution angewendet werden mittels ¬A,A und man erhältdie Resolvente

{B} ≡ B

Die Resolution führt also den einfachsten logischen Schluß durch. Implementiertman die Resolution (wie in Prolog für die Hornlogik, realisiert), so hat man denComputer in die Lage versetzt, logische Schlüsse zu ziehen!

Beispiel 1.14 Gegeben seien folgende Aussagen:

1. In einer Firma kann Team 1 die Projekte A und B vollenden, wenn dieStatistik C vorliegt.

2. Team 2 kann Projekt D vollenden, wenn Projekt A fertig ist und die StatistikE vorliegt.

3. Team 3 kann Projekt F fertig stellen, wenn die Projekte B und D abge-schlossen sind.

Frage: Kann Projekt F fertig gestellt werden, wenn die Statistiken C und Evorliegen ?

Modellierung:

1. Zunächst die aussagenlogischen Variablen:A = „Projekt A kann vollendet werden.“;B = „Projekt B kann vollendet werden.“;C = „Statistik C liegt vor.“;D = „Projekt D kann vollendet werden.“;E = „Statistik E liegt vor.“;F = „Projekt F kann vollendet werden.“


2. nun die Modellierung der Sätze:F1 = (C → A);F2 = (C → B);F3 = ((A ∧ E)→ D);F4 = ((B ∧D)→ F ) undFgesamt = F1 ∧ F2 ∧ F3 ∧ F4.

3. Transformation in eine KNF:

Fgesamt = F1∧F2∧F3∧F4 = (C → A)∧(C → B)∧((A∧E)→ D)∧((B∧D)→ F )

= (¬C ∨ A) ∧ (¬C ∨B) ∧ (¬(A ∧ E) ∨D) ∧ (¬(B ∧D) ∨ F )

= (¬C ∨ A) ∧ (¬C ∨B) ∧ (¬A ∨ ¬E ∨D) ∧ (¬B ∨ ¬D ∨ F )

Fgesamt ist unser (korrektes) Programm.

4. Die Frage (Programmaufrufparameter) wird als Aussage modelliert:Fanfrage = ((C ∧ E)→ F );ihre Negation: F¬anfrage = ¬((C ∧ E)→ F ).

Transformation in eine KNF:

F¬anfrage = ¬((C ∧ E)→ F ) = ¬(¬(C ∧ E) ∨ F ) = (C ∧ E ∧ ¬F )

5. Zu prüfen ist die Formel (konkreter Programmaufruf):Fanwendung = Fgesamt ∧ F¬anfrage= (¬C ∨A) ∧ (¬C ∨B) ∧ (¬A ∨ ¬E ∨D) ∧ (¬B ∨ ¬D ∨ F ) ∧C ∧E ∧ ¬F

Nun die Beweisführung:

1. Transformation in die Mengenschreibweise:{{(¬C,A}1, {¬C,B}2, {¬A,¬E,D}3, {¬B,¬D,F}4, {C}5, {E}6, {¬F}7}Resolvieren: K1 mit K5 mit L = C ergibt R1 = {A}K2 mit K5 mit L = C ergibt R2 = {B}K3 mit K6 mit L = E ergibt R3 = {¬A,D}K4 mit K7 mit L = F ergibt R4 = {¬B,¬D}R1 mit R3 mit L = A ergibt R5 = {D}R2 mit R4 mit L = B ergibt R6 = {¬D}R5 mit R6 mit L = D ergibt R7 = {} = ∅.Die Resolution hat einen Widerspruch erkannt. Unter der Voraussetzung,dass das Programm Widerspruchsfrei ist, muss die negierte Anfrage denWiderspruch erzeugt haben, daher gilt die Anfrage, d.h. ((C ∧E)→ F ) istwahr.

Widerspruchsfreiheit des Programms:


1. {{(¬C,A}1, {¬C,B}2, {¬A,¬E,D}3, {¬B,¬D,F}4}

2. Resolvieren:K1 mit K3 mit L = A ergibt R1 = {¬C,¬E,D}K2 mit K4 mit L = B ergibt R2 = {¬C,¬D,F}K3 mit K4 mit L = D ergibt R3 = {¬A,¬E, ?B,F}K1 mit R3 mit L = A ergibt R4 = {¬C,¬E,¬B,F}K2 mit R3 mit L = B ergibt R5 = {¬A,¬C,¬E,F}K1 mit R5 mit L = A ergibt R6 = {¬C,¬E,F}K2 mit R4 mit L = B ergibt R6 = {¬C,¬E,F}Das Programm ist Widerspruchsfrei. Durch weitere Analyse kann gezeigtwerden: Das Programm ist keine Tautologie, aber erfüllbar.

Als Prolog-Programm:

1. F1 = (C → A);a :- c.F2 = (C → B);b :- c.F3 = ((A ∧ E)→ D);d :- a,e.F4 = ((B ∧D)→ F ) f :- b,d. undFanfrage = ((C ∧ E)→ F );c. e. ?- f.

2. Die Anfrage wird hier durch Fakten im Programm umgesetzt (die Voraus-setzung) und durch eine Anfrage an das System (die Schlussfolgerung derImplikation).

Hier der Ablauf des Prolog-Programms als Resolution. Die Arbeitsweise vonProlog gibt vor, welche Resolutionen durchgeführt werden.{{(a,¬c}1, {b,¬c}2, {d,¬a,¬e}3, {f,¬b,¬d}4, {c}5, {e}6, {¬f}7}Resolvieren: K7 mit K4 mit L = f ergibt R1 = {¬b,¬d}R1 mit K2 mit L = b ergibt R2 = {¬c,¬d}R2 mit K1 mit L = c ergibt R3 = {¬d}R3 mit K3 mit L = d ergibt R4 = {¬a,¬e}R4 mit K1 mit L = a ergibt R5 = {¬c,¬e}R5 mit K5 mit L = c ergibt R6 = {¬e}R6 mit K6 mit L = e ergibt R7 = {} = ∅Prolog verwendet eine Reihenfolge (links nach rechts in der Menge) undbetreibt eine Tiefensuche: mit neuster Resolvente weiter arbeiten.

3. a :- c.b :- c.d :- a,e.f :- b,d.c.e.


[trace] 3 ?- f.Call: (6) f ? Creep K7 mit K4 mit L=f ergibt R1Call: (7) b ? Creep R1 mit K2 mit L=b ergibt R2Call: (8) c ? Creep R2 mit K1 mit L=c ergibt R3Exit: (8) c ? creepExit: (7) b ? creepCall: (7) d ? Creep R3 mit K3 mit L=d ergibt R4Call: (8) a ? Creep R4 mit K1 mit L=a ergibt R5Call: (9) c ? Creep R5 mit K5 mit L=c ergibt R6Exit: (9) c ? creepExit: (8) a ? creepCall: (8) e ? Creep R6 mit K6 mit L=e ergibt R7Exit: (8) e ? creepExit: (7) d ? creepExit: (6) f ? creep

true

Bei der Modellierung sollte man sich möglichst nah am Text halten, statt schonvor der Formalisierung den Text verbal zu transformieren oder ggf. zu interpre-tieren. Gerade bei Neulingen führt dies mit hoher Wahrscheinlichkeit zu Fehlern.Man beachte zudem:

Schwache Kopplung : Implikation (A → B). Keine Festlegung der Wahr-heitswerte von A und B, nur Festlegung der Abhängigkeit.

Äquivalenz (A ↔ B). Keine Festlegung der Wahrheitswerte von A undB, nur Festlegung der Abhängigkeit.

Schwache Kopplung : Oder (A ∨ B). Festlegung der Wahrheitswerte von Aund B: einer muss wahr sein.

Und (A ∧B). Festlegung der Wahrheitswerte von A und B: beide müssenwahr sein.

Eine allgemeine Strategie für die handschriftliche Resolution ist (z.B. bei Mo-dellierungsaufgabe):

1. Starte mit den Klauseln, die aus der Anfrage resultieren (im Beispiel K5,K6, K7)

2. Versuche Resolventen zu erzeugen, die „kleiner werden“

3. Versuche 1-Elementige Resolventen zu erzeugen


1.3.5 Tableau- und Resolutionskalkül

In diesem Abschnitt werden einige Gemeinsamkeiten und Unterschiede der beidenvorgestellten Verfahren besprochen.

Beide Verfahren können eine gegebene Formel F in zwei Klassen einordnen:

1. Die Klasse der widersprüchlichen Formeln, im Folgenden mit ⊖ bezeichnet.

2. Die Klasse der erfüllbaren Formeln, im Folgenden mit ⊕ bezeichnet.

Um eine eindeutige Zuordnung für alle Klassen (Widerspruch, Falsifizierbar, Kon-tingent, Erfüllbar, Tautologie) vornehmen zu können, muss man zwei Beweiseführen. In der nachfolgenden Tabelle wird dies verdeutlicht. Mit 0 oder 1 wirdangegeben, in welche Klasse das Verfahren (Tableau oder Resolution) die FormelF bzw. ¬ F zugeordnet hat. Rechts ist die zugehörige Interpretation gegeben.

direkter Beweis indirekter Beweismit F mit ¬ F⊖ ⊕ ⊖ ⊕ F ist1 0 0 1 Widerspruch0 1 1 0 Tautologie0 1 0 1 Kontingent

Zu beachten ist, dass eine falsifizierbare Formel sowohl ein Widerspruch wie auchein Kontingent sein kann und dass eine erfüllbare Formel sowohl eine Tautologiewie auch ein Kontingent sein kann.

Welche Fragestellungen werden nun behandelt ?

1. Generelle Fragestellung: Kann man, und wenn ja, wie, effizient nachweisen,dass eine Formel eine Tautologie ist. Hieraus resultieren z.B. das Tableau-und das Resolutionskalkül.

2. Spezielle Fragestellung:

(a) Theoretische Frage: Unter der Annahme, also Vermutung bestimmterWahrheitswerte ist zu prüfen, wann jetzt (mit diesen Annahmen) eineFormel Tautologie ist.

(b) Praktische Fragestellung: die „Aussenwelt“ legt alle Wahrheitswerte fürAussagen fest, indem sie die Inhalte der Aussagen betrachtet. Es istzu prüfen, ob jetzt (mit diesen Festlegungen aller atomaren Formeln)die Formel eine Tautologie ist.

Warum wird nach einer Tautologie gefragt ? Für eine Formel ist man an der Wahr-heit interessiert, also wann ist sie gültig, z.B. in welchem Modell. Man möchtealso wissen, wann zusammengesetzte Aussagen wahr sind. Seltener möchte manwissen, wann sie nicht wahr sind.


Soll nun einer der vorgestellten Kalküle verwendet werden, so muss ein indi-rekter Beweis durchgeführt werden, weil nur dieser die Tautologie einer Formeleindeutig erkennt.

Im Fall (1.) wird die gesamte Formel negiert. Z.B. A∨¬A würde als ¬(A∨¬A)an das Verfahren übergeben werden.

Im Fall (2.a) wird nur die Behauptung negiert. Die Annahmen bleiben so, wiesie sind. Z.B. Annahme ist A und A→ B gelten. Behauptung könnte sein: B gilt.An die Verfahren wäre dann die Formel (A ∧ (A → B)) ∧ (¬B) zu übergeben.Dies kommt aus der Fragestellung, ob (A ∧ (A → B)) → (¬B) ein Widerspruchist. Prolog macht dies indirekt, indem dort die Annahmen in der Programmdateistehen und die Behauptungen als Anfragen dem System übergeben werden. Diesewerden dann durch das System automatisch negiert.

Welches Verfahren ist nun effizienter ? Warum verwendet Prolog die Reso-lution und nicht das Tableau ? Bei der Resolution sucht man ganz gezielt nachder leeren Klausel. Ist diese gefunden, kann sofort abgebrochen werden, da dieeingegebene Formel eindeutig widersprüchlich (im Original also eine Tautologie)ist. Das Tableau muss jedoch expandiert werden, bis alle Pfade des Baums ge-schlossen sind bzw. keine Expansion mehr möglich ist.

1.3.6 Hornlogik

Eine Hornformel ist eine Formel in konjunktiver Normalform, wobei jedes Dis-junktionsglied höchstens ein positives Literal hat. Man beachte dazu (F → G) ≡(¬F ∨G).

Prolog stellt quasi eine 1:1-Implementierung der Hornlogik für Prädikatenlogikdar. Ähnliches ist z.B. bei einer der ältesten noch „aktiven Programmiersprachen“LisP der Fall: dies ist quasi eine 1:1-Implementierung des Lambda-Kalküls ausder Funktionentheorie.

Aber warum wird nicht mit einer Einschränkung der Prädikatenlogik gearbei-tet ? Die Antwort ist die Berechenbarkeit. Die Hornlogik bewirkt eine Eindeutig-keit bei einer, wie in Prolog verwendeten, Rückwärtsverkettung (Ziel orientierteInferenz). Wir betrachten nun verschiedene Fälle bzgl. der Anzahl an negativenund positiven Literalen bzw. der Gestalt der Implikationen:

• (F ∧G)→ H ≡ ¬(F ∧G) ∨H ≡ (¬F ∨ ¬G ∨H)h :- f,g.

• (F ∨G)→ H ≡ ¬(F ∨G) ∨H ≡ (¬F ∧ ¬G) ∨H ≡ (¬F ∨H) ∧ (¬G ∨H)h :- (f;g). oder h :- f. h :- g.

• F → (G ∧H) ≡ ¬F ∨ (G ∧H) ≡ (¬F ∨G) ∧ (¬F ∨H)f :- g. f :- h.


• F → (G∨H) ≡ ¬F ∨ (G∨H): Lässt sich nicht eindeutig auflösen, da dreiFälle möglich sind! Für eine weitere Berechnung müssen alle Fälle weiterbetrachtet werden.

• ¬F ≡ falsch ∨ ¬F ≡ wahr → ¬F ≡ F → falsch. In der Hornlogik wirddie Close World Assumption (CWA) verwendet, um auf der einen SeiteEindeutigkeit zu fordern und auf der anderen Seite durch diese Regelungauch in der Berechnung einfach zu bleiben. Hier müssten z.B. in obigem odernachfolgendem Fall mit drei möglichen Fällen weiter gerechnet werden!Programm zu ¬F : leeres Programm oder f :- fail.Anfrage zu ¬F : ?- f.

• ¬F ∨ ¬G ≡ wahr → (¬F ∨ ¬G) ≡ (F ∧G)→ falschProgramm zu ¬F ∨ ¬G: Lässt sich nicht eindeutig auflösen, da drei Fällemöglich sind!Anfrage zu ¬F ∨ ¬G: ?- f,g.

Näheres kann der Leser in [KK06] finden.

1.4 Prädikatenlogik 1-ter Stufe

Die Prädikatenlogik der ersten Stufe ist eine Erweiterung der Aussagenlogik.Was hinzu kommt sind Quantoren (für alle ∀, existiert ∃) für Funktionssymbole,Funktions- und Prädikatsymbole.

Funktionssymbole PrädikatssymboleAussagenlogik - 0-stellige

Prädikatenlogik n-stellige n-stelligeerster Stufe Variablen

Prädikatenlogik n-stellige n-stelligezweiter Stufe Variablen Variablen

Durch diese neuen Konzepte sind nun Sachverhalte beschreibbar, die im Rah-men der Aussagenlogik nicht formuliert werden konnten. In der Aussagenlogikwar es z.B. nicht möglich auszudrücken, dass gewisse Objekte in gewissen Bezie-hungen stehen; dass eine Eigenschaft für alle Objekte gilt, oder dass ein Objektmit einer gewissen Eigenschaft existiert. Die sprachlichen Symbole (Syntax derPrädikatenlogik) haben dabei für sich genommen noch keine Bedeutung, sie ge-winnen sie erst durch die semantische Zuordnung zu den konkreten Relationenund Funktionen des betrachteten Bereichs. Zu beachten ist aber, dass die Prädi-katenlogik reale Sachverhalte meist nur partiell repräsentiert bzw. repräsentierenkann; ihre Semantik ist gegenüber etwa einer natürlichsprachlichen Ausdrucks-weise stark verarmt. Nun wird dieser Mangel aber wenigstens teilweise durch

1.4. PRÄDIKATENLOGIK 1-TER STUFE 61

einen großen Zuwachs an Präzision aufgewogen. Letztendlich erweist sie sich je-doch vornehmlich als die Logik der vollständigen und statischen Informationenund stellt dennoch das Zentrum vieler anderer logischer Ansätze dar.

Bzgl. den Erweiterungen sei darauf hingewiesen, das die Prädikatenlogik vomBerechnungskern der Aussagenlogik entspricht. Die Berechnung bzw. Auswertungder Funktionen etc. erfolgt in der „Aussenwelt“, wie wir es bei der Aussagenlogikschon gesehen haben.

Im Kern werden in der Prädikatenlogik drei Fragen gestellt:

1. Was ist Wahrheit ?

2. Was ist ein Beweis ?

3. Wie findet man einen Beweis ?

Gerade letzte Frage kam erst mit dem Einzug der Computer stärker auf. Hierwerden wir die der logischen Programmiersprache Prolog zugrunde liegende Logikkennenlernen.

In Prolog wird ein Interpreter für die Prädikatenlogik zur Verfügung gestellt,der aus folgenden vier Dateien besteht:

main.pl Ist das Hauptmodul mit zwei Prädikaten zum Testen: test/2 als Inter-preteroberfläche zum Testen vorgegeben Beispielen bei gegebenem Modelloder test_F/2 zum Testen von Formeln bei gegebenem Modell.

examples.pl Spezifikation der Aussagensymbole, Relationen, Konstanten, Funk-tionen, Universen (domain) und Modellen (interpretation) sowie einigerFormelbeispiele.

formulae.pl syntaktische Beschreibung: hier wird die Wohlgeformtheit von For-meln geprüft. Zudem gibt es Prolog-Prädikate, die syntaktische Informatio-nen liefern, etwa freieVariablen_F/2.

modelChecker.pl Ein prädikatenlogischer Modell-Prüfer: hier wird die Semantikbeschrieben. Zudem gibt es Prolog-Prädikate, die semantisch interessanteAspekte prüfen, etwa satisfy/3.

Zu Beginn der Dateien findet man Anweisungen, z.B. :- op(800,yfx,user:(&)).% conjunction, die dazu dienen, Operatoren für den prädikatenlogischen Inter-preter einzuführen. Das liegt daran, dass viele für den Interpreter notwendigeAufgaben direkt durch Prolog durchgeführt werden. Das Paket ist bzgl. der Co-dierung eine Erweiterung des Paketes aus der Aussagenlogik. Dies soll verdeutli-chen, welche Unterschiede bzw. Gemeinsamkeiten bestehen.

In den nachfolgenden Abschnitten wird nun auf Teile dieses Paketes verwie-sen. Dies soll helfen, praktisch in SWI-Prolog die Prädikatenlogik bearbeiten zukönnen, z.B. durch Erweiterungen im Interpreter oder einfach nur durch Arbeitenmit Formeln.


1.4.1 Syntax der Prädikatenlogik

Der Definition von (prädikatenlogischen) Formeln wird die Definition von Termenvorangestellt, da sie Bestandteile der Formeln sind.

Variablen xi mit i ∈ N.

Prädikatssymbole PKi mit i ∈ N, K ∈ N die Stelligkeit.

Funktionssymbole fKi mit i ∈ N, K ∈ N die Stelligkeit.

Logiksymbole ∧,∨,¬,∀, ∃,→,↔ und zur Verdeutlichung von Strukturen dieKlammern (,),[,],{, }

Terme Die elementaren sprachlichen Ausdrücke

1. Jede Variable ist ein Term

2. Sei fKj ein Funktionssymbol und t1, . . . , tK Terme. Dann ist fK

j (t1, . . . , tK)ein Term.f 0i ist eine Konstante und auch ein Term!

Formeln Die komplexen sprachlichen Ausdrücke

1. Sei PKj ein Prädikatssymbol und t1, . . . , tK Terme. Dann ist PK

j (t1, . . . , tK)eine Formel.P 0i ist eine Konstante und auch eine Formel!

2. Sei F eine Formel. Dann ist auch (¬F ) eine Formel

3. Sei F,G zwei Formeln. Dann sind auch (F ∧G) und (F ∨G) Formeln

4. Sei F eine Formel und xj eine Variable. Dann sind auch (∀xjF ) und(∃xjF ) Formeln

Die Formeln, die nur nach Punkt 1 aufgebaut sind, werden auch atomare Formelngenannt.

Definition 1.4 Sei xj eine Variable, die in der Formel F vorkommt. Dann heißtxj gebunden in G, falls F eine Teilformel enthält mit der Gestalt (∀xjG) oder(∃xjG). Sonst heißt xj frei.

Eine prädikatenlogische Formel F heißt eine geschlossene Formel, oder eineprädikatenlogische Aussage, falls keine Variable in F frei vorkommt.

Definition 1.5 Sei F Formel, x eine Variable, t ein Term. Dann ist die Substi-tution F[x|t] definiert durch die Formel, die entsteht, wenn jedes freie Vorkommenvon x in F durch t ersetzt (substituiert) wird.

Sub = [x|t1], [y|t2], dann wird zuerst x durch t1 ersetzt und dann y durch t2.


Für die Resolution wird eine Normalform benötigt8. Dazu wird zu einerFormel F

• die (semantisch äquivalente) bereinigte Pränexformel erstellt. Sollte eineVariable bei unterschiedlichen Quantoren oder gebunden und frei vorkom-men, so wird sie für den jeweiligen Fall umbenannt. Gemäß syntaktischerStruktur (Negation kehrt die Quantoren um!) werden die Quantoren vor dieFormel „geschoben“. Die (erfüllbarkeitsäquivalente) geschlossene berei-nigte Pränexformel (GBPF) entsteht, indem alle freien Variablen durcheinen Existensquantor (ganz links in der Formel) gebunden werden. Dabeizu beachten ist, dass Existensquantoren, die in der Formel rechts von einemAllquantor stehen, ggf. nach der Transformation links von diesem Quantorstehen sollten, um keine nicht vorhandenen Abhängigkeiten zu erzeugen.Beispiel: (∀x : P (X))∧ (∃y : Q(y)) würde in ∃y : (∀x : (P (X)∧Q(y))) bes-ser transformiert werden. ∀x : (∃y : (P (X)∧Q(y))) würde eine irritierendelogische Aussage erstellen!

• die (semantisch äquivalente) Skolemform erstellt. Sollte die bereinigtePränexformel von F Existenzquantoren beinhalten, so werden diese (vonlinks nach rechts) entfernt und die zugehörige Variable durch einen Funkti-onsaufruf über alle links von diesem Existenzquantor stehenden Variablen(von Allquantoren) substituiert.

Bemerkung 1.3 ∀x : ∃y : P (x, y) heisst: für alle x finde ich jeweils ein passen-des y, so dass P (x, y) erfüllt ist.∃y : ∀x : P (x, y) heisst: ich finde ein passendes y, so dass für alle x P (x, y)

erfüllt ist.

Beispiel 1.15 (Aus [KK06])Gegeben sei die Formel

F = Q(x) ∨ (∀z : P (x, g(z))) ∨ (∃x : (∀y : (P (f(x), y) ∧Q(a))))

Die bereinigte Pränexform von F (siehe den Algorithmus in [KK06]) ist:

F ≡ ∃x1 : ∀y : ∀z : [Q(x0) ∨ P (x0, g(z)) ∨ (P (f(x1), y) ∧Q(a))]

Dabei wurde x als freie Variable in x0 und x als gebundene Variable in x1 umbe-nannt.

Die daraus resultierende Skolemform von F (siehe den Algorithmus in [KK06])ist:

F ≡ ∀y : ∀z : [Q(x0) ∨ P (x0, g(z)) ∨ (P (f(h()), y) ∧Q(a))]

Dabei wurde die Existenz-gebundene Variable x1 durch h() substituiert.8Siehe hierzu die ausführliche Beschreibung in [KK06]


Wir nehmen nun die Formel und strukturieren sie etwas um (auf Klammernachten!):

F ′ = Q(x) ∨ (∀z : P (x, g(z)) ∨ (∃x : (∀y : (P (f(x), y) ∧Q(a)))))

Die bereinigte Pränexform von F (siehe den Algorithmus in [KK06]) ist:

F ′ ≡ ∀z : ∃x1 : ∀y : [Q(x0) ∨ P (x0, g(z)) ∨ (P (f(x1), y) ∧Q(a))]

Dabei wurde x als freie Variable in x0 und x als gebundene Variable in x1 umbe-nannt.

Die daraus resultierende Skolemform von F ′ (siehe den Algorithmus in [KK06])ist:

F ′ ≡ ∀z : ∀y : [Q(x0) ∨ P (x0, g(z)) ∨ (P (f(h(z)), y) ∧Q(a))]

Dabei wurde die Existenz-gebundene Variable x1 durch h(z) substituiert.Gegeben sei (in bereinigter Pränexform) die Formel

G = ∃x : ∀y : ∃z : ∀w : ((¬P (x, y) ∧ ¬Q(y, f(z))) ∨ P (g(x,w), x))

Die daraus resultierende Skolemform von G (siehe den Algorithmus in [KK06])ist:

G ≡ ∀y : ∀w : ((¬P (h1(), y) ∧ ¬Q(y, f(h2(y)))) ∨ P (g(h1(), w), h1()))

Dabei wurden die Existenz-gebundenen Variablen y durch die nullstellige Funktionbzw. Konstante h1() und z durch die Funktion h2(y) substituiert.

In der Datei formulae.pl ist die Syntax direkt umgesetzt. Nehmen wir alsBeispiel die Vorgabe: Sei F,G zwei Formeln. Dann sind auch (F ∧G) und (F ∨G)Formeln. Dies wird implementiert durch:

% Konjuktionwff(Formula1 & Formula2):- !,


% Disjunktionwff(Formula1 v Formula2):- !,


Nehmen wir folgende Vorgabe als Übergang zu den Termen: Sei PKj ein Prädi-

katssymbol und t1, . . . , tK Terme. Dann ist PKj (t1, . . . , tK) eine Formel.


wff(Formula):-Formula =..[Pred | ArgList],relation(Pred, Arity),length(ArgList, Arity), !,wfts(ArgList).

Nehmen wir folgende Vorgabe für Terme: Sei fKj ein Funktionssymbol und t1, . . . , tK

Terme. Dann ist fKj (t1, . . . , tK) ein Term.

wft(T):- !,\+var(T),T =..[Funk | ArgList],function(Funk, Arity),length(ArgList, Arity),wfts(ArgList).

1.4.2 Semantik der Prädikatenlogik

Die Semantik wird beschrieben durch die Struktur A := (UA, IA), wobei UA einebeliebige aber nicht leere Menge ist, die Grundmenge von A bzw. das Univer-sum, der Individuenbereich . . . und IA eine Abbildung IA : {PK

i , fLj , xr|i, j, r ∈

N;K,L ∈ N0} → UA, die den syntaktischen Symbolen gewissen, adäquaten Ele-menten des Universums zuordnet.

Schreibweise: Statt IA(PKj ) = PK

jA, IA(fK

j ) = fKj

A und IA(xj) = xjA.

Sei F eine Formel und A := (UA, IA) eine Semantik, dann heißt A passend,wenn IA für alle in F vorkommenden Prädikatssymbole, Funktionssymbole undfreien Variablen definiert ist.

Die Interpretation einer Formel wird nun (im Sinne einer komposenationalenSemantik) am Aufbau einer Formel orientiert.

Gegeben sei ein Term t:

1. t ist Variable (atomar): A(t) := xA

2. t ist von der Form fK(t1, . . . , tK): A(t) := fAK(A(t1), . . . ,A(tK))

Gegeben sei eine Formel F :

1. F ist von der Form PK(t1, . . . , tK) (atomar):

A(F ) :=

{1 falls (A(t1), . . . ,A(tK)) ∈ PKA

0 sonst

2. F ist von der Form (¬G):

A(F ) :=

{1 falls A(G) = 00 sonst


3. F ist von der Form (G1 ∧G2) oder (G1 ∨G2)

A(F ) :=

{1 falls A(G1) = 1 und/oder A(G2) = 10 sonst

4. F ist von der Form (∀xG) oder (∃xG)

A(F ) :=

{1 falls für alle d ∈ UA gilt A[x|d](G) = 10 sonst

A(F ) :=

{1 falls es ein d ∈ UA gibt, mit A[x|d](G) = 10 sonst

Bemerkung 1.4 Wenn alle Prädikatssymbole nullstellig sind, haben wir wiederdie Aussagenlogik!

Satz 1.5 (Church) Das Gültigkeitsproblem der Prädiaktenlogik ist unentscheid-bar!

Seien F,G,H prädikatenlogische Formeln, wobei H nicht x und F nicht yenthält, dann gelten die fundamentalen Äquivalenzen der Aussagenlogik und esgilt desweiteren:

• ¬(∀x : F ) ≡ ∃x : ¬F und ¬(∃x : F ) ≡ ∀x : ¬F

• (∀x : F ) ∧ (∀x : G) ≡ ∀x : (F ∧G) und (∃x : F ) ∨ (∃x : G) ≡ ∃x : (F ∨G)

• (∀x : F ) ∨ (∀x : G) ≡ ∀x : (F ∨ G) gilt nicht, da aus ∀x : (F ∨ G) nichtfolgt, dass (∀x : F ) ∨ (∀x : G) gilt.

(∃x : F ) ∧ (∃x : G) ≡ ∃x : (F ∧ G) gilt nicht, da aus (∃x : F ) ∧ (∃x : G)nicht folgt, dass ∃x : (F ∧G) gilt.

• ∀x : ∀y : F ≡ ∀y : ∀x : F und ∃x : ∃y : F ≡ ∃y : ∃x : F

• (∀x : F )∧H ≡ ∀x : (F ∧H), (∃x : F )∧H ≡ ∃x : (F ∧H), (∀x : F )∨H ≡∀x : (F ∨H) und (∃x : F ) ∨H ≡ ∃x : (F ∨H)

• (∀x : F ) ∧ (∃y : H) ≡ ∃y : ∀x : (F ∧ H) ≡ ∀x : ∃y : (F ∧ H) und(∀x : F ) ∨ (∃y : H) ≡ ∃y : ∀x : (F ∨H) ≡ ∀x : ∃y : (F ∨H)

In der Datei modelChecker.pl ist die Semantik direkt umgesetzt. Nehmenwir als Beispiel die Vorgabe:

A(G1 ∧G2) :=

{1 falls A(G1) = 1 und A(G2) = 10 sonst



% KonjuktionevaluateF(Formula1 & Formula2, Modell, VarBelegung, true):-

evaluateF(Formula1, Modell, VarBelegung, true),evaluateF(Formula2, Modell, VarBelegung, true), !.

Im Unterschied zur Aussagenlogik wird eine Formel der Prädikatenlogik immerim Kontext eines gegebenen Modells untersucht. Die Bivalenz ist hier wie in derAussagenlogik umgesetzt.

Nehmen wir noch einen Quantor als Beispiel:

A(∀xG) :=

{1 falls für alle d ∈ UA gilt A[x|d](G) = 10 sonst


evaluateF(forall(X, Formula), Model, VarBelegung, true) :-domain(Model, Domain),evaluateF_all(X-Domain, Formula, Model, VarBelegung, true), !.

Hier werden nun alle möglichen Belegungen der freien Variablen getestet. Sonstliefert varBelegung/3 nur eine Belegung, meist die erste in der Liste.

Nehmen wir noch die Auswertung von Funktionen und dazu die Vorgabe:

A(fK(t1, . . . , tK)) := fAK(A(t1), . . . ,A(tK))


evaluateArg(A, Value,Model, VarBelegung):- !,\+ var(A),A =..[Funk | ArgList],evaluateArgs(ArgList, Args, Model, VarBelegung),interpretation(Model, Interpretation),member(Funk -> FValue, Interpretation),member(Args -> Value, FValue).

1.4.3 Unifikation

Für die Programmierung ist es oft wichtig, Formeln identisch zu machen, d.h. zuunifizieren. Meist beschränkt sich das darauf, die Syntax der Formeln zu unifizie-ren. Dies wird in diesem Abschnitt vorgestellt: Die Unifikation, die versucht, zweigegebene Formeln syntaktisch gleich zu machen. Dieses „machen“ wird durch dieSubstitution durchgeführt. Da es meist ziemlich viele Substitutionen gibt, die zwei(oder mehr) Formeln gleich machen können, wird nur die allgemeinste gesucht,also die, die die beiden Formeln mit minimalem Aufwand gleich macht.


Definition 1.6 Eine Substitution SUB ist ein Unifikator einer Menge vonLiteralen L = {L1, . . . , Ln} falls die Anwendung der Substitution ergibt, dassL1,SUB = . . . = Ln,SUB, d.h. alle Literale nach der Anwendung von SUB syntak-tisch gleich sind. Schreibweise: |LSUB| = 1

Eine Substitution SUB ist ein allgemeinster Unifikator mgu für eine Men-ge L von Literalen, falls für jeden anderen Unifikator SUB′ für L es eine Sub-stitution S gibt, mit SUB′ = SUB, S, d.h. wird S nach SUB angewendet ist dasResultat das gleiche, als wenn SUB′ angewendet worden wäre.

Die Frage ist nun, ob man auch stets einen solchen allgemeinsten Unifikatorfindet. Nachfolgender Algorithmus stellt dies sicher. Die Substitution SUB istdort als Menge realisiert. Dadurch ist es notwendig, jede neu gefundene Sub-stitution auf die bisherigen anzuwenden SUB[x|t]. Alternativ könnte eine Listeverwendet werden, die sicherstellt, dass die Substitutionen in der richtigen Rei-henfolge angewendet werden. Bei einer Menge wäre eine nebenläufige Ausführungmöglich.

Algorithmus 1.7 Eingabe: Literalmenge L = ∅.

Vorbereitung SUB := ∅

Iteration while |LSUB| > 1 do

1. Durchsuche alle Literale jeweils von links nach rechts (nach Aufbaustruk-tur!) bis die erste Position gefunden ist, wo sich mindestens zwei Li-terale L1, L2 in den vorkommenden Zeichen unterscheiden.

2. if keines der beiden Zeichen ist eine Variable

• then Stoppe: L ist nicht unifizierbar!• else Sei o.B.d.A. L1 = x Variable und L2 = t ein Termif x kommt in t vor– then Stoppe: L ist nicht unifizierbar!– else SUB := SUB[x|t] ∪ {[x|t]} und L := L[x|t].

Gebe SUB als allgemeinsten Unifikator aus.

1.4.4 Resolution

Eigentlich ist die Resolution nichts weiteres, als eine einfach anzuwendende syn-taktische Umformungsregel. Praktisch ist es aber ein Beweischritt oder kann alssolcher verwendet werden, da die Resolution durch die syntaktische Umformungsich gegenseitig widersprechende Literale aus zwei Literalmengen löscht. Als Vor-aussetzung sind die Formeln zunächst in eine geschlossene Skolemform zu bringen,d.h. es gibt nur ∀-Quantoren und diese stehen ganz am Anfang der Formel. Dannist (wie gewohnt) die Formel in eine KNF zu transformieren.


Seien K1, K2, R prädikatenlogische Klauseln. Dann ist R ein prädikatenlo-gischer Resolvent von K1 und K2, falls folgendes gilt:

1. ∃sub1, sub2 Substitutionen: sub1, sub2 sind Variablenumbenennungen, so dassK1,sub1 und K2,sub2 keine gemeinsamen Variablen enthalten.

2. ∃L1, . . . , Lm ∈ K1,sub1 und ∃L′1, . . . , L

′n ∈ K2,sub2 , so dass die Menge der

Literale L := {L1, . . . , Lm, L′1, . . . , L

′n} mit SUB unifizierbar ist

3. R hat die Form

R := ((K1,sub1 \ {L1, . . . , Lm}) ∪ (K2,sub2 \ {L′1, . . . , L

′n}))SUB

Bemerkung 1.5 Mit Prolog („Programmation en Logique“) wurde eine Program-miersprache entwickelt, die auf der Hornlogik basiert und deren einzelne Schrittemittels Resolution durchgeführt werden. Die bisherige vorgestellte Logik ist alsoin Prolog enthalten. Auf diese Weise ist ein Teil der Prädikatenlogik erster Stufezur Programmiersprache geworden.

Bevor resolviert werden kann, ist mittels Unifikation festzustellen, welche Li-terale (bis auf die Negation) unifiziert werden können. Alle Unifikationsaufgabensind bei der Suche zu einem Widerspruch zu lösen, da sie im Allgemeinen zuunterschiedlichen Resolventen und damit zu unterschiedlichen Lösungsmöglich-keiten führen. Als Heuristik für die handschriftliche Resolution sollte mit dergrößten Literalmenge begonnen werden, weil sie zu kleinen Klauselmengen führt.

1.4.5 Tableau

Es ist zu klären, wie quantifizierte Formeln expandiert werden. Dazu werden zweiTypen von quantifizierter Formeln γ bzw. δ unterschieden. Für beliebige Varia-blen x, Formeln F und für jeden beliebigen Term t gilt nachfolgende Klassifikationund es sind die Instanzen γ(t) bzw. δ(t) definiert.

Universell ∀

• γ: (∀x : F ) und ¬(∃x : F )

• γ(t): F[x|t] und ¬F[x|t]

Existentiell ∃

• δ: (∃x : F ) und ¬(∀x : F )

• δ(t): F[x|t] und ¬F[x|t]


Die uniforme Notation zur Quantifizierung liefert nicht eindeutige Komponentender Formel, sondern beliebig viele (sogar unendlich viele) Instanzen. Die Instan-zen bei der universellen und der existentiellen Quantifizierung unterscheiden sichsyntaktisch nicht. Der Unterschied liegt in der Nutzung der Instanzen.

Die prädikatenlogische Tableau-Expansion für die γ- und δ-Formeln sieht nunwie folgt aus:

1. Expandiere γ zu einem γ(t) für einen (geschlossenen) Term t.

In dieser Expansion kann jeder mögliche (geschlossene) Term verwendetwerden. (In der Resolution: gelöst durch Unifikation)

2. Expandiere δ zu einem δ(t) für einen neuen Parameter p.

In dieser Expansion können nur neue Parameter verwendet werden, d.h.solche, die noch nicht im Tableau (bzw. dem Zweig) auftreten. Nach einer γ-Expansion darf keine δ-Expansion mehr erfolgen. (In der Resolution: gelöstdurch Skolemform)

Alle anderen Tableau-Regeln bleiben wie zuvor.Vergleicht man das aussagenlogische Tableau und das prädikatenlogischen Ta-

bleau erhält man folgende Darstellung.

Aussagenlogisches Tableau Prädikatenlogisches TableauReihenfolge der Expansion Reihenfolge der Expansionbeliebig wichtig (zuerst δ!)Keine Formel muss in einem Mehrfachexpansion im selbenZweig mehrfach expandiert Zweig (γ) kann entscheidendwerden seinvollstandige Expansion einer vollständige Expansion einerFormel erfordert nur endlich Formel kann unendlich vieleviele Schritte Schritte erfordernEntscheidungsverfahren Semi-Entscheidungsverfahren

Prädikatenlogik erster Stufe ist nicht entscheidbar. Das heißt, dass es zu jedemVerfahren, das Beweise führen kann, mindestens eine Formel gibt, bei der diesesVerfahren in Schwierigkeiten kommt. Man kann sich also Verfahren überlegen, diefür viele Formeln schnell zum Ergebnis kommen, aber keines, das für alle Formelnin vorhersehbarer Zeit zum Ergebnis kommt.

Gemeinsamkeiten von Tableau und Resolution sind:

• Suchen einen Widerspruch (Widerspruchsbeweis).

• Widerspruch muss explizit in der Form P (x) ∧ ¬P (x) vorliegen, damit ererkannt werden kann.

• Zum Finden wird die Formel transformiert.


• Die Transformationen werden der Formel angefügt; die Formel selbst wirdnicht ersetzt.

Die Unterschiede werden nun aufgeführt. Zunächst die Eigenschaften beimTableau:

1. Setzt auf beliebiger Formel auf

2. Keine Vorbereitung notwendig: Alles wird während der Expansion durch-geführt. Einzige Reihen-folgenfaustregel: Alle δ- vor einer γ-Expansion!

3. Expansion entspricht Beweisschritt

4. Abgeschlossener Baum steht für Widerspruch

5. Instanziierung während Expansion

6. Unendlich viele Instanzen möglich (Prinzip der Tiefensuche)

Und nun die Eigenschaften bei der Resolution (Nummern korrespondieren):

1. Setzt nur auf KNF-Formeln auf

2. Vorbereitung:

(a) Geschlossene Bereinigte Pränexform

(b) Skolemform

(c) KNF

3. Resolutionschritt entspricht Beweisschritt

4. Leere Klausel steht für Widerspruch

5. Instanzierung mittels Unifikation (γ) während der Resolution und Skolemi-sierung (δ)

6. Nur endlich viele Instanzen möglich (Prinzip der Breitensuche)Aber: Durch unterschiedliche Unifikationen verschiedener Terme kann dieZahl der möglichen entstehenden Klauseln unendlich sein.

1.4.6 Prolog und Prädikatenlogik

1.4.6.1 Syntax

Prädikatenlogik:

1. Prädikatsymbole, z.B. P k, Ql


2. Funktionssymbole, z.B. fk, gl

3. Logiksymbole, z.B. ∧,∨,¬,→ (Junktoren); ∀,∃ (Quantoren);

4. (Funktions-)Variablen xi

5. Terme, z.B. fk(t1, . . . , tk)

6. Formeln, z.B. (P (x, y) ∧Q(z))→ Q(x)

7. Normalformen, geschlossene Formel, etc.

Prolog (Nummern korrespondieren!):

1. Funktor, z.B. p/k, q/l

2. Funktor, z.B. f/k, g/l

3. , für ∧, (; ) für ∨, bzw. zwei Regeln, not/1 bzw. \+ für ¬, : − für →

4. Prolog Variablen Xi

5. Strukturen, z.B. f(t1, . . . , tk, Out)

6. Regeln, z.B. q(X) : −p(X, Y ), q(Z).

7. bereinigte Pränexformel in Skolemform einer Hornlogikformel,d.h. Prologarbeitet nur auf einem Teil der Prädikatenlogik!

1.4.6.2 Semantik

Universum : Konstanten, die in Fakten oder Regeln vorkommen bzw. Werte,die über externe Schnittstellen geliefert werden; nicht explizit aufgeführt.

Abbildung : Prolog hat im Kern nur Prädikate, deren Semantik durch Regelnund Fakten beschrieben werden bzw. durch externe Schnittstellen.

Für Terme müssen Prädikate verwendet werden, die einen weiteren (out-) Parameter für den Rückgabewert der zugehörigen Funktion haben. DieBerechnung erfolgt ebenfalls durch Regeln und Fakten bzw. durch externeProgramme.

Interpretation : Prolog bestimmt nicht direkt den Wahrheitsgehalt einer For-mel, sondern sucht mittels Resolution indirekt nach einer Tautologie. DieVariablenbindungen geben dann dafür das zugehörige Modell an.

Kapitel 2

Nichtklassische Logik

An dieser Stelle sei ganz auf [KK06] verwiesen.

73

74 KAPITEL 2. NICHTKLASSISCHE LOGIK

Anhang A

Übungsaufgaben

Ziel der Übungen ist, den Stoff aus der Vorlesung zu vertiefen. Durch diese Ver-tiefung soll ein besseres Verständnis für den Stoff selbst gegeben werden. Dienachfolgenden Aufgaben sind Prüfungsfragen aus ehemaligen Klausuren. ZumLernen sind jedoch andere Aufgaben wichtig, die Sie sich selbst stellen sollten,um den Stoff zu erlernen. Ziel von Prüfungsaufgaben ist, erlerntes Wissen oderKompetenzen abzufragen. Ziel anderer Aufgaben kann die Ergründung fachlicherThemen sein.

A.1 Übungen Prolog

Aufgabe A.1 (Prolog) 1. Logische Programmierung (? Punkte)Geben Sie in einer kurzen und prägnanten Beschreibung die Kernidee derMethodik zur logischen Programmierung wieder. Was zeichnet logische Pro-grammierung aus ? Was sind die wesentlichen Elemente zur Strukturierungeines logischen Programms ?

2. Elemente von Prolog (? Punkte)Beschreiben Sie die möglichen Elemente in Prolog (Variablen, Listen, Kon-stanten, Strukturen, Fakten, Regeln, Anfragen).

3. Abarbeitungsstrategie (? Punkte)Erklären Sie die Abarbeitungsstrategie von Prolog (Depth-First - Left-Right- Top-Down) und geben Sie jeweils erklärende Beispiele dazu an. Wie ver-hält sich Prolog, wenn „theoretisch“ mehr als eine Regel anwendbar wäre ?

Regeln: bsp(X,Y) :- bearbeite(X).bsp(X,Y) :- bearbeite(Y).

Anfrage: ?- bsp(1,2).

75

76 ANHANG A. ÜBUNGSAUFGABEN

4. Backtracking (? Punkte)Erklären Sie das Prinzip des Backtracking.

5. Resolution (? Punkte)Erklären Sie kurz die Begriffe Substitution, Unifikation und Resolution.Wie bzw. wozu verwendet Prolog die Substitution, Unifikation und die Re-solution ?

6. Unifikation (? Punkte)Führen Sie für folgende Aufgaben die Unifikation aus. Begründen Sie IhreErgebnisse, falls keine Bindung vorgenommen wird bzw. Sie einen Fehlererkennen.

f(X,g(a,b)) = f(g(Y,b),X) 1 + 2 is 2 + 1 [Eins,Zwei|Rest] = [4,3,2,1]f(X,g(a,b)) = f(g(Y,b),Z) 3 is 1 + 2 [Eins|[Zwei|Rest]] = [4,3,2,1]

f(X,Y) = f(Y,X) X + 2 = 1 + 2 [_,_,_,Vier|_] = [a,b,c,d,e]X = f(X) 1 + (3 * 5) = X + Y [Kopf|Rest] = XX = f(X,Y) X is 2 + 1 [Kopf|Rest] = []

7. Vollständige Induktion (? Punkte)Gegeben sei folgendes Prolog-Programm:

01 % Tuerme von Hanoi02 hanoi(N) :- move(N,left,middle,right).0304 % Spielregeln/-strategie05 move(0,_,_,_) :- !.06 move(I,Q,Z,Tmp) :- J is I - 1,07 move(J,Q,Tmp,Z),08 inform(Q,Z),09 move(J,Tmp,Z,Q).1011 % Ausgabe Funktion12 inform(X,Y) :- write([move,a,disc,from,the,X,pole,to,the,Y,pole]),nl.

Zeigen Sie mittels vollständiger Induktion (Induktionsanfang, Induktionsbe-hauptung und Induktionsschritt), dass hanoi(N). korrekt arbeitet.

Tipp: Im Induktionsanfang sollten Sie die Fälle für n = 0 und n = 1betrachten, da das Programm in beiden Fällen unterschiedlichen Code aus-führt.

A.1. ÜBUNGEN PROLOG 77

Im Induktionsanfang für n = 1 und im Induktiunsschritt sind die Zeilen 06bis 09 zu betrachten!

In der Induktionsbehauptung wird die Beziehung zwischen Induktionsprinzipund rekursiver Programmierung besonders deutlich!

Sie können voraussetzen, dass wenn move(N,left,middle,right) korrektarbeitet, dies auch für jede andere Anordnung von left,middle,right kor-rekt arbeitet.

inform(Q,Z) müssen Sie nicht näher betrachten und können diesen Aufrufo.B.d.A. mit der Bewegung einer Scheibe von Quelle auf Ziel assoziieren.

8. Vollständige Induktion (? Punkte)Gegeben sei folgendes Prolog-Programm:

01 bFV([X|T], F, f(X,O)) :- bFV(T,F,O).02 bFV([], F, F).

Das Prolog-Programm soll z.B. nachfolgendes Verhalten aufzeigen:

1 ?- bFV([X,Y,Z], g(X,h(Y,Z)), Loesung).Loesung = f(X, f(Y, f(Z, g(X, h(Y, Z))))).

Zeigen Sie mittels vollständiger Induktion (Induktionsanfang, Induktionsbe-hauptung und Induktionsschritt), dass bFV/3. korrekt arbeitet.

Tipp: Legen Sie zunächst fest, über was die Induktion läuft, also was wirddurchgezählt bzw. was ist mit einer Zahl n ∈ N0 assoziierbar ? Legen Siedann fest, welche Aktion bzw. Anweisung den Induktionsschritt beschreibt.

9. Interpretieren (? Punkte)Sie treffen auf folgenden Programmcode eines Hackers:

maximal(K,M) :- schleife(K,L),!,maximal(L,M).maximal(A,A).

schleife([R,S|T],[S,R|T]) :- R >= S.schleife([F|G],[F|H]) :- schleife(G,H).

Ermitteln Sie die Funktionalität des Programms und benennen Sie die Funk-tionsnamen und Symbolnamen ggf. um, so daß in Zukunft durch die vonIhnen gewählte Namensgebung der Programmcode leichter verständlich ist.


Verwenden Sie evtl. eine Ablauftabelle ähnlich der in dem nachfolgendenTip für die Anfrage ?- maximal([4,1,5],Was)., um die Funktionalität zuermitteln.

Hier der Anfang der Tabelle, dabei wird maximal mit max und schleifemit sch abgekürzt:

Ziel geprüfte Regel/Fakt:- max([4,1,5],Was)

max(K1,M1) :- sch(K1,L1),!,max(L1,M1).Bindungen:K1 = [4,1,5]; M1 = Was;

:- sch([4,1,5],L1),!,max(L1,Was)sch([R2,S2|T2],[S2,R2|T2]) :- R2 >= S2.Bindungen:[R2,S2|T2] = [4,1,5]; [S2,R2|T2] = L1;

:- 4 >= 1,!,max([1,4,5],Was)aktuelles Ziel kann erfolgreich bewiesenwerden.

10. Interpretieren (? Punkte)Sie treffen auf folgenden Programmcode eines Hackers:

geheim(A,B) :- xyz(A,A,B).xyz([],C,[s|C]).xyz([D|Es],F,[D|G]) :- xyz(Es,F,G).

Ermitteln Sie die Funktionalität des Programms. Verwenden Sie eine Ab-lauftabelle ähnlich der in dem nachfolgenden Beispiel für die Anfrage ?-geheim([a,b,c],Geheimnis)., um die Funktionalität zu ermitteln.

Hier der Anfang der Tabelle, dabei wird geheim mit max und schleife mitsch abgekürzt:






11. Cut (? Punkte)Erklären Sie das Prinzip des Cut. Was bedeuten ein roter Cut und ein grü-ner Cut bzgl. der Semantik eines Prolog-Programms ?

12. Cut (? Punkte)Gegeben sei folgendes Prolog-Programm:

spass :- witz, lustig.spass :- lustig.spass.witz :- unsinn.lustig :- unsinn.lustig :- lustig.unsinn :- fail.

(a) Dokumentieren Sie den Ablauf für die Anfrage ?- spass.. Was würdeProlog auf diese Anfrage Antworten ?

(b) Stellen Sie die Klauseln des Programms so um, dass die Anfrage ?- spass.in endlicher Zeit beantwortet werden kann.

(c) Fügen Sie einen cut (!) in das Originalprogramm ein, so dass der vonProlog erstellte Ablauf bzgl. der Anfrage ?- spass. endlich, aber sogroß wie möglich ist. Begründung nicht vergessen, z.B. warum es beiIhrer Lösungen keinen größeren Ablauf geben kann!

(d) Beschreiben Sie den Effekt bzgl. der Anfrage ?- spass., den das Ein-fügen eines cut an jeder der drei möglichen Positionen in der erstenProgrammklausel ?- spass. :- witz, lustig. auslöst.

Hier der Anfang einer möglichen Tabelle zur Dokumentation des Ablaufs:






13. Cut (? Punkte)Gegeben sei folgender Programmabschnitt:

01 % Aussagenlogische Junktoren02 al_not(X) :- X,!,fail.03 al_not(_).04 al_and(X,Y) :- X, Y.05 al_or(X,_Y) :- write(’or_a ’),X.06 al_or(_X,Y) :- write(’or_b ’),Y.07 % Aussagenlogische Wahrheitstafel08 al_tafel(A,B,Expr) :- member(A,[true,fail]),

member(B,[true,fail]),pprint(A,B),pprint(Expr),fail.

09 al_tafel(_A,_B,_Expr).10 % Pretty Print11 pprint(X,Y) :- write(X),write(’ ’),write(Y),write(’ | ’).12 pprint(X) :- X,!, writeln(true).13 pprint(_X) :- writeln(fail).

(a) Geben Sie die Ausgabe für den Aufruf al_tafel(A,B,al_or(A,B)).an.

(b) In Zeile 12 wird der Cut gelöscht. Geben Sie nun ebenfalls die Ausgabefür den Aufruf al_tafel(A,B,al_or(A,B)). an.

(c) Vergleichen Sie die Ergebnisse. Sofern die Ausgabe des zweiten Aufrufssich von der Ausgabe des ersten Aufrufs unterscheidet, machen Siebitte deutlich, welche Teile in der Ausgabe durch Alternativen bewirktwurden, die durch diesen Cut gelöscht wurden. Geben Sie auch an,


ob es sich bei dem Cut in Zeile 12 um einen grünen oder roten Cuthandelt (Begründung nicht vergessen!).

(d) Die vorangegangene Aufgabe offenbart einen kleinen Fehler in obigemProgramm. Wie kann dieser Fehler beseitigt werden ?

14. Abarbeitungsstrategie (? Punkte)Was ergeben folgende Anfragen ? Begründen Sie Ihre Antwort!

?- not(k(v)).?- not(u(v)).

Verwenden Sie dabei Ihr eigenes Prädikat myNot oder das vorgegebene Prä-dikat not und nachfolgendes Prolog-Programm.

k(v) :- not(l(X)),a(X).l(v).a(w).u(v) :- r(X),not(s(X)).s(v).r(w).

15. AbarbeitungsstrategieGegeben sei folgendes Prolog-Programm:

1 pfad(X,Y) :- kante(X,Y).2 pfad(X,Y) :- kante(X,I), pfad(I,Y).3 pfad(a,_).

4 kante(b,c).5 kante(c,e).6 kante(c,d).

Bei nachfolgenden Aufrufen sind (z.B. durch drücken der Taste n) alle mög-lichen Lösungen zu erzeugen (also bis Prolog mit no bzw. fail antwortet).Die Lösungen sind in der korrekten Reihenfolge aufzuführen. Begründen Siekurz Ihre Lösung ggf. unter Referenzierung der entsprechenden Programm-zeile!

(a) 1 ?- pfad(a,b).

(b) 2 ?- pfad(X,b).


(c) 3 ?- pfad(X,e).

(d) 4 ?- pfad(S,Z).

(e) 5 ?- pfad(A,X),pfad(X,b).

16. Implementierung (? Punkte)Implementieren Sie folgendes Verfahren in Prolog. Dieses Verfahren zurBerechnung der Zahl π ist aus dem Jahr 1976 und stammt von den HerrenSalamin und Brent.

am :=am−1 + bm−1

2mit a0 := 1

bj :=2√

aj−1 ∗ bj−1 mit b0 :=2√0.5

πn :=(an + bn)

2

(1−∑n

k=0[2k ∗ (ak − bk)2])

Tip: Sie können verwenden, daß

• <Variablenname> is <Arithmetischer Ausdruck> die Art und Wei-se ist, wie in Prolog arithmetische Ausdrücke bestimmt werden können.

• Z is X / Y die Division z := xy

in Prolog ist,

• Y is sqrt(X) die Wurzelfunktion y := 2√x in Prolog ist,

• Z is XˆY die Exponentialfunktion z := xy in Prolog ist.

17. Implementierung (? Punkte)Implementieren Sie folgendes rekursive Verfahren (die Ackermann-Funktion)in Prolog.

a(m,n) :=

n+ 1 , falls m = 0a(m− 1, 1) , falls n = 0a(m− 1, a(m,n− 1)) , sonst

18. Implementierung (? Punkte)Implementieren Sie eine einfache For-Schleife in Prolog: schleife. Sie er-hält zwei Parameter: die Anzahl der Durchläufe und den Namen des auszu-führenden Prädikats. Ist das Prädikat im Verlaufe der Schleifenabarbeitungnicht ausführbar, wird eine Fehlermeldung ausgegeben. Beispiel

1 ?- schleife(5,p).pieppieppieppiep


pieptrue.

2 ?- schleife(5,q).qiepqiepFehler: q nicht ausführbar. (3)true.

19. Implementierung (? Punkte)

(a) (2P) Gegeben sei folgendes Prolog-Programm:

or(X,_Y) :- X.or(_X,Y) :- Y.

Definieren Sie das Prädikat orListunter Verwendung des Prädikatsor, welches genau dann erfüllt ist, wenn mindestens eine der in einerListe übergebenen Formeln erfüllt ist. Das heißt, orList([A1,. . .,An]) ist genau dann erfüllt, wenn eine der Formeln Ai erfüllt ist.Beispiel:

1 ?- orList([1==2,1==1]).true

2 ?- orList([1==2,3==2]).false.

3 ?- orList([1==2,3==2,X is 5*2]).X = 10.

(b) Definieren Sie das Prädikat firstOf, welches für eine Liste von Wer-ten, eine Variable und eine Formel überprüft, mit welchem Wert dieFormel erfüllt wird. Das heißt firstOf([q1,. . . ,qn],X,A) liefertdie Antwort X = qi genau dann wenn qi der erste Wert ist, für dendie Formel A mit [ X | qi ], also X = qi, erfüllt ist. Beispiel:

1 ?- firstOf([1,2,3,4,5,6],X,X > 2).X = 3.

2 ?- firstOf([6,3,2,1],X,X*3 =:= 6).X = 2.


3 ?- firstOf([Y,Z],X,X=2).Y = 2,X = 2.

20. Implementierung (? Punkte)

(a) Implementieren Sie das Prädikat map, welches ein zweistelliges Prädi-kat p und zwei gleichlange Listen als Parameter bekommt, so dass eineAnfrage der Form map(p,[x1,. . . ,xn],[y1,. . . ,yn]). genaudann erfüllt ist wenn p(xi,yi) für alle i ∈ {1, . . . , n} erfüllt ist. Bei-spiel:

1 ?- map(==,[1,2,3],[1,2,3]).true

2 ?- map(is,[X,Y,Z],[1+1,X,3]).X = 2,Y = 2,Z = 3

3 ?- map(succ,[28,10,12],XS).XS = [29, 11, 13]

Hinweis: Sie können das Metaprädikat call verwenden. Das Metapä-dikat call übersetzt eine Anfrage der Form call(p,t1,. . . ,tn)in die Anfrage p(t1,. . . ,tn).

(b) Implementieren Sie das 4-stellige Prädikat ntimes, welches ein zwei-stelliges Prädikat p und eine Zahl n als Parameter bekommt, so dasseine Anfrage der Form ntimes(p,n,x,y). genau dann erfüllt ist, wennp(x,x1),p(x1,x2),... ,p(xn,y) für geeignete x1,. . . ,xn erfülltsind (Dies entspricht der n-fachen Anwendung der Funktion, welchedurch das Pädikat p implementiert wird). Beipsiel, wobei das Prädikatp wie folgt definiert ist: p(XS,[a|XS]).:

1 ?- ntimes(pn,3,[],XS).XS = [a, a, a]

2 ?- ntimes(succ,4,1,X).X = 5


21. Rekursiv und Iterativ (? Punkte)Implementieren Sie zwei Funktionen teile-rek und teile-iter, die eineListe in zwei gleiche Listen aufteilt, ohne Beachtung der Reihenfolge derElemente:

?- teile-***([1,2,3,4,5,6,7,8,9,0],Out1,Out2).Out1 = [1,9,5,8,3]Out2 = [2,4,0,7,6]yes

teile-rek soll dabei mit einem rekursiven Ablauf arbeiten und teile-itermit einem iterativen Ablauf, d.h. einer Endrekursion.

22. Rekursiv und Iterativ (? Punkte)Implementieren Sie zwei Funktionen count-rek und count-iter, die dieElemente einer Liste zählen:

?- count-***([a,b,c,d,e,f,g,h,i,j],Count).Count = 10yes

count-rek soll dabei mit einem rekursiven Ablauf arbeiten, d.h. es wird erstnach dem Rekursionsaufruf gezählt, und count-iter mit einem iterativenAblauf, d.h. einer Endrekursion, d.h. es wird vor dem Rekursionsaufruf ge-zählt.

23. Listen (? Punkte)

(a) Implementieren Sie ohne Verwendung des Prädikats length undauch ohne selbst geschriebenem Prädikat zur Längenbestimmungeiner Liste ein Prädikat laenge3n(Liste), das genau dann zutrifft,wenn die Länge von Liste ein Vielfaches von 3 darstellt! Beispiel:

1 ?- laenge3n([1,2,3,4,5,6,7,8,9]).true.2 ?- laenge3n([1,2,3,4,5,6,7,8,9,10]).false.

(b) Implementieren Sie ein Prädikat zip, welches zwei Listen als Eingabehat und eine Liste mit den Paaren der korrespondierenden Elemen-te liefert. Sofern die Länge der beiden Listen nicht übereinstimmt, soll


nur für den übereinstimmenden Teil die zip-Liste erstellt werden. Bei-spiel:

1 ?- zip([1,2,3,4],[a,b,c,d],Zip).Zip = [[1, a], [2, b], [3, c], [4, d]].

2 ?- zip([1,2,3,4],[a,b,c,d,e,f,g],Zip).Zip = [[1, a], [2, b], [3, c], [4, d]].

Implementieren Sie das „Umkehrprädikat“ unzip. Beispiel:

1 ?- unzip([[1, a], [2, b], [3, c], [4, d]],L1,L2).L1 = [1, 2, 3, 4],L2 = [a, b, c, d].

24. Listen (? Punkte)Schreiben Sie ein Prädikat

substitute(X,A,InList,OutList),

dass in der Liste InList jedes Vorkommen von X durch A ersetzt.

substitute(a,z,[a,b,c,b,a],X).X = [z,b,c,b,z]

substitute(a,z,[b,c,d,c,b],X).X = [b,c,d,c,b]

25. Listen (? Punkte)Implementieren Sie in Prolog ein Prädikat flatten/2, das aus verschach-telten Listen die Atome extrahiert und sie in eine Liste schreibt. Die Atomesollen in der Ergebnisliste in der gleichen Reihenfolge stehen, wie sie in derverschachtelten Liste vorkommen. Ausserdem soll ein Aufruf flatten(L,FL).wahr sein, wenn FL eine solche flache Liste zu L ist. Beispiele:

flatten([a,b,c],X).X = [a,b,c]

flatten([a,b,c,[1,2,3]],X).X = [a,b,c,1,2,3]

flatten([[a],b,c,[1,[2],3,[x,y,z]]],X).


X = [a,b,c,1,2,3,x,y,z]

flatten([a,b,c,[1,2,3,[x,y,z]]],[a,b,c,1,2,3,x,y,z]).yes

26. Listen (? Punkte)

(a) Implementieren Sie ein PrädikattouchListe(InList, OutNRList,OutERList),dass die Liste InList einmal zerlegt (mittels [.|.]-Operator) und die-se per naiver Rekursion (OutNRList) und Endrekursion bzw. iterati-ver Rekursion (OutERList) ausschließlich mittels dem [.|.]-Operatorwieder zusammen baut. Beispiel:

9 ?- touchListe([1,2,3,4],OutNRList,OutERList).OutNRList = [1, 2, 3, 4],OutERList = [4, 3, 2, 1].

(b) In der vorgenommenen Implementierung von touchListe wurde eineRegel mit einem rekursiven Aufruf erstellt. Fügen Sie vor diesem Auf-ruf ein writeln (erzeugt Ausgabe und einen Zeilenumbruch) ein undein write nach diesem Aufruf (erzeugt Ausgabe ohne Zeilenumbruch)des aktuellen Kopfes der zu bearbeitenden Liste ein. Also in etwa:

touchListe(...) :- ...writeln(Kopf),touchListe(...), % rekursiver Aufrufwrite(Kopf),...

Welche Ausgabe erzeugt folgender Aufruf:9 ?- touchListe([1,2,3,4,5],NRrek,ERiter).?

27. Listen (? Punkte)Wenn eine Liste sich wiederholende Elemente enthält, sollen diese in jeweilsgetrennten Teillisten komprimiert gesammelt werden. Die Reihenfolge derElemente soll nicht verändert werden; dazu ist das Prädikat append zu ver-wenden! Die Teillisten enthalten die Anzahl der ursprünglich vorhandenenElemente und genau eines dieser Elemente.

Implementieren Sie dazu in Prolog das Prädikat encode/2, das diese Trans-formation vornimmt.

Beispiele:


?- encode([a,a,a,a,b,c,c,a,a,d,e,e,e,e],Code).Code = [[4, a], [1, b], [2, c], [2, a], [1, d], [4, e]]

?- encode([a],Code).Code = [[1, a]]

?- encode([],Code).Code = [].

?- encode([a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a],Code).Code = [[17, a]]

28. Tiefensuche (? Punkte)Gegeben sei folgender gerichteter Graph in Prolog-Notation:

c(a, b).c(b, c).c(b, d).c(b, f).c(c, e).c(c, f).c(f, g).c(g, e).c(e, b).c(e, c).

Implementieren Sie folgende Algorithmen:

(a) Einen Algorithmus, der den Graphen von einem Ausgangspunkt zueinem Zielpunkt traversiert (durchläuft) und dabei die Zwischenziele(inkl. Start und Ziel) sammelt. Dieser Pfad soll am Ende in einerListe stehen. Zyklen sind nicht abzufangen! Beispielaufruf:

?- traverse(b, e, Pfad).Pfad = [b, c, e] ;Yes

(b) Erweiteren Sie den Algorithmus aus Teilaufgabe 1, so dass er Zyklenvermeidet:

?- traverse(b,g,L).Pfad = [b, c, f, g] ;


Yes

statt (im Sinne von [b, c, e, c, e, ...]:

?- traverse(b,g,L).ERROR: Out of local stack

29. Beweise zählen (? Punkte)Gegeben sei das folgende Prolog-Programm P.

nqed([], 0).nqed([X|Xs], Y) :- not(X),!,nqed(Xs,Z),Y is Z+1.nqed([_|Xs], Y) :- nqed(Xs,Y).

p(s(X),X). % Ein Beispiel

Das Prädikat nqed(Xs,Y) ist genau dann wahr, wenn Xs eine Liste vonatomaren Formeln ist, von denen Y viele nicht beweisbar sind. Beispiel:

1 ?- nqed([p(X,0),p(0,X)],Y).Y = 1.Yes

Geben Sie eine Ablauftabelle oder einen Ablaufbaum (ein SLD („Selective Li-near Definite“)-Baum) oder einen Ablauf-Trace (nach dem Vierportmodell)an, der bei der Anfrage ?- nqed([p(X,0),p(0,X)],Y). entsteht. Wichtigist, dass Sie den Ablauf im Detail nachvollziehbar dokumentieren. Wenn Siegleiche Teile abkürzen, machen Sie bitte deutlich, wie Ihre Abkürzungen zulesen sind. Beachten Sie, durch welche zwei Klauseln das Prädikat not/1definiert ist.

30. Auswerten (? Punkte)

(a) Eine „simple arithmetic expression“ (SAE) ist eine Zahl oder ein Termder Form mal(E1,E2), wobei die Argumente E1 und E2 wieder SAEssind. Implementieren Sie ein Prädikat eval(E,N) in Prolog, welchesgenau dann beweisbar ist, wenn sich die SAE E zu der Zahl N auswer-ten lässt. Hierbei steht die SAE mal(E1,E2) für die Multiplikation vonE1 mit E2. Bei der Auswertung von mal(E1,E2) sollte E2 nur ausge-wertet werden, falls die Auswertung von E1 nicht 0 ergibt.


Beispiel: Die Anfrage ?- eval(mal(mal(5,0), mal(7,7)), N). soll-te beweisbar sein und die Antwort N=0 liefern. Hierbei sollte jedochdie SAE mal(7,7) nicht ausgewertet werden!

(b) Wir erweitern die Klasse der SAEs um bedingte Ausdrücke, die dieForm B ? E1 : E2 haben. Hierbei ist B eine Bedingung, d.h. eine ato-mare Formel, und E1 und E2 sind SAEs. Definieren Sie ? und : alsOperatoren, so dass bedingte Ausdrücke vom Prolog-System akzeptiertwerden. Erweitern Sie dann eval für die Auswertung von bedingtenAusdrücken. Falls B beweisbar ist, so wertet der obige bedingte Aus-druck zum Resultat von E1 aus. Falls man feststellt, dass B nicht be-weisbar ist, dann ergibt sich das Resultat von E2. Auch hier solltenunnötige Auswertungen vermieden werden.Beispiel: Die Anfrage ?- eval((3 < 2) ? mal(3,3) : mal(4,4), N)sollte folglich die Antwort N=16 liefern, ohne dabei mal(3,3) aus-zuwerten. In gleicher Weise sollte die Anfrage ?- eval((2 < 3) ?mal(3,3) : mal(4,4), N) die Antwort N=9 liefern, ohne dabei mal(4,4)auszuwerten.

A.2 Übungen Klassische LogikAufgabe A.2 (Aussagenlogik) 1. Begriffsklärung (? Punkte)

Erklären Sie die drei wesentlichen Bestandteile eines logischen Systems:Syntax, Semantik und Kalkül. Erklären Sie insbesondere bei der Semantik,was unter einem Modell verstanden wird.

2. Aussagen (? Punkte)Tatsachen sind beweisbar und damit Aussagen (im logischen Sinne), Mei-nungen muss man ausdiskutieren und sind daher keine Aussagen (im logi-schen Sinne). Welche Sätze sind hier Tatsachen bzw. Meinungen? (Begrün-dung unbedingt angeben!)

(a) „Geld macht nicht glücklich, aber es beruhigt.“(b) „Manche behaupten, der Mensch stamme von Adam und Eva ab.“(c) „Rauchen gefährdet die Gesundheit.“(d) „Politik ist ein schmutziges Geschäft.“(e) „Es gibt Menschen, die übersinnliche Kräfte haben“.(f) „Manche Zeitungsmeldungen sind falsch.“

3. Aussagen (? Punkte)Seien i, j ∈ Z ganze Zahlen. Bestimmen Sie, ob die folgenden Formeln Tau-tologien, kontigente Formeln oder Widersprüche sind! Bilden Sie außerdemfür jede Formel das Gegenteil (im Sinne der logische Negation)!

A.2. ÜBUNGEN KLASSISCHE LOGIK 91

(a) ∀i ≤ 0 : i < j.

(b) ∀i ≤ 0 : ∃j < 0 : i < j.

(c) ∀i < 0 : ∃j < 0 : i ≤ j.

(d) ∃j < 0 : ∀i < 0 : i ≤ j.

(e) i2 ≤ 0.

(f) i2 ≤ i2 − 1.

(g) (i+ j)2 = i2 + 2 ∗ i ∗ j + j2.

4. Aussagen (? Punkte)Modellieren Sie die folgenden Sätze möglichst adäquat als aussagenlogischeFormeln. In schwierigen Fällen begründen Sie bitte kurz die Wahl der Junk-toren.

(a) Die Situation ist hart, aber nicht hoffnungslos.

(b) Genau dann, wenn sich weder eine Diskette noch eine CD im Laufwerkbefindet, kann der Computer von der Festplatte booten.

(c) An Weihnachten schneit es, es sei denn, man ist in Bielefeld oder inder Karibik.

(d) Wenn die Bayern alle Spiele gewinnen, dann werden sie von allengehasst, aber wenn sie nicht alle Spiele gewinnen, werden sie von nie-mandem geliebt.

Prüfen Sie folgendes mittels Wahrheitstafel nach: Aus der Modellierung desletzten Satzes ((d)) folgt die Aussage „Wenn die Bayern von jemandem ge-liebt werden, dann werden sie von allen gehasst.“. Diskutieren Sie das Er-gebnis.

5. Aussagen (? Punkte)Welche der folgenden Aussagen sind wahr bzw. falsch ? Begründen Sie bitteIhre Antworten! Gehen Sie davon aus, das Lügner hier immer lügen undnie die Wahrheit sagen.

(a) Eine Klauselmenge M ist erfüllbar gdw. jede endliche Teilmenge vonM erfüllbar ist.

(b) Wenn 2 + 2 = 5 gilt, dann schreiben wir das Jahr 1984.

(c) Das Bibelzitat1 „Ein Kreter sagt: Alle Kreter lügen.“ ist in sich wider-sprüchlich.

(d) Dieser Satz ist falsch.

1Brief des Paulus an Titus 1,12


6. Tautologie (? Punkte)Welche der folgenden aussagenlogischen Ausdrücke sind Tautologien ? Ver-wenden Sie Wahrheitstafeln zum Beweis. (x↔ y ist dabei (x∧y)∨(¬x∧¬y)und x→ y ist ¬x ∨ y)

(a) (x→ y)↔ [(x ∧ ¬y)→ y]

(b) (x→ y)→ [(z ∨ x)→ (z ∨ y)]

(c) [(x→ y)→ (y → z)]→ (x→ z)

7. Tautologie (? Punkte)Seien F,G,H aussagenlogische Formeln. Zeigen Sie mit Hilfe der funda-mentalen Äquivalenzen:

(a) Ist F → H eine Tautologie, so ist F äquivalent zu F ∧H.

(b) ((F ∨H) ∧ (G ∨ ¬H))→ (F ∨G)

8. Äquivalenz (? Punkte)Gegeben seinen die folgenden beiden aussagenlogischen Formeln:

• F := (a ∧ b) ∨ (a ∧ c) ∨ (b ∧ c)

• G := (a ∧ b) ∨ (c ∧ ¬(a↔ b))

Zeigen Sie, dass F und G semantisch äquivalent sind, indem Sie

(a) für beide Formeln eine Wahrheitstafel aufstellen.

(b) G durch die Anwendung der aussagenlogischen fundamentalen Äqui-valenzregeln in F überführen.

9. Wahrheitstafel (? Punkte)Gegeben seinen die folgenden beiden aussagenlogischen Formeln:

• F := (¬(a→ b) ∧ c)↔ c

• G := ¬(c ∧ (a→ (b ∨ ¬c)))

(a) Erstellen Sie eine Wahrheitstafel der Formeln F und G ohne vorherdiese zu transformieren!

(b) Sind die Formeln erfüllbar, kontingent und/oder falsifizierbar ?

(c) Sind die Formeln semantisch äquivalent ?

(d) Erstellen Sie für F oder G eine kanonische DNF oder KNF.

10. Begiffe (? Punkte)Welche der folgenden Aussagen sind wahr ? (Begründung nicht vergessen!)


(a) A und B seien erfüllbar. Dann ist

A ∧B erfüllbar A ∨B falsifizierbar

A→ B kontingent ¬A falsifizierbar

(b) A sei erfüllbar und B nicht erfüllbar. Dann ist

A ∧B ein Widerspruch A ∨B erfüllbar

A→ B ein Widerspruch B → A eine Tautologie

(c) A sei keine Tautologie und B erfüllbar. Dann ist

A ∧B kontingent ¬A ∧ (A ∨B) falsifizierbar

(¬A)→ B erfüllbar ¬A ein Widerspruch

(d) B ist Tautologie, wenn A und A→ B Tautologien sind.

11. Wahrheitstafel (? Punkte)Gegeben sei die aussagenlogische Formel F

F ≡ (¬A ∨ ¬(¬B ∨ ¬A))→ (C ∨ (¬B ↔ A))

(a) Erstellen Sie eine Wahrheitstafel der Formel F ohne vorher diese zutransformieren!

(b) Ist die Formel erfüllbar und/oder kontingent und/oder falsifizierbar ?

(c) Erstellen Sie eine kanonische DNF oder KNF, je nachdem, welchekürzer ist.

12. Wahrheitstafel (? Punkte)Gegeben sei folgende Formel:

H = (A ∧ ¬B ∧ C) ∨ (A ∧B ∧ ¬C) ∨ (A ∧ ¬B ∧ ¬C)

(a) Bestimmen Sie die Wahrheitstafel der Formel H.

(b) Beschreiben Sie drei unterschiedliche Möglichkeiten, eine semantischäquivalente Formel in KNF für die Formel H zu erstellen. Wählen Siedann eine dieser Möglichkeiten, um eine semantisch äquivalente For-mel in KNF zu erstellen, die aus maximal zwei Klauseln besteht. Wei-sen Sie die Korrektheit dieser Äquivalenz nach. Begründen Sie kurz,warum Sie sich für die gewählte Möglichkeit zur Erstellung der KNFentschieden haben und warum Sie die anderen nicht genommen haben.

(c) Gegeben sei folgende Definition:


Definition A.1 Sei F eine aussagenlogische Formel. Ein Modell Aheisst kleinstes Modell von F , wenn für alle Modelle B von F und alleaussagenlogische Variablen a in F gilt: wenn A(a) = 1, dann ist auchB(a) = 1.

Bestimmen Sie das/die kleinsten Modelle der Wahrheitstafel in Auf-gabenteil (a)

13. Äquivalenz (? Punkte)Es seien A und B mathematische Aussagen. Zeigen Sie durch geeigneteäquivalente Umformungen (bis zum Ende!), das nachfolgende Formel eineTautologie ist:

((A ∨B)→ A)↔ (B → (A ∧B))

14. Äquivalenz (? Punkte)Es seien A,B,C und D mathematische Aussagen. Zeigen Sie durch ge-eignete äquivalente Umformungen (also ohne die Verwendung einer Wahr-heitstafel) mit Hilfe des DeMorganschen Gesetzes, der Assoziativität, derDistributivität und der Kommutativität schrittweise unter Angabe der ver-wendeten Gesetze, dass folgende beide Aussagen äquivalent sind.

(¬(D → ((A ∧ ¬B) ∧ C))) ((¬A ∧D) ∨ ((B ∧D) ∨ (¬C ∧D)))

Beachten Sie: Das doppelte Komplement kann direkt weggelassen werden.Die Klammern sind jedoch nur mittels Assoziativität verschiebbar, jedochnicht wegzulassen!

15. NAND (? Punkte)Wir bezeichnen im Folgenden den logischen Junktor nand mittels dem Sym-bol |.

(a) Untersuchen Sie, ob der |-Junktor assoziativ ist.

(b) Bilden Sie die zur Formel (x1|x2)|x3 äquivalente kanonische DNF. Fin-den Sie mittels Transformation dieser kanonischen DNF eine verein-fachte DNF, die maximal zwei Konjunktionsglieder hat.

16. Semantisch äquivalent (? Punkte)Seien F,G aussagenlogische Formeln. Zeigen Sie mit Hilfe der fundamenta-len Äquivalenzen durch geeignete Transformationen die semantische Äqui-valenz (≡) der nachfolgenden Formeln. Verwenden Sie dazu folgende Defi-nitionen: A↔ B ≡ (A→ B) ∧ (B → A) sowie A→ B ≡ ¬A ∨B.

(a) F ↔ ¬G ≡ ¬F ↔ G

(b) ¬F ↔ G ≡ (F ∨G) ∧ ¬ (F ∧G)

(c) (F ∨G) ∧ ¬ (F ∧G) ≡ (F → ¬G) ∧ (¬F → G)


(d) (F → ¬G) ∧ (¬F → G) ≡ ¬ (F ↔ G)

17. Semantisch äquivalent (? Punkte)

(a) Zeigen Sie mittels den fundamentalen Äquivalenzen, dass eine beliebi-ge aussagenlogische Formel, die nur die aussagenlogischen Variablena1, a2, . . . , an und nur die Symbole (, ) und ∧ enthält, semantisch äqui-valent zu dem Ausdruck

(((((a1 ∧ a2) ∧ a3) ∧ a4) . . .) ∧ an)

ist. Beachten Sie, dass in der beliebigen Formel die Variablen mehr-mals und in nicht aufsteigend sortierter Reihenfolge bzgl. dem Indexvorkommen können! Die beliebige Formel ist korrekt geklammert.Hinweis: Es gibt keine fundamentale Äquivalenz, die Klammern ent-fernt!

(b) Gilt die zu (a) analoge Aussage für ∨ bzw. → bzw. ↔ anstelle von ∧auch?

18. Verschlüsselung (? Punkte)Im ASCII-Code heißtGEHEIM 1000111.1000101.1001000.1000101.1001001.1001101 undSECRETE 1010011.1000101.1000011.1010010.1000101.1010100.1000101.

J.R. Hacker kennt die xor-Funktion und möchte seinem Freund die Nach-richt GEHEIM verschlüsselt im Internet übermitteln, damit kein anderer sielesen kann. Als Schlüssel verwendet er die ersten sechs Buchstaben des Wor-tes SECRETE, also SECRET. Diesen Schlüssel hat er seinem Freund bei einemTreffen schon mal persönlich übergeben.

(a) Stellen Sie die Wahrheitstafel für die Funktion xor auf.

(b) Verschlüsseln Sie nun die Nachricht GEHEIM = x mit dem Schlüs-sel SECRET = y, indem Sie die einzelnen binären Werte xi, yi; i ∈{1, . . . , 42} durch die xor-Funktion verknüpfen, also zi = xi xor yi.Das Ergebnis ist die binäre Folge z.

(c) Welchen Zeichen in der ASCII-Tabelle entspricht dieser Ausdruck ?ASCII-Tabellen finden Sie z.B. in den meisten Büchern über die Pro-grammiersprache C.

(d) Entschlüsseln Sie nun die verschlüsselte Nachricht z mit dem SchlüsselSECRET. Was kommt heraus ?

19. Beweise (? Punkte)


(a) Zeigen Sie mit Hilfe einer Wahrheitstafel, dass das DistributivgesetzA ∨ (B ∧ C) ≡ (A ∨B) ∧ (A ∨ C) gilt.

(b) Die Formeln beim Distributivgesetz sind in DNF (linke Seite) undKNF (rechte Seite) gehalten. Bei einer kanonischen DNF bzw. ka-nonischen KNF sind bei der jeweiligen konjunktiven bzw. disjunkti-ven Klausel alle aussagenlogischen Variablen vorhanden. Geben Sie zudem Distributivgesetz entweder die kanonische DNF oder die kano-nische KNF an, je nachdem, welche am kürzesten ist (am wenigstenKlauseln beinhaltet).

(c) Zeigen Sie durch geeignete äquivalente Umformungen, dass die Aus-sage ((A → B) ∧ ((¬A) → B)) → B unabhängig von den Wahrheits-werten von A und B stets wahr ist.

20. Interpretation (? Punkte)Gegeben sei die aussagenlogische Formel F = ¬((A ∧ B) ∨ C) und die Be-legungen A(A) = 1;A(B) = 1; und A(C) = 0;. Bestimmen Sie A(F ) durchAnwendung der Definition der Semantik der Aussagenlogik (Belegungsfunk-tion A).

21. Modellierung (? Punkte)Es sei festgelegt: a := „Ich bestehe die Klausur“ und b := „Ich freue mich“.Formulieren Sie nachfolgende Aussagen in aussagenlogische Formeln aus-schließlich mittels der drei Junktoren ¬,∧ und ∨, so dass die Reihenfolgeder aussagenlogischen Variablen soweit möglich erhalten bleibt:

(a) „weder bestehe ich die Klausur noch freue ich mich“

(b) „auf jeden Fall bestehe ich die Klausur unabhängig davon, ob ich michfreue“

(c) „dann bestehe ich die Klausur, wenn ich mich freue“

(d) „auf keinen Fall freue ich mich“

(e) „entweder bestehe ich die Klausur oder ich freue mich“

(f) „Ich kann nicht zugleich die Klausur bestehen und mich freuen“

(g) „Ich werde mindestens eins von beidem tun: die Klausur bestehen odermich freuen“

Beispiel: „Ich bestehe die Klausur und ich freue mich“: a ∧ b.

22. Modellierung (? Punkte)Hawkeye hat beim Baseball seinen Golfschläger zertrümmert und brauchtdringend einen neuen. Er wendet sich mit seinem Problem an Radar. Derschwingt sich ans Funkgerät und legt nach einiger Zeit die folgende Listemit möglichen Tauschgeschäften vor:


• Morphium + reiner Alkohol → 1 Schinken + 1 Flasche Whisky

• 1 Flasche Whisky + 1 Flasche Selbstgebrannter → 1 Lenkrad

• 1 Tüte Gips + 1 Schinken → 1 Topf + 1 Grammophon

• 1 Grammophon + 1 Lenkrad → 1 Golfschläger

Im Lager vorhanden sind Morphium, reiner Alkohol, Selbstgebrannter undGips. Bekommt Hawkeye seinen Golfschläger ?

(a) Wandeln Sie diese Fragestellung in eine Erfüllbarkeitsfrage für einegeeignete aussagenlogische Formel um.

(b) Lösen Sie die Erfüllbarkeitsfrage für diese Formel mit Hilfe des Reso-lutionskalkül.

23. Modellierung (? Punkte)Bauer Horst besitzt einen kleinen Acker, einen Wolf und das Schwein Bor-sti. Wenn der Händler ehrlich ist, ist das Saatgut, das Horst von ihm kauft,gut. Wenn das Saatgut und das Wetter im Sommer gut sind, verdient Horstausreichend Geld. Wenn er ausreichend Geld hat, füttert er den Wolf. Wenner den Wolf gefüttert hat und in der Stadt Kirmes ist, geht er in die Stadtund lässt Wolf und Borsti allein. Wenn der Wolf gefüttert worden ist, ist ersatt. Wenn der Wolf satt ist oder der Bauer anwesend ist, wird Borsti nichtgefressen.

(a) Wandeln Sie diesen Text in eine Erfüllbarkeitsfrage für eine geeigneteaussagenlogische Formel in KNF um.

(b) Angenommen, in der Stadt ist Kirmes. Wird Borsti nicht gefressen,wenn das Wetter im Sommer gut und der Händler ehrlich waren ?Lösen Sie diese Erfüllbarkeitsfrage für die Formel aus Teil (a) mitHilfe des Resolutionskalkül.

24. Modellierung (? Punkte)Geben Sie eine Formel F an, die drei atomare Formeln A,B und C ent-hält und folgende Eigenschaften erfüllt: Für jede Belegung A : {A,B,C} →{0, 1} gilt, dass das Ändern irgendeiner der Werte A(A), A(B) oder A(C)auch A(F ) ändert. Beispiel: Sei o.B.d.A. F (1, 0, 1) = 1, dann müssteF (0, 0, 1) = F (1, 1, 1) = F (1, 0, 0) = 0 sein.

Tipp: Stellen Sie zunächst eine Formel auf, die nur zwei atomare Formelnbeinhaltet und die Änderung der Eingabe signalisiert.

25. Modellierung (? Punkte)Nach dem ersten Semester an der HAW Hamburg fühlen Sie sich nun fitin Logik und können erklären, ob folgender Schluß richtig oder falsch ist:


„Wenn ich 100m unter 10 Sekunden laufe, werde ich zur Olympiade zugelas-sen. Da ich die 100m nicht unter 10 Sekunden laufe, werde ich folglich nichtzur Olympiade zugelassen“. Verwenden Sie zur Erklärung die Aussagenlo-gik, d.h. leiten Sie mittels der Aussagenlogik die Gültigkeit oder Ungültigkeitdieser Aussage ab!

26. Modellierung (? Punkte)Auf die Frage, worin sein Geheimnis für sein langes Leben besteht, ant-wortete ein 100-jähriger wie folgt: „Ich halte mich streng an die Diätregel:Wenn ich keinen Wein zur Mahlzeit trinke, dann habe ich immer Fisch.Immer wenn ich Fisch und Wein zur selben Mahlzeit habe, verzichte ich aufSchokolade. Wenn ich Schokolade habe oder Wein meide, dann rühre ichFisch nicht an“. Der Fragensteller fand diesen Ratschlag ziemlich verwir-rend. Können Sie ihn mit Hilfe der Aussagenlogik vereinfachen ?

27. Modellierung (? Punkte)Zwei Logiker, beide in Rente, eröffnen jeder ein Restaurant. Sie kommenüberein, folgende Ruhetag-Regelung streng logisch durch folgende Aussage-variablen zu erklären:

Restaurant 1 „Wenn Montag ist, dann ist Ruhetag“

Restaurant 2 „Nur wenn es Montag ist, dann ist Ruhetag“

Formalisieren Sie obige Erklärungen, füllen Sie eine Wahrheitstafel aus undinterpretieren Sie deren Zeilen. Genau das ist (hier) mit „logischem Den-ken“ gemeint!

28. Modellierung (? Punkte)Vorgelegt seien die Aussagenvariablen (Sätze)

a : „Wiebke ist Diplom-Ingenieurin“

b : „Wiebke ist verheiratet“

c : „Wiebke wohnt in Hamburg“

Modelieren Sie mittels den Aussagenvariablen in kanonischer Normalform(KNF oder DNF) folgende Formalisierungen:

(a) Mindestens einer der drei Sätze gilt.

(b) Genau einer der drei Sätze gilt, d.h. einer und nur einer gilt.

(c) Höchstens einer der drei Sätze gilt.

29. Modellierung (? Punkte)Schon kurz nach der Geburt der Zwillingsbrüder Herakles und Eurystheusentstand ein Streit, wer von den beiden der rechtmäßige Herrscher sei. Dazu


wurden die drei bekanntesten Orakel befragt. Das Ammonion gab bekannt,dass die Orakelsprüche aus Klaros grundsätzlich falsch seien. Ebenso ließdas Orakel aus Klaros verlauten, dass die Orakelsprüche aus Delphi samtund sonders unzutreffend seien. Das Orakel aus Delphi jedoch behauptete,sowohl die Sprüche des Ammonions als auch die des Orakels in Klaros seienunwahr.

Wem sollten die armen Griechen nun glauben? Lösen Sie die Aufgabe mit-tels Wahrheitstafel.

30. Modellierung (? Punkte)Captain Archer und Sub-Commander T’Pol landen auf dem Planeten Wahr-lüg, auf dem die Bewohner immer lügen oder immer die Wahrheit sagen.Sie treffen auf drei Bewohner:

• Der erste sagt: „Einer von den beiden anderen ist ein Lügner.“

• Der zweite sagt: „Wenn das wahr ist, dann ist der dritte der Lügner.“

• Der dritte sagt: „Nur wenn der erste die Wahrheit gesagt hat, dann istder Zweite ein Lügner.“

Wen sollten die beiden als Ortskundigen mitnehmen ? Lösen Sie die Fragemittels einer Wahrheitstafel.

31. Modellierung (?? Punkte)Donald war erbost: „Wer von euch hat von der Torte genascht ?“ SeineNeffen blickten betreten auf das Backwerk, dessen kunstvolle Dekoration vonkleinen Entenfingern (wie auch immer die aussehen) übel zugerichtet war.Einerseits wollten sie nicht petzen oder sich selbst beschuldigen, andererseitswollten sie ihren Onkel auch nicht belügen.

• Nach einigen Anläufen quälte Tick aus sich heraus: „Trick oder ichwaren es.“

• Dann druckste Trick: „Entweder war es Track oder ich.“

• Track gab an: „Entweder hat Tick oder ich nicht genascht.“

Zum Erstaunen der drei wusste Donald sofort, wer genascht hatte. Näm-lich ?

Begründen Sie kurz, warum Sie sich für das von Ihnen gewählte Verfahrenzur Klärung der Frage entschieden haben.

32. Modellierung (? Punkte)In einer Stahlbaufirma haben die Vorbereitungen für die Montage einerBrücke begonnen. Die vormontierten Baugruppen sollen mit Hilfe von Hy-draulikpressen in die erforderliche Position gebracht werden. Bei einem


dieser Montageschritte muss unbedingt vermieden werden, dass die Ventilezur Betätigung der Hydraulikpressen in eine der folgenden Konstellationenkommen:

• Ventile A und B geschlossen.

• Ventile A und C offen.

• Ventil A geschlossen, und Ventile B oder C offen.

• Ventil B geschlossen, und Ventile A oder C offen.

(a) Stellen Sie eine aussagenlogische Formel auf, die die Regeln für er-laubte Konstellationen beschreibt.

(b) Ist die einzig mögliche Konstellation, dass die Ventile A und B offenund Ventil C geschlossen sind ? Lösen Sie diese Frage mit Hilfe desResolutionskalkül.

33. Modellierung (? Punkte)Von der Schwierigkeit, Menschen zu verstehen:

• Anne sagt: „Bettina sagt die Wahrheit.“

• Bettina sagt: „Claudia lügt.“

• Claudia sagt: „Anne und Bettina sagen beide die Wahrheit oder lügenbeide.“

Wer lügt denn nun und wer sagt die Wahrheit ? Beantworten Sie die Fragemittels Resolutions-Kalkül und behaupten dazu, dass Claudia die Wahrheitsagt.

34. Modellierung (? Punkte)Übersetzen Sie folgende Texte in aussagenlogische Formeln. Bestimmen Siedazu zunächst die elementaren/atomaren Aussagen (im Sinne aussagenlo-gischer Variablen) und ordnen Sie diesen Buchstaben als Abkürzung zu;Beispiel: K = „Ich habe Recht“.

(a) „Platon hatte Recht mit seiner Einschätzung des Sokrates genau dann,wenn Sokrates kein großer Philosoph war.“

(b) „Wenn Sokrates ein großer Philosoph war, dann hatte Aristoteles Rechtmit seiner Einschätzung des Platon.“

(c) „Aristoteles hatte nur dann Recht mit seiner Einschätzung des Platon,falls Platon Recht hatte mit seiner Einschätzung des Sokrates.“

(d) „Unter der Annahme, dass zu all den bisherigen Aussagen noch gilt,dass Platons Einschätzung des Sokrates stimmt, folgt, dass Sokrateskein großer Philosoph war.“


Hinweis: Sie können →,↔,∧,∨,¬ verwenden.

35. Modellierung (? Punkte)Gegeben seien folgende Aussagen:

• Wenn Elmo Aktien der Logik-AG kauft, dann erhält er viel Dividende,falls der aktuelle Direktor der Logik-AG von seinem Posten abgelöstwird.

• Elmo wird sich kein Haus bauen, falls er viel Dividende erhält undheiratet.

• Wenn Elmo im Sommer nicht nach Madeira fährt, dann wird er hei-raten und sich ein Haus bauen.

• Falls also Elmo Aktien der Logik-AG kauft, dann fährt er im Sommernach Madeira, wenn der aktuelle Direktor der Logik-AG von seinemPosten abgelöst wird.

(a) Erstellen Sie eine aussagenlogische Formel aus den Aussagen.

(b) Zeigen Sie mittels Resolutions-Kalkül, dass die vierte Formel (letztebzw. unterste Aussage) aus den vorangegangenen Formeln folgt.

36. Modellierung (? Punkte)Sie kommen auf eine Insel mit zwei Stämmen, den Wahrheitssprechern undden Lügensprechern. Die Wahrheitssprecher sagen immer die Wahrheit, dieLügensprecher lügen immer.

Beim Landen auf der Insel treffen Sie Alice, Bob und Charlie. FormalisierenSie die nachfolgenden Situation mit Hilfe einer aussagenlogischen Formel.Wählen Sie die aussagenlogischen Variablen so, dass Sie die Situationen in(b) und (c) auch zusammen betrachten können.

(a) Klären Sie, wie der Begriff „sagt“ zu modellieren ist, also wie wird „Je-mand sagt etwas“ in einer aussagenlogischen Formel modelliert, unterder Voraussetzung, dass Jemand sowohl Wahrheitssprecher wie auchLügensprecher sein kann. Verwenden Sie dazu ausschließlich die zweiaussagenlogischen Variablen JW: „Jemand ist Wahrheitssprecher“ undE: „Etwas“.Begründen Sie Ihre Antwort ausführlich.Modellieren Sie mit der gefundenen Formel als kleines Beispiel folgen-de Situation: Hans sagt: „Es regnet“ mittels den beiden aussagenlo-gischen Variablen HW für Hans ist Wahrheitssprecher und R für Esregnet. Geben Sie für die Formel eine Wahrheitstafel an und interpre-tieren Sie das Ergebnis.


(b) Sie fragen Alice, zu welchem Stamm sie gehöre. Alice versteht Sie we-gen Ihrem Akzent nicht und Bob dolmetscht. Bob sagt, Alice habe ge-sagt, sie sei eine Lügensprecherin. Charlie mischt sich ein und sagt,Bob lüge und Alice sei eine Wahrheitsprecherin.Können Sie entscheiden, zu welchen Stämmen Alice, Bob und Charliegehören? Begründen Sie Ihre Antwort ausführlich durch z.B. Berech-nung / Umformung oder eine Wahrheitstafel.

(c) Sie hören das folgende Gespräch: Alice sagt: „Charlie sagt die Wahr-heit.“. Bob sagt: „Wenn Alice lügt, dann sage ich die Wahrheit.“ Charliesagt: „Wenn Bob lügt, dann lügt auch Alice.“Ist Charlie vom Stamme der Lügensprecher? Begründen Sie Ihre Ant-wort ausführlich durch z.B. Berechnung / Umformung oder eine Wahr-heitstafel.

(d) Widersprechen sich die Situationen in (b) und (c) oder stimmen sieüberein? Begründen Sie auch hier Ihre Antwort!

37. Modellierung (? Punkte)In der Stadt Sörknatten besteht die Bevölkerung ausschließlich aus Ritternund Schurken, wobei Ritter immer die Wahrheit sagen, und Schurken immerlügen.

Beim Eintreffen in der Stadt Sörknatten treffen Sie Kunibert, Hotzenblotzund Siegfried. Formalisieren Sie die nachfolgende Situation mit Hilfe eineraussagenlogischen Formel.

(a) Klären Sie, wie der Begriff „sagt“ zu modellieren ist, also wie wird „Je-mand sagt etwas“ in einer aussagenlogischen Formel modelliert, unterder Voraussetzung, dass Jemand sowohl Ritter wie auch Schurke seinkann. Verwenden Sie dazu ausschließlich die zwei aussagenlogischenVariablen JR: „Jemand ist Ritter“ und E: „Etwas“.Begründen Sie Ihre Antwort ausführlich.Modellieren Sie mit der gefundenen Formel als kleines Beispiel folgen-de Situation: Kunibert sagt: „Es regnet“ mittels den beiden aussagen-logischen Variablen KR für Kunibert ist Ritter und R für Es regnet.Geben Sie für die Formel eine Wahrheitstafel an und interpretierenSie das Ergebnis.

(b) Sie fragen alle Drei, ob sie Ritter oder Schurken seien. Kunibert sagt:„Einer von den beiden anderen ist ein Schurke.“ Hotzenblotz sagt:„Wenn das wahr ist, dann ist Siegfried der Schurke.“ Siegfried sagt:„Hotzenblotz ist nur ein Schurke, wenn Kunibert die Wahrheit gesagthat.“


Können Sie entscheiden, wer von den Dreien Ritter oder Schurke ist?Begründen Sie Ihre Antwort ausführlich durch z.B. Berechnung / Um-formung oder eine Wahrheitstafel.

38. Modellierung (? Punkte)Meiko möchte seinen Geburtstag feiern. Leider sind seine Freunde Emma-nuela, Samuel, Ronja und Neo recht schwierig. Und zwar ist es so, dass

• Emmanuela kommt nur, wenn auch Samuel kommt.• Samuel kommt nur, wenn Ronja kommt.• Wenn wiederum Ronja kommt, kommt auch Neo.• Wenn allerdings Samuel und Neo kommen, kommt Ronja nicht.• Neo kommt nur, wenn Emmauela oder Samuel kommen.

(a) Stellen Sie eine aussagenlogische Formel auf, die die obige Situationbeschreibt.

(b) Zeigen Sie, dass keiner dieser vier Freunde zu Meikos Geburtstagsfeierkommt.

39. Modellierung (? Punkte)Modellieren Sie die nachfolgenden Argumentationen und beantworten Siedie Fragen mittels Resolution. Gegeben seien dazu die nachfolgenden Vor-aussetzungen:

(a) Peter bekommt in der Prüfung eine gute Note genau dann, wenn erlernt, alle Vorlesungen besucht und genügend schläft.

(b) Peter kann nicht genügend schlafen, wenn er ständig in die Disko geht.(c) Peter besucht alle Vorlesungen, lernt, geht ständig in die Disko und

wird dort von seinem Professor gesehen.

Erste Frage: Bekommt Peter in der Prüfung eine gute Note ?

Zweite Frage: Zu welchem Ergebnis kommen Sie, wenn die erste Prämissedurch nachfolgende ersetzt wird ?(a’) Wenn Peter lernt oder alle Vorlesungen besucht oder genügend schläft,so bekommt er in der Prüfung eine gute Note.

40. Modellierung (? Punkte)Anja, Bernd und Claudia wollen nach Schweden fahren. Da dort insbesonde-re Alkohol sehr teuer ist, wollen sie Aquavit, Bier und Cognac mitnehmen.Wie jeder weiß, gehört zu jedem Gläschen Aquavit ein Bierchen, vertragensich Bier und Cognac nicht, und ist Cognac nicht gern allein im Magen.

Man zeige, dass sich die drei die Flasche Cognac sparen können, indemman


(a) eine Wahrheitstafel aufstellt.(b) mit Hilfe fundamentaler Äquivalenzen zeigt, dass obige Aussagen zu-

sammengefasst werden können zu der Formel „Niemals Cognac undwenn Aquavit, dann auch Bier.“

41. Modellierung (? Punkte)Vor dem letzten Geburtstag des Bären planten der Hamster und der Wolfeinen Kuchen für den Bären zu backen. Über das Rezept gerieten Sie jedochin Streit. Der Wolf sagte: „Wenn Eier in den Kuchen kommen, dann isst derBär nichts von dem Kuchen!“. Der Hamster widersprach: „Fehlen die Eier,dann kann man keinen Apfelkuchen backen! Und der Bär isst genau dannKuchen, wenn es Apfelkuchen gibt.“ „Aber der Bär muss von dem Kuchenessen!“ entgegnete der Wolf.

(a) Stellen Sie eine aussagenlogische Formel auf, die die obige Situationbeschreibt.

(b) Prüfen Sie mittels Resolutions-Kalkül, ob dies ein korrektes Ende derGeschichte sein könnte: Da rief der Hamster: „Das geht doch garnicht!“ − „Wir müssen das aber hin bekommen!“ brüllte der Wolf. DerWolf verbat dem Hamster darauf hin das Durchqueren seines Waldesund versuchte erfolglos den Kuchen zu backen.

42. Modellierung (? Punkte)Ein Bäcker möchte Rosinenbrötchen backen. Leider hat er nicht alle nötigenZutaten (ihm fehlen die Rosinen), er kann jedoch einige vorhandene Zutatengegen andere tauschen, und zwar:

• Mehl + Eier → Milch + Honig• Mandeln + Honig → Rosinen• Milch + Hefe → Mandeln• In großer Menge vorhanden sind Mehl, Eier und Hefe.

(a) Übersetzen Sie die Aussagen in aussagenlogische Formeln und formu-lieren Sie die Frage, ob der Bäcker Rosinen erhält, als Unerfüllbar-keitsproblem.

(b) Stellen Sie für die Formel aus (a) ein Prolog–Programm auf.

43. Modellierung (? Punkte)Der Fakultätsrat eines norddeutschen Informatikdepartements beschloss ei-ne neue Prüfungsordnung für einen Bachelorstudiengang. Es werden Schei-ne für die Fächer Theologik, Praxologie und Schaltkreislöten sowie für einGrünkohlpraktikum vergeben. Für den Bachelorabschluss müssen alle fol-genden Bedingungen erfüllt werden:


(a) Wurde ein Grünkohlschein nicht erworben, so muss ein Praxologiescheinvorhanden sein.

(b) Fehlt der Praxologieschein oder fehlt der Schaltkreisschein, so müssender Theologikschein und der Grünkohlschein vorhanden sein.

(c) Wurden weder der Theologikschein noch der Praxologieschein erwor-ben, so müssen der Schaltkreisschein und der Grünkohlschein vorhan-den sein.

Das zuständige Kultusministerium lehnte die Prüfungsordnung wegen „un-durchsichtiger Formulierungen“ ab. Das Departement wurde aufgefordert,die Scheinerwerbsbedingungen so umzuformulieren, dass möglichst wenige,einfache Alternativen entstehen. Helfen Sie dem Dekan bei dieser schwerenArbeit!

44. Modellierung (? Punkte)Nachdem Ensel und Krete die Hexe in den Ofen gestoßen haben, wollen siesich nun über das Knusperhäuschen hermachen. Aber wie allgemein bekanntist, muss man beim Verspeisen eines solchen Hauses sehr vorsichtig sein,da diese Häuser zur Instabilität neigen. Die beiden wenden sich zunächsteiner Wand zu, die aus drei Lebkuchen besteht. Da Ensel erfolgreich Knus-perhäuschenarchitektur studiert hat, erkennt er, dass folgende drei Regelnaus Sicherheitsgründen unbedingt einzuhalten sind:

• Von den beiden ersten Lebkuchen darf höchstens einer entfernt werden.

• Wenn man den dritten entfernt, muss man auch den zweiten entfer-nen.

• Wenn man den zweiten entfernt und den ersten nicht, dann darf manden dritten nicht entfernen.

Da Krete in Logik aufgepasst hat, weiss sie, dass man vom dritten Lebkuchenbesser die Finger lässt.

(a) Stellen Sie für die beschriebenen Regeln eine aussagenlogische Formelauf.

(b) Prüfen Sie mittels Resolutions-Kalkül, ob Krete Recht hat.

(c) Prüfen Sie mittels Wahrheitstafel, ob Krete Recht hat.

45. Äquivalenz und Implikation (? Punkte)In einer Theorieklausur wird von den Studierenden der Nachweis der Null-teilerfreiheit in Körperstrukturen verlangt. Unter Beschränkung auf die Aus-sagenlogik soll also die Gültigkeit des Ausdrucks

(1)(a ∧ b = 0)→ (a = 0 ∨ b = 0)


(für alle a,b des Körpers) gezeigt werden. Diese Aufgabe steht hier nichtan!! Sondern: Bei der Korrektur stellt es sich heraus, dass eine Reihe vonStudenten nicht (1), sondern andere Aussagen bewiesen haben, nämlich

(2)((a = 0) ∧ (b = 0))→ (a ∧ b = 0)

(3)((a = 0) ∧ (b = 0))→ (a ∧ b = 0)

(4)(a ∧ b = 0)↔ (a = 0 ∨ b = 0)

Gefragt wird, mit welchen der Formeln (2) bis (4) zugleich – und zwar auslogischen Gründen – auch (1) bewiesen worden ist. Helfen Sie dem Professorbei der Korrektur, indem Sie die Äquivalenz bzw. Implikation der Ausdrücke(2) bis (4) bezüglich (1) zeigen.

Tipp: Formalisieren Sie gemäß A := (a = 0);B := (b = 0);C := ((a ∧b) = 0) und überlegen Sie den Nutzen von (konjunktiver oder disjunktiver)Normalform!

46. neue Junktoren (? Punkte)Zeigen Sie, dass die Junktorenmenge {◦, ⋆} vollständig für die Aussagen-logik ist. Das heißt, man kann jeden Junktor der Aussagenlogik mit Hilfedieser beiden Junktoren darstellen. Dabei sind ◦ (Replikation: „nur wenn ...,dann ...“) und ⋆ ((Postsektion: „das eine ohne das andere“) folgendermaßendefiniert:

a ⋆ b := a ∧ ¬b und a ◦ b := a ∨ ¬bDefinieren Sie ¬,∧ und ∨ ausschließlich mittels den beiden neuen Junktoren◦ und ⋆ und weisen Sie die Korrektheit mittels einer Wahrheitstafel oderdurch direkte Umformung nach. Beginnen Sie mit dem Junktor ¬.

47. neue Junktoren (? Punkte)Zeigen Sie jeweils, dass der Junktor | (Shefferscher Strich: „nicht sowohl ...als auch ...“) sowie der Junktor ⇓ (Peirce-Pfeil: „weder ... noch ...“) jeweilsvollständig für die Aussagenlogik sind. Das heißt, man kann jeden Junktorder Aussagenlogik mit Hilfe einer dieser beiden Junktoren darstellen. Dabeisind | und ⇓ folgendermaßen definiert:

a|b := ¬(a ∧ b) und a ⇓ b := (¬a) ∧ (¬b)

Definieren Sie ¬,∧ und ∨ ausschließlich mittels einem dieser beiden neuenJunktoren | und ⇓ und weisen Sie die Korrektheit mittels einer Wahrheits-tafel oder durch direkte Umformung nach. Beginnen Sie mit dem Junktor¬.

48. neue Junktoren (? Punkte)Zeigen Sie, dass die Junktorenmenge {→, ←} vollständig für die Aussagen-logik ist. Das heißt, man kann jeden Junktor der Aussagenlogik mit Hilfe


dieser beiden Junktoren darstellen. Dabei sind → (Implikation: „wenn ...dann ...“) und ← (Präsektion: „das andere ohne das eine“) folgendermaßendefiniert:

a→ b := ¬a ∨ b und a ≤ b := ¬a ∧ b

Definieren Sie ¬,∧ und ∨ ausschließlich mittels den beiden neuen Junktoren→ und ≤ und weisen Sie die Korrektheit mittels einer Wahrheitstafel oderdurch direkte Umformung nach. Beginnen Sie mit dem Junktor ¬.

49. Basis (? Punkte)Weisen Sie die Korrektheit mittels einer Wahrheitstafel oder durch direkteUmformung mittels den fundamentalen Äquivalenzen nach.

(a) Zeigen Sie, dass die Junktorenmenge {∧,¬} vollständig für die Aus-sagenlogik ist.

(b) Zeigen Sie, dass die Junktorenmenge {∨,¬} vollständig für die Aus-sagenlogik ist.

(c) Zeigen Sie, dass die Junktorenmenge {→,¬} vollständig für die Aus-sagenlogik ist.

(d) Zeigen Sie, dass die Junktorenmenge {|} (NAND, Shefferstrich) voll-ständig für die Aussagenlogik ist.

(e) Zeigen Sie, dass die Junktorenmenge {|} (NAND, Shefferscher Strich)vollständig für die Aussagenlogik ist.

Als bekannt vorausgesetzt ist, dass die Junktorenmenge {∧,∨,¬} vollständigfür die Aussagenlogik ist, also eine Basis bildet: man kann alle aussagenlo-gischen Formeln ausschließlich mit Hilfe dieser Junktoren darstellen.

50. KNF-Algorithmus (? Punkte)Erzeugen Sie durch Anwendung des KNF-Algorithmus (siehe Tipp) ausnachfolgender Formel eine KNF (Die Anwendung des Algorithmus mussaus der Dokumentation nachvollziehbar sein!):

F = (((¬(¬B)) ∨ A) ∧ ((¬A ∧ ¬(B ∧ ¬C)) ∨ (A ∧ (B ∧ ¬C))))

Wenden Sie auf die so erzeugte KNF die Tautologieregel und die Unerfüll-barkeitsregel sowie die Distributivregel an, um den Ausdruck zu vereinfa-chen. Jede Anwendung einer Äquivalenzregel ist deutlich zu markieren! AlsEndergebnis ist eine KNF zu erstellen, die maximal drei Disjunktionsgliederhat ((?1∨?2 ∨ . . .) ∧ (?1∨?2 ∨ . . .) ∧ (?1∨?2 ∨ . . .)).

51. KNF-Algorithmus (? Punkte)Erzeugen Sie ausschliesslich durch Anwendung des KNF-Algorithmus


(siehe Tipp) aus nachfolgender Formel eine KNF (Die Anwendung des Al-gorithmus muss aus der Dokumentation nachvollziehbar sein!):

F = ¬(([((P ↔ ¬S) ∧ (S → A)) ∧ (P → A)] ∧ P )→ ¬S)

52. DNF-Algorithmus (? Punkte)Erzeugen Sie durch Anwendung des DNF-Algorithmus (siehe Tipp) ausnachfolgender Formel eine DNF. Der DNF-Algorithmus arbeitet analog zudem KNF-Algorithmus, erzeugt jedoch eine disjunktive Normalform undkeine konjunktive Normalform! (Die Anwendung des Algorithmus muss ausder Dokumentation nachvollziehbar sein!):

F = (((¬(¬B)) ∨ A) ∧ ((¬A ∧ ¬(B ∧ ¬C)) ∨ (A ∧ (B ∧ ¬C))))

Wenden Sie auf die so erzeugte DNF die Idempotenzregel, Tautologieregel,Unerfüllbarkeitsregel sowie die Distributivregel an, um den Ausdruck zu ver-einfachen. Jede Anwendung einer Äquivalenzregel ist deutlich zu markieren!Als Endergebnis ist eine DNF zu erstellen, die maximal zwei Konjunktions-glieder hat ((?1∧?2 ∧ . . .) ∨ (?1∧?2 ∧ . . .)).

53. Resolutions-Kalkül (? Punkte)Geben Sie sämtliche Resolventen an, die aus den Klauseln der Klauselmenge

{{A,¬B,E}, {A,B,C}, {¬A,¬D,E}, {A,¬C}}

gewonnen werden können.

54. Resolutions-Kalkül (? Punkte)Kann bei der Resolution zweier Hornformeln eine Formel entstehen, diekeine Hornformel ist ?

55. Hornformel (? Punkte)Zeigen Sie, dass es nicht zu jeder aussagenlogischen Formel eine seman-tisch äquivalente Hornformel gibt. Tipp: Arbeiten Sie an einem konkretenBeispiel und mit der Belegung A.

56. Resolutions-Kalkül (? Punkte)Zeigen Sie mittels Resolutionsmethode, dass

F = ((¬A ∨B) ∧ (¬B ∨ C) ∧ (A ∨ ¬C) ∧ (A ∨B ∨ C) ∧ (¬A ∨ ¬B ∨ ¬C))

unerfüllbar ist, d.h. die leere Klausel hergeleitet werden kann.

57. Resolutions-Kalkül (? Punkte)Wenden Sie auf die nachfolgende Formel das Resolutions-Kalkül (Algorith-mus: siehe im Tipp) wie folgt an:


(a) Erzeugen Sie mittels den Klauseln alle direkten Resolventen.

(b) Erzeugen Sie alle Resolventen, die mittels Resolution aus der zu (¬b→c) gehörenden Klausel und jeweils den (unter (a), wie auch hier neu)erzeugten Resolventen entstehen, bis keine neuen Resolventen gebildetwerden können.

Transformieren Sie dazu nachvollziehbar die Formel in eine KNF (benötigteÄquivalenzen und Definitionen: siehe Tipp)

F = (¬b→ c) ∧ ((¬c→ b)→ a) ∧ (¬b→ (a→ ¬c))

58. Resolutions-Kalkül (? Punkte)Testen Sie mittels Resolution folgende KNF (ohne Vereinfachungen vorzu-nehmen!) auf Widersprüchlichkeit:

F = P ∧(¬P ∨A)∧(P ∨¬P )∧(P ∨S)∧S∧(¬S∨A)∧(¬S∨¬P )∧(¬S∨S)

Transformieren Sie dazu die Formel in die Mengenschreibweise. Identifizie-ren Sie die Klauseln und führen dann den Algorithmus aus.

59. Resolutions-Kalkül (? Punkte)Folgende vier Formeln seien gegeben:

P1 = (a ∧ b)→ ¬c P2 = (b ∨ c)→ a P3 = (a ∧ ¬b)→ ¬c P4 = ¬a→ c

Zeigen Sie mittels Resolutions-Kalkül, ob folgende Formeln eine Folgerungaus P = P1 ∧ P2 ∧ P3 ∧ P4 sind:

(a) F1 = a

(b) F2 = (a ∧ ¬c)(c) Wenn P5 = ¬(b→ b) zu P hinzugefügt wird, welchen Einfluss hat dies

auf die Folgerung einer beliebigen Formel F aus P ∧ P5 ?

60. Resolutions-Kalkül (? Punkte)Gegeben seien folgende Aussagen:

In einer Firma wird Team 1 die Projekte A und B vollenden,wenn die Statistik C vorliegt. Team 2 wird Projekt D vollen-den, wenn Projekt A fertig ist und die Statistik E vorliegt.Team 3 wird Projekt F fertig stellen, wenn die Projekte Bund D abgeschlossen sind.

(a) Übersetzen Sie diesen Text in eine aussagenlogische Hornformel (Nureine Schlußfolgerung bei →!). Bestimmen Sie dazu zunächst die ele-mentaren/atomaren Aussagen (im Sinne aussagenlogischer Variablen)


und ordnen Sie diesen Buchstaben als Abkürzung zu; Beispiel: K =„Ich habe Recht“.Hinweis: Verwenden Sie die Symbole →,∧,∨,¬.

(b) Erzeugen Sie ausschließlich durch Anwendung des KNF-Algorithmus(siehe Tipp) aus der in (a) gewonnenen Formel eine KNF (Die An-wendung des Algorithmus muss aus der Dokumentation nachvollzieh-bar sein!).

(c) Kann Projekt F fertig gestellt werden, wenn die Statistiken C und Evorliegen ?Formulieren Sie diese Frage als eine aussagenlogische Formel, negierenSie diese Formel und transformieren Sie diese (gemäß dem Algorith-mus) in eine KNF. Verknüpfen Sie nun diese KNF mittels ∧ mit der in(b) erhaltenen KNF zu einer neuen KNF und testen Sie diese Formelmittels dem Resolutions-Kalkül (siehe Tipp) auf Widersprüchlichkeit.

61. Resolutions-Kalkül (? Punkte)Zeigen Sie mittels Resolutions-Kalkül, dass nachfolgende Formel eine Tau-tologie ist:

(A ∧ (¬B → ¬A))→ B

Zeigen Sie zusätzlich mittels Wahrheitstafel, dass diese Formel eine Tauto-logie ist.

62. Resolutions-Kalkül (? Punkte)

(a) Zwei Formeln F und G schließen einander aus, wenn es keine Inter-pretation gibt, welche beide Formeln erfüllt. Wie kann man mit demResolutions-Kalkül prüfen, ob zwei Formeln F und G einander aus-schließen ?

(b) Zeigen bzw. begründen Sie, dass sich die Erfüllbarkeit einer Klausel-menge K nicht ändert, wenn man aus K alle Klauseln ausschließt bzw.löscht, die eine Variable enthalten, welche nur positiv oder nur negativin K vorkommt.

(c) Verwenden Sie die Methoden aus Teil (a) und (b), um zu zeigen, dass

F := (X → (Y ∨Z))∧(Z → V )∧(Y ∨V )∧(Z → (¬X∨V ))∧(V ∨¬Y ∨¬Z)

und

G := ((Z∧¬V )→ X)∧¬(¬V ∨¬Z)∧(X → (V ∨Z))∧(V ∨¬X∨¬Y )∧

((¬V ∧ ¬X)→ (Y ∨ Z)) ∧ ¬(¬V ∧X)

einander nicht ausschließen.


63. Modellierung (?? Punkte)Eine Person macht die folgenden Aussagen:

• Wenn ich genug Geld gespart habe, kaufe ich mir ein Auto.

• Wenn ich nicht genug Geld gespart habe, kaufe ich mir ein Fahrrad.

• Wenn ich ein Auto kaufe, fahre ich nach Spanien in den Urlaub.

• Wenn ich ein Fahrrad kaufe, bleibe ich im Urlaub daheim.

• Ich habe im Vorjahr gespartes Geld verbraucht.

• In diesem Jahr habe ich andere Ausgaben.

• Es stimmt nicht, dass ich nicht genug Geld gespart habe und im Vor-jahr gespartes Geld verbraucht habe und in diesem Jahr andere Aus-gaben habe.

Fährt diese Person nach Spanien in den Urlaub?

(a) Modellieren Sie die Aussagen als aussagenlogische Formel und trans-formieren Sie diese in eine KNF.

(b) Stellt die resultierende KNF eine Hornformel dar ? Wenn nicht, welcheKlauseln sind keine Horn-Klauseln ?Würde Ihnen es gelingen, die Formel in eine Hornformel zu transfor-mieren, wenn Sie für bestimmte aussagenlogische Variablen, z.B. dieVariable L, eine Ersetzung der Art L :≡ ¬L (und ¬L :≡ L) vorneh-men würden ?

(c) Lösen Sie die Fragestellung mittels dem Resolutions-Kalkül.

64. Modellierung (? Punkte)Für die Informatikstudierenden Anton, Berta, Charlie und Dora steht dem-nächst die Klausur „Mathematische Grundlagen“ an. Eigentlich wollen siedie ins nächste Semester verschieben. Sie beschließen aber, dass mindestenseiner von ihnen an dieser Klausur teilnehmen sollte, damit sie wissen, wasdrankommt. Charlie weigert sich grundsätzlich, zu dieser Klausur zu gehen.Da Anton und Dora auf ihre gemeinsame kleine Schwester aufpassen müs-sen, kann höchstens einer von beiden zur Klausur gehen. Dora geht nur zurKlausur, wenn auch ihre beste Freundin Esmeralda hingeht. Wenn Esme-ralda an der Klausur teilnimmt, dann auch Anton.

(a) Stellen Sie eine aussagenlogische Formel auf, die die obige Situationbzgl. Teilnahme an dieser Klausur beschreibt.

(b) Angenommen, Berta wird krank und kann an dieser Klausur nichtteilnehmen. Zeigen Sie mittels Resolutions-Kalkül, dass dann Antonzur Klausur geht und Dora nicht.


65. Modellierung (? Punkte)Inspektor Columbo hat einen Fall zu lösen. Er hat drei Personen in Ver-dacht, die Tat (eventuell gemeinschaftlich) begangen zu haben. Als Täterkommen nur Martin,Franz oder Stefan in Frage. Inspektor Columbo hat diefolgenden Informationen:

(a) Wenn Martin schuldig und Franz unschuldig ist, so ist Stefan schuldig.

(b) Stefan arbeitet niemals allein.

(c) Martin arbeitet niemals mit Stefan.

(d) Nur Martin, Franz oder Stefan kommen als Täter in Frage.

Formulieren Sie diese Sachverhalte als aussagenlogische Formeln und zeigenSie mittels Resolution, dass Franz ein Täter ist.

Tipp: Wie jemand arbeitet ist so direkt nicht interessant. Zur Lösung isthier mehr gefragt, welche Folgerung dies auf die Täterschaft hat! Also: aus-nahmsweise vor der Modellierung etwas nachdenken!

66. Modellierung (? Punkte)Wenn keine Klausur geschrieben wird, sind die Studenten glücklich. Wenndie Studenten glücklich sind, fühlt sich der Dozent wohl. Wenn sich aberder Dozent wohl fühlt, dann hat er keine Lust, Vorlesung zu halten. Wirdaber keine Klausur geschrieben, dann hat er Lust, Vorlesung zu halten. Alsowird eine Klausur geschrieben.

(a) Formalisieren Sie den vorliegenden Text als aussagenlogische Formel.

(b) Untersuchen Sie, ob ein korrekter Schluß vorliegt.

67. Modellierung (? Punkte)Schneewittchen möchte in die Stadt einkaufen gehen und die Zwerge be-schließen, dass mindestens einer von ihnen sie begleitet. Drei der Zwergescheiden als Begleitung aus, da sie Holz hacken müssen. Die möglichen Be-gleiter, die Zwerge Alberich, Gimli, Rübezahl und Zwergnase, diskutieren,wer mit in die Stadt geht.

• Alberich: “Wenn Gimli nicht geht und Rübezahl nicht geht, dann geh’ich auch nicht.“

• Gimli: „Ich gehe nur, wenn Rübezahl oder Zwergnase mitgehen.“

• Rübezahl: „Wenn Gimli nicht geht, dann gehe ich auch nicht.“

• Zwergnase: „Ich gehe nur, wenn Gimli nicht mitkommt. Wenn Rü-bezahl geht, dann will ich auf jeden Fall mit.“


Zeigen Sie mit Hilfe des Resolutions-Kalkül, dass die vier Zwerge nur zu-frieden sind, wenn Zwergnase als einziger mit Schneewittchen in die Stadtgeht.

68. strukturelle Induktion (? Punkte)Für jede aussagenlogische Formel F und jede aussagenlogische VariableP,Q, sei F [P 7→ Q] die Formel, die durch das Ersetzen aller Vorkommenvon P in F durch Q entsteht. Beispiele:

(P∧R)[P 7→ Q] = Q∧R ((P → R)∧(P∨Q))[P 7→ Q] = ((Q→ R)∧(Q∨Q))

(R ∨ S)[P 7→ Q] = R ∨ S P [P 7→ Q] = Q R[P 7→ Q] = R

Beweisen Sie folgende Behauptung durch strukturelle Induktion (ähnlichvollständiger Induktion, jedoch nicht über n, sondern über den strukturellenAufbau): Sei A die Interpretation (und Belegung) von Formeln der Aus-sagenlogik, mit A(P ) = A(Q), d.h. P und Q sind unter A semantischäquivalent. Dann gilt für jede Formel F : A(F ) = A(F [P 7→ Q]).

Hinweis: Sie können der Einfachheit halber statt der natürlichsprachlichen,etwas aufwendigeren Schreibweise, bei der Interpretation A dies wie folgtschreiben: A(¬F ) ≡ ¬A(F ) bzw. A(F1 ∧ F2) ≡ A(F1) ∧A(F2). Die Induk-tionsbehauptung bezieht sich auf die echten Teilformeln einer Formel.

69. Modellierung (? Punkte)Gegeben seien die folgenden Aussagen:

• (P1) Wenn dieses Argument schlüssig ist und alle Prämissen diesesArguments wahr sind, dann ist dieses Argument korrekt.

• (P2) Wenn die Prämissen dieses Arguments die Konklusion dieses Ar-guments implizieren, dann ist dieses Argument schlüssig.

• (P3) Die Prämissen dieses Arguments implizieren die Konklusion die-ses Arguments.

• (F ) Dieses Argument ist korrekt.

(a) Übersetzen Sie obige Aussagen jeweils in eine Formel der Aussagenlo-gik.

(b) Weisen Sie nach, dass die Formel PF kontingent ist.

(c) Ergänzen Sie eine vierte Prämisse P4 (ohne dass sich die Prämissendann widersprechen) in der Formel PF , sodass die um diese Prämisseerweiterte Formel PF2 eine Tautologie ist. Weisen Sie dies mittelsTableaukalkül nach.


70. Modellierung (? Punkte)Ede, Max und Otto werden des Diebstahls verdächtigt. Sie können jeweilsein notorischer Lügner sein, d.h. nicht die Wahrheit sagen, oder ehrlichsein.

• Otto sagt: „Ede ist der Täter!“• Ede sagt: „Ich bin unschuldig!“• Max sagt: „Otto lügt!“

(a) Ermitteln Sie mittels Tableaukalkül die Modelle der zugehörigen logi-schen Formel. Wer ist jeweils der Täter?

(b) Welche Lösung (welches Modell) erhalten Sie, wenn Sie erfahren, dasszwei von ihnen notorische Lügner sind und nur einer ehrlich ist?

71. Modellierung (? Punkte)Die Suche nach Iasons Goldenem Vlies führt Indiana Jones zu einem ver-borgenen Tempel. Der Öffnungsmechanismus des Eingangs wird von dreiHebeln gesteuert, die sich in der Wand befinden. Aus seinem Studium dergriechischen Mythologie weiß Indiana, dass er

• mindestens einen Hebel ziehen muss.• Hebel 1 nicht ziehen darf, wenn er nicht ebenfalls Hebel 2 oder Hebel

3 zieht.• auf keinen Fall beide Hebel 1 und Hebel 3 ziehen darf.• Hebel 2 und Hebel 3 entweder beide ziehen muss oder beide nicht ziehen

darf.

(a) Stellen Sie eine aussagenlogische Formel auf, die die Regeln für dieÖffnung des Tempels beschreibt.

(b) Ermitteln Sie mittels Tableaukalkül die Modelle der zugehörigen logi-schen Formel: Welche Hebelkonstellation führt zur Öffnung des Tem-pels ?

72. Tableaukalkül (? Punkte)Wenden Sie auf die nachfolgende Formel das Tableaukalkül vollständigan, d.h. bis keine Expantionen mehr möglich sind (Regeln siehe im Tipp).Zeichnen Sie dazu den entstehenden Baum so, dass die Konstruktion, alsoder Ablauf deutlich wird. Die Formel ist direkt, d.h. ohne Umformung zuverwenden!

F = (a→ b) ∧ (b↔ ¬c) ∧ (c→ a)

Sofern kein Widerspruch gefunden wird: geben Sie bitte alle Modelle an, diedie Formel wahr machen.


73. Tableaukalkül (? Punkte)Wenden Sie auf die nachfolgenden Formeln das Tableaukalkül vollständigan und entscheiden Sie mit diesem Verfahren, ob die Formeln erfüllbar oderunerfüllbar sind. Geben Sie im Falle der Erfüllbarkeit alle Modelle gemäßTableaukalkül der Formel an.

(a) F1 ≡ (A→ (¬A ∧B)) ∧ ((B ↔ ¬C) ∧ C)

(b) F2 ≡ ((A↔ ¬B) ∧ (B → C)) ∧ ((C → A) ∧ (A ∧B))


Aufgabe A.3 (Prädikatenlogik) 1. PL versus AL (? Punkte)Erklären Sie folgende Unterschiede zwischen Aussagenlogik und Prädikaten-logik 1-ter Stufe:

(a) Welcher syntaktische Unterschied besteht ?(b) Welcher semantische Unterschied besteht ?(c) Was wird in einer Domäne bzw. einem Universum „geregelt“ ? Wer

übernimmt diese Rolle bei der Aussagenlogik ?(d) Betrachten Sie nachfolgende prädikatenlogische Formel, wobei A,O Prä-

dikate seien, bi,t Konstanten (nullstellige Funktionen) und X,Y,Z Funk-tionsvariablen. Wie könnte dies in der Aussagenlogik formuliert wer-den ? Zeigen Sie nur einen möglichen Ansatz an Hand von Beispielen.Zeigen Sie auf, was transformiert werden kann und was nicht und ma-chen Sie daran deutlich, was der Unterschied bzgl. der Ausdruckskraftder Aussagenlogik und der Prädikatenlogik ist, also z.B. bzgl. dem, wasman aufschreiben kann oder/und bzgl. den möglichen Fragestellungen,die man an das System stellen kann.

A(b3, b1) ∧ A(b1, t) ∧ A(b4, b2) ∧ A(b2, t)∧

(A(X, Y )→ O(X,Y )) ∧ ((A(X, Y ) ∧O(Y, Z))→ O(X,Z))

2. Formel (? Punkte)Gegeben sei folgende prädikatenlogische Formel F :

F = ¬(∀x1 : ∃x2 : P2(f1(x1, x2, f2(x1)))) ∧ P1(x2, f3)

Geben Sie sämtliche Teilformeln von F an, sowie alle in F vorkommendenTerme und bestimmen Sie für jedes Vorkommen einer Variablen, ob sie freioder gebunden ist.

3. Formel (? Punkte)Gegeben sei folgende prädikatenlogische Formel F :

F = ¬(∀x1 : (P1(x1, x2)→ P2(f(x1)))) ∧ ∀x1 : ∀x2 : P1(x1, f(x2))

Geben Sie sämtliche Teilformeln von F an, sowie alle in F vorkommendenTerme und bestimmen Sie für jedes Vorkommen einer Variablen, ob sie freioder gebunden ist.

4. Struktur (? Punkte)Gegeben sei folgende Formel:

F = ∀x∃yP (x, y, f(z)).

Man gebe eine Struktur A an, die Modell für F ist, und eine Struktur B,die kein Modell für F ist.


5. Struktur (? Punkte)Gegeben sei folgende prädikatenlogische Formel F :

F = Q(x1) ∨ (∀x2 : P (x1, g(x2))) ∨ (∃x3 : ∀x4 : (P (f(x3), x4) ∧Q(a)))

(a) Geben Sie eine passende Struktur an, die diese Formel immer wahrmacht, die also ein Modell für diese Formel ist und weisen Sie diesnach!

(b) Geben Sie eine zweite passende Struktur an, die (bzgl. der Belegung derfreien Variablen) diese Formel sowohl wahr wie auch falsch macht, diealso kein Modell der Formel ist und weisen Sie dies nach!

(c) Geben Sie eine dritte passende Struktur an, die diese Formel immerfalsch macht, die also kein Modell der Formel ist.

6. Struktur (? Punkte)Bestimmen Sie für jede der folgenden prädikatenlogischen Formeln, ob sieeine Tautologie ist oder ein Widerspruch ist oder keines von beiden. Ge-ben Sie für jede Formel, die weder eine Tautologie noch ein Widerspruchist, eine passende Struktur an, die ein Modell für die Formel ist, und einepassende Struktur, die kein Modell der Formel ist. Weisen Sie dies jeweilsnach!

F1 = ∀x : (P (x) ∨ (∃y : Q(y, x))) F2 = ∃x : (R(x, f(x)))

7. Struktur für Äquivalenz (? Punkte)Gegeben seien die Formeln F1, F2, F3, die gerade die Reflexivität, Symmetrieund Transitivität des zweistelligen Prädikates P „besagen“.

F1 = ∀xP (x, x)

F2 = ∀x∀y[P (x, y)→ P (y, x)]

F3 = ∀x∀y∀z[P (x, y) ∧ P (y, z)→ P (x, z)]

Man zeige, dass keine dieser Formeln Folgerung der anderen beiden ist,indem man für jedes Formelpaar ein Modell angibt, das aber nicht Modellfür die jeweils dritte Formel ist.

8. Struktur (? Punkte)Welche der folgenden Strukturen sind Modelle für die Formel F ?

F = ∃x∃y∃z : [P (x, y) ∧ P (z, y) ∧ P (x, z) ∧ ¬P (z, x)]

(a) A = (UA, IA), wobei UA = N, PA = {(m,n)|m,n ∈ N ∧m < n}.(b) A = (UA, IA), wobei UA = N, PA = {(m,n)|m,n ∈ N ∧m+ 1 = n}.


(c) A = (UA, IA), wobei UA = N, PA = {(m,n)|m ∈ Nm = n}.(d) A = (UA, IA), wobei UA = 2N (die Potenzmenge von N, also die Menge

aller Teilmengen von N), PA = {(X, Y )|X, Y ⊆ N ∧X ⊆ Y }.

Begründen Sie Ihre Antwort durch Dokumentation des Nachweises!

9. Struktur (? Punkte)Gegeben sei folgende semantische Struktur:

• Es sei U := Z = {. . .− 3,−2,−1, 0, 1, 2, 3, . . .} die Menge der ganzenZahlen,

• I(f) := U2 → U ; mit f(x, y) = |x− y|, wobei | | die Betragsfunktionist;

• I(P ) := {(x, y) ∈ U2|x > y},• I(Q) := {x ∈ U |x ist gerade },

Bestimmen Sie den Wahrheitswert nachfolgender prädikatenlogischer For-mel. Dabei sei für die freie Variable z der Wert −1 zu verwenden.

F = (¬∃x : ((∃y : P (z, f(x, y))) ∨ (∀z : Q(z)))) ∨ (∀x : Q(x))

10. Struktur (? Punkte)Sei A = (UA, IA) eine Struktur mit folgenden Elementen:

• UA := N (Universum);

• IA(c) := 2 (Konstante c);

• IA(f) := ∀n ∈ UA : n 7→ n2 (Funktion f);

• IA(R) := {m ∈ UA|m ≥ 4} (Prädikat R);

• IA(S) := {(n,m)|n,m ∈ UA und n < m} (Prädikat S);

• IA(x) := 1 (freie Variable x);

Bestimmen Sie jeweils (mit detailliertem Lösungsweg) den Wert von

(a) A(S(f(c), x) ∨ S(c, f(x)))

(b) A(∃x : (R(f(c)) ∧ S(x, f(x))))

11. Struktur (? Punkte)Gegeben sei folgende prädikatenlogische Formel G:

G ≡ (∀x : ∃y : R(x, y)) ∧ (∀x : ∃y : ¬R(x, y))∧

(∀x : ∀y : ∀z : (R(x, y) ∧R(y, z)→ R(x, z)))


(a) Die Formel G ist erfüllbar. Geben Sie von allen Strukturen, die einModell von G sind, eine Struktur A = (UA, IA) an, bei der die Anzahlder Elemente des Universums minimal ist. Achtung: das Universumdarf nicht leer sein!Zeigen Sie, dass Ihre gewählte Struktur tatsächlich ein Modell der For-mel G ist!

(b) Zeigen Sie, dass Ihre in (a) angegebene Struktur tatsächlich minimalist. Das heißt, es gibt kein Modell von G, dessen Universum wenigerElemente enthält. Beginnen Sie dazu bei dem kleinst möglichen Uni-versum mit nur genau einem Element und zeigen Sie ggf. dass mandamit keine Lösung finden kann. Angenommen Sie haben unter (a)ein Universum der Größe 4 entwickelt. Dann müssen Sie hier in derTeilaufgabe für die Größen 1,2 und 3 zeigen, dass man damit keineLösung erzeugen kann.

12. Struktur (? Punkte)Gegeben sei folgende Formel:

(∀x : (∀y : P (f(y), x))) ∧ ¬(∀x : (¬Q(f(y))→ ¬P (y, x)))

(a) Transformieren Sie die Formel in Skolemnormalform (Sichtbarkeit dergebundenen Variablen beachten!)

(b) Finden Sie eine Struktur, die Modell der Formel ist. Weisen Sie diesauch nach!

(c) Finden Sie eine Struktur, die kein Modell der Formel ist. Weisen Siedies auch nach!

13. Struktur (? Punkte)Gegeben sei folgende prädikatenlogische Formel F :

F = ∀x : ∀y : (P (x, y)⇒ P (x, f (y)))

und folgende prädikatenlogische Formel G:

G = ∀x : ∀y : (P (x, y)⇒ P (f (x) , y))

Finden Sie eine Struktur, die Modell für F ist, die jedoch kein Modell fürG ist, und eine Struktur, die Modell für G ist, welche jedoch kein Modellfür F ist.

14. Variablen (? Punkte)In dieser Aufgabe geht es um den Unterschied zwischen durch Allquantorengebundene Variablen und freien Variablen, aber auch die Gemeinsamkeitendieser Variablen.

Es sei F eine prädikatenlogische Formel, die die Variable x enthält.


(a) Zeigen Sie: Ist ∀x : F wahr, so ist auch F wahr. (∀x : F |= F , d.h.aus ∀x : F folgt semantisch F .)

(b) Geben Sie ein Beispiel für eine Formel F an, so dass wenn F wahrist ∀F nicht wahr ist. (F |= ∀x : F , d.h. aus F folgt semantisch nicht∀x : F .)

(c) Zeigen Sie: Wenn F eine Tautologie ist (bzw. allgemeingültig ist), dannist auch ∀x : F eine Tautologie (bzw. allgemeingültig).

(d) Zeigen Sie: Wenn ∀x : F eine Tautologie ist (bzw. allgemeingültig ist),dann ist auch F eine Tautologie (bzw. allgemeingültig).

Hinweis: Verwenden Sie bei Ihrem Nachweis eine (allgemeine oder spezifi-sche) Struktur A!

15. Modellierung (? Punkte)Archer und T’Pol finden während ihres Aufenthalts auf Wahrlüg Folgendesheraus:

• Eine Person vom Stamm der Xur vermählt sich nur mit jemandemvom Stamm der Xur oder der Yzy. Polits vermählen sich nie, weil sieauf eine entscheidende Frage immer mit „nein“ zu antworten pflegen.

• Ein Bewohner von Wahrlüg ist nur dann ein Xur, wenn die Elternbeide Xur oder beide Yzy sind.

Geben Sie eine passende Struktur an und modellieren die beiden Tatsachenals prädikatenlogische Formel.

16. Modellierung (? Punkte)Gegeben sei folgende Aussage:

„Kein Kind mag jedes Gemüse, aber jedes Kind mag irgendein Gemüse.“

(a) Formulieren Sie die Aussage als prädikatenlogische Formel. Geben Siedazu eine passende Struktur an, wobei folgende Prädikate zu verwen-den sind: mag(X,Y), mit der Semantik „X mag Y“, kind(X) mit derSemantik „X ist ein Kind“ und gemüse(X) mit der Semantik „Y ist einGemüse“.

(b) In der vorangegangenen Modellierung haben Sie evtl. Quantoren be-nutzt. Um den korrekten Einsatz zu prüfen, zeigen Sie bitte die Uner-füllbarkeit der nachfolgenden Formel mittels Resolution.

¬((∃y∀x : P (x, y))→ (∀x∃y : P (x, y)))


(c) Zeigen Sie zudem bitte das nachfolgende Formel kontingent ist, indemSie geeignete passende Strukturen angeben.

(∀x∃y : P (x, y))→ (∃y∀x : P (x, y))

(d) Gilt dann folgende Äquivalenz ?

(∃y∀x : P (x, y))↔ (∀x∃y : P (x, y))

17. Modellierung (? Punkte)Formulieren Sie die nachfolgenden Aussagen über die Bewohner von Trans-sylvanien (die Mensch oder Vampir sind) als prädikatenlogische Formeln.Bestimmen Sie dazu zunächst die elementaren/atomaren Elemente (im Sin-ne von Prädikaten und Funktionen) und ordnen Sie diesen Buchstaben alsAbkürzung zu. Versuchen Sie die Anzahl dieser Elemente klein zu halten(Denken Sie an die in den Formeln verwendbare Negation!).

(a) „Alle geisteskranken Vampire sagen die Wahrheit.“

(b) „Ist ein Mensch geistig gesund, so ist mindestens einer seiner Eltern-teile geistig gesund.“

(c) „Vampire heiraten nur Vampire.“

(d) „Alle geisteskranken Vampire haben mindestens ein Kind.“

Bestimmen Sie auch die Menge U (das Universum) aller möglichen Wer-te/Individuen etc. Bestimmen Sie dann die Interpretation I für die Prädi-kate (durch informales Auswahlkriterium) und die Funktionen (durch infor-male Angabe der Berechnungsvorschrift). Vorgabe: Mutter und Vater sindals Funktionen zu modellieren.

Beispiel: U = {alle Teilnehmer der Logik und Berechenbarkeit Klausur;alle Matrikelnummern der Teilnehmer; }, I(P ) := {x ∈ U |x hat die PVL}, I(f) := U → U ; mit f(x) = y, falls y ist Matrikelnummer von x.

18. Modellierung (? Punkte)Gegeben seien folgende Tatsachen:

• Ein Bewohner Transsylvaniens ist wahnsinnig, wenn alle seine KinderVampire sind.

• Alle Mondsüchtigen sind Vampire.

• Ist ein Bewohner Transsylvaniens nicht mondsüchtig, so ist auch kei-ner seiner Elternteile mondsüchtig.


(a) Formulieren Sie die nachfolgenden Aussagen über die Bewohner vonTranssylvanien (die Mensch oder Vampir sind) als prädikatenlogischeFormeln. Bestimmen Sie dazu zunächst die elementaren/atomaren Ele-mente (im Sinne von Prädikaten und Funktionen) und ordnen Sie die-sen Buchstaben als Abkürzung zu. Versuchen Sie die Anzahl dieserElemente klein zu halten (Denken Sie an die in den Formeln verwend-bare Negation!).

(b) Überprüfen Sie mittels Resolutions-Kalkül, ob die Folgerung, dass alleMondsüchtigen wahnsinnig sind, korrekt ist.

19. Modellierung (? Punkte)Formulieren Sie die nachfolgenden Aussagen über die Jagd nach dem Rie-senkaninchen als prädikatenlogische Formeln. Geben Sie dazu zunächst einegeeignete Struktur an!

Vorgaben: Das Riesenkaninchen ist als eine Konstante (0-stellige Funkti-on) und Mutter als 1-stellige Funktion zu modellieren. Weitere Funktionensind nicht zugelassen. Als Prädikate können Sie nur verwenden „x hat einschwarzes Fell“ und „x isst gerne Gemüse“. Weitere Prädikate sind nichterlaubt.

Beispiel für die vorzunehmende Formalisierung: U = {alle Teilnehmer derLogik und Berechenbarkeit Klausur; alle Matrikelnummern der Teilnehmer;}, I(P ) := {x ∈ U |x hat die PVL }, I(f) := U → U ; mit f(x) = y, falls yist Matrikelnummer von x.

Um dem Riesenkaninchen auf die Schliche zu kommen, startet Wallace undGromit eine Untersuchung und finden über die Kaninchen des Dorfes Fol-gendes heraus:

(a) Zeugenaussagen belegen, dass das Riesenkaninchen kein schwarzes Fellhat.

(b) Alle Kaninchen, die kein schwarzes Fell haben, essen nur gerne Ge-müse.

(c) Hat ein weibliches Kaninchen schwarzes Fell, so auch alle seine Kin-der.

(d) Es ist unmöglich, dass ein weibliches Kaninchen, das nur Gemüse isst,Mutter des Riesenkaninchens ist.

Gromit schließt aus den Tatsachen, dass das Riesenkaninchen eigentlichgar kein Kaninchen ist. Zeigen Sie dies, indem Sie die Unerfüllbarkeit derMenge dieser Formeln per Resolution beweisen.


20. Modellierung (? Punkte)Formulieren Sie die nachfolgenden Aussagen über eine Hochschule als prädi-katenlogische Formeln. Bestimmen Sie dazu zunächst die elementaren/atomarenElemente (im Sinne von Prädikaten und Funktionen) und ordnen Sie diesenBuchstaben als Abkürzung zu, d.h. geben Sie eine passende Struktur an.

Verwenden Sie das Resolutions-Kalkül um zu beweisen, dass der Professorfür Logik und Berechenbarkeit Recht hat mit seiner Behauptung!

Beachten Sie: Alle Lösungsschritte sind nachvollziehbar zu dokumentie-ren, von der Modellierung der Formeln über das Bilden einer KNF bis hinzu der Resolution!

Der Präsident einer Hochschule gibt dem Professor für Didaktik - kurz PD- einen ungewöhnlichen Auftrag. Erfüllt der PD die Bedingungen des Prä-sidenten ein Jahr lang exakt, so erhält er einen beträchtlichen Lohn. Hierdie Bedingungen:

(a) Jeder PD unterweist alle Professoren in Didaktik, die sich nicht selbstin Didaktik unterweisen.

(b) Kein PD unterweist jemanden in Didaktik, der sich selbst in Didaktikunterweist.

Der Professor für Logik und Berechenbarkeit hat über diese Bedingungennachgedacht und behauptet:

(c) Es gibt an dieser Hochschule keine PD’s.

21. Modellierung (? Punkte)Formulieren Sie die nachfolgenden Aussagen über die Welt der Drachenals prädikatenlogische Formeln. Bestimmen Sie dazu zunächst die elemen-taren/atomaren Elemente (im Sinne von Prädikaten und Funktionen) undordnen Sie diesen Buchstaben als Abkürzung zu, d.h. geben Sie eine passen-de Struktur an.

(a) Jeder Drache ist glücklich, wenn alle seine Kinder fliegen können.

(b) Alle grünen Drachen können fliegen.

(c) Ein Drache ist grün, wenn er Kind mindestens eines grünen Drachensist.

Verwenden Sie das Resolutions-Kalkül um zu beweisen, dass nach diesenAussagen alle grünen Drachen glücklich sein müssen.

Beachten Sie: Alle Lösungsschritte sind nachvollziehbar zu dokumentie-ren, von der Modellierung der Formeln über das Bilden einer KNF bis hinzu der Resolution!


22. Modellierung (? Punkte)Es ist allgemein bekannt, dass der Weihnachtsmann jede Familie besucht, inder alle Kinder artig sind. Nicht so bekannt ist, dass er auch alle kinderlosenFamilien besucht, obwohl dies eine Folgerung der ersten Regel ist.

Zeigen Sie dies mittels Resolution, nachdem Sie die beiden Aussagen alsprädikatenlogische Formeln modelliert haben.

Tipp: Vor der Skolemform sollten Sie in der Pränexform, sofern möglich,die ∃-Quantoren möglichst weit nach links setzen, um unnötige Abhängig-keiten von ∀-Quantoren zu vermeiden.

23. Modellierung (? Punkte)Ein Programmierer, der gerade allein ein Programm geschrieben hat, über-legt sich, dass seine Kollegen alle diejenigen Programme schreiben müssen,die er nicht debuggt. Schreibt aber er alleine ein Programm, so braucht eres nicht zu debuggen.

(a) Zeigen Sie, dass sich die Überlegungen des Programmierers durch fol-gende Klauselmenge ausdrücken lassen:

{{P (fx)}1, {¬K(fx)}2, {(D(y), K(y)}3, {¬P (z), K(z),¬D(z)}4}

(b) Zeigen Sie mittels prädikatenlogischer Resolution, dass sich der guteMann in einen Widerspruch verstrickt hat.

24. Modellierung (? Punkte)Christine, Stephan und Katja gehören dem Alpenverein an. Jedes Mitglieddes Alpenvereins ist entweder Snowboarder oder Bergwanderer oder beides.Kein Bergwanderer liebt den Regen, und alle Snowboarder lieben Schnee.Stephan liebt alles (Regen, Schnee), was Christine nicht liebt und umge-kehrt. Stephan und Katja lieben den Schnee.

Gibt es ein Mitglied des Alpenvereins, das Bergwanderer und kein Snow-boarder ist ?

Verwenden Sie zum Nachweis die prädikatenlogische Resolution.

25. Prädikatenlogik mit Identität (? Punkte)In der Prädikatenlogik mit Identität ist auch das Symbol = zugelassen, dasGleichheit zwischen Termen bedeuten soll. Wie muß die Syntax (Definiti-on von Formeln) und Semantik (Definition von A(F )) der Prädikatenlogikerweitert werden, um die Prädikatenlogik mit Identität zu erhalten ?

26. Unifikation (? Punkte)Man wende den Unifikationsalgorithmus an auf die Literalmenge

L = {P (x, y), P (f(a), g(x)), P (f(z), g(f(z)))}


27. Unifikation (? Punkte)Man wende den Unifikationsalgorithmus an auf die Literalmenge (w, x, y, zalle Variable!):

L = {P (x, z, g(x, y, f(z))), P (y, f(x), w)}

28. Unifikation (? Punkte)Man wende den Unifikationsalgorithmus an auf die Literalmenge

L = {P (x4, f(g(x2)), x3), P (f(a), f(x3), x1), P (f(x2), f(x1), x1)}

29. Unifikation (? Punkte)Man wende den Unifikationsalgorithmus an auf die Literalmenge (xi Varia-ble, a Konstante)

L = {P (f(x1), x2, f(a)), P (f(x2), x2, f(x3)), P (f(g(x3)), x1, x4)}

30. Unifikation: occur check (? Punkte)In manchen Implementierungen des Unifikationsalgorithmus (z.B. bei PRO-LOG) wird aus Effizienzgründen auf den Test kommt x in t vor ? ver-zichtet (der occur check).

Man gebe ein Beispiel einer zweielementigen, nicht unifizierbaren Literal-menge {L1, L2} an, so dass L1 und L2 keine gemeinsamen Variablen enthal-ten, und ein Unifikationsalgorithmus ohne occur check - je nach Implemen-tierung - in eine unendliche Schleife gerät oder fälchlicherweise unifizierbarkonstatiert.

31. Unifikation (? Punkte)Betrachten Sie die folgende Formelmenge Fn:

Fn := {p(x1, x2), p(f(x2), f(x3)), . . . ,

p(fn−2(xn−1), fn−2(xn)), p(f

n−1(xn), fn−1(xn+1))}

Dabei ist fn(x) wie folgt definiert:

f 0(x) = x f 1(x) = f(x) fn+1(x) = f(fn(x))

(a) Bestimmen Sie für n = 3 einen allgemeinsten Unifikator der Formel-menge F3.

(b) Geben Sie, für beliebige n, einen allgemeinsten Unifikator für die For-melmenge an und weisen Sie die Korrektheit durch einen Beweis mit-tels vollständiger Induktion nach.


32. Unifikation (? Punkte)Wenden Sie den Unifikationsalgorithmus auf die folgenden LiteralmengenLi an und bilden Sie damit, wenn möglich, einen Unifikator σ, so dass|(Li)σ| = 1. Sind die Literale nicht unifizierbar, so erläutern Sie das Pro-blem.

(a) L1 = {Q(x, a), Q(h(y, z), y), Q(h(f(u), f(v)), v)}(b) L2 = {Q(z, f(z)), Q(y, w), Q(x, x)}(c) L3 = {Q(f(y), h(w, z)), Q(v, h(u, a)), Q(f(x), x)}

Dabei ist a eine Konstante, f ein einstelliges Funktionssymbol, h ein zwei-stelliges Funktionssymbol, Q ein zweistelliges Prädikatensymbol und u, v,w, x, y, z Variablen.

33. Tautologie (? Punkte)Zeigen Sie mittels Resolution, dass die Formel

F1 ≡ (∃x1 : ∀x2 : P (x1, x2))→ (∀x3 : ∃x4 : P (x4, x3))

eine Tautologie ist und die Formel

F2 ≡ (∀x3 : ∃x4 : P (x4, x3))→ (∃x1 : ∀x2 : P (x1, x2))

keine Tautologie ist.

34. Resolutions-Kalkül, Unifikation (? Punkte)Sind folgende Aussagen wahr oder falsch? Begründen Sie Ihre Antwort aus-führlich!

(a) Aus den Klauseln K1 = {¬a, b} und K2 = {a,¬b} läßt sich durchResolution die leere Klausel ({}) herleiten. a, b sind aussagenlogischeVariablen.

(b) Die Menge L = {P (f(y), g(z, f(f(y)))), P (x, g(x, z))} ist unifizierbar.x, y, z sind Variablen, P ein zweistelliges Prädikat und f, g Funktionen.

35. Struktur und Resolutions-Kalkül (? Punkte)In (a) und (b) sehen Sie zwei Formeln der Prädikatenlogik. Eine von die-sen ist eine Tautologie, die andere ist zwar erfüllbar, aber keine Tautologie,d.h. sie ist kontingent. Geben Sie an, welche Formel die Tautologie ist. Be-gründen Sie Ihre Antwort einmal kurz in einem Satz und außerdem, indemSie

(a) die Negation der Tautologie in eine Klauselnormalform umwandelnund so mit Hilfe des Resolutions-Kalkül die leere Klausel herleiten,und


(b) für die kontingente Formel (erfüllbar, aber keine Tautologie) Struktu-ren A und B angeben, so dass A ein Modell für die Formel ist, B jedochnicht.

F1 = ((∀x : P (x)) ∧ (∀y : Q(y)))→ (∀z : (P (z) ∧Q(z)))

F2 = ((∃x : P (x)) ∧ (∃y : Q(y)))→ (∃z : (P (z) ∧Q(z)))

36. Resolutions-Kalkül (? Punkte)Geben Sie (bis auf Variablenumbenennungen) alle direkten Resolventen derbeiden folgenden Klauseln K1 und K2 an. xi, yi seien dabei Variablen unda, b seien Konstanten.

K1 = {¬P (x1, x2),¬P (f(a), g(x3, b)), Q(x1, x3)}

K2 = {P (f(y1), g(a, b)),¬Q(f(a), b),¬Q(a, b)}

37. Resolutions-Kalkül (? Punkte)Schließen Sie mit Hilfe des Resolutions-Kalkül, dass bzgl. der folgenden For-mel P (a) wahr ist. Dokumentieren Sie dies ausführlich und geben Sie z.B.jeweils die benutzten Substitutionen an. x, y, z seien dabei Variablen und asei Konstante.

F = (∀x : ∀y : (¬P (x)→ Q(y))) ∧ (∀z : (Q(z)→ ¬R(z))) ∧R(a)

38. Resolutions-Kalkül (? Punkte)Zeigen Sie mittels Resolutionsmethode, dass

F = {{¬P (x1), Q(x1), R(x1, f(x1))}, {¬P (x2), Q(x2), S(f(x2))}, {T (a)}, {P (a)},

{¬R(a, z), T (z)}, {¬T (x3),¬Q(x3)}, {¬T (y),¬S(y)}}

unerfüllbar ist, d.h. die leere Klausel hergeleitet werden kann. Dabei seienx1, x2, x3, y, z Variablen und a Konstante. Die Klauseln seien von links nachrechts durchnummeriert, z.B. ist K5 = {¬R(a, z1), T (z1)}. Die Herleitung(mit ca. 10 Resolutionsschritten möglich) ist zu dokumentieren, indem z.B.auch die Substitutionen angegeben werden in z.B. folgender Weise: K6 ={¬T (x3),¬Q(x3)};K14 = {T (y)}. SUB = {[x3|y]}, womit ¬T (y) aus K6

und T (y) aus K14 resolviert werden resultierend in der Resolvente K19 ={¬Q(y)}.

39. Resolutions-Kalkül (? Punkte)Beantworten Sie folgende Fragen:


(a) Bei einer theoretischen Betrachtung von konkreten Formeln könnendiese u.a. in drei Kategorien eingestuft werden: Tautologie, Wider-spruch oder Erfüllbar. Welche Kategorien werden von dem Resolutions-bzw. Tableaukalkül erkannt ?Schlagen Sie ein Vorgehen vor, so dass mittels den Kalkülen eine For-mel eindeutig in eine dieser drei Klassen einsortiert werden kann.

(b) Bei der generellen Untersuchung von Formeln durch die Kalküle müs-sen in irgendeinerweise die Quantoren, die restlichen Junktoren unddie Negation behandelt werden. Beschreiben Sie kurz, wie die Resolu-tion und das Tableauverfahren dies tun.

(c) Die Interpretation A berechnet zu einer konkreten Formel mit einerkonkreten Interpretation der Symbole den Wahrheitswert. Wie kanndies mit einem Kalkül, das ja letztlich eine generelle Betrachtung einerFormel vornimmt, simuliert werden ?

40. Resolutions-Kalkül (? Punkte)Zeigen Sie mittels Resolutions-Kalkül, dass aus

F = ∀x : ∀y : ∀z : ((P (f(x), x)∨Q(x))∧¬R(f(y))∧(¬P (z, y)∨¬R(y)∨R(z)))

folgt: ∀w : (R(w) → Q(w)), d.h. das F → (∀w : (R(w) → Q(w))) eineTautologie ist.

Tipp: Seien K1, K2, R prädikatenlogische Klauseln. Dann ist R ein prädi-katenlogischer Resolvent von K1 und K2, falls folgendes gilt:

(a) ∃SUB1, SUB2 Substitutionen: SUB1, SUB2 sind Variablenumbenen-nungen, so dass K1,SUB1 und K2,SUB2 keine gemeinsamen Variablenenthalten.

(b) ∃L1, . . . , Lm ∈ K1,SUB1 und ∃L′1, . . . , L

′n ∈ K2,SUB2, so dass die Menge

der Literale L := {L1, . . . , Lm, L′1, . . . , L

′n} mit SUB unifizierbar ist

(c) R hat die Form

R := ((K1,SUB1 \ {L1, . . . , Lm}) ∪ (K2,SUB2 \ {L′1, . . . , L

′n}))SUB

Zudem: Eine Formel ist für die Resoltion durch Erzeugung der zugehörigenPränex- und Skolemform auf die Resolution vorzubereiten. Im Wesent-lichen sind für die Pränexform alle Quantoren gemäss ihrer Reihenfolgean den Anfang der Formel zu bringen; ggf. müssen Variablenumbennun-gen stattfinden. Für die Skolemform sind ∃-Quantoren durch Funktionenzu ersetzen, die für alle links von ihnen stehenden ∀-Quantoren deren Va-riablen als Argumente haben. Stehen dort keine, ist eine 0-stellige Funktionzu verwenden.

A.3. ÜBUNGEN NICHTKLASSISCHE LOGIK 129

41. Resolutions-Kalkül (? Punkte)Gegeben seien folgende vier prädikatenlogische Formeln:

F1 = ∀x : (¬R(f(x), x)→ P (x))

F2 = ∀y : (¬Q(f(y)))

F3 = ∀w : ∀z : (R(z, w)→ (Q(w)→ Q(z)))

F4 = ∀v : (¬P (v)→ ¬Q(v))

Zu zeigen ist mittels dem Resolutions-Kalkül, dass {F1, F2, F3} =F4 giltbzw. (F1 ∧ F2 ∧ F3)→ F4 eine Tautologie ist.

42. Resolutions-Kalkül (? Punkte)Sei K die folgende Klauselmenge mit folgender Semantik: A = (UA, IA),wobei {f/1, g/1, h/1} ⊂ IA Funktionssymbole sind, {P/2, Q/1, R/2} ⊂ IAPrädikatssymbole sind und V = {x1, . . . , x9} eine Menge von Variablenist. Zeigen Sie mit Hilfe des prädikatenlogischen Resolutions-Kalküls, dassdie unten angegebene Klauselmenge K unerfüllbar ist. Geben Sie für jedenSchritt explizit alle Unifikatoren und Resolventen an. Geben Sie am Endeeine begründete Aussage über die Unerfüllbarkeit der gegebenen Klausel-menge an.

K = {{R(x1, f(x2)),¬P (x3, g(x2))}, {¬Q(h(g(x4))), P (x5, x4)},

{Q(h(x6)), P (x7, x6)}, {¬R(g(x8), x9),¬P (f(x10), x11)}}

A.3 Übungen Nichtklassische LogikAufgabe A.4 (Mehrwertige Logik) 1. Begriffsklärung (? Punkte)

Erklären Sie folgende Unterschiede zwischen Aussagenlogik und der mehr-wertigen Logik L3:

(a) Welcher syntaktische Unterschied besteht ?(b) Welcher semantische Unterschied besteht ?

2. Tautologie (? Punkte)Ist A eine beliebige L3-Formel (ohne Identität, d.h. ohne =), in der dieschwache Negation ˜ nicht vorkommt (auch keine damit definierte Abkür-zung, wie etwa ⇀), dann ist A keine Tautologie.

3. Tautologie (? Punkte)Es seien in L3 folgende Abkürzungen verwendet: A ⇀ B ≡ (Ã)∨B (schwa-che Implikation) und A⇒ B ≡ (¬A) ∨ B (starke Implikation). Zeigen Siemittels Wahrheitstafel, dass die folgenden Formeln in L3 Tautologien bzw.keine Tautologien sind.


(a) (Ã) ⇀ (A ⇀ B)

(b) (A⇒ (A⇒ B))⇒ (A⇒ B)

4. Tautologie (? Punkte)In der zweiwertigen Aussagenlogik sind die beiden Formeln ¬A → B ≡ F1

und (A→ B)→ B ≡ F2 äquivalent.

Sind deren Korrelarate Ã ⇀ B ≡ F3 und (A ⇀ B) ⇀ B ≡ F4 in derdreiwertigen Logik L3 auch äquivalent ?

5. Tautologie (6 Punkte)Es seien in L3 folgende Abkürzungen verwendet: a ⇀ b ≡ ( a)∨b (schwacheImplikation). Zeigen Sie mittels Wahrheitstafel, ob die folgenden Formelnin L3 Tautologien sind.

(a) ((a ⇀ b) ∧ a) ⇀ b

(b) ((a ⇀ b) ∧ b) ⇀ a

6. Tautologie (? Punkte)Es seien in L3 folgende Abkürzungen verwendet: a ⇀ b ≡ ( a)∨b (schwacheImplikation). a b ≡ (a ⇀ b)∧ (b ⇀ a) (schwache Äquivalenz). Zeigen Siemittels Wahrheitstafel, ob die folgenden Formeln in L3 Tautologien sind.

(a) (a ⇀ b) ( (a ∧ b))

(b) (a ⇀ (a ⇀ b)) (a ⇀ b)

7. Formeln (? Punkte)Geben Sie jeweils eine Beispielformel an (keine, die in der nachfolgendenKlausuraufgabe aufgeführt ist!), deren Wahrheitstafel nachfolgende Eigen-schaften aufweist (1 steht für wahr, 0 für falsch und u für unbekannt):

(a) nur 1

(b) nur 0

(c) mindestens einmal 1, mindestens einmal u und kein 0

(d) mindestens einmal 0, mindestens einmal u und kein 1

(e) mindestens einmal 1, mindestens einmal u und mindestens einmal 0

Die Eigenschaften sind nachzuweisen!

8. Formeln (? Punkte)Zeigen Sie mittels Wahrheitstafel das Wahrheitswertverhalten der nachfol-genden Formeln in L3 auf.

(a) (a ⇀ b) ( b ⇀ a)


(b) ( a ⇀ a)

(c) ¬(¬a⇒ a)

9. Stark gültig (? Punkte)Eine Formel der dreiwertigen Logik von Sobocinski heißt stark gültig,wenn sie bei allen Variablenbelegungen den Wert 2 ergibt. Bestimmen Sie,ob die folgenden Formeln bezüglich dieser dreiwertigen Logik stark gültigsind.

(a) a⇒ (b⇒ a)

(b) ( (a⇒ b))⇒ b

Die entsprechenden Operationen dieser dreiwertigen Logik sind wie folgtdefiniert:

a⇒ b 0 1 20 2 1 21 0 2 22 0 1 2

a a0 11 22 0

10. Standardfortsetzung (? Punkte)Teil 1: Geben Sie für die ⊙-Funktion (⊙ := (x ∨ y) ∧ (¬x ∨ ¬y)) die Stan-dardfortsetzung ⊙∗ für die dreiwertige Logik L3 an. Die Entwicklung dieserFortsetzung ist nachvollziehbar anzugeben!

Teil 2: Definieren Sie die (schwache) ⊙-Funktion der dreiwertigen LogikL3 im Sinne einer Standardfortsetzung zu der Funktion ⊙, wobei ⊙ imUnterschied zu ⊙∗ mittels schwacher Negation definiert ist. Die Entwicklungdieser Fortsetzung ist nachvollziehbar anzugeben! Bitte beachten Sie: eineStandardfortsetzung kann hier wegen der schwachen Negationñicht benutztwerden!

11. Standardfortsetzung (? Punkte)Teil 1: Geben Sie für den |-Junktor (Shefferscher Strich: „nicht sowohl ...als auch ...“) (a|b := ¬(a ∧ b)) die Standardfortsetzung |∗ für die dreiwer-tige Logik L3 an. Die Entwicklung dieser Fortsetzung ist nachvollziehbaranzugeben!

Teil 2: Definieren Sie die (schwache) |-Funktion der dreiwertigen LogikL3 im Sinne einer Standardfortsetzung zu der Funktion |, wobei | im Un-terschied zu |∗ mittels schwacher Negation definiert ist. Die Entwicklungdieser Fortsetzung ist nachvollziehbar anzugeben! Bitte beachten Sie: eineStandardfortsetzung kann hier wegen der schwachen Negationñicht benutztwerden!


12. Standardfortsetzung (? Punkte)Teil 1: Geben Sie für den ←-Junktor (Präsektion: „das andere ohne das ei-ne“) (a ← b := ¬a∧b) die Standardfortsetzung ←∗ für die dreiwertige LogikL3 an. Die Entwicklung dieser Fortsetzung ist nachvollziehbar anzugeben!

Teil 2: Definieren Sie die (schwache) ← -Funktion der dreiwertigen LogikL3 im Sinne einer Standardfortsetzung zu der Funktion ←, wobei ← ˜ imUnterschied zu ←∗ mittels schwacher Negation definiert ist. Die Entwick-lung dieser Fortsetzung ist nachvollziehbar anzugeben! Bitte beachten Sie:eine Standardfortsetzung kann hier wegen der schwachen Negation ˜ nichtbenutzt werden!

Aufgabe A.5 (Modale Logik) 1. Modell (? Punkte)Finden Sie ein modallogisches Modell für die Negation von

(�♢A)→ (♢�A)

Tipp: mögliche Welten (im Sinne von Referenzpunkten) können auch Zahlensein, z.B. Z.

2. Tableaukalkül (? Punkte)Seien F,G modallogische Formeln. Zeigen Sie mit Hilfe des Tableaukalkülsder Modallogik, dass die folgenden Formeln Tautologien sind:

(a) ¬♢F ⇔ �¬F(b) ¬�F ⇔ ♢¬F

3. Tableaukalkül (? Punkte)Seien F,G modallogische Formeln. Zeigen Sie mit Hilfe des Tableaukalkülsder Modallogik, dass die folgenden Formeln Tautologien sind:

(a) ¬♢¬F ⇒ �F

(b) � (F ∨ ¬G)⇒ (♢G⇒ ♢F )

4. Tableaukalkül (? Punkte)Seien F,G modallogische Formeln. Zeigen Sie mit Hilfe des Tableaukalkülsder Modallogik, dass die folgende Formel eine Tautologie ist:

(♢(F → G))→ (�F → ♢G)

Geben Sie bitte im Tableau an, in welcher Reihenfolge Sie expandieren.

5. Tableaukalkül (? Punkte)Seien F und G zwei modallogische Formeln. Zeigen Sie mit Hilfe des Ta-bleaukalküls, dass die Formel:

(¬F ∧ (♢F → �G))→ �(F → G)


allgemein gültig ist. Geben Sie bitte im Tableau an, in welcher ReihenfolgeSie expandieren.

6. Modellierung (? Punkte)Für Wallace stellt sich nicht nur das Problem, wie er das Riesenkaninchenfängt, sondern auch, was er mit diesem anfangen soll, wenn er es gefangenhat. Dazu überlegt er sich Folgendes:

Er bringt das Riesenkaninchen dazu, eine mit Liebestrank ver-sehene Riesenkarotte zu fressen. Daraufhin wird es sich in die vonWallace hergestellte Attrappe eines weiblichen Riesenkaninchensverlieben und von da an solange im selben Raum wie diese Attrap-pe bleiben, wie es die Gestalt eines Riesenkaninchen hat. Somitwird der Zeitpunkt kommen, an dem das Riesenkaninchen in die-sem Raum einschläft, so dass Wallace ihm einen Karottenpflockdurchs Herz jagen kann und sich das Riesenkaninchen so in einnormales Kaninchen verwandelt.

Drücken Sie Wallace’s Überlegungen mit Hilfe von modallogischen Formelnaus. Geben Sie einen zugehörigen konkreten Rahmen an.

7. Modellierung (? Punkte)In einem Computerprogramm kommen die vier Integer-Variablen w, x, y, zvor. Ab einem gewissen Zeitpunkt im Programm gilt:

• Wenn z ≤ 0 ist, ist y > 0.

• Wenn w > 0 ist, ist x ≤ 0.

• Wenn w ≤ 0 ist, ist y ≤ 0.

• Es ist nie z > 0.

(a) Übersetzen Sie diese Aussagen in modallogische Formeln.

(b) Das Programm endet genau dann, wenn x > 0 ist. Zeigen Sie, dassdas Programm nie endet.

8. Modellierung (? Punkte)Die Saison befindet sich schon mitten in der Rückrunde, als am Stammtischfür die kommenden restlichen Spieltage folgende Thesen als allgemeingültigeRegeln vertreten werden:

(a) „Wenn Pauli mal nicht gewinnt, so gewinnt an diesem Spieltag auchBremen nicht.“

(b) „Wenn Pauli an einem Spieltag gewinnt, so gewinnt am selben Spieltagauch Hamburg.“


(c) „In jeder Runde gewinnt mindestens eine der Mannschaften Bremen,Hamburg und Pauli.“

(d) „Hamburg gewinnt alle restlichen Spiele.“

• Formulieren Sie obige Voraussagen als modallogische Formeln. GebenSie dabei die zugehörige Struktur an.

• Zeigen Sie mit Hilfe des Tableaukalküls, dass die Aussage des viertenExperten (Aussage d) redundant ist, d.h. dass sie aus den Aussagender übrigen drei folgt.’

9. Modellierung (?? Punkte)Lucky Looser, passionierter Roulettespieler mit zweifelhaften Kenntnissenin der Wahrscheinlichkeitstheorie, ist mal wieder im Spielcasino. Bei demhier gespielten Roulette wird mittels einer Kugel in einem Kreisel zufälligeine Zahl aus der Menge {1, 2, . . . , 36} gewählt. Jede dieser Zahlen hat ent-weder die Farbe rot oder die Farbe schwarz. Lucky hat schon den ganzenAbend Statistik geführt und glaubt, für die nächsten 20 Rouletterunden diefolgenden Voraussagen treffen zu können:

• Die Zahl wird jedesmal rot oder kleiner 19 sein.

• Es wird nicht passieren, dass die Zahl gleichzeitig kleiner 19 und un-gerade ist.

• Es wird jedesmal so sein, dass, wenn die Zahl rot ist, sie dann auchgerade ist.

(a) Formulieren Sie obige Aussagen als modallogische Formeln. Geben Siedabei die zugehörige Struktur an.

(b) Angenommen, die Voraussagen treten tatsächlich ein. Zeigen Sie mitHilfe des modallogischen Tableaukalküls, dass dann in den nächsten 20Runden nur gerade Zahlen fallen.

10. Modellierung (? Punkte)Um wie von Gaius Pupus verlangt in der römischen Stadtverwaltung Pas-sierschein A38 zu erhalten, müssen Asterix und Obelix unter anderem zu-nächst Antragsformular L3O7-G15IK ausfüllen. Dazu müssen sie zunächstden Raum finden, in dem es dieses Formular gibt. Über die an diesen Raumangrenzenden Räume sagt der zuständige Beamte Folgendes:

„Ich kann mich nicht genau erinnern, in welchem Raum esdas Formular L3O7-G15IK gibt, aber ich weiß, dass alle angren-zenden Räume Fenster haben oder rot sind. Und all diese Räume,die Fenster haben, sind nicht viereckig. Außerdem sind all diese

A.4. ÜBUNGEN BERECHENBARKEIT 135

Räume genau dann rot, wenn sie nicht viereckig sind. Ach ja,und wenn all diese Räume rot sind, dann ist unter diesen auchein viereckiger mit Fenstern.“

(a) Formulieren Sie obige Aussagen als modallogische Formeln. Geben Siedabei die zugehörige Struktur an.

(b) Zeigen Sie mit Hilfe des modallogischen Tableaukalküls, dass es einenRaum wie oben beschrieben nicht geben kann. Geben Sie bitte im Ta-bleau an, in welcher Reihenfolge Sie expandieren.

A.4 Übungen BerechenbarkeitAufgabe A.6 (Berechenbarkeit) 1. Loop-Programme (? Punkte)

Geben Sie jeweils ein Loop-Programm an, welches die folgenden Funktio-nen berechnet (und erklären Sie kurz, warum es dies tut):

(a) die Addition auf den natürlichen Zahlen (positiven ganzen Zahlen):add(m,n) = m+ n.

(b) die Multiplikation auf den natürlichen Zahlen (positiven ganzen Zah-len): mult(m,n) = m ∗ n.

(c) die Maximum-Funktion auf den natürlichen Zahlen (positiven ganzenZahlen):

max(m,n) =

{m m ≥ nn m < n

2. Loop-Programme (? Punkte)Geben Sie ein Loop-Programm an, dass die Anweisung

if x1 = x2 then A1 else A2 endif

simuliert und erklären Sie kurz, warum es dies tut.

3. While-Programme (? Punkte)Die Loop-Anweisung ist in While-Programmen im Prinzip überflüssig,denn sie kann durch eine While-Anweisung simuliert werden. Geben Sieeine zusammengesetzte While-Anweisung an, die die Anweisung

Loop x1 do A End

simuliert und erklären Sie kurz, warum es dies tut.


Literaturverzeichnis

[CM94] Clocksin, William F. and Mellish, Christopher S.˙Programming in Prolog.Springer-Verlag, 1994.

[KJ00] Kelly, John. Logik im Klartext. Pearson-Studium Verlag, 2003.

[KK06] Kreuzer, Martin and Kühling, Stefan. Logik für Informatiker. Pearson-Studium Verlag, 2006.

[SU00] Schöning, Uwe. Logik für Informatiker. Hochschultaschenbuch bei Spek-trum Akademischer Verlag, 2000.

[SU08] Schöning, Uwe. Ideen der Informatik. oldenbourg Verlag, 2008.

137

Documents

Logik1 - users.informatik.haw-hamburg.deklauck/LoBe/lbskript.pdf · 1.1.1.1 Elemente von Prolog In diesem Abschnitt werden zunächst die wesentlichsten Elemente von Prolog präsentiert,