Kurs:Einführung in die mathematische Logik (Osnabrück 2021)/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
{}
{
Es sei $S$ ein
\definitionsverweis {Symbolalphabet}{}{}
einer
\definitionsverweis {prädikatenlogischen Sprache}{}{}
mit einer leeren Variablenmenge. Zeige, dass man für Terme $s,t$ im Allgemeinen
\mathl{s=t \rightarrow t= s}{} nicht ableiten kann.
}
{} {}
\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}
\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?
}
{} {}