Gibt es einen intuitiven Grund, warum das NAND-Gatter ein universelles Gatter ist?

Jetzt kenne ich die Mathematik und Logik, um herauszufinden, dass jede boolesche Funktion nur mit UND- und NICHT-Gattern ausgedrückt werden kann, die wiederum nur mit NAND-Gattern ausgedrückt werden können, und daher kann jede boolesche Funktion nur mit einer Kombination von NANDs ausgedrückt werden. Ich kenne die Mathematik, ich kann leicht das Wie herausfinden .

Aber ich suche nach einem intuitiveren ( nicht unbedingt nicht mathematischen, vielleicht philosophischen ) Grund, warum dies wahr sein muss (falls es überhaupt einen solchen Grund gibt). Aus irgendeinem Grund denke ich, dass es nicht nur eine mathematische Tatsache ist, dass das NAND-Gatter universell ist, es muss einen "tieferen" Grund oder etwas in der Eigenschaft von NAND-Gattern geben, das dies hat, wenn ich mich selbst erklären kann.

Also, gibt es wirklich einen solchen Grund? Oder ist die universelle Natur von NANDs wirklich nur ein mathematisches Artefakt, das wir gerade irgendwie entdeckt haben?

BEARBEITEN: Die grundlegenden Tore wurden korrigiert. Ich habe das vermasselt.

Sie wissen, dass NOR-Gatter auch universell sind, oder? Nicht nur NAND-Gatter?
Nun, die Tatsache, dass Sie nur nach NAND fragen, zeigt, dass Sie denken, dass ein NAND etwas Besonderes ist. Ich wies auf NOR hin, um zu zeigen, dass dies nicht der Fall ist. Und die Tatsache, dass sie beide universell sind, könnte darauf hindeuten, dass Sie lediglich ein NOT-Gate in den Mix mischen müssen. OR und AND machen zusammen so ziemlich alles ... außer einem NOT, und wenn ein NOT verfügbar ist, spielt es keine Rolle, ob Sie OR oder AND verwenden, da sie nur Duale voneinander sind.
Mein Bauchgefühl ist, dass Sie konjunktive und disjunktive Normalformen und ihre Beweise nachschlagen sollten. Aber ich bin mir auch nicht sicher, ob du danach fragst.

Antworten (2)

Jetzt kenne ich die Mathematik und Logik, um herauszufinden, dass jede boolesche Funktion nur mit UND- und ODER-Gattern ausgedrückt werden kann

Unwahr. Sie brauchen auch Wechselrichter.

Jede boolesche Funktion kann nur durch Kombination von NANDs ausgedrückt werden.

WAHR. Oder Sie können es mit NOR-Gattern machen ...

Aber ich suche nach einem intuitiveren (nicht unbedingt nicht mathematischen, vielleicht philosophischen) Grund, warum dies wahr sein muss (falls es überhaupt einen solchen Grund gibt).

Was NAND und NOR gemeinsam haben, ist, dass sie:

  • Ermöglicht es Ihnen, eine einzigartige Möglichkeit der vier in einer Logiktabelle mit zwei Eingängen zu "erkennen" .

  • Ermöglicht den Aufbau eines Wechselrichters, indem beide Eingänge mit demselben Signal versorgt werden

Im Grunde haben Sie also eine "Test"-Engine und eine "Transformations"-Engine; Sie verwenden die „Transform“-Engine nach Bedarf, um das Muster, nach dem Sie suchen möchten, in das Muster umzuwandeln, nach dem die „Test“-Engine sucht , und dann die „Transform“-Engine, um das Ergebnis in das zu verwandeln, was Sie wollen.

Und wenn Sie mehrere Muster erkennen müssen, behandeln Sie die Erfüllung beider (oder keiner ihrer Anti-Muster) als das in einer anderen Stufe zu erkennende Muster.

Oder finden Sie einfach eine Serviette und zeichnen Sie alle anderen Gatter als Sammlung von NAND-Gattern ...

„Im Grunde haben Sie also eine „Test“-Engine und eine „Transformations“-Engine; Sie verwenden die „Transformations“-Engine nach Bedarf, um das Muster, nach dem Sie suchen möchten, in das Muster umzuwandeln, nach dem die „Test“-Engine sucht, und dann das "Transformations"-Engine, um das Ergebnis in das umzuwandeln, was Sie wollen." - Eine fantastische Erklärung. +1!
Interessanterweise kann man mit n Invertern zusammen mit einer ausreichenden Anzahl von UND- und ODER-Gattern eine rein kombinatorische Schaltung mit 2ⁿ-1 Eingängen und 2ⁿ-1 Ausgängen aufbauen, deren stationäre Ausgänge das Inverse der Eingänge sind.

Ich finde De Morgans Gesetze sehr intuitiv:

Wenn Sie A und B brauchen, um X zu erreichen, dann haben Sie X nicht, wenn Sie A oder B nicht haben.

Geben Sie hier die Bildbeschreibung ein

Und Sie haben intuitiv die Summe der Produkte: Jedes UND erkennt eine bestimmte Kombination mit einem HIGH-Ausgang, und Sie ODER sie zusammen.

Ein ähnlicher Ansatz gilt für NOR-Gatter und das Produkt von Summen.

Gibt es einen intuitiven Grund, warum das NAND-Gatter ein universelles Gatter ist?
AntwortenHierDatenschutz-Bestimmungen1y, 0v