Syntax

Geschichte (Intro)

Einteilung der Logik

Klassische Prädikatenlogik erster Stufe

Wir beschränken uns nur auf diese PL

Klassisch Weil es nur 2 Wahrheitswerte gibt - nach Frege

First Order Aussagenlogik ohne Quantoren

Einteilung der Logik

0. Stufe Aussagenlogik - keine Quantoren

$\small (A \wedge B) \supset C, \ldots$

1. Stufe Prädikatenlogik - Mit Quantoren über Domäne

$\small \forall x \exists y(P(x, y) \supset Q(c, f(x, y))), \ldots$

2. Stufe Quantoren über Prädikate (Relation), Funktionen

$\small \forall R \exists x \exists f(R(x, f(x)) \supset P(f(x))), \ldots$

Höhere Stufe: Quantoren über Funktionale, Relationen zwischen Relationen

$\small \forall F \exists P \exists f \forall x(P(F(f, y)) \supset g(x)=y), \ldots$

Syntax Prädikatenlogik

Syntax = Einteilung der Symbole

Logische Symbole

Aussagenlogische Konnektive / Junktoren / Operatoren

1-stellig: $\small \neg$

2-stellig: $\small \wedge, \vee \color{grey}, \supset ,\uparrow, \downarrow, \lrarr$

Aussagenlogische Konstanten / Wahrheitskonstanten

Keine Wahrheitswerte (semantisch)

Quasi 0-stellige Konnektive

$\small \bot, \top$ (falsum, verum)

Quantoren

$\small \forall, \exists$

Identität

Dieses Symbol ist mehrdeutig in der Mathematik - mal auf semantischer, mal auf syntaktischer Ebene benutzt (wir benutzen auf der semantischen Ebene $\small \equiv$ )

$\small =$

Signatur $\small \Sigma = \langle P S, K S, F S\rangle$

Auch "aussagenlogisches Alphabet" genannt

Prädikatensymbole $\small PS$

Eigenschaften, Relationen

Wenn n-stellig auch Relationssymbol genannt.

Wenn 0-stellig quasi Aussagenlogische Variable.

Funktionssymbole $\small FS$

Funktionen

Konstantensymbole $\small KS$

Bestimmte Dinge aus der Domäne (Gegenstände, Individuen)

Hat keine Stelligkeit (= Anzahl benötigter Argumente) im Gegensatz zu anderen Symbolen

Quasi 0-stellige Funktionssymbole

Hilfssymbole

$\small (, )$ wobei zur besseren Lesbarkeit auch eckige benutzt werden

Individuenvariablensymbole $\small IVS$

Variablen

$\small \{x, y, z, x_1, \dots\}$

Terme $\small \mathcal{T}_{\Sigma}$

Menge der $\small \mathcal{T}_{\Sigma}$ über Signatur $\small \Sigma=\langle P S, K S, F S\rangle$ :

Kleinste Menge für die gilt

$\small I V S \subseteq \mathcal{T}_{\Sigma}$ Variablen

$\small K S \subseteq \mathcal{T}_{\Sigma}$ Konstantensymbole

$\small f\left(t_{1}, \ldots, t_{n}\right) \in \mathcal{T}_{\Sigma}$ Funktionen mit Termen als Argument
wenn $\small f \in F S_{n}$ und $\small t_{1}, \ldots, t_{n} \in \mathcal{T}_{\Sigma}$

Keine Prädikatensymbole.

Können als Bäume verstanden werden.

Blätter Variable oder Konstantensymbole, innere Knoten Funktionssymbole.

Prädikatenlogische Formeln $\small \mathcal{P F}_{\Sigma}$

Menge der $\small \mathcal{P F}_{\Sigma}$ über $\small \Sigma=\langle P S, K S, F S\rangle$

Kleinste Menge für die gilt

$\small \perp, \top \color{grey} \in \mathcal{P F}_{\Sigma}$

$\small p\left(t_{1}, \ldots, t_{n}\right) \color{grey}\in \mathcal{P} \mathcal{F}_{\Sigma}$
wenn $\small p \in P S_{n}$ und $\small t_{1}, \ldots, t_{n} \in \mathcal{T}_{\Sigma}$

$\small s=t \color{grey}\in \mathcal{P F}_{\Sigma}$
wenn $\small s, t \in \mathcal{T}_{\Sigma}$

$\small \neg F,~ (F \wedge G), ~(F \vee G),~ (F \supset G) \color{grey}\in \mathcal{P} \mathcal{F}_{\Sigma}$
wenn $\small F, G \in \mathcal{P F}_{\Sigma}$

