imported>Quaoaris: /* growthexperiments-addlink-summary-summary:2|0|1 */

2025-01-06T11:50:19Z

growthexperiments-addlink-summary-summary:2|0|1

Neue Seite

Eine '''elementare Sprache''' <math>L^S</math> (auch: Sprache erster Stufe mit der [[#Das Alphabet einer Sprache erster Stufe|Symbolmenge]] S) ist eine im Rahmen der [[Prädikatenlogik erster Stufe]] definierte [[formale Sprache]]. Mit diesen Sprachen lassen sich mathematische Theorien formallogisch behandeln; so z. B. die [[Mengenlehre]] usw. Die Erfahrung zeigt sogar, dass sich ''alle'' mathematischen Aussagen in einer geeigneten Sprache erster Stufe formalisieren lassen, und dass sich ''alle'' beweisbaren Aussagen innerhalb einer Sprache erster Stufe mit Hilfe des [[Sequenzenkalkül]]s ableiten lassen.<ref>Ebbinghaus u. a., Kapitel VII § 2: Mathematik im Rahmen der ersten Stufe.</ref>

== Das Alphabet einer Sprache erster Stufe ==
=== Definition ===
Das [[Alphabet (Mathematik)|Alphabet]] einer Sprache erster Stufe umfasst folgende Zeichen:
# <math>v_0, v_1, v_2, \ldots</math>  Symbole für [[Variable (Mathematik)|Variablen]];
# <math>\neg, \wedge, \vee, \rightarrow, \leftrightarrow</math>  [[Junktor]]en: nicht, und, oder, wenn – so, genau dann wenn;
# <math>\forall, \exists</math>  [[Quantor]]en: für alle, es gibt;
# <math>\equiv</math>  Gleichheitszeichen;
# <math>),(</math>  technische Zeichen: Klammersymbole;
# sowie
::a)  für jedes <math>n\ge 1</math> eine (eventuell leere) Menge von <math>n</math>-stelligen [[Relation (Mathematik)|Relationssymbolen]], alle zusammen: <math>R_1, R_2,\ldots</math>;
::b)  für jedes <math>n\ge 1</math> eine (eventuell leere) Menge von <math>n</math>-stelligen [[Funktion (Mathematik)|Funktionssymbolen]], alle zusammen: <math>f_1, f_2,\ldots</math>;
::c)  eine (eventuell leere) Menge von Symbolen für [[Konstante (Logik)|Konstanten]] <math>c_1, c_2,\ldots</math> (siehe Anmerkung unten zu 0-stelligen Funktionen).

Die Menge der Zeichen unter Punkt 1 bis 5 sind die ''logischen Zeichen''; sie sind für alle Sprachen erster Ordnung dieselben; sie werden mit ''A'' bezeichnet.

Die Menge der Zeichen unter Punkt 6 bezeichnet man als ''Symbolmenge'' (auch [[Signatur (Modelltheorie)|Signatur]]) <math>S=\{R_1,R_2,\ldots,f_1,f_2,\ldots, c_1,c_2,\ldots\}</math>; durch sie wird die spezielle Sprache erster Stufe bestimmt.

