Kurs:Einführung in die mathematische Logik (Osnabrück 2021)/Arbeitsblatt 11/kontrolle

Übungsaufgaben

Aufgabe Aufgabe 11.1 ändern

Beweise allein aus der Existenzeinführung im Sukzedens und aussagenlogischen Gesetzen die Alleinführung im Antezedens, also dass für eine Variable ${}x$, einen Term ${}t$ und einen Ausdruck ${}\alpha$

$\vdash \forall x\neg \alpha \rightarrow \neg \alpha {\frac {t}{x}}$

eine Tautologie ist.

Aufgabe Aufgabe 11.2 ändern

Zeige

$\vDash \exists x(x=y).$

Aufgabe Referenznummer erstellen

Zeige

$\vdash \exists x(x=y).$

Aufgabe Referenznummer erstellen

Beweise aus der Existenzeinführung im Antezedens die Alleinführung im Sukzedens. Sie besagt, dass man aus

$\vdash \beta \rightarrow \alpha {\frac {y}{x}}$

unter der Bedingung, dass ${}y$ weder in ${}\forall x\alpha$ noch in ${}\beta$ frei vorkommt, auf

$\vdash \beta \rightarrow \forall x\alpha$

schließen kann.

Aufgabe Referenznummer erstellen

Zeige, dass der Ausdruck

${\left(\alpha {\frac {y}{x}}\rightarrow \beta \right)}\rightarrow {\left(\exists x\alpha \rightarrow \beta \right)}$

keine Tautologie ist (auch nicht, wenn ${}y$ weder in ${}\exists x\alpha$ noch in ${}\beta$ frei vorkommt).

Aufgabe Referenznummer erstellen

Es sei ${}\alpha$ ein Ausdruck in einer Sprache ${}L^{S}$ erster Stufe. Zeige, dass

$\alpha \leftrightarrow \forall x\alpha$

keine Tautologie ist.

Aufgabe * Aufgabe 11.7 ändern

Zeige, dass mit

$\vdash \alpha \rightarrow \beta$

auch

$\vdash \forall x\alpha \rightarrow \forall x\beta$

gilt.

Aufgabe Aufgabe 11.8 ändern

Zeige, dass in der Prädikatenlogik die Alleinführung im Antezedens ableitbar ist, also dass für eine Variable ${}x$, einen Term ${}t$ und einen Ausdruck ${}\alpha$

$\vdash \forall x\alpha \rightarrow \alpha {\frac {t}{x}}$

gilt.

Aufgabe * Aufgabe 11.9 ändern

Zeige

$\vdash \forall x\alpha \wedge \forall x\beta \rightarrow \forall x{\left(\alpha \wedge \beta \right)}.$

Aufgabe * Aufgabe 11.10 ändern

Zeige

$\vdash \forall x{\left(\alpha \wedge \beta \right)}\rightarrow \forall x\alpha \wedge \forall x\beta .$

Aufgabe Aufgabe 11.11 ändern

a) Zeige

$\vdash \exists x(\alpha \wedge \beta )\rightarrow \exists x\alpha \wedge \exists x\beta .$

b) Zeige, dass

$\exists x\alpha \wedge \exists x\beta \rightarrow \exists x(\alpha \wedge \beta )$

keine Tautologie ist.

Aufgabe Aufgabe 11.12 ändern

Es sei ${}S$ ein erststufiges Symbolalphabet und ${}f\in S$ ein ${}n$-stelliges Funktionssymbol. Erstelle eine Ableitung für den Ausdruck

$\exists y{\left({\left(fx_{1}{\ldots }x_{n}=y\right)}\wedge \forall z{\left({\left(fx_{1}{\ldots }x_{n}=z\right)}\rightarrow y=z\right)}\right)}.$

Aufgabe * Referenznummer erstellen

Es seien ${}A,B,C$ einstellige Relationssymbole. Zeige, dass der Modus Barbara, also die Aussage

$(\forall x(Ax\rightarrow Bx)\wedge \forall x(Bx\rightarrow Cx))\rightarrow (\forall x(Ax\rightarrow Cx))$

im Prädikatenkalkül ableitbar ist.

Aufgabe * Referenznummer erstellen

Es seien ${}A,B,C$ einstellige Relationssymbole. Zeige, dass der Modus Darii, also die Aussage

$(\forall x(Ax\rightarrow Bx)\wedge \exists x(Ax\wedge Cx))\rightarrow (\exists x(Bx\wedge Cx))$

im Prädikatenkalkül ableitbar ist.

Aufgabe Referenznummer erstellen

Im Kalkül der Prädikatenlogik sei ${}\vdash \alpha \rightarrow \beta$ ableitbar. Zeige, dass dann auch

$\vdash \exists x\alpha \rightarrow \exists x\beta$

ableitbar ist.

Aufgabe Referenznummer erstellen

Zeige, dass in der Prädikatenlogik

$\vdash \exists x\alpha \leftrightarrow \exists x\neg \neg \alpha$

ableitbar ist.

Aufgabe * Referenznummer erstellen

Es seien ${}x,y,u,v$ Variablen und ${}\Gamma =\{\forall x\forall y{\left(x=y\right)}\}$ und ${}\Delta =\{x=y\}$.

