Kapitel 2 Die Pr adikatenlogik (erster Stufe) · Kapitel 2 Die Pr adikatenlogik (erster Stufe) Mathematische Strukturen und formale Sprachen Mathematische Logik (WS 2017/18) Kap

Kapitel 2

Die Pradikatenlogik (erster Stufe)

Mathematische Strukturen und formale Sprachen

Mathematische Logik (WS 2017/18) Kap. 2: Pradikatenlogik 1. Stufe 1 / 81

Ubersicht

2.0 Vorbemerkungen

2.1 Mathematische Strukturen

2.2 Pradikatenlogik: Grundzeichen der Sprachen

2.3 Pradikatenlogik: Terme

2.4 Pradikatenlogik: Formeln und Satze

2.5 Pradikatenlogik: Zentrale semantische Konzepte


2.0 Vorbemerkungen


Vorbemerkungen

Wir erweitern hier die Aussagenlogik zur Pradikatenlogik, die uns erlaubenwird Aussagen uber mathematische Strukturen zu formalisieren und denWahrheitswert dieser Aussagen zu analysieren.

Um uber Strukturen sprechen zu konnen, fuhren wir Individuenvariablen ein,die fur die Grundobjekte (= Individuen) der Strukturen stehen.

Weiter werden wir Funktionszeichen und Relationszeichen zur Bezeichnungvon ausgezeichneten Funktionen und Relationen der Struktur verwenden,sowie Konstanten zur Bezeichnung ausgezeichneter Individuen. DieseZeichen hangen von der zu beschreibenden Struktur - genauer von derenTyp - ab. In jedem Fall haben wir das Gleichheitszeichen zur Bezeichnungidentischer Individuen.

Weiter benotigen wir die Moglichkeit der Quantifizierung. Hierbeiquantifizieren wir nur uber die Grundobjekte (Fur alle Individuen gilt ...bzw. Es gibt ein Individuum, fur das ... gilt).

Da man die Individuen einer Struktur auch die Objekte der Stufe 1, Mengenvon Individuen Objekte der Stufe 2 usw. nennt, sprechen wir hier auch vonder Pradikatenlogik 1. Stufe (PL1).


VorbemerkungenIm Folgenden erlautern wir die gerade genannten Konzepte am Beispiel vonAussagen uber die Struktur der naturlichen Zahlen:

quantifizierte Aussagen uber die Grundobjekte (= Individuen)Fur jede Zahl x gibt es eine Zahl y mit . . .

Eigenschaften und Beziehungen (Pradikate und Relationen) von undzwischen den Grundobjekten. . . x ist Primzahl oder x ist kleiner als y

Abbildungen (Funktionen) von Grundobjekten. . . y ist der Nachfolger von x

Spezielle Grundobjekte (Konstanten). . . y ist kleiner als x , falls x 6= 0 gilt

Die Aussage Zu jeder von Null verschiedenen Zahl x gibt es eine Zahl y , sodassx der Nachfolger von y ist, wobei y kleiner als x ist. werden wir durch die Formel

x ((x = 0) y (x = S(y) y < x))

darstellen, wobei S die Nachfolgerfunktion bezeichnet.Mathematische Logik (WS 2017/18) Kap. 2: Pradikatenlogik 1. Stufe 5 / 81

2.1 Mathematische Strukturen


Mathematische Strukturen: Idee

Eine (mathematische) Struktur A besteht aus

einer nichtleeren Menge A, dem Individuenbereich (oder Trager oderUniversum) der Struktur

Hierbei kann der Individuenbereich beliebige Kardinalitat ( 6= 0) haben, alsoendlich oder unendlich (und hier wiederum abzahlbar oder uberabzahlbar)sein.

ausgezeichneten Relationen und Funktionen auf dem Trager sowieausgezeichneten Elementen des Tragers, den Grundrelationen,Grundfunktionen und Konstanten von AHierbei ist die Anzahl der Grundrelationen und Grundfunktionen (sowiederen Dimension) und die Anzahl der Konstanten beliebig. Es konnen alsoz.B. gar keine Grundrelationen vorkommen oder unendlich viele.


Mathematische Strukturen: Formale Definition

DEFINITION. Eine Struktur A ist ein 4-Tupel

A = (A; (RAi |i I ); (f Aj |j J); (cAk |k K ))

wobei I , J,K beliebige (moglicherweise leere oder unendliche) Mengen sind undfolgendes gilt:

A ist eine nichtleere Menge (das Universum oder der Trager oder derIndividuenbereich der Struktur A; entsprechend werden die Elemente von Adie Individuen von A genannt),

fur jedes i I ist RAi eine ni -stellige Relation auf A (fur ni 1 geeignet),d.h. RAi Ani (die Grundrelationen von A),

fur jedes j J ist f Aj eine mj -stellige Funktion auf A (fur mj 1 geeignet),d.h. f Aj : A

mj A (die Grundfunktionen von A), und

fur jedes k K ist cAk ein Element von A (die Konstanten von A).


Mathematische Strukturen: Typ oder Signatur

Die Anzahl der ausgezeichneten Relationen und Funktionen zusammen mit derenStelligkeiten sowie die Anzahl der Konstanten bestimmen den Typ einer Struktur:

DEFINITION. Die Struktur A = (A; (RAi |i I ); (f Aj |j J); (cAk |k K )) ist vomTyp oder besitzt die Signatur

(A) = ((ni |i I ); (mj |j J);K ),

falls RAi ni -stellig und fAj mj -stellig ist.

Besitzt eine Struktur keine ausgezeichneten Relationen (bzw. Funktionen), so

spricht man auch von einer algebraischen oder funktionalen (bzw. relationalen)

Struktur.


Mathematische Strukturen: Notation

Bei einer Struktur A = (A; (RAi |i I ); (f Aj |j J); (cAk |k K )) der Signatur(A) = ((ni |i I ); (mj |j J);K ) machen wir o.B.d.A. folgende Annahmen:

Sind die Indexmengen I , J, K endlich, so gehen wir davon aus, dass dieseein Anfangsstuck der naturlichen Zahlen sind und schreiben z.B. statt(RAi |i {0, . . . , k}) einfach RA0 , . . . ,RAk und beim Typ statt(ni |i {0, . . . , k}) entsprechend n0, . . . , nk .

Ist eine der Indexmengen leer, so lassen wir die entsprechende Komponentein der Beschreibung der Struktur auch weg. In der Signatur ersetzen wir eineleere Indexmenge auch durch .

Wird im Folgenden eine Struktur A nicht naher beschrieben, so gehen wir von derallgemeinen Form A = (A; (RAi |i I ); (f Aj |j J); (cAk |k K )) und der Signatur(A) = ((ni |i I ); (mj |j J);K ) aus. Entsprechend nehmen wir von einer nichtnaher beschriebenen Signatur an, dass = ((ni |i I ); (mj |j J);K ) gilt.


Mathematische Strukturen: Beispiele

Ein (gerichteter oder ungerichteter) Graph ist eine relationale StrukturG = (V ;EG), wobei

I V die Menge der Knoten (vertices) undI EG die 2-stellige Kantenrelation (edges) auf der Knotenmenge ist.

Der Typ von G ist also (G) = (2;;).

Eine partielle oder lineare Ordnung ist eine relationale Struktur O =(A;O), wobei

I A die Menge ist, auf derI die 2-stellige Ordnungsrelation O definiert ist.

Der Typ der Ordnung O ist (O) = (2;;).

Ordnungen und Graphen haben also denselben Typ (wobei jedoch an dieausgezeichnete 2-stellige Relation unterschiedliche Anforderungen gestelltwerden).


