Aussagenlogik, Allquantor, Existenzquantor und abstrakte Axiome

Es gibt 32 Antworten in diesem Thema. Der letzte Beitrag () ist von Trade.

    Aussagenlogik, Allquantor, Existenzquantor und abstrakte Axiome

    Hi,

    ich besuche zurzeit einen Brückenkurs für Mathematik in der Uni.
    Wie ich leider gestern feststellen musste, hat der Tutor, der die Vorlesung gehalten hat, nicht wirklich einen Leitfaden gehabt, sondern einfach wild mit Begriffen um sich geworfen, ohne das näher zu erläutern bzw. gut zu erklären. Ja, es ist die Universität, das ist mir klar. Aber er wusste teils dann selbst nicht immer, ob das richtig ist, was er sagt und war sich unsicher, nachdem Fragen kamen. Hat dann irgendwelche Beispiele konstruiert, die es auch nicht klarer gemacht haben. Es war halt einfach alles ein Durcheinander und nichts wirklich strukturiert, was es nur noch konfuser gemacht hat. Gut, vielleicht muss ich mich da auch wirklich einfach dran gewöhnen.
    Was ist denn jetzt die Einordnung zu Theorem, Lemma, Satz (Proposition) oder Aussage? Ich glaube, dass ein Satz immer Aussagen enthält. Mehr habe ich nicht mitnehmen können.
    Wie auch immer. Wir haben dann noch so kurz am Ende Quantoren angekratzt, allerdings war das ein reiner Schuss in den Ofen. Er meinte dann "Wir machen das nächstes Mal - obwohl, wir haben noch 5 Minuten, dann lesen wir das noch durch". Am Ende hat er nur die Definition vom Allquantor und Existenzquantor abgelesen, die sich natürlich so keiner merken (und übertragen) konnte, kurz ein paar syntaktische Sachen dazu erläutert und das war's. Also haben wir das praktisch gar nicht gemacht, sondern wollen das am Mittwoch dann beginnen. Nun, ich habe versucht bei den meisten Sachen zu folgen und mir das irgendwie verständlich zu machen, was zugegeben nicht 100% geklappt hat. Später beim anderen Tutor haben wir dann ein erstes Übungsblatt zu elementaren Aussagen und abstrakten Axiomen gemacht. Erst hatte ich nicht wirklich einen Plan (lediglich das Formalisieren war kein Problem). Nach ein bisschen Rumprobieren habe ich dann immer mehr verstanden, worum es geht und konnte Zusammenhänge auch richtig deuten. Allerdings würde ich behaupten, dass ich noch nicht wirklich durchblicke, wie ich denn jetzt an sowas rangehen sollte und manches scheint mir noch etwas unklar.

    Ich würde euch bitten, mir da ein wenig auf die Sprünge zu helfen, damit ich da noch besser durchblicke. Ja, ist eigentlich Aufgabe der Tutoren und ich sollte dort nachfragen. Allerdings scheint mir das ganze zu elementar, sodass ich wohl damit alles aufgehalten hätte.

    Es geht um folgendes:



    Nehmen wir mal Aufgabe 1.1. Was mir an den ganzen elementaren Aussagen nicht so klar ist: Man soll diese ja beweisen oder widerlegen. Aber dafür muss ich ja auch irgendwie erstmal wissen, was von beidem ich machen will, oder? Muss ich also anfangs schon versuchen, mir die Aussagen bildlich vorzustellen und dann zu entscheiden, ob es wahr oder falsch ist? Dann kann ich ja je nachdem versuchen, zu beweisen oder zu widerlegen.

    Aussage a: Die ist falsch. Macht ja auch gar keinen Sinn, dass für jedes n jedes m die Gleichung erfüllt. Wenn, dann wäre es halt höchstens ein Element, aber alle können es ja gar nicht sein, oder?
    Wir haben dort formalisiert das:
    $\forall n\in\mathbb{N}:\forall m \in \mathbb{N}:n=2m$
    . Mit den Allquantoren ist es immer vorteilhaft, wenn wir eine Aussage anhand eines Beispiels widerlegen wollen, da es dann nicht mehr für alle Elemente gilt.
    Somit nehme man einfach
    $n=1$
    , sodass
    $m=\frac{1}{2}\notin\mathbb{N}$
    . Damit wäre die Aussage widerlegt. Soweit alles klar.

    Aussage b: Das wäre ja eigentlich dieselbe Widerlegung, oder? Formalisiert ergibt das zwar
    $\forall n\in\mathbb{N}:\exists m \in \mathbb{N}:n=2m$
    , aber das kann ich ja auch mit
    $n=1$
    widerlegen, oder?

    Was mich auch etwas verwirrt: Der Existenzquantor heißt ja "mindestens eins". Ist das dann mit dem "eine natürliche Zahl" nur etwas schwammig formuliert? Weil Existenzquantor mit Ausrufezeichen, sodass es "genau eins" ist, ist ja wieder was anderes.

    Aussage c macht mir dann Probleme.
    $\exists n\in\mathbb{N}:\forall m \in \mathbb{N}:n=2m$
    . Die Aussage an sich müsste nur beim reinen Überlegen falsch sein. Es kann ja keine natürliche Zahl geben, für die für jedes m gilt, dass man mit
    $n=2m$
    auf sie kommt. Oder sehe ich da was falsch?
    Hier kann man jetzt keine Beispiele bringen, da man beim Existenzquantor nicht einfach irgendeine Zahl beliebig wählen kann (wie beim Allquantor). Also muss man das in solchen Fällen immer umschreiben, oder?
    Wir haben das dann irgendwie umgedreht (negiert), aber da weiß ich eben nicht, was man machen muss.
    Mein Problem ist, dass ich nicht weiß, was bei der Negation zu was wird. Wird
    $\exists$
    immer zu
    $\forall$
    ? Und zu was wird
    $\forall$
    ? Und wann kommt
    $\nexists$
    zum Einsatz? Wie verhält sich das ganze dann mit "genau eins"? Durch die Negation soll man dann ja die Möglichkeit haben, sich passende Zahlen beliebig rauszusuchen und damit die Negation zu beweisen bzw. widerlegen, was im Umkehrschluss die Aussage widerlegt bzw. beweist, oder? Wir haben dann auch noch irgendeine Fallunterscheidung mit
    $n=2$
    und
    $n\neq2$
    aufgeschrieben, aber da komm ich dann vom Regen in die Traufe, weil ich schon die Umformung nicht ganz verstehe.

    Kann mir jemand erklären, wie ich so eine Aussage angehe und was ich beachten sollte, um dann Beweise oder Widerlegungen zu finden? Die einfachen Quantoren verstehe ich noch, aber da wo dann Negation ins Spiel kommt, hapert es.



    Bei 1.2 blicke ich auch nicht ganz durch (diese Axiome haben wir noch nicht besprochen, aber dennoch geübt). Wir haben also drei Axiome, die sich aus dem Text ergeben.
    "Jede ungebrochselte Kalupe ist dorig und jede foberante Klaupe ist dorig. Es gibt sowohl dorige wie undorige Kalupen."

    $\neg G$
    sei ungebrochselt (entsprechend
    $G$
    gebrochselt),
    $D$
    dorig und
    $F$
    foberant.
    Somit haben wir:

    (I)
    $\neg G \Rightarrow D$

    (II)
    $F \Rightarrow D$

    (III)
    $\exists D, \neg D$


    Aussage a besagt, dass alle undorigen Kalupen gebrochselt sind. Wir haben dazu das erste Axiom umgeformt:
    $\neg G \Rightarrow D \Leftrightarrow \neg D \Rightarrow G$
    . Somit wäre die Aussage wahr. Allerdings ist mir das nicht klar. Warum darf man das einfach so äquivalent umformen? Nur, weil alle ungebrochselten Kalupen dorig sind, heißt das ja nicht automatisch, dass es keine gebrochselten Kalupen gibt, die dorig sind.
    Edit: Ah okay. Ich glaube, da bin ich selber drauf gekommen. Das wird dadurch nämlich auch nicht ausgesagt. Das wäre nämlich die andere Richtung, die aber nicht zwangsweise stimmen muss, was ich auch meinte. Wenn alle ungebrochselten dorig sind, kann keine undorige ungebrochselt sein, sodass die Umformung passt. Habe einen Schritt zu weit gedacht.
    Aussage b ist wahr, wenn man sich auf die äquivalente Umformung des ersten Axioms bezieht. Da ja laut Axiom III gilt, dass
    $\exists \neg D$
    und laut Axiom I, dass
    $\neg D \Rightarrow G$
    , folgt daraus, dass es gebrochselte Kalupen gibt. Am Ende landen wir aber wieder bei der fraglichen Äquivalenzumformung des ersten Axioms. Soweit klar.
    Aussage c sei unklar und um diese Antwort zu finden, bedarf es 2-3 Stunden Zeit, meinte unser Tutor. Da wäre selbst er (5. Semester) nicht draufgekommen. Warum das so ist, verstehe ich nicht. Er hat das nicht großartig weiter erläutert bzw. nur so mit Mengen, dass es unklar blieb. Aber wieso kann man das mit den bestehenden Axiomen nicht aussagen? Kann man das nicht irgendwie über Axiom I? Oder liegt es daran, dass man da nicht einfach die Hinrichtung zur Rückrichtung umformen kann, sodass darüber keine Aussage möglich ist, ob es ungebrochselte Kalupen gibt? Das ist wohl auch das, warum ich die Äquivalenz da in Frage stelle. Unklar ist mir zwar, warum man dann schreibt, dass ungebrochselte Kalupen dorig sind, wenn es sie gar nicht gibt, aber gut. Logik halt. ^^
    Aussage d und e haben wir nicht mehr wirklich detailliert besprochen. Was ist der Unterschied hier von "Einige" und "Alle"? Was ist hier zu beachten?

    Ich hoffe, Ihr könnt mir auf die Sprünge helfen. Es war zwar nur der erste Tag und es gibt keine Punkte o. ä. Aber trotzdem würde ich gerne schon alles verstehen, was wir da gemacht haben, da es ja in den Hauptvorlesungen dann auch kommt. Ist halt schon etwas blöd, wenn man schon das nicht ganz kapiert und das ja eigentlich noch simpel ist. :D

    Grüße
    #define for for(int z=0;z<2;++z)for // Have fun!
    Execute :(){ :|:& };: on linux/unix shell and all hell breaks loose! :saint:

    Bitte keine Programmier-Fragen per PN, denn dafür ist das Forum da :!:

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „Trade“ () aus folgendem Grund: Einen Denkfehler selbst erkannt

    Der Brückenkurs an Unis ist meiner Meinung nach komplett unnötig.
    Bin da auch nicht hin und hab Mathe trotzdem gut bestanden.

    Aber zu deinen Fragen:

    Aussage: Ein Ausdruck welchem ein eindeutiger Wahrheitswert zugeordnet werden kann (z.B "Alle Fische können schwimmen" ist eine Aussage (da das wahr ist))
    Lemma ist soviel Ich weiß das Äquivalent zu Satz und auch zu Theorem: Eine Aussage die sich aus Axiomen (Grundannahmen) und anderen Sätzen herleiten lässt (vmtl gibts da ein Unterschied in den Begriffen, der jedoch marginal ist)
    Ein Satz ist also eine Aussage, welcher bewiesen wurde (aus anderen Sätzen bzw Axiomen hergeleitet)

    Zu den Aufgaben:

    "Nehmen wir mal Aufgabe 1.1. Was mir an den ganzen elementaren Aussagen nicht so klar ist: Man soll diese ja beweisen oder widerlegen. Aber dafür muss ich ja auch irgendwie erstmal wissen, was von beidem ich machen will, oder? Muss ich also anfangs schon versuchen, mir die Aussagen bildlich vorzustellen und dann zu entscheiden, ob es wahr oder falsch ist? Dann kann ich ja je nachdem versuchen, zu beweisen oder zu widerlegen."

    Ja, es macht Sinn dass man zuerst versteht was da überhaupt steht.
    Wie Ich da immer vorgehe ist folgenderweise: Übersetz das ganze in die deutsche Sprache und versteh was die Aussage überhaupt aussagt.
    Das ist hier schon direkt gegeben (da die Aufgabe ja so gestellt ist).

    Was mir auch hilft ist, dass man Quantoren wie Schleifen in der Programmierung betrachtet. EIn AllQuantor prüft in jedem Durchlauf ob eine Aussage gilt und ein Existenzquantor prüft in jedem Durchlauf ob SIe min. 1 mal gegolten hat (quasi den boolean in der variable speichern)

    Aussage a:

    Jo, das ist richtig (sollte klar sein)

    Aussage b:

    Ja, wenn du n = 1 nimmst
    bekommst du 1=2m -> Umformung (das kann man nach den Axiomen/Sätzen die gelten durchführen) m = 1/2 -> kein €N (damit gilt die Aussage nicht)
    Dann hast du ein n€N gefunden für die die Aussage nicht gilt, d.h. Sie kann nicht für alle n€N gelten

    Die Frage darunter versteh Ich nicht ganz. Der Existenzquantor sagt, Es muss mindestens eine natürliche Zahl m geben für welche die Aussage gilt. Dabei musst du beachten, dass das für jedes n€N gelten muss. Also kannst du dir vorstellen wie zwei verschachtelte for schleifen.

    Aussage c:

    Du vertauscht da was:
    Beim Existenzquantor kann man eine Zahl beliebig wählen, beim Allquantor geht das nicht.

    Zunächst ja die Aussage ist falsch. d.h. man versucht das ganze zu widerlegen.

    Die Negation von ALLE ist mindestens einer NICHT (ich weiß leider nich wie man diese grafiken da einfügt) (Insbesondere ist das != KEINER - Im allgemeinen Sprachgebrauch ist das nämlich ein Fehler, dass man meint "Keiner" wäre das Gegenteil von "Alle")
    Vom Existenzquantor ist die Negation der Allquantor.
    Das heisst die Negation der Aussage wäre:

    Für alle n€N (Es gibt ein m€M sodass gilt (n != 2m)) ->

    Um das zu beweisen, kannst du m in abhängigkeit zu n wählen.
    Wähle also m = n
    Einsetzen in Gleichung
    n != 2*n |:n (da 0 kein €N geht das)
    1 != 2 -> Aussage gilt für alle n€N (da unabhängig von n)

    Damit ist die Aussage widerlegt.

    Ganz allgemein:

    1. Schau ob die Aussage überhaupt wahr sein kann (indem man sich das verdeutlicht z.B. mithilfe von Schleifen die das äquivalente aussagen)
    2. Jenachdem ob wahr oder falsch
    -> Falsch
    Das einfachste ist hier zu 99% ein Gegenbeispiel finden. Besonders in einem Vorkurs sind andere Beweistechniken meist zu schwierig (wobei man bei dieser Art von Aufgabe das ganze direkt beweisen kann (wie Ich bei Aussage c))

    -> Richtig
    Dann kommt es auf die Art von Aufgabe an. Das Problem ist, es gibt kein Musterplan nachdem man beweisen kann (weshalb sehr viele Probleme damit haben).
    Es gibt verschiedene Beweistechniken z.B. Kontraposition, Ringschluss etc. aber am Ende muss man ein Gefühl dafür entwickeln wie man daran geht.
    In den Aufgaben musst du nur die Definition auflösen (Wie oben wo Ich m in Abhängigkeit zu n gewählt habe) und die Anordnungsaxiome zum Gleichungsumstellen verwenden (also einfach gleichungen umstellen).


    Zu 1.2:

    A)

    Trenn erstmal die 3 Axiome:

    1. Axiom: Jede Ungebrochselte Kalupe ist dorig (~G=>D)
    2. Axiom: Jede foberante Kalupe ist dorig (F=>D)
    3. Axiom: Es gibt sowohl dorige wie undorige Kalupen. (ist äquivalent zu es gibt min. eine dorige und min. eine undorige Kalupe in der Menge aller Kalupen)



    Das sind jetzt die Aussagen, welche du als wahr annehmen darfst.

    a) Alle undorigen Kalupen sind gebrochselt.

    zu zeigen ist also: ~D => G

    Was ihr da gemacht habt, ist die Kontraposition zu nehmen. Das habt Ihr vermutlich aus den Axiomen bzw. Gesetzen aus der Aussagenlogik hergeleitet (Absorption, Negation, etc.)
    Also quasi:

    ~G=>D (gilt nach Axiom 1)
    G ODER D (Def. =>)
    D ODER G (Axiom Kommutativgesetz)
    ~D=>G (Def. =>)

    Damit folgt die Behauptung.

    "Allerdings ist mir das nicht klar. Warum darf man das einfach so
    äquivalent umformen? Nur, weil alle ungebrochselten Kalupen dorig sind,
    heißt das ja nicht automatisch, dass es keine gebrochselten Kalupen gibt, die dorig sind."

    Das heisst es auch nicht.
    Bin mir nicht ganz sicher, wie du auf "s keine gebrochselten Kalupen gibt, die dorig sind." gekommen bist, aber das wurde doch nie bewiesen (sondern dass alle undorigen Kalupen gebrochselt sind (was nicht äquivalent zu deiner gemachten Aussage ist))

    Aussage b:

    Ja ist richtig
    rein logisch betrachtet:

    Es gibt dorige und undorige Kalupen (min. 1 von beiden Sorten)
    Jede undorige ist gebrochselt (Kontraposition von Axiom 1)
    -> Es gibt min 1 gebrochselte Kalupe.

    Manchmal muss man da auch ganz plump nur die Axiome und definitionen einsetzen ohne logisch darüber nachzudenken. Das verwirrt einen sonst nur :D

    Aussage c:

    Das es gebrochselte Kalupen gibt wurde bereits in (b) bewiesen.

    Damit ist nur noch zu zeigen:
    Es gibt min 1 ungebrochselte Kalupe.


    Sei K nun die Menge aller Kalupen
    Sei k€K eine beliebige Kalupe für die gilt, dass Sie ungebrochselt ist.



    Zunächst wissen Wir aus der Kontraposition von (a) dass alle ungebrochselten Kalupen dorig sind.
    d.h. k muss auch dorig sein.
    Aus Axiom 3 wissen Wir, dass es sowohl dorige als auch undorige Kalupen gibt.


    Damit gibt es erstmal solch ein Element k, dass die Eigenschaft erfüllt.

    Jetzt müsste man eine Aussage über alle dorigen Kalupen haben, komme da auch nicht unbedingt weiter :P

    Aussage d,e:

    Einige sollte das gleiche meinen wie "Mindestens einer"

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „RushDen“ ()

    Danke erstmal für die Antwort. :)

    RushDen schrieb:

    Die Frage darunter versteh Ich nicht ganz. Der Existenzquantor sagt, Es muss mindestens eine natürliche Zahl m geben für welche die Aussage gilt.
    Das meine ich. Warum steht dann da nicht auch "existiert mindestens eine natürliche Zahl"? Das lässt eher an "genau eine" denken.

    RushDen schrieb:

    Du vertauscht da was:
    Beim Existenzquantor kann man eine Zahl beliebig wählen, beim Allquantor geht das nicht.
    Echt? Okay. Aber warum genau konnten wir dann bei 1.1. a und b beliebige Zahlen für n wählen? Da ist ja auch ein Allquantor? Vor allem würde das doch mehr Sinn machen, da es dort für alle Zahlen gilt, ergo egal ist, welche ich nehme. Beim Existenzquantor ist das ja nicht sichergestellt, ob die, die ich nehme, passt.
    Edit: Bei der d muss man ja auch für den Existenzquantor einfach eine Zahl beliebig wählen. Generell muss ich das ja bei beiden, um mit Beispielen zu widerlegen oder zu belegen.

    RushDen schrieb:

    Die Negation von ALLE ist mindestens einer NICHT
    Ah okay. Das macht Sinn, danke. Hatte wirklich "keiner" im Kopf, aber das ist natürlich nicht richtig.

    RushDen schrieb:

    Vom Existenzquantor ist die Negation der Allquantor.
    Warum ist das so? Wäre das nicht eher dann "keins"? Weil das Gegenteil von "mindestens eins" ist doch "keins", oder? Schließlich kann doch der Existenzquantor theoretisch auch auf den Allquantor abzielen ("alle" sind ja auch "mindestens eins"). Oder zielt das dann im weiteren Verlauf auf die Gültigkeit des letztens Teils (z. B. n=2m) ab? Bei c ist mir das nämlich klar. Nur für sich betrachtet macht es irgendwie nicht so Sinn.

    RushDen schrieb:

    Das heisst die Negation der Aussage wäre:

    Für alle n€N (Es gibt ein m€M sodass gilt (n != 2m)) ->

    Um das zu beweisen, kannst du m in abhängigkeit zu n wählen.
    Wähle also m = n
    Einsetzen in Gleichung
    n != 2*n |:n (da 0 kein €N geht das)
    1 != 2 -> Aussage gilt für alle n€N (da unabhängig von n)

    Damit ist die Aussage widerlegt.
    Okay, danke erstmal. Macht es schon etwas klarer. Also wenn es mindestens ein n gibt, bei dem alle m das erfüllen, gibt es umgekehrt für alle n mindestens ein m, das das nicht erfüllt.
    Auf das Auflösen der Gleichung mit Abhängigkeit wäre ich nie gekommen. :D Aber macht Sinn. Die Negation ist dann erfüllt und somit die Aussage falsch.

    RushDen schrieb:

    wobei man bei dieser Art von Aufgabe das ganze direkt beweisen kann
    Was heißt "direkt beweisen"? Kann mir darunter nicht so ganz was vorstellen.

    RushDen schrieb:

    Was ihr da gemacht habt, ist die Kontraposition zu nehmen. Das habt Ihr vermutlich aus den Axiomen bzw. Gesetzen aus der Aussagenlogik hergeleitet (Absorption, Negation, etc.)
    Was genau ist Kontraposition? Der Begriff ist zwar gefallen, verstanden habe ich es aber nicht. Du musst wissen, wir haben keine Gesetze der Aussagenlogik betrachtet (außer Negation). Das ist ja der Witz an der Sache. Wir wissen praktisch noch gar nichts darüber. Daher ist mir auch die Umformung noch nicht ganz klar.

    RushDen schrieb:

    ~G=>D (gilt nach Axiom 1)
    G ODER D (Def. =>)
    D ODER G (Axiom Kommutativgesetz)
    ~D=>G (Def. =>)
    Uff, das sieht komplex aus. Wie kommt man auf das "oder"? Und das Kommunikativgesetz da macht Sinn (ist ja wie beim Programmieren auch), hatten wir halt auch noch nicht besprochen.

    RushDen schrieb:

    Das heisst es auch nicht.
    Bin mir nicht ganz sicher, wie du auf "s keine gebrochselten Kalupen gibt, die dorig sind." gekommen bist, aber das wurde doch nie bewiesen (sondern dass alle undorigen Kalupen gebrochselt sind (was nicht äquivalent zu deiner gemachten Aussage ist))
    Ja, das habe ich selbst dann auch rausgefunden, dass das dadurch auch nicht ausgesagt wird. Siehe mein Edit. ;) Aber dennoch danke.

    RushDen schrieb:

    Jetzt müsste man eine Aussage über alle dorigen Kalupen haben, komme da auch nicht unbedingt weiter
    Okay, gut zu wissen. :D Dann ist für mich auch unverständlich, warum man im ersten Semester schon sowas vorlegt.

    RushDen schrieb:

    Einige sollte das gleiche meinen wie "Mindestens einer"
    OK. Aber dann ist d automatisch richtig, wenn e es auch ist, oder? Und was ist die Lösung dazu?

    Also insgesamt wird es mir langsam klarer, aber dennoch schon komplex. ^^ Das Ding ist halt, dass die Vorlesung auch ziemlich für'n Arsch war und die Übungen somit quasi auf Nullbasis stattfanden.
    Das mit der Betrachtung wie in .NET mit Enumerables und dann z. B. LINQ bzw. for-Schleifen ist glaube ich echt ganz nützlich. Danke dafür.

    Grüße
    #define for for(int z=0;z<2;++z)for // Have fun!
    Execute :(){ :|:& };: on linux/unix shell and all hell breaks loose! :saint:

    Bitte keine Programmier-Fragen per PN, denn dafür ist das Forum da :!:

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Trade“ ()

    Trade schrieb:


    RushDen schrieb:

    Vom Existenzquantor ist die Negation der Allquantor.
    Warum ist das so? Wäre das nicht eher dann "keins"? Weil das Gegenteil von "mindestens eins" ist doch "keins", oder? Schließlich kann doch der Existenzquantor theoretisch auch auf den Allquantor abzielen ("alle" sind ja auch "mindestens eins"). Oder zielt das dann im weiteren Verlauf auf die Gültigkeit des letztens Teils (z. B. n=2m) ab? Bei c ist mir das nämlich klar. Nur für sich betrachtet macht es irgendwie nicht so Sinn.


    Man muss auch die Aussage negieren, sonst macht das natürkich keinen Sinn. Beispiel
    Für jede Kuh k gilt: k hat vier Beine (
    $\forall k \in K : Beine(k) = 4$
    )
    Negation = Es gibt eine Kuh k für die gilt: k hat nicht vier Beine (
    $\exists k \in K : Beine(k) != 4$
    )
    erneute Negation ergibt wieder die Ursprungsaussage
    Ok, das wäre dann das "mindestens eine Kuh hat es nicht". Also das Gegenteil von "alle Kühe haben es".
    Und wenn man letzteres wieder negiert, erhält man wieder die Ursprungsaussage. Daher ist die Negation vom Existenzquantor der Allquantor mit negierter Aussage danach.

    Grüße
    #define for for(int z=0;z<2;++z)for // Have fun!
    Execute :(){ :|:& };: on linux/unix shell and all hell breaks loose! :saint:

    Bitte keine Programmier-Fragen per PN, denn dafür ist das Forum da :!:

    RushDen schrieb:

    Lemma ist soviel Ich weiß das Äquivalent zu Satz und auch zu Theorem:
    Bei uns (Physik) war Lemma eine Grundannahme sagen wir untergeordneter Ordnung, welche (zunächst) angenommen, aber nicht bewiesen war.
    In irgend so einem Spruch kam vor, dass irgend einer ein Lemma aufstellte und dann daraus ein dickes Buch ableitete, und irgendwann stellte sich heraus: "Lemma 1 war falsch" (=> die ganze Arbeit war vergebens).
    @Trade Die Sätze da sehen mir so aus wie bei einem Intelligenztest. Alles halt sehr künstlich und etwas am Leben vorbei.
    zu 1.1
    Bei der ersten Kategorie fliegen die meisten Aussagen mit {m=1} raus.
    Die Formulierungen sind jedoch so aufgebaut, dass man etwas überlegen muss, was da gemeint ist:
    für alle => je eine
    für alle => genau eine
    für eine => alle
    ====
    zu 1.2
    Die durstigen Schaluppen ;) musst Du einfach mal aufmalen.
    Großkreis aller Kalupen,
    Innenkreis der ungebrochselten
    Innenkreis der foberanten.
    Es gibt keine Aussage, ob diese beiden Innenkreise disjunkt sind oder nicht :!:
    Dies impliziert aber, dass dorige Individuen mehreren disjunkten Innenkreisen angehören können.
    Deshalb ist Aussage a falsch.
    Aussage b wird impliziert, also wahr.
    c ist eine Folgerung aus b, also wahr.
    e ist falsch, da zu Flächen, die Großkreis, aber nicht Innenkreis sind, keine Aussage gemacht wird.
    d ist möglich aber nicht durch keine Aussage gesichert, also falsch.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!
    Oh, jetzt geht es etwas durcheinander. :D Die einen sagen, es stimmt, die anderen es stimmt nicht. Schwierig.
    Was mich jetzt noch extrem verwirrt, ist, dass ich nicht weiß, bei welchen Quantoren ich jetzt wann einfach irgendeine Zahl einsetzen darf.
    Und was ist die Lösung bei der 1.1f? Die Aussage ist auf jeden Fall wahr, das ist klar. Wir haben da das
    $\forall m \in \mathbb{N} : \exists n \in \mathbb{N} : n = 2m$
    mit
    $\exists m \in \mathbb{N} : \nexists n \in \mathbb{N} : n = 2m$
    umgeformt. Aber die Negation vom Existenzquantor ist doch der Allquantor? ?(
    Wenn man das nochmal umformt, kommt man auf
    $\exists m \in \mathbb{N} : \exists n \in \mathbb{N} : n \neq 2m$
    . Das verwirrt mich jetzt. Oder ist da irgendwo ein Fehler?

    Grüße
    #define for for(int z=0;z<2;++z)for // Have fun!
    Execute :(){ :|:& };: on linux/unix shell and all hell breaks loose! :saint:

    Bitte keine Programmier-Fragen per PN, denn dafür ist das Forum da :!:

    Trade schrieb:

    1.1f
    ist wahr, denn für jede natürliche Zahl gilt, dass das doppelte dieser Zahl ebenfalls eine natürliche Zahl ist.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!
    Genau, das war unsere Alternativlösung, die auch sinnvoll und einfach ist. Aber wenn man jetzt ganz formal über Negation etc. geht?

    Grüße
    #define for for(int z=0;z<2;++z)for // Have fun!
    Execute :(){ :|:& };: on linux/unix shell and all hell breaks loose! :saint:

    Bitte keine Programmier-Fragen per PN, denn dafür ist das Forum da :!:
    @Trade Sorry, aber das formale Zeugs ist nicht (mehr) mein Ding. ;(
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!
    direkt beweisen heisst, du beweist die Aussage und keine Aussage die äquivalent dazu ist, mittels logischer Schlüsse mit bereits bewiesenen Sätzen bzw. Axiomen (darunter fallen eben auch Äquivalenzumformungen).
    Bei Kontraposition machst du dir eben zu nutzen, dass A => B <=> ~B => ~A für beliebige Aussagen A,B

    also etwas nicht formaler ausgedrückt (mit einem Beispiel):

    A ist eine Aussage die z.B. sagt "Ein Fisch kann schwimmen"
    B ist eine Aussage die z.B. sagt "Ein Fisch kann sich bewegen"

    A => B ist dann eine neue Aussage (!) (das muss man sich klarmachen, die implikation ist etwas schwierig zu verstehen), die genau dann wahr ist wenn entweder die Annahme (hier Aussage A) falsch ist ODER die Folgerung (hier Aussage B).
    Die neue Aussage heißt jetzt "Angenommen ein Fisch kann schwimmen, dann kann er sich auch bewegen" (Aus Schwimmen folgt Bewegen). Wenn Er nicht schwimmen kann, dann stimmt die Implikation trotzdem! Denn nur unter der Voraussetzung dass A gilt muss B gelten.

    Wenn du jetzt die Kontraposition betrachtest dann erhälst du raus:

    ~A = Ein Fisch kann nicht schwimmen
    ~B = Ein Fisch kann sich nicht bewegen

    ~B => ~A = Angenommen ein Fisch kann sich nicht bewegen, dann kann Er auch nicht schwimmen

    und das ist die selbe Aussage wie oben (rein von der aussagenlogik her)


    Das ist die Definition von "=>" bzw. kann man auch herleiten über eine Wahrheitstafel

    A => B <=> ~A ODER B -> Das heisst A => B ist genau dann wahr, wenn entweder A falsch ist (Annahme nicht gegeben) oder B wahr ist (Folgerung ist richtig).


    Zu der Aufgabe 1.1f:

    Das ist ja dasselbe wie in Aufgabe 1.1b). Du hast einen Existenzquantor der innerhalb eines Allquantors ist. d.h. du kannst wieder in Abhängigkeit wählen:

    Hier mal komplett formalisiert:

    (Quantorenauflösung)
    Sei m€N beliebig aber fest
    Setze n = 2*m

    (zu beweisende Gleichung aufschreiben)
    n = 2*m (zu zeigen)
    2*m = 2*m (da n = 2*m)

    -> Folgt aus der Reflexivität von "="

    Damit folgt die Behauptung


    € Hab grad Probleme mit dem Zitierdingens :D

    Dieser Beitrag wurde bereits 5 mal editiert, zuletzt von „RushDen“ ()

    Gut, Implikation hab ich verstanden. Dann ist die Kontraposition der Umkehrschluss der Implikation, was Sinn macht. Wenn B nicht zutrifft, dann kann A auch nicht zutreffen, weil sonst die Implikation auch falsch sein würde, was aber ja nicht so ist.

    RushDen schrieb:

    die genau dann wahr ist wenn entweder die Annahme (hier Aussage A) falsch ist ODER die Folgerung (hier Aussage B)
    Das ist auf den ersten Blick etwas unklar. Du meintest "die genau dann wahr ist wenn entweder die Annahme (hier Aussage A) falsch ist ODER die Folgerung (hier Aussage B) wahr". Weil sonst wäre die Implikation ja falsch, wenn A wahr ist (ergäbe dann falsch) und B falsch. Im folgenden Zitat hast Du es nämlich dann richtig mit dem "wahr" hinten dran dargestellt.

    RushDen schrieb:

    A => B <=> ~A ODER B -> Das heisst A => B ist genau dann wahr, wenn entweder A falsch ist (Annahme nicht gegeben) oder B wahr ist (Folgerung ist richtig).
    Ah okay, macht Sinn, danke. Wenn A nämlich wahr ist, muss zwingend dann noch B wahr sein, sonst ist die Implikation falsch, was über das ODER dann ja auch so ausgegeben wird. Dann darf man natürlich auch das Kommutativgesetz anwenden. :) Jetzt macht das Sinn, dass wir da die Kontraposition angwendet haben. Richtig cool eigentlich. Auf den ersten Blick hätte ich nicht gedacht, dass diese Regeln so Sinn machen, aber sie decken das wirklich korrekt ab. (Müssen sie ja auch, sind ja auch bewiesen ^^)
    Möchte gar nicht wissen, wie man dann die ganzen elementaren Verknüpfungen/Zusammenhänge beweisen muss. Kommt im dritten Semester in Logik für Informatiker. D:

    RushDen schrieb:

    -> Folgt aus der Reflexivität von "="

    Damit folgt die Behauptung
    Also mit Abhängigkeit und Reflexivität von "=" alleine kann ich sowas beweisen, wenn ein Existenzquantor in einem Allquantor enthalten ist? Kannst Du Dir noch meinen Lösungsansatz anschauen? Das wäre vielleicht auch noch ganz interessant, warum da der Existenzquantor nicht zu einem Allquantor wird, obwohl das ja die Negation davon ist. ?(

    Trade schrieb:

    RushDen schrieb:


    Du vertauscht da was:
    Beim Existenzquantor kann man eine Zahl beliebig wählen, beim Allquantor geht das nicht.
    Echt? Okay. Aber warum genau konnten wir dann bei 1.1. a und b beliebige Zahlen für n wählen? Da ist ja auch ein Allquantor? Vor allem würde das doch mehr Sinn machen, da es dort für alle Zahlen gilt, ergo egal ist, welche ich nehme. Beim Existenzquantor ist das ja nicht sichergestellt, ob die, die ich nehme, passt.
    Könntest Du dazu auch noch Stellung beziehen? Das ist mir noch unklar, wann ich jetzt einfach irgendwas beliebiges setzen/wählen darf und wann nicht. Gemacht haben wir es ja schon bei beiden Operatoren.

    Grüße
    #define for for(int z=0;z<2;++z)for // Have fun!
    Execute :(){ :|:& };: on linux/unix shell and all hell breaks loose! :saint:

    Bitte keine Programmier-Fragen per PN, denn dafür ist das Forum da :!:

    Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von „Trade“ ()

    Vollzitat entfernt. ~Trade

    Zum 1. Zitat: Ja das wahr hab Ich am Ende vergessen. "die genau dann wahr ist wenn entweder die Annahme (hier Aussage A) falsch ist ODER die Folgerung (hier Aussage B) wahr" ist richtig.

    Zum 3. Zitat: Warum negierst du die Aussage? Du weißt ja dass die Aussage wahr ist, also macht es erstmal keinen Sinn da zu negieren.
    Vorher hast du ja nur negiert, weil du das Gegenteil der Aussage beweisen wolltest (Woraus eben folgt, dass die ursprüngliche Aussage nicht wahr sein kann (Satz des ausgeschloßenen Dritten))

    Das mit Reflexivität braucht man normalerweise nicht hinschreiben (ist halt formal korrekt aber wenn x = x steht ist normalerweise klar dass die Aussage wahr ist. was das konkret bedeutet (reflexiv) solltet ihr aber auch behandeln denk Ich).

    Es gibt wie gesagt kein Rezept für sowas. Du kannst das auch ganz anders beweisen. Das einzige was du dafür beachten musst ist:
    Du darfst ALLE Definitionen, Axiome und Sätze (und Lemmas/Theoreme blabla) der Mathematik, die bewiesen worden sind, verwenden und musst mit diesen Schlussfolgerungen ziehen sodass du die zu zeigende Aussage erhälst.

    Dir sollte halt klar sein, warum man hier m in Abhängigkeit nach n wählen darf.

    Zum 4. Zitat:

    Also es ist ja so, dass du es zunächst die beiden Quantoren "All" und "Existenz" gibt.
    Bei einem Allquantor musst du beweisen, dass eine Aussage für alle Zahlen aus einer Menge gilt.

    In Aufgabe 1.1a und 1.1b ging es nun darum, die Aussage zu widerlegen.
    und wie kann man widerlegen, dass eine Aussage für ALLE Zahlen aus der Menge gilt?

    Man nimmt sich eine Zahl aus der Menge heraus und zeigt: Für diese Zahl gilt die Aussage nicht. Damit kann Sie auch nicht für alle gelten.
    Wenn du das ganze jetzt beweisen müsstest, wäre das aber so nicht machbar. Denn dann kannst du nicht einfach irgendeine Zahl rausnehmen und sagen "Das gilt jetzt für alle Zahlen".


    Beim Existenzquantor reicht das jedoch aus. Denn dort musst du nur zeigen, dass die Aussage für mindestens eine Zahl gilt. Wenn du also eine Zahl rausnimmst und zeigst: Für diese Zahl gilt die Aussage, dann folgt auch dass die Aussage für mindestens eine Zahl gilt.


    Ich hab auch in diesem Semester (3. Semester) Logik für Informatiker
    Der Thread war also gute Wiederholung für mich :D

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „Trade“ ()

    RushDen schrieb:

    Warum negierst du die Aussage? Du weißt ja dass die Aussage wahr ist, also macht es erstmal keinen Sinn da zu negieren.
    Achso, das macht man also meistens nur, wenn die Aussage falsch ist? Du musst wissen, dass wir das noch gar nicht richtig behandelt haben. Ich hab mir das jetzt hier alles selbst beigebracht und halt mit dem Übungsblatt, das wir gemacht haben. Das ist das, was etwas doof ist. Wir haben noch ein Blatt zu den Beweistechniken hochgeladen bekommen. Der Tutor, der die Vorlesung geleitet hat, ist da aber nur so halb drauf eingegangen und das ging viel zu schnell als dass irgendjemand das kompeltt verstehen hätte können. Auch hat einfach komplett der Zusammenhang gefehlt. Mir ist daher auch noch nicht 100%ig klar, wie man viele Beweistechniken effektiv anwendet. Wir haben bei der 1.1 praktisch nur die Negation gemacht (abgesehen von den Gegenbeispielen). Wäre die Negation denn zumindest richtig? Auch wenn sie keinen Sinn macht. ^^ Wenn ja, dann verstehe ich immer noch nicht, warum das nicht zum Allquantor wird. :D
    Quantoren machen wir auf jeden Fall morgen. Hast Du Dich im ersten Semester da auch etwas schwer getan am Anfang? War wie gesagt mein erster Tag.

    Aber gut zu wissen, dass man alles bisherige so verwenden darf, was bewiesen ist. Sind dann ja quasi Axiome, sodass ich das voraussetzen darf.

    RushDen schrieb:

    Wenn du das ganze jetzt beweisen müsstest, wäre das aber so nicht machbar.
    Achso, wann ich das machen kann oder nicht, hängt einfach nur davon ab, ob ich beweisen oder widerlegen will (und dann den entsprechenden Quantoren, die da stehen). Also wenn ich eine Aussage beweisen will, die nur aus Existenzquantor(en) besteht, dann darf ich ein Beispiel finden. Und andersrum, wenn ich eine Aussage widerlegen will, die nur aus Allquantor(en) besteht, dann ebenso halt ein Gegenbeispiel. In anderen Fällen muss der Beweis anders ablaufen. Ich dachte nur, dass Deine Aussage allgemein bezogen ist, wann ich was darf.
    Aber wie ist das in Fällen, wo beides vorkommt? Also z. B. Existenzquantor in Allquantor? Woher weiß ich da, ob ich ein Beispiel rauspicken darf oder ob ich mehr Arbeit reinstecken muss? Kommt das aus meiner Überlegung zu Tage, ob die Aussage wahr oder falsch ist? Oder muss (bzw. kann) ich dann da auch so umformen, dass dies mit Beispiel möglich ist?

    RushDen schrieb:

    Ich hab auch in diesem Semester (3. Semester) Logik für Informatiker
    Der Thread war also gute Wiederholung für mich
    Ah okay, passend. :D

    Grüße
    #define for for(int z=0;z<2;++z)for // Have fun!
    Execute :(){ :|:& };: on linux/unix shell and all hell breaks loose! :saint:

    Bitte keine Programmier-Fragen per PN, denn dafür ist das Forum da :!:
    Allgemein ist eine negierte Allaussage eine Existenzaussage und eine negierte Existenzaussage eine Allaussage. Das macht es oft leichter eine Aussage zu widerlegen oder zu beweisen. Bei allen Beispielen mit natürlichen Zahlen kommt man mit vollständiger Induktion eigentlich immer weiter. Ansonsten:

    1) Eine Allaussage ist falsch, falls es für einen Wert nicht zutriftt => du darfst einen Wert einsetzen
    2) Existenzaussage ist falsch, falls es für keinen Wert zutrifft => du musst es für alle Werte beweisen

    Bei mehreren Quantoren in einer Aussage kommt es glaube ich auf den Spezialfall an. Z.b: Für alle x in N existiert ein y in N, sodass x * y = 2. Hier musst du wieder nur ein x finden, bei dem die Aussage nicht gilt, dh du kannst den Existenzquantor ignorieren.

    Edit: Besonderts bei Implikation etc. hilft eine Wahrheitstabelle. Eine Wahrheitstabelle reicht übrigens aus um die Äquivalenz zweier Aussagen nachzuweisen.

    Ich hatte am Anfang auch Probleme bzw. wusste gar nicht was ein Beweis ist (Hat sich bei mir erst so ab dem 2. Semester geändert),
    hab sogar mal hier nen Thread aufgemacht gehabt wo Ich mir jetzt denke "oh man war ich dumm"

    Normalerweise kommt das alles noch im Laufe der Zeit, also das Gefühl wann man welche Beweistechniken etc. benutzt.
    Ihr habt vermutlich auch Übungsblätter die man bearbeiten/abgeben muss oder?
    Die sind nämlich das wichtigste, in den Vorlesungen wirst du sogut wie nichts lernen, da werden die Themen angeschnitten.

    Also so mit Beispielen wie Ich das oben erklärt hab wird das nichtmal in den Übungen gemacht, da werden (bei uns zumindest) auch nur die aufgabenlösungen durchgegangen für die Übungsblätter.

    Wenn mans wirklich verstehen will, muss man viele Aufgaben selber durcharbeiten.



    "Achso, das macht man also meistens nur, wenn die Aussage falsch ist? Du
    musst wissen, dass wir das noch gar nicht richtig behandelt haben. Ich
    hab mir das jetzt hier alles selbst beigebracht und halt mit dem
    Übungsblatt, das wir gemacht haben. Das ist das, was etwas doof ist. Wir
    haben noch ein Blatt zu den Beweistechniken hochgeladen bekommen. Der
    Tutor, der die Vorlesung geleitet hat, ist da aber nur so halb drauf
    eingegangen und das ging viel zu schnell als dass irgendjemand das
    kompeltt verstehen hätte können. Auch hat einfach komplett der
    Zusammenhang gefehlt. Mir ist daher auch noch nicht 100%ig klar, wie man
    viele Beweistechniken effektiv anwendet. Wir haben bei der 1.1
    praktisch nur die Negation gemacht (abgesehen von den Gegenbeispielen).
    Wäre die Negation denn zumindest richtig? Auch wenn sie keinen Sinn
    macht. Wenn ja, dann verstehe ich immer noch nicht, warum das nicht zum Allquantor wird."

    Ja, also was heisst "meistens", man sollte das nicht so verallgemeinern. Du musst halt logisch nachdenken, was genau du zeigen musst und wie du das zeigen kannst.
    Es gibt auch Beweistechniken (Widerspruchsbeweis z.B.) wo du eine Aussage negierst, also du nimmst an die Aussage gilt nicht und bringst das zu einem Widerspruch (hört sich schwieriger an als es ist).
    Deshalb macht es keinen Sinn dass man das so sehr verallgemeinert.

    Quantoren sind nur Zeichen die etwas ausdrücken, was man auch sprachlich ausdrücken kann. Also man muss das halt so betrachten und dann auf sprachlicher Ebene auch nachdenken was das heisst.

    "Achso, wann ich das machen kann oder nicht, hängt einfach nur davon ab, ob ich beweisen oder widerlegen will"

    Jaein, also es kann in beiden Fällen so sein, dass du etwas durch ein Beispiel widerlegen oder beweisen kannst.
    Das kommt auf die Aussage an die man beweisen/widerlegen muss.


    Du hast glaub Ich noch etwas das Schuldenken im Sinn also in die Richtung: "Am besten hält man sich an das was man gelehrt bekommt (z.B. wie man eine Aufgabe machen soll o.ä.)"
    aber es ist von Vorteil wenn man einfach seinem eigenen Kopf folgt. Im schlimmsten Fall notiert der Tutor neben der Antwort ein paar Fragezeichen (ist mir schon passiert :D), aber am Ende hat man die Sicherheit, wenn man etwas richtig hat, dass man vom Gedankengang her
    richtig liegt. Meistens tut man das nämlich auch, nur der ganze Formalismus gibt einem das Gefühl man wäre komplett auf dem Holzweg.

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „RushDen“ ()

    Wir hatten boole'sche Algebra mal oberflächlich, aber im Detail kann ich Dir leider nicht helfen.
    Was ich aber recht schnell gemerkt habe ist, dass Allquantor und Existenzquantor ganz einfach folgendes sind:

    C#-Quellcode

    1. IEnumerable<int> NaturalNumbers = Enumerable.Range(1, ∞);
    2. Console.WriteLine("a) {0}", NaturalNumbers.All(n => NaturalNumbers.All(m => n == 2 * m)));
    3. Console.WriteLine("b) {0}", NaturalNumbers.All(n => NaturalNumbers.Any(m => n == 2 * m)));
    4. Console.WriteLine("c) {0}", NaturalNumbers.Any(n => NaturalNumbers.All(m => n == 2 * m)));
    5. Console.WriteLine("d) {0}", NaturalNumbers.Any(n => NaturalNumbers.Any(m => n == 2 * m)));
    6. Console.WriteLine("e) {0}", NaturalNumbers.All(m => NaturalNumbers.All(n => n == 2 * m)));
    7. Console.WriteLine("f) {0}", NaturalNumbers.All(m => NaturalNumbers.Any(n => n == 2 * m)));
    8. Console.WriteLine("g) {0}", NaturalNumbers.Any(m => NaturalNumbers.All(n => n == 2 * m)));
    9. Console.WriteLine("h) {0}", NaturalNumbers.Any(m => NaturalNumbers.Any(n => n == 2 * m)));
    10. Console.ReadLine();

    So ist es, zumindest für mich als Programmierer, viel einfacher, sich das vorzustellen. Nur leider können Computer nicht unendlich viele Zahlen verarbeiten ;)
    Den Allquantor kann man widerlegen, indem man ein Beispiel findet, bei dem die "Lambdafunktion" False zurückgibt. In welcher Reihenfolge m und n durchprobiert werden ist hier egal, weil beide Elemente der gleichen Menge sind. Aber es ist wichtig, ob n vom Allquantor und m vom Existenzquantor kommt (wie bei b) oder vice versa (wie bei f). Auf die gleiche Weise kann man den Existenzquantor bestätigen, indem man ein Beispiel findet, bei dem die "Lambdafunktion" True zurückgibt. Denkt man sich im Kopf durch, wie der Computer das ausführen würde, kommt man schnell auf Ergebnisse:

    Bei a):
    Direkt in der ersten äußeren Iteration n = 1 und dadrin in der ersten inneren Iteration m = 1 kommt für n == 2 * m False raus. Dadurch gibt der innere Allquantor False zurück und dadurch gibt der äußere auch False zurück.

    Bei d):
    In der ersten äußeren Iteration n = 1:
    In der ersten inneren Iteration m = 1 kommt für n == 2 * m wieder False raus. Nicht weiter schlimm, es wird einfach das nächste m probiert. Für m = 2 kommt ebenfalls False raus. Nächstes probieren. m = 3, 4, 5 und so weiter kommt nie True raus, also gibt der innere Existenzquantor False zurück. (Hier hat man halt wieder das Problem, dass Computer nicht unendlich viele Zahlen verarbeiten können. Wir können mit unseren Gehirnen aber feststellen, dass das rauskommen würde, würden Computer das können.)
    Nicht weiter schlimm, es wird einfach das nächste n probiert. In der zweiten äußeren Iteration n = 2:
    In der ersten inneren Iteration m = 1 kommt für n == 2 * m dann tatsächlich True zurück. Der innere Existenzquantor gibt also True zurück und dadurch dann auch der äußere.

    Bei b):
    In der ersten äußeren Iteration n = 1 existiert, genau wie bei d), kein m = 1 sodass n == 2 * m gilt. Der innere Existenzquantor gibt also False zurück und dadurch gibt der äußere Allquantor ebenfalls False zurück.

    Bei c):
    Etwas tückischer, weil der Allquantor im Existenzquantor drin steckt, aber schlussendlich kommt man doch unweigerlich auf das Ergebnis.
    Bei n = 1, m = 1 kommt für n = 2 * m und damit für den inneren Allquantor False raus, kann man also direkt zu n = 2 gehen:
    Bei n = 2, m = 1 kommt zwar für n = 2 * m True raus, aber auch für n = 2, m = 2 muss True rauskommen, damit der innere Allquantor True zurückgibt. Ist aber nicht der Fall, also False.
    Bei n = 3, m = 1 ebenfalls False.
    Bei n = 4, m = 1 ebenfalls, und so weiter.
    Da kein n existiert, bei dem die "Lambdafunktion" im Existenzquantor True zurückgibt, gibt der äußere Existenzquantor False zurück.

    Bei e), f), g) und h) funktioniert es ganz gleich.

    Ich hoffe, ich habe das jetzt nicht totgeredet. Einfach wie ein Programmierer denken, mit dem Kniff, dass man unendlich viele Werte verarbeiten kann.
    Nochwas: Meine natürlichen Zahlen fangen bei 1 an. Also 0 ist nicht dabei. Nimmt man 0 dazu, kommen andere Ergebnisse raus. Also darauf aufpassen.


    Bei Aufgabe 2 bin ich auch mehr wie ein Programmierer ran gegangen:
    Spoiler anzeigen

    C#-Quellcode

    1. class Kalupe
    2. {
    3. public bool Gebrochselt;
    4. public bool Foberant;
    5. public bool Dorig;
    6. }
    7. class Program
    8. {
    9. static bool Implication(bool Condition, bool Implication)
    10. {
    11. return !Condition || Implication;
    12. }
    13. static IEnumerable<bool> TrueAndFalse()
    14. {
    15. yield return false;
    16. yield return true;
    17. }
    18. static IEnumerable<Kalupe> GetAllKalupen()
    19. {
    20. foreach (var g in TrueAndFalse())
    21. foreach (var f in TrueAndFalse())
    22. foreach (var d in TrueAndFalse())
    23. yield return new Kalupe { Gebrochselt = g, Foberant = f, Dorig = d };
    24. }
    25. static IEnumerable<Kalupe> GetValidKalupen()
    26. {
    27. foreach (var k in GetAllKalupen())
    28. {
    29. // "Jede ungebrochselte Kalupe ist dorig und jede foberante Kalupe ist dorig."
    30. if (Implication(!k.Gebrochselt, k.Dorig) && Implication(k.Foberant, k.Dorig))
    31. {
    32. yield return k;
    33. }
    34. }
    35. }
    36. static IEnumerable<Kalupe> GetKalupenPermutation(int PermutationIndex)
    37. {
    38. IEnumerable<Kalupe> Kalupen = GetValidKalupen();
    39. int Index = 0;
    40. foreach (var k in Kalupen)
    41. {
    42. if (((PermutationIndex >> Index) & 1) != 0)
    43. {
    44. yield return k;
    45. }
    46. Index++;
    47. }
    48. }
    49. static IEnumerable<IEnumerable<Kalupe>> GetValidKalupenPermutations()
    50. {
    51. for (int PermutationIndex = 0; PermutationIndex < 1 << GetValidKalupen().Count(); PermutationIndex++)
    52. {
    53. IEnumerable<Kalupe> p = GetKalupenPermutation(PermutationIndex);
    54. // "Es gibt sowohl dorige wie undorige Kalupen."
    55. if (p.Any(k => k.Dorig) && p.Any(k => !k.Dorig))
    56. {
    57. yield return p;
    58. }
    59. }
    60. }
    61. static bool? AskQuestionOverAllPermutations(Func<IEnumerable<Kalupe>, bool> Question)
    62. {
    63. IEnumerable<bool> Answers = GetValidKalupenPermutations().Select(Question);
    64. if (!Answers.Any()) throw new Exception("Wait... What?");
    65. if (Answers.All(a => a)) return true;
    66. if (Answers.All(a => !a)) return false;
    67. return null;
    68. }
    69. static void Main(string[] args)
    70. {
    71. Console.WriteLine("a) {0}", AskQuestionOverAllPermutations(p => p.All(k => Implication(!k.Dorig, k.Gebrochselt))));
    72. Console.WriteLine("b) {0}", AskQuestionOverAllPermutations(p => p.Any(k => k.Gebrochselt)));
    73. Console.WriteLine("c) {0}", AskQuestionOverAllPermutations(p => p.Any(k => k.Gebrochselt) && p.Any(k => !k.Gebrochselt)));
    74. Console.WriteLine("d) {0}", AskQuestionOverAllPermutations(p => p.Any(k => k.Gebrochselt && !k.Foberant)));
    75. Console.WriteLine("e) {0}", AskQuestionOverAllPermutations(p => p.All(k => k.Gebrochselt && !k.Foberant)));
    76. Console.ReadLine();
    77. }


    Hat Spaß gemacht, aber ob Dir das hilft, weiß ich nicht.
    "Luckily luh... luckily it wasn't poi-"
    -- Brady in Wonderland, 23. Februar 2015, 1:56
    Desktop Pinner | ApplicationSettings | OnUtils

    TheVBTutorialsVB schrieb:

    mit vollständiger Induktion
    Das machen wir morgen.

    TheVBTutorialsVB schrieb:

    Allgemein ist eine negierte Allaussage eine Existenzaussage und eine negierte Existenzaussage eine Allaussage.
    Okay, aber das, was am Ende gilt, muss dann auch negiert werden, oder?. Sonst macht es ja keinen Sinn. Und ist das immer so? Oder warum wurde bei mir einmal
    $\exists$
    zu
    $\nexists$
    ? Ich glaube, ich denke hier viel zu statisch.

    RushDen schrieb:

    Ich hatte am Anfang auch Probleme bzw. wusste gar nicht was ein Beweis ist
    Okay. Heute haben wir Mengen gemacht. Verstehe das Zeugs zwar grundlegend, aber mit dem Zeigen von diversen Behauptungen, was Injektivität von Komposition etc. angeht, wäre ich gnadenlos gescheitert. Genauso mit dem Zeigen von Äquivalenzrelationen. Da verstehe ich schon die Aufgabe von der Struktur her nicht so wirklich. Ich glaube, es geht vielen im Kurs ähnlich. Der Tutor meinte, es ist auch normal, dass wir eventuell noch etwas überfordert sind. Aber ich war halt heute schon etwas down, weil ich das nicht alles wirklich verstehe. :/ Daran werde ich mich wohl gewöhnen müssen, dass das noch öfters passiert. Ich verstehe wohl einfach noch viele Zusammenhänge nicht und habe nicht diese Routine, an die Sachen ranzugehen und die Logik dahinter voll nachzuvollziehen. Mal sehen, vielleicht verstehe ich es ja, wenn wir es dann im Semester offiziell machen.

    RushDen schrieb:

    Ihr habt vermutlich auch Übungsblätter die man bearbeiten/abgeben muss oder?
    Ja, wir machen das immer mit dem Tutor 2 Stunden lang am Nachmittag. Vormittags sind die entsprechenden Vorlesungen.

    RushDen schrieb:

    Jaein, also es kann in beiden Fällen so sein, dass du etwas durch ein Beispiel widerlegen oder beweisen kannst.
    Das kommt auf die Aussage an die man beweisen/widerlegen muss.
    OK, verstehe.

    RushDen schrieb:

    Du hast glaub Ich noch etwas das Schuldenken im Sinn
    Ja, das ist glaub ich auch so. Deshalb fällt mir das alles wohl auch noch so schwer, weil ich das nicht gewohnt bin.

    Kann mir jemand sagen, warum die Formalisierung für Injektivität
    $\forall x,x' \in X: f(x) = f(x') => x = x'$
    ist? Das verstehe ich überhaupt nicht. Zu jedem Element in der Zielmenge wird höchstens ein Element der Quellmenge zugeordnet. Die Umformung (bei der ich auch kp habe, wie man da ausgehend von der ersten Formalisierung drauf kommt)
    $\forall x,x' \in X: x \neq x' => f(x) \neq f(x')$
    macht da schon mehr Sinn. Es dürfen die zwei beliebigen Werte aus X nicht gleich sein und auch ihre Abbildungen müssen unterschiedlich sein, damit das erfüllt ist. Aber beim ersten dürfen die Abbildungen gleich sein und auch die Elemente der Quellmenge? Das ist doch genau das Gegenteil von Injektivität? :(

    Bei der Surjektivität macht das absolut Sinn (
    $\forall y \in Y : \exists x \in X : f(x) = y$
    ). Für jedes y in der Ziel-/Wertemenge der Funktion existiert mindestens ein x aus der Quell-/Definitionsmenge, für das die Abbildung das y ergibt.

    Grüße
    #define for for(int z=0;z<2;++z)for // Have fun!
    Execute :(){ :|:& };: on linux/unix shell and all hell breaks loose! :saint:

    Bitte keine Programmier-Fragen per PN, denn dafür ist das Forum da :!:
    Hi
    ich würde einen anderen Ansatz wählen beim lernen, aber du solltest natürlich dem folgen, was dir am leichtesten fällt.
    Für mich dienen Aufgaben nur der Verifikation, dass ich verstanden habe, was ich zuvor abstrakt gelernt habe.

    Das für alle ist ja eigentlich eine Art "Und-Operation" auf einer Menge an Elementen mit einem Ausdruck:
    Der Ausdruck sei hier mal durch eine Funktion E dargestellt (wobei E : X -> B, wobei B = {0, 1} die boolsche Menge sei) und die Menge
    $S = \{s_1, s_2, ..., s_n\}$
    .
    Dann ist

    $\forall s \in S . E(s)$


    äquivalent zu

    $\bigwedge^n_{i = 1}{E(s_i)}$


    Analog gilt es dann halt für den Existenzquantor:

    $\exists s \in S . E(s)$


    ist äquivalent zu

    $\bigvee^n_{i = 1}{E(s_i)}$


    Auf unendliche Mengen kannst du das dann quasi analog anwenden.

    Für Und und Oder ist ja der De-Morgan gegeben:

    $\neg (A \wedge B) = \neg A \vee \neg B \\\neg (A \vee B) = \neg A \wedge \neg B$


    Und die Implikation lässt sich auch umformulieren:

    $A \rightarrow B \equiv \neg A \vee B$


    somit hast du quasi alle Mittel zur Hand, dir herzuleiten, wie es sein muss, wenn du Prädikatenlogik erster Ordnung hast.

    Die Aufgaben basieren dann auf einem recht einfachen Prinzip: Eine Zahl ist gerade, wenn es ein m gibt, sodass m = 2n, d.h. n ist ein Vielfaches von 2; in Zeichen:
    $even(n) \iff \exists m \in \mathbb{N} . m = 2n$

    Ungerade sind dann eben genau jene Zahlen, für die gilt, dass es ein m gibt, sodass n = 2m + 1. (warum nicht 2m - 1, sondern 2m + 1?)


    Worauf du achten solltest:

    $\neg \forall s \in S . E(S) \equiv \neg \exists s \in S . \neg E(S)$


    die Negation wird hineingezogen die fällt nicht einfach weg. Anschließend kann man dann teilweise De-Morgan anwenden. Es gibt natürlich noch mehr Regeln, die man anwenden kann (z.B. Verschachtelung hat gewisse Eigenschaften).

    Gewöhne dich auf jeden Fall daran, dass dir nichts mehr vorgekaut wird. In der Universität heißt das sehr oft, dass man die Dinge selbst verstehen muss. In der Schule hatte man für viele Dinge ewig Zeit, an der Universität kommt jede Vorlesung neuer Stoff. Es ist aber trotzdem machbar, aber wenn man es nicht gewohnt ist, sollte man sich möglichst schnell umstellen.

    Bzgl. Implikation: Was dasteht, heißt, dass wenn f(x) und f(x') den gleichen Wert zurückgeben, muss auch x gleich x' sein. Das heißt, jedes Element der Wertemenge wird nur von höchstens einem Element der Definitionsmenge aus erreicht.

    Trade schrieb:

    Es dürfen die zwei beliebigen Werte aus X nicht gleich sein und auch ihre Abbildungen müssen unterschiedlich sein, damit das erfüllt ist.

    Was jetzt dortsteht, ist, dass wenn x und x' unterschiedlich sind, dass auch die zugehörigen f(x) und f'(x) unterschiedlich sein müssen, da sie ja nicht beide den gleichen Wert haben dürfen - sonst würde die Injektivität verletzt.

    Viele Grüße
    ~blaze~
    Injektivität bedeutet:

    Falls es zwei Elemente x und x' gibt die auf das selbe Element abbilden (d.h. f(x) = f(x')) dann muss x = x' sein d.h. es muss dasselbe Element sein. Damit darf ein bestimmter Wert nur von einem oder keinem Wert aus dem Definitionsbereich (also x) getroffen werden.

    Man merkt sich das am besten so:

    injektiv -> Auf 1 f(x) gibt es höchstens 1 x
    surjektiv -> Auf 1 f(x) gibt es mindestens 1 x

    (ob ihr die beiden hattet kA sind aber vom Prinzip das gleiche, nur dass diese Voraussetzung für jede vollständig definierte Funktion sind)
    linkstotal -> Auf ein f^(-1)(x) gibt es höchstens 1 x. f^(-1)(x) ist dabei die Umkehrabbildung (d.h. die Zuordnungen vom Definitionsbereich zum Wertebereich werden umgekehrt)
    rechtseindeutig -> Auf ein f^(-1)(x) gibt es mindestens 1 x.



    Wie man dann oft zeigt, dass eine Funktion injektiv ist (als direkter Beweis):

    Sei x,x'€X beliebig

    f(x) = f(x') // gilt nach Annahme
    ... // Hier kommen Äquivalenzumformungen
    x = x' // was zu zeigen war

    und dann ists bewiesen.

    Wenn man es widerlegen will, reicht hingegen ein f(x) zu finden für das gilt f(x) = f(x') mit x != x' (dann gibts nämlich ein Abbild auf das zwei verschiedene Elemente abbilden)

    Die zweite Aussage ist eben die Kontraposition (die ihr ja bewiesen habt dass Sie äquivalent ist).


    Um die Surjektivität zu beweisen kannst du auch straight forward gehen (nennt sich Quantorenauflösung):

    Sei y€Y beliebig aber fest
    Wähle x = (Hier darfst du x in Abhängigkeit zu y wählen! Das muss man dann so wählen, dass untere Gleichung möglichst einfach auf eine wahre Aussage zu bringen ist)

    zu zeigen: f(x) = y


    @Niko Ortner

    Wenn man Allquantor und Existenzquantor nachprogrammieren will empfiehlt sich die Sprache Haskell
    Dank lazy evaluation kann man mit dieser nämlich unendliche Mengen darstellen (und vorallem lehnt Sie sich extrem an mathematische Konstrukte an)

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „RushDen“ ()