Ich bin mir ziemlich sicher, dass ich mich daran erinnern kann, so etwas in einem meiner College-Kurse zu machen und dass es eine Art Formel dazu gibt, aber mein Verstand versagt mich darüber hinaus.
Gegeben die Aussage: (a ODER b ODER d) UND (a ODER c)
Ich bin mir ziemlich sicher, dass dies reduziert werden kann: (a ODER b ODER d ODER c)
Aber ich kann mich nicht erinnern, wie ich es beweisen würde.
Vielleicht war es eine Reihe von logischen Tabellen?
Sie können "(a ODER b OR d) UND (a OR c)" nicht auf "(a ODER b ODER d OR c)" reduzieren, weil ersterer nicht mit "c = wahr, a, b, d zufrieden ist = falsch ", während letzteres ist. Also kannst du die Reduktion auch nicht richtig beweisen:)
Im Allgemeinen gibt es viele Möglichkeiten, um boolesche Formeln in der Größe zu reduzieren, und es ist auch eine Frage dessen, was Sie optimieren möchten (Gesamtgröße? durchschnittliche Anzahl von Zustandsbewertungen?). Karnaugh-Karten funktionieren nur für eine kleine Anzahl von Variablen. Das Reduzieren großer boolescher Formeln in kleinere ist ein fortgeschrittenes Thema, das z. automatisches logisches Schaltungsdesign.
Eine Karnaugh-Karte ist dein Freund hier:
Sie müssen es irgendwie umgekehrt von den obigen Gleichungen aufbauen, aber es ist ein gutes Werkzeug, um Ihnen zu sagen, ob es weiter reduziert werden kann.
Karnaugh Karten, der Schlüssel ist "zeichnen" alle möglichen Eingaben und zeigen ihre Ausgaben an. Dann können Sie damit beginnen, die Eingänge herauszufiltern, die für die Ausgabe keinen Unterschied machen, wodurch die Karte verkleinert wird. Sobald es optimiert ist, können Sie dann Ihre Logik daraus erstellen.
(a ODER b ODER d) UND (a ODER c)
Dies bedeutet, wenn a wahr ist, ist alles wahr!
= & gt; a ODER {(b ODER d) UND (c)}
= & gt; a ODER (b UND C) ODER (d und C)
Ich denke, das Ergebnis (a OR b ODER d OR c) ist falsch, aber gib mir eine Hand, wenn es falsch ist.
Mit Karnaugh-Karten :
Dies ist ein OR b ODER d:
%Vor%Dies ist ein OR c:
%Vor%Indem wir sie schneiden, erhalten wir:
%Vor%Offensichtlich ist dies ein OR (etwas), wo das (etwas) ist:
%Vor%Da das (etwas) kein Rechteck ist, benötigt es zwei Ausdrücke, die entweder UND- oder ODER-verknüpft sein können, je nachdem, wie wir uns nähern wollen. Wir verwenden OR in diesem Beispiel, da es einen einfacheren Ausdruck ergibt.
In diesem Fall können wir die zwei X nebeneinander mit zwei weiteren gruppieren, um die gesamte CD-Zeile zu füllen, also kann cd einer der Ausdrücke sein. Wir können die beiden auch übereinander mit den beiden zu ihrer Rechten gruppieren. Dieses Quadrat repräsentiert den Ausdruck bc, da sowohl a als auch d innerhalb des Quadrats variieren.
Der letzte Ausdruck ist also a OR ((c UND d) ODER (b AND d)) oder a + cd + bd . Viel schöner, oder?
Ja, Sie können es beweisen. Sie können es nicht auf (a ODER b ODER d OR c) reduzieren
Sehen Sie sich die dritte Zeile unten an. Ihre Reduzierung würde nicht die richtige Antwort erzeugen.
Führe es einfach durch:
A B C D
0 0 0 0 = 0
0 0 0 1 = 0
0 0 1 0 = 0
.
.
.
1 0 0 0 = 1
1 0 0 1 = 1
Bisher habe ich (A OR (???)): (
Tags und Links computer-science equivalence logic