Mathematische Strukturen: Beispiele (Forts.)

Eine Gruppe G ist gegeben durchI den Trager A von G undI die 2-stellige Verknupfung +G auf dem Trager.

Zeichnet man noch das neutrale Element 0G der Verknupfung +G aus, soerhalt man die Struktur G = (A; +G ; 0G) vom Typ (G) = (; 2; {0}).

Nimmt man das Inverse als weitere (1-st.) Grundfunktion hinzu, so erhaltman die Struktur G = (A; +G ,G ; 0G) vom Typ (G) = (; 2, 1; {0}).

G und G sind algebraische Strukturen.

Ein Korper K kann als (algebraische) Struktur K = (A; +K, K; 0K, 1K) mit(K) = (; 2, 2; {0, 1}) beschrieben werden, wobei +K und K dieKorperaddition und -multiplikation sind und 0K und 1K die zugehorigenneutralen Elemente.


Mathematische Strukturen: Beispiele (Forts.)

Struktur der naturlichen Zahlen (Arithmetik): Versieht man die Menge dernaturlichen Zahlen N mit Addition und Multiplikation und deren neutralenElementen, so erhalt man die (algebraische) Struktur N = (N; +, ; 0, 1)deren Typ (N ) = (; 2, 2; {0, 1}) mit dem Typ der Korper ubereinstimmt.

Erweitern kann man diese Struktur z.B. noch dadurch, dass man dieOrdnung auf N sowie die Nachfolgerfunktion S(x) = x + 1 alsGrundrelation bzw. -funktion hinzunimmt:

N = (N;; +, ,S ; 0, 1) wobei (N ) = (2; 2, 2, 1; {0, 1}).Man konnte die Struktur der naturlichen Zahlen auch als reineOrdnungsstruktur betrachten:

N = (N;) wobei (N ) = (2;;).Die Wahl der Grundrelationen, Grundfunktionen und Konstanten hat(moglicherweise) Einfluss darauf, was in der zu einer Struktur gehorendenSprache uber die Struktur ausgedruckt werden kann.

Wir fuhren nun die zu einer Struktur passende Sprache ein, wobei diese nurvom Typ der Struktur abhangt.


2.2 Pradikatenlogik: Grundzeichen der Sprachen


Die Grundzeichen der Sprache L()

Um uber Strukturen eines gegebenen Typs = ((ni |i I ); (mj |j J);K )Aussagen machen zu konnen, fuhren wir nun die zugehorige Sprache L() ein.

Bei den Grundzeichen der Sprache L = L() unterscheidet man zwischen

den logischen Zeichen (die nicht von abhangen) und

den nichtlogischen Zeichen (die von abhangen). Die nichtlogischenZeichen sind hierbei gerade Namen fur die Grundrelationen, Grund-funktionen und Konstanten.

Die Menge aller Grundzeichen von L bezeichnen wir als das Alphabet von L.


Die Grundzeichen der Sprache L(): logische Zeichen

Logische Zeichen von L():I Abzahlbar unendlich viele Individuenvariablen (kurz: Variablen):

v0, v1, v2, . . .Wir bezeichnen Variablen im Folgenden mit x , y , z , xi , . . .

I Die Junktoren und .(Die ubrigen ublichen Junktoren ,, werden wir wiederum alsAbkurzungen einfuhren.)

I Der Existenzquantor .(Den Allquantor werden wir spater ebenfalls als Abkurzungeinfuhren.)

I Das Gleichheitszeichen =.

I Die Klammern ( und ) sowie das Komma ,.


Die Grundzeichen der Sprache L(): nichtlogische Zeichenund Typ

Nichtlogische Zeichen von L():I Fur jedes i I das ni -stellige Relationszeichen Ri .I Fur jedes j J das mj -stellige Funktionszeichen fj .I Fur jedes k K die Konstante ck .

Wie bei den Strukturen nennen wir den Typ oder die Signatur der SpracheL().

Sind die Struktur A und die Sprache L vom selben Typ , so heit

L die Sprache von A (und wir schreiben auch L = L(A)) und

A eine L-Struktur.


Strukturen und deren zugehorige Sprachen: Beispiele

Fur die im letzten Beispiel eingefuhrten Strukturen konnen wir die zugehorigenSprachen (deren Signaturen gerade durch die Signaturen der Strukturen gegebensind) durch Angabe der nichtlogischen Zeichen angeben:

Die Sprache der Graphen enthalt ebenso wie die Sprache der Ordnungen alseinziges nichtlogisches Zeichen das 2-stellige Relationszeichen R0. Wirbenutzen statt R0 allerdings in der Regel die suggestiveren Zeichen E (dasfur die Kantenrelation steht) bzw. (das fur die Ordnungsrelation steht)und schreiben L(E ) und L().

Die Sprache der Gruppen verfugt uber ein 2-stelliges Funktionszeichen f0und eine Konstante c0, fur die wir in der Regel aber + und 0 schreibenwerden: L(+; 0). Bei der Sprache der Korper kommen das 2-stelligeFunktionszeichen f1 () und die Konstante c1 (1) hinzu: L(+, ; 0, 1).


Strukturen und deren zugehorige Sprachen: Beispiele(Fortsetzung)

Die Sprache L der Struktur N = (N; +, ; 0, 1) der naturlichen Zahlenumfasst die 2-stelligen Funktionszeichen f0 und f1 und die Konstanten c0und c1. Wir schreiben hierfur i.a. +, , 0 und 1: L = L(+, ; 0, 1).

Man beachte, dass hierbei z.B. + zwei unterschiedliche Bedeutungen hat: inN ist + die Addition auf den naturlichen Zahlen; in L ist + dagegen einZeichen (genauer: die Abkurzung des 2-st. Funktionszeichens f0).

Wo diese Mehrdeutigkeit der Notation zu Missverstandnissen fuhren kann,schreiben wir daher auch +N fur die Addition auf N (und entsprechend N ,0N , etc.).


2.3 Pradikatenlogik: Terme


Terme: Vorbemerkungen

Terme dienen dazu, Individuen und Funktionen auf demIndividuenbereich zu bezeichnen.

Vorgehen:

1 Induktive Festlegung der Gestalt der Terme (Syntax)

2 Zuordnung der dargestellten Individuen und Funktionen(Semantik)

Es ist im Folgenden L wiederum die Sprache L = L() der Signatur = ((ni |i I ); (mj |j J);K ).


2.3.1 Terme: Syntax


Induktive Definition der L()-Terme (Syntax)DEFINITION. Sei L = L() mit = ((ni |i I ); (mj |j J);K ). Die Menge der(L-)Terme ist induktiv definiert durch:

(T1) Jede Variable vn (n 0) und jede Konstante ck (k K ) ist ein Term.

(T2) Sind t1, . . . , tmj Terme, so ist auch fj(t1, . . . , tmj ) ein Term (j J).

NOTATION:

Terme bezeichnen wir mit s, t, si , ti , etc.

Die Terme gema (T1) sind die Grundterme oder atomaren Terme.

V (t) bezeichnet die Menge der im Term t vorkommenden Variablen.

Kommen in t keine Variablen vor (d.h. V (t) = ), so ist t einkonstanter Term.

Schreiben wir t(x1, . . . , xn) statt t, so bedeutet dies, dassV (t) {x1, . . . , xn} gilt (d.h. es kommen hochstens die Variablenx1, . . . , xn in t vor).


Terme: Beispiele

In einer relationalen Sprache L sind die Variablen und Konstanten dieeinzigen Terme. Enthalt eine Sprache L keine Konstanten, so besitzt sieauch keine konstanten Terme.

In der Sprache der Graphen oder Ordnungen (die weder Funktionszeichennoch Konstanten besitzt) sind daher die Variablen die einzigen Terme.

In der Sprache der Gruppen kann man z.B. folgenden Term bilden:

t +(v0,+(v3, 0)) [ f0(v0, f0(v3, c0))]

wobei wir die suggestiven Abkurzungen + : f0 und 0 : c0 verwenden. ZurVerbesserung der Lesbarkeit benutzen wir auch die in der Algebra ublicheInfixschreibweise fur +, wodurch der Term t die Gestalt v0 + (v3 + 0) erhalt.Letzteres ist aber kein Term im formalen Sinn und wird von uns nur als(informelle) Abkurzung von t verwendet.


Terme: Beispiele (Fortsetzung)

Bei der Sprache der Struktur N = (N; +, ; 0, 1) der naturlichen Zahlenverwenden wir (wie bereits erwahnt) die Funktionszeichen + und anstelleder Funktionszeichen f0 und f1 und die Konstanten 0 und 1 an Stelle von c0und c1, und wir benutzen fur die Funktionszeichen + und die Infixschreib-weise.

Wiederum sind die entsprechend gebildeten Terme als abkurzendeSchreibweise aufzufassen. So steht

(1 + 0) (1 1)

fur den (abgekurzten) Term

(+(1, 0), (1, 1))

und dieser wiederum fur den (eigentlichen) Term

f1(f0(c1, c0), f1(c1, c1)).


2.3.2 Terme: Semantik


Interpretation der L()-Terme

Wir wollen nun die L-Terme in den L-Strukturen interpretieren. Hierzu sei imFolgenden A = (A; (RAi |i I ); (f Aj |j J); (cAk |k K )) eine L-Struktur, d.h. eineStruktur vom Typ = ((ni |i I ); (mj |j J);K ).

IDEE:

Konstante L-Terme werden in der L-Struktur A als Individuen interpretiert.

Beliebige L-Terme werden in der L-Struktur A als Funktionen auf demIndividuenbereich interpretiert.

Wir bestimmen zunachst die von konstanten Termen dargestellten Individuen,wobei wir induktiv nach dem Aufbau der Terme vorgehen (vgl. mit dersyntaktischen Induktion im Teil uber die Aussagenlogik).


Interpretation konstanter Terme: Definition

Konstante L-Terme werden in der L-Struktur A als Individuen interpretiert.Hierzu ordnen wir jedem konstanten Term t durch Induktion nach dem Aufbauder Terme (kurz: Ind(t)) ein Individuum tA aus A zu:

DEFINITION. Fur einen konstanten L-Term t ist tA A wie folgt durch Ind(t)definiert:

1 (ck)A := cAk

2 (fj(t1, . . . , tmj ))A := f Aj (t

A1 , . . . , t

Amj )


Interpretation konstanter Terme: Beispiele (1)

Sei L die Sprache der Arithmetik. Der konstante Term t (+(1, 1), (1, 1))erhalt in der Struktur N = (N; +, ; 0, 1) der naturlichen Zahlen den WerttN = 2. Da das Zeichen 1 durch die Eins und die Funktionszeichen + und durch Addition und Multiplikation interpretiert werden, sieht man diesinduktiv wie folgt:

1N = 1+(1, 1)N = 2(1, 1)N = 1tN = 2 1 = 2


Interpretation konstanter Terme: Beispiele (2)

Sei L weiterhin die Sprache der Arithmetik und N = (N; +, ; 0, 1).

Definiert man induktiv die konstanten Terme n (n 0) durch

0 : 0 und n + 1 : (n + 1),

so gilt gerade nN = n. (Wir nennen n die Ziffer zur Bezeichnung der Zahln.) Es lasst sich also jede naturliche Zahl durch einen konstanten Term derSprache von N darstellen.

Die Sprache einer Struktur erlaubt aber nicht immer, dass man alleIndividuen durch konstante Terme beschreiben kann: Ersetzen wir oben Ndurch den Korper R = (R; +, ; 0, 1) der reellen Zahlen, so lassen sich indiesem ebenfalls nur die naturlichen Zahlen durch konstante Termedarstellen. Erweitert man die Sprache um ein Zeichen fur die 2-stelligeDifferenz bzw. ein Zeichen : fur die Division, so lassen sich inR = (R;,+, ; 0, 1) bzw. R = (R;,+, , :; 0, 1) gerade die ganzen bzw.rationalen Zahlen durch konstante Terme darstellen (wobei wir x : 0 = 0setzen).

Betrachten wir eine Struktur ohne Konstanten, so gibt es - wie bereits beobachtet - keine konstanten Terme in derzugehorigen Sprache. Hier lasst sich also sogar uberhaupt kein Individuum durch einen konstanten Term darstellen.


Interpretation beliebiger Terme: Definition

Wir betrachten nun die Interpretation beliebiger L-Terme t in der L-Struktur A.Einem Term t t(~x) t(x1, . . . , xn), in dem hochstens die Variablen x1, . . . , xnvorkommen, ordnen wir einen Wert aus A in Abhangigkeit von einer Belegung Bder Variablen xi durch Werte ai aus A zu:

DEFINITION. Sei V = {x1, . . . , xn} eine Menge von Variablen und A eineL-Struktur. Eine (Variablen-)Belegung B von V in A ist eine AbbildungB : V A.

DEFINITION. Sei t t(~x) t(x1, . . . , xn) ein L-Term, in dem hochstens dieVariablen x1, . . . , xn vorkommen, und sei B : {x1, . . . , xn} A eine Belegungdieser Variablen in der L-Struktur A. Der Wert tAB A von t in A bzgl. derBelegung B ist durch Ind(t) wie folgt definiert:

1 (xi )AB := B(xi ) und (ck)

AB := c

Ak

2 (fj(t1, . . . , tmj ))AB := f

Aj ((t1)

AB , . . . , (tmj )

AB )


Interpretation beliebiger Terme: Bemerkungen

Ordnet die Belegung B von V = {x1, . . . , xn} in A den Variablen xi dieIndividuen ai zu, so schreiben wir fur t t(x1, . . . , xn) statt tAB auch

tAB tA[B(x1), . . . ,B(xn)] tA[a1, . . . , an].

(Diese Schreibweise wird im Skript von Gloede verwendet!)

Der Term t t(~x) t(x1, . . . , xn) kann in A also als n-stellige Funktion

f At(~x) : An A mit f At(~x)(~a) = t

A[~a]

interpretiert werden.

Dabei hangt der Wert von tA[~a] hochstens dann von ai ab, wenn dieVariable xi tatsachlich in t vorkommt (Beweis durch Ind(t); Ubung!):

KOINZIDENZLEMMA (fur Terme). Sei A eine L-Struktur, t ein L-Term,V = {x1, . . . , xm} und V = {x 1, . . . , x n} Variablenmengen mitV (t) V ,V und B und B Belegungen von V bzw. V in A, sodassB V (t) = B V (t) gilt. Dann gilt tAB = t

AB .


Interpretation beliebiger Terme: Beispiel

Der durch

t : f0(f1(x1, x1), f1(f0(c1, c1), x2)) +((x1, x1), (+(1, 1), x2))

definierte Term t der Sprache von N lasst sich in Infixschreibweise auch als

t (x1 x1) + ((1 + 1) x2)

schreiben. Es gilt V (t) = {x1, x2}. Wir konnen t also z.B. alst t(x1, x2, x3) schreiben.Fur die Belegung B(x1) = 0,B(x2) = 1,B(x3) = 2 gilt dann

