Ergebnis 1 bis 13 von 13

Thema: KKNF -> KNF

  1. #1
    Gesperrt
    Registriert seit
    29.10.2006
    Herkunft
    Zürich Wiedikon
    Semester
    Masterstudium
    Beiträge
    39
    Zustimmungen
    0
    Erhalten: 0 in 0 Beiträgen

    KKNF -> KNF

    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

  2. #2
    contains nuts Avatar von dpk
    Registriert seit
    19.10.2005
    Herkunft
    Berkeley, CA
    Semester
    Alumna
    Beiträge
    1.769
    Zustimmungen
    507
    Erhalten: 397 in 133 Beiträgen
    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. Ist also nicht wirklich eine Anfängerfrage..

    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*

  3. #3
    Teiler und Herrscher Avatar von zarzu
    Registriert seit
    30.10.2005
    Semester
    Alumnus
    Beiträge
    600
    Zustimmungen
    679
    Erhalten: 410 in 187 Beiträgen
    was ist bitte eine kknf? O.o
    "first they ignore you, then they laugh at you, then they fight you, then you win."

  4. #4
    Inaktiver Benutzer
    Registriert seit
    17.11.2006
    Beiträge
    4
    Zustimmungen
    0
    Erhalten: 0 in 0 Beiträgen

    KKNF und KDNF -> KANONISCHE Formen

    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

  5. #5
    Prozedur Avatar von kobold
    Registriert seit
    26.10.2005
    Herkunft
    Zug
    Semester
    Nicht ETH
    Beiträge
    492
    Zustimmungen
    787
    Erhalten: 486 in 163 Beiträgen
    Dann wohl eher eine KONjunktive Normalenform

  6. #6
    Inaktiver Benutzer
    Registriert seit
    24.10.2006
    Herkunft
    Schaffhausen
    Semester
    3. Jahr Bachelor
    Beiträge
    13
    Zustimmungen
    0
    Erhalten: 0 in 0 Beiträgen
    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 zudem werden die Begriffe kKNF und kDNF (meistens mit kleinem 'k' am anfang) auch ausserhalb von LogicTraffic verwendet, sollte man also schon beherrschen


    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

  7. #7
    Prozedur
    Registriert seit
    11.09.2005
    Semester
    Alumnus
    Beiträge
    293
    Zustimmungen
    143
    Erhalten: 317 in 102 Beiträgen
    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)?

  8. #8
    Inaktiver Benutzer
    Registriert seit
    17.11.2006
    Beiträge
    4
    Zustimmungen
    0
    Erhalten: 0 in 0 Beiträgen

    Optimieren von Formeln

    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

  9. #9
    Inaktiver Benutzer
    Registriert seit
    13.11.2004
    Herkunft
    Schweiz, VS
    Semester
    1. Jahr Bachelor
    Beiträge
    95
    Zustimmungen
    0
    Erhalten: 0 in 0 Beiträgen
    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

  10. #10
    Gesperrt
    Registriert seit
    29.10.2006
    Herkunft
    Zürich Wiedikon
    Semester
    Masterstudium
    Beiträge
    39
    Zustimmungen
    0
    Erhalten: 0 in 0 Beiträgen
    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

  11. #11
    Inaktiver Benutzer
    Registriert seit
    13.11.2004
    Herkunft
    Schweiz, VS
    Semester
    1. Jahr Bachelor
    Beiträge
    95
    Zustimmungen
    0
    Erhalten: 0 in 0 Beiträgen
    Reto,

    verlier kein Zeit mit Quine-McClusky, dass wirst du im 2. Semester im Digitech ausführlich sehen.

    Fresh

  12. #12
    Baumschüler
    Registriert seit
    25.10.2005
    Herkunft
    Tuggen Downtown
    Semester
    Alumnus
    Beiträge
    1.314
    Zustimmungen
    452
    Erhalten: 361 in 135 Beiträgen
    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)

  13. #13
    Gesperrt
    Registriert seit
    29.10.2006
    Herkunft
    Zürich Wiedikon
    Semester
    Masterstudium
    Beiträge
    39
    Zustimmungen
    0
    Erhalten: 0 in 0 Beiträgen
    Bookmark gelöscht

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein