Mengenlehre/Aussagenlogik

Neue Frage »

Jack159 Auf diesen Beitrag antworten »
Mengenlehre/Aussagenlogik
Ich komme bei folgender Aufgabe nicht weiter:

Def.: 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, wann ein Graph mit n Knoten nicht vollständig ist.

Soll man das jetzt so Aussagenlogik-mäßig aufschreiben? Unser Prof gibt uns da nicht viel Hilfestellung bei.
Falls ja, dann würde ich die Aussage oben erstmal etwas umschreiben:


"Wenn es zu je zwei Knoten stets genau eine verbindende Kante gibt, dann heißt der Graph mit n Knoten "vollständig".

Die Negation (und somit die Lösung der Aufgabe) dazu wäre dann:

Es gibt zu je zwei Knoten stets genau eine verbindende Kante und der Graph mit n Knoten heißt nicht "vollständig".


Wäre das so richtig?
Abakus Auf diesen Beitrag antworten »
RE: Mengenlehre/Aussagenlogik
Zitat:
Original von Jack159
Es gibt zu je zwei Knoten stets genau eine verbindende Kante und der Graph mit n Knoten heißt nicht "vollständig".


Wäre das so richtig?


Hallo!

Das ist noch nicht die Negation.

Abakus smile
Jack159 Auf diesen Beitrag antworten »
RE: Mengenlehre/Aussagenlogik
Zitat:
Original von Abakus
Zitat:
Original von Jack159
Es gibt zu je zwei Knoten stets genau eine verbindende Kante und der Graph mit n Knoten heißt nicht "vollständig".


Wäre das so richtig?


Hallo!

Das ist noch nicht die Negation.

Abakus smile

Hmmm vielleicht doch quantifizierung?

Für alle vollständige Graphen mit n Knoten gilt: Wenn es zu je zwei Knoten stets genau eine verbindende Kante gibt, dann heißt der Graph mit n Knoten "vollständig.

Negation dazu:

Für (mind) einen vollständigen Graphen mit n Knoten gilt: Es gibt zu je zwei Knoten stets genau eine verbindende Kante und der Graph mit n Knoten heißt nicht "vollständig".

So richtig?
Aber bei der Aufgabe geht es auf jedenfall darum, die Aussageform dort zu negieren?
Abakus Auf diesen Beitrag antworten »
RE: Mengenlehre/Aussagenlogik
Zitat:
Original von Jack159
Für alle vollständige Graphen mit n Knoten gilt: Wenn es zu je zwei Knoten stets genau eine verbindende Kante gibt, dann heißt der Graph mit n Knoten "vollständig.


Alle vollständigen Graphen sind vollständig, wenn... überlege selbst, wieso dies keinen Sinn macht (das erste vollständig muss weg).

Ein Beispiel?

Alle Vögel können fliegen.

oder auch nicht:

Es gibt (mindestens) einen Vogel, der nicht fliegen kann.

Denken wir mal an Strauße oder sowas. Lässt sich das auf die Aufgabe anwenden?

Abakus smile
Jack159 Auf diesen Beitrag antworten »
RE: Mengenlehre/Aussagenlogik
Zitat:
Original von Abakus
Zitat:
Original von Jack159
Für alle vollständige Graphen mit n Knoten gilt: Wenn es zu je zwei Knoten stets genau eine verbindende Kante gibt, dann heißt der Graph mit n Knoten "vollständig.


Alle vollständigen Graphen sind vollständig, wenn... überlege selbst, wieso dies keinen Sinn macht (das erste vollständig muss weg).

Ein Beispiel?

Alle Vögel können fliegen.

oder auch nicht:

Es gibt (mindestens) einen Vogel, der nicht fliegen kann.

Denken wir mal an Strauße oder sowas. Lässt sich das auf die Aufgabe anwenden?

Abakus smile


Die Quantifizierungen kenne ich so:

Für alle x gilt:.....
bzw.
Für (mind) ein x gilt:....

Auf die Aufgabe dann bezogen:
Für alle Knoten n gilt: Wenn es zu je zwei Knoten stets genau eine verbindende Kante gibt, dann heißt der Graph "vollständig".

Negierung:
Für (mind) einen Knoten n gilt: Es gibt zu je zwei Knoten stets genau eine verbindende Kante und der Graph mit n Knoten heißt nicht "vollständig".
Abakus Auf diesen Beitrag antworten »
RE: Mengenlehre/Aussagenlogik
Zitat:
Original von Jack159
Für alle Knoten n gilt: Wenn es zu je zwei Knoten stets genau eine verbindende Kante gibt, dann heißt der Graph "vollständig".


Die Formulierung hat ein paar Schwächen: ist n der Name (irgend-) eines Knotens oder sprichst du von n-vielen Knoten? Und was hat das dann mit der wenn... dann... Bedingung zu tun, da kommt n ja gar nicht vor?

Bei einer "für alle"-Aussageform hast du ja ein von der gebundenen Variable abhängiges Prädikat, zB:

Abakus smile
 
 
Jack159 Auf diesen Beitrag antworten »
RE: Mengenlehre/Aussagenlogik
Zitat:
Original von Abakus
Zitat:
Original von Jack159
Für alle Knoten n gilt: Wenn es zu je zwei Knoten stets genau eine verbindende Kante gibt, dann heißt der Graph "vollständig".


Die Formulierung hat ein paar Schwächen: ist n der Name (irgend-) eines Knotens oder sprichst du von n-vielen Knoten? Und was hat das dann mit der wenn... dann... Bedingung zu tun, da kommt n ja gar nicht vor?

Bei einer "für alle"-Aussageform hast du ja ein von der gebundenen Variable abhängiges Prädikat, zB:

Abakus smile

Stimmt auch wieder...

Ist der Satz aus der Aufgabe:
Ein Graph mit n Knoten heißt "vollständig" wenn es zu je zwei Knoten stets genau eine verbindende Kante gibt.
überhaupt eine Aussageform? Eigentlich nicht, der Satz hat zwar eine Variable, aber auch mit Variable lässt sich der Warheitsgehalt prüfen. Somit ist es eine Aussage und keine Aussageform, oder?
Aber dann wäre ich wieder bei der Lösung aus meinem Startpost, was ja auch falsch ist...

Ich weiß nicht mehr weiter unglücklich
Abakus Auf diesen Beitrag antworten »
RE: Mengenlehre/Aussagenlogik
Zitat:
Original von Jack159
Ist der Satz aus der Aufgabe:
Ein Graph mit n Knoten heißt "vollständig" wenn es zu je zwei Knoten stets genau eine verbindende Kante gibt.
überhaupt eine Aussageform? Eigentlich nicht, der Satz hat zwar eine Variable, aber auch mit Variable lässt sich der Warheitsgehalt prüfen. Somit ist es eine Aussage und keine Aussageform, oder?


Das ist eine Definition. Hänge dich mal nicht zu sehr an Formalien auf, denke einfach logisch. Viel mehr als das obige Beispiel mit den Vögeln brauchst du für die Lösung nicht.

Abakus smile
Jack159 Auf diesen Beitrag antworten »
RE: Mengenlehre/Aussagenlogik
Zitat:
Original von Abakus
Zitat:
Original von Jack159
Ist der Satz aus der Aufgabe:
Ein Graph mit n Knoten heißt "vollständig" wenn es zu je zwei Knoten stets genau eine verbindende Kante gibt.
überhaupt eine Aussageform? Eigentlich nicht, der Satz hat zwar eine Variable, aber auch mit Variable lässt sich der Warheitsgehalt prüfen. Somit ist es eine Aussage und keine Aussageform, oder?


Das ist eine Definition. Hänge dich mal nicht zu sehr an Formalien auf, denke einfach logisch. Viel mehr als das obige Beispiel mit den Vögeln brauchst du für die Lösung nicht.

Abakus smile


Die Definition etwas umgeschrieben:
Für alle Graphen mit n Knoten gilt: Alle Graphen sind vollständig, wenn es zu je zwei Knoten stets genau eine verbindende Kante gibt.

Negiert:
Für mind einen Graphen mit n Knoten gilt: Alle Graphen sind vollständig und haben nicht zu je zwei Knoten stets genau eine verbindende Kante.
Abakus Auf diesen Beitrag antworten »
RE: Mengenlehre/Aussagenlogik
Zitat:
Original von Jack159
Die Definition etwas umgeschrieben:
Für alle Graphen mit n Knoten gilt: Alle Graphen sind vollständig, wenn es zu je zwei Knoten stets genau eine verbindende Kante gibt.


Jetzt bedeutet es etwas völlig anderes und ist auch wenig sinnvoll, denn wir wissen ja, dass nicht alle Graphen vollständig sind.