tNB = (B(x1) B(x1)) + ((1 + 1) B(x2))= (0 0) + ((1 + 1) 1) = 2

Die Auswertung von tN [0, 1, 2] = tNB hangt also nicht von der BelegungB(x3) = 2 der nicht in t vorkommenden Variablen x3 ab.

Die von t(x1, x2, x3) dargestellte Funktion fNt(x1,x2,x3)

: N3 N ist:

f Nt(x1,x2,x3)(a1, a2, a3) = a21 + 2a2 (a1, a2, a3 N)


Interpretation beliebiger Terme: Weitere Bemerkungen

Fur einen konstanten Term t ist die Funktion f At(x1,...,xn) = fAt (nach dem

Koinzidenzlemma) konstant und es gilt f At (~a) = tA fur alle ~a An.

In einer L-Struktur A lassen sich genau die Funktionen durch L-Termedarstellen, die uber den Grundfunktionen und den Konstanten der Strukturexplizit definierbar sind.

Fur die Sprache L der Arithmetik N = (N; +, ; 0, 1) kann man so (durchAusmultiplizieren und mit Hilfe der Kommutativitat von + und ) zeigen,dass die durch Terme definierbaren Funktionen uber N gerade diemehrstelligen Polynome p(x1, . . . , xn) mit Koeffizienten aus N sind.


2.4 Pradikatenlogik: Formeln und Satze


Formeln und Satze: Vorbemerkungen

(L-)Satze dienen dazu, Aussagen uber (L-)Strukturen zu machen.

Die von Formeln (auch Satzformen genannt) gemachten Aussagenhangen noch von der Interpretation der in ihnen vorkommenden freienVariablen ab, und konnen so auch als Relationen auf den Tragern von(L-)Strukturen interpretiert werden.

Vorgehen:

1 Induktive Festlegung der Gestalt der Formeln (Syntax)

2 Interpretation der Formeln in zugehorigen Strukturen (Semantik)

Es ist im Folgenden L wiederum die Sprache L = L() der Signatur = ((ni |i I ); (mj |j J);K ).


2.4.1 Formeln und Satze: Syntax


Induktive Definition der L()-Formeln

DEFINITION. Sei L = L() mit = ((ni |i I ); (mj |j J);K ). Die Menge der(L-)Formeln ist induktiv definiert durch:

(F1) (a) Sind t1, t2 Terme, so ist t1 = t2 eine Formel.

(b) Sind t1, . . . , tni Terme, so ist Ri (t1, . . . , tni ) eine Formel (i I ).

(F2) Ist eine Formel, so ist auch eine Formel.

(F3) Sind 1 und 2 Formeln, so ist auch (1 2) eine Formel.

(F4) Ist eine Formel und x eine Variable, so ist auch x eine Formel.

Die gema (F1) definierten Formeln heien Primformeln oder atomare Formeln.Formeln vom Typ (F1)(a) nennt man auch Gleichheitsformeln. Formeln vom Typ(F2), (F3) und (F4) heien Negationsformeln bzw. Disjunktionen bzw.Existenzformeln.

Im Folgenden bezeichnen ,, , , i , . . . (L-)Formeln.


Verbesserung der Lesbarkeit von Formeln (Abkurzungen)

Zur Verbesserung der Lesbarkeit der Formeln benutzen wir folgende Konventionenund abkurzende Schreibweisen:

Die Junktoren , und fuhren wir wie in der AL ein.

Zusatzlich fuhren wir den Allquantor durch x : x ein.

Wir verwenden die schon im Teil uber die Aussagenlogik eingefuhrten Regelnzur Klammerersparnis.

Zusatzlich erlauben wir fur , x und x auch die Schreibweise ()bzw. x() bzw. x().

Statt t1 = t2 schreiben wir auch t1 6= t2.

Wo ublich benutzen wir fur Funktionszeichen (wie + und ) undRelationszeichen (wie ) auch die Infixschreibweise.

NB: Die derart verallgemeinerten Formeln sind keine eigentlichen Formeln undsind daher bei formaler Sichtweise (z.B. in Beweisen durch Ind()) immer durchdie entsprechenden eigentlichen Formeln zu ersetzen.


Verbesserung der Lesbarkeit von Formeln: Beispiele

Nach den gerade eingefuhrten Konventionen sind die folgenden (uneigentlichen)Formeln alle identisch mit der (eigentlichen) Formel

(x (x , y) y = x) :

x(x y) (y = x)

x(x y) (y = x)

x(x y) y 6= x


Freie und gebundene Vorkommen von Variablen in Formeln

Eine in einer Formel vorkommende Variable x kann frei oder (durch einenExistenzquantor ) gebunden auftreten (wobei x in einer Formel an einer Stellefrei und an einer anderen Stelle gebunden auftreten kann). Dabei ist einVorkommen von x in einer Formel gebunden, wenn es in einer Teilformel xliegt (formale Definition: nachste Folie).

Wir bezeichnen mit V (), FV () und GV () die Mengen der in vorkommenden bzw. frei vorkommenden bzw. gebunden vorkommendenVariablen.

Gilt FV () {x1, . . . , xn}, so schreiben wir auch (x1, . . . , xn) statt .

DEFINITION. Kommt in einer (L-)Formel keine Variable frei vor (d.h. giltFV () = ), so ist ein (L-)Satz.

Im Folgenden bezeichnen , , n etc. Satze.


Freie und gebundene Vorkommen von Variablen: DefinitionFormal definiert man das Vorkommen einer Variablen x und die freien undgebunden Vorkommen von x in einer Formel durch Ind():

1 Die Variable x kommt in der Primformel t1 = t2 bzw. Ri (t1, . . . , tni ) vor,falls x in einem der Terme t1, t2 bzw. t1, . . . , tni vorkommt. Alle Vorkommenvon x sind frei.

2 Die Variable x kommt in vor, wenn sie in der Formel vorkommt. EinVorkommen von x in ist frei (gebunden), wenn das entsprechendeVorkommen von x in frei (gebunden) ist.

3 Die Variable x kommt in der Formel (1 2) vor, wenn sie in der Formel1 oder in der Formel 2 vorkommt. Ein Vorkommen von x in (1 2) istfrei (gebunden), wenn das entsprechende Vorkommen von x in 1 bzw. 2frei (gebunden) ist.

4 Die Variable x kommt in der Formel y vor, wenn x y oder x in derFormel vorkommt. Ist x y , so sind alle Vorkommen von x in ygebunden. Sonst ist ein Vorkommen von x in y frei (gebunden), wenn dasentsprechende Vorkommen von x in frei (gebunden) ist.


Freie und gebundene Vorkommen von Variablen: Beispiele

In der Formel (x (x , y) y = x)

der Sprache der Ordnungen sind die ersten beiden Vorkommen der Variablenx gebunden, wahrend das dritte Vorkommen frei ist. Weiter sind beideVorkommen von y frei.

Es gilt also V () = FV () = {x , y} und GV () = {x}.

In der Formel yx(x (x , y) y = x)

sind alle Vorkommen von x und y gebunden. ist also ein Satz.


2.4.2 Formeln und Satze: Semantik


Semantik der L()-Formeln: Idee

Wir wollen nun zeigen, wie ein (L-)Satz als eine Aussage uber die(L-)Struktur A interpretiert werden kann.

Hierzu ordnen wir zunachst allgemeiner einer Formel , in der hochstens dieVariablen x1, . . . , xn frei vorkommen, und jeder Belegung B dieser Variablendurch Individuen a1, . . . , an von A einen Wahrheitswert WAB () zu.

Wir zeigen dann, dass dieser Wert hochstens dann von B(xi ) = ai abhangt,wenn xi in frei vorkommt (Koinzidenzlemma fur Formeln).

