Ciao zäme
Hier die ultimative Anfänger-Frage:
Ich habe eine riesige Formel in KKNF und möchte diese jetzt vereinfacht in KNF ausdrücken. Wie löst man das systematisch?
Gruess
Reto
Ciao zäme
Hier die ultimative Anfänger-Frage:
Ich habe eine riesige Formel in KKNF und möchte diese jetzt vereinfacht in KNF ausdrücken. Wie löst man das systematisch?
Gruess
Reto
Gar nicht.Gruss von einem, der die Logik-BP praktisch durchwegs korrekt gelöst hat ausser sämtliche {NNF,DNF,KNF}->{NNF,DNF,KNF} Umformungen, die irgendwann nach 2 A4-Seiten mit weisser Fahne in einer Sackgasse endeten.
Nein, im Ernst: Weiss nicht, aber sieh zu, dass du solche Dinge genügend früh trainierst und dir ein System aneignest, sonst ärgerst du dich an der BP grün und blau... dasselbe gilt übrigens für Gleichungssysteme (nichtlinear, also nicht Matrizen), die man irgendwann in der 4. Kanti hatte, aber an der BP dummerweise von Hand können muss.
So. *Platz für produktivere Postings mach*
was ist bitte eine kknf? O.o
"first they ignore you, then they laugh at you, then they fight you, then you win."
Ups, der Begriff KKNF kommt wohl von LogicTraffic...
KKNF steht für KANONISCHE konjunktive Normalform. Und das ist eine KNF, bei der in jeder Klausel jede Variable vorkommt. Also gewissermassen eine nicht-optimierte KNF, wie sie nach dem einfachen (in der Vorlesung gezeigten) Verfahren aus einer Wahrheitstabelle gebildet werden kann ("für jede 0-Spalte eine entsprechende Klausel").
Analog dazu gibt es die KDNF, siehe z.B. http://de.wikipedia.org/wiki/Disjunktive_Normalform
Dann wohl eher eine KONjunktive Normalenform
uhm hab den breitrag zwar vor paar stunden geschrieben, aber vergessen auf "Antwort erstellen" zu klicken. aber naja, ich denke es ergänzt sich trotzdem gut mit dem Post 1 obendran, also schicke ichs trotzdem mal ab.
und @ Mr. LogicTraffic, du hast kKNF falsch ausgeschrieben
Kanonische konjunktive normalform
sprich sie enthält nur Maxterme (bzw. minterme für Kanonische DNF)
z.B.
KNF:
(AvB)+(CvD) (ich hab hier ~als "nicht" und + als "und")
KKNF:
(~A v ~B v C v D) + (~A v B v C v D) + (A v ~B v C v D) +(A v B v ~C v ~D) + (A v B v ~C v D) + (A v B v C v ~D) + (A v B v C v D)
Ein maxterm/minterm enthält immer alle Atomformeln oder deren Verneinungen.
Durch Resolution der KKNF sollte man auf die KNF kommen. Jedenfalls sind die 2 semantisch Äquivalent.
für weitere infos würd ich selber nachlesen bei google oder so.
Grüsse
Zum Vereinfachen gibt es Karnaugh-Maps und Quine McClusky. Die werden in Digitech behandelt, sind wohl etwas zu aufwändig um sie wirklich in Betracht zu ziehen.
Ansonsten wie wärs mit stehen lassen (würd ich so machen) und wursteln (da es ja kaum länger werden kann)?
Bemerkung noch zum Optimieren von aussagenlogischen Formeln: Ja, das ist nicht trivial. Es gibt in der Literatur das klassische Verfahren nach Quine und McCluskey (siehe z.B.: http://de.wikipedia.org/wiki/Verfahr..._und_McCluskey) und dieses ist in LogicTraffic auch implementiert, von einem Studenten im Rahmen einer Semesterarbeit. Das Verfahren hat eine exponetielle Laufzeit (mehr zu diesem Begriff folgt wohl in einer Vorlesung zu theoretischer Informatik o.ä.), d.h. muss im wesentlichen auch viele (alle) Möglichkeiten durchprobieren. Also wie gesagt: Kein einfaches Problem!... Gruäs, Ruedi
Hi,
ich denke du probierst 6.1.b) zu lösen? Du hast 2 möglichkeiten:
1. Du machst ein Wahrheitstabelle, und dann aus die einsen machst du ein KNF. (Ich glaube dass ist der weg den du schon gemachst hat?)
2. Du probierst den gegebenen DNF mit distribution usw. um zu formen in ein KNF.
Ich habe mit die 2. Variant es durchgearbeitet, und komme zu eine korrekte umformung, aber hatte am schlimmste teil 26 Klauseln. Dann kommen ein paar (A\/-A) Klauseln die man streichen kann, ein paar (A\/B\/C\/D)/\(A\/B\/C) die man mit (A\/B\/C) ersetzen kann (Absorption rule). Am schluss hatte ich 7 Klauseln mit je 3 Literalen.
Du kannst das original DNF im LogicTraffic (Situation 10) eingeben, und dann macht es für dich ein Wahrheitstabelle, und du kannst ein KNF daraus rechnen lassen. Du kannst auch so schauen ob deine Lösung korrekt ist, in dem du die Wahrheitswerte vergleichst mit dem Original. (32 Werte...)
By the way, ein KKNF ist ein KNF, einfach nicht "simplified".
Gruss,
Fresh
Oookay, merci für eure Posts.
Die Aufgabe 6.1 b) habe ich auch mit "ausmultiplizieren" gelöst. Ich bin dann auf 12 Klammern mit je 3 Atomen gekommen. Was ich gerade gesehen habe, habe ich vereinfacht und hatte dann noch 8 Klammern. Dann habe ich das mit LogicTraffic kontrolliert und festgestellt, dass meine Lösung zwar stimmt aber auf 4 Klammern vereinfacht werden kann.
Und so bin ich auf diese Frage gekommen.
Auf den Wikipedia Artikel "Verfahren nach Quine und McCluskey" habe ich mir ein Bookmark gesetzt. Werde ich in einer freien Minute mal durchlesen.
Aber mein Fazit ist in dem Fall folgendes: So gut vereinfachen wie in nützlicher Zeit möglich und dann stehen lassen.
Best regards again,
Reto
Reto,
verlier kein Zeit mit Quine-McClusky, dass wirst du im 2. Semester im Digitech ausführlich sehen.
Fresh
Quine McClusky: Tus nicht! Hast im zweiten Semester genug Gelegenheit dazu, es in- und auswendig zu lernen - vorher brauchst dus ja nicht wirklich....
.... too slow ....
First, say to yourself what you would be. Then do what you have to do. (Epictectus)
Bookmark gelöscht
Berechtigungen
