0 Daumen
547 Aufrufe

Aufgabe:

20220716_205018.jpg

Text erkannt:

Wir betrachten die Signatur \( \Sigma \) der Arithmetik mit zwei Konstanten 0 und 1 , zwei zweistelligen Funktionensymbolen \( + \) und . einem zweistelligen Prädikatensymbol \( < \). Viele Aussagen über natürliche Zahlen (also die \( \Sigma \)-Struktur mit Trägermenge \( \mathbb{N} \) und der üblichen Interpretation der Symbolc in \( \Sigma \) ) lasscn sich als prädikatcnlogische Formcln übcr \( \Sigma \) ausdrückcn.

Beispiel: Der Aussage " \( x \) ist eine gerade Zahl"" entspricht die Formel \( \exists y:(x=y+y) \) mit einer freien Variable \( x \).
Transformieren Sie die folgenden Aussagen in prädikatenlogische Formelı über \( \Sigma \) :
(a) [3 PUNKTE] " \( x \) teilt \( y+1 \)."
(b) [4 PUNKTE] " \( x \) ist eine Primzahl."
(c) [4 PUNKTE] "Es gibt unendlich viele Primzahlen",
(d) [5 PUNKTE] "'Jede gerade Zahl \( \geq 4 \) läßt sich als Summe zweier Primzahlen darstellen.",
(e) [5 PUNKTE] "'Alle Zahlen mit ungeradem Quadrat sind ungerade.",

20220716_205106.jpg

Text erkannt:

a) \( x \mid y+1 \)
b) \( \forall y:(y<x)(y=1 \wedge \) y \( x \times x) \)
c) \( \forall x: \exists y((z<y)(z-1 \wedge z X y)) \wedge(y>x) \)
d) \( \forall x \geqslant 4((\exists y \mid x=y+y) \Rightarrow(\exists z, w \mid x=z+w \wedge z, w \in P) \)
\( P \) is eine Menge von Primzahlen.
e) \( \forall x \mid x^{2} \in 0 \Rightarrow x \in 0 \), wobei 0 eine Menge aller ungeraden zahlen ist.



Problem/Ansatz:

Hallo,

Ich habe die folgende Aufgabe bekommen und darunter ist meine Lösungsvorschlag. Können Sie bitte einmal überprüfen, ob das richtig oder falsch? Wenn die so falsch ist, können Sie mir bitte weiter helfen? Ich brauche eure Hilfe unbedingt! Diese Frage ist sehr wichtig für mich!! Die Frage ist vom Logik

Avatar von

Bitte bitte helfen Sie mir bei dieser Aufgabe. Das ist sehr wichtig für mich

2 Antworten

0 Daumen
 
Beste Antwort
a) \( x \mid y+1 \)

Das Relationssysmbol \(\mid\) ist nicht teil der Signatur. Es darf deshalb nicht in der Formel vorkommen.

Tipp. Greife auf die Definition von \(a\mid b\) zurück.

b) \( \forall y:(y<x)(y=1 \wedge \) y \( x \times x) \)

Es fehlen Junktoren.

Das \(\times\) soll wohl ein \(\nmid\) sein. Für \(\nmid\) gilt entsprechendes wie für \(\mid\).

c) \( \forall x: \exists y((z<y)(z-1 \wedge z X y)) \wedge(y>x) \)

Es fehlen Junktoren.

Für \(X\) gilt das Gleiche wie für \(\mid\) und \(\nmid\).

d) \( \forall x \geqslant 4((\exists y \mid x=y+y) \Rightarrow(\exists z, w \mid x=z+w \wedge z, w \in P) \)

Das \(\mid\) soll wohl den Teil \(\exists y\) vom Teil \(x = y+y\) trennen. Im Beispiel wurde dafür der Doppelpunkt verwendet.

Formulierungen wie \(\forall x \geqslant 4\) sind prädikatenlogische Umgangssprache. Für ein einstelliges Prädikatssymbol \(P\) und eine Formel \(\varphi\) ist

        \(\forall x\in P:\ \varphi\)

eine abkürzende Schreibweise für

        \(\forall x:\ \left(x\in P\to \varphi\right) \)

und

      \(\exists x\in P:\ \varphi\)

eine abkürzende Schreibweise für

        \(\exists x:\ \left(x\in P \wedge \varphi\right)\).

Überprüfe ob du solche Abkürzungen verwenden darfst.

Unabhängig davon sind weder \(\geqslant\), noch \(4\), noch \(P\) Teil der Signatur und es gilt das Gleiche wie für \(\mid\), \(\nmid\) und \(X\).

\(\exists z,w\) ist eine abkürzende Schreibweise für \(\exists z\exists w\). Überprüfe ob du solche Abkürzungen verwenden darfst.

\(z, w \in P\) darfst du höchstwahrscheinlich nicht so verwenden, auch wenn es in der mathematischen Umgangssprache üblich ist. Du dürftest \(z\in P \wedge w\in P\) verwenden, wenn \(P\) Teil der Signatur wäre.

e) \( \forall x \mid x^{2} \in 0 \Rightarrow x \in 0 \), wobei 0 eine Menge aller ungeraden zahlen ist.

\(\square^2\) und \(O\) sind nicht Teil der Signatur.

Avatar von 105 k 🚀
  • a) \(\exists z:z\cdot x=y+1\)
  • b) \(\neg x=1\wedge\forall y:\left(y=1\vee y=x\vee\neg\exists z:\ z\cdot y=x\right)\)
  • c) \(\forall x\exists y:\left(x<y\wedge\neg y=1\wedge\forall z:\left(z=1\vee z=y\vee\neg\exists w:\ w\cdot z=y\right)\right)\)
  • d) \(\forall x:\left(\left(1+1+1<x\wedge\neg\exists w:\ w\cdot\left(1+1\right)=x\right)\to\exists y\exists z:y\cdot y+z\cdot z=x\right)\)
  • e) \(\forall x:\left(\left(\neg\exists y:y\cdot\left(1+1\right)=x\cdot x\right)\to\left(\neg\exists y:\ y\cdot\left(1+1\right)=x\right)\right)\)
+1 Daumen

Wenn es erlaubt ist, mit Hilfe der gegebenen Signatur

neue Prädikate einzuführen, würde ich so vorgehen:

Einführung von "x teilt y":

\(T(x,y)\stackrel{def}{\iff}\exists k: \;  y=x\cdot k\)

(a) \(T(x,y+1)\)

(b) \(\forall a,b:\; T(x,ab)\Rightarrow (T(x,a) \vee T(x,b))\)

Einführung von "ist Primzahl":

\(P(x)\stackrel{def}{\iff}\forall a,b:\; T(x,ab)\Rightarrow (T(x,a) \vee T(x,b))\)

(c) \(\forall x\; \exists y: \; (x<y\wedge P(y))\)

(e) \(\forall x:\; \lnot T(2,x^2)\Rightarrow \lnot T(2,x)\)

Alternativ könnte man auch die Kontraposition nehmen:

\(\forall x:\; T(2,x)\Rightarrow T(2,x^2)\).

Avatar von 29 k

Kannst du mir auch möglicherweise teil e auch zeigen? Da habe ich auch schwierigkeiten!

Habe (e) ergänzt.

Dankeschön für deine Hilfe

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community