Variante "AllewahrMitBool"

Bei dieser Variante der Überlegungen hilft ein C-Programm (Dateiname AllewahrMitBool.c) zur Erforschung der Möglichkeiten. Es listet in einer Tabelle zu einer vorgegebenen logischen Funktion alle Varianten, wie sich die Funktion mit der Nandfunktion gewinnen lässt, wenn man als Argumente beliebige andere Logikfunktionen einsetzt. Die Überlegungen gehen unten nach dem folgenden C-Quelltext weiter

//===========================================
// Programm Zur Erzeugung von Wahrheitstabellen des Nand-Gatters
// Programmname AllewahrMitBool.c

#include <stdio.h>
#define byte unsigned char

/*
and 0 0 0 1  == 1
nand 1 1 1 0 == 14
aeq 1 0 0 1 == 9
Xor 0 1 1 0 == 6
or 0 1 1 1 == 7
nor 1 0 0 0 == 8
a 0 0 1 1 == 3
!a 1 1 0 0 == 12
b 0 1 0 1 == 5
!b 1 0 1 0 == 10
*/
byte nand(byte arg1, byte arg2) {
byte result;
result = 0xf & (~(arg1 & arg2)) ;
return result ;
}
// Hauptprogramm
int main() {
byte ErgebnisZaehl[16] = { 0 };
byte erg;
byte ergFunk[] =  { 2 , 4 , 6  , 7 , 8 , 9 , 10 , 11 , 12 , 13 , -1 };
int suchEnde;
printf ("========\n");
// Forschleifen fÃ¼r die mÃ¶glichen Bytes, die an den EingÃ¤ngen des
Nand's
// infrage kommen
for (int ergFunkzahl = 0; ergFunkzahl < 10; ergFunkzahl++ ) {
if ( ergFunk[ergFunkzahl] < 0 ) break;
for (byte ii1 = 1; ii1 < 15; ii1++ ) {
for (byte ii2 = 1; ii2 < 15; ii2++ ) {

if (ii1 == 9) continue;
if (ii2 == 9) continue;
if (ii1 > ii2) continue;
erg = nand(ii1,ii2);
if (ergFunk[ergFunkzahl] == erg ) {
printf( "%d = nand( %d , %d )\n", erg, ii1, ii2 );
}
// ErgebnisZaehl[erg]++;
}
}
}
}

=========================================
Das Programm hat eine Tabelle für alle Darstellmöglichkeiten gefunden.
Banale Funktionen False = 0, True = 1 wurden bei der Tabellenerzeugung
ausgeschlossen. Das AEQ ist gesucht und wurde daher nicht als Zwischen-
Ergebnis zugelassen. Die Nand-Funktion wird für alle Tabellenzeilen
verwendet und wurde daher ebenfalls nicht als Suchergebnis zugelassen. Der Output
des C-Programms lieferte die Tabelle TabAllewahr.txt (Siehe Anhang dieses
Textes).
Das Ziel der Überlegung, die Darstellung der AEQ-Funktion mit möglichst
wenigen NAND-Zwischenergebnissen ist, kann mit dieser Tabelle erforscht werden.

Ich fange an mit den Zeilen für AEQ in der Tabelle
AEQ = nand( xor , xor ) | 9 = nand( 6 , 6 )
AEQ = nand( xor , or ) | 9 = nand( 6 , 7 )
AEQ = nand( xor , nand ) | 9 = nand( 6 , 14 )
AEQ = nand( or , nand ) | 9 = nand( 7 , 14 )

Was lernt man aus diesen Zeilen? Das AEQ kann mit einem Nand gewonnen werden, wenn man das Zwischenergebnis 6 hat. Das ist eigentlich klar. Die 6=(0110) ist die Inverse der 9=(1001). Mit einem Nandbaustein kann man doch aus jedem Zwischenergebnis die Inverse gewinnen. Von den vier Zeilen der Tabelle sind zwei unnötig. 9 = nand( 6 , 7 ) und 9 = nand( 6 , 14 ) sind unnötig, weil man doch das Zwischenergebnis 6 braucht und 9 = nand( 6 , 6 ) dafür die einfachste Möglichkeit ist.

Für die Minimierung der AEQ-Schaltung genügen also zwei Anfangszeilen

AEQ = nand( xor , xor ) | 9 = nand( 6 , 6 )
AEQ = nand( or , nand ) | 9 = nand( 7 , 14 )

Für die Gewinnung die Zwischenergebnisses 6 mit nand gibt es genau eine Möglichkeit in der Tabelle TabAllewahr.txt

xor = nand( a>=b , a<=b ) | 6 = nand( 11 , 13 )

Beispiele für die Gewinnung der Zwischenergebnisse 11 und 13
a<=b = nand( a , nand ) | 13 = nand( 3 , 14 )
a>=b = nand( b , nand ) | 11 = nand( 5 , 14 )

Für die Zwischenergebnisse 11 und 13 reicht das weitere Zwischenergebnis 14 = nand(a,b) aus.
Die Tabelle TabAllewahr.txt zeigt für die Gewinnung von 11 oder 13 weitere Möglichkeiten auf, aber keine, die ohne ein weiteres Zwischenergebnis auskommt. Also nicht besser.

Wie geht es mit der anderen Zeile für die Gewinnung des AEQ weiter ?

AEQ = nand( or , nand ) | 9 = nand( 7 , 14 )

