X

Aussagenlogik: Wahrheitstabellen schnell mit vier, fünf oder mehr Variabeln aufstellen ohne Dopplung

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).

ZeilennummerABCDA ∨ B ∧ C ∨ D
000000
100011
200100
300111
401000
501011
601101
701111
810001
910011
1010101
1110111
1211001
1311011
1411101
1511111

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.

ZeilennummerABCDEFA ∨ B ∧ C ∨ D ∧ E ∧ F
00000000
10000010
20000100
30000110
40001000
50001010
60001100
70001111
80010000
90010010
100010100
110010110
120011000
130011010
140011100
150111111
160100000
170100010
180100100
190100110
200101000
210101010
220101100
230101111
240110001
250110011
260110101
270110111
280111001
290111011
300111101
310111111
321000001
331000011
341000101
351000111
361001001
371001011
381001101
391001111
401010001
411010011
421010101
431010111
441011001
451011011
461011101
471011111
481100001
491100011
501100101
511100111
521101001
531101011
541101101
551101111
561110001
571110011
581110101
591110111
601111001
611111011
621111101
631111111

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. ;-)

Christopher Piontek: Ich bin ein technikbegeisterter Blogger, nebenberuflich (Fern-)Student der Wirtschaftsinformatik, hauptberuflicher Webentwickler und schreibe auf Bitpage.de gerne Technik-News, Tutorials und Reviews. Meine favorisierten Themen sind #Software, #Internet und digitale Fotografie.

Zeige Kommentare (3)

  • 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, ...

  • 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.

Verwandte Blogbeiträge