Qualifikationsphase Q4 · Themenfeld Q4.2

Q4.2 – Prolog als logische Programmiersprache

Wissen modellieren, Anfragen stellen und logische Herleitungen untersuchen

Prolog verändert die Perspektive auf Programmierung. In einem objektorientierten oder imperativen Programm wird meist festgelegt, welche Anweisungen in welcher Reihenfolge ausgeführt werden. Ein Logikprogramm beschreibt dagegen Wissen über eine abgegrenzte Miniwelt: Welche Objekte gibt es? Welche Eigenschaften und Beziehungen gelten? Welche weiteren Aussagen lassen sich daraus ableiten?

Der Prolog-Interpreter erhält dieses Wissen in Form von Fakten und Regeln. Eine Anfrage setzt eine Suche nach einer passenden Herleitung in Gang. Das Ergebnis kann true oder false sein, aber auch aus Variablenbelegungen bestehen. So steht nicht zuerst ein vorgezeichneter Lösungsweg im Mittelpunkt, sondern die logische Struktur des Problems – und zugleich die Frage, wie der Interpreter diese Struktur operativ durchsucht.

Q4.2 nimmt frühere D-Book-Lernbewegungen erneut auf: Rekursion aus Q1, Daten und Abfragen aus Q2, formale Sprachen aus Q3 sowie die Modellierung logischer Zusammenhänge aus Q4.1.

Prolog-Labor öffnen

Kerncurriculum kompakt
Wissensbasis, Anfragen und rekursive Relationen als verbindlicher Kern

A) Allgemeine Einordnung

Ein Prolog-Programm verbindet eine Wissensbasis mit Anfragen an diese Wissensbasis. Fakten halten explizites Wissen fest. Regeln beschreiben, unter welchen Bedingungen weitere Aussagen gelten. Eine Inferenzmaschine versucht anschließend, eine Anfrage aus diesen Klauseln herzuleiten. Damit entsteht ein begründeter Kontrast zu objektorientiertem oder imperativem Programmieren: Nicht jede Einzelschrittfolge wird vorab ausgeschrieben; dennoch beeinflussen die Programmstruktur und die Suchordnung den konkreten Ablauf.

Grundlegendes Niveau

Lernende modellieren kleine Welten mit Fakten und Regeln, lesen Prädikate mit ihrer Stelligkeit, unterscheiden Konstanten und Variablen und formulieren Ja-Nein-, Ergänzungs- sowie zusammengesetzte Anfragen. Einfache rekursive Prädikate erschließen indirekte Beziehungen.

Als Anwendungskontexte tragen Beziehungen, Verkehrsverbindungen und Logikrätsel die Verbindung von Modellierung und Suche.

Erhöhtes Niveau · Leistungskurs

Listen machen die rekursive Datenstruktur selbst sichtbar: [] steht für die leere Liste, [K|R] trennt Kopf und Rest. Rekursive Listenprädikate werden als Relationen gelesen, die – abhängig von den bereits gebundenen Argumenten – prüfen, erzeugen oder zerlegen können.

B) Curriculare Vernetzung

Frühere Lernbewegung	Anschluss in Q4.2
Q1.3 Rekursion	Rekursive Regeln und Listenprädikate brauchen einen erreichbaren Abschluss.
Q1.5 Graphen	Direkte Kanten, Erreichbarkeit und Pfade werden als Relationen beschrieben.
Q2.2 SQL	Eine Anfrage bezieht sich auf einen modellierten Datenbestand, aber die Herleitung arbeitet anders.
Q3.1 Formale Sprachen	Syntax, Terme und regelgeleitete Ableitungen werden erneut fachlich bedeutsam.
Q4.1 Logische Verknüpfungen	Komma und Semikolon strukturieren Bedingungen als UND beziehungsweise ODER.

Vom Beschreiben zum Ableiten

Prolog beschreibt Wissen in sehr knapper Form. Gerade deshalb ist der Weg von der Anfrage zur Lösung im Programmtext nicht unmittelbar sichtbar. Der Transformationspfad trennt daher Modell und Suche, ohne die beiden Seiten auseinanderzureißen.

Miniwelt Fakten Regeln Wissensbasis Anfrage Unifikation und Teilziele Herleitung Lösung oder Backtracking