1. Zeige (ohne Bezug auf den Vollständigkeitssatz) ${}\Gamma \vdash u=v$.
2. Charakterisiere die Modelle ${}M$ mit ${}M\vDash \Gamma$.
3. Zeige ${}\Delta \not \vdash u=v$.

Aufgabe * Referenznummer erstellen

Es sei ${}G$ ein dreistelliges Relationssymbol und ${}L$ die zugehörige prädikatenlogische Sprache. Es sei ${}I$ die Interpretation, bei der die Grundmenge die euklidische Ebene ist und ${}G$ durch die dreistellige Relation interpretiert wird, bei der ${}G(A,B,C)$ zutrifft, wenn die Punkte ${}A,B,C$ auf einer Geraden liegen.

1. Zeige ${}I\vDash Gxyz\leftrightarrow Gyxz$.
2. Zeige, dass im Allgemeinen nicht ${}I\vDash \forall x\forall y\forall z{\left(Gxyz\rightarrow Gxyu\right)}$ gelten muss.
3. Es sei ${}\Gamma =\{\forall x\forall y\forall z{\left(Gxyz\leftrightarrow Gyxz\right)},\,\forall x\forall y\forall z{\left(Gxyz\leftrightarrow Gxzy\right)}\}$. Erstelle eine Ableitung für ${}\Gamma \vdash Gxyz\leftrightarrow Gyzx$.
4. Zeige, dass der Ausdruck ${}Gxyz\wedge Gxyu$ bei der gegebenen Interpretation nicht bedeutet, dass die die freien Variablen ${}x,y,z,u$ belegenden Punkte auf einer Geraden liegen.
5. Formuliere einen Ausdruck aus ${}L$ in vier freien Variablen, der bei der gegebenen Interpretation besagt, dass die die freien Variablen belegenden Punkte auf einer Geraden liegen.

Die beiden folgenden Aufgaben sind vermutlich mühselig.

Aufgabe Referenznummer erstellen

Man gebe einen formalen Beweis für die Aussage, dass die Hintereinanderschaltung von zwei surjektiven Abbildungen auf einer Menge wieder surjektiv ist.

Aufgabe Referenznummer erstellen

Man gebe einen formalen Beweis für die Aussage, dass die Hintereinanderschaltung von zwei injektiven Abbildungen auf einer Menge wieder injektiv ist.

Aufgabe Referenznummer erstellen

Es sei ${}\Gamma$ eine Ausdrucksmenge aus einer Sprache erster Stufe und ${}\alpha$ ein weiterer Ausdruck. Es sei ${}\alpha$ nicht aus ${}\Gamma$ ableitbar. Zeige, dass man aus ${}\Gamma \cup \{\neg \alpha \}$ keinen Widerspruch (also keinen Ausdruck der Form ${}\beta \wedge \neg \beta$) ableiten kann.

Aufgabe Aufgabe 11.22 ändern

Begründe die folgenden Ableitungsregeln (es seien ${}s,t$ Terme, ${}\alpha ,\beta$ Ausdrücke und ${}\Gamma$ eine Ausdrucksmenge).

1. Wenn ${}\Gamma \vdash s=t$, dann ist auch ${}\Gamma \vdash \alpha {\frac {s}{x}}\rightarrow \alpha {\frac {t}{x}}$,
2. Wenn ${}\Gamma \vdash \alpha {\frac {t}{x}}$, dann ist auch ${}\Gamma \vdash \exists x\alpha$,
3. Wenn ${}\Gamma \vdash \alpha {\frac {y}{x}}\rightarrow \beta$, dann ist auch ${}\Gamma \vdash \exists x\alpha \rightarrow \beta$, unter der Bedingung, dass ${}y$ nicht frei in ${}\Gamma ,\exists x\alpha ,\beta$ vorkommt.

Aufgaben zum Abgeben

Aufgabe (2 Punkte)Referenznummer erstellen

Es sei ${}\alpha \in L^{S}$. Zeige die Ableitbarkeit

$\vdash \exists x\exists x\alpha \leftrightarrow \exists x\alpha .$

Aufgabe (4 Punkte)Aufgabe 11.24 ändern

Es sei ${}\alpha \in L^{S}$. Zeige die Ableitbarkeit

$\vdash \exists x\forall y\alpha \rightarrow \forall y\exists x\alpha .$

Zeige, dass

$\forall y\exists x\alpha \rightarrow \exists x\forall y\alpha$

nicht ableitbar ist.

Aufgabe (4 Punkte)Referenznummer erstellen

Formuliere mit dem zweistelligen Funktionssymbol ${}\cdot$ die Aussage, dass wenn eine Zahl ${}a$ die Zahl ${}b$ teilt und ${}b$ die Zahl ${}c$ teilt, dass dann ${}a$ auch ${}c$ teilt.

Erstelle eine Ableitung für diese Aussage.

Aufgabe (3 Punkte)Referenznummer erstellen

Zeige, dass es eine Ausdrucksmenge ${}\Gamma$ mit der Eigenschaft gibt, dass für jede Interpretation ${}I$ genau dann ${}I\vDash \Gamma$ gilt, wenn die Grundmenge der Interpretation unendlich ist.