Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Disjunktive Normalform
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> Disjunktive Normalform
 
Autor Nachricht
Gast220001
Gast






BeitragVerfasst am: 14 Nov 2004 - 14:14:01    Titel: Disjunktive Normalform

Hi,

ich soll folgenden Ausdruck in die disjunktive Normalform bringen (- soll der Negationsoperator sein):

f(a,b,c,d) = (c AND -a) OR (d AND -c AND -b) OR(-d AND b AND -a)
OR (-d AND -c AND b AND -a)

Wenn ich wie in der Vorlesung eine Wertetabelle habe, in der alle Variablen immer vorkommen, dann ists kein Problem. Nur kommen in dem Term aus der Aufgabe nicht immer alle Variablen vor, das ist der Knackpunkt. Kann mir vielleicht jemand erklären, wie ich aus diesem Ausdruck in die disjunktive Normalform komme?

Ciao
Thorsten
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 14 Nov 2004 - 16:34:47    Titel:

Wenn das schon auf diesem Niveau gemacht werden soll, dann erstelle doch deine Wertetabelle einfach durch Auswerten des gesamten Ausdruckes an allen 16 Stellen. Und dann hast Du ja nach deiner Methode alles. Was ist das Problem?
Weyoun
Gast






BeitragVerfasst am: 14 Nov 2004 - 16:46:39    Titel:

Also eine Formel F ist genau dann in DNF, wenn
* keine Junkoren ausser UND, NICHT und NICHT mehr vorkommen
* jede Teilformel von F mit Hauptoperator NICHT als (echte) Teilformel genau eine atomare Formel hat
* keine Teilformel von F mit Hauptoperator UND ein ODER enthält

Es gibt ein allgemeines Verfahren, das immer Erfolg hat:


0) Ersetze alle Teilformeln der Form
(G <-> H) durch (-G ODER H) UND (G ODER -H)
(G --> H) durch (-G ODER H)

1) Ersetze alle Teilformeln der Form
--G durch G
-(G UND H) durch (-G ODER -H)
-(G ODER H) durch (-G UND -H)

2a) Für KNF: Ersetze alle Teilformeln der Form
(F ODER (G UND H)) durch (F ODER G) UND (F ODER H)
((F UND G) ODER H) durch (F ODER H) UND (G ODER H)
["Treibe Disjunktionen nach innen und Konjunktionen nach außen!"]

2b) Für DNF: Ersetze alle Teilformeln der Form
(F UND (G ODER H)) durch (F UND G) ODER (F UND H)
((F ODER G) UND H) durch (F UND H) ODER (G UND H)
["Treibe Konjunktionen nach innen und Disjukntionen nach außen!"]


Ist das Verfahren korrekt angewandt worden, liefert es stets eine Normalform. Von den einzelnen Äquivalenzen kann man sich klassisch per Wahrheitstabelle überzeugen!

Hoffe, geholfen zu haben...
Gast220001T
Gast






BeitragVerfasst am: 14 Nov 2004 - 16:47:08    Titel:

das problem ist, dass ich

1. für eine Wertetabelle keine Zeit hab
2. die Wertetabelle mit steigender Anzahl an Variablen exponentiell wächst

Und was meinst du mit "auf diesem Niveau"?

Ich möchte es einfach mal schrittweise erklärt bekommen, wie ich von so einem Ausdruck auf die disjunktive Normalform komme, mehr nicht.
Weyoun
Gast






BeitragVerfasst am: 14 Nov 2004 - 16:47:56    Titel:

* keine Junkoren ausser UND, ODER und NICHT mehr vorkommen


so muss das heissen Wink
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 14 Nov 2004 - 17:05:02    Titel:

Im Beitrag nach meinem ist ein rekursiver Algorithmus angegeben, wie es gemacht wird. Das ist das richtige Niveau. Das mit Wertetabellen haben sich Informatiker ausgedacht Smile (Ich bin ja selber einer) um anschaulich, bzw. bei leichten Formeln ohne Aufwand bzw. für ganz spezielle Zwecke (Schaltungen) zu machen. Wie Du es selber treffend bemerkt hast, ist die Umwandlung einer beliebigen Formel in DNF im besten Fall Konstant (0) und im schlimmsten Fall, wenn die Formel in KNF vorliegt exponentiell. Daher wirst Du keine Methode finden, die es dir besser macht. Also ran an die Arbeit Smile

@weyoun: Wir sind hier doch in der Aussagenlogik. Hier gibt es doch keine "atomaren Formeln", nur Elementaraussagen, oder irre ich mich?
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 14 Nov 2004 - 17:07:48    Titel:

Noch was, bemerke ich gerade. Der Definition

http://www-ai.cs.uni-dortmund.de:8765/lexikon/theorie/logik/node2.html#DNF

nach ist deine Formel bereits in DNF.
Weyoun
Gast






BeitragVerfasst am: 14 Nov 2004 - 18:29:33    Titel:

Zitat:

@weyoun: Wir sind hier doch in der Aussagenlogik. Hier gibt es doch keine "atomaren Formeln", nur Elementaraussagen, oder irre ich mich?


meint dasselbe...
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 14 Nov 2004 - 19:02:01    Titel:

Eine atomare Formel ist normal entweder eine Gleichung oder ein Prädikat über einer festgelegten Sprache mit Funktions- und Relationssymbolen. Elementaraussagen als atomare Formeln zu bezeichnen finde ich unschön Smile.
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> Disjunktive Normalform
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum