Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in 2013-N-06

Beantwortet: Wie heißt der Algorithmus, um aus einem booleschen Term eine Schaltung bestehend aus NAND und NOR Gattern zu bauen?

Tue, 07 Feb 2017 21:42:52 +0000

Hallo,

Denke mir würden da 2 bestimme Tricks einfallen.

Ein ¬a lässt sich auch durch NOR(a,a) oder NAND(a,a) realisieren. Damit lässt sich schonmal jede Negation umschreiben.

Mit der DeMorgan´schen Regel lässt sich jedes "a v b" zu einem NAND(¬a,¬b) umformen (Doppelnegation und eine Negation aus der Klammer ziehen mit DeMorgan´scher Regel) und jedes "a und b" zu einem NOR(¬a,¬b) umschreiben.

Die Umkehrung wenn man mit AND-, NOT- und OR-Gattern schreiben muss geht selbstverstädnlich auch.

Hoffe ich konnte damit helfen :)

Beantwortet: alternativer Lösungsvorschlag: nur aus NAND

Wed, 23 Sep 2015 13:47:26 +0000

Hallo,

Ihre Umformung ist korrekt, aber die Umsetzung mit NAND-Gattern, die nur zwei Eingänge haben, so nicht. Wenn wir die drei negierten Klauseln Ihrer unteren Formel als \( A,B,C \) bezeichnen, also die Formel so angeben:

\( \neg({A\wedge B \wedge C}) \)

dann nehmen Sie in der Schaltung an, dass

\( \neg({A\wedge B \wedge C})=\neg(\neg(AB)C) \)

gilt. Das stimmt aber nicht. Ich habe das in der folgenden Wahrheitstabelle in den letzten beiden Spalten dargestellt.

Viele Grüße

Lukas König

Beantwortet: Wie kann ich (a AND c) aus der Schaltung ablesen?

Wed, 23 Sep 2015 13:38:48 +0000

Hallo,

Ihre Formel ist so korrekt, das entspricht ja genau der Anwendung der de Morganschen Regel.

Sie können (a AND c) relativ einfach ablesen. Wenn Sie die ersten beiden Teile der Formel verstanden haben, dann müssen Sie an dieser Stelle nur noch beachten, dass die beiden Eingänge der dritten reihenschaltung vorher negiert wurden. Wenn Sie dies beachten, dann kommen Sie direkt au den Term (a AND c).

Ich hoffe, dass Ihnen das weiter hilft.

Viele Grüße

Friederike Pfeiffer-Bohnen, Micaela Wünsche und Lukas König