Ist ein Satz, so hangt die Wahrheit von also nur von der Struktur A undnicht von der gewahlten Variablenbelegung B ab.


Interpretation einer L-Formel in einer L-Struktur A

DEFINITION. Sei A eine L-Struktur, (x1, . . . , xn) eine L-Formel mitFV () {x1, . . . , xn} und B eine Belegung von {x1, . . . , xn} in A. Dann ist derWahrheitswert

WAB () {0, 1} (= {FALSCH,WAHR})

von in A bzgl. der Variablenbelegung B durch Ind() wie folgt definiert:1 WAB (t1 = t2) = 1, g.d.w. (t1)

AB = (t2)

AB

(fur die Definition von tAB siehe Semantik der Terme).

2 WAB (Ri (t1, . . . , tni )) = 1, g.d.w. ((t1)AB , . . . , (tni )

AB ) RAi .

3 WAB () = 1, g.d.w. WAB () = 0.4 WAB (1 2) = 1, g.d.w. WAB (1) = 1 oder WAB (2) = 1 (oder beides).5 WAB (y) = 1, g.d.w. es eine Belegung B von {x1, . . . , xn, y} gibt, die mit

B auf {x1, . . . , xn} \ {y} ubereinstimmt und fur die WAB() = 1 gilt.


Interpretation uneigentlicher Formeln

Fur uneigentliche Formeln (x1, . . . , xn) und Belegungen B von {x1, . . . , xn}in A ergeben sich hieraus folgende Wahrheitswerte (Beweis: Ubung):

WAB (1 2) = 1, g.d.w. WAB (1) = 1 und WAB (2) = 1.

WAB (1 2) = 1, g.d.w. WAB (1) = 0 oder WAB (2) = 1 (oder beides).

WAB (1 2) = 1, g.d.w. WAB (1) = WAB (2).

WAB (y) = 1, g.d.w. fur alle Belegungen B von {x1, . . . , xn} {y}, diemit B auf {x1, . . . , xn} \ {y} ubereinstimmen, WAB() = 1 gilt.


Interpretation der L-Formeln: Notation

Ordnet die Belegung B den Variablen ~x = (x1, . . . , xn) die Individuen~a = (a1, . . . , an) zu, so schreibt man statt W

AB () = 1 auch

A [B(x1), . . . ,B(xn)] oder kurz A [~a]

und sagt: A macht die Formel (x1, . . . , xn) bzgl. der Belegung ~a wahr (oder gilt in A bzgl. ~a).

Entsprechend schreibt man auch A 6 [~a], falls WAB () = 0 gilt.

(Diese Schreibweisen werden im Skript von Herrn Gloede verwendet! ImFolgenden werden wir beide Schreibweisen benutzen.)


Das Koinzidenzlemma (fur Formeln)

Der Wahrheitswert WAB () einer Formel in einer Struktur A bzgl. einerVariablenbelegung B hangt nur von der Belegung der freien Variablen in ab:

KOINZIDENZLEMMA (fur Formeln). Sei A eine L-Struktur, eine L-Formel,V = {x1, . . . , xm} und V = {x 1, . . . , x n} Variablenmengen mit FV () V ,V und B und B Belegungen von V bzw. V in A, sodass

B FV () = B FV ().

Dann gilt WAB () = WAB().

BEWEIS. Induktion nach dem Aufbau von (wobei man fur Primformeln naturlich das Koinzidenzlemma fur Terme verwendet). Ubung!


Wahrheit und Modelle von Satzen

Nach dem Koinzidenzlemma hangt der Wahrheitswert eines Satzes in einerStruktur A nicht von der gewahlten Variablenbelegung ab: Da keine freienVariablen enthalt (d.h. FV () = ), gilt fur alle Variablenbelegungen B und B beliebiger Variablenmengen V und V in A: WAB () = WAB()

DEFINITION. Ein L-Satz ist in einer L-Struktur A wahr, wenn WAB () = 1 furdie leere Variablenbelegung gilt (d.h. fur die eindeutig bestimmte Belegung B derleeren Menge ).

NOTATION. Ist ein Satz in der Struktur A wahr, so schreiben wir

A

und sagen, dass A ein Modell von ist.


Wahrheit und Modelle von Formeln: Idee

In der Mathematik ist es ublich, bei Aussagen mit freien Variablen anzunehmen,dass die freien Variablen implizit allquantifiziert sind. So wird z.B. die Aussage,dass jede von der Null verschiedene naturliche Zahl Nachfolger einer naturlichenZahl ist, durch die Formel

x 6= 0 y (x = y + 1)

ausgedruckt, wobei diese als

x (x 6= 0 y (x = y + 1))

gelesen wird. Diese Konvention fuhrt zu folgender Erweiterung des Wahrheits-und Modellbegriffs fur Satze auf beliebige Formeln:


Wahrheit und Modelle von Formeln: Definition

DEFINITION. Eine L-Formel ist in einer L-Struktur A wahr, wenn WAB () = 1fur alle Variablenbelegungen B von FV () gilt.

Ist eine Formel in der Struktur A wahr, so schreiben wir A und sagen, dassA ein Modell von ist.

NB: Ist ein Satz, so stimmt diese Definition mit der zuvor fur Satze gegebenenDefinition der Wahrheit in einer Struktur uberein.


Wahrheit von Formeln vs. Wahrheit von Satzen:Allabschluss

DEFINITION. Der Allabschluss einer Formel , in der die Variablen x1, . . . , xnfrei vorkommen, ist der Satz

: x1 . . . xn ,

wobei wir davon ausgehen, dass die Variable x1, . . . , xn geordnet bzgl. derAufzahlung aller Variablen sind.

NB: Fur einen Satz gilt .

SATZ UBER DEN ALLABSCHLUSS. A A

BEWEIS: Ubung!


Wahrheit von Formeln vs. Wahrheit von Satzen:Bemerkungen

Man beachte, dass - nach Definition der Wahrheitswerte WAB () und demKoinzidenzlemma - fur einen L-Satz und eine L-Struktur A entweder A oder A gilt.

Fur eine Formel mit freien Variablen, konnen wir dagegen i.a. nur feststellen,dass nicht gleichzeitig A und A gelten kann. Hier ist jedoch moglich,dass weder A noch A gilt.

Der Grund hierfur ist, dass nicht als Negation von interpretiert wird,sondern als und als . Hierbei ist aber nicht zur Negation von (namlich ) aquivalent.

Zum Beispiel gilt fur die Formel x = y :

A 6 (x = y) fur alle Strukturen A

A 6 x = y fur alle Strukturen A, deren Trager zumindest 2 Elemente enthalt

Fur A mit |A| 2 gilt also weder A noch A .


Durch Formeln dargestellte Relationen

Wir beenden die Diskussion des Interpretationsbegriffs in der Pradikatenlogik mitder Beobachtung, dass L-Formeln Relationen auf den L-Strukturen A definieren:

DEFINITION. Sei (x1, . . . , xn) eine L-Formel mit FV () {x1, . . . , xn}.Die von auf der L-Struktur A definierte n-stellige Relation RA ist durch

(a1, . . . , an) RA A [a1, . . . , an]

bestimmt.

BEISPIEL. In der Sprache von N = (N; +, ; 0, 1) wird die Menge der geradenZahlen durch die Formel

(x) y(x = (1 + 1) y)

und die Teilbarkeitsrelation (x teilt y) durch die Formel

(x , y) x 6= 0 z(x z = y)

definiert.


2.5 Pradikatenlogik: Zentrale semantische Konzepte