Überlege einmal, worauf sich der Allquantor (wenn wir ihn denn benutzen wollen) in der ursprünglichen Definition bezieht: ein Graph heißt vollständig, wenn für alle Paare von verschiedenen Knoten (u, v) gilt, dass diese durch eine Kante verbunden sind...

Der Quantor bezieht sich demnach auf Knotenpaare mit einer bestimmten Eigenschaft...

Insgesamt gilt: eine möglichst einfache Formulierung gewinnt.

Abakus smile
Jack159 Auf diesen Beitrag antworten »
RE: Mengenlehre/Aussagenlogik
Zitat:
Original von Abakus
Zitat:
Original von Jack159
Die Definition etwas umgeschrieben:
Für alle Graphen mit n Knoten gilt: Alle Graphen sind vollständig, wenn es zu je zwei Knoten stets genau eine verbindende Kante gibt.


Jetzt bedeutet es etwas völlig anderes und ist auch wenig sinnvoll, denn wir wissen ja, dass nicht alle Graphen vollständig sind.

Überlege einmal, worauf sich der Allquantor (wenn wir ihn denn benutzen wollen) in der ursprünglichen Definition bezieht: ein Graph heißt vollständig, wenn für alle Paare von verschiedenen Knoten (u, v) gilt, dass diese durch eine Kante verbunden sind...

Der Quantor bezieht sich demnach auf Knotenpaare mit einer bestimmten Eigenschaft...

Insgesamt gilt: eine möglichst einfache Formulierung gewinnt.

Abakus smile

Die Knotenpaare müssen die EIgenschaft haben, dass sie jeweils genau eine verbindene Kante besitzen.

Negation:
Es gibt zu je zwei Knoten stets genau eine verbindende Kante und der Graph mit n Knoten heißt nicht vollständig.

Hatte ich schon im Startpost ....... unglücklich unglücklich

Sorry, aber ich komm einfach nicht drauf -.-

Wo liegt jetzt überhaupt der Unterschied, zwischen einer Aussage(form) und einer Definition im Bezug auf Aussagenlogik?
Abakus Auf diesen Beitrag antworten »
RE: Mengenlehre/Aussagenlogik
Zitat:
Original von Abakus
Ein Beispiel?

Alle Vögel können fliegen.

oder auch nicht:

Es gibt (mindestens) einen Vogel, der nicht fliegen kann.


Schaue nochmal hier, da steckt alles drin, was du brauchst.

Eine Definition führt nur einen Begriff/eine Vokabel ein; eine Aussage dagegen ist richtig oder falsch.

Abakus smile
Jack159 Auf diesen Beitrag antworten »
RE: Mengenlehre/Aussagenlogik
Zitat:
Original von Abakus
Zitat:
Original von Abakus
Ein Beispiel?

Alle Vögel können fliegen.

oder auch nicht:

Es gibt (mindestens) einen Vogel, der nicht fliegen kann.


Schaue nochmal hier, da steckt alles drin, was du brauchst.

Eine Definition führt nur einen Begriff/eine Vokabel ein; eine Aussage dagegen ist richtig oder falsch.

Abakus smile


Nächster Versuch:

Für einen Graph mit n Knoten gilt: Der Graph ist vollständig, wenn er zu je zwei Knoten stets genau eine verbindende Kante besitzt.

Negation:

Für alle Graphen mit n Knoten gilt: Der Graph ist vollständig und ist nicht im besitz einer verbindenen Kante zu je zwei Knoten.

Das problem besteht darin, dass ich es nicht hinbekomme, die Definition in eine Aussage(form) zu verwandeln (Finde die Definition aus der Aufgabe auch recht kompliziert).
Aber vielleicht ist diese Lösung diesmal richtig^^
Pavel Auf diesen Beitrag antworten »
RE: Mengenlehre/Aussagenlogik
So, ich versuche mal, hier ein bisschen zu helfen.

Die Definition eines vollständigen Graphen und die Aufgabe lauten:

Zitat:
Def.: 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, wann ein Graph mit n Knoten nicht vollständig ist.

Als erstes musst du dir klar machen, dass Definitionen "genau dann, wenn" Aussagen sind. Was also in der Definition steht, ist genau genommen:

"Ein Graph mit n Knoten heißt genau dann "vollständig", wenn es zu je zwei Knoten stets genau eine verbindende Kante gibt."

Anders geschrieben:

Sei G ein Graph. Dann gilt:



