Übungen zu Quantoren und Prädikate

17.09.2013, 09:32

un1x

Übungen zu Quantoren und Prädikate

Hi

Gestern wurden wir in das neue Thema "Grundlagen und diskrete Mathematik" eingeführt und haben einige Übungen zu Quantoren und Prädikate bekommen. Leider gibt es zu den Übungen keine Lösungen. So kann ich nicht wirklich kontrollieren, ob das richtig ist was ich da mache.

Ich hoffe ich kann hier einige Aufgaben posten sowie meine Lösungsansätze.

Bemerkung: Alle Quantoren verstehen wir hier als Quantoren über der Menge N (Natuerliche Zahlen). Irgendwie funktioniert der Latex code \N nicht.

Aufgabe1: Es sei E(n) irgend eine Eigenschaft welche auf natuerliche Zahlen zutreffen kann oder nicht. Formalisieren Sie folgende Aussagen:

Es gibt natuerliche Zahlen mit der Eigenschaft E

$\begin{eqnarray*} \exists xE(x) \end{eqnarray*}$

Alle natuerlichen Zahlen haben die Eigenschaft E

$\begin{eqnarray*} \forall xE(x) \end{eqnarray*}$

"Genau eine natuerliche Zahl hat die Eigenschaft E"

$\begin{eqnarray*} \exists x(E(x)\wedge\forall y E(y) \Rightarrow x=y) \end{eqnarray*}$

Mindestens drei natuerliche Zahlen haben die Eigenschaft E

$\begin{eqnarray*} \exists x,y,zE(x,y,z) \end{eqnarray*}$

Es gibt hoechstens zwei natuerliche Zahlen mit der Eigenschaft E
$\begin{eqnarray*} \exists x,y(E(x) \lor E(y)) \wedge \forall z(E(z) \Rightarrow (z=y \lor z=x)) \end{eqnarray*}$

Habe ich vestanden um was es hier geht oder ist das quatsch? geschockt

17.09.2013, 11:14

watcher

Auf diesen Beitrag antworten »

Hallo und auch Willkommen

Zitat:

$\begin{eqnarray*} \exists xE(x) \end{eqnarray*}$

Eher $\begin{eqnarray*} \exists x \in \mathbb N : E(x) \end{eqnarray*}$

Zitat:

Mindestens drei natuerliche Zahlen haben die Eigenschaft E $\begin{eqnarray*} \exists x,y,zE(x,y,z) \end{eqnarray*}$

E(x,y,z) ist doch gar nicht definiert.

Zitat:

Es gibt hoechstens zwei natuerliche Zahlen mit der Eigenschaft E $\begin{eqnarray*} \exists x,y(E(x) \lor E(y)) \wedge \forall z(E(z) \Rightarrow (z=y \lor z=x)) \end{eqnarray*}$

Sicher, dass du dich hier nicht vertippt hast?

Der LaTeX-Code für die natürlichen Zahlen ist \mathbb {N} .
Wie kommst du drauf \N wärs?

17.09.2013, 11:39

un1x

Auf diesen Beitrag antworten »

Hi

Ich dachte mit dem Satz "Alle Quantoren verstehen wir hier als Quantoren über der Menge $\begin{eqnarray*} \mathbb {N} \end{eqnarray*}$ " haette sich das spezifizieren der Menge eruebrigt. Nicht?

Ansonsten muesste ich das noch ueberall eintragen.

Mindestens drei natuerliche Zahlen haben die Eigenschaft

Zitat:

E(x,y,z) ist doch gar nicht definiert.

Hm kann man das nicht so zusammenfassen? Big Laugh

Dann wohl eher

$\begin{eqnarray*} \exists x E(x) \wedge \exists y E(y) \wedge \exists z E(z) \end{eqnarray*}$

Koennte man dies zusammenfassen in:

$\begin{eqnarray*} \exists x,y,z \in \mathbb {N} (E(x) \wedge E(y) \wedge E(z)) \end{eqnarray*}$

Es gibt hoechstens zwei natuerliche Zahlen mit der Eigenschaft

Zitat:

Sicher, dass du dich hier nicht vertippt hast?

Eigentlich nicht verwirrt