2.5.1 Allgemeingultigkeit, Erfullbarkeit und Folgerungsbegriff:Definition und Eigenschaften

2.5.2 Beispiele: Aussagenlogik vs. Pradikatenlogik

2.5.3 Beispiele: Gleichheitsformeln

2.5.4 Beispiele: Existenzformeln und deren Instanzen


2.5.1 Allgemeingultigkeit, Erfullbarkeit undFolgerungsbegriff: Definition und Eigenschaften


Zentrale semantische Konzepte: Vorbemerkungen

Nachdem wir die Syntax und Semantik der Sprachen der Pradikatenlogikeingefuhrt haben, konnen wir nun die zentralen (semantischen) Begriffe derPradikatenlogik (Allgemeingultigkeit, Erfullbarkeit, Folgerung, Aquivalenz)vorstellen.

Diese zentralen Begriffe werden entsprechend wie in der Aussagenlogik definiert,wobei wir aber statt von der Wahrheit einer (al.) Formel bzgl. einer Belegung derAussagenvariablen nun von der Wahrheit einer (pl.) Formel in einer Strukturausgehen.

(Wir halten hierbei immer noch eine Sprache

L = L((Ri |i I ), (fj |j J), (ck |k K ))

vom Typ(L) = ((ni |i I ), (mj |j J),K )

der Pradikatenlogik fest, und meinen im Folgenden mit einer Struktur A immereine L-Struktur.)Mathematische Logik (WS 2017/18) Kap. 2: Pradikatenlogik 1. Stufe 58 / 81

Allgemeingultigkeit und Erfullbarkeit: Definition

DEFINITION. Eine (L-)Formel ist (logisch) wahr oder allgemeingultig, wennalle L-Strukturen Modell von sind, d.h. wenn

Fur alle L-Strukturen A: A

gilt.

DEFINITION. (a) Eine (L-)Formel ist erfullbar, wenn ein Modell besitzt, d.h.wenn

Es gibt eine L-Struktur A mit A

gilt. Andernfalls ist unerfullbar.

(b) Eine Menge von L-Formeln ist erfullbar, wenn es eine L-Struktur A gibt,die Modell aller Formeln in ist.

Ist eine L-Struktur A Modell aller Formeln in einer Formelmenge , so nennenwir A ein Modell von und schreiben A .


Allgemeingultigkeit vs. Erfullbarkeit

Ahnlich wie in der Aussagenlogik beobachtet man die folgenden Zusammenhangezwischen Allgemeingultigkeit und Erfullbarkeit:

Jede allgemeingultige Formel ist erfullbar.

Die Umkehrung hiervon gilt i.a. nicht. So ist z.B. die L-Formel x = yerfullbar, da sie in allen L-Strukturen A mit |A| = 1 gilt. Sie ist jedoch nichtallgemeingultig, da sie in L-Strukturen A mit |A| > 1 nicht gilt.

Ein L-Satz () ist genau dann allgemeingultig, wenn () unerfullbarist.

BEWEIS. Dies folgt aus der Tatsache, dass in jeder L-Struktur A entwederder Satz oder der Satz gilt.

Fur beliebige Formeln folgt zwar aus der Allgemeingultig von auch dieUnerfullbarkeit von . Die Umkehrung gilt aber i.a. nicht. So ist fur dieFormel x = y die Negation x 6= y nicht erfullbar, aber nichtallgemeingultig (s.o.).


Erfullbarkeit von Formeln vs. Erfullbarkeit vonFormelmengen

Die leere Formelmenge ist erfullbar.

Ist eine nichtleere Formelmenge erfullbar, so sind alle Formeln in erfullbar, da

A : A

Die Umkehrung gilt jedoch i.a. nicht. So sind die Formeln

1 x y (x = y) und 2 x y (x 6= y)

beide erfullbar. Die Modelle von 1 und 2 sind aber gerade die Strukturenmit einem Individuum bzw. mit mindestens zwei Individuen, sodass 1 und2 kein gemeinsames Modell besitzen. Die Formelmenge = {1, 2} istalso unerfullbar.


Folgerung und Aquivalenz: Definition

DEFINITION. Eine (L-)Formel folgt aus einer (L-)Formel ( ), wennjedes Modell von auch ein Modell von ist, d.h. wenn

Fur alle L-Strukturen A: A A

gilt. und sind aquivalent ( aq ), falls aus und aus folgt (also und dieselben Modelle besitzen).

Der Folgerungsbegriff lasst sich auf Formelmengen erweitern:

DEFINITION. Eine (L-)Formel folgt aus einer Menge von (L-)Formeln( ), wenn jedes Modell von auch ein Modell von ist, d.h. wenn

Fur alle L-Strukturen A: A A

gilt.


Folgerungsbegriff: Bemerkungen und Beobachtungen (1)

NOTATION:

Fur nichtleeres endliches = {1, . . . , n} schreiben wir statt auch1, . . . , n .

Entsprechend schreiben wir statt auch kurz .

NB: Dies ist konsistent mit der zuvor eingefuhrten Schreibweise furallgemeingultiges : jede L-Struktur A ist ein Modell der leerenFormelmenge, weshalb genau dann aus der leeren Formelmenge folgt,wenn allgemeingultig ist.


Folgerungsbegriff: Bemerkungen und Beobachtungen (2)

EINFACHE FAKTEN:

MONOTONIE DES FOLGERUNGSBEGRIFFS:

&

VERTRAGLICHKEIT VON UND :

1, . . . , n 1 n

(1 n)


Zusammenhang zw. Folgerungsbegriff und Erfullbarkeit

Ruckfuhrung der Erfullbarkeit auf den Folgerungsbegriff:

LEMMA. Eine L-Formelmenge is genau dann erfullbar, wenn es keinen L-Satz mit und gibt.

Ruckfuhrung des Folgerungsbegriffs auf die Erfullbarkeit:

LEMMA (Zusammenhang zwischen Folgerungs- und Erfullbarkeitsbegriff). Furjede L-Formelmenge und jeden L-Satz gilt:

{} unerfullbar

BEWEIS.

A : A A (nach Definition) A : A A 6 (da entweder A oder A ) 6 A : A & A {} unerfullbar (nach Definition)


Allgemeingultigkeit und Folgerungsbegriff: Beispiele

In den folgenden Unterabschnitten betrachten wir noch Beispiele furallgemeingultige Formeln (und korrekte Folgerungen):

2.5.2 Junktoren: aussagenlogische Gultigkeit vs. pradikatenlogische Gultigkeit

2.5.3 Gleichheitszeichen: allgemeingultige Aussagen uber die Gleichheit(Gleichheitsformeln)

2.5.4 Existenzquantor: allgemeingultige Aussagen uber Existenzformeln undderen Instanzen


2.5.2 Beispiele: Aussagenlogik vs. Pradikatenlogik


Aussagenlogische Gultigkeit: Aussagenlogische Belegungen

Eine Formel ist elementar, falls atomar oder eine Existenzformel x ist.

Elementare Formeln lassen sich aussagenlogisch nicht weiter zerlegen,spielen daher in PL die Rolle der Aussagenvariablen in AL.

Eine aussagenlogische Belegung B von L ist eine Abbildung

B : { : elementar} {0, 1}.

Eine al. Belegung B lasst sich induktive wie folgt auf alle Formeln fortsetzen:

B() := 1 B()

B(1 2) := max(B(1),B(2))


Aussagenlogische Gultigkeit: Tautologien

DEFINITION. Eine Formel ist eine Tautologie (oder aussagenlogisch gultig,AL ), falls B() = 1 fur alle al. Belegungen B gilt.

