Partielle Ordnung < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:17 So 15.12.2013 | | Autor: | rsprsp |
| Aufgabe | Wir betrachten die Menge $X$ aller Wörter der Länge $k$
über dem Alphabet [mm] $\{ 0 , 1 \}$ [/mm] und definieren die Relation als: $xRy$ genau dann, wenn ein [mm] $i\in\{1,...,k\}$ [/mm] existiert, so dass [mm] $x_{i} [/mm] > [mm] y_{i}$ [/mm] und [mm] $x_{j} [/mm] = [mm] y_{j}$ [/mm] für [mm] $j\in\{1,...,k\}\setminus\{i\}$.
[/mm]
1. Warum definiert diese Relation keine partielle Ordnung auf $X$?
2. Wir bilden die reflexive, transitive Hülle von $(X,R)$. Wie lässt sich diese formal beschreiben? Die entstehende partielle Ordnung bezeichnen wir mit $(X,<)$.
3. Zeichnen Sie das Hesse-Diagramm von $(X,<)$ für $k=4$.
4. Bestimmen Sie die Höhe $h$ der partiellen Ordnung $(X,<)$ für $k=4$.
5. Bestimmen Sie die Weite $w$ der partiellen Ordnung $(X,<)$ für $k=4$. |
Hallo, ich brauche Hilfe beim Ansatz dieser Aufgabe. Ich komme nicht drauf was ein Alphabet dieser Art ist und wie es aussieht. Könne mir jemand bei dieser Aufgabe helfen und sie Schritt für Schritt mit mir zu lösen?
|
|
| |
|
Hallo,
> Wir betrachten die Menge [mm]X[/mm] aller Wörter der Länge [mm]k[/mm]
> über dem Alphabet [mm]\{ 0 , 1 \}[/mm] und definieren die Relation
> als: [mm]xRy[/mm] genau dann, wenn ein [mm]i\in\{1,...,k\}[/mm] existiert, so
> dass [mm]x_{i} > y_{i}[/mm] und [mm]x_{j} = y_{j}[/mm] für
> [mm]j\in\{1,...,k\}\setminus\{i\}[/mm].
>
> 1. Warum definiert diese Relation keine partielle Ordnung
> auf [mm]X[/mm]?
> 2. Wir bilden die reflexive, transitive Hülle von [mm](X,R)[/mm].
> Wie lässt sich diese formal beschreiben? Die entstehende
> partielle Ordnung bezeichnen wir mit [mm](X,<)[/mm].
> 3. Zeichnen Sie das Hesse-Diagramm von [mm](X,<)[/mm] für [mm]k=4[/mm].
> 4. Bestimmen Sie die Höhe [mm]h[/mm] der partiellen Ordnung [mm](X,<)[/mm]
> für [mm]k=4[/mm].
> 5. Bestimmen Sie die Weite [mm]w[/mm] der partiellen Ordnung [mm](X,<)[/mm]
> für [mm]k=4[/mm].
>
> Hallo, ich brauche Hilfe beim Ansatz dieser Aufgabe. Ich
> komme nicht drauf was ein Alphabet dieser Art ist und wie
> es aussieht.
Na, hier geht es um die Menge [mm]X[/mm] aller Wörter w mit Länge [mm]k[/mm], die nur aus Nullen und Einsen bestehen.
Also [mm]X=\{w\in\{0,1\}^k\}[/mm]
Etwa sind [mm]\underbrace{010001}_{k \text{Stellen}}[/mm] oder [mm]\underbrace{111111}_{k \text{Stellen}}[/mm] aus [mm]X[/mm]
> Könne mir jemand bei dieser Aufgabe helfen
> und sie Schritt für Schritt mit mir zu lösen?
Fang mal mit a) an...
Hast du verstanden, was die Relation aussagt?
Zwei Wörter [mm]x[/mm] und [mm]y[/mm] aus [mm]X[/mm] stehen genau dann in Relation zueinander, wenn x in einem Eintrag einen größeren Wert als y hat und die Wörter ansonsten gleich sind.
Etwa (wieder für [mm]k=6[/mm]) die Wörter [mm]x=0\red 10111[/mm] und [mm]y=0\red 00111[/mm]
An der Stelle [mm]\red{i=2}[/mm] hat [mm]x[/mm] die Ziffer 1, die größer ist als die Ziffer 0, die an der 2.Stelle von y steht. An allen anderen Stellen stimmen x und y überein. Also $xRy$
Soweit so gut.
Wie ist es mit der Halbordnung. Was würde gelten, wenn [mm]R[/mm] eine Halbordnung wäre?
Drei Bedingungen. Welche sind das?
Die eine geht doch direkt kaputt ...
Kommst du drauf?
Gruß
schachuzipus
|
|
|
|
