Im Stoff geht es heute weiter mit dem Kapitel Prädikatenlogik,
Prädikatenlogik erster Stufe.
Bei der Prädikatenlogik kann man das so ein bisschen sehen als eine
Erweiterung dessen, was wir bereits mit der Aussagenlogik gemacht
haben.
Das heißt, Sie werden jetzt viele von den Mechanismen wiedersehen, die
wir schon angewandt haben bei der Aussagenlogik.
Sie werden also sehen, wie man schrittweise aus einzelnen Komponenten
so eine Formel erstmal syntaktisch korrekt aufbaut.
Welche Regeln es also gibt, um erstmal syntaktisch korrekte
prädikatenlogische Formeln hinschreiben zu können.
Und dann der zweite Schritt ist, wir machen uns Gedanken darüber, was
bedeuten diese prädikatenlogischen Formeln.
Wir schauen uns die Semantik an.
Wir werden dafür wieder diese Value-Funktion kennenlernen.
Wir werden kennenlernen, was eine Interpretation ist und wir werden
aber auch noch kennenlernen, was dann bei der Prädikatenlogik eine
Variablebelegung ist.
Und da kollidieren so ein bisschen die Begriffe.
Sie können sich erinnern, eine Interpretation bei der Aussagenlogik,
da haben wir gerade Variable belegt.
Bei der Prädikatenlogik bekommt jetzt der Begriff der Interpretation
eine andere Bedeutung und stattdessen wird der Begriff der
Variablebelegung separat nochmal eingeführt.
In einer ähnlichen Art und Weise, wie wir das eigentlich schon bei der
Aussagenlogik hatten.
Plus wir werden sehen, bei der Prädikatenlogik wird das Ganze noch ein
bisschen komplizierter, was so eine Interpretation, die Semantik einer
prädikatenlogischen Formel angeht.
Weil wir dann zusätzlich noch umspielen werden mit der Menge, über die
wir Variablen und Konstanten belegen werden.
Und wenn wir dann wissen, was die Semantik ist, dann gibt es wieder
die gleichen Begriffe wie allgemeingültige Formeln, Modell einer
Formelmenge, so wie wir das bei der Aussagenlogik hatten.
Und dann im letzten Schritt, den wir heute vermutlich dann nicht mehr
schaffen werden, der wird dann für Mittwoch vorbehalten sein, werden
wir uns überlegen, wie können wir jetzt beweisen.
Und bei der Aussagenlogik haben Sie für das systematische Beweisen
bereits kennengelernt den Begriff des Kalküls.
Sie erinnern sich, ein Kalkül hatte ein Alphabet, hatte eine Menge von
Formeln, hatte Schlussregeln.
Und auch hier werden Sie ein Kalkül kennenlernen, das sogenannte
Hilbert -Kalkül, mit dem Sie dann prädikatenlogische Formeln beweisen
können.
Also fangen wir ganz langsam an mit der Syntax der prädikatenlogischen
Formeln.
Prädikatenlogische Formeln sind deutlich komplizierter aufgebaut als
Aussagenlogische Formeln.
Wenn wir uns anschauen, Aussagenlogische Formeln, da hatten wir
Variablen und wir hatten Konnektive.
Bei den prädikatenlogischen Formeln kommen jetzt noch drei weitere
Dinge hinzu.
Wir fügen hinzu Funktionen, also Abbildungen.
Wir fügen hinzu Relationen, also allgemeine Relationen, die nicht
notwendigerweise Abbildungen sind.
Und wir fügen hinzu sogenannte Quantoren.
Das, wo Sie alle schon so mehr oder minder intuitiv mit rumagiert
haben, dieses für alle es existiert, das nennen wir die Quantoren, die
werden auch hinzugefügt.
Und dann kann man mithilfe dieser Bestandteile, die man hat, den
Bestandteilen aus der Aussagenlogik, aus der formalen Sprache, der
syntaktisch korrekten Aussagenlogischen Formeln, unterhin Zunahme von
Konstanten, das ist noch das Vierte, was noch hinzukommt, von
konstanten Funktionen kann man anfangen, Terme aufzubauen.
Hinterher bei der Semantik wird man sehen, bei diesen Termen sind die
immer von der Form, da kommt erstmal irgendein Wert aus irgendeiner
Grundmenge heraus, beispielsweise natürliche Zahlen, reelle Zahlen,
kann aber irgendwas Beliebiges sein.
Aus diesen Termen, die also aus variablen Symbolen, Konstanten und
Funktionen bestehen, da wird also irgendwas abgebildet von einer Menge
wieder in eine andere Menge, kann man dann atomare Formeln machen.
Und diese atomaren Formeln nimmt man dann mithilfe von
Relationssymbolen.
Wir haben also dann Relationen, Relationen als Teilmenge eines
kathesischen Produktes zweier Mengen.
Das müssen dann logischerweise die Mengen sein, in die man mithilfe
der Funktionen, der Konstanten und der Variablen abbildet.
Und diese Werte, die bei den Termen rauskommen, die werden dann mit
Relationen zueinander ins Verhältnis gesetzt oder verglichen.
Und entweder sie sind im Verhältnis zueinander gegeben, diese
Relation, oder sie sind eben nicht im Verhältnis zueinander gegeben,
diese Relation.
Das hat dann hinterher Auswirkungen darauf, was hat diese
prädikatenlogische Formel für eine Bedeutung.
Und diese atomaren Formeln, die dann aus den Termen und den
Relationssymbolen bestehen, mit denen ich diese Termen in Relation
setze, mache ich dann hinterher mithilfe aussagenlogischer Konnektive,
so wie ich das aus der Aussagenlogik kenne, und mithilfe der Quantoren
dann echte prädikatenlogische Formeln.
Jetzt ist die Syntax aufwendiger.
Wir haben also da deutlich mehr Bestandteile, als wir das zum Beispiel
bei der Aussagenlogik hatten.
Aber die prädikatenlogischen Formeln sind damit auch mächtiger.
Alles, was ich mithilfe der Aussagenlogik ausdrücken kann, kann ich
über einen kleinen Umweg auch mithilfe der Prädikatenlogik ausdrücken.
Aber ich kann halt noch deutlich mehr mithilfe der prädikatenlogischen
Formeln ausdrücken, weil ich halt auch Funktionen, Konstanten,
richtige Relationen habe, zusätzlich zu den Konnektiven, die ich bei
der Aussagenlogik habe.
Und deswegen kann man zum Beispiel viele natürlichsprachliche
Aussagen, die man so aufwendig in Worte fassen müsste, kann man da
relativ kompakt und schön mithinschreiben.
Wenn ich Definitionen hinschreibe, wenn ich irgendwelche Sätze
hinweise, wenn ich Beweise durchführe, später natürlich auch, wenn ich
jetzt Informatiker bin, wenn ich Algorithmen verifizieren möchte, ob
der Algorithmus das tut, was er will, kann ich da so Teilaussagen
immer schön mit prädikatenlogischen Formeln hinschreiben und kann dann
bei der Verifikation immer überprüfen, zu bestimmten speziellen
Zeitpunkten.
In einem Algorithmus ist diese prädikatenlogische Formel auch
bitteschön immer wahr.
Und nur wenn sie immer wahr ist, dann ist zum Beispiel der Algorithmus
auch korrekt.
Und allgemein in der Mathematik werden Sie das an vielen Stellen
sehen.
Bei der Verifikation von Algorithmen können Sie sich das so
vorstellen, das werden wir dann in naher Zukunft noch ein bisschen
formaler und genauer besprechen, aber Schleifen sind zum Beispiel so
etwas, das ist immer ein Kandidat dafür, irgendwas falsch zu machen.
Meistens hat man ja eine Schleife, eine Abbruchbedingung und in der
Schleife wird irgendwas berechnet und dann kann man meistens schön das
hinschreiben, was diese Schleife macht, mit Hilfe von
prädikatenlogischen Formeln.
Sie können eine Vorbedingung hinschreiben, Sie können, nachdem die
Schleife fertig gelaufen ist, hinschreiben, was soll denn jetzt
gelten, nachdem die Schleife komplett durchgelaufen ist und innerhalb
der Schleife können Sie hinschreiben, was soll vor jedem Durchgang der
Schleife gelten und was soll nach jedem Durchgang der Schleife gelten.
Und wenn Sie dann sozusagen die Richtigkeit dieser prädikatenlogischen
Formeln beweisen können, mit Hilfe der Schritte, die in dieser
Schleife ausgeführt werden, dann haben Sie zum Beispiel auch
nachgewiesen, dass die Schleife genau das macht, von dem Sie auch
gehofft haben oder gedacht haben, dass sie das macht.
Bei einfachen Schleifen kann das wahrscheinlich noch durch Draufgucken
gemacht werden, aber auch da werden erstaunlich viele Fehler gemacht.
Also viele Fehler beim Programmieren entstehen bei so Extremfällen
oder Endfällen in der Schleife, dass die Schleifenabbruchbedingung
nicht richtig gemacht wurde.
Aber es gibt durchaus auch hinterher kompliziertere Schleifen, wenn
man ein bisschen was Komplizierteres macht, da kann das dann nicht
mehr so durch einfaches Draufschauen gemacht werden, aber dann kann
man halt das verifizieren mit Hilfe solcher Methoden.
Und das Schöne ist, dadurch, dass ich jetzt hier etwas habe, was ich
syntaktisch korrekt definieren kann, eindeutig definieren kann, muss
ich das hinterher nicht mehr selber machen, sondern Sie werden ja
Informatiker und als Informatiker wird man nicht Informatiker, dass
man hinterher selber komplizierte Formeln per Hand ausrechnet.
Es gibt welche, die machen das, sondern die theoretischen
Informatiker.
Aber auch als theoretischer Informatiker will man hinterher Programme
schreiben, die für mich verifizieren.
Also das große Ziel ist am Ende, dass man halt ein Programm schreibt,
das einem all diese Beweisen und die Verifizierung des Algorithmuses
hinterher abnimmt.
Man ist noch nicht so weit, also es gibt zum Teil Programme, die das
schon zu einem gewissen Maß leisten, aber ich meine, der Traum ist,
Sie schreiben ein Programm, Sie tun das in den Verifizierer rein und
der sagt Ihnen dann hinterher, ist es richtig oder nicht richtig.
Und vielleicht ist es von da irgendwann auch der Schritt dahin, dass
das Programm gibt, dass das Programm schreibt, das man haben möchte,
auch nicht mehr ganz so weit.
Aber bevor wir dahin kommen, müssen wir uns jetzt erstmal immer noch
mit solchen Prädikaten, logischen Formeln und der korrekten Syntax
auseinandersetzen, damit Sie hinterher der Star-Informatiker sind, der
den allgemeinen Programmbeweiser schreiben wird.
Also, wir haben Variablen-Symbole.
Das kennen Sie schon aus der Aussagen-Logik.
Da hieß die Menge damals var.al, jetzt heißt sie var.pl, weil wir sind
in der Prädikaten-Logik.
Da sind Variablen drin, endlich viele, die erstmal im Allgemeinen
durchnummeriert werden, von 0 bis irgendeinem Index k, die nennen wir
xi.
Und weil das so unschön ist, die zu schreiben, schreiben wir
stattdessen kleine Buchstaben aus dem oberen Ende des lateinischen
Alphabetes, also sowas wie x, y, z, u, v, w, irgendwas, was hinten
kommt.
Und dem gegenüber gibt es Konstantensymbole, ci.
Wieder endlich viele, also 0 bis k viele Konstantensymbole.
Und da schreiben wir dann Buchstaben, eher aus dem vorderen Ende des
Alphabetes, anfangen bei c wie Konstante und dann d, e, f.
Und wenn man da nicht aufpasst, kollidiert man irgendwann.
Das heißt, wenn man also irgendso einen kleinen Buchstaben da sieht in
einer Prädikaten-Logischen-Formel, muss man sich immer im Klaren
darüber sein, reden wir jetzt hier von einer Konstanten oder reden wir
hier von einer Variable.
Und dann gibt es Funktionssymbole, Abbildungen, nennen wir sie fun.pl.
Das ist also hier, wo der Fun anfängt, würde Sheldon Cooper sagen.
Also jedenfalls, hier fängt also der Spaß an mit der Funktion von der
Prädikaten -Logik.
Da gibt es wieder endlich viele, f0 bis fk.
Statt fi schreiben wir halt kleine Buchstaben aus der Mitte des
Alphabetes, irgendwo bei f angefangen, fgh.
Und jetzt hat jede Funktion, jede Abbildung eine Stelligkeit.
Und diese Stelligkeit besagt nichts anderes als, wie viele Argumente
nimmt denn diese Funktion an.
Also bildet die aus einer Menge ab in eine andere Menge, dann ist sie
einstellig.
Bildet sie aus dem kathesischen Produkt zweier Mengen heraus ab, dann
ist sie zweistellig.
Bildet sie aus dem kathesischen Produkt dreier Mengen heraus ab, dann
ist sie streistellig und so weiter und so fort.
Und diese Stelligkeit geben wir an, wieder mithilfe einer Abbildung,
die halt abbildet von den Funktionen der Prädikaten-Logik in die
positiven natürlichen Zahlen.
Das heißt, es gibt also keine Funktion mit Stelligkeit 0.
Und dann können wir uns erstmal das Alphabet der Terme definieren.
Für Terme brauchen wir sowas wie eine runde Klammer auf, wir brauchen
sowas wie ein Komma und eine runde Klammer zu.
Und tun damit zusätzlich hinein die Variablen, die Konstanten und die
Funktionen.
Damit haben wir ein Alphabet für Terme bekommen.
Und jetzt müssen wir uns überlegen, wie wir über diesem Alphabet
syntaktisch korrekte Terme erstmal definieren können.
Sie erinnern sich noch, in der Aussagen-Logik hatten wir das
ursprünglich mal gemacht über solche Konstruktions-Abbildungen, mit
denen wir dann für jedes Konjektiv hatten wir eine Konstruktions
-Abbildung.
Und dann haben wir ins Induktiv die syntaktisch korrekten
aussagenlogischen Formeln definiert.
Jetzt sind wir aber in der Vorlesung schon weiter.
Wir kennen inzwischen das Werkzeug der kontextfreien Grammatik und
haben kennengelernt, wie man mit kontextfreien Grammatiken
tatsächliche Sprachen, sogenannte kontextfreie Sprachen definieren
können.
Und jetzt ist die Sprache, der Terme, der Prädikaten-Logik auch nichts
anderes als eine kontextfreie Sprache, die man mithilfe einer
kontextfreien Grammatik definieren kann.
Wir erinnern uns, eine kontextfreie Grammatik besteht aus einer Menge
von Nicht-Terminalsymbolen, einer Menge von Terminalsymbolen, das sei
an dieser Stelle das Alphabet der Terminalsymbole.
Dann brauche ich irgendein Staatssymbol, nennen wir es mal T, Teil der
Nicht -Terminale.
Und ich brauche Produktionen für die Terme der Prädikaten-Logik.
Angenommen, wir haben jetzt Funktionen und innerhalb der Funktionen
und später auch der Relation, im Augenblick haben wir nur Funktionen,
aber angenommen später, wenn wir dann übergehen zu den atomaren
Formeln und zu den prädikatenlogischen Formeln, haben wir dann auch
Relationssymbole, dann brauchen wir noch sowas wie immer die maximale
Stelligkeit.
Also sei m die maximale Stelligkeit der Funktionen.
Also es gibt keine Funktion, die mehr als m Argumente braucht.
Dann können wir uns diese Grammatik wie folgt zusammenbauen.
Wir nehmen erstmal die Menge der Nicht-Terminalsymbole her, das ist
offensichtlich das Symbol T, weil es unser Staatssymbol auch sein
soll, und vereinigen das mit diesen m Symbolen li, l1 bis lm.
Und dann definieren wir uns Produktionen.
Und jetzt kommen wir wieder nicht um die Induktionen drumherum.
Während wir also bei den aussagenlogischen Formen mithilfe dieser
Konstruktionsabbildungen induktiv definiert haben, wie so eine
syntaktisch korrekte aussagenlogische Formel drumherum kommt, müssen
wir diesmal die Induktionen anwenden, um die Produktionen dieser
kontextfreien Grammatik zu beschreiben, die jetzt die Terme
entsprechend definieren soll.
Das heißt, wir definieren uns einen Induktionsanfang, das ist l1.
l1 bildet ab auf T, auf das Staatssymbol T.
Und li plus 1 bildet ab auf li, T.
Also li, T, hier das Komma nicht mit dem senkrechten Strich
verwechseln.
Das ein Wort li, T ist ein Wort, auf das li plus 1 abgebildet wird.
Dadurch, dass das i immer 1 kleiner wird, ist das tatsächlich schön
wohl definiert.
Es ist alles definiert, diese Rückwärtsinduktion hört irgendwann auf,
nämlich bei dem l1.
Und jetzt müssen wir aufpassen, dass wir da in keine Schleife
reinlaufen.
Also das l1 bildet ab auf T, und jetzt müssen wir uns noch überprüfen,
ob das T nicht plötzlich wieder auf irgendeinen lk abbildet mit k
größer gleich 1.
Weil wenn das passieren würde, dann hätte ich sozusagen so eine
Schleife.
Das wäre zwar nicht schlimm, aber wir müssen aber auch aufpassen, dass
wir auch irgendwann aus dieser Schleife aufhören, dass wir also nicht
nur unendlich lange Wörter bauen können.
Also das l1 bildet ab auf T, und das T bildet dann entweder ab auf ein
Konstantensymbol, oder das T bildet ab auf eine Variable, oder das T
bildet ab auf eine Funktion.
Und diese Funktion, die hat eine Stelligkeit.
Die hat die Stelligkeit Argument von fi.
Das heißt, die braucht Argument von fi, Argumente.
Und da tue ich halt entsprechend wieder das l von Argumenten von fi
rein.
Was soll uns das Ganze jetzt sagen?
Was kann ich denn mit sowas machen?
Jetzt kann man erstmal hingehen und sich das irgendwie allgemein
anschauen.
Also solche Terme aus der Aussagenlogik.
Was sind so die einfachsten Fälle?
Die einfachsten Fälle ist, ich mache es aus einem Term eine Konstante,
oder ich mache aus einem Term eine Variable.
Also jedes Konstantensymbol und jede Variable ist erstmal ein Term für
sich.
Weil ich muss ja bei dem T anfangen.
Das T ist mein Startsymbol.
Das Einfachste ist Konstante oder auf eine Variable, dann habe ich da
ein relativ maximal kurzes Wort abgebildet.
Das leere Wort ist offensichtlich keine.
Keine korrekter Term, auch das kann ich nicht abbilden.
Und dann kann ich noch abbilden dieses T auf eine Funktion.
Und in der Funktion steht dann so ein l drin.
Das sind Argumente, und zwar das l mit dem Unterstrich, so viele
Argumente wie die Funktion braucht.
Jetzt hat man ja schon gesagt, diese Buchstaben haben alle irgendwie
immer eine Bedeutung.
T ist das Startsymbol und steht offensichtlich für Term.
Weil ich will dann einen Term ableiten aus dem T.
Wofür steht das l?
Wenn man jetzt hinguckt, wie ich diese ls zusammensetze.
Wofür steht das l offensichtlich?
Ja?
Genau, das steht für Liste.
Weil das l macht nichts anderes, als dass es mir am Ende Terme
aufbaut.
Und zwar ein li plus 1 macht insgesamt hinterher eine Liste von i
Termen.
Und diese Liste ist durch Kommata separiert.
Das heißt, meine Funktion selber nimmt als Argument eine Liste von
Argument von fi vielen Termen, die in diese Funktion reinkommen.
Das heißt, wenn ich hinterher mich um die Semantik kümmere, der Terme,
dann muss ich aufpassen, dass die Funktion mit so einer Stelligkeit
dann entsprechend auch von diesen Werten, die den Termen entsprechen,
auch entsprechend vernünftig aus abbildet.
Machen wir ein einfaches Beispiel.
Nehmen wir an, wir haben zwei Variablen xy, eine Konstante c und dann
haben wir zwei Funktionen f und g. Die Funktion f, die nehmen zwei
Argumente und die Funktion g, die nehmen ein Argument.
Also maximale Argumentzahl ist gleich zwei.
Und aus der Liste der Nicht-Terminale wäre dann entsprechend t, l1,
l2.
Dann habe ich halt entsprechend nach der Definition Produktionen l2
auf l1 und t, l1 auf t und t wird entweder abgebildet auf c, x oder y.
Oder t wird abgebildet auf g von l1 oder g von l2.
Und dann kann man sich halt anschauen, was sind so mögliche
Abbildungen.
Aus dem l1 kann ich zum Beispiel ableiten eine Konstante.
Oder aus dem t kann ich abbilden ein g von c, ein g von einer
Konstante.
Oder ich kann aus dem l2 ableiten eine Liste, die zwei Terme enthält,
x und gc.
Und aus dem t kann ich dann entsprechend ableiten eine Funktion f, die
braucht zwei Argumente und in diese zwei Argumente sind halt diese
Liste x und g von c zum Beispiel.
Das heißt also diese Produktionen sorgen halt genau dafür, dass das
rauskommt, was ich so vom Prinzip her haben will.
Ich will in der Lage sein, solche Terme zu bauen, aus denen hinterher
ein Wert aus dem Zielbereich rauskommt.
Und das mache ich, indem ich entweder einen Wert aus dem Zielbereich
hinschreibe, entweder implizit mit einer Variable, die ich hinterher
belegen muss, oder mit einer Konstante.
Oder indem ich halt eine Funktion hinschreibe, die braucht halt eine
bestimmte Anzahl an Argumenten und die Argumente selber können
entweder ein direkter Wert sein, sie können eine Variable sein, oder
sie können wieder eine Funktion sein, wo hinterher ein Wert rauskommt.
Und diese Funktionen kann ich sozusagen beliebig tief staffen, wenn
ich das möchte.
Nicht ableitbar sind dementsprechend solche Sachen wie xy.
Ergibt keinen Sinn.
c von x ergibt auch keinen Sinn, weil c keine Funktion ist, sie nimmt
keine Argumente auf.
Ich kann auch nicht so schlecht geklammerte Dinger ableiten.
Und für jede Funktion ist auch sichergestellt, dass die Anzahl der
Argumente, die zwischen den Klammern steht, auch wirklich ihrer
Wertigkeit entspricht.
Da g also Wertigkeit 1 hat, kann ich sowas wie g von c, c, c, x halt
nicht ableiten.
Dann, wenn ich solche Terme habe, kann ich anfangen atomare Formeln zu
bauen.
Und da brauche ich jetzt wieder ein Alphabet.
Und dieses Alphabet wird wieder aufgebaut aus dem Alphabet der Terme,
die ich habe, und einem neuen Alphabet.
Und das Alphabet nenne ich die Alphabet der Relationen der
Prädikatenlogik.
Bei diesen Relationen der Prädikatenlogik sind, wie der Name schon
sagt, logischerweise Relationen drin.
Aber es gibt immer eine Relation, die immer dabei ist.
Und das ist diese Relation, die hier geschrieben ist mit einem Gleich
und einem Punkt drüber.
Dieses Gleich mit dem Punkt drüber, das kennen Sie schon.
Das kennen Sie vom Programmieren her.
Wenn Sie Java programmieren, in Java ist das glaube ich so, wenn Sie
abprüfen wollen, ob zwei Werte, zwei Variablen gleich sind, dann
schreiben Sie so ein Doppelgleichheitszeichen, gleich gleich.
Und das ist letztendlich genau das Gleiche.
Das wird hier halt geschrieben als Gleichheitszeichen und oben so ein
Punkt drüber.
Kann sich einer vorstellen, warum?
Warum schreiben wir nicht gleich gleich?
Warum man in Java nicht gleich mit einem Punkt oben drüber schreibt,
ist klar.
Da werden Sie auf der Tastatur lange suchen müssen, bis Sie die Taste
finden, dass Sie über ein Gleichheitszeichen einen Punkt setzen
können.
Warum schreiben wir hier nicht gleich gleich?
Was wäre das Unschöne daran, wenn wir hier gleich gleich schreiben
würden?
Das Unschöne daran wäre, dass man ja sich vorstellen könnte, dass man
auch das einfache Gleichheitszeichen irgendwo hat.
Und das findet man häufig irgendwie als ein einfaches Symbol, als ein
Zeichen in unserem Mindset.
Und gleich gleich müsste ja auch ein Zeichen sein aus dem Alphabet,
das jetzt in unserem Kopf, so der Kopf denkt, das sind zwei Zeichen.
Und dann wird es schwierig, das zu trennen, um auszudrücken, dass es
wirklich nur ein Zeichen ist.
Schreibt man das halt als gleich mit dem Punkt drüber, dann kann man
als Mensch gleich erkennen, okay, das ist nur ein Zeichen.
Wenn ich hinterher Zeichen zählen muss zum Beispiel oder so, dann
zähle ich nicht aus Versehen beim gleich gleich zwei Zeichen.
Zu einer der Gründe, warum man das besser so hinschreibt.
Und dann habe ich halt beliebige Relationen, endlich viele R0 bis Rk
-Relationen.
Und die schreiben wir halt mit großen lateinischen Buchstaben,
möglichst angefangen bei R, also R, S, T und so weiter und so fort.
Und so eine Relation hat auch eine Stelligkeit, genauso wie eine
Abbildung eine Stelligkeit hat, hat halt auch eine Relation eine
Stelligkeit.
Weil eine Relation ist immer die Teilmenge eines kathesischen
Produktes von zwei oder mehr Mengen.
Und die Stelligkeit sagt mir halt an, wie viele Mengen ich da per
kathesischen Produkt miteinander zusammen kombiniert habe.
Jetzt fange ich also an, mir das Alphabet der atomaren Formeln
aufzubauen.
Das nenne ich dann halt A, wie atomare Formeln.
Und generell, weil die enthalten halt erstmal Relationen und dann auch
Terme, ist also die Vereinigung von diesem A-Ter und den
Relationssymbolen.
Und dann kann ich mir wieder eine Grammatik zusammenbauen, um jetzt
syntaktisch korrekte atomare Formeln aufzubauen.
Die Grammatik besteht wieder aus Nicht-Terminalsymbolen, nennen wir
sie RL, aus Terminalsymbolen.
Das ist logischerweise das Alphabet der atomaren Formeln, AREL.
Dann brauchen wir halt ein Startsymbol, A, wie atomare Formeln.
Und wir brauchen Relationen und Produktionen, wie P, REL.
Jetzt ist wieder M, unsere maximale Stelligkeit, diesmal von Funktions
- und tatsächlich auch Relationssymbolen, weil ich diesmal halt auch
Relationssymbole habe.
Und die Menge der Nicht-Terminale besteht aus A und T.
Das A für das Startsymbol muss logischerweise drin sein und das T sind
halt die Terme.
Und das vereinige ich wieder mit so einer Menge von Nicht
-Terminalsymbolen, mit denen ich mehr Listen aufbauen kann.
Ich nenne sie LI und es gibt halt L1 bis LK viele von denen.
Entschuldigung, LM viele, wobei M halt die maximale Stelligkeit ist.
Und die Produktionen, die bestehen jetzt aus den Produktionen der
Terminalsymbole.
Das heißt, wenn ich irgendwann mal einen T abgeleitet habe in dieser
Grammatik, dann kann ich daraus Terme ableiten.
Und ich fange jetzt an, aus dem Anfangssymbol ableiten zu können auf
diese Relation.
Ich kann also entweder das A ableiten auf eine meiner Relationen, die
ich mir da gegeben habe.
Und in dieser Relation brauche ich halt so eine Liste von Argumenten.
Und dieses L von den Argumenten, das steckt dann, wie es weitergeht,
das steckt halt in den Produktionen der Terme drin.
Das heißt, ich baue mir da wieder so Listen von Termen auf, die stecke
ich rein in die Relation.
Oder alternativ kann ich halt ableiten auf diese Relation, die ich
immer da habe.
Dieses gleich mit dem Punktzeichen drüber.
Und das setzt halt zwei Terme zueinander in der Relation.
Wenn ich mir das also anschaue, wie viele Relationen enthält,
Relationszeichen enthält damit eine atomare Formel.
Ich höre nicht alle auf einmal.
Genau hinschauen, wie viele, wenn ich mir die Produktionen anschaue.
Ich muss vom A anfangen.
Also muss ich eine von den beiden Produktionen auswählen.
Das A kommt in den Produktionen der Terme gar nicht drin vor.
Das kennt sich nur mit Termen aus, nicht mit atomaren Formeln.
Jetzt kann ich es einmal entweder auf einen Term ableiten, auf
irgendein Relationssymbol.
Entweder auf das gleich mit dem Punkt oder irgendeines dieser
beliebigen RIs.
Und dann steht rechts entweder Term gleich Term oder Relation und in
der Relation selber steht eine Liste von Termen drin.
Und von diesen Listen von Termen komme ich nie wieder auf ein
Relationssymbol.
Weil diese LIs, die stecken ja nur in dem p-Term drin.
Die stecken nirgendwo anders drin.
Das heißt also, wie viele Relationssymbole kann ich haben maximal in
einer atomaren Formel, die ich damit ableiten kann?
Eins.
Und zwar genau eins.
Ich kann daraus auch nichts ableiten, das kein Relationssymbol
enthält, weil dieses Gleichpunkt ist auch nichts anderes als eine
Relation.
Es ist halt eine besondere Relation.
Das heißt, so eine atomare Formel besteht irgendwie aus einer
Relation.
Und diese Relation setzt entweder zwei oder mehr Terme zueinander in
Relation.
Und die Terme selber sind wieder irgendwie sowas Geschachteltes aus
konstanten Variablen oder Funktionen über konstanten und Variablen
oder anderen Funktionen.
Also, wenn wir jetzt uns Variablen, Konstanten und Funktionen mal
geeignet wählen.
Also die sind irgendwie vernünftig da.
Die schreiben wir jetzt nicht wieder hin, wie die sein müssen, sondern
aus den Beispielen, wenn wir sagen, dass es ableitbar, dann kann man
daraus offensichtlich was geeignetes ableiten.
Wenn jetzt die Relationssymbole, die wir haben, seien R und S, die
Stelligkeit von R sei 3 und die Stelligkeit von S sei 1, dann kann ich
halt sowas ableiten, wie zwei Terme werden mit diesem Gleich- und dem
Punkt übereinander in Relation gesetzt.
Und der Term selber, das kann eine Funktion sein, das kann eine
Variable sein oder halt was Geschachteltes.
Das kann also sowas sein wie g von x gleich f von x, g von z.
Oder es kann auch einfach nur eine Relation S sein über einer
Konstanten c.
Das heißt, diese Relation selber kann auch einstellig sein.
Oder es kann halt eine mehrstellige Relation sein und innerhalb der
Relation ist dann halt so eine Liste von Konstanten y, c, g und so
weiter und so fort.
Was halt nicht funktioniert ist, dass man Sachen zueinander in
Relation setzt, die nicht zueinander in Relation sein dürfen.
Relationen, es dürfen nur Terme zueinander in Relation stehen.
Das heißt, sowas wie Relation gleich Punkt f darf nicht sein, weil
links von dem Gleichheitszeichen steht eine Relation und kein Term.
Und ein Term enthält höchstens Abbildungen, Konstanten oder Variablen.
Dann darf meine Formel halt nur genau ein Relationszeichen enthalten.
Das heißt, das erste enthält schon mal zwei Relationszeichen.
In diesem Fall zweimal das gleiche mit dem Punkt.
Darf auch nicht sein.
Da hinten, die dritte in der obersten Zeile, da werden wieder zwei
Relationen zueinander in Relation gesetzt.
Das darf nicht sein.
Dann habe ich hier so etwas wie r von x, y.
Das darf nicht sein, weil...
Mann, da stehen ja nur Terme drin.
Weil r eine dreiwertige Relation ist.
Das heißt, darf ich nicht machen.
Dann sowas wie f von s von x darf ich auch nicht ableiten.
Da steht zwar ein Relationssymbol drin, genau ein Relationssymbol.
Aber nicht alles, was genau ein Relationssymbol enthält, ist auch eine
atomare Formel.
Weil ich außen einen Term stehen habe.
Und ich muss irgendwie zumindest dann auf der obersten Ebene Terme
zueinander in Relation setzen.
Erst dann ist es eine atomare Formel.
Das heißt, darf ich auch nicht ableiten.
Und dann sowas wie r von s von x, x, x geht auch nicht.
Weil eine Relation nimmt als Werte nur Terme, aber keine allgemeinen
Relationen an.
Das heißt also, das geht auch nicht, weil das s von x darf nicht
drinstehen.
Auch wenn das jetzt Wertigkeit 3 hat, s von x ist kein gültiges
Argument von r.
Weil es halt eine Relation ist und kein Term.
Dann sowas falsch geklammertes geht schon mal gar nicht.
Und sowas hier kann man auch nicht machen, weil diese komischen Pfeile
da, das ist erstmal nicht richtig geklammert.
Und dann diese Konnektive, die kennen wir ja schon, die kommen erst
später ins Spiel bei tatsächlichen prädikatenlogischen Formeln, aber
nicht bei atomaren Formeln.
Bei denen noch nicht.
Wenn ich jetzt also solche atomaren Formeln erzeugen kann, dann kann
ich jetzt endlich dazu übergehen, dass ich jetzt im dritten Schritt
tatsächliche prädikatenlogische Formeln erzeugen kann.
Ich brauche jetzt wieder ein Alphabet, das Alphabet der
prädikatenlogischen Formeln, hier nur noch a4 genannt.
Und das ist eben gerade dieses Alphabet der atomaren Formeln, die nur
Relationen enthalten, vereinigt mit den Konnektiven aus der
Aussagenlogik und zwei neuen Symbolen, die wir die Quantoren nennen.
Dieses umgekehrte a ist halt der Allquantor und dieses gespiegelte e
ist der Existenzquantor.
Und dann kann ich mir wieder eine kontextfreie Grammatik
zusammenbauen, mit denen ich dann die prädikatenlogischen Formeln
erzeugen kann.
Ich habe Nicht-Terminalsymbole, ich habe ein Staatssymbol, F wie
Formel und ich habe Produktionen für Formeln.
Die Nicht-Terminalsymbole enthalten wieder offensichtlich das F und
ansonsten nur die Nicht-Terminalsymbole der atomaren Formeln, die nur
so Relationen enthalten, die genau eine Relation enthalten.
Und die Produktionen F vor, setze ich halt zusammen, das sind die
Produktionen der atomaren Formeln und die Produktionen der atomaren
Formeln enthielten unter anderem die Produktionen der Terme.
Das heißt, da stecken auch die Produktionen der Terme hin und dann
kann ich halt vom Staatssymbol F anfangen und daraus
prädikatenlogische Formeln ableiten.
Als erstes kann ich aus dem Staatssymbol F eine atomare Formel
ableiten, A.
Das heißt, jede atomare Formel ist automatisch auch eine
prädikatenlogische Formel.
Oder ich kann halt was Komplizierteres ableiten.
Ich kann aus einer prädikatenlogischen Formel zum Beispiel ableiten,
dass ich da so ein Außenterminologisches Nicht davor setze und das
Ganze dann sicherheitshalber klammere.
Oder ich kann aus einer Formel ableiten, dass ich zwei Formeln mit
einem und verbinde oder mit einem oder verbinde oder mit diesem
Implikationsfall verbinde.
Das heißt, wenn ich meine Formel habe, eine korrekte
prädikatenlogische Formel, dann kann ich die auch wie in der
Aussagenlogik über die Quantoren miteinander verbinden.
Und dann kann ich halt zusätzlich noch was mit den Quantoren machen.
Und zwar kann ich vor eine Aussagenlogische Formel so einen Quantor
stellen und der Quantor hat immer die Form Quantor und eine Variable.
Also entweder kann ich da vor eine Formel stellen für alle x, y, x, y
eine Variable f oder ich kann mir vorstellen, es gibt ein x, y, f.
Und damit kann ich dann alle syntaktisch korrekten prädikatenlogischen
Formeln ableiten.
Dann habe ich da halt relativ viel Klammerung drin, um halt mehr
Deutlichkeiten zu vermeiden.
Jetzt hatten wir in der Aussagenlogik schon kennengelernt, dass man
halt Klammern einsparen kann.
Das kann man jetzt hier an der Stelle auch machen.
Wir haben die gleichen Klammer-Einsparungsregeln wie der
Aussagenlogik.
Und dann hatten wir halt so Bindungsstärken für die einzelnen
Konnektive, damit man halt nicht mehr Deutlichkeiten erhält, wenn man
zu viele Klammern weghält.
Und diese Vorrangregeln, die gelten auch hier in der Prädikatenlogik.
Und zusätzlich noch ist es so, dass diese Quantoren noch stärker
binden als alle anderen aussagenlogischen Konnektive, die wir haben.
Das heißt, wenn ich so eine syntaktisch korrekte aussagenlogische
Formel habe, zum Beispiel dieses für alle x, r von x, y und s von x,
dann sind da schon jede Menge Klammern weggefallen.
Weil das Erste, was einem auffällt, jede aussagenlogische Formel, die
so ein Quantor enthält, die muss außen drum herum Klammern haben.
Das sind also die Klammern, die ich schon mal weggelassen habe.
Und dann muss bei dem und eigentlich auch eine Klammerung drin.
Das heißt, was da oben steht, wer hatte mir bisher immer E-Mails
geschrieben?
Olje 12, kurzform von, was fehlt?
Ja, der Allquantor ist richtig geklammert.
Also ich habe da r von x, y und das habe ich mit einem Allquantor
davor und dann muss ich das einmal klammern.
Aber beim logischen und, da ist die Regel, da muss außen auch nochmal
eine Klammer drum herum und die Klammer fehlt.
Das heißt, Fehler auf der Folie, bitte E-Mail schreiben, dass ich
daran denke, dass ich das korrigiere.
Also da, selbst da ist ein Fehler drin, da müssten eigentlich hier
nach den Produktionen bei dem und, bei dem und steht, da müssen außen
Klammern drum herum.
Das heißt, da muss außen noch einmal drum geklammert werden.
Wichtig ist halt hier, dass man halt schön sieht, dass dieses für alle
x, das gilt nicht für dieses s von x, was da hinten steht hinter dem
und, sondern das gilt erstmal nur für das x, was in diesem r von x, y
steht.
Da muss man aufpassen, dass man die Klammerung da richtig liest.
Immer daran denken, dass für alle x windet stärker als das und.
Das heißt, wenn ich hinterher ans Auswerten gehe, da muss ich erstmal
das für alle x bis zu dem nächsten Konnektiv auswerten und dann kann
ich unabhängig davon das s von x auswerten und dann kann ich erst den
ersten Teil und den zweiten Teil auswerten.
Und genauso, wenn ich jetzt hier sowas habe wie das da.
Warum habe ich da nichts?
Da sind schon offensichtlich Klammern weggelassen, auch wieder die
äußeren Klammern, aber es macht einen Unterschied, ob ich diese
inneren Klammern habe oder nicht, weil ich damit diese Reichweite der
Quantoren miteinander binde.
Aber was ich zum Beispiel weggelassen habe, ist zum Beispiel diese
Klammern bei diesem Nicht und die Klammern um die Relation drumherum
und so weiter, das braucht man dann, kann man getrost weglassen.
Also, bisher an dieser Stelle haben wir uns erstmal nur damit
auseinandergesetzt, was sind syntaktisch korrekte prädikatenlogische
Formeln, wenn wir sie hinschreiben.
Wenn wir sie einfach als Wort, als Liste von Zeichen, als
Aneinanderhängung von Zeichen über einem Alphabet hinschreiben.
Und das haben wir in drei Stufen gemacht.
Wir haben uns erstmal Terme definiert, dann haben wir uns atomare
Formeln definiert und dann haben wir Formeln ausgebaut.
Und atomare Formeln bestehen aus Termen und Formeln bestehen aus
atomaren Formeln.
Wenn Sie jetzt so eine prädikatenlogische Formel sehen, können Sie
schon mal zumindest analysieren auf syntaktischer Ebene.
Sie können also gucken, ob das syntaktisch korrekt ist oder halt
Syntaxfehler finden.
Plus, wenn Sie prädikatenlogische Formeln hinschreiben, dann können
Sie halt Syntaxfehler entsprechend hoffentlich vermeiden.
Gut, jetzt der zweite, der interessantere Schritt.
Was bedeuten überhaupt diese prädikatenlogischen Formeln?
Damit wir herauskriegen, was bedeutet, was ist die Semantik so einer
prädikatenlogischen Formel, brauchen wir wieder den Begriff der
Interpretation.
Den hatten wir schon bei der Aussagenlogik gesehen und bei der
Aussagenlogik haben wir mit der Interpretation variablen Werte
zugewiesen.
Hier wird es jetzt komplizierter.
Hier hat erstmal die Interpretation noch gar nichts mit den Variablen
zu tun.
Wenn Sie da schauen, so eine Interpretation, das ist erstmal ein
Tupel, besteht aus einem sogenannten Universum D.
Das kann man sich vorstellen als eine Grundmenge, den man dann in die
konstanten Funktionen und Relationen in gewisser Art und Weise
abbildet.
Also bei Relationen ist es das, worüber die dann aufgebaut sind.
Also diese lichtleere Menge D sei das Universum und so eine Konstante
Ci, wenn ich die interpretiere, die Konstante, dann kommt eben gerade
ein Element aus diesem Universum heraus.
Das kann zum Beispiel eine natürliche Zahl sein.
Das muss nicht eine natürliche Zahl sein.
Wenn da also irgendein Symbol steht, das eine Konstante ist, dann kann
das alles beliebige sein.
Daraus wird erst etwas, wenn ich ihm eine Interpretation zuweise.
Wenn ich ihm also ein Universum zuweise, die Werte, die es annehmen,
die es sein kann, und dann festlege, jedes Konstantensymbol, welchem
Wert aus dem Universum entspricht es überhaupt.
Dann habe ich die Funktionen und solche Funktionen bilden halt ab aus
Argumentfunktionen, vielen Werten aus dem Universum, auf einen Wert
aus dem Universum.
Brauche ich für jedes Funktionssymbol, logischerweise.
Und dann habe ich die Relationen.
Und eine Relation war ja eine Teilmenge des kathesischen Produktes von
ein, zwei oder mehr Wengen.
Und dementsprechend ist so eine Relation dann halt entsprechend eine
Teilmenge dieses d hoch a Menge der Argumente der Relation.
Wobei dieses d hoch a, d ist eine Menge, dann entsprechend dem
kathesischen Produkt aus Argument mal viel diese Menge entspricht.
Relativ einfach in der Mathematik sieht man das häufiger.
Man kann zum Beispiel das Universum als die Menge der natürlichen
Zahlen nehmen.
Und dann kann ich der Konstanten den Wert 0 zuweisen und dann kann ich
sagen, wenn so eine Funktion f mit zwei Stellen da ist, dann kann die
zum Beispiel abbilden aus dem n0 hoch 2 in den n0.
Und x und y wird halt abgebildet auf die Summe aus x und y.
Oder wenn ich eine Relation habe, die hat jetzt Stelligkeit 2, dann
ist das eben eine Menge von Tuplen.
Die Teilmenge sind das n0 hoch 2, also n0 kathesisches Produkt n0.
Und zum Beispiel können das alle Tuplen x, y sein.
Für die gilt x kleiner gleich y.
Und da hat man schon gesehen, sowas kann man dann auch problemlos mit
infix -Schreibweise schreiben.
Das heißt, wir könnten dann auch statt der Relation R dann x kleiner
gleich y schreiben.
Das ist dann nur eine andere Notation der selben Relation, die wir
gesehen haben.
Andere Beispielinterpretationen, ich kann zum Beispiel jetzt als
Grundmenge die Menge der reellen Zahlen nehmen, dann eine Konstante c,
kann wieder den Wert zum Beispiel 0 annehmen.
Und wenn ich dann eine Funktion f habe, die ist wieder zweistellig,
wie vorher auch.
Und ich kann dann f von R² nach R abbilden und f von x, y soll halt
sein Sinus von x mal Cosinus von y.
Und die Relation soll diesmal der Form sein, dass sie alle x, y
zueinander in Relation setzt, für die x² kleiner gleich y hoch 4 gilt.
Ich kann jetzt also jedes Mal eine prädikatenlogische Formel
hinschreiben, die aus diesen Symbolen besteht, aus den Konstanten, aus
den Funktionen, aus dem Relationssymbol R.
Und je nachdem, welche Interpretation ich wähle, wird hinterher diese
prädikatenlogische Formel unter Umständen ganz andere Werte annehmen.
In Abhängigkeit davon, was ich halt als Universum nehme und in
Abhängigkeit davon, was ich halt jetzt als Semantik für die Funktionen
und die Relationen zuweise.
Und dann brauche ich jetzt zusätzlich noch zu dieser Interpretation
die Variablenbelegung.
Die Interpretation selber, die kümmert sich erstmal nur um die
Bedeutung von konstanten Funktionen und Relationen.
Und jetzt habe ich ja noch Variablen und denen weise ich jetzt halt
auch Werte zu aus diesem Universum.
Das heißt, ich habe eine Funktion, die nenne ich Beta, das sei halt
die Variablenbelegung.
Und diese Funktion Beta bildet jede Variable ab auf einen Wert aus dem
Universum.
Und wenn ich das gemacht habe, dann kann ich rangehen und die
eigentliche prädikatenlogische Formel auswerten.
Ich kann ihr ihren Wert zuweisen und dafür gibt es jetzt wieder die
Funktion wallen.
Und wir erinnern uns, bei der Aussagenlogik war es so, da gab es ein
wal -Unterscript i, niedriggestellt Groß i für Interpretation.
Und dann kam halt ein Wert aus wahr oder falsch raus.
Hier habe ich jetzt halt nicht nur eine Interpretation, die mir bei
der Aussagenlogik Variablen belegt, sondern hier habe ich drei Dinge.
Ich habe das Universum, ich habe die Interpretation, der sich um die
Konstanten und die Funktionen und die Relationen kümmert, wie die ins
Universum abbilden und ich habe noch die Variablenbelegung Beta, die
mir halt jetzt sagt, welche Variablen welchen Wert annehmen.
Und dann kann ich jetzt anfangen, mir diesen Wert der
prädikatenlogischen Formel anzugeben.
Und diese Auswertungsfunktion, die bildet ab aus den Termen und den
Formeln, also diese Auswertungsfunktion, weist Termen etwas zu und sie
weist Formeln etwas zu.
Und das, was zugewiesen wird, ist entweder ein Wert aus dem Universum
oder einer dieser beiden bool'schen Werte, wahr oder falsch.
Und diese Auswertungsfunktion soll halt so geformt sein, dass wenn ich
in die Auswertungsfunktion einen Term reinstecke, dann soll halt ein
Wert aus dem Universum rauskommen und wenn ich in die
Auswertungsfunktion eine Formel reinstecke, dann soll entweder der
Wert wahr oder falsch rauskommen.
Das heißt, ganz am Ende, der Wert einer prädikatenlogischen Formel ist
immer wahr oder falsch und ob die einzelnen Bestandteile, wozu die
sich auswerten, das hängt davon ab, ob es ein Term oder halt wieder
eine Formel sind, werden die einzelnen Bestandteile entweder wieder zu
einem Wert aus dem Universum zugefügt oder sie kriegen halt immer den
Wert wahr oder falsch.
Also, ganz einfaches Beispiel.
Wir haben ein Term und dann habe ich halt drei Möglichkeiten.
Ich kann entweder sagen, dass wenn ich so ein xi habe in dem Term,
dann kriegt der halt seinen Wert beta xi.
Wenn ich eine Konstante habe, dann kriegt die halt den Wert der
Konstanten.
Oder wenn dieser Term zusammengebaut ist aus einer Funktion, die als
Argumente wieder einzelne Terme bekommt, dann ist eben gerade die
Interpretation dieser Funktion oder ist gerade der Wert dieser
Funktion die Interpretation der Funktion in dem Universum.
Wenn ich jetzt geschachtelt jeden einzelnen Term, der Argument dieser
Funktion ist, auswerte.
Das heißt also, Variablen kriegen den Wert, Konstanten kriegen den
Wert und wenn ich dann Funktionen auswerte, dann muss ich halt erstmal
von innen nach außen raus mit der while-Funktion die einzelnen Werte
ausrechnen und kann dann ganz am Ende den Wert der äußersten Funktion
ausgeben.
Also angenommen wieder unser Universum sei die natürlichen Zahlen, die
Konstante c sei 0 und die Interpretation der Funktion f, das sei eben
die Addition auf die natürlichen Zahlen.
Wenn ich jetzt die Variable x den Wert 3 zuordne und der Variable y
den Wert 2, dann ist erstmal dieser Value-Wert der Funktion f von y, c
und dann muss ich jetzt von außen losgehen.
Das ist also der Wert, den ich erhalte, wenn ich die Interpretation
von f nehme und dann die einzelnen Terme, die Funktionswerte auswerte.
Gut, y und c sind einzelne Variablen, die werden halt belegt durch die
Beta -Funktion.
Das heißt, ich habe dann hinterher die Interpretation von f von 42 und
0 dastehen.
Das heißt, die Interpretation von f ist die Addition.
Das heißt, ich habe dahinter stehen 42 plus 0 gleich 42.
Das heißt also, der Wert dieser Formel mit der Interpretation di und
der Variablenbedingung beta ist gleich 42.
Ich kann auch was ganz anderes nehmen.
Ich kann mir zum Beispiel als Universum hernehmen den y-freien
Konkatenationsabschluss über dem Alphabet ab.
Dann muss ich der Konstanten c irgendein Element zuordnen und Elemente
aus dem Universum sind jetzt halt Worte.
Also kann ich der Konstanten c zum Beispiel das Wort bab zuordnen und
ich muss irgendwie die Funktion f interpretieren.
Das sei jetzt zum Beispiel halt die Konkatenation.
Und dann muss ich noch meinen Variablen irgendwelche Werte zuordnen
aus dem Universum.
Das heißt, die kriegen also auch Wörter, die nicht y sind, über dem
Alphabet ab.
Also x gleich 3 mal a und y gleich ba.
Und wenn ich jetzt wieder das Ganze auswerte und das ist jetzt wieder
genau dasselbe, was da steht.
Da steht erstmal f von y, c.
Das ist mein prädikatenlogischer Term.
Den werte ich jetzt aus.
Also muss ich das alles wieder, wie gehabt, nach innen ziehen, in die
Terme rein.
Dann wird aus dem y durch das beta irgendwann das ba.
Aus der Konstanten wird durch die Interpretation bab.
Und dann ist die Funktion die Konkatenation.
Und dann kommt halt raus die Konkatenation aus ba, bab.
Also das Wort bab ist damit die Interpretation.
Ist erstmal der Wert der Funktion f, y, c unter der Interpretation di
und der Variablenbelegung beta.
Ich kann jetzt also Termwerte zuordnen.
Jetzt muss ich als nächstes atomaren Formelnwerte zuordnen.
Ich habe also wieder meine Interpretation di gegeben.
Ich habe meine Variablenbelegung beta gegeben.
Und jetzt so eine atomare Formel, die kann halt aus zwei Dingern
bestehen.
Die atomare Formel kann erstmal bestehen aus so einer Relation mit
diesem Gleichheitszeiten mit dem Punkt drüber.
Und so ein Gleichheitszeiten mit einem Punkt drüber setzen mal zwei
Terme zueinander in Relation.
Und wir hatten ja schon gesagt, das soll diesem Gleich-Gleich
entsprechen.
Das heißt, der Wert von so einer Formel Term 1 Gleich-Gleich Term 2,
der soll halt wahr sein, wenn der erste Term und der zweite Term halt
den gleichen Wert haben, unter der Funktion der Auswertungsfunktion y
und ansonsten falsch.
Oder so eine atomare Formel besteht aus einem einzigen Relationssymbol
und in dem Relationssymbol selber sind wieder als Argumente k
verschiedene Terme, k die Stelligkeit der Relation.
Dann sage ich halt, das Ganze soll wahr sein, falls dieses N-Tupel,
das ich erhalte, indem ich jeden einzelnen Term in dem Tupel, der in
der Relation drin steht, wenn ich jeden einzelnen Term halt mit der y
-Funktion ausrechne und wenn der dann in der Interpretation dieser
Relation liegt oder falsch halt sonst, wenn er halt nicht in dieser
Interpretation liegt.
Dann kann ich jetzt atomare Formeln auswerten und mache jetzt halt
entsprechend...
ach so, ich mache erstmal noch ein Beispiel für atomare Formeln.
Angenommen, ich habe als Universum wieder die natürlichen Zahlen, ich
habe eine Konstante, die wird auf 0 gesetzt, ich habe eine Funktion,
die sei die Addition und ich habe eine Relation, die sei das kleiner
gleich.
Und habe eine Variable x, die belege ich auf 3, eine Variable y belege
ich auf 42.
Dann ist der Wert der Relation oder der atomaren Formel yc unter der
Interpretation di und der Variablen in Belegung beta genau dann wahr,
wenn diese y-Funktion reingezogen in die beiden Terme, die da in der
Argumentsliste der Relation stehen, wenn dieses Tupel, das sich dann
aufspannt, Teil der Interpretation der Relation sind, also der kleiner
gleich Interpretation.
Das heißt, das ist genau dann der Fall, dieses Tupel, die Auswertung
von y und c ergeben sich halt zu beta von c und i von c und die sind
dann Teil von i von r.
Das ist also genau dann der Fall, wenn 42,0 aus der Interpretation
sind von r.
Das ist genau dann der Fall, wenn 42 kleiner gleich 0 ist.
Das ist allerdings nicht der Fall.
Also ist die gesamte Formel ausgewertet nicht wahr, sondern dann
logischerweise entsprechend falsch.
Also Wert von r von y und c unter dieser Interpretation variablen
Belegung ist halt falsch.
Und jetzt machen wir den Schritt heraus, nach oben und schauen uns an
die Auswertung einer gesamten prädikatenlogischen Formel.
Wieder Interpretation di, variablen Belegung beta.
Inzwischen muss es in Fleisch und Blut übergegangen sein, dass sie
halt bei prädikatenlogischen Formeln, wenn sie auswerten, sagen, ja,
ich habe eine Interpretation di und eine variablen Belegung beta
gegeben und jetzt habe ich eine Formel g. Und diese Formel, die kann
aus verschiedenen Dingen bestehen.
Die kann verschiedene Arten haben.
Die kann entweder sowas sein, dass sie die Negation einer Formel ist
oder die Unverknüpfung, die Oder-Verknüpfung, die Implikation.
Für jede einzelne dieser Teilformeln muss ich halt wieder meine
Wahlfunktion anwenden und dann der Wert, der herauskommt, ist dasselbe
wie in der Aussagen-Logik.
Das heißt also, der Wert von di-beta von sowas wie h1 und h2 ist halt
der Wert der Booleschen-Funktion für das Und-Konnektiv und jetzt der
Wert von h1 und der Wert von h2 reingesteckt.
Das funktioniert natürlich nur, wenn meine Auswertungsfunktion auch
dafür sorgt, dass diese Werte, die ich da bei h1 und h2 rausbekomme,
dass die auch immer schön wahr oder falsch sind.
Das habe ich bisher nur dann gegeben, wenn da nur eine atomare Formel
zum Beispiel drinsteckt oder irgendwas drinsteckt, was sich nur
mithilfe von Relationen und Funktionen irgendwie zusammensetzt.
Das ist aber noch nicht, und Booleschen ausdrückt einen Zusammensatz,
also diesen Aussagen-Logischen-Konnektiven-Zusammensatz.
Das ist aber noch nicht der Fall, wenn ich jetzt diese Quantoren habe.
Das heißt, dafür, was es bedeutet, diesen All-Quantor oder den
Existenz -Quantor anzuwenden auf eine Prädikat-Logische-Formel und wie
man das dann auswertet, das sauber hinzuschreiben, müssen wir ein
klein bisschen vorbereiten.
Das können wir nicht einfach so in einem Rutsch hinschreiben.
Sondern wir definieren uns eine neue Abbildung.
Also, wir haben eine Variablenbelegung.
Es sei eine Variable x, i, eine der Variablen der Prädikaten-Logik.
Es sei ein Kleinwert klein d, der sei eben aus dem Universum D.
Und dann definiere ich mir jetzt die neue Abbildung.
Beta-Unterskript x, i hoch d.
Kann man auch nichts anderes lesen, als das sind irgendwie Parameter.
Die bilden halt ab von der Menge der Variablen wieder in das
Universum.
Und zwar in der Form, dass eine beliebige Variable x, j wird
abgebildet auf den Wert d.
Falls das j gleich i ist, also das Beta oben d und unten x, i bildet
das x, i mal auf d ab.
Und ansonsten bildet es ab auf die ursprüngliche Variablenbelegung
Beta x von j.
Ohne diese Sub- und Skripte unter dem Superskript.
Das heißt mit anderen Worten, das ist nichts anderes als eine
Abbildung.
Die nimmt eine bestehende Variablenbelegung Beta her.
Und sorgt jetzt dafür, dass in dieser Variablenbelegung Beta die
einzelne Variable x, i ersetzt wird durch den Wert d.
Das heißt, da kann ich eine Variablenbelegung modifizieren.
Und auf die Art und Weise den Wert einer einzigen Variable in einer
Variablenbelegung durch etwas anderes austauschen.
Und damit kann ich jetzt definieren, was es heißt, mithilfe dem All-
oder dem Existenzquantor solche Formeln auszubilden.
Wenn ich den Allquantor habe und ich sowas habe wie für alle x, i
prädikatenlogische Formen h, dann soll das eben genau dann wahr sein,
falls für jedes Element aus meinem Universum und für jede
Variablenbelegung Beta Strich, die ich dadurch erhalte, indem ich
einer beliebigen Variablenbelegung die Variable x, i durch d ersetze,
gilt, dass ich dieses x, i durch d ersetze.
Das heißt, für alle x, i Formeln ist wahr, wenn es völlig egal ist,
womit ich dieses x, i belege.
Da muss immer noch die Auswertung der Variablenbelegung für alle
Variablenbelegungen, indem ich das x, i mit beliebigen Werten
einsetze, muss dann immer wahr geben.
Egal, womit die ursprüngliche Variablenbelegung mir das x, i belegt
hat.
Wenn das nicht der Fall ist, dann ist das Ganze halt falsch.
Und bei dem Existenzquanto ist es halt so, dass es gibt eine x, i
Formel genau dann wahr ist, wenn es mindestens einen Wert aus dem
Universum gibt, sodass, wenn ich diesen Wert für x, i einsetze, dann
die Auswertung der Formel h mit der ursprünglichen Variablenbelegung,
aber x, i jetzt auf dieses d, das es geben muss, gesetzt, wahr ergibt.
Das heißt also, es muss mindestens einen Wert geben aus dem Universum,
sodass dann h wahr wird.
Dann gibt es eine x, i Formel h wahr.
Einfaches Beispiel.
Ich habe wieder ein Universum, das ist die Menge der natürlichen
Zahlen.
Ich habe eine konstante c, die wird auf 0 gelegt, f ist wieder
Addition, Relation r ist kleiner gleich.
x sei wieder 3y gleich 42, also genauso wie vorhin.
Und jetzt will ich halt auswerten für alle x diese Relation r von c,
x.
Und ich behaupte, der Wert, wenn ich jetzt mit dieser Interpretation
und Variablenbelegung für alle x, r von c, x auswerte, der sei halt
wahr und der ist wahr, genau dann, wenn für alle Werte aus dem
Universum gilt, dass mit dieser neuen Variablenbelegung, wo ich halt
das x durch das d ersetze, muss halt die Auswertung der Konstante, die
Auswertung der Variable, darüber das Tupe gebildet, Element der
Relation sein.
Oder mit anderen Worten, die Auswertung der Konstante muss kleiner
gleich sein der Auswertung der Variable.
Jetzt war meine Konstante 0, das heißt, dass es genau dann war, wenn
also gilt, Interpretation von c kleiner gleich diesem Beta-Strich der
modifizierten Variablenbelegung von x.
Das heißt, dass es genau dann war, wenn für alle d gilt, mit diesem
Beta -Strich, dass 0 kleiner gleich d ist.
Und da d die Menge der natürlichen Zahlen war, ist das halt immer
wahr.
Also 0, irgendeine beliebige Zahl ist immer Element der Relation, weil
0 immer kleiner gleich d ist.
Und daraus folgt halt, dass diese Formel sich hier zu wahr auswertet.
Und da sieht man halt, es ist halt extrem wichtig, wie ich jetzt das
Universum nehme, weil wenn ich jetzt für das Universum statt die Menge
der natürlichen Zahlen die Menge der reellen Zahlen hinschreiben
würde, dann hat sich an der Formel als solches ja nichts geändert.
Es hat sich auch nicht die Belegung der Variablen geändert, es hat
sich nicht die Interpretation der Relation geändert, es hat sich nicht
die Interpretation irgendeiner Funktion geändert.
Die Konstante ist gleich, die Variablen sind gleich belegt, aber die
Formel wäre falsch, weil es gibt halt genügend Elemente aus den
reellen Zahlen, für die halt nicht gilt 0 kleiner gleich.
0 kleiner gleich minus 1 gilt nicht.
Das heißt, ich finde also ein d aus dem Universum, wo das dann
entsprechend nicht mehr der Fall ist.
Also nur dadurch, dass ich halt dieses d ändere, kann sich der
Wahrheitsgehalt so einer prädikatenlogischen Formel drastisch ändern.
Dann hatten wir schon bei der Aussagenlogik kennengelernt, sowas wie
allgemeingültige Formeln.
Wir hatten gesagt, in der Aussagenlogik, eine aussagenlogische Formel
ist allgemeingültig, wenn für jede Interpretation die aussagenlogische
Formel den Wert war annimmt.
Jetzt haben wir hier halt eine andere Form der Allgemeingültigkeit,
weil wir haben ja nicht nur eine Interpretation im Sinne einer
variablen Belegung, sondern wir haben Universum, wir haben diese
Interpretation der Konstanten und Funktionswerte und wir haben eine
variablen Belegung Beta.
Man sagt jetzt, dass eine ausprädikatenlogische Formel f
allgemeingültig ist, wenn für jede passende Interpretation di und jede
passende variablen Belegung Beta gilt, die Auswertung der Funktion
gleich war.
Und jetzt sieht man schon, das wird jetzt deutlich komplizierter.
Ich muss jetzt hier nicht wie in der Aussagenlogik einfach jede
mögliche Variablenbelegung mit Werten W oder F durchprobieren, sondern
hier muss ich jede mögliche Menge an Universen durchprobieren und in
Kombination mit der zugehörigen Möglichkeit, die Relationen und die
Konstanten zu interpretieren.
Und wenn man sich das überlegt, so ein i von der Relation, das ist
eine beliebige Teilmenge des kathesischen Produktes von so vielen mal
d, wie die Stelligkeit der Relation ist.
Und das muss ich alles durchprobieren und wenn das immer wahr ergibt,
erst dann ist so eine prädikatenlogische Formel wahr.
Das ist also im Allgemeinen wahrscheinlich relativ kompliziert, sich
zu überlegen.
Man kann aber auch ein paar einfache Beispiele nehmen.
Wenn ich so eine aussagenlogische Tautologie G zum Beispiel habe.
G ist immer wahr, egal welche Interpretation ich da reinstecke.
Und dann habe ich eine prädikatenlogische Formel g i für jede
Aussagenvariable p i.
Und jetzt ersetzen wir in dieser Tautologie G, die ich habe, jede der
Aussagenvariablen p i, durch eine beliebige prädikatenlogische Formel
g i.
Dann kriege ich da zum Beispiel eine Tautologie heraus.
Eine sogenannte prädikatenlogische Tautologie.
Einfaches Beispiel, ich habe eine Formel erstmal aus der
Aussagenlogik.
p impliziert, q impliziert p.
Das ist keine prädikatenlogische Formel, da ist ja kein
Relationssymbol drin.
Das kann gar keine prädikatenlogische Formel sein, sondern eine
aussagenlogische Formel.
Die kann ich in der Aussagenlogik auswerten.
Und ich weiß, das ist eine Tautologie, die wertet immer zu wahr aus,
egal wie ich die Variablen p und q belege.
Und jetzt ersetze ich p durch eine beliebige prädikatenlogische Formel
und ich ersetze q durch eine beliebige prädikatenlogische Formel.
Ersetzen wir mal das p durch r von x, y.
Und jetzt ist es auch gar nicht mehr wichtig, dass ich mir überlegen
muss, was soll denn dieses r von x, y bedeuten.
Weil es soll ja hinterher für jede beliebige Bedeutung passen und es
soll für jedes beliebige Universum passen.
Und schreibe halt r von x, y impliziert und dann schreibe ich für q
die prädikatenlogische Formel für alle x f von y gleich gleich c.
Und dann kommt wieder dieses implizit p, für p schreibe ich r von x,
y.
Das ist jetzt eine prädikatenlogische Formel, die immer zu wahr
auswertet.
Es ist völlig egal, welche Grundmenge d ich da reinstecke.
Es ist völlig egal, wie ich die Konstanten und wie ich die
Relationssymbole interpretiere, also wie ich die ausrechne, was ich
den Konstanten zuweise.
Kann ich nehmen, was will, solange es passt zu den Ständigkeiten des
Relationssymbols und der Funktion, wird diese prädikatenlogische
Formel sich immer zu wahr auswerten.
Das kann man sich halt relativ leicht überlegen, weil woraus ist diese
prädikatenlogische Formel dann ausgebaut?
Die ist aus so einer atomaren Formel aufgebaut.
So eine atomare Formel hat immer den Wert w oder f.
Dann habe ich hier eine prädikatenlogische Formel, die hat immer den
Wert w oder f.
Dann habe ich hier nochmal wieder diese Relation als atomare
prädikatenlogische Formel, die hat den Wert w oder f.
Und dann habe ich auf oberster Ebene das Ganze verknüpft mit
Aussagenlogischen Konnektiven.
Und egal, was ich also an Universum und Belegung der Variablen und
Belegung der Konstanten und der Funktionen und Relationen reinstecke,
ich habe hinterher auf oberster Ebene, wenn ich das weil ausrechne,
immer sowas stehen wie Wahrheitswert impliziert, Klammer auf,
Wahrheitswert impliziert, Klammer zu.
Und aus der Aussagenlogik weiß ich, dass egal, wo ich da w oder f
einsetze, es kommt immer wahr raus.
Und dementsprechend, weil ich halt die gleiche Auswertung dieser
Aussagenlogischen Konnektive in den prädikatenlogischen Formeln habe,
wie in den Aussagenlogischen Formeln, muss auch da immer wieder wahr
rauskommen.
Wie gesagt, zu sowas nennt man eine Tautologie, weil die
Aussagenlogische Formel, die ich aus dieser Art und Weise daraus
wieder aufbauen kann, eine Tautologie ist.
Aber ich kann auch prädikatenlogische Formeln aufbauen, die keine
Tautologien sind.
Angenommen, ich habe also zwei Terme, T1 und T2, und dann werte ich
sowas aus wie T1 gleich gleich T2 impliziert T2 gleich gleich T1.
Da kann man sich jetzt überlegen, dass diese prädikatenlogische Formel
immer wahr sein muss.
Warum?
Was kann denn da passieren?
Also links von dem Implikationspfeil kann wahr oder falsch stehen, und
rechts von dem Implikationspfeil kann wahr oder falsch stehen, und
rechts vom Implikationspfeil steht aber immer der gleiche Wert, W oder
F, wie links von dem Implikationspfeil.
Das heißt, da kann nur stehen, wahr impliziert wahr, oder falsch
impliziert falsch.
Was anderes kann da nicht stehen in der Prädikatenlogik.
Und das ist, wenn man nachguckt in der Tabelle für die biblischen
Funktionen, für Implikationen, kommt dann immer der Wert wahr raus.
Oder wir hatten das so gesagt, allgemein gesprochen, aus wahren kann
ich nur wahres folgern, also aus wahr folgert wahr ist wahr, und aus
falschem kann ich alles folgern, insbesondere auch falsches, also aus
falsch folgt falsch ist auch wahr.
Würde ich das jetzt zurückrechnen in eine aussagenlogische Formel,
also würde ich diese prädikatenlogische Formel T gleich gleich T2
wieder rückersetzen durch eine aussagenlogische Variable, dann ständen
links und rechts vom Implikationspfeil immer dieselbe Variable, weil
da ja immer dieselbe aussagenlogische Formel steht, und dann steht da
halt drin P impliziert...
Achso, dann steht da, links und rechts stehen unterschiedliche
prädikatenlogische Formeln, weil T1 gleich gleich T2 ist erstmal eine
andere Formel als T2 gleich gleich T1.
Dann stände da also sowas wie P impliziert Q, und das ist halt im
Aussagenlagerkalkül erstmal keine Tautologie, weil sowas wie F falsch
impliziert war halt nicht stimmt.
Anderes Beispiel, allgemeiner gehalten, seien also G und H zwei
Aussagen, zwei Formeln aus der Menge der Formel.
Dann baue ich mir die prädikatenlogische Formel auf, die da lautet für
alle XI, G impliziert H, Klammer zu, impliziert für alle XI, G
impliziert für alle XIH.
Kann man sich leicht überlegen, dass das Sinn ergibt, wenn also G H
impliziert für alle XI.
Dann habe ich eine Interpretation und jetzt für alle XI, egal welches
X ich für XI einsetze, gilt immer G impliziert H.
Dann heißt das also G impliziert H ist immer war.
G impliziert H ist immer war, für alle XI gilt G impliziert H, das
heißt links von meinem Implikationsfall steht war, das heißt rechts
darf nur was wahres stehen, aber das ist dann halt nur dann der Fall,
wenn für alle XI G war ist und daraus impliziert wird, dass für alle
XI A war ist.
Oder wenn ich jetzt wieder einen Term hernehme und ich habe so eine
allgemeine Relation R einstellig und ich weiß für alle XI R von X, das
impliziert R von T.
Das heißt nichts anderes, also für alle X von R von X, wenn das falsch
ist, dann darf rechts stehen was es will, das ist sowieso egal.
Wenn das war ist, dann ist insbesondere für alle X R von X war, das
ist insbesondere R von T.
Wenn ich das auswerte war, das heißt dann steht da für W impliziert W
und das ist halt auch entsprechend wieder war.
Jetzt hatten wir auch den Begriff des Modells.
Wir kannten den Begriff des Modells aus der Aussagenlogik.
Da war es so, ein Modell war eine Interpretation einer
Aussagenlogischen Formel, für die die Aussagenlogische Formel immer
war ist.
Jetzt haben wir hier das Modell der Prädikatenlogischen Formel und das
Modell der Prädikatenlogischen Formel ist jetzt diese Interpretation
DI aus Universum und Belegung der konstanten Funktionen und
Relationen.
Und so eine Interpretation ist jetzt ein Modell für eine
Prädikatenlogische Formel, wenn sie für jede variablen Belegung war
ergibt.
Und genauso ist eine Interpretation DI Modell einer Menge von
Aussagenlogischen Formeln, wenn DI ein Modell für jede Formel in
dieser Menge der Prädikatenlogischen Formeln ist.
Wir schreiben auch G ist Modell,
dieses G Strich gleich G, wenn jedes Modell dieser Formelmenge G auch
ein Modell von der einzelnen Formel G ist.
Und genauso, wenn wir statt der Menge von Formeln Gamma eine einzelne
Formel H uns hernehmen.
H ist halt eine, dieses Strich gleich G, genau dann, wenn die Menge,
die nur aus H besteht, ein Modell ist für die Formel G.
Und wenn diese Menge Gamma leer ist, dann schreibt man halt eine leere
Menge, senkrechter Strich gleich G, das heißt G ist wahr für jedes
Modell und für jede variablen Belegung, das heißt G ist
allgemeingültig.
Also G ist wahr für jede Interpretation und für jede variablen
Belegung und unabhängig von der Interpretation, G ist also
allgemeingültig.
Ein paar einfache Beispiele für Modelle.
Wenn ich sowas habe wie für alle x, f von xc gleich gleich x, nehme
ich das Modell her mit den natürlichen Mengen an Zahlen, Konstante
wird wieder auf 0 gesetzt und f sei die Addition.
Was man jetzt schreiben kann ist, dass egal welche Zahl x ich aus den
natürlichen Zahlen hernehme, wenn ich 0 drauf addiere, kommt wieder x
raus.
Kennen Sie auch als 0 ist das neutrale Element unter der Addition auf
den natürlichen Zahlen.
Wenn man das jetzt überprüfen möchte, kann man jetzt überprüfen und
für jede variablen Belegung Beta gilt, dass der Wert der geeigneten
prädikatenlogischen Formel G, die halt überprüft, ob x plus 0, also f
von x, c gleich gleich im ursprünglichen Wert x ist, ob diese
geeignete prädikatenlogische Formel G wahr ist.
Das heißt, ich prüfe nach, ob jedes d, das ich für x einsetzen kann,
in jeder und alle anderen Variablen, die es glücklicherweise nicht
gibt, sind irgendwie anders beliebig belegt, prüfe ich nach, ob diese
prädikatenlogische Formel f von x, c sich gleich gleich x ergibt.
Das kann ich wieder über die Wertefunktion machen.
Ich muss die Wertefunktion entsprechend wieder reinziehen und sehe,
dass f von x, c, wenn ich das reinsetze in die Addition, dann kommt x
plus 0 raus, das soll halt gleich 0 sein, hat also auch
dementsprechend immer wieder den Wert x.
Das heißt, wenn ich diese äußere gleich gleich abprüfe, dann habe ich
da halt stehen, immer beliebiger Wert, plus 0 muss gleich dem
ursprünglichen beliebigen Wert sein und das ist dann entsprechend
immer erfüllt und dementsprechend ist diese prädikatenlogische Formel
wahr, wenn ich halt d als die Menge natürlich in Zahlen wähle und die
Interpretation für c als 0 annehme und wenn ich für die Interpretation
der Funktion f als die Addition annehme.
Genauso kann ich jetzt halt arbeiten, mit dem ich als Universum wieder
Wörter aus der klinischen Hülle von a, b nehme.
Diesmal ist epsilon im Universum enthalten, das leere Wort.
Die Konstante wird halt auf das leere Wort gesetzt und diesmal sei die
Funktion halt nicht die Addition, sondern die Konkatenation von meiner
Sprache.
Dann kann ich auch wieder zeigen, dass das ein Modell ist, dass diese
Formel da oben für jede beliebige Variablenbelegung sich so wahr
auswertet.
Wenn ich jetzt aber zum Beispiel wieder ein Modell hernehme, wo ich
sage, also eine Interpretation hernehme, wo ich sage, das Universum
sei die natürlichen Zahlen, die Konstante sei wieder mit 0 belegt,
diesmal sei f die Multiplikation, dann wäre dieses d, i eben gerade
kein Modell mehr, weil dann die prädikatenlogische Formel
logischerweise falsch ist, weil für alle x eben nicht mehr gilt, dass
x mal 0 gleich x ergibt.
Also an dieser Stelle sollten sie jetzt also in der Lage sein, die
Semantik von prädikatenlogischen Formeln zu verstehen und
prädikatenlogische Formeln entsprechend auch auswerten zu können, wenn
man ihnen ein Universum und eine Belegung von Variablen und eine
Interpretation auch für die Funktionsrelation zum konstanten Symbole
angibt.
Sie sollten das auswerten können, sie sollten sich überlegen können,
welche Formeln sind vielleicht allgemeingültig und welche Formeln sind
vielleicht nicht allgemeingültig und sollten halt auch Modelle angeben
können für aussagenlogische Formeln.
Dann kann man sich jetzt noch ein bisschen was anschauen über die
Variablen, die in einer aussagenlogischen Formel vorkommen.
Und die Variablen, die in einer aussagenlogischen Formel vorkommen,
die kann man unterteilen in zwei verschiedene Arten von Variablen.
Die eine Art von Variablen nennen wir die gebundenen Variablen und die
andere Art von Variablen nennen wir die freien Variablen.
Wir kümmern uns bei diesen Variablen nur um das Vorkommen der
Variablen in Termen, aber wir betrachten uns nicht die Variablen
direkt hinter dem Quantoren-Symbol.
Also wenn da steht für alle x, i, f von x, dann kümmern wir uns um das
x, das in dem f vorkommt, aber für dieses x, das hinter dem for all
-Quantor steht, um das kümmern wir uns nicht.
Aber alle anderen x, die also in solchen Termen vorkommen, die
unterteilen wir eben in die freien und die gebundenen Variablen.
Die freien, die tun wir in die Mengereihen f, v von g, freie Variablen
von g und die anderen Mengen, die nennen wir b, v von g, also
gebundene Variablen von g. Das Wichtigste ist, diese beiden Mengen,
die müssen nicht des Jungs sein.
Eine Variable, die vorkommt, die kann sowohl frei als auch gebunden
vorkommen.
Das heißt, es ist also keine scharfe Unterteilung, eine Variable ist
entweder frei oder gebunden, sondern so eine Variable kann frei sein
und gebunden gleichzeitig.
Gut, jetzt müssen wir uns überlegen, wie können wir diese Mengen
definieren und das kann man jetzt wieder so induktiv machen, indem man
sich von unten nach oben vorarbeitet.
Als erstes kümmern wir uns um die automaren Formeln.
Bei den automaren Formeln, wir erinnern uns, die enthalten so ein
Relationssymbol, aber die enthalten keine Quantoren.
Bei den automaren Formeln sagen wir, alle Variablen sind frei und
keine Variable in einer automaren Formel ist gebunden.
Wenn wir eine automare Formel jetzt haben und die mit dem
Aussagenlogischen nicht konnektiv versehen, dann sagen wir, dass die
Menge der gebundenen und die Menge der freien Variablen sich nicht
ändert.
Also die Menge der gebundenen Variablen von g ist gleich wie die Menge
der gebundenen Variablen von nicht h und die Menge der freien
Variablen von g ist das gleiche wie die Menge der freien Variablen von
h.
Das gleiche können wir machen mit Konnektiven und, oder und
impliziert, wenn ich also so eine Formel habe, die sich zusammensetzt
aus zwei Teilformeln und die werden über so ein zweistelliges
Konnektiv miteinander verbunden, dann ist die Menge der gebundenen
Variablen in dieser kombinierten Formel g gerade die Vereinigung der
gebundenen Variablen, die durch das Konnektiv verbunden werden.
Und genauso ist die Menge der freien Variablen gerade die Vereinigung
und Verabredung für heute Abend steht.
Steht nicht, hat sich gerade in den Kopf geschossen.
Soll ich vermitteln?
Scheint irgendwie nicht klar zu sein.
Einfache Regel, wenn es mich hier vorne stört, dann ist es zu laut.
Sie haben in fünf Minuten, sind Sie hier schon freudestrahlend
draußen, dann können Sie es in Ruhe zusammen zu Ende diskutieren.
Also, wenn ich so eine Konnektive habe, dann werfe ich einfach die
gebundenen Variablen zusammen und die freien Variablen werfe ich
zusammen und bekomme die Menge der gebundenen und die Menge der freien
Variablen für diese kombinierte Formel.
Bleibt noch übrig, was passiert bei den Allquantoren.
Und da wird es halt eben interessant, so ein Allquantor oder bei den
Quantoren, so ein Allquantor und Existenzquantor, die bestimmen gerade
eben, was jetzt eine gebundene und was eine freie Variable sein soll.
Wenn ich also so eine Formel habe, g, die setzt sich entweder zusammen
aus für alle x, i, h oder für alle, es gibt ein x, i, h, dann ist eben
die Menge der gebundenen Variablen in h und das x, i kommt noch dazu,
wenn es nicht vorher sowieso schon gebunden war.
Und falls das x, i vorher schon gebunden war, also nicht frei war,
dann mache ich nichts mit der Menge.
Jetzt kann man sich auch leicht überlegen, wie kann man diesen
Ausdruck da vorne verkürzen.
Den kann man kürzer hinschreiben, weil der erste Zweig reicht
vollständig aus.
Also wenn das x, i frei war in h, dann kommt es mit dazu.
Es kann sein, dass es vorher noch nicht gebunden war.
Es kann aber auch sein, dass es nicht in der freien Menge von
Variablen von h war und auch nicht notwendigerweise in der gebundenen
Menge von Variablen.
Dann kommt es hinzu.
Und die Menge der freien Variablen von g, das ist halt die Menge der
freien Variablen von h und ich ziehe das x, i davon ab.
Das fliegt raus.
Also wenn das x, i vorher frei war, dann ist es nach dem Quantor nicht
mehr frei und es wird aufgenommen in die Menge der gebundenen
Variablen.
In g sind damit also alle Vorkommen dieser Variable x, i in dieser
Teilmenge g durch den Quantor gebunden.
Es kann aber sein, dass ich dann zum Beispiel mit einem und oder sowas
später Formeln zusammensetze, da kann dann im zweiten Fall die
Variablen nur frei vorkommen und dementsprechend kann sie dann auch,
wenn ich die da mit und zusammensetze, sowohl in der Menge der
gebundenen Variablen vorkommen, als auch in der Menge der freien
Variablen.
Man spricht jetzt davon, dass wenn so ein x, i gebunden ist durch den
Quantor, dann befindet es sich im Wirkungsbereich des Quantors.
Sie werden durch den Quantor am Anfang von g gebunden und wenn ich
eine Formel habe, die nur gebundene Variablen, aber keine freien
Variablen mehr enthält, dann nenne ich diese Formel eine geschlossene
Formel.
Man kann sich also vorstellen, dass die Variablenbelegung in einer
geschlossenen Formel, die macht überhaupt nichts mehr aus, weil wenn
ich die Wahlfunktion anwende, ich hinterher sowieso alle möglichen
Variablenbelegungen durchprobieren muss, weil ich für jede einzelne
Variable immer mit diesem Beta x, i oben d sämtliche ds in das x, i
einsetzen muss und überprüfen muss, ob die für alle wahr sind oder ob
sie für mindestens eine Belegung wahr sind, abhängig davon, ob ich
jetzt ein Allquantor oder ein Existenzquantor habe.
Damit machen wir heute an der Stelle hier Schluss und am Mittwoch wird
mich dann der Herr Worsch vertreten, dann werden Sie den auch
kennenlernen, dann werden Sie mal denjenigen kennen, der diese Formeln
und das Skriptum auch in großen Teilen erstellt hat.