Logo

DISKRETE MATHEMATIK
Erich Prisner
Sommersemester 2000

Semantik

Mit der Sprache L können wir über jede mathematische Struktur M mit derselben Signatur (d.h. mit p Relationen, m Operationen, jeweils gleichstellig wie die entsprechenden Symbole in der Sprache, sowie k Konstanten) reden. Jedes solche M wird Struktur oder Modell von L genannt. Wichtig ist dabei, daß wir dann auch eine Abbildung von der Variablenmenge der Sprache in die Grundmenge der Struktur fest wählen (möglichst surjektiv, eventuell sollte diese Variablenmenge erweitert werden). So sind z.B. (N,+) und (R,*) Modelle derselben Sprache. Weitere Beispiele:

Haben wir eine feste Struktur M der Sprache L gewählt, so erhalten wir für jeden Term T von L ein Element der Grundmenge M von M, den sogenannten Wert des Terms (in M). Formeln und Aussagen sind in M gültig oder nicht---bei Aussagen setzen wir einfach die Werte der Terme ein, eine Formeln A(x1,x2,...,xn,) ist in M gültig, falls die Generalisierung "x1 "x2 ... "xn A(x1,x2,...,xn,) gültig ist. Wir schreiben dann M A und nennen M ein Modell von A. Dies lässt sich auch auf Mengen von Formeln übertragen:

Eine Theorie ist eine beliebige Formelmenge {A1, A2, ... } der Sprache L.
Eine Struktur M für L ist ein Modell für {A1, A2, ... }, M {A1, A2, ... }, falls alle diese Formeln Ai in M gelten.
Die Theorie ist
  • erfüllbar (semantisch widerspruchsfrei), wenn es ein Modell dafür gibt, andernfalls unerfüllbar (semantisch widerspruchsvoll)
  • allgemeingültig, wenn jede Struktur für L ein Modell für {A1, A2, ... } ist.
Beispiele:

Wir benutzen das Symbol "" noch in einer anderen Bedeutung:

Eine Formel B folgt aus der Theorie {A1, A2, ... }, falls B in jedem Modell von {A1, A2, ... } gilt. Wir schreiben dann {A1, A2, ... } B.
Der deduktive Abschluß Ded({A1, A2, ... }) ist die Menge aller Folgerungen aus ihr (also die Menge aller Formeln, die in jedem Modell der Theorie gelten).

Ded(Æ) ist die Menge der allgemeingültigen Aussagen. Theorien mit demselben deduktiven Abschluß werden äquivalent genannt. Hier ist ein Beispiel:

"Ded" ist ein Hüllenoperator, d.h.
  • Q Í Ded(Q),
  • Ist Q Í Q', so folgt Ded(Q) Í Ded(Q'),
  • Ded(Ded(Q)) = Ded(Q),

Q sei eine Theorie (also eine Menge von Formeln), A und B seien Formeln.
Abtrennungsregel: Wenn Q (A ® B), dann Q È {A} B.
Deduktionstheorem: Wenn Q È {A} B, dann Q (A ® B)

Äquivalenzen

Wir nennen zwei Formeln A und B äquivalent, A B, falls A in genau denselben Strukturen gilt, wie B, d.h. falls A « B in jeder Struktur gilt.

Tatsächlich ist "Äquivalenz" sogar eine Kongruenz bzgl. "Ù", "Ø", "Ú", """, "$", ... Das bedeutet: Gilt A1 A2 und B1 B2, so folgt


Ø A1 Ø A2,
A1 Ù B1 A2 Ù B2,
" x A1 " x A2, usw.

Es gelten alle aussagenlogischen Äquivalenzen, aber darüberhinaus auch noch folgende:

Bitte schauen Sie ganz genau hin. Nicht äquivlent sind z.B. " x (A Ú B) und " x A Ú " x B; auch keins der folgenden drei Formeln ist äquivalent: " x $ y A, bzw. $ y " x A, bzw. " y $ x A
Die rechts aufgelisteten Äquivalenzen gelten falls x in B nicht frei vorkommt:
  • " x (A Ú B) " x A Ú B
  • $ x (A Ú B) $ x A Ú B
  • " x (A Ù B) " x A Ù B
  • $ x (A Ù B) $ x A Ù B
  • " x (A ® B) $ x A ® B
  • $ x (A ® B) " x A ® B
  • " x B B $ x B $ x B

Weitere Äquivalenzen erhält man mittels Ersetzung (Replacement) und Substitution. Bei der Ersetzung ersetzt man eine Teilformel durch eine äquivalente Teilformel (dies funktioniert nicht mit Termen). Ist A(x,...) eine Formel mit (mindestens) der freien Variablen x, und ist t ein Term, so bezeichne A(t, ...) die Formel, die man erhält, indem man jedes freie vorkommende x in A durch den Term t substituiert. Falls keine Variable von t in A gebunden vorkommt, so ist A(t, ...) zu A(x,...) äquivalent.

Vorsichtigere Charaktere ziehen es vielleicht vor, mit Formeln zu arbeiten, bei denen eine Variable nie in derselben Formel frei und gebunden erscheint, und bei der je zwei gebundene Erscheinen jeder Variable durch denselben Quantor gebunden sind. Zu jeder Formel gibt es so eine äquivalente "Nummer-Sicher" Formel. So ist z.B. " y $ x ($ y z = + x y Ù $ y y = + x z) zu " y $ x ($ y1 z = + x y1 Ù $ y2 y2 = + x z) äquivalent.

Wieder kann man Formeln in Normalform bringen. Diesmal möchte man, daß zuerst alle Quantoren (zusammen mit den gebundenen Variablen) erscheinen, und der Rest der Formel in (kanonischer) konjunktiver bzw. disjunktiver Normalform ist. Das heißt dann pränexe Normalform. Näheres finden Sie im Abschnitt über pränexe und Skolemsche Normalformen.

Testen Sie Ihr Äquivalenzverständnis!

Definitorische Erweiterungen

Die Sprache L1 sei eine Sprachwerweiterung der Sprache L, d.h. jedes Symbol von L kommt auch in L1 mit derselben Stelligkeit vor.

"R" sei ein n-stelliges Relationenzeichen in L, aber nicht in L1. "R" heißt L-definierbar in einer Struktur M' von L1, falls es eine L-Formel A(x1,...,xn) gibt so daß R(x1,...,xn) genau dann in M' gilt, falls A(x1,...,xn) in M' gilt. So ist beispielsweise "größer" durch die Formel A(x,y): $ z (y = + x z Ù Ø x = z) (M,+)-definierbar in (N,+), und auch die 1-stellige Relation (d.h. Eigenschaft) "ist gerade" ist durch B(x): $ z (x = + z z) (M,+)-definierbar in (N,+). Interessanterweise ist etwa "größ,er" nicht (M,+)-definierbar in (Z,+).

Etwas kompizierter ist die Situation bei n-stelligen Verknüpfungszeichen "F" in L ohne L1. "F" heißt L-definierbar in einer Struktur M' von L1, falls es eine L-Formel A gibt so daß es für alle Individuenvariablen x1,...,xn die durch die Gleichung y = (x1,...,xn) in M' definierte Individuenvariable y die einzige Variable z ist, für die A(x1,...,xn,z) in M' gilt. Ähnlich verfahren wir auch bei Konstanten (die ja auch als 0-stellige Verknüpfungen angesehen werden können). Dazu dieses Beispiel:

Der Vollständigkeitssatz

 Der wichtige Zusammenhang zwischen Semantik und Syntax bei Sprachen 1. Stufe wird durch diesen fundamentalen Satz hergestellt:
Gödelscher Vollständigkeitssatz: Es sei Q eine Theorie der Sprache (1. Stufe) L. Für jede Aussage A der Sprache gilt: A folgt genau dann aus Q wenn A aus Q ableitbar ist.

Somit folgt aus dem Endlichkeitssatz fürs Ableiten:

Endlichkeitssatz: Wenn A aus einer Theorie Q folgt, so folgt Q bereits aus einer endlichen Teiltheorie von Q.
Kompaktheitssatz: Eine Theorie Q ist genau dann (semantisch) widerspruchsfrei, wenn jede endliche Teiltheorie von T widerspruchsfrei ist.
Weiter zu Ableitungen, oder zurück zur Sprachbeschreibung?
Erich Prisner
erstellt im Juni 2000.