Kurs:Einführung in die mathematische Logik (Osnabrück 2018)/Arbeitsblatt 10/latex

\setcounter{section}{10}

\zwischenueberschrift{Übungsaufgaben}

\inputaufgabe
{}
{

Ersetze in den folgenden aussagenlogischen Tautologien
\mathdisp {p_1 \text{ durch } \beta_1 \defeq \exists x Rxy,\, p_2 \text{ durch } \beta_2 \defeq \forall u { \left( fu = c \rightarrow Pc \right) } ,\, p_3 \text{ durch } \beta_3 \defeq \exists y \forall x gxz= y,\, p_4 \text{ durch } \beta_4 \defeq Rcu \rightarrow c=u} { . }
\aufzaehlungvier{ $p_1 \wedge p_2 \rightarrow p_1$, }{ ${ \left( p_1 \wedge p_4 \rightarrow \neg p_2 \right) } \wedge { \left( p_1 \wedge p_4 \rightarrow { \left( p_2 \rightarrow p_1 \right) } \right) } \rightarrow { \left( p_1 \wedge p_4 \rightarrow \neg p_2 \wedge { \left( p_2 \rightarrow p_1 \right) } \right) }$, }{ $p_3 \wedge \neg p_3 \rightarrow p_4$, }{ ${ \left( p_1 \wedge p_4 \rightarrow p_3 \right) } \wedge { \left( \neg { \left( p_1 \wedge p_4 \right) } \rightarrow p_3 \right) } \rightarrow p_3$. }

}
{} {}

\inputaufgabe
{}
{

Unterscheide zwischen den verschiedenen Bedeutungen von Gleichheit. \aufzaehlungdrei{Gleichheit von Elementen in einer Menge. }{Gleichheit von Zeichenketten. }{Das Gleichheitssymbol in einer erststufigen Sprache. }

}
{} {}

\inputaufgabe
{}
{

Es sei $S$ ein \definitionsverweis {Symbolalphabet}{}{} einer Sprache erster Stufe. Es seien $S$-\definitionsverweis {Terme}{}{} $s,t$ mit
\mathdisp {\vdash s = t} { }
gegeben. Zeige, dass es sich bei $s$ und $t$ um eine identische Zeichenreihe handelt.

}
{} {}

\inputaufgabe
{}
{

Es sei $S$ ein \definitionsverweis {Symbolalphabet}{}{} und
\mathl{t_1 , \ldots , t_n}{} seien $S$-\definitionsverweis {Terme}{}{.} Zeige die \definitionsverweis {Ableitbarkeit}{}{}
\mathdisp {\vdash t_1=t_2 \wedge t_2=t_3 \wedge \ldots \wedge t_{n-1} =t_n \rightarrow t_1 =t_n} { . }

}
{} {}

\inputaufgabegibtloesung
{}
{

Es seien
\mathl{s_1 , \ldots , s_n, t_1 , \ldots , t_n}{} \definitionsverweis {Terme}{}{} und $f$ ein $n$-stelliges Funktionssymbol. Zeige, dass die \definitionsverweis {Ableitbarkeit}{}{}
\mathdisp {\vdash s_1=t_1 \wedge \ldots \wedge s_n=t_n \rightarrow fs_1 \ldots s_n =ft_1 \ldots t_n} { }
gilt.

}
{} {}

\inputaufgabe
{}
{

Zeige direkt \zusatzklammer {ohne die Verwendung der Ableitungsbeziehung} {} {}, dass die folgenden Ausdrücke \definitionsverweis {allgemeingültig}{}{} sind \zusatzklammer {dabei seien
\mathl{r,s,t,s_1 , \ldots , s_n, t_1 , \ldots , t_n}{} \definitionsverweis {Terme}{}{,} $f$ ein $n$-stelliges Funktionssymbol und $R$ ein $n$-stelliges Relationssymbol} {} {.} \aufzaehlungvier{
\mathdisp {\vDash s=t \rightarrow t=s} { . }
}{
\mathdisp {\vDash r=s \wedge s=t \rightarrow r=t} { . }
}{
\mathdisp {\vDash s_1=t_1 \wedge \ldots \wedge s_n=t_n \rightarrow fs_1 \ldots s_n =ft_1 \ldots t_n} { . }
}{
\mathdisp {\vDash s_1=t_1 \wedge \ldots \wedge s_n=t_n \wedge Rs_1 \ldots s_n \rightarrow Rt_1 \ldots t_n} { . }
}

}
{} {}