Intuitiv: Eine pradikatenlogische Formel ist aussagenlogisch gultig, wenn dieaussagenlogische Formel AL, die man aus erhalt indem man alle elementarenFormeln durch Aussagenvariablen ersetzt, allgemeingultig (in AL) ist.

TAUTOLOGIELEMMA. Jede Tautologie ist allgemeingultig:

AL

Die Umkehrung des Tautologielemmas gilt i.a. nicht. So ist z.B. die elementareFormel x (x = x) allgemeingultig, wogegen keine elementare Formelaussagenlogisch gultig ist.


Beweis des Tautologielemmas: elementare Teilformeln

Zum Beweis des Tautologielemmas definieren wir zunachst die Menge ETF ()der elementaren Teilformeln einer Formel durch Ind():

Ist elementar, so ist ETF () = {}.

Ist die Negationsformel , so ist ETF () = ETF ().

Ist die Disjunktionsformel 1 2, so istETF () = ETF (1) ETF (2).


Beweis des Tautologielemmas: Hilfssatz

HILFSSATZ. Sei A eine L-Struktur und sei B : {v1, v2, v3, . . . } A eineBelegung aller Individuenvariablen in A. Dann gibt es eine aussagenlogischeBelegung B von L, fur die

() WAB () = B ()

fur alle L-Formeln gilt.

BEWEIS. Definiere B durch B () := WAB () fur jede elementare Formel . DieBehauptung () folgt dann einfach durch Ind().


Beweis des Tautologielemmas: Kern des Beweises

Der Beweis ist durch Kontraposition:

Annahme: sei nicht allgemeingultig.

Dann gibt es eine L-Struktur A und eine Belegung B : FV () A der in vorkommenden freien Variablen in A, sodass WAB () = 0.

Setzt man B beliebig zu einer Belegung B aller Variablen fort, so gilt nachdem Koinzidenzlemma, dass WA

B() = WAB () = 0.

Nach dem Hilfssatz gibt es nun eine aussagenlogische Belegung B von L,sodass B () = WA

B() = WAB () = 0.

Folglich ist keine Tautologie.

Hiermit ist das Tautologielemma bewiesen.


Aussagenlogische Folgerungen

DEFINITION. Eine Formel ist eine aussagenlogische Folgerung aus den Formeln1, . . . , n ( 1, . . . , n AL ), falls fur alle al. Belegungen B gilt:

B(1) = = B(n) = 1 B() = 1

LEMMA UBER AL. FOLGERUNGEN: 1, . . . , n AL 1, . . . , n

BEWEIS:

1, . . . , n AL AL 1 n

1 n (Tautologielemma)

1, . . . , n


2.5.3 Beispiele: Gleichheitsformeln


Allgemeingultige Gleichheitsformeln

LEMMA. Die folgenden Formeln sind allgemeingultig:

1 1 x = x2 2 x = y y = x3 3 x = y y = z x = z4 4 x1 = y1 . . . xmj = ymj fj(x1, . . . , xmj ) = fj(y1, . . . , ymj )5 5 x1 = y1 . . . xni = yni Ri (x1, . . . , xni ) Ri (y1, . . . , yni )

BEWEIS: Da die Beweis sehr ahnlich sind, zeigen wir hier nur dieAllgemeingultigkeit von 4 (andere Formeln: Ubung).


Allgemeingultigkeit von 4Die Allgemeingultigkeit von

4 x1 = y1 . . . xmj = ymj fj(x1, . . . , xmj ) = fj(y1, . . . , ymj )

zeigt man wie folgt:

Gegeben: L-Struktur A und Belegung B : {x1, . . . , xmj , y1, . . . , ymj} A.Zu zeigen: WAB (4) = 1.

Gilt WAB (x1 = y1 . . . xmj = ymj ) = 0, so ist die Behauptung trivial.Also o.B.d.A. WAB (x1 = y1 . . . xmj = ymj ) = 1.Es folgt: WAB (xp = yp) = 1 fur p = 1, . . . ,mj .

Also nach Definition von WAB : (xp)AB = (yp)

AB fur p = 1, . . . ,mj .

Mit der Definition von tAB folgt:

fj(x1, . . . , xmj )AB = f

Aj ((x1)

AB , . . . , (xmj )

AB )

= f Aj ((y1)AB , . . . , (ymj )

AB ) = fj(y1, . . . , ymj )

AB

Mit der Definition von WAB folgt WAB (fj(x1, . . . , xmj ) = fj(y1, . . . , ymj )) = 1

und hieraus WAB (4) = 1.


2.5.4 Beispiele: Existenzformeln und deren Instanzen


Existenzformeln und deren Instanzen: Substitution

SUBSTITUTION: Ersetzen wir in einer Formel alle freien Vorkommen derVariablen x durch den Term t, so bezeichnen wir das Ergebnis dieser Substitutionmit [t/x ].

INSTANZEN EINER EXISTENZFORMEL: Unter den Instanzen einerExistenzformel versteht man die Formeln [t/x ], wobei t ein konstanter Termist.

Anschaulich klar ist, dass die Wahrheit einer Instanz [t/x ] in einer Struktur A(bezuglich einer Belegung B) die Wahrheit der Existenzformel x in A(bezuglich B) impliziert. (Die Umkehrung braucht im Allgemeinen nicht gelten,da moglicherweise nicht jedes Indviduum von A durch einen konstanten Termdargestellt werden kann.) Wir werden dies im Folgenden formal beweisen, wobeiwir sogar beliebige Terme t zulassen, solange es nicht durch eine Bindung der in tvorkommenden Variablen zu einer Sinnentstellung kommen kann.


Das Substitutionslemma

SUBSTITUIERBARKEITSBEDINGUNG (SB): Ein Term t heisst in einer Formel fur die Variable x substituierbar, wenn keine in t vorkommende Variable y 6= xin gebunden vorkommt.

SUBSTITUTIONSLEMMA. Sei der Term t fur die Variable x in der Formel substituierbar. Dann ist [t/x ] x allgemeingultig.

BEMERKUNG. Die Substituierbarkeitsbedingung ist notwendig: Fur

t y und y(x = y)

ist die Formel[t/x ] x y(y = y) xy(x = y)

nicht allgemeingultig (sie gilt namlich in keiner Struktur mit mehr als einemIndividuum).


Beweis des Substitutionslemmas: Aufgabenstellung

Annahmen:

Keine in t vorkommende Variable y 6= x kommt in gebunden vor (=SB).

FV () V (t) {x , x1, . . . , xn} (wobei x , x1, . . . , xn paarweise verschieden)

A sei eine L-Struktur und B eine Belegung B : {x , x1, . . . , xn} A

Zu zeigen: (*) WAB ([t/x ] x) = 1

Voruberlegungen:

Da WAB ([t/x ] x) = 1 genau dann gilt, wennWAB ([t/x ]) WAB (x) gilt, folgt die Behauptung (*) ausWAB ([t/x ]) = 0 trivialerweise.

Gilt x 6 FV (), so gilt [t/x ] und WAB () = WAB (x), also auchWAB ([t/x ]) = W

AB (x) und daher (*).

Wir konnen also o.B.d.A. zusatzlich annehmen, dass WAB ([t/x ]) = 1 undx FV () gilt, und mussen dann WAB (x) = 1 zeigen.


Beweis des Substitutionslemmas: Aufgabenstellung neuAnnahmen (aktualisiert):

Keine in t vorkommende Variable y 6= x kommt in gebunden vor (=SB).x FV () & FV () V (t) {x , x1, . . . , xn} (wobei x , x1, . . . , xn paarweiseverschieden)