Mein Ansatz war:

Es gibt mindestens eine Zahl x oder eine Zahl y (oder beides). Das waere dann min. 2.
Dann sage ich, dass jede weitere Zahl der von x oder y entsprechen muss. Somit sollte ich auf max 2 kommen. oder nicht?

17.09.2013, 11:49

watcher

Auf diesen Beitrag antworten »

Zitat:

Ich dachte mit dem Satz "Alle Quantoren verstehen wir hier als Quantoren über der Menge $\begin{eqnarray*} \mathbb {N} \end{eqnarray*}$ " haette sich das spezifizieren der Menge eruebrigt. Nicht?

Wenn der Satz von der Aufgabenstellung kommt ja. Wenn er von dir kommt, wovon ich nach dem Nachsatz ausging, rate ich davon ab hier so schreibfaul zu sein.

Zitat:

$\begin{eqnarray*} \exists x E(x) \wedge \exists y E(y) \wedge \exists z E(z) \end{eqnarray*}$

Das ist gleichwertig zu $\begin{eqnarray*} \exists x E(x) \end{eqnarray*}$
Du vergisst sicherzustellen, dass x,y,z verschieden sind.

Beim letzten ist das hier das Problem.

Zitat:

$\begin{eqnarray*} (E(x) \lor E(y)) \end{eqnarray*}$

Der Hintergedanke ist schon o.k.

17.09.2013, 12:22

un1x

Auf diesen Beitrag antworten »

Zitat:

Wenn der Satz von der Aufgabenstellung kommt ja.

Ja kommt von der Aufgabenstellung

Zitat:

Du vergisst sicherzustellen, dass x,y,z verschieden sind.

Ach.. logisch. Müsste also so sein
$\begin{eqnarray*} \exists x,y,z(E(x) \wedge E(y) \wedge E(z) \wedge x \not = y \wedge x \not = z \wedge y \not = z) \end{eqnarray*}$

Zitat:

Beim letzten ist das hier das Problem.

Etwa so?

$\begin{eqnarray*} \exists x,y((E(x) \lor E(y)) \lor (E(x) \wedge E(y)) \wedge \forall (E(z) \Rightarrow (z=y \lor z=x)) \end{eqnarray*}$

17.09.2013, 12:29

watcher

Auf diesen Beitrag antworten »

Es ist $\begin{eqnarray*} (A \vee B)\vee (A \wedge B)\equiv A\vee B \end{eqnarray*}$

Wieso verwendest du hier ein oder, wo du doch in der Aufgabe davor ein und verwendet hast? Wo siehst du denn Unterschied zwischen beiden Aufgaben?

17.09.2013, 12:42

un1x

Auf diesen Beitrag antworten »

Der Unterschied ist doch, dass in der oberen Aufgabe die Aufgabenstellung "mindestens 3" heisst und bei der letzten Aufgabe "maximal zwei"

Wenn ich jetzt x UND y nehmen wuerde, heisst es ja min. 2. Es koennten jedoch auch 1 oder keine Zahl vorkommen oder habe ich das falsch verstanden?

17.09.2013, 13:52

watcher

Auf diesen Beitrag antworten »

Und wenn keine Zahl E erfüllt hast du mir der Formel ein Problem.

Ich würde das hier mit $\begin{eqnarray*} \forall x,y,z \end{eqnarray*}$ anfangen.

Anmerkung:
Nur weil Variablen verschieden sind heißt es nicht, dass sie verschiedene Belegungen haben. Es kann durchaus x=y=2 vorkommen.

17.09.2013, 14:00

un1x

Auf diesen Beitrag antworten »

Hm. Stimmt.

Neuer Versuch

$\begin{eqnarray*} \forall x,y,z((E(x) \wedge E(y) \wedge E(z)) \Rightarrow (x=y \lor x=z \lor y=z)) \end{eqnarray*}$

Uebersetzt. Wenn 3 Zahlen existieren muss eine der Zahl die gleiche sein wie einen von den anderen beiden..

17.09.2013, 14:02

watcher

Auf diesen Beitrag antworten »

Ja.

17.09.2013, 14:05

un1x

Auf diesen Beitrag antworten »

DANKE