Wir brauchen das Zwischenergebnis 7

Es gilt
or = nand( nor , nor ) | 7 = nand( 8 , 8)
Das Zwischenergebnis 8 kann nur auf eine Art gewonnen werden
nor = nand( or , or ) | 8 = nand( 7 , 7 )
Da kommt man nicht weiter. Das Zwischenergebnis 8 ist der Anfang einer Sackgasse.

Eine zielführende Variante ist

or = nand( nb , na ) | 7 = nand( 10 , 12 )

Es geht auch

or = nand( nb , a<=b ) | 7 = nand( 10 , 13 )
or = nand( a>=b , na ) | 7 = nand( 11 , 12 )

Die bisherigen Überlegungen können in einem Zwischenergebnisschema graphisch zusammengefasst werden.

Duagramm der Zwischenergebnisse
Es wurden, wenn man offensichtlich umständlichere Pfade weglässt, vier Zwischenergebnispfade gefunden.

Pfad (1) : 9, 6, 11, 13, 14 benötigt 4 Zwischenergebnisse und das Endergebnis 9

Pfad (2) : 9, 7, 14, 10, 12 Zahl der Zwischenergebnisse gleich wie Pfad 1

Pfad (3) : 9, 7, 14, 10, 13 Zahl der Zwischenergebnisse mehr als bei Pfad 1,
weil Zwischenergebnis 13, weitere Zwischenergebnisse braucht

Pfad (4) : 9, 7, 14, 11, 12 Zahl der Zwischenergebnisse mehr als bei Pfad 1,
weil Zwischenergebnis 12, weitere Zwischenergebnisse braucht

Graphik: Das AEQ mit 5 Nands geschaltet:

AEQ aus Nands

Anhang: Die vollständige Tabelle "TabAllewahr.txt

"TabAllewahr.txt
======================================
a>b = nand( a<=b , a<=b ) | 2 = nand( 13 , 13 )
a=b , a>=b ) | 4 = nand( 11 , 11 )
xor = nand( a>=b , a<=b ) | 6 = nand( 11 , 13 )
or = nand( nor , nor ) | 7 = nand( 8 , 8 )
or = nand( nor , nb ) | 7 = nand( 8 , 10 )
or = nand( nor , a>=b ) | 7 = nand( 8 , 11 )
or = nand( nor , na ) | 7 = nand( 8 , 12 )
or = nand( nor , a<=b ) | 7 = nand( 8 , 13 )
or = nand( nor , nand ) | 7 = nand( 8 , 14 )
or = nand( nb , na ) | 7 = nand( 10 , 12 )
or = nand( nb , a<=b ) | 7 = nand( 10 , 13 )
or = nand( a>=b , na ) | 7 = nand( 11 , 12 )
nor = nand( or , or ) | 8 = nand( 7 , 7 )
AEQ = nand( xor , xor ) | 9 = nand( 6 , 6 )
AEQ = nand( xor , or ) | 9 = nand( 6 , 7 )
AEQ = nand( xor , nand ) | 9 = nand( 6 , 14 )
AEQ = nand( or , nand ) | 9 = nand( 7 , 14 )
nb = nand( b , b ) | 10 = nand( 5 , 5 )
nb = nand( b , or ) | 10 = nand( 5 , 7 )
nb = nand( b , a<=b ) | 10 = nand( 5 , 13 )
nb = nand( or , a<=b ) | 10 = nand( 7 , 13 )
a>=b = nand( a=b = nand( a=b = nand( a=b = nand( a=b = nand( a=b = nand( a=b = nand( a=b = nand( b , xor ) | 11 = nand( 5 , 6 )
a>=b = nand( b , na ) | 11 = nand( 5 , 12 )
a>=b = nand( b , nand ) | 11 = nand( 5 , 14 )
a>=b = nand( xor , na ) | 11 = nand( 6 , 12 )
a>=b = nand( xor , a<=b ) | 11 = nand( 6 , 13 )
a>=b = nand( or , na ) | 11 = nand( 7 , 12 )
na = nand( a , a ) | 12 = nand( 3 , 3 )
na = nand( a , or ) | 12 = nand( 3 , 7 )
na = nand( a , a>=b ) | 12 = nand( 3 , 11 )
na = nand( or , a>=b ) | 12 = nand( 7 , 11 )
a<=b = nand( a>b , a>b ) | 13 = nand( 2 , 2 )
a<=b = nand( a>b , a ) | 13 = nand( 2 , 3 )
a<=b = nand( a>b , xor ) | 13 = nand( 2 , 6 )
a<=b = nand( a>b , or ) | 13 = nand( 2 , 7 )
a<=b = nand( a>b , nb ) | 13 = nand( 2 , 10 )
a<=b = nand( a>b , a>=b ) | 13 = nand( 2 , 11 )
a<=b = nand( a>b , nand ) | 13 = nand( 2 , 14 )
a<=b = nand( a , xor ) | 13 = nand( 3 , 6 )
a<=b = nand( a , nb ) | 13 = nand( 3 , 10 )
a<=b = nand( a , nand ) | 13 = nand( 3 , 14 )
a<=b = nand( xor , nb ) | 13 = nand( 6 , 10 )
a<=b = nand( xor , a>=b ) | 13 = nand( 6 , 11 )
a<=b = nand( or , nb ) | 13 = nand( 7 , 10 )