Sheffer-Operator (NAND-Operator)

04.11.2004, 00:51

snake32

Sheffer-Operator (NAND-Operator)

Der Sheffer-Operator (oder NAND-Operator), in Zeichen x|j, ist definiert durch folgende Wahrheitstafel

code:
1: 2: 3: 4: 5: 6:	x y x\|y w w f w f w f w w f f w

Finden Sie Ausdrücke für nicht x, x <-> y und x -> y in denen nur der Sheffer-Operator vorkommt.

Bemerkung:
Man kann zeigen, dass jeder logische Ausdruck durch einen Ausdruck ersetzt werden kann, der
nur den Sheffer-Operator enthält. Diese Tatsache gewährleistet zum Beispiel, dass Schaltungen nur mit einem
einzigen Schaltelement realisiert werden können.

thx für eure Hilfe

04.11.2004, 03:01

Tobias

Auf diesen Beitrag antworten »

Wenn ich das noch richtig in Erinnerung habe wird dieser Operator auch "Sheffer'scher Strich" genannt. Jedenfalls bekommt er bei mir jetzt mal folgendes Symbol: $\begin{eqnarray*} \updownarrow \end{eqnarray*}$ .

Die Bemerkung, die dort genannt wurde zielt darauf ab, dass du beweisen sollst, dass $\begin{eqnarray*} \{ \updownarrow \} \end{eqnarray*}$ funktional vollständig ist. Das kann man z.B. beweisen, indem man eine Menge nimmt, von der man die Funktionale Vollständigkeit bereits kennt. Typischerweise z.B. $\begin{eqnarray*} \{ \neg, \wedge \} \end{eqnarray*}$ .

Nun zeigt man, dass beide Operatoren in dieser Menge durch den Sheffer-Operator darstellbar sind.

Die Negation "Nicht" ist ganz einfach:

$\begin{eqnarray*} \neg x \equiv x \updownarrow x \end{eqnarray*}$

Denn aus deiner Tabelle geht hervor: Ist x wahr, so führt wahr NAND wahr zu falsch. Ist x falsch, so ergibt sich entsprechend wahr.

Wenn du nun das Nicht kennst und hast ein NAND, dann sollte sich auch ein AND konstruieren lassen. Dann hast du gezeigt, dass $\begin{eqnarray*} \{ \updownarrow \} \end{eqnarray*}$ funktional vollständig ist. Man kann also allein mit diesem Operator jede Boole'sche Funktion darstellen.

Neue Frage »

Antworten »

Sheffer-Operator (NAND-Operator)

Verwandte Themen