Matroids Matheplanet Forum Index
Moderiert von mire2 StrgAltEntf
Logik, Mengen & Beweistechnik » Mengenlehre » Wie führe ich einen Beweis (Implikation) mit Mengen?
Autor
Universität/Hochschule Wie führe ich einen Beweis (Implikation) mit Mengen?
infosoccom
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 19.09.2021
Mitteilungen: 36
  Themenstart: 2022-11-25

Hallo allerseits, folgende Aufgabe: Es soll folgende Implikation bewiesen werden, wobei A, B und C beliebe Mengen sind: \(A \triangle C = B \triangle C \Rightarrow A = B \) Dies ist ja äquivalent zu: \((A \setminus C) \cup (C \setminus A) = (B \setminus C) \cup (C \setminus B) \Rightarrow A = B \) Ich weiß aber wirklich nicht wie man bei Implikationen mit Mengen mit der Beweisführung startet. Allgemein ist das Vorgehen ja: Aussage p: \((A \setminus C) \cup (C \setminus A) = (B \setminus C) \cup (C \setminus B)\) Aussage q: \(A = B\) Nun muss \(p \Rightarrow q\) gezeigt werden. Bei der Beweisführung wird ja p zunächst als wahr angenommen und in einer Folge von Schritten soll q schließlich aus p gefolgert werden. Mir macht es große Schwierigkeiten einen solchen Beweis zu führen, wenn die Aussagen selbst auf Mengen bezogen sind. Ich finde einfach keinen Ansatz. Wäre sehr dankbar für jede Hilfe.


   Profil
Qing
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 11.03.2022
Mitteilungen: 288
  Beitrag No.1, eingetragen 2022-11-25

Hallo, zu erst musst du wissen was Gleichheit von Mengen bedeutet. Dies sagt uns das Axiom der Extensionalität. Klingt kompliziert, ist es aber nicht. Für zwei Mengen $A$ und $B$ gilt $A=B$, wenn (1) $A\subseteq B$ und (2) $A\supseteq B$ gilt. Es sind also zwei Teilmengeninklusionen zu prüfen. Jetzt musst du nachschlagen was das Symbol $\subseteq$ bedeutet. Also nicht intuitiv, sondern streng nach Definition. Es gilt $A\subseteq B$ wenn für $x\in A$ folgt, dass $x\in B$ gilt. Und damit ist die Methode wie der Beweis zu führen ist festgelegt. Wir müssen unter der Voraussetzung $A\Delta C = B\Delta C$ zeigen, dass $A=B$ ist. Also eine Mengengleichheit, und damit zwei Inklusionen. Um $A\subseteq B$ zu zeigen, muss der Beweis also so beginnen: Sei $x\in A$... und so muss er enden: Also $x\in B$. Sei also $x\in A$. Was sagt dir nun die Gleichheit $A\Delta C = B\Delta C$? Du kannst etwa zwei Fälle unterscheiden. Einmal $x\in C$ und einmal $x\notin C$.


   Profil
infosoccom
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 19.09.2021
Mitteilungen: 36
  Beitrag No.2, vom Themenstarter, eingetragen 2022-11-25

Vielen Dank erstmal für die ausführliche Erklärung. Gibt es aber nicht noch weitere Fälle zusätzlich zu \(x \in C\) oder \(x \notin C\)? So wie ich das verstehe würde das ja bedeuten, dass wenn \(x \in C\), dann gilt \(A = C\) (denn wir setzen ja voraus, dass \(x \in A\)) und wenn \(x \notin C\) dann gilt ja \(A \setminus C = A\). Aber es könnte ja auch den Fall geben, dass manche Elemente von C in A sind und andere wiederum kein Element von A sind. Z.B. : \(A = \{2, 7, 11, 15 \}, C = \{2, 5, 11, 21 \}\) Dann wären ja, wenn wir für \(x = 2\) oder \(x = 11\) wählen, diese beiden Elemente von A auch in C und die anderen beiden Elemente \(x = 7\) und \(x = 15\) wären kein Element von C. Müsste es also nicht noch weitere Fälle geben? Oder verstehe ich folgendes falsch: Wenn man sagt es sei \(x \in A\) und 1. Fall: \(x \in C\), dann meint man doch \(\forall x \in A \Rightarrow x \in C\) und 2. Fall: \(x \notin C\), dann \(\forall x \in A \Rightarrow x \notin C\). Aber wie schon gesagt zeigt das Beispiel, dass es Fälle gibt in denen \(x\) Element von A und C ist.


   Profil
