Funktionssymbole der Prädikatenlogik

Question

was ist der Unterschied zwischen den Funktionssymbolen und Relationssymbolen in der Prädikatenlogik erster Stufe?

Answer 1

Funktionssymbole sind Symbole für Funktionen. Funktionen sind mathematische Objekte, mit denen anhand von Eingabewerten Ausgabewerte berechnet werden können.

Relationssymbole sind Symbole für Relationen. Relationen sind mathematische Objekte, mit denen Elmente des Universums zueinander in Beziehung gesetzt werden können.

Beispiel 1. Ist f ein zweistelliges Funktionssymbol, dann wird f(x,y) bei Auswertung der Formel zu einem Element des Universums, nämlich zu dem, dass sich ergibt wenn die Interpretation f_I des Funktionssysmbols f auf die Belegungen der Variablen x und y angewendet wird.

Beispiel 2. Ist R ein zweistelliges Relationsymbol, dann stellt  R(x,y) die Aussage dar, dass x und y in einer gewissen Beziehung zueinander stehen. Bei Auswertung der Formel wird R(x,y) zu einem Wahrheitswert, nämlich zu dem, der sich ergibt, wenn geprüft wird, ob für die Interpretation R_I des Relationsymbols R und die Belegungen x_I und y_I der Variablen x und y die Aussage (x_I, y_I) ∈ R_I gilt.

Comments

Danke für Deine tolle Antwort. Könntest Du mir vielleicht noch sagen, was es mit Formeln der Prädikatenlogik hat d.h. vielleicht ein Beispiel nennen? Ich kenne Formeln wie z.B. \( ( \forall x ) x>0 \), aber wo tauchen denn in solchen Formeln Funktionssymbole auf?

---

Sei z ein nullstelliges Funktionsymbol, i ein einstelliges Funktionssymbol und m ein zweistelliges Funktionssymbol. Betrachte folgende Formeln.

• ∀g m(g,z()) = g
• ∀g m(g,i(g)) = z()
• ∀g₁ ∀g₂ ∀g₃ m(m(g₁, g₂), g₃) = m(g₁, m(g₂, g₃))

Ein nullstelliges Funktionssymbol wird durch eine Funktion interpretiert, deren Funktionswert nicht von irgendeiner Eingabe abhängt. Im wesentlichen können solche Funktionen als konstante Elemente des Universums aufgefasst werden.

Die obigen Formeln zusammengenommen besagen, dass es sich bei eine Struktur

(U, 1: ∅→U, ^-1:U→U, •: U×U→U),

die alle Formeln erfüllt, um eine Gruppe handelt. Die nullstellige Funktion liefert das neutrale Element, die einstellige Funktion bildet inverse Elemente und die zweistellige Funktion ist die auf der Gruppe definierte Verknüpfung. Die erste Formel sichert die rechtsneutralität der 1 zu, die zweite Formel sichert die Existenz von Rechtsinversen Elementen zu und die dritte Formel sagt aus, dass die Verknüpfung assoziativ ist.

Die Notation der Gruppenaxiome in dieser Form ist etwas ungwöhnlich. Normalerweise würde man die Verknüpfung in Infix-Schreibweise (z.B. (g₁• g₂) • g₃ = g₁ • (g₂• g₃)) notieren. Ich wollte mit der Notation herausstellen, dass es sich bei Verknüpfungen in Formeln tatsächlich um Funktionssymbole handelt.

---

Oswald, danke das ganze ist aber bisschen abstrakt, finde ich. Man benutzt die Prädikatenlogik um Aussagen, die in der deutschen Sprache geschrieben wurden in die PL zu übersetzen und besser verstehen. Z.B. "alle Mengen X haben mindestens ein Element". Ich kann also schreiben \( (\forall M) \neg (M = \emptyset) \). Dabei werden Prädikate, logische Zeichen, Quantoren benutzt. Aber keine Funktionssymbole und deswegen suche ich nach einem Beispiel der deutschen Sprache, wo man direkt erkennt, dass ein Funktionssymbol benutzt wurde.

---

∀a ∀b (a+b)² = a² + 2·a·b + b².