Eingabe

Miniwelt, Fakten, Regeln, Anfrage

Interaktion

consultieren, ausführen, nächste Lösung, Trace untersuchen

Beobachtung / Output

Prädikate, Variablenbindungen, Teilziele, Herleitungszweige, Backtracking

Die deklarative Sicht fragt, was in der Miniwelt gilt. Die operative Sicht verfolgt, welche Klausel passt, welche Bindung entsteht und wo ein Suchzweig endet. Erst beide Perspektiven zusammen erklären, was eine Prolog-Anfrage leistet.

Paradigmenwechsel: Wissen statt Schrittfolge?
Zwei Perspektiven kontrolliert vergleichen

Der Kontrast ist hilfreich, wenn er nicht überzeichnet wird. Imperative oder objektorientierte Programme können mehrere Wege und Abstraktionen enthalten; Prolog nimmt den Entwicklerinnen und Entwicklern nicht jede Entscheidung über die Suche ab. Die Leitfragen bleiben jedoch verschieden.

Imperativ / objektorientiert

Der Lösungsweg wird über Methoden und Kontrollstrukturen organisiert.
Anweisungen verändern schrittweise einen Zustand.
Das Ergebnis erscheint etwa als Rückgabewert oder Objektzustand.

Logisch mit Prolog

Wissen und Beziehungen werden durch Fakten, Regeln und Prädikate beschrieben.
Eine Anfrage löst eine Herleitungssuche aus.
Das Ergebnis ist true, false oder eine Variablenbelegung.

Wichtige Grenze

„Deklarativ“ bedeutet nicht „ohne Ablauf“. Klausel- und Teilzielreihenfolge beeinflussen Suchweg, Lösungsreihenfolge und Terminierung. Die Modellierung beschreibt also nicht nur, was gelten soll, sondern schafft zugleich Bedingungen für eine tragfähige Suche.

Eine Miniwelt aus Fachbeziehungen
Durchgehender Modellkontext für Fakten, Regeln und Anfragen

Die Seite arbeitet mit Themen und curricularen Kontexten als Objekten. Direkte Anschlüsse sind als Fakten notiert; eine rekursive Regel kann daraus indirekte Fachpfade erschließen. Das Modell bleibt absichtlich klein, damit die Herleitung lesbar bleibt.

Didaktisch reduzierte Miniwelt – keine technische Abbildung des produktiven D-Book-Wissensnetzes.

Die folgende Wissensbasis erklärt eine Prolog-Relation. Sie ersetzt weder Concepts noch Relationen oder Daten des Wissensnetzes.

% Themen und curriculare Kontexte
behandelt_in(rekursion, q1_3).
behandelt_in(sql, q2_2).
behandelt_in(relationenalgebra, q2_5).
behandelt_in(formale_sprache, q3_1).
behandelt_in(prolog, q4_2).
behandelt_in(listen, q4_2).

% direkte fachliche Anschlusswege
direkter_fachpfad(prolog, formale_sprache).
direkter_fachpfad(prolog, rekursion).
direkter_fachpfad(relationenalgebra, sql).
direkter_fachpfad(sql, relationenmodell).

Die Miniwelt hält die folgenden Abschnitte zusammen: Fakten, Regeln, Anfragen, Rekursion, Unifikation, Rückwärtsschließen und Backtracking. Ihre Begriffe sind dabei keine Behauptung über die vollständige Fachstruktur, sondern ein bewusst reduziertes Lernmodell.

Fakten: explizit notiertes Wissen

Ein Faktum beschreibt eine Eigenschaft eines Objekts oder eine Beziehung zwischen mehreren Objekten. In der Miniwelt gilt etwa direkt: Prolog wird im Kontext Q4.2 behandelt.

Prädikat und Stelligkeit: die Code-Lupe

behandelt_in( prolog, q4_2) .

Prädikatsname
behandelt_in benennt die vereinbarte Beziehung.

Stelligkeit /2
Das Prädikat besitzt zwei Argumente.

Erstes Argument
prolog ist eine Konstante.

Zweites Argument
q4_2 ist eine Konstante.

Klauselabschluss
Der Punkt beendet das Faktum.