Qing
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 11.03.2022
Mitteilungen: 288
  Beitrag No.3, eingetragen 2022-11-25

Du verstehst es falsch. Wenn wir ein festes Element $x\in A$ betrachten. Dann gibt es stets zwei Fälle. Entweder ist $x\in C$, oder eben nicht. Das ist immer so. Die Frage ist hier ja ob eine Menge eine bestimmte Eigenschaft hat. Nun, entweder hat sie diese Eigenschaft, oder eben nicht. Das ist eine Tautologie. Für eine Aussage $\mathcal{A}$ gilt ja immer $\mathcal{A}\vee\neg\mathcal{A}$, also letztere Aussage ist immer richtig. Die Fallunterscheidung deckt dann eben alles ab, und machen sie um den Beweis strukturierter führen zu können. Eventuell gibt es auch einen Beweis der auf die Fallunterscheidung verzichtet. Für beliebiges $x\in A$, muss natürlich nicht immer $x\in C$ gelten. Das würde ja gerade bedeuten, dass $A\subseteq C$ ist. Es ist schon so wie du es sagst, aber man entscheidet halt für individuelles $x\in A$, und da gibt es dann wie gesagt nur diese beiden Fälle. Mit $A$ hat das dann eigentlich auch gar nichts zu tun. Wie gesagt, entweder trifft eine Aussage zu, oder es trifft ihre Negation zu. Das sind die zwei Fälle.


   Profil
Triceratops
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.04.2016
Mitteilungen: 6469
Wohnort: Berlin
  Beitrag No.4, eingetragen 2022-11-25

Tipp: $(A \Delta C) \Delta C = A$.


   Profil
infosoccom
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 19.09.2021
Mitteilungen: 36
  Beitrag No.5, vom Themenstarter, eingetragen 2022-11-25

Danke Qing nochmal für die Klarstellung und Triceratops für den Tipp. Auf diese Weise scheint die Beweisführung sehr einfach zu funktionieren: Sei \(x \in A\). Da \(A = (A \triangle C)\triangle C\), folgt \(x \in (A \triangle C)\triangle C \). Aus der Hypothese wissen wir \(A \triangle C = B \triangle C\). Also \(x \in (B \triangle C)\triangle C \). Mit \(B = (B \triangle C)\triangle C \) folgt \(x \in B\). \(A \subseteq B\) ist somit bewiesen. Analoge Vorgehensweise für \(B \subseteq A\). Es gilt damit: \(A \subseteq B \land B \subseteq A \Leftrightarrow A = B\) Meint ihr das wäre so in Ordnung oder müsste man den Schritt \(A = (A \triangle C)\triangle C\) ebenfalls noch erstmal beweisen. Natürlich könnte man es sich durch ein Venn - Diagramm schnell klar machen, dass dies immer stimmt. Ich muss aber ehrlich gestehen, dass ich im Leben nicht auf diese Beziehung gekommen wäre...


   Profil
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 2673
  Beitrag No.6, eingetragen 2022-11-25