$\small \forall v F,~ \exists v F \color{grey}\in \mathcal{P F}_{\Sigma}$
wenn $\small v \in I V S$ und $\small F \in \mathcal{P F}_{\Sigma}$

Klammer-Einsparungsregeln

Äußere Klammer auslassen.

$\small \neg$ bindet stärker als $\small \vee, \wedge$

$\small \vee, \wedge$ binden gleich stark (Assoziativität muss berücksichtigt werden)

$\small \vee, \wedge$ binden stärker als $\small \supset$

Schreibkonventionen

$\small a, b, c, d, e$ Konstanten-Symbole

$\small f, g, h$ Funktionen-Symbole

$\small P,Q, R$ Prädikaten-Symbole

$\small x,y,z,u,v,w$ Variablen-Symbole

Traditionelle Symbole und Strukturen wie $\small \N, \Z$ .

$\small 0, 1$ sind $\small KS$

$\small +, -$ sind $\small FS$

$\small <, \leq$ sind $\small PS$

Freie vs. gebundene Variable

$\small V(t)$ Alle Variablen in Term $\small t$

$\small V(F)$ Alle Variablen in Formel in $\small F$

$\small FV(F)$ Menge der freien, ungebundenen Variablen in $\small F$

zB bei $\small \forall v F,~ \exists v F$ ist $\small v$ die durch einem Quantor in $\small F$ gebundene Variable .

Definition: Freie Vorkommen

$\small F V(\perp)=F V(\top)=\{\}$

$\small F V(p(t_{1}, \ldots, t_{n}))=V(p(t_{1}, \ldots, t_{n}))~~\color{grey}(=V(t_{1}) \cup \ldots \cup V(t_{n}))$

$\small F V(t=s)=V(t=s)~~\color{grey}(=V(t) \cup V(s))$

$\small F V(\neg F)=F V(F)$

$\small F V(F \circ G)=F V(F) \cup F V(G)$
für $\small \circ \in\{\wedge, \vee, \supset\}$

$\small F V(Q v F)=F V(F)-\{v\}$
für $\small Q \in\{\forall, \exists\}$
Der Quantor bindet die freien Vorkommen von $\small v$ in $\small F$ .

Wichtig

$\small v$ kann gleichzeitig frei und gebunden vorkommen.

$\small F$ ist geschlossen wenn $\small F V(F)=\{\}$

selbiges für $\small t$ wenn $\small F V(t)=V(t)=\{\}$

Variablen-Substitution

$\small F(x / t)$

Ausschließlich die freien Variablen $\small x$ in $\small F$ durch Term $\small t$ ersetzt.

Syntax Aussagenlogik

Sonderfall von Prädikatenlogik

Aussagenlogik

keine: $\small IVS$ , $\small KS$ , $\small FS$ , $\small =$ und Quantoren

Aussagenvariable

0-stellige Prädikatensymbole $\small P,Q,R$

sowie $\small \top, \bot$

Keine Angabe von Signatur - es gibt abzählbar unendlich viele Aussagenvariablen zur Verfügung

Aussagenlogische Formeln $\small \mathcal{AF}$

Keine $\small IVS, PS, KS, =$

Aussagenlogische Formeln

Kleinste Menge für die gilt:

Sei $\small AV = PS_0$ eine aussagenlogische Variable

$\small \perp, \top \color{grey}\in \mathcal{A F}$

$\small p \color{grey}\in \mathcal{AF}$
wenn $\small p \in AV$

$\cancel {\small s=t \color{grey}\in \mathcal{A F}_{\Sigma}}$

$\small \neg F,~ (F \wedge G), ~(F \vee G),~ (F \supset G) \color{grey}\in \mathcal{A} \mathcal{F}_{\Sigma}$
wenn $\small F, G \in \mathcal{P F}_{\Sigma}$

$\cancel {\small \forall v F,~ \exists v F \color{grey}\in \mathcal{A F}_{\Sigma}}$

Einteilung der Logik

Syntax Prädikatenlogik

Terme @import url("https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css"); TΣ\small \mathcal{T}_{\Sigma}TΣ​﻿

Prädikatenlogische Formeln @import url("https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css"); PFΣ\small \mathcal{P F}_{\Sigma}PFΣ​﻿

Freie vs. gebundene Variable

Variablen-Substitution

Syntax Aussagenlogik

Aussagenlogische Formeln @import url("https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css"); AF\small \mathcal{AF}AF﻿

Terme $\small \mathcal{T}_{\Sigma}$

Prädikatenlogische Formeln $\small \mathcal{P F}_{\Sigma}$

Aussagenlogische Formeln $\small \mathcal{AF}$