$ 6. Die disjunktive Normalform für logische Ausdrücke. 13

kürzung.) Da U —>® gleichbedeutend ist mit U —V, so erhalten wir
wieder einen richtigen Ausdruck, indem wir von beiden Seiten der
Gleichung das Gegenteil bilden. Sind nun die beiden Seiten der
Gleichung aus den Grundaussagen und ihren Negationen nur durch
Addition und Multiplikation gebildet, so können wir die eben genannte
Regel anwenden. Wir erhalten demnach eine Formel, die aus der an-
fänglichen Gleichung X —> B dadurch entsteht, daß Summe mit Produkt
und jede Grundaussage mit ihrem Gegenteil vertauscht wird. Da diese
Gleichung immer richtig ist, so können wir sie anwenden, indem wir
für eine jede Grundaussage das Gegenteil einsetzen. Dadurch heben
wir aber die Vertauschung der Grundaussagen mit ihren Negationen auf.

Somit ergibt sich folgendes Dualitätsprinzip: Aus einer Formel
N> B, die auf Grund unserer Regeln stets richtig ist, und deren beide
Seiten aus Grundaussagen und deren Negationen mır durch Addition und
Multiplikation gebildet sind, erhält man wieder eine vichtige Gleichung,
indem man Summe und Produkt miteinander vertauscht.

So ist z. B.

KÜY VE ZWSZCLLC

immer richtig. Es ist die Formel des ersten distributiven Gesetzes, Aus
dieser gewinnt man gemäß dem Dualitätsprinzip die Formel:

X&YZ> (X&Y)(X &Z),

welche gleichfalls richtig ist und das zweite distributive Gesetz darstellt.
Ebenso ist der richtigen Formel

SA SE
nach dem Dualitätsprinzip die ebenfalls richtige Formel

XX ELE
zugeordnet.

8 6. Die disjunktive Normalform für logische Ausdrücke.

Von der Regel zur Bildung des Gegenteils läßt sich eine wichtige
Anwendung machen. Wir hatten gesehen, daß jeder logische Ausdruck
auf eine Normalform gebracht werden kann. Diese Normalform besteht
aus einer Summe von Produkten, wo jedes Produktglied eine negierte
oder unnegierte Grundaussage ist. Die Umformung eines Ausdrucks zur
Normalform geschieht mit Hilfe der Regeln a1)—a4). — Daneben gibt
es noch eine zweite Normalform, die aus einem Produkt von Summen
besteht. Jeder Summand ist eine negierte oder unnegierte Grundaussage.
Wir bezeichnen diese Normalform als „dis/unktive‘““ und die frühere zur
Unterscheidung als „konjunktwve‘‘.

Die Umformung eines Ausdrucks zur disjunktiven Normalform
kann man in der folgenden Weise vornehmen: Man negiert den ur-