in DNF/ KNF umformen < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Formen Sie die folgende Formel zu einer äquivalenten Formel in disjunkter Normalform (DNF) um:
(a) (A->B)->((B->C)->(A->C))
(b) ((A->B)->(B->C))->(A->C)
und geben sie zu folgender Formel die KNF an:
(c) [mm] (A<->B)<->\neg [/mm] C |
Hallo!
Ich habe mich im Internet zu den Umformungen belesen und folgende Regeln rausgefunden:
DNF: [mm] A->B=\neg [/mm] A [mm] \vee [/mm] B; A<->B=(A [mm] \wedge [/mm] B) [mm] \vee (\neg [/mm] A [mm] \wedge \neg [/mm] B)
KNF: A<->=(A->B) [mm] \wedge (B->A)=(\neg [/mm] A [mm] \vee [/mm] B) [mm] \wedge (\neg [/mm] B [mm] \vee [/mm] A)
Gibt es noch weitere Regeln, die man für die Umformung brauchen könnte?
Ich habe jetzt zu der Aufgabe folgende Lösungen:
(a) (A [mm] \vee \neg [/mm] B) [mm] \vee [/mm] ((B [mm] \vee \neg [/mm] C) [mm] \vee (\neg [/mm] A [mm] \vee [/mm] C))
(b) [mm] ((\neg [/mm] A [mm] \vee [/mm] B) [mm] \vee [/mm] (B [mm] \vee \neg [/mm] C)) [mm] \vee (\neg [/mm] A [mm] \vee [/mm] C)
(c) ((A->B) [mm] \wedge [/mm] (B->A)) -> [mm] \neg [/mm] C [mm] \wedge (\neg [/mm] C -> ((A->B) [mm] \wedge [/mm] (B->A))
Stimmt das so?
Was ist eigentlich der Unterscheid zwischen einer DNF/KNF und einer vollständigen DNF/KNF? Und wie schreibt man eine DNF/KNF als Klauselmenge auf?
Danke schonmal für´s kontrollieren und so!
Lg, Jennymaus
|
|
| |
|
Hallo Jennymaus!
> Formen Sie die folgende Formel zu einer äquivalenten Formel
> in disjunkter Normalform (DNF) um:
> (a) (A->B)->((B->C)->(A->C))
> (b) ((A->B)->(B->C))->(A->C)
> und geben sie zu folgender Formel die KNF an:
> (c) [mm](A<->B)<->\neg[/mm] C
Wenn du unseren Formeleditor benutzt, sieht das ganze noch schöner aus. 
> Hallo!
> Ich habe mich im Internet zu den Umformungen belesen und
> folgende Regeln rausgefunden:
> DNF: [mm]A->B=\neg[/mm] A [mm]\vee[/mm] B; A<->B=(A [mm]\wedge[/mm] B) [mm]\vee (\neg[/mm] A
> [mm]\wedge \neg[/mm] B)
> KNF: A<->=(A->B) [mm]\wedge (B->A)=(\neg[/mm] A [mm]\vee[/mm] B) [mm]\wedge (\neg[/mm]
> B [mm]\vee[/mm] A)
> Gibt es noch weitere Regeln, die man für die Umformung
> brauchen könnte?
Ich würde sagen, du kannst alle ![[]](/images/popup.gif) Booleschen Gesetze dafür benutzen und auch brauchen. Kommt halt auf deine Ausgangsterme an - abgesehen davon sollten einem die Gesetze irgendwann so in Fleisch und Blut übergehen, dass man gar nicht mehr weiß, welches Gesetz das jetzt eigentlich ist.
> Ich habe jetzt zu der Aufgabe folgende Lösungen:
> (a) (A [mm]\vee \neg[/mm] B) [mm]\vee[/mm] ((B [mm]\vee \neg[/mm] C) [mm]\vee (\neg[/mm] A
> [mm]\vee[/mm] C))
Hab' ich auch raus. ![[daumenhoch]](/images/smileys/daumenhoch.gif "[daumenhoch]") Allerdings kannst du dir die Klammern sparen, und dann kannst du es noch weiter vereinfachen. Da kommt allerdings raus, dass das ganze immer wahr ist, naja, und "1" sieht nicht mehr so schön nach DNF aus. 
> (b) [mm]((\neg[/mm] A [mm]\vee[/mm] B) [mm]\vee[/mm] (B [mm]\vee \neg[/mm] C)) [mm]\vee (\neg[/mm] A
> [mm]\vee[/mm] C)
Hab' ich auch raus. Auch das könnte man noch vereinfachen, aber so sieht's mehr nach DNF aus.
> (c) ((A->B) [mm]\wedge[/mm] (B->A)) -> [mm]\neg[/mm] C [mm]\wedge (\neg[/mm] C ->
> ((A->B) [mm]\wedge[/mm] (B->A))
Das ist doch aber keine KNF!?
> Stimmt das so?
> Was ist eigentlich der Unterscheid zwischen einer DNF/KNF
> und einer vollständigen DNF/KNF? Und wie schreibt man eine
> DNF/KNF als Klauselmenge auf?
Ich weiß leider gerade nicht, wie eine vollständige DNF/KNF definiert ist, hast du das vielleicht irgendwo stehen? Ich glaube, das ist so was wie, dass wirklich jede Klausel die Form [mm] $(A\vee [/mm] B)$ bzw. [mm] $(A\wedge [/mm] B)$ hat, theoretisch kann ja bei der normalen DNF/KNF eine Variable einzeln als Klausel dort stehen, also z. B. ist [mm] $(A\vee B)\wedge [/mm] C$ ja eine KNF, aber C hat nicht die Form (irgendwas [mm] \vee [/mm] irgendwasanderes), und damit wäre es nicht vollständig. Bin mir da aber im Moment nicht sicher, ob das wirklich so definiert ist.
Und was verstehst du unter einer Klauselmenge?
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
Hallo!
Danke!
Wie könnte man denn die Ergebnisse (a) und (b) noch vereinfachen?
Zur (c) habe ich jetzt die Wahrheitstabelle aufgestellt und daraus die KNF abgelesen und habe raus: (A [mm] \vee [/mm] B [mm] \vee \neg [/mm] C) [mm] \vee [/mm] (A [mm] \vee \neg [/mm] B [mm] \vee [/mm] C) [mm] \vee (\neg [/mm] A [mm] \vee [/mm] B [mm] \vee [/mm] C) [mm] \vee (\neg [/mm] A [mm] \vee \neg [/mm] B [mm] \vee \neg [/mm] C). Stimmt das?
Die Klauselmenge wäre meiner Meinung nach dazu: {{ [mm] A,B,\neg [/mm] C },{ [mm] A,\neg [/mm] B,C },{ [mm] \neg [/mm] A,B,C },{ [mm] \neg A,\neg B,\neg [/mm] C }}. Richtig? Also zumindest haben wir das mal in einer Übungsaufgabe gemacht (wenn ich das richtig nachvollzogen habe).
Das mit der vollständigen DNF/KNF hatte ich auf irgend einer Internetseite gelesen. Scheint aber eh unwichtig zu sein, da es in meiner Vorlesung nicht behandelt wurde.
Lg, Jennymaus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:21 Do 15.02.2007 | | Autor: | Bastiane |
Hallo Jennymaus!
> Wie könnte man denn die Ergebnisse (a) und (b) noch
> vereinfachen?
Wie gesagt, erst die Klammern weg, und dann gilt doch [mm] $A\vee\neg [/mm] A$=1$ usw.
> Zur (c) habe ich jetzt die Wahrheitstabelle aufgestellt
> und daraus die KNF abgelesen und habe raus: (A [mm]\vee[/mm] B [mm]\vee \neg[/mm]
> C) [mm]\vee[/mm] (A [mm]\vee \neg[/mm] B [mm]\vee[/mm] C) [mm]\vee (\neg[/mm] A [mm]\vee[/mm] B [mm]\vee[/mm] C)
> [mm]\vee (\neg[/mm] A [mm]\vee \neg[/mm] B [mm]\vee \neg[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
C). Stimmt das?
Das ist noch immer keine KNF. Abgesehen davon weiß ich nicht, ob es Sinn der Aufgabe war, das mit einer Wahrheitstabelle zu machen. Benutze doch einfach die Booleschen Regeln.
> Die Klauselmenge wäre meiner Meinung nach dazu: {{ [mm]A,B,\neg[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
> C },{ [mm]A,\neg[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
B,C },{ [mm]\neg[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
A,B,C },{ [mm]\neg A,\neg B,\neg[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
C
> }}. Richtig? Also zumindest haben wir das mal in einer
> Übungsaufgabe gemacht (wenn ich das richtig nachvollzogen
> habe).
Wie gesagt, ich habe keine Ahnung, was du mit Klauselmenge meinst.
Viele Grüße
Bastiane
|
|
|
| |
|
Hallo!
Zu (c): Ich hatte mich geirrt beim Aufschreiben der KNF...Zwischen den Klammern muss immer [mm] \wedge [/mm] stehen...dann stimmts, oder?
Ich hab die KNF auch mal durch umschreiben erstellt und habe bekommen: (((A [mm] \vee \neg [/mm] B) [mm] \wedge [/mm] (B [mm] \vee \neg [/mm] A)) [mm] \vee \neg [/mm] C) [mm] \wedge [/mm] ( C [mm] \vee [/mm] ( ( [mm] \neg [/mm] A [mm] \vee [/mm] B) [mm] \wedge [/mm] ( [mm] \neg [/mm] B [mm] \vee [/mm] A))).
Wenn man [mm] \neg [/mm] (A [mm] \vee [/mm] B) hat, wird das dann zu [mm] (\neg [/mm] A [mm] \vee \neg [/mm] B) oder wird aus dem [mm] \vee [/mm] auch noch ein [mm] \wedge?
[/mm]
Lg, Claudi
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:20 Di 20.02.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