Willst du nun wissen, wann ein Graph nicht vollständig ist, dann muss ja auch genau das Gegenteil von der Aussage, die einen vollständigen Graphen charakterisiert, gelten.

Anders geschrieben:



Von daher sind deine Versuche, die so wie "Für einen Graphen mit n Knoten gilt" oder "Für alle Graphen mit n Knoten gilt" anfangen, sinnlos.
Ein Graph ist genau dann nicht vollständig, wenn das Gegenteil von "Es gibt zu je zwei Knoten von G stets genau eine verbindende Kante" gilt. Bilde also einfach diese Negation und schon weißt du, wann ein Graph nicht vollständig ist, was herauszufinden ja die Aufgabe ist.

MfG, Pavel
Jack159 Auf diesen Beitrag antworten »
RE: Mengenlehre/Aussagenlogik
Zitat:
Original von Pavel
So, ich versuche mal, hier ein bisschen zu helfen.

Die Definition eines vollständigen Graphen und die Aufgabe lauten:

Zitat:
Def.: 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, wann ein Graph mit n Knoten nicht vollständig ist.

Als erstes musst du dir klar machen, dass Definitionen "genau dann, wenn" Aussagen sind. Was also in der Definition steht, ist genau genommen:

"Ein Graph mit n Knoten heißt genau dann "vollständig", wenn es zu je zwei Knoten stets genau eine verbindende Kante gibt."

Anders geschrieben:

Sei G ein Graph. Dann gilt:



Willst du nun wissen, wann ein Graph nicht vollständig ist, dann muss ja auch genau das Gegenteil von der Aussage, die einen vollständigen Graphen charakterisiert, gelten.

Anders geschrieben:



Von daher sind deine Versuche, die so wie "Für einen Graphen mit n Knoten gilt" oder "Für alle Graphen mit n Knoten gilt" anfangen, sinnlos.
Ein Graph ist genau dann nicht vollständig, wenn das Gegenteil von "Es gibt zu je zwei Knoten von G stets genau eine verbindende Kante" gilt. Bilde also einfach diese Negation und schon weißt du, wann ein Graph nicht vollständig ist, was herauszufinden ja die Aufgabe ist.

MfG, Pavel

Es wäre also auch richtig, wenn ich schreiben würde:

Ein Graph ist vollständig, wenn es zu je zwei Knoten vom Graphen stets genau eine verbindene Kante gibt."
Negation
Ein Graph ist vollständig und es gibt nicht zu je zwei Knoten vom Graphen stets genau eine verbindene Kante."

Das ich eine Folgerung in eine Äquivalenz umforme, kenne ich nicht. Daher wäre mir der klassische Weg einer Folgerung-Formulierung lieber^^ (Falls das denn hier auch richtig wäre)

Aber danke schonmal für alle Antworten hier im Thread Augenzwinkern
hallo2 Auf diesen Beitrag antworten »

Hallo,

ich habe mir den ganzen Thread jetzt nicht durchgelesen, aber das was ich gelesen habe, war nicht sehr hilfreich. Ich habe die Aufgabe gelöst und möchte meine Lösung vorstellen.


D: Ein Graph mit n Knoten heißt "vollständig", wenn es zu je zwei Knoten stets genau eine verbindende Kante gibt."

Versteckt ist hier in dieser Aussage eine Quantifizierung. Und zwar genau in "zu je zwei Knoten"

Ich teile diese Aussage in Teilaussagen auf:

A: Ein Graph mit n Knoten heißt "vollständig".
B: Es gibt zwei Knoten.
C: Es gibt eine verbindende Kante.

A <=> Für alle Knotenpaare gilt: C

//Hier wähle ich absichtlich das Wort Knotenpaar, da es ja auch im Text immer um zwei Knoten handelt.

Negation: nicht A <=> Für min. ein Knotenpaar gilt: nicht C

Nicht D: Ein Graph mit n Knoten ist nicht vollständig, wenn es min. ein Knotenpaar gibt, für das es keine oder mehrere verbindende Kanten gibt.

Dabei ist in dieser Negierung folgendes wichtig:
ist nicht vollständig: Die Negierung ist keine Definition. Da diese Negierung nicht der einzige Grund dafür sein kann, dass es ein Graph nicht vollständig ist.

keine oder mehrere: Der Fall, dass es mehrere verbindende Kanten auch nicht existieren darf, muss auch ausgeschlossen werden.


Ich hoffe ich konnte helfen ;-)
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »