Wahrheitstabelle zu bool'schen Ausdruck

[Medium]

So, mal was für die Theoretiker unter uns :)

Ich hab hier eine Tabelle mit 6 Konditionen, und darin sämtliche Verknüpfungen dieser die "wahr" ergeben sollen. Alle anderen sollen "falsch" liefern. Da ich diese 16 Kombis die "wahr" sein sollen ungern alle einzeln abtesten will, suche ich nun nach einem Verfahren wie ich diese Tabelle in einen möglichst kurzen logischen Term überführe, der nur "and", "or", "not" und "xor" beinhaltet.

Meine Tabelle schaut so aus: (blank = 0)

Code:

A | | |1|1| | |1|1| |1| |1| |1| |1|
B | | |1| |1| |1|1| |1| |1|1|1| | |
C | | | |1| |1|1|1| |1| |1| | |1|1|
D |1| | | |1|1|1| |1| |1| |1|1| | |
E | |1| | |1|1| |1|1| |1| | | |1|1|
F | |1| |1| |1| |1| | |1|1| | |1|1|
--+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-|
= |1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|

Da bekomm ich eindeutig nen :drunken: von :)

[JasonDX]

Du könntest dir den Quine-McCluskey-Algorithmus angucken. Der ist eine maschinenfreundliche Form der KV-Diagramme und genau für solche Problemstellungen gemacht. Dammit kannst du die kürzeste DNF- bzw. CNF-Formel zu einer gegebenen Wahrheitstabelle berechnen.

greetz
Mike

[Medium]

Da ich das nur für diesen einen speziellen Fall brauche, würd' ich es lieber von Hand machen statt gleich ein ganzes Programm dafür zu bauen :) Allerdings nicht uninteressant!

[himitsu]

Den kürzesten Algo bekommt man so zwar nicht, ber du kannst ja einfach erstmal nah gemeinsamkeiten schauen und diese dann zusammenfassen.

[JasonDX]

Im Wikipedia-Artikel unten sind ein paar Implementierungen verlinkt, unter anderem auch ein Applet. Die kannst du dann dafür verwenden ;)
Allerdings sind das lediglich die minimalen CNF-/DNF-Formeln. Beliebige Kombinationen aus and, or, xor und not könnten evt. noch zu kleineren Formeln führen.

greetz
Mike

[Medium]

Hey das Applet ist cool :) Für meine Tabelle hat es den vergleichsweise handlichen Term:
(!x5*!x3*x2*!x0)+(!x5*!x4*x1*x0)+(x5*x4*!x1*!x0)+( x5*x3*!x2*x0)
ausgespuckt. Nur wie war das noch, * ist 'oder' und + ist 'und', oder war's umgekehrt? :gruebel:

[himitsu]

+ oder
* und

Code:

Result := (not a and not b and e and f) 
  or (a and b and not e and not f) 
  or (a and c and not d and f) 
  or (not a and b and not c and d and not e);

per Hand und nach einfachen Gemeinsamkeiten suchend:

Code:

(A = B) and (E = F) and (A <> F) and (C = D)  // 2 3 6 7

aber hier sind erstmal nur 4 der 16 Möglichkeiten drinnen, also kleiner als das Apllet bekommt man es so schonmal nicht.


Aber hattest du alle Möglichkeiten eingegeben?
Also auch die 0-Ergebnisse ... nicht daß dann was anderes rauskommt.

[Medium]

Danke für die Aufklärung!

Bei dem Applet steht bei, dass es reicht die 1-er Fälle einzutragen, und dass Beliebigkeiten auch eingegeben werden müssen. Das hab ich so verstanden, dass der Ergebnisterm wirklich 1:1 zu o.g. Tabelle passt.

Von Hand hatte ich mich auch ein wenig versucht, sogar mit Baum aufstellen und so Krams, hab aber nach ~1h aufgegeben. Ich konnte mich nur noch zu dunkel an meine Theo.-Inf. Vorlesung erinnern: Es reichte nur noch für "da gab es was" :)