Aussage/Definition < Aussagenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Definition: Ein Graph mit n Knoten heißt "vollständig" wenn es zu je zwei Knoten stets genau eine verbindende Kante gibt.
Geben Sie ein Kriterium an, das äquivalent dazu ist, dass ein Graph mit n Knoten nicht vollständig ist. |
Hallo,
Ich würde die Aufgabe gerne Schritt für Schritt möglichst systematisch Lösen. Das bedeutet, dass ich (Teil)-Aussagen formuliere, zusammensetze und dann negiere.
Ich könnte auch direkt die Endlösung hinschreiben ala
Ein Graph mit n Knoten ist nicht vollständig [mm] \gdw [/mm] ......
Jedoch macht man so leichter Fehler und zudem gäbe es in Klausuren für solch knappe Lösungen eventuell Punktabzug.
Definitionen sind doch generell Äquivalenzen, oder? Ich würde die obige Definition wie folgt umschreiben:
Ein Graph mit n Knoten heißt "vollständig" [mm] \gdw [/mm] Es gibt zu je zwei Knoten stets genau eine verbindende Kante.
Wäre das so schonmal richtig umgeschrieben?
Dann Teilaussagen/Teilaussageformen definieren:
A(x): Ein Graph mit n Knoten heißt "vollständig".
B: Es gibt zu je zwei Knoten stets genau eine verbindende Kante.
Dann gilt:
(Ein Graph mit n Knoten heißt "vollständig" [mm] \gdw [/mm] Es gibt zu je zwei Knoten stets genau eine verbindende Kante. ) [mm] \gdw [/mm] (A(x) [mm] \gdw [/mm] B)
Negation:
[mm] \neg [/mm] (A(x) [mm] \gdw [/mm] B)
[mm] \gdw [/mm] ( [mm] \neg [/mm] A(x) [mm] \gdw \neg [/mm] B )
[mm] \gdw [/mm] (Ein Graph mit n Knoten heißt nicht "vollständig" [mm] \gdw [/mm] Es gibt mindestens zwei Knoten mit mehr als einer verbindenden Kante oder mit keiner verbindenden Kante.)
Ist das richtig so?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo Peeter123,
> Definition: Ein Graph mit n Knoten heißt "vollständig"
> wenn es zu je zwei Knoten stets genau eine verbindende
> Kante gibt.
>
> Geben Sie ein Kriterium an, das äquivalent dazu ist, dass
> ein Graph mit n Knoten nicht vollständig ist.
> Hallo,
>
> Ich würde die Aufgabe gerne Schritt für Schritt
> möglichst systematisch Lösen. Das bedeutet, dass ich
> (Teil)-Aussagen formuliere, zusammensetze und dann
> negiere.
Du suchst doch ein Kriterium, mit dem du die Vollständigkeit eines Graphen beschreiben kann. Und das willst du dann negieren.
> Ich könnte auch direkt die Endlösung hinschreiben ala
> Ein Graph mit n Knoten ist nicht vollständig [mm]\gdw[/mm] ......
> Jedoch macht man so leichter Fehler und zudem gäbe es in
> Klausuren für solch knappe Lösungen eventuell
> Punktabzug.
>
>
>
>
> Definitionen sind doch generell Äquivalenzen, oder?
Nein
> Ich
> würde die obige Definition wie folgt umschreiben:
>
> Ein Graph mit n Knoten heißt "vollständig" [mm]\gdw[/mm] Es gibt
> zu je zwei Knoten stets genau eine verbindende Kante.
>
> Wäre das so schonmal richtig umgeschrieben?
>
> Dann Teilaussagen/Teilaussageformen definieren:
>
> A(x): Ein Graph mit n Knoten heißt "vollständig".
> B: Es gibt zu je zwei Knoten stets genau eine verbindende
> Kante.
>
> Dann gilt:
>
> (Ein Graph mit n Knoten heißt "vollständig" [mm]\gdw[/mm] Es gibt
> zu je zwei Knoten stets genau eine verbindende Kante. )
> [mm]\gdw[/mm] (A(x) [mm]\gdw[/mm] B)
>
>
> Negation:
>
> [mm]\neg[/mm] (A(x) [mm]\gdw[/mm] B)
> [mm]\gdw[/mm] ( [mm]\neg[/mm] A(x) [mm]\gdw \neg[/mm] B )
> [mm]\gdw[/mm] (Ein Graph mit n Knoten heißt nicht "vollständig"
> [mm]\gdw[/mm] Es gibt mindestens zwei Knoten mit mehr als einer
> verbindenden Kante oder mit keiner verbindenden Kante.)
Das hast du formal richtig negiert, aber du suchst doch für einen Graphen mit n Knoten eine Charakterisierung, die äquivalent zu der in der Definition gegebenen ist und die du nachher negierst ...
Überlege mal, wieviele Kanten ein vollst. Graph mit n Knoten hat und wie du ihn dadurch charakterisieren kannst ...
Ein Graph mit n Knoten ist genau dann vollst., wenn er **** Kanten hat.
Also ist ein Graph mit n Knoten nicht vollst., genau dann wenn .......
>
>
> Ist das richtig so?
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:58 Mo 29.10.2012 | | Autor: | tobit09 |
Hallo schachuzipus,
> Das hast du formal richtig negiert, aber du suchst doch
> für einen Graphen mit n Knoten eine Charakterisierung, die
> äquivalent zu der in der Definition gegebenen ist und die
> du nachher negierst ...
>
> Überlege mal, wieviele Kanten ein vollst. Graph mit n
> Knoten hat und wie du ihn dadurch charakterisieren kannst
> ...
Das funktioniert nur, wenn Mehrfachkanten ausgeschlossen sind. Das scheint beim Fragesteller nicht der Fall zu sein.
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:14 Mo 29.10.2012 | | Autor: | tobit09 |
Hallo Peeter123!
> Definitionen sind doch generell Äquivalenzen, oder?
Wenn es in einer Definition lautet
"... heißt ..., wenn ... .",
ist damit
"... heißt ... genau dann, wenn ... ."
gemeint. War das das, was du meintest?
> Ich
> würde die obige Definition wie folgt umschreiben:
>
> Ein Graph mit n Knoten heißt "vollständig" [mm]\gdw[/mm] Es gibt
> zu je zwei Knoten stets genau eine verbindende Kante.
>
> Wäre das so schonmal richtig umgeschrieben?
Ja.
> Dann Teilaussagen/Teilaussageformen definieren:
>
> A(x): Ein Graph mit n Knoten heißt "vollständig".
Gemeint offensichtlich:
x sei ein Graph mit n Knoten.
A(x) bezeichne die Aussage "x ist vollständig.".
> B: Es gibt zu je zwei Knoten stets genau eine verbindende
> Kante.
B(x) bezeichne die Aussage "In x gibt es zu je zwei Kanten stets genau eine verbindende Kante."
> Dann gilt:
>
> (Ein Graph mit n Knoten heißt "vollständig" [mm]\gdw[/mm] Es gibt
> zu je zwei Knoten stets genau eine verbindende Kante. )
> [mm]\gdw[/mm] (A(x) [mm]\gdw[/mm] B)
>
>
> Negation:
>
> [mm]\neg[/mm] (A(x) [mm]\gdw[/mm] B)
Das ist Blödsinn. Du sollst nicht die [mm] $A(x)\gdw [/mm] B(x)$ negieren, sondern (wahlweise) A(x) oder B(x).
> [mm]\gdw[/mm] ( [mm]\neg[/mm] A(x) [mm]\gdw \neg[/mm] B )
Dies ist äquivalent zu [mm] $A(x)\gdw [/mm] B(x)$.
> [mm]\gdw[/mm] (Ein Graph mit n Knoten heißt nicht "vollständig"
> [mm]\gdw[/mm] Es gibt mindestens zwei Knoten mit mehr als einer
> verbindenden Kante oder mit keiner verbindenden Kante.)
Die letzte Zeile beinhaltet die korrekte Negation von "x vollständig".
Du hast unnützen Formalkram betrieben, bei dem du dann auch Fehler eingebaut hast. Zu negieren ist lediglich die Aussage $B(x)$. Das hast du intuitiv richtig gemacht. Willst du die Negation formaler durchführen, müsstest du zunächst die Aussage B(x) formalisieren.
Viele Grüße
Tobias
|
|
|
|
![[bonk]](/images/smileys/bonk.gif "[bonk]"){kind=small}
, steht aber echt nirgends.
![[konfus]](/images/smileys/konfus.gif "[konfus]"){kind=small}
![[sorry]](/images/smileys/sorry.gif "[sorry]"){kind=small}
, meinen Beitrag kannst du vergessen ![[verlegen]](/images/smileys/verlegen.gif "[verlegen]"){kind=small}