Faktum: Unmittelbar gespeichertes Wissen über eine Eigenschaft oder Beziehung.
Prädikat: Name einer Eigenschaft oder Beziehung mit festgelegter Argumentstruktur.
Stelligkeit: Anzahl der Argumente, etwa behandelt_in/2.
Argument: Eine Stelle innerhalb eines Prädikats, die ein Objekt oder eine Variable aufnimmt.
Atom / Konstante: Ein benannter Wert wie prolog oder q4_2.
Variable: Ein Platzhalter wie THEMA, der durch eine Bindung konkret werden kann.
Klausel: Ein Faktum oder eine Regel, die mit einem Punkt abgeschlossen wird.

Syntax kompakt
Notation als Werkzeug zum Lesen der Wissensbasis

Atome beginnen klein oder stehen bei Bedarf in einfachen Anführungszeichen.
Variablen beginnen groß oder mit einem Unterstrich.
_ steht für jeweils eine neue anonyme Variable.
% beginnt einen Kommentar; . beendet eine Klausel.

Der Begriff Funktor kann in einer späteren Vertiefung präzisieren, welche Struktur ein Term besitzt. Für den Basiskern bleibt „Prädikat mit Stelligkeit“ die bessere Lesebrücke.

Regeln und Rekursion
Implizites Wissen als fachlich lesbare Relation formulieren

Direkte Fachbeziehungen können als Fakten gespeichert werden. Ein längerer Fachpfad muss jedoch nicht für jede mögliche Kombination als Fakt vorliegen. Die folgende Relation beschreibt, wann ein direkter oder indirekter Weg existiert.

fachpfad(X, Y) :-
    direkter_fachpfad(X, Y).

fachpfad(X, Y) :-
    direkter_fachpfad(X, Z),
    fachpfad(Z, Y).

Regelkopffachpfad(X, Y)Die Folgerung: X besitzt einen Fachpfad zu Y.

←gilt, wenn

Bedingungen / Regelrumpfdirekter_fachpfad(X, Z), fachpfad(Z, Y)Beide Teilziele müssen erfolgreich sein.

:- trennt Regelkopf und Regelrumpf. Das Komma bedeutet logisches UND: Erst wenn der direkte Schritt von X nach Z und der anschließende Pfad von Z nach Y herleitbar sind, gilt der gesamte Fachpfad. Die Variablen gelten jeweils nur innerhalb ihrer Klausel; gleich geschriebene Namen in zwei Klauseln sind keine gemeinsame Variable.

Nichtrekursiver und rekursiver Fall

Direkter Fall

Die erste Klausel beendet die Suche, sobald eine direkte Beziehung vorhanden ist.

Rekursiver Fall

Die zweite Klausel zerlegt den offenen Weg in einen direkten Schritt und einen verbleibenden Fachpfad.

Terminierung

Ein rekursiver Aufruf braucht einen erreichbaren Abschluss und eine Struktur, in der die Suche vorankommt.

Arbeitsfrage

Welche direkte Beziehung bildet den Abschluss der Rekursion, und welches Argument verändert sich auf dem Weg dorthin?

Die Regel ist damit mehr als Syntax: Sie übersetzt die fachliche Aussage „Ein indirekter Anschluss besteht aus einem ersten Anschluss und einem weiteren Pfad“ in eine überprüfbare Relation.

Anfragen an die Wissensbasis
Prüfen, ergänzen und Beziehungen mit Variablen erschließen

Eine Anfrage wird mit ?- begonnen. Sie kann nur prüfen, ob eine Aussage herleitbar ist, oder zugleich nach allen passenden Variablenbelegungen suchen.

Ja-Nein-Anfrage

?- behandelt_in(prolog, q4_2).

Die Anfrage kann unmittelbar zu true führen.

Ergänzungsanfrage

?- behandelt_in(THEMA, q4_2).

Prolog sucht Werte für THEMA.

Zusammengesetzte Anfrage

?- direkter_fachpfad(prolog, THEMA),
   behandelt_in(THEMA, KONTEXT).

Beide Teilziele müssen mit zueinander passenden Bindungen gelten.

Anonyme Variable

?- direkter_fachpfad(prolog, _).

Es wird nur geprüft, ob irgendein direkter Fachpfad existiert.

true zeigt eine herleitbare Anfrage; false markiert das Ende der Suche ohne passende Herleitung. Eine Variable liefert eine oder mehrere Belegungen. Mit einer weiteren Lösung wird die Suche an der nächsten noch offenen Alternative fortgesetzt. Das Komma verbindet Teilziele als UND, das Semikolon formuliert Alternativen als ODER und _ unterdrückt eine an dieser Stelle nicht benötigte Belegung.

Bedeutungsgrenze von false

false bedeutet nicht: Die Aussage ist in der Wirklichkeit falsch. Es bedeutet: Die Anfrage ist aus der aktuellen Wissensbasis nicht herleitbar.

Herleitung, Unifikation und Backtracking
Wie aus einem Ziel Teilziele, Sackgassen und eine Lösung werden

Leitfrage: ?- fachpfad(relationenalgebra, relationenmodell).

fachpfad(relationenalgebra, relationenmodell)
├─ direkter Fall
│  └─ direkter_fachpfad(relationenalgebra, relationenmodell)
│     └─ scheitert
└─ rekursiver Fall
   ├─ direkter_fachpfad(relationenalgebra, sql)
   └─ fachpfad(sql, relationenmodell)
      └─ direkter_fachpfad(sql, relationenmodell)
         └─ erfolgreich

Unifikation: passend machen durch Bindungen

Zwei Terme werden durch geeignete Variablenbindungen zur Deckung gebracht. Bei einer Anfrage wie ?- direkter_fachpfad(prolog, X). kann das Faktum direkter_fachpfad(prolog, formale_sprache). passen, wenn X an formale_sprache gebunden wird. Unifikation ist deshalb keine bloße Textgleichheit, sondern eine strukturelle Passung von Prädikatsname, Stelligkeit und Argumenten.

Rückwärtsschließen: vom Ziel zu den Voraussetzungen

Die Suche beginnt beim Ziel und zerlegt es mithilfe von Regeln in Teilziele, bis Fakten erreicht werden. Für die Leitfrage wird zunächst geprüft, welche fachpfad/2-Klausel passen könnte. Der direkte Fall scheitert. Der rekursive Fall erzeugt die Teilziele direkter_fachpfad(relationenalgebra, sql) und fachpfad(sql, relationenmodell).

Backtracking: zur letzten Alternative zurückkehren

Scheitert ein Suchweg oder wird eine weitere Lösung angefordert, kehrt Prolog zum letzten noch offenen Wahlpunkt zurück. Dabei werden frühere Bindungen zurückgenommen, damit eine andere Klausel oder ein anderes Faktum erprobt werden kann. Backtracking ist also keine Fehlermeldung, sondern ein kontrollierter Bestandteil der Suche.

Die Anfrage wird zum aktuellen Ziel.
Prolog sucht eine passende Klausel und vereinheitlicht Ziel und Regelkopf.
Aus dem Regelrumpf entstehen neue Teilziele, die von links nach rechts bearbeitet werden.
Ein Teilziel führt zum Erfolg oder zu einer Sackgasse.
Bei einer Sackgasse kehrt die Suche zum letzten Wahlpunkt zurück.
Eine vollständige erfolgreiche Kette liefert die Lösung und gegebenenfalls Variablenbelegungen.

Vertiefung: Resolution
Ein Begriff für die regelgeleitete Herleitungsstruktur

Resolution kann die Verbindung aus Klauselauswahl, Unifikation und Erzeugung neuer Teilziele fachsprachlich präzisieren. Für das erste Verständnis bleibt die beobachtbare Bewegung von Ziel, Teilziel, Erfolg, Sackgasse und Backtracking führend.

Deklarativ heißt nicht ablauflos
Warum die Reihenfolge von Klauseln und Teilzielen fachlich zählt

Ähnliche logische Ideen können in einer konkreten Prolog-Suche unterschiedlich arbeiten. Prolog prüft Klauseln von oben nach unten und Teilziele im Regelrumpf von links nach rechts.

Gut zugängliche Reihenfolge: Ein konkreter direkter Schritt entsteht vor dem rekursiven Aufruf.

fachpfad(X, Y) :-
    direkter_fachpfad(X, Y).

fachpfad(X, Y) :-
    direkter_fachpfad(X, Z),
    fachpfad(Z, Y).