\inputaufgabegibtloesung
{}
{

Es seien
\mathl{x_1 , \ldots , x_n}{} Variablen,
\mathl{s_1 , \ldots , s_n, t_1 , \ldots , t_n}{} Terme und
\mathl{\alpha}{} ein Ausdruck in einer \definitionsverweis {prädikatenlogischen Sprache}{}{} $L^S$. Zeige, dass
\mathdisp {s_1=t_1 \wedge \ldots \wedge s_n=t_n \rightarrow { \left( \alpha { \frac{ s_1 , \ldots , s_n }{ x_1 , \ldots , x_n } } \rightarrow \alpha { \frac{ t_1 , \ldots , t_n }{ x_1 , \ldots , x_n } } \right) }} { }
\definitionsverweis {allgemeingültig}{}{} ist.

}
{} {}

\inputaufgabe
{}
{

Es seien $r_1,r_2,s, t$ Terme einer \definitionsverweis {prädikatenlogischen Sprache}{}{} $L^S$ und sei
\mathl{x}{} eine Variable. Zeige durch ein Beispiel, dass
\mathdisp {s=t \rightarrow r_1 { \frac{ s }{ x } } =r_2 { \frac{ t }{ x } }} { }
nicht \definitionsverweis {ableitbar}{}{} sein muss\zusatzfussnote {Die Nicht-Ableitbarkeit wird durch die Angabe eines Modells gezeigt; dies verwendet die Korrektheit des Ableitungskalküls, den wir noch nicht vollständig behandelt haben} {.} {.}

}
{} {}

\inputaufgabegibtloesung
{}
{

Zeige durch ein Beispiel, dass für Terme $r_1,r_2,s$ und eine Variable
\mathl{x}{} einer \definitionsverweis {prädikatenlogischen Sprache}{}{} $L^S$ der Ausdruck
\mathdisp {r_1 = r_2 \rightarrow r_1 { \frac{ s }{ x } } =r_2 { \frac{ s }{ x } }} { }
nicht \definitionsverweis {ableitbar}{}{} sein muss.

}
{} {}

\inputaufgabe
{}
{

Gehört in einem Ausdruck der Form
\mathl{{ \left( x=y \right) } { \frac{ t }{ x } }}{} die Symbolfolge
\mathl{{ \frac{ t }{ x } }}{} zur prädikatenlogischen Sprache? Gehört
\mathl{{ \left( x=y \right) } { \frac{ t }{ x } }}{} dazu?

}
{} {}

\zwischenueberschrift{Aufgaben zum Abgeben}

\inputaufgabe
{2}
{

Es seien $c,d$ Konstanten, es sei $f$ ein zweistelliges Funktionssysmbol und es $R$ ein dreistelliges Relationssymbol. Man erläutere, wie man die prädikatenlogische Tautologie
\mathdisp {{ \left( Rxcfyd \vee z = x \right) } \wedge \neg { \left( Rxcfyd \vee z = x \right) } \rightarrow { \left( \exists x fxc= d \right) }} { }
aus einer aussagenlogischen Tautologie im Sinne von Lemma 10.2 erhält.

}
{} {}

\inputaufgabe
{4}
{

Es seien $r,s_1 , \ldots , s_n, t_1 , \ldots , t_n$ Terme einer \definitionsverweis {prädikatenlogischen Sprache}{}{} $L^S$ und seien
\mathl{x_1 , \ldots , x_n}{} verschiedene Variablen. Zeige durch Induktion über den Aufbau des Termes $r$ die Ableitbarkeit
\mathdisp {\vdash s_1=t_1 \wedge \ldots \wedge s_n=t_n \rightarrow { \left( r { \frac{ s_1 , \ldots , s_n }{ x_1 , \ldots , x_n } } = r { \frac{ t_1 , \ldots , t_n }{ x_1 , \ldots , x_n } } \right) }} { . }

}
{} {}

\inputaufgabe
{4}
{

Es seien $s_1 , \ldots , s_n, t_1 , \ldots , t_n$ Terme einer \definitionsverweis {prädikatenlogischen Sprache}{}{} $L^S$ und seien
\mathl{x_1 , \ldots , x_n}{} verschiedene Variablen. \aufzaehlungzwei {Es sei $R$ ein $k$-stelliges Relationssymbol und
\mathl{r_1 , \ldots ,r_k}{} seien Terme. Zeige die \definitionsverweis {Ableitbarkeit}{}{}
\mathdisp {\vdash s_1=t_1 \wedge \ldots \wedge s_n=t_n \rightarrow { \left( (R r_1 \ldots r_k) { \frac{ s_1 , \ldots , s_n }{ x_1 , \ldots , x_n } } \rightarrow (R r_1 \ldots r_k) { \frac{ t_1 , \ldots , t_n }{ x_1 , \ldots , x_n } } \right) }} { . }
} {Es seien \mathkor {} {r_1} {und} {r_2} {} Terme. Zeige die Ableitbarkeit
\mathdisp {\vdash s_1=t_1 \wedge \ldots \wedge s_n=t_n \rightarrow { \left( r_1 { \frac{ s_1 , \ldots , s_n }{ x_1 , \ldots , x_n } } = r_2 { \frac{ s_1 , \ldots , s_n }{ x_1 , \ldots , x_n } } \rightarrow r_1 { \frac{ t_1 , \ldots , t_n }{ x_1 , \ldots , x_n } } = r_2 { \frac{ t_1 , \ldots , t_n }{ x_1 , \ldots , x_n } } \right) }} { . }
}

}
{} {Tipp: Verwende Aufgabe 10.12}

\inputaufgabe
{4}
{

Es sei $S$ ein \definitionsverweis {Symbolalphabet}{}{,}
\mathl{s_1 , \ldots , s_n,t_1 , \ldots , t_n}{} seien $S$-\definitionsverweis {Terme}{}{,}
\mathl{x_1 , \ldots , x_n}{} verschiedene Variablen und $\alpha$ sei ein $S$-\definitionsverweis {Ausdruck}{}{.} Zeige die Allgemeingültigkeit
\mathdisp {\vDash s_1=t_1 \wedge \ldots \wedge s_n=t_n \rightarrow { \left( \alpha { \frac{ s_1 , \ldots , s_n }{ x_1 , \ldots , x_n } } \rightarrow \alpha { \frac{ t_1 , \ldots , t_n }{ x_1 , \ldots , x_n } } \right) }} { . }

}
{} {}

\inputaufgabe
{4}
{

Zeige durch ein Beispiel, dass bei einem ableitbaren Ausdruck der Form
\mathdisp {\vdash s=t \rightarrow { \left( { \left( \exists z \beta \right) } { \frac{ s }{ x } } \rightarrow { \left( \exists z \beta \right) } { \frac{ t }{ x } } \right) }} { }
die durch die Existenzquantoren gebundenen Variablen \zusatzklammer {nach der durchgeführten Substitution} {} {} nicht übereinstimmen müssen.

}
{} {}

\zwischenueberschrift{Die Aufgabe zum Aufgeben}

Lösungen zu der folgenden Aufgabe direkt an den Dozenten. Bis Ende Mai.

\inputaufgabe
{}
{

Wir betrachten eine Variante des Ableitungskalkül \zusatzklammer {geschrieben $\vdash_V$} {} {} der Aussagenlogik, bei dem die Grundtautologien aus Axiom 3.8 unverändert übernommen werden, bei der aber der \definitionsverweis {Modus ponens}{}{} durch die Schlussregel

Wenn
\mathl{\vdash_V \alpha \wedge (\alpha \rightarrow \beta)}{,} dann ist
\mathl{\vdash_V \beta}{}

ersetzt wird. Stimmen
\mathbed {\vdash} {und}
{\vdash_V} {}
{} {} {} {} überein?

}
{} {}