=== Hinweise ===
* In [[Alphabet (Mathematik)#Das Alphabet einer Prädikatenlogik erster Stufe|Alphabeten]] sind bei sonst identischer Definition die Konstanten aus (6)(c) nicht aufgeführt; dafür sind in (6)(a) nullstellige Relationen und Funktionen erlaubt (<math>n=0</math>), letztere entsprechen den Konstanten aus der obigen Definition (siehe auch [[Verknüpfung (Mathematik)#Nullstellige Verknüpfungen|Nullstellige Verknüpfungen]]).
* Die einstelligen Relationen definieren Zusammenfassungen wie sie Mengen oder allgemeiner [[Klasse (Mengenlehre)|Klassen]] entsprechen.

=== Beispiel: Gruppentheorie ===
Um den Begriff der [[Gruppe (Mathematik)|Gruppe]] und die definierenden Axiome zu formalisieren, geht man wie folgt vor:

# Die ''Variablen'' <math>x,y,z,\ldots</math> stehen für Elemente der Gruppe; außerdem gibt es eine Konstante <math>e</math>.
# Es wird ein Symbol <math>\circ</math> eingeführt; dieses steht für die ''zweistellige Verknüpfung'' zweier Elemente.
# [[Assoziativgesetz]]: <math>\forall x \forall y \forall z (x\circ y)\circ z \equiv x\circ(y\circ z)</math>
# [[Neutrales Element]]: <math>\forall x (x\circ e\equiv x)</math>
# Inverse Elemente: <math>\forall x \exists y (x\circ y \equiv e)</math>

In diesem Fall gibt es also ein zweistelliges ''Funktionssymbol'' <math>\circ</math> sowie eine einzige Konstante <math>e</math>.

=== Weitere Beispiele ===

{| class="wikitable" style="text-align:center;"
|-
!Relationssymbole
!Funktionssymbole
!Konstanten
!Name
|-
| <math>\leq</math> (zweistellig)
| <math>+, \cdot</math> (beide zweistellig)
|0, 1
|[[Geordneter Körper|Geordnete Körper]]
|-
|
| <math>\circ </math> (zweistellig)
| e
|[[Gruppe (Mathematik)|Gruppen]]
|-
|
| +,<math>\cdot</math> (beide zweistellig)
|0, 1
|[[Ring (Algebra)|Ringe]]
|-
| <math>\sim</math> (zweistellig)
|
|
|[[Äquivalenzrelation]]
|}

== Terme ==
{{Hauptartikel|Term#Formale Definition|titel1=Terme}}
Die Definition der Terme <math>T^S</math> einer elementaren Sprache erfolgt [[rekursiv]]. Ein Term der elementaren Sprache wird durch endlich viele Anwendungen der folgenden Regeln erhalten

#Variablensymbole sind Terme.
#Konstantensymbole sind Terme.
#Wenn <math>f</math> ein <math>n</math>-stelliges Funktionssymbol und <math>t_1,\ldots,t_n</math> Terme sind, dann ist auch <math>f(t_1,\ldots,t_n)</math> ein Term.

{| class="wikitable"
!Symbolmenge S
!Beispiel für Terme aus <math>T^S</math>
|-
|<math>(0,1,+,\cdot,<)\ </math>
|<math>0,1,0+1,(0+v_1)\cdot((v_0+1)+(v_2+1))\ </math>,
|-
|<math>( 0 , + )\ </math>
|<math> 0+v_0\ </math>
|-
|<math>(1,S)\ </math>
|<math>1, S(1),S(S(1)),\ldots</math>
|}

;Anmerkungen
* Es gibt auch klammerfreie Notationen wie etwa die [[polnische Notation]]; in der Regel sind diese aber nicht so leicht zu lesen. Die dritte obige Definitionszeile lautet in dieser Notation (vergleiche: [[Prädikatenlogik erster Stufe#Terme|Prädikatenlogik erster Stufe §Terme]]):
::<small>o</small>  Wenn <math>f</math> ein ''n''-stelliges Funktionssymbol ist und <math>t_1,\dotsc, t_n</math> Terme sind, so ist auch <math>ft_1,\dotsc, t_n</math> ein Term.
* Gelegentlich werden die Konstanten als nullstellige Funktionen subsumiert, was sich besonders natürlich in der klammerfreien Notation darstellt.

== Formeln ==
→ Siehe auch: [[Logische Formel]]n;  [[Term#Ausdrücke|Term §Ausdrücke]];  [[Prädikatenlogik erster Stufe#Ausdrücke|Prädikatenlogik erster Stufe §Ausdrücke]].

Die Formeln der Sprache <math>L^S</math> werden durch endlich viele Anwendungen der folgenden Regeln erhalten:

=== Atomformeln ===
#Wenn <math>t_1</math> und <math>t_2</math> Terme sind, dann ist <math>t_1=t_2</math> eine Formel.
#Wenn <math>R</math> ein <math>n</math>-stelliges Relationssymbol und <math>t_1,\ldots,t_n</math> Terme sind, dann ist <math>R(t_1,\ldots,t_n)</math> eine Formel.<ref>Gelegentlich werden nullstellige Relationen zugelassen, dies treten dann als logische Konstanten (im Prinzip Bezeichner für ''wahr'' oder ''falsch'') auf.<br />{{Literatur |Autor=Stefan Brass |Titel=Mathematische Logik mit Datenbank-Anwendungen |Verlag=Martin-Luther-Universität Halle-Wittenberg, Institut für Informatik |Ort=Halle |Datum=2005 |Seiten=176 |Fundstelle=hier S. 19 |Online=[https://users.informatik.uni-halle.de/~brass/db07/d2_logic.pdf informatik.uni-halle.de] |Format=PDF |KBytes=}}</ref>

=== Aussagenlogische Verknüpfungen ===
#Wenn <math>\psi</math> eine Formel ist, dann auch <math>\neg\psi</math>.
#Wenn <math>\psi</math> und <math>\theta</math> Formeln sind, dann auch
#*<math>\psi\wedge\theta</math>
#*<math>\psi\vee\theta</math>
#*<math>\psi\rightarrow\theta</math>
#*<math>\psi\leftrightarrow\theta</math>

=== Quantoren ===
{{Hauptartikel|Quantor|titel1=Quantoren}}
Wenn <math>\psi</math> eine Formel und <math>x</math> ein beliebiges Variablensymbol ist, dann sind auch
:<math>\exists x \psi</math> und
:<math>\forall x \psi</math>
Formeln.

Die elementare Sprache <math>L^S</math> zur Symbolmenge (Signatur) <math>S</math> besteht nun aus allen nach den obigen Regeln gebildeten Formeln.

== Zusammenhang mit Chomsky-Hierarchie ==
{{Siehe auch|Chomsky-Hierarchie}}
# Die Regeln für Terme entsprechen einer [[Kontextfreie Sprache|kontextfreien Sprache]].
# Die Regeln für Formeln entsprechen ebenfalls einer [[Kontextfreie Sprache|kontextfreien Sprache]]: Elementare Sprachen sind also kontextfreie Sprachen und damit eine spezielle Klasse von [[Formale Sprache|formalen Sprachen]].
# Die Regeln für [[Beweis (Logik)|Beweise]] entsprechen einer [[Kontextsensitive Sprache|kontextsensitiven Sprache]]. Durch eine kontextsensitive Analyse kann entschieden werden, ob ein ''gegebener'' Beweis für eine Formel vorliegt.
# Die Regeln für das [[Ableitung (Logik)|Ableiten]] einer Formel aus einem [[Axiomensystem#Logik|Axiomensystem]] entspricht einer [[Rekursiv aufzählbare Sprache|semi-entscheibaren Sprache]]. Es gibt im Allgemeinen keinen [[Algorithmus]], um einen Beweis ''zu erhalten'', der eine Formel aus einer anderen Aussagenmenge ableitet.

== Quellen ==
* H.D. Ebbinghaus, J. Flum, W. Thomas: ''Einführung in die mathematische Logik.'' BI-Wiss. Verlag, Mannheim / Leipzig / Wien / Zürich 1992, ISBN 3-411-15603-1.
* Hans-Peter Tuschik, Helmut Wolter: ''Mathematische Logik – kurzgefasst. Grundlagen, Modelltheorie, Entscheidbarkeit, Mengenlehre.'' BI-Wiss. Verlag, Mannheim / Leipzig / Wien / Zürich 1994, ISBN 3-411-16731-9.

== Einzelnachweise ==
<references />

[[Kategorie:Mathematische Logik]]
[[Kategorie:Logik]]

Elementare Sprache - Versionsgeschichte

imported>Quaoaris: /* growthexperiments-addlink-summary-summary:2|0|1 */