Disjunktive Normalform < Aussagenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:26 Sa 28.04.2012 | | Autor: | durden88 |
| Aufgabe | Bilde die disjunktive Normalform von:
[mm] (A->(B->C))\vee ((A<->B)\vee [/mm] C) |
Hallo liebe Leute,
also ich habe eine Frage zur disjunktiven Normalform. Also bei dieser Aufgabe habe ich die konjunktive Normalform bilden können. Bei der disjunktiven Normalform bin ich mir sehr unsicher und ich komme da auch auf kein richtig gutes Ergebnis. Ich habe alle äuivalenzpfeile aufgedröselt und kam dann auf folgende Gleichung:
[mm] (\neg [/mm] A [mm] \vee (\neg [/mm] B [mm] \vee [/mm] C)) [mm] \vee (((\neg A\vee B)\wedge (\neg [/mm] B [mm] \vee [/mm] A)) [mm] \vee [/mm] C)
Und ich habe im Gefühl das danach der entscheidende Schritt kommt: Wenn ich jetzt weiter machen würde, um auf die konjunktive Normalform zu kommen, würde ich das C distributiv einbeziehen und dann das [mm] (\neg [/mm] A [mm] (\neg [/mm] B [mm] \vee [/mm] C) genauso. Aber ich komme Patu nicht auf die Form [mm] (\delta \wedge ....\wedge delta)\vee...\vee(\delta \wedge....\wedge \delta). [/mm] Also woran erkenne ich, wie ich auf die disjunktive Normalform kommen kann? Weil für die konjunktive hab ich nen Algorithmus....
Ich habe zwei Onlinesoftware-Löser, und bei dem einen kommt als Ergbnis:
[mm] \neg [/mm] A v [mm] \neg [/mm] B v C v (A & B) v [mm] (\neg [/mm] A [mm] \wedge \neg [/mm] B) v C
Bei dem anderen kommt: [mm] \neg [/mm] A [mm] \vee(\neg [/mm] B [mm] \vee C)\vee (A\wedge B\vee \neg [/mm] A [mm] \wedge \neg [/mm] B [mm] \vee [/mm] C)
Das hat aber nicht die Form die ich da als Definition habe. Außerdem sag der erste Plotter: [mm] (A<->B)=(\neg [/mm] A [mm] \wedge \neg [/mm] B) [mm] \vee [/mm] (A [mm] \wedge [/mm] B). Das hab ich auch noch nicht gekannt, das gilt auch?
So ich hoffe mir kein da einer weiter helfen sodass ich auch das bald mal behersche :) Danke im Voraus!
|
|
| |
|
Also: Was der este Plotter sagt stimmt.
(A [mm] \equiv [/mm] B)
[mm] \gdw [/mm] ( A [mm] \Rightarrow [/mm] B) [mm] \wedge [/mm] ( B [mm] \Rightarrow [/mm] A)
[mm] \gdw (\neg [/mm] A [mm] \vee [/mm] B) [mm] \wedge (\neg [/mm] B [mm] \vee [/mm] A)
(Dann zweimal Assoziativgestez)
[mm] \gdw (\neg [/mm] A [mm] \wedge (\neg [/mm] B [mm] \vee [/mm] A)) [mm] \vee [/mm] (B [mm] \wedge (\neg [/mm] B [mm] \vee [/mm] A))
[mm] \gdw ((\neg [/mm] A [mm] \wedge \neg [/mm] B) [mm] \vee (\neg [/mm] A [mm] \wedge [/mm] A)) [mm] \vee [/mm] ((B [mm] \wedge \neg [/mm] B) [mm] \vee [/mm] (B [mm] \wedge [/mm] A))
[mm] \gdw [/mm] ( [mm] \neg [/mm] A [mm] \wedge \neg [/mm] B) [mm] \vee [/mm] (B [mm] \wedge [/mm] A)
Und wenn ddas bei deinem Ansatz benutzt, müsstest du leicht auf die disjunkte Normalform kommen. ( wie bei ersten Plotter)
Gruß
ConstantinJ
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:19 So 29.04.2012 | | Autor: | durden88 |
> Also: Was der este Plotter sagt stimmt.
>
> (A [mm]\equiv[/mm] B)
> [mm]\gdw[/mm] ( A [mm]\Rightarrow[/mm] B) [mm]\wedge[/mm] ( B [mm]\Rightarrow[/mm] A)
> [mm]\gdw (\neg[/mm] A [mm]\vee[/mm] B) [mm]\wedge (\neg[/mm] B [mm]\vee[/mm] A)
> (Dann zweimal Assoziativgestez)
> [mm]\gdw (\neg[/mm] A [mm]\wedge (\neg[/mm] B [mm]\vee[/mm] A)) [mm]\vee[/mm] (B [mm]\wedge (\neg[/mm] B
> [mm]\vee[/mm] A))
Ne das check ich nicht: Assoziativgesetzt heißt doch: ((φ [mm] \wedge [/mm] ψ) [mm] \wedge [/mm] δ) ≡ (φ [mm] \wedge [/mm] (ψ [mm] \wedge [/mm] δ))
Gilt die Regel immer, dass ( [mm] Y<->\delta)=(y \wedge \delta)\vee (\neg [/mm] Y [mm] \wedge \neg \delta)?
[/mm]
> [mm]\gdw ((\neg[/mm] A [mm]\wedge \neg[/mm] B) [mm]\vee (\neg[/mm] A [mm]\wedge[/mm] A)) [mm]\vee[/mm]
> ((B [mm]\wedge \neg[/mm] B) [mm]\vee[/mm] (B [mm]\wedge[/mm] A))
> [mm]\gdw[/mm] ( [mm]\neg[/mm] A [mm]\wedge \neg[/mm] B) [mm]\vee[/mm] (B [mm]\wedge[/mm] A)
>
> Und wenn ddas bei deinem Ansatz benutzt, müsstest du
> leicht auf die disjunkte Normalform kommen. ( wie bei
> ersten Plotter)
>
> Gruß
> ConstantinJ
>
Falls ich dann weiter Rechne, komme ich ja dann auf die Form, die mir der Plotter auch ausgespuckt hat: [mm] (\neg [/mm] A [mm] \vee(\neg [/mm] B [mm] \vee [/mm] C)) [mm] \vee [/mm] ((( [mm] \neg [/mm] A [mm] \wedge \neg B)\vee [/mm] (B [mm] \wedge [/mm] A) [mm] \vee [/mm] C)). Auf der linken Seite habe ich aber drei oder-Verknüfungen die wiederum mit einer oder-Verknüfung mit einer disjunktiven Normalform zusammen hängen. Habe aber gedacht, es müssten immer zusammengeknüpfte ´´Und´´ Formeln mit oder zusammen gesetzt werden und nicht drei atomare Formeln mit der disjunktiven Formel. Also wieso ist das schon die disjunktive Normalform?
|
|
|
| |
|
>Ne das check ich nicht: Assoziativgesetzt heißt doch: ((φ $ [mm] \wedge [/mm] $ ψ) $ [mm] \wedge [/mm] $ δ) ≡ (φ $ [mm] \wedge [/mm] $ (ψ $ [mm] \wedge [/mm] $ δ))
Entschuldigung: Das war das Distributivgesetz von [mm] \vee und\wedge.
[/mm]
>Gilt die Regel immer, dass ( $ [mm] Y<->\delta)=(y \wedge \delta)\vee (\neg [/mm] $ Y $ [mm] \wedge \neg \delta)? [/mm] $
Hier gilt keine Gleichheit, sondern logische Äquivalenz.
Aber das gilt natürlich immer.
>Falls ich dann weiter Rechne, komme ich ja dann auf die Form, die mir der Plotter auch ausgespuckt hat: $ [mm] (\neg [/mm] $ A $ [mm] \vee(\neg [/mm] $ B $ [mm] \vee [/mm] $ C)) $ [mm] \vee [/mm] $ ((( $ [mm] \neg [/mm] $ A $ [mm] \wedge \neg B)\vee [/mm] $ (B $ [mm] \wedge [/mm] $ A) $ [mm] \vee [/mm] $ C))
Hier gilt:
$ [mm] (\neg [/mm] $ A $ [mm] \vee(\neg [/mm] $ B $ [mm] \vee [/mm] $ C)) $ [mm] \vee [/mm] $ ((( $ [mm] \neg [/mm] $ A $ [mm] \wedge \neg B)\vee [/mm] $ (B $ [mm] \wedge [/mm] $ A) $ [mm] \vee [/mm] $ C))
[mm] \gdw [/mm] $ [mm] \neg [/mm] $ A $ [mm] \vee \neg [/mm] $ B $ [mm] \vee [/mm] $ C $ [mm] \vee [/mm] $ ( $ [mm] \neg [/mm] $ A $ [mm] \wedge \neg B)\vee [/mm] $ (B $ [mm] \wedge [/mm] $ A) $ [mm] \vee [/mm] $ C
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:42 So 29.04.2012 | | Autor: | durden88 |
> >Ne das check ich nicht: Assoziativgesetzt heißt doch:
> ((φ [mm]\wedge[/mm] ψ) [mm]\wedge[/mm] δ) ≡ (φ [mm]\wedge[/mm] (ψ [mm]\wedge[/mm] δ))
>
> Entschuldigung: Das war das Distributivgesetz von [mm]\vee und\wedge.[/mm]
>
> >Gilt die Regel immer, dass ( [mm]Y<->\delta)=(y \wedge \delta)\vee (\neg[/mm]
> Y [mm]\wedge \neg \delta)?[/mm]
>
> Hier gilt keine Gleichheit, sondern logische Äquivalenz.
> Aber das gilt natürlich immer.
>
> >Falls ich dann weiter Rechne, komme ich ja dann auf die
> Form, die mir der Plotter auch ausgespuckt hat: [mm](\neg[/mm] A
> [mm]\vee(\neg[/mm] B [mm]\vee[/mm] C)) [mm]\vee[/mm] ((( [mm]\neg[/mm] A [mm]\wedge \neg B)\vee[/mm] (B
> [mm]\wedge[/mm] A) [mm]\vee[/mm] C))
>
> Hier gilt:
> [mm](\neg[/mm] A [mm]\vee(\neg[/mm] B [mm]\vee[/mm] C)) [mm]\vee[/mm] ((( [mm]\neg[/mm] A [mm]\wedge \neg B)\vee[/mm]
> (B [mm]\wedge[/mm] A) [mm]\vee[/mm] C))
> [mm]\gdw[/mm] [mm]\neg[/mm] A [mm]\vee \neg[/mm] B [mm]\vee[/mm] C [mm]\vee[/mm] ( [mm]\neg[/mm] A [mm]\wedge \neg B)\vee[/mm]
> (B [mm]\wedge[/mm] A) [mm]\vee[/mm] C
>
Ja aber schau, da hast du auf der linken Seite nur atomare Formeln die mit oder verknüpft sind. Bei der disjunktiven Normalform müssen aber doch gelten: [mm] (\delta \wedge...\wedge \delta) \vee (\delta \wedge [/mm] ... [mm] \wedge \delta) [/mm] , oder ist (A [mm] \vee [/mm] B [mm] \vee [/mm] C) auch eine disjunktive Normalform?
|
|
|
| |
|
Ja aber schau, da hast du auf der linken Seite nur atomare Formeln die mit oder verknüpft sind. Bei der disjunktiven Normalform müssen aber doch gelten: $ [mm] (\delta \wedge...\wedge \delta) \vee (\delta \wedge [/mm] $ ... $ [mm] \wedge \delta) [/mm] $ , oder ist (A $ [mm] \vee [/mm] $ B $ [mm] \vee [/mm] $ C) auch eine disjunktive Normalform?
Ja.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:57 So 29.04.2012 | | Autor: | durden88 |
Meine Welt bricht aus einander, also ist (A [mm] \wedge [/mm] B [mm] \wedge [/mm] C [mm] \wedge [/mm] D) auch eine konjunktive Normalform und (A [mm] \vee [/mm] B [mm] \vee [/mm] C [mm] \vee [/mm] D) eine disjunktive Normalform?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:15 So 29.04.2012 | | Autor: | felixf |
Moin!
> Meine Welt bricht aus einander, also ist (A [mm]\wedge[/mm] B [mm]\wedge[/mm]
> C [mm]\wedge[/mm] D) auch eine konjunktive Normalform und (A [mm]\vee[/mm] B
> [mm]\vee[/mm] C [mm]\vee[/mm] D) eine disjunktive Normalform?
Nicht wirklich.
Den Term $A$ in der "KNF" muss man ersetzen durch $(A [mm] \vee [/mm] B [mm] \vee [/mm] C [mm] \vee [/mm] D) [mm] \wedge [/mm] (A [mm] \vee \overline{B} \vee [/mm] C [mm] \vee [/mm] D) [mm] \wedge [/mm] (A [mm] \vee [/mm] B [mm] \vee \overline{C} \vee [/mm] D) [mm] \wedge [/mm] (A [mm] \vee \overline{B} \vee \overline{C} \vee [/mm] D) [mm] \wedge [/mm] (A [mm] \vee [/mm] B [mm] \vee [/mm] C [mm] \vee \overline{D}) \wedge [/mm] (A [mm] \vee \overline{B} \vee [/mm] C [mm] \vee \overline{D}) \wedge [/mm] (A [mm] \vee [/mm] B [mm] \vee \overline{C} \vee \overline{D}) \wedge [/mm] (A [mm] \vee \overline{B} \vee \overline{C} \vee \overline{D})$.
[/mm]
Den Term $A$ in der "DNF" muss man ersetzen durch $(A [mm] \wedge [/mm] B [mm] \wedge [/mm] C [mm] \wedge [/mm] D) [mm] \vee [/mm] (A [mm] \wedge \overline{B} \wedge [/mm] C [mm] \wedge [/mm] D) [mm] \vee [/mm] (A [mm] \wedge [/mm] B [mm] \wedge \overline{C} \wedge [/mm] D) [mm] \vee [/mm] (A [mm] \wedge \overline{B} \wedge \overline{C} \wedge [/mm] D) [mm] \vee [/mm] (A [mm] \wedge [/mm] B [mm] \wedge [/mm] C [mm] \wedge \overline{D}) \vee [/mm] (A [mm] \wedge \overline{B} \wedge [/mm] C [mm] \wedge \overline{D}) \vee [/mm] (A [mm] \wedge [/mm] B [mm] \wedge \overline{C} \wedge \overline{D}) \vee [/mm] (A [mm] \wedge \overline{B} \wedge \overline{C} \wedge \overline{D})$.
[/mm]
Im Endeffekt kann man wieder etwas zusammenfassen (da manche der Terme mehrmals vorkommen), aber die eigentliche KNF bzw. DNF wird schon etwas komplizierter...
LG Felix
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:19 So 29.04.2012 | | Autor: | tobit09 |
> Meine Welt bricht aus einander, also ist (A [mm]\wedge[/mm] B [mm]\wedge[/mm]
> C [mm]\wedge[/mm] D) auch eine konjunktive Normalform und (A [mm]\vee[/mm] B
> [mm]\vee[/mm] C [mm]\vee[/mm] D) eine disjunktive Normalform?
Aus meiner Sicht sind das entsprechende Normalformen. Nehmen wir das erste Beispiel [mm] $(A\wedge [/mm] B [mm] \wedge [/mm] C [mm] \wedge [/mm] D)$: A, B, C und D bilden jeweils eine Disjunktion von Literalen mit nur einem Literal.
Die Formel ist sogar gleichzeitig in disjunktiver Normalform: [mm] $(A\wedge [/mm] B [mm] \wedge [/mm] C [mm] \wedge [/mm] D)$ ist eine Disjunktion von Konjunktionen von Literalen mit nur einer Konjunktion (von 4 Literalen).
@Felix: Du gehst anscheinend z.B. bei der konjunktiven Normalform von der Definition aus, die bei ![[]](/images/popup.gif) Wikipedia als kanonische konjunktive Normalform bezeichnet wird. Bei durden (mir liegt sein/ihr Skript vor) wird jedoch nicht verlangt, dass in jedem Disjunktionsterm alle Aussagevariablen vorkommen.
|
|
|
| |
|
ok vielen Dank für die Antworten. Also ich habe noch zwei Fragen zu dem ganzen:
Ich kenne nur die Regeln zum ausdrösen von (A->B)= [mm] (\neg [/mm] A [mm] \vee [/mm] B) und (A<->B)= (A->B) [mm] \wedge [/mm] (B->A) und jetzt neuerdings auch das (A<->B)= [mm] (\neg [/mm] A [mm] \wedge \neg B)\vee [/mm] (A [mm] \wedge [/mm] B) ist.
Auf das letzte wär ich nie gekommen und auch die Herleitung habe ich gerade erst verstanden . Gibt es noch weitere solcher ´´wichtigen´´ Regeln, oder waren das die wichtigsten die ich mit dem Distributivgesetz kennen muss?
2) Ich hab für die KNF einen Algorithmus den ich anwende, also da hab ich keine Probleme mit auf eine Endform zu kommen. Wie ist das denn mit der DNF? Gibt es da irgendwelche Anhaltspunkte ab wann ich danach auflösen kann? Ich hatte so im Gefühl, ab dem Zeitpunkt wo ich ein Distributivgesetz anwende oder so...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:01 So 29.04.2012 | | Autor: | tobit09 |
Deine eigentlichen Fragen hier kann ich leider nicht befriedigend beantworten. Aber folgender Hinweis:
Es gibt Algorithmen für die Ermittlung einer konjunktiven bzw. disjunktiven Normalform, die mit Wahrheitstafeln arbeiten und völlig ohne Formelumformungen auskommen. Sie sind z.B. bei Wikipedia unter "Beispiel für die Bildung" an einem Beispiel vorgeführt.
(Vielleicht solltest du, bevor du diese Algorithmen in einer Klausur verwendest, jemanden fragen, ob das für die Klausur ok ist oder ob Formelumformungen gefordert werden.)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:22 Di 01.05.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 07:48 So 29.04.2012 | | Autor: | tobit09 |
Hallo durden,
> Außerdem sag der erste Plotter: [mm](A<->B)=(\neg[/mm] A [mm]\wedge \neg[/mm] B) [mm]\vee[/mm] (A [mm]\wedge[/mm] B).
> Das hab ich auch noch nicht gekannt, das gilt auch?
Ja.
Die Formel $(A<->B)$ sagt anschaulich aus, dass A und B den gleichen Wahrheitswert haben. Mit anderen Worten: A und B haben beide Wahrheitswert "falsch" oder beide Wahrheitswert "wahr". Letzteres sagt die Formel [mm](\neg A \wedge \neg B) \vee (A \wedge B)[/mm] aus.
Formal kannst du dir die Äquivalenz der beiden Formeln anhand einer Wahrheitstafel verifizieren.
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 12:21 So 29.04.2012 | | Autor: | durden88 |
> >Also: Was der este Plotter sagt stimmt.
> >
> > (A [mm]\equiv[/mm] B)
> > [mm]\gdw[/mm] ( A [mm]\Rightarrow[/mm] B) [mm]\wedge[/mm] ( B [mm]\Rightarrow[/mm] A)
> > [mm]\gdw (\neg[/mm] A [mm]\vee[/mm] B) [mm]\wedge (\neg[/mm] B [mm]\vee[/mm] A)
> > (Dann zweimal Assoziativgestez)
> > [mm]\gdw (\neg[/mm] A [mm]\wedge (\neg[/mm] B [mm]\vee[/mm] A)) [mm]\vee[/mm] (B [mm]\wedge (\neg[/mm] B
> > [mm]\vee[/mm] A))
>
Ne das check ich nicht: Assoziativgesetzt heißt doch: ((φ
[mm]\wedge[/mm] ψ) [mm]\wedge[/mm] δ) ≡ (φ [mm]\wedge[/mm] (ψ [mm]\wedge[/mm] δ))
Gilt die Regel immer, dass ( [mm]Y<->\delta)=(y \wedge \delta)\vee (\neg[/mm]
Y [mm]\wedge \neg \delta)?[/mm]
> > [mm]\gdw ((\neg[/mm] A [mm]\wedge \neg[/mm] B)
> [mm]\vee (\neg[/mm] A [mm]\wedge[/mm] A)) [mm]\vee[/mm]
> > ((B [mm]\wedge \neg[/mm] B) [mm]\vee[/mm] (B [mm]\wedge[/mm] A))
> > [mm]\gdw[/mm] ( [mm]\neg[/mm] A [mm]\wedge \neg[/mm] B) [mm]\vee[/mm] (B [mm]\wedge[/mm] A)
Falls ich dann weiter Rechne, komme ich ja dann auf die
Form, die mir der Plotter auch ausgespuckt hat: [mm](\neg[/mm] A
[mm]\vee(\neg[/mm] B [mm]\vee[/mm] C)) [mm]\vee[/mm] ((( [mm]\neg[/mm] A [mm]\wedge \neg B)\vee[/mm] (B [mm]\wedge[/mm] A) [mm]\vee[/mm] C)). Auf der linken Seite habe ich aber drei
oder-Verknüfungen die wiederum mit einer oder-Verknüfung
mit einer disjunktiven Normalform zusammen hängen. Habe
aber gedacht, es müssten immer zusammengeknüpfte
´´Und´´ Formeln mit oder zusammen gesetzt werden und
nicht drei atomare Formeln mit der disjunktiven Formel.
Also wieso ist das schon die disjunktive Normalform?
|
|
|
|
