2. Prädikatenlogik

Quantoren

Ein Quantor ist ein Operator der Prädikatenlogik, der eine Aussage über die Häufigkeit von Objekten macht.

Das heist die Bedingung wohnort gilt für alle c in der Grundmenge.

Analog beschreibt

Wenn diese beiden Zeichen nicht vorhanden sind können diese auch als

All-

Existenz- Quantor bezeichnent wertden.

Als eine atomare Formel.

Wobei eine atomare Formel in der Prädikatenlogik einen oder mehrere Terme enthalten kann und dadurch möglicherweise sehr viel komplexer ist als eine atomare Formel in der Aussagenlogik.

Dabei ist wohnort() ein zweistelliges Prädikatensymbol, anzahl-bestellungen() ein einstelliges Funktionssymbol, 'Bad Reichenhall', 'Bad Honnef' und 1 sind nullstellige Funktionssymbole, also Konstanten; die Gleichheit = ist hier nicht als eigenständiges Symbol der Sprache der Prädikatenlogik definiert, sondern wird als Prädikat verwendet, d. h., um zu beschreiben, dass die Anzahl der Bestellungen 1 beträgt, wird die Schreibweise "=(Anzahl Bestellungen(c),1)" verwendet statt der üblichen Schreibweise "Anzahl Bestellungen(c)=1". Das Symbol c ist eine Individuenvariable.

Eine Formel ist dann allgemeingültig:

• Wenn sie unter jeder solchen Interpretation wahr ist.

• Sie ist erfüllbar, wenn sie unter mindestens einer Interpretation wahr ist.

Ein oft genutztes Beispiel für eine derartige Variablensubstitution ist die Beschreibung der Sterblichkeit von Sokrates: Alle Menschen sind sterblich, also ∀x (Mensch(x)-> sterblich(x)). Da Sokrates ein Mensch ist, also Mensch(Sokrates), kann man jetzt die Variable x durch den Wert Sokrates ersetzen (substituieren) und erhält sterblich(Sokrates), hat damit also gezeigt, dass Sokrates sterblich ist.

Zwei Literale L1 und L2 heißen unifizierbar, wenn es eine Variablensubstitution subst gibt, sodass subst(L1)=subst(L2). In diesem Fall wird subst als Unifikator bezeichnet.

Ein Unifikator, aus dem alle anderen Unifikatoren durch eine weitere Substitution erzeugt werden können, heißt allgemeinster Unifikator (engl.: Most General Unifier [MGU]).

Die Antinomien, also Widersprüchen in der Mathematik und der Logik, bei denen beide Aussagen scheinbar überzeugend begründet werden konnten.

• Eine der bekanntesten dieser Antinomien ist der Satz „Dieser Satz ist falsch“, von dem Varianten schon in der Antike bekannt waren.

• Sowohl die Annahme, dass dieser Satz wahr ist, als auch, dass er falsch ist, führt zu Widersprüchen zur Aussage des Satzes.

Er definierte die „Menge aller Mengen, die sich nicht selbst enthalten“, und fragte dann, ob diese Menge sich selbst enthält. In den meisten dieser Antinomien war der Ausgangspunkt eine Selbstreferenz, bei der aber nicht klar war, wie diese vermieden werden kann.

Selbstreferenz/Diagonalisierung

Es beschreibt das zu lösende Problem, nicht den Lösungsweg oder Algorithmus.

Deklarative Programmierung nennt man diesen Programmierstiel.

Für rekursive Berechnungen.

z.B. die suche in einem Baum.

Prolog ist somit eine Rekursive Sprache.

Aus Fakten und Regeln.

Jede Eingabe ( Fakt, Regel, Anfrage)

• muss mit einem Punkt und einem Zeilenende abgeschlossen

  werden.

• Kommentare werden in /*………*/ eingeschlossen.

Ein Fakt in Prolog besteht aus einem eingelnen positiven Literal.

Eine Regel ist eine Horn-Klausel,

• d. h. eine Klausel, die aus einem positiven Literal und beliebig vielen negativen Literalen besteht.

• Dabei schreibt man wie im Beispiel oben zuerst das positive Literal, dann das Symbol „:-“,

• und dann die negativen Literale ohne Negationszeichen, bei mehreren verbunden durch Kommas.

Code

es_regnet.

strasse_nass:-es_regnet.

?-strasse_nass.

true.

Konstanten in Prolog beginnen mit einem Kleinbuchstaben.

Variablen mit einem Großbuchstaben.

Prädikate beginnen ebenfalls mit einem Kleinbuchstaben.

a) eLISABETH ist ein Atom, weil es mit einem Kleinbuchstaben beginnt.

b) Party ist eine Variable, weil sie mit einem Großbuchstaben beginnt.