\(\begingroup\)\(\newcommand{\sem}[1]{[\![#1]\!]} \newcommand{\name}[1]{\ulcorner#1\urcorner} \newcommand{\upamp}{\mathbin {⅋}} \newcommand{\monus}{\mathbin {∸}}\) Das Lemma, dass $A = (A \triangle C)\triangle C$ für alle $A,C$ gilt, solltest du natürlich schon noch beweisen. Auf Arbeit mit Elementen kann man im Beweis, um den es ursprünglich ging, aber verzichten, wenn man das Lemma benutzt: $$\begin{array}{rclll} A &=& (A \triangle C)\triangle C & \text{Lemma} \\&=& (B \triangle C)\triangle C & \text{wg. Annahme } A \triangle C = B \triangle C \\&=& B & \text{Lemma}&\square \end{array}$$\(\endgroup\)


   Profil
Triceratops
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.04.2016
Mitteilungen: 6469
Wohnort: Berlin
  Beitrag No.7, eingetragen 2022-11-26

Das 'Lemma' kann man übrigens entweder direkt oder konzeptionell so beweisen: (1) $\Delta$ ist assoziativ: $A \Delta (B \Delta C) = (A \Delta B) \Delta C$ (2) Es gilt $A \Delta A = \emptyset$. (3) $\Delta$ hat $\emptyset$ als neutrales Element: $A \Delta \emptyset = A$ und $\emptyset \Delta A = A$ Daraus folgt dann ja $(A \Delta C) \Delta C \stackrel{(1)}{=} A \Delta (C \Delta C) \stackrel{(2)}{=} A \Delta \emptyset \stackrel{(3)}{=} A$. Natürlich muss man das dann auch noch jeweils beweisen, aber der Vorteil dieser Vorgehensweise ist, dass man (1),(2),(3) ohnehin beim Arbeiten mit der symmetrischen Differenz $\Delta$ (deren Name hier noch gar nicht gefallen war) erforderlich ist. Die erbrachte Arbeit beschränkt sich also nicht nur auf eine Aussage. Und zudem erklärt sie auch gut, wie man überhaupt auf das 'Lemma' kommt. Und warum man das Lemma hier sinnvoll einsetzen kann, wird von tactac im vorigen Beitrag, aber auch allgemein hier https://matheplanet.de/matheplanet/nuke/html/article.php?sid=1969 in Lemma 3 erklärt. Das ganze ist vielleicht jetzt etwas viel für jemandem, der/die gerade mit Mathematik beginnt, aber vielleicht ist es dennoch lehrreich. Du musst so oder so in der Lage sein bzw. es lernen, auch den von Qing angedeuteten Beweis mit Elementen zu führen.


   Profil
infosoccom
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 19.09.2021
Mitteilungen: 36
  Beitrag No.8, vom Themenstarter, eingetragen 2022-11-26

Bezüglich des Lemmas ist der Beweis für (2) und (3) sehr einfach: (2) \(A \triangle A\) = \((A \setminus A) \cup (A \setminus A)\) = \(\varnothing \cup \varnothing\) = \(\varnothing\) (3) \(A \triangle \varnothing\) = \((A \setminus \varnothing) \cup (\varnothing \setminus A)\) = \(A \cup \varnothing\) = \(A\) Die Assoziativität zu beweisen scheint da schon deutlich schwieriger...


   Profil
Triceratops
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.04.2016
Mitteilungen: 6469
Wohnort: Berlin
  Beitrag No.9, eingetragen 2022-11-26

Das ist soweit richtig.


   Profil
infosoccom
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 19.09.2021
Mitteilungen: 36
  Beitrag No.10, vom Themenstarter, eingetragen 2022-11-26

Die Assoziativität zu beweisen scheint mir da leider etwas zu aufwendig und kompliziert. Ich würde es gerne nochmal mit der Methode von Qing versuchen. Ich habe es jetzt verstanden, dass wir ein festes \(x \in A\) betrachten, sodass es für dieses feste \(x\) in Bezug zur Menge \(C\) jeweils zwei Fälle geben kann. Entweder ist dieses gewählte \(x\) auch Element von \(C\) oder es ist eben kein Element von \(C\). Zunächst einmal kann man ja: \(A \triangle C\) auch als \((A \cup C) \setminus (A \cap C)\) schreiben. Sei also \(x \in A\). 1. Fall: \(x \in C\). Es folgt \(x \in A \cap C\). Nach Definition der symmetrischen Differenz folgt damit \(x \notin A \triangle C\) und als Konsequenz unserer Hypothese \(x \notin B \triangle C\). Wie führe ich den Beweis für den 1.Fall aber fort? Meine Vermutung wäre, dass man aus \(x \in A \cap C\) auch \(x \in B \cap C\) folgern könnte und damit \(x \in B\). Ich hab aber das Gefühl, dass mir der letzte Geistesblitz fehlt, damit es 100% intuitiv Sinn für mich macht oder lässt es sich nicht auf diese Weise \(x \in B\) folgern?


   Profil
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 1283
Wohnort: Kiel, Deutschland
  Beitrag No.11, eingetragen 2022-11-26

\(\begingroup\)\(\newcommand{\id}{\operatorname{id}}\) Hallo infosoccom, \quoteon(2022-11-26 17:19 - infosoccom in Beitrag No. 10) Die Assoziativität zu beweisen scheint mir da leider etwas zu aufwendig und kompliziert. \quoteoff Hier ein Tipp dazu: Zeige zunächst, dass für alle Mengen U, V das Folgende gilt: \[U\triangle V = (U\cup V)\setminus (U\cap V)\quad.\] Schreibe dann \(A\triangle (B\triangle C)\) in einer Art disjunktiven Normalform, d.h. \[A\triangle (B\triangle C) = (\alpha)\cup(\beta)\cup(\gamma)\cup(\delta)\] wobei jede der Klauseln \(\alpha\), \(\beta\), \(\gamma\), \(\delta\) von jeder der drei Mengen A, B, C entweder das Original oder das Komplement enthält und zudem in jeder Klausel lediglich Durchschnitte solcher Mengen gebildet werden, und nutze schließlich aus, dass der Ausdruck, den du so erhältst, invariant unter Vertauschungen von A, B, C ist. mfg thureduehrsen\(\endgroup\)


   Profil
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 2673
  Beitrag No.12, eingetragen 2022-11-26

\(\begingroup\)\(\newcommand{\sem}[1]{[\![#1]\!]} \newcommand{\name}[1]{\ulcorner#1\urcorner} \newcommand{\upamp}{\mathbin {⅋}} \newcommand{\monus}{\mathbin {∸}}\) Ein konstruktiver Beweis der Assoziativität ist ohnehin nicht möglich, also kann man auch die 8 Wahrheitswert-Kombinationen von $x \in A$, $x \in B$, $x \in C$ (ggf. auch optimiert) abklappern.\(\endgroup\)


   Profil
infosoccom
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 19.09.2021
Mitteilungen: 36
  Beitrag No.13, vom Themenstarter, eingetragen 2022-11-26

Hallo thureduehrsen, danke für den Tipp. Zunächst zeigen wir also \(U \triangle V = (U \cup V) \setminus (U \cap V)\). Beweis: Ich muss zeigen, dass \(x \in U \triangle V \Leftrightarrow x \in (U \cup V) \setminus (U \cap V) \). \(\ \ \ \ \ x \in U \triangle V \\ \Leftrightarrow x \in (U \setminus V) \cup (V \setminus U)\ \\ \Leftrightarrow (x \in U \setminus V) \lor (x \in V \setminus U)\\ \Leftrightarrow (x \in U \land x \notin V) \lor (x \in V \land x \notin U)\\ \Leftrightarrow ((x \in U \land x \notin V) \lor x \in V) \land ((x \in U \land x \notin V) \lor x \notin U)\\ \Leftrightarrow (x \in U \lor x \in V) \land (x \notin V \lor x \in V) \land (x \in U \lor x \notin U) \land (x \notin V \lor x \notin U)\\ \Leftrightarrow (x \in U \lor x \in V) \land \lnot (x \in V \land x \in U)\\ \Leftrightarrow (x \in U \lor x \in V) \land \lnot(x \in U \land x \in V) \\ \Leftrightarrow (x\in U \cup V) \land (x \notin U \cap V)\\ \Leftrightarrow x \in (U \cup V) \setminus (U \cap V) \). Diese Beweisschritte habe ich aus einer Übung, die wir besprochen haben übernommen: (1) Vereinigung, (2) Differenz, (3) und (4) Distributivität, (5) de Morgan, (6) Kommutativität, (7) Schnitt und Vereinigung. Ich wollte diesbezüglich nochmal fragen: eine Mengengleichheit muss grundsätzlich auf diese Weise bewiesen werden richtig? Also es muss immer in die Element- und aussagenlogische Schreibweise überführt werden. Leider verstehe ich nicht ganz wie der zweite Teil funktionieren soll. Außerdem weiß ich nicht, was "Klauseln" oder "disjunktive Normalform" im Allgemeinen bedeuten. Könnte ich bitte noch einen weiteren Tipp bekommen oder etwas ausführlicher formuliert bekommen, was genau zu machen ist und wieso es die Assoziativität so beweist. [Die Antwort wurde nach Beitrag No.11 begonnen.]


   Profil
infosoccom
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 19.09.2021
Mitteilungen: 36
  Beitrag No.14, vom Themenstarter, eingetragen 2022-11-26

Hallo tactac, kannst du mir bitte erklären was "konstruktiver Beweis" bedeutet. Die Assoziativität lässt sich also ganz einfach durch eine Wahrheitstafel beweisen, auch wenn es wahrscheinlich eine etwas breite Wahrheitstafel wird.


   Profil
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 2673
  Beitrag No.15, eingetragen 2022-11-26

\(\begingroup\)\(\newcommand{\sem}[1]{[\![#1]\!]} \newcommand{\name}[1]{\ulcorner#1\urcorner} \newcommand{\upamp}{\mathbin {⅋}} \newcommand{\monus}{\mathbin {∸}}\) \quoteon(2022-11-26 21:11 - infosoccom in Beitrag No. 14) Hallo tactac, kannst du mir bitte erklären was "konstruktiver Beweis" bedeutet. \quoteoff Das bedeutet vor allem, dass man eine Logik mit größerem Anwendungsbereich einsetzt, als ihn die klassische Logik bietet. Nämlich intuitionistische Logik. Natürlich bekommt man die Vorteile nicht kostenlos: Man kann im allgemeinen zum Beispiel nicht von $\lnot\lnot\phi$ auf $\phi$ schließen oder von $\phi \to \psi$ und $\lnot \phi \to \psi$ auf $\psi$. \quoteon Die Assoziativität lässt sich also ganz einfach durch eine Wahrheitstafel beweisen, auch wenn es wahrscheinlich eine etwas breite Wahrheitstafel wird. \quoteoff Ja. 8 Zeilen, 7 Spalten. \(\endgroup\)


   Profil
Qing
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 11.03.2022
Mitteilungen: 288
  Beitrag No.16, eingetragen 2022-11-26

\quoteon kannst du mir bitte erklären was "konstruktiver Beweis" bedeutet \quoteoff Oder zu dem was TacTac schon geschrieben hat, bedeutet das wohl, dass ein Beweis die Existenz eines Objektes so beweist, indem man tatsächlich dieses Objekt konstruiert, also einen Algorithmus angibt, den man danach nur noch anwenden muss. Ein Beispiel für einen konstruktiven Beweis ist etwa der chinesische Restsatz. Es gibt aber auch viele Beweise die eben nicht konstruktiv sind. Zum Beispiel wenn das Auswahlaxiom angewendet wird. Das berühmteste Beispiel ist wohl das Banach-Tarski-Paradoxon welches naiv formuliert sagt, dass man eine Orange so zerteilen kann, dass sich die Einzelteile dann wieder so zusammensetzen lassen, dass man am ende zwei Orangen hat. Aber nicht irgendwelche, sondern zweimal genau die gleiche, mit der man angefangen hat (gleiches Gewicht und alles). Man hat die Orange also verdoppelt. Da der Beweis aber nicht konstruktiv ist, kann man in der Realität keine Orangen verdoppeln. Man unterscheidet zwischen Existenzaussagen und schwachen Existenzaussagen. Eine schwache Existenzaussage ist etwa, dass es in Deutschland mit sicherheit zwei Menschen gibt, die gleich viele Haare auf dem Kopf haben. Das kann man leicht mit dem sog. Schubfachprinzip begründen. Man weiß aber nicht welche Menschen gleich viele Haare auf dem Kopf haben. Ein konstruktiver Beweis dieser Aussage wäre, wenn man zwei Menschen und einen Rasierer nimmt, und beiden eine Glatze rasiert...


   Profil
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 1283
Wohnort: Kiel, Deutschland
  Beitrag No.17, eingetragen 2022-11-26

\(\begingroup\)\(\newcommand{\id}{\operatorname{id}}\) Hallo infosoccom, \quoteon(2022-11-26 21:06 - infosoccom in Beitrag No. 13) Leider verstehe ich nicht ganz wie der zweite Teil funktionieren soll. Außerdem weiß ich nicht, was "Klauseln" oder "disjunktive Normalform" im Allgemeinen bedeuten. Könnte ich bitte noch einen weiteren Tipp bekommen oder etwas ausführlicher formuliert bekommen, was genau zu machen ist und wieso es die Assoziativität so beweist. \quoteoff Ich übertrage hier Begriffe aus der Logik in die Mengenlehre, nach der Art \[x\in A\color{red}{\cup} B\quad \Longleftrightarrow\quad x\in A\color{red}{\lor} x\in B\quad.\] In der Logik ist
  • ein Literal eine aussagenlogische Variable oder eine negierte aussagenlogische Variable
  • eine Klausel eine endliche Disjunktion von Literalen
  • eine Klauselmenge eine endliche Konjunktion von Klauseln.
Siehe auch Stückwerk Logik: Konjunktive Normalform, wobei hier noch im Detail anders vorgegangen wird. Ich nenne nun also
  • Literal eine Menge A, B, C oder ein Komplement davon. Beispiel: \(B\)
  • Klausel einen endlichen Durchschnitt von Literalen, der jedes Literal genau einmal enthält. Beispiel: \(A^\complement\cap B^\complement\cap C\)
  • DNF eine endliche Vereinigung von paarweise verschiedenen Klauseln. Beispiel: \((A^\complement\cap B^\complement\cap C)\cup(A^\complement\cap B\cap C)\)
Warum ist dieser Ansatz nun zielführend? Weil er es erlaubt, den Ausdruck \((A\triangle B)\triangle C\) gewissermaßen flachzuklopfen, und weil jedes Literal in jeder Klausel enthalten ist, müssen wir die Buchstaben A, B, C nur geschickt vertauschen und haben dann die Assoziativität direkt dort stehen (es wird hilfreich sein, die Kommutativität von \(\triangle\) im Hinterkopf zu behalten). Führe es selbst einmal durch. mfg thureduehrsen [Die Antwort wurde nach Beitrag No.15 begonnen.]
\(\endgroup\)


   Profil
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 2673
  Beitrag No.18, eingetragen 2022-11-26

\(\begingroup\)\(\newcommand{\sem}[1]{[\![#1]\!]} \newcommand{\name}[1]{\ulcorner#1\urcorner} \newcommand{\upamp}{\mathbin {⅋}} \newcommand{\monus}{\mathbin {∸}}\) @Qing: Die Änderung der verwendeten Logik ist aber essentiell. Aus einem konstruktiven Beweis von $\lnot\forall x.\, \lnot \phi$ kann man im Allgemeinen keinen konstruktiven Beweis von $\exists x. \phi$ basteln, was sehr seltsam wäre, wenn die beiden Aussagen stets äquivalent wären. Sie sind es konstruktiv aber eben nicht (genauer: man kann i.A. konstruktiv nicht beweisen, dass sie es sind). Analoges mit $\lnot(\lnot\phi \land \lnot \psi)$ und $\phi \lor \psi$. Und wenn man den Schritt schon gegangen ist, sind formale Beweise einer Existenzaussage (u.a.) automatisch schon so etwas wie (i.d.R ineffiziente) Algorithmen zum Finden eines Beispiels. Das kennt man als "existence property" (und "disjunction property" für das analoge mit $\lor$).\(\endgroup\)


   Profil
Qing
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 11.03.2022
Mitteilungen: 288
  Beitrag No.19, eingetragen 2022-11-27

@tactac: Danke für die weitere Erläuterung. Der Hauptgrund für das Schreiben meines Beitrages war, dass bei mir der Beitrag in No. 15 ein paar Fragezeichen ausgelöst hat, weshalb ich eine informellere Sichtweise probiert habe.


   Profil
infosoccom
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 19.09.2021
Mitteilungen: 36
  Beitrag No.20, vom Themenstarter, eingetragen 2022-11-27

Großen Dank für die Erklärungen. Die informelle Art des Erklärens hat es nochmal verständlicher gemacht. Bitte entschuldigt zudem meine verzögerte Antwort. Ich habe leider auch andere Module im Studium und es kommen oft Dinge dazwischen. Thureduehrsen ist es bei der Übertragung von Logik in die Mengenlehre zu einer Verwechselung gekommen? Wenn eine Klausel in der Logik eine endliche Disjunktion von Literalen ist, wieso übersetzt es sich dann zu einem Durchschnitt von Literalen in der Mengenlehre anstelle einer Vereinigung von Literalen? Das Gleiche für die Klauselmenge. Könnte ich außerdem bitte eine Rückmeldung für meinen Beitrag No. 10 bekommen also für den Beweis mit der Methode von Qing. Ich würde gerne beide Methoden parallel bearbeiten.


   Profil
Qing
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 11.03.2022
Mitteilungen: 288
  Beitrag No.21, eingetragen 2022-11-27

\quoteon(2022-11-26 17:19 - infosoccom in Beitrag No. 10) Sei also \(x \in A\). 1. Fall: \(x \in C\). Es folgt \(x \in A \cap C\). Nach Definition der symmetrischen Differenz folgt damit \(x \notin A \triangle C\) und als Konsequenz unserer Hypothese \(x \notin B \triangle C\). Wie führe ich den Beweis für den 1.Fall aber fort? \quoteoff Du weißt nun $x\notin B\Delta C$. Da $x\in C$ gilt (in diesem Fall befinden wir uns ja gerade), muss (wegen $x\notin B\Delta C$) bereits $x\in B$ gelten. Das folgt wieder durch abklappern der Definition. Bzw. was ist denn wenn $x\notin B$ gilt? Dann wäre $x\in B\cup C$. (Warum?) und $x\notin B\cap C$. Nach Definition der symmetrischen Differenz also $x\in B\Delta C$, was ja ein Widerspruch dazu ist, dass $x\notin B\Delta C$.


   Profil
infosoccom
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 19.09.2021
Mitteilungen: 36
  Beitrag No.22, vom Themenstarter, eingetragen 2022-11-27

Danke Qing. Ich habe mich einige Minuten nochmal an die Aufgabe gesetzt mit deiner Rückmeldung aber der Aha-Moment wieso jetzt \(x \in B\) ist leider ausgeblieben. Möglicherweise weil es wahrscheinlich schon zu spät ist und meine Denkleistung bereits nachgelassen hat. Ich werde es morgen nochmal versuchen.


   Profil
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 1283
Wohnort: Kiel, Deutschland
  Beitrag No.23, eingetragen 2022-11-27

\(\begingroup\)\(\newcommand{\id}{\operatorname{id}}\) \quoteon(2022-11-27 17:51 - infosoccom in Beitrag No. 20) ist es bei der Übertragung von Logik in die Mengenlehre zu einer Verwechselung gekommen? Wenn eine Klausel in der Logik eine endliche Disjunktion von Literalen ist, wieso übersetzt es sich dann zu einem Durchschnitt von Literalen in der Mengenlehre anstelle einer Vereinigung von Literalen? \quoteoff Das mache ich so, weil der Beweis, den ich vor Augen habe, auf oberster Ebene mit Vereinigungen und auf nächsttieferer Ebene mit Durchschnitten arbeitet und weil der verlinkte Stückwerk-Artikel die KNF anstelle der DNF behandelt. Letzteres hat aber algorithmisch-technische Gründe und keine "innermathematischen". Ich will hier einfach nur Begriffe zur Verfügung haben, damit ich mich beim Erklären leichter tue. Mir ist bewusst, dass ich die Begriffe hier nicht standardkonform verwende. Übersetze also \((A\triangle B)\triangle C\) in "meine" DNF und schaue dann einmal scharf hin. mfg thureduehrsen\(\endgroup\)


   Profil
infosoccom
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 19.09.2021
Mitteilungen: 36
  Beitrag No.24, vom Themenstarter, eingetragen 2022-11-28

Ich versuche zunächst den Beweis aus Beitrag No. 21 fortzuführen. Wir beweisen \(A \subseteq B\): Sei \(x \in A\) beliebig aber fest gewählt. Es lassen sich zwei Fälle unterscheiden: 1. Fall: \(x \in C\) 2. Fall: \(x \notin C\) Außerdem gilt: \(A \triangle C = (A \cup C) \setminus (A \cap C)\) 1. Fall: \(x \in A \cap C \Rightarrow x \notin A \triangle C \Rightarrow x \notin B \triangle C\) Da wir wissen, dass \(x \notin B \triangle C\) und \(A \triangle C = B \triangle C\) muss gelten, dass \(x \in B \cap C\). Es folgt also: \(x \in A \Rightarrow x \in B \cap C \Rightarrow x \in B\) Analoge Vorgehensweise für \(B \subseteq A\) im 1. Fall 2. Fall: \(x \in A \Rightarrow x \notin A \cap C\\ \ \ \ \ \ \ \ \ \ \ \Rightarrow x \in (A \cup C) \setminus (A \cap C)\\ \ \ \ \ \ \ \ \ \ \ \Rightarrow x \in A \triangle C\\ \ \ \ \ \ \ \ \ \ \ \Rightarrow x \in B \triangle C \ \ \ (wegen\ Annahme)\\ \ \ \ \ \ \ \ \ \ \ \Rightarrow x \in (B \cup C) \setminus (B \cap C)\\ \ \ \ \ \ \ \ \ \ \ \Rightarrow x \in B \ \ \ (da \ x \notin C) \) Analoge Vorgehensweise für \(B \subseteq A\) im 2. Fall Für beide Fälle ist damit \(A \subseteq B\) bzw. \(B \subseteq A\) bewiesen und damit \(A = B\). Setzen wir: \(A \triangle C = B \triangle C\) daher als wahr voraus, so folgt jedes mal \(A = B\) für beliebe Mengen A, B und C. Wäre der Beweis auf diese Weise richtig, zufriedenstellend und vollständig? Außerdem bezüglich der anderen Methode: Danke für die Klarstellung thureduehrsen. Die Assoziativität der symmetrischen Differenz zu beweisen werde ich nach dieser Methode fortführen. Kann man Leute hier benachrichtigen, wenn man @ vor ihrem Namen setzt?


   Profil
infosoccom
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 19.09.2021
Mitteilungen: 36
  Beitrag No.25, vom Themenstarter, eingetragen 2022-11-28

Vielleicht nochmal eine Klarstellung zum 1. Fall: Es ist mir gerade bewusst geworden, dass: \(x \in B \triangle C \Leftrightarrow x \in B \ \dot\lor \ x \in C\) ja äquivalent sind. Wenn also \(x \notin B\) gelten würde (und im 1. Fall ist ja \(x \in C\) wahr), dann wäre \(x \in B \triangle C\) wahr und dies widerspricht \(x \notin B \triangle C\), denn eine Aussage A und ihre Negation können nicht gleichzeitig wahr sein: \(A \land \lnot A \Leftrightarrow f\)


   Profil
infosoccom hat die Antworten auf ihre/seine Frage gesehen.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]