Problematische Umstellung: Die Rekursion startet, bevor ein Zwischenschritt konkretisiert wurde.

fachpfad(X, Y) :-
    fachpfad(X, Z),
    direkter_fachpfad(Z, Y).

Die zweite Variante behauptet nicht einfach etwas anderes, kann aber operativ in immer neue offene Aufrufe geraten. In Beziehungsnetzen mit Zyklen kommt eine weitere Grenze hinzu: Eine belastbare Wegsuche benötigt später eine Besuchsliste. Diese Seite behandelt noch bewusst den kleinen, azyklischen Kern.

Anwendungskontexte
Ein relationales Modell wird erst durch seine Fragestellungen konkret

Fachbeziehungen im D-Book

Der Seitenkontext: Themen und Kontexte werden als Objekte, direkte Anschlüsse als Fakten und indirekte Lernwege als rekursive Relation modelliert. Die Miniwelt bleibt klar vom produktiven Wissensnetz getrennt.

Historische Entwicklungslinien

Das vorhandene Prolog-Labor nutzt eine bereits angelegte, neutrale zeitliche Folge. folgt_auf beschreibt dort keine vollständige Kausalität; zeitliche Folge, Vorläuferbeziehung und Einfluss dürfen nicht vermischt werden.

Verkehrsverbindungen

direkt(giessen, frankfurt).
direkt(frankfurt, mainz).
direkt(giessen, marburg).

Direkte und indirekte Erreichbarkeit machen Rekursion, Suchreihenfolge und später zyklensichere Pfade anschaulich.

Logikrätsel

Bedingungen werden modelliert, zulässige Belegungen gesucht und die kombinatorische Suche wird beobachtbar. Aussagenlogische Rätsel bilden dabei eine Brücke zu Q4.1, ohne hier eine vollständige Musterlösung vorwegzunehmen.

Die Qualität der Lösung hängt in jedem Kontext zuerst von der Qualität des Modells ab: Welche Beziehung wird tatsächlich beschrieben, welche Richtung haben ihre Argumente und welche Grenze besitzt die Miniwelt?

Erhöhtes Niveau · Leistungskurs: Listen
Kopf-Rest-Methode und mehrgerichtete Listenrelationen

Listen als rekursive Struktur

Eine Liste ist entweder leer oder besitzt einen ersten Eintrag und eine Restliste. Dadurch kann sie mit derselben Grundidee wie eine rekursive Regel verarbeitet werden.

[java, sql, prolog]=[java | [sql | [prolog | []]]]

[]

Die leere Liste: ein möglicher Abschluss der Rekursion.

[K|R]

Eine nichtleere Liste mit Kopf K und Restliste R.

Kopf

Das erste Element, etwa java.

Rest

Die verbleibende Liste, die wiederum Kopf und Rest besitzt.

Listenoperationen als Relationen

element/2: X ist Element einer Liste, wenn X ihr Kopf ist oder in ihrer Restliste liegt.

element(X, [X|_]).

element(X, [_|R]) :-
    element(X, R).

anhaengen/3: Zwei Listen und ihre zusammengefügte Liste stehen in einer Relation.

anhaengen([], L, L).

anhaengen([K|R], L, [K|N]) :-
    anhaengen(R, L, N).

Ergebnisliste erzeugen

?- anhaengen([java, sql], [prolog], L).

L = [java, sql, prolog].

Eine Liste zerlegen

?- anhaengen(A, B, [java, sql, prolog]).

Prolog findet mehrere mögliche Aufteilungen in Anfangs- und Restliste.

Relation statt festgelegter Ein- und Ausgabe

Ein Prolog-Prädikat ist nicht notwendig eine Funktion mit festgelegten Eingabe- und Ausgabeparametern. Je nach instanzierten Argumenten kann dieselbe Relation prüfen, erzeugen oder zerlegen.

Vertiefung: innere Punktschreibweise
Eine zusätzliche Darstellung derselben rekursiven Listenstruktur

Die innere Punktschreibweise kann die Konstruktion von Listen weiter präzisieren. Für den offenen Basiskern genügt jedoch die lesbarere Kopf-Rest-Notation [K|R].

Vernetzung und Transfer
Bekannte Strukturen erhalten im logischen Programmieren eine neue Rolle