c) variable123 ist ein Atom, weil es mit einem Kleinbuchstaben beginnt.

d) Variable2020 ist eine Variable, weil sie mit einem Großbuchstaben beginnt.

e) kloss_mit_soss ist ein Atom, weil es mit einem Kleinbuchstaben beginnt.

f) kloss mit soss ist weder Atom noch Variable, weil es Leerzeichen enthält.

Closed-World Assumption

Diese beschreibt die Annahme einer geschlossenen Welt, in der alles, was nicht als wahr bekannt oder ableitbar ist, falsch ist.

Rekursion

Bei Rekursion wird in der Definition einer Funktion dieselbe Funktion erneut verwendet, allerdings angewendet auf ein kleineres oder einfacheres Argument. Analog können Prädikate rekursiv definiert werden.

bei Prolog muss mann zwischen der

• deklarativen Semantik, also der logischen Bedeutung eines Prolog-Programms,

• und seiner operationalen Semantik, also dem Ergebnis seiner Ausführung, unterscheiden muss.

• Die deklarative Semantik ändert sich durch die Vertauschung der Reihenfolge verschiedener Regeln bzw. der Bedingungen innerhalb einer Regel nicht,

• aber die operationale Semantik kann sich dadurch massiv ändern.

• Die Veränderung der Reihenfolge kann dazu führen, dass das Programm nicht mehr terminiert und also kein Ergebnis zurückliefert oder, bei mehreren korrekten Ergebnissen, diese in unterschiedlicher Reihenfolge liefert.

1. Rekursionsbasis (Basisfall): Der Fall, der die Rekursion beendet.

2. Rekursionsregel (Rekursionsfall): Die Regel, die die Rekursion definiert und fortführt.

Ohne eine ordnungsgemäße Rekursionsbasis würde die Rekursionsregel unendlich weiterlaufen, was zu einer Endlosschleife führen würde.

• Eine Antinomie ist eine logisch paradoxe Aussage,

• bei der sowohl die Annahme, dass die Aussage wahr ist,

• als auch die Annahme, dass die Aussage falsch ist, zu einem Widerspruch führt.

• Der erste Gödelsche Unvollständigkeitssatz besagt grob gesprochen, dass jedes hinreichend mächtige formale System entweder widersprüchlich oder unvollständig ist.

• Der zweite Gödelsche Unvollständigkeitssatz besagt, dass ein solches System seine eigene Konsistenz nicht beweisen kann.

a) Die Goldbachsche Vermutung lautet:

• „Jede gerade Zahl größer 2 lässt sich als Summe zweier Primzahlen darstellen.“

b) Gemäß dem Gödelschen Unvollständigkeitssatz gibt es folgende mögliche Ergebnisse für die Lösung des Problems:

b) Drei Möglichkeiten:

• wahr und beweisbar

• falsch mit Gegenbeispiel

• wahr, aber nicht beweisbar

Kurze Lösung

a) Prädikatenlogik mit Arithmetik

b) Aussagenlogik, somit auch Prädikatenlogik und Prädikatenlogik mit Arithmetik

c) Prädikatenlogik, somit auch Prädikatenlogik mit Arithmetik

d) Prädikatenlogik mit Arithmetik

e) Prädikatenlogik mit Arithmetik

Ausführliche Lösung

a) Die Aussage erfordert Prädikatenlogik mit Arithmetik, denn sie enthält Begriffe der Arithmetik wie „gerade Zahl“, „größer“, „Summe“ und „Primzahl“.

b) Die Aussage kann im Rahmen der Aussagenlogik als 𝐴 ∨ ¬𝐴 formalisiert werden. Somit ist die Aussage auch im Rahmen der Prädikatenlogik und im Rahmen der Prädikatenlogik mit Arithmetik darstellbar.

c) Die Aussage kann im Rahmen der Prädikatenlogik als ∃𝑥∀𝑦 ⋅ 𝑃(𝑥, 𝑦) ⇒ ∀𝑦∃𝑥 ⋅ 𝑃(𝑥, 𝑦) formalisiert werden. Somit ist die Aussage auch im Rahmen der Prädikatenlogik mit Arithmetik darstellbar.

d) Die Aussage erfordert Prädikatenlogik mit Arithmetik, denn sie enthält Begriffe der Arithmetik wie „ganze Zahl“, „natürliche Zahl“, „größer“ sowie die Gleichung 𝑥 𝑛 + 𝑦 𝑛 = 𝑧 𝑛 .

e) Die Aussage erfordert Prädikatenlogik mit Arithmetik, denn sie enthält Begriffe der Arithmetik wie „unendlich viele“ und „Primzahl“

In einem wiedersrpüchlichen Kalkül lassen sich alle Aussagen als wahr beweisen —> Er ist wertlos.