A L-Struktur und B Belegung B : {x , x1, . . . , xn} A mit WAB ([t/x ]) = 1

Zu zeigen (aktualisiert): (**) WAB (x) = 1Nach Definition des Wahrheitsbegriffs genugt es eine BelegungB : {x , x1, . . . , xn} A anzugeben mit B (xi ) = B(xi ), fur die() WAB() = 1 gilt.Definiere solch eine Belegung durch B (x) = tAB (und B

(xi ) = B(xi )).

Zum Nachweis von () genugt es wegen WAB ([t/x ]) = 1 (nachAnnahme!) zu zeigen:

WAB() = WAB ([t/x ])

Dies zeigt man aber leicht durch Ind() (unter Verwendung von (SB)),nachdem man zuvor (fur beliebige Terme t) tAB = t[t/x ]

AB durch Ind(t)

gezeigt hat): Ubung.


Kapitel 2 Die Pr adikatenlogik (erster Stufe) · Kapitel 2 Die Pr adikatenlogik (erster Stufe) Mathematische Strukturen und formale Sprachen Mathematische Logik (WS 2017/18) Kap

Text of Kapitel 2 Die Pr adikatenlogik (erster Stufe) · Kapitel 2 Die Pr adikatenlogik (erster Stufe)...

Kapitel 1 Grundlagen · 1 Unternehmensführung II Kapitel 1 Grundlagen ... stufe 1. Haupt-stufe 1. Haupt-stufe 2. Haupt-stufe 1 Grundlagen der Net Economy 1.1 Merkmale einer

Stufe 4 Rotes Paddel Stufe 4 - kanu.de Deutschland/7_EPP... · Europäischer Paddel-Pass Deutschland Seite 65 Stand: Juni 2019 Stufe 4 - Rotes Paddel Stufe 4 . Rotes Paddel . Stufe

Mathematische Ansätze1 Dynamisches Verhalten Mathematische Ansätze Rechenverfahren

Pr¨adikatenlogik 1. Stufe - Centrum für Informations- …micha/kurse/matheI-WS0607/begle... · 2007-01-16 · Pr¨adikatenlogik 1. Stufe Im Rahmen der Aussagenlogik hatten wir eine

Logik - · PDF fileGrundlagen der Pr¨adikatenlogik Beziehungen zwischen Eigenschaften von Elementen Semantik der P-Logik 2-Stufe – Interpretationen, Belegungen, Bewertungen

Einfuhrung¨ in die Mathematische Modellierung · Einfuhrung¨ in die Mathematische Modellierung Skript zur Vorlesung Mathematische Modellbildung fu¨r das Lehramt an Gymnasien an

Mathematische Ansätze

Stufe für Stufe Qualität. DIETEL - TREPPEN...DIETEL Stufe für Stufe QualitätFENSTER TÜREN TREPPEN Mehr Informationen finden Sie unter: Form und Funktion in Harmonie, so präsen-tieren

Kiwa International Cert GmbH Thermografie Stufe 1 und Stufe 2 · PDF fileSeite 3 Kiwa International Cert GmbH: Thermografie Stufe 1 und Stufe 2 Thermografie Stufe 2 - Schulung, Prüfung

Mathematische Grundlagen geophysikalischer ... · Mathematische Grundlagen . geophysikalischer Naturgefahrenmodelle . Tagung der Fachschaft Mathematik/Informatik des Cusanuswerks

Tabelle TVöD / VKA - kav-nw.de · Entgelt-gruppe. Stufe 1 Stufe 2 Stufe 3 Stufe 4 Stufe 5 Stufe 6 N-2.796,54 2.932,80 3.107,51 3.248,61 3.444,31 . Notfallsanitäterinnen und Notfallsanitäter

~Erste Stufe!~

0843 34 TK GKVi 2014 - sozialversicherung.verdi.de+file++53c913f36f684458d7000… · März 2014 Stufe 1 Stufe 2 Stufe 3 Stufe 4 Stufe 5 1 2.275,92 2.418,17 2.560,41 2.702,66 2.844,90

~Dritte Stufe!~

Jugendarbeit im Distrikt P. Elektronikbasteln Robotergruppe Amateurfunkgruppe Der aktive OV Stufe 4 Stufe 3 Stufe 2 Stufe 1 13-15 12-13 11-12 Alter (ca.)

Mathematische Grundlagen I Logik und Algebratimhaga/mathematische-grundlagen-1-ws2017/... · Mathematische Grundlagen I Zu meiner Person Dr.TimHaga StudiumderMathematik,Physik,Informatikund

Kapitel 2 Die Pr¨adikatenlogik (erster Stufe) · 2013-01-04 · Kapitel 2 Die Pr¨adikatenlogik (erster Stufe) Mathematische Strukturen und formale Sprachen Mathematische Logik (WS

~Zweite Stufe!~

Zweiwegebagger - Liebherr … · Generation 6 Einsatzgewicht 20.400 – 23.400 kg Motor 120 kW / 163 PS Stufe V Stufe Tier 4f Stufe IIIA (konform) Stufe China III Zweiwegebagger

Logik I - mcmp.philosophie.uni-muenchen.de · Hannes Leitgeb Logik I Eine Einf uhrung in die klassische Aussagen- und Pr adikatenlogik Stand: 24.01.2016

Klassische Prädikatenlogik - uni-muenster.de · mantik und Syntax der klassischen Prädikatenlogik erreicht sein, kurz gesagt der Symbole |= und ‘. Beide fußen auf dem Begriff

· Britta Ehrich (LV S-H), Stufe D 1/2 Andreas Taschner (LV S-H), Stufe DI /2 ... König (LV S-H), Stufe DI/2 Olaf Maibaum (Rendsburg), Stufe DI/2 Ivonne Köppen (Rendsburg), Stufe

Mathematische Grundlagen

2. Mathematische Grundlagen - uni-muenster.de · 2. Mathematische Grundlagen Erforderliche mathematische Hilfsmittel: ‘ Summen und Produkte ‘ Exponential- und Logarithmusfunktionen

Was ist (individuelle) mathematische Begriffsbildung? · Florian Schacht Was ist mathematische Begriffsbildung? Mathematische Begriffe am Beispiel der Differentialrechnung Die Schüler

Überraschende Mathematische Kurzgeschichten

Logik Vorlesung 7: Grundlagen Prädikatenlogikquaas/ws2014logvl07_ho.pdf · Vorlesungsziele heutige Vorlesung 1 Modellierung in Pr adikatenlogik 2 Syntax der Pr adikatenlogik 3 Semantik

Ökosystem Gartenteich · Stufe 1 Wasserwerte einstellen Basiswasserpflege Stufe 2 Algen bekämpfen Algenvernichter, Fadenalgenvernichter Stufe 3 Algen vorbeugen Algenvorbeugung 1

Tutorium Mathematische Grundlagen · Tutorium Mathematische Grundlagen Erg anzungen zu der Vorlesung Mathematische Grundlagen der Physik (G1) Mathematik f ur Physik 1 Klaus Huthmacher

Logik - TU Braunschweig · PDF fileGrundlagen der Pr¨adikatenlogik Beziehungen zwischen Eigenschaften von Elementen Semantik der P-Logik 2-Stufe – Interpretationen, Belegungen,

Documents

Kapitel 2 Die Pr adikatenlogik (erster Stufe) · Kapitel 2 Die Pr adikatenlogik (erster Stufe) Mathematische Strukturen und formale Sprachen Mathematische Logik (WS 2017/18) Kap

Text of Kapitel 2 Die Pr adikatenlogik (erster Stufe) · Kapitel 2 Die Pr adikatenlogik (erster Stufe)...