Um in der Aussagenlogik Äquivalenzen oder Tautologien zu beweisen ist eine Wahrheitstabelle unumgänglich. Dabei müssen alle möglichen Kombinationen von wahr und falsch bzw. Eins und Null der Variabeln aufgestellt werden. Bei zwei oder drei Variabeln ist das noch problemlos möglich. Ohne schematisches Vorgehen ist das ab vier Variabeln sehr fehleranfällig und zeitintensiv. Aus diesem Grund möchte ich Euch das binäre Durchzählen in diesem Blogbeitrag zeigen, mit dem Ihr gelassen auch zehn Variabeln in einer Wahrheitstafel mit allen möglichen Kombinationen aus wahr und falsch aufschreiben könnt.
Grundlagen: Das Binärsystem und Kombinatorik
Neben unserem alltäglichem Dezimalsystem gibt es das – besonders in der Informatik beliebte – Binärsystem. Zahlen werden dabei nur mit Nullen und Einsen dargestellt. Bei der Wahrheitstafel bleibt es zumeist freigestellt, ob Ihr für einen Wert der Variable „Eins“ oder „wahr“ eintragt. Ich empfehle Euch Null und Eins zu benutzen. Das macht das binäre Durchzählen leichter. Beim Binärsystem hat jede „Stelle“ einen Wert, der für eine Zahl steht. Die erste Stelle steht im Binärsystem für die 1, die Zweite für die 2, die Dritte für die 4, die Vierte für die 16 und ewig so weiter verdoppelt. Die 1001 bspw. stellt die 9 dar, während die 1111 die 15 darstellt. Falls das Binärsystem total neu für dich ist, ließ dich hierzu ein und wandel ein paar Zahlen aus dem Binärsystem ins Dezimalsystem. Es schadet nicht, wenn Du auch den umgekehrten Weg lernst, ist aber fürs binäre Durchzählen hier nicht weiter nötig.
Kommen wir zur Kombinatorik. Keine Sorge, auch hier gibt es an dieser Stelle nur eine Formel, die Du dir merken musst: 2n. Dabei steht die 2 für die Anzahl der möglichen Werte, die eine Variabel im Binärsystem bzw. Aussagenlogik annehmen kann: Wahr oder Falsch, Eins oder Null. N steht dabei für die Anzahl der Variabeln. Bei vier Variablen ergibt die Formel 2n = 24 = 16 mögliche Kombinationen ohne Wiederholungen. Und hier liegt dann auch schon die Strategie: Ihr müsst einfach im Binärsystem alle Zahlen von 0 bis 15 darstellen. Das sind 16 Zeilen. In der Informatik geht es häufiger ab 0 direkt los.
Binär durchzählen: So geht’s
Fangt bei Null an und zählt bis 16 binär hoch. Falls Ihr mehr Variablen habt, natürlich bis zu der Gesamtanzahl der möglichen Kombinantionen (Formel 2n).
| Zeilennummer | A | B | C | D | A ∨ B ∧ C ∨ D |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 1 |
| 2 | 0 | 0 | 1 | 0 | 0 |
| 3 | 0 | 0 | 1 | 1 | 1 |
| 4 | 0 | 1 | 0 | 0 | 0 |
| 5 | 0 | 1 | 0 | 1 | 1 |
| 6 | 0 | 1 | 1 | 0 | 1 |
| 7 | 0 | 1 | 1 | 1 | 1 |
| 8 | 1 | 0 | 0 | 0 | 1 |
| 9 | 1 | 0 | 0 | 1 | 1 |
| 10 | 1 | 0 | 1 | 0 | 1 |
| 11 | 1 | 0 | 1 | 1 | 1 |
| 12 | 1 | 1 | 0 | 0 | 1 |
| 13 | 1 | 1 | 0 | 1 | 1 |
| 14 | 1 | 1 | 1 | 0 | 1 |
| 15 | 1 | 1 | 1 | 1 | 1 |
In der ersten Spalte „Zeile (binär)“ wird die Zeilennummer im Dezimalsystem angefangen bei Null dargestellt. Danach bilden die Spalten A bis D die Binärdarstellung der Zeilennummer. Der Term A ∨ B ∧ C ∨ D in der letzten Spalte dient nur als mögliches Beispiel für eine Interpretation der Variablen.
Um es einmal auf die Spitze zu treiben, habe ich nachfolgend eine Wahrheitstabelle mit sechs Variablen. Derjenige der so eine gigantische Wahrheitstabelle aber in einer Klausur fordert, sollte seinen Beruf noch einmal überdenken.
| Zeilennummer | A | B | C | D | E | F | A ∨ B ∧ C ∨ D ∧ E ∧ F |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| 2 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 3 | 0 | 0 | 0 | 0 | 1 | 1 | 0 |
| 4 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 5 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
| 6 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| 7 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 8 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 9 | 0 | 0 | 1 | 0 | 0 | 1 | 0 |
| 10 | 0 | 0 | 1 | 0 | 1 | 0 | 0 |
| 11 | 0 | 0 | 1 | 0 | 1 | 1 | 0 |
| 12 | 0 | 0 | 1 | 1 | 0 | 0 | 0 |
| 13 | 0 | 0 | 1 | 1 | 0 | 1 | 0 |
| 14 | 0 | 0 | 1 | 1 | 1 | 0 | 0 |
| 15 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| 16 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 17 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
| 18 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
| 19 | 0 | 1 | 0 | 0 | 1 | 1 | 0 |
| 20 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
| 21 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 22 | 0 | 1 | 0 | 1 | 1 | 0 | 0 |
| 23 | 0 | 1 | 0 | 1 | 1 | 1 | 1 |
| 24 | 0 | 1 | 1 | 0 | 0 | 0 | 1 |
| 25 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 26 | 0 | 1 | 1 | 0 | 1 | 0 | 1 |
| 27 | 0 | 1 | 1 | 0 | 1 | 1 | 1 |
| 28 | 0 | 1 | 1 | 1 | 0 | 0 | 1 |
| 29 | 0 | 1 | 1 | 1 | 0 | 1 | 1 |
| 30 | 0 | 1 | 1 | 1 | 1 | 0 | 1 |
| 31 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| 32 | 1 | 0 | 0 | 0 | 0 | 0 | 1 |
| 33 | 1 | 0 | 0 | 0 | 0 | 1 | 1 |
| 34 | 1 | 0 | 0 | 0 | 1 | 0 | 1 |
| 35 | 1 | 0 | 0 | 0 | 1 | 1 | 1 |
| 36 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
| 37 | 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 38 | 1 | 0 | 0 | 1 | 1 | 0 | 1 |
| 39 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
| 40 | 1 | 0 | 1 | 0 | 0 | 0 | 1 |
| 41 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |
| 42 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 43 | 1 | 0 | 1 | 0 | 1 | 1 | 1 |
| 44 | 1 | 0 | 1 | 1 | 0 | 0 | 1 |
| 45 | 1 | 0 | 1 | 1 | 0 | 1 | 1 |
| 46 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
| 47 | 1 | 0 | 1 | 1 | 1 | 1 | 1 |
| 48 | 1 | 1 | 0 | 0 | 0 | 0 | 1 |
| 49 | 1 | 1 | 0 | 0 | 0 | 1 | 1 |
| 50 | 1 | 1 | 0 | 0 | 1 | 0 | 1 |
| 51 | 1 | 1 | 0 | 0 | 1 | 1 | 1 |
| 52 | 1 | 1 | 0 | 1 | 0 | 0 | 1 |
| 53 | 1 | 1 | 0 | 1 | 0 | 1 | 1 |
| 54 | 1 | 1 | 0 | 1 | 1 | 0 | 1 |
| 55 | 1 | 1 | 0 | 1 | 1 | 1 | 1 |
| 56 | 1 | 1 | 1 | 0 | 0 | 0 | 1 |
| 57 | 1 | 1 | 1 | 0 | 0 | 1 | 1 |
| 58 | 1 | 1 | 1 | 0 | 1 | 0 | 1 |
| 59 | 1 | 1 | 1 | 0 | 1 | 1 | 1 |
| 60 | 1 | 1 | 1 | 1 | 0 | 0 | 1 |
| 61 | 1 | 1 | 1 | 1 | 0 | 1 | 1 |
| 62 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
| 63 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Schreibt ruhig mal in die Kommentare, ob Ihr das binäre Durchzählen von mir verständlich erklärt findet oder ob es irgendwo hakt. ;-)
Wenn man wie hier immer nur um 1 hochzählen möchte, dann gibt es noch einen etwas anderen Ansatz, den man als kleine Eselsbrücke nehmen könnte: Wenn du eine beliebige binäre Zahl um 1 erhöhen möchtest, tu das Folgende: Starte ganz rechts und kippe so lange 1en auf 0en um bis du eine 0 zu einer 1 machen kannst.
Was ich außerdem immer noch interssant zu sagen finde, ist, dass das Binärsystem eigentlich für uns gar nicht so neu ist. Unser Dezimalsystem funktioniert nach dem selben Prinzip. Uns ist z.B. bei 142 automatisch klar, dass die 4 hier nicht für 4, sondern 40 bzw. 4*10 steht, weil sie eben an der 2. Stelle kommt. Die Stellen werden mit 1, 10, 100, … multipliziert. Beim Binärsystem ist es das gleiche, aber irgendwer hat alle Ziffern bis auf die 0 und 1 geklaut. Daher ist die Basis 2 und man multipliziert die Stellen hier mit 1, 2, 4, 8, …
guter artikel
Ganz toll erklärter Artikel. Für die, die sich darüber hinaus noch weiter informieren möchten, können sich auch mal das ternäre System (oder Ternärsystem) ansehen.