imported>Neutronstar2 am 16. Oktober 2020 um 21:24 Uhr

2020-10-16T21:24:49Z

Neue Seite

Die '''Ringsummennormalform''' (kurz RSNF oder RNF) (auch: '''Algebraische Normalform''' (kurz ANF), '''Reed-Muller-Entwicklung''', '''Ringsummenexpansion''' oder [[Iwan Iwanowitsch Schegalkin|Schegalkinsches]] Polynom) ist eine Darstellungsform einer [[Boolesche Funktion|Booleschen Funktion]]. Diese [[Klausel-Normalform|Normalform]] verwendet ausschließlich die Operatoren [[Kontravalenz|XOR (Kontravalenz)]] und [[Konjunktion_(Logik)|UND (Konjunktion)]].

== Definition ==

Die beiden Operatoren Kontravalenz und Konjunktion <math>\{\oplus,\wedge,1\}</math> bilden eine vollständige Basis der [[Boolesche Funktion|booleschen Funktionen]]. Damit wird die folgende Definition möglich.

Eine Formel ist in Ringsummennormalform, wenn sie eine [[Kontravalenz]] (<math>\oplus</math>) von [[Konjunktion_(Logik)|Konjunktionen]] (<math>\wedge</math>) der Eingabevariablen <math>x_1, \dots, x_n</math> und der Konstanten <math>0,1</math> ist. Eine Formel in RSNF hat folgende Form:

:<math>\bigoplus_{T\subseteq\{1, \dots, n\}} ( a_T \wedge \bigwedge_{i\in T} x_i )</math>,

wobei <math>a_T\in\{0,1\}</math> für jede Teilmenge <math>T</math> ist.

== Berechnung der RSNF ==
Man geht von einer [[orthogonalen disjunktiven Normalform]] (also einer [[disjunktive Normalform|disjunktiven Normalform]], deren Konjunktionen alle gegenseitig disjunkt sind, d. h. 0 ergeben) aus. Das kann z. B. auch die [[Disjunktive Normalform#Kanonische disjunktive Normalform|kanonisch disjunktive Normalform]] sein. In dieser ersetzt man den [[Disjunktion]]soperator durch den [[Kontravalenz|Antivalenzoperator]] (Ringsumme), was aufgrund der Orthogonalität möglich ist. Danach schreibt man die [[Negation]]en in die (geklammerte) Antivalenz mit 1 um. Anschließend „multipliziert“ man unter besonderer Beachtung der Rechenregel für die Antivalenz <math>x \oplus x = 0</math> aus.

=== Beispiel ===
Die disjunktive Normalform <math>AB \vee \bar{A} \bar{B} \vee A \bar{C}</math> kann wie folgt in ihre RSNF umgeformt werden:

Orthogonalisierung (z. B. mit Hilfe eines [[Karnaugh-Veitch-Diagramm|Karnaugh-Planes]]): <math>AB \vee \bar{A} \bar{B} \vee A \bar{B}\bar{C}</math>

Ersetzen der Disjunktion durch die Antivalenz: <math>AB \oplus \bar{A} \bar{B} \oplus A \bar{B}\bar{C}</math>

Umschreiben der Negation: <math>AB \oplus (A \oplus 1) (B \oplus 1) \oplus A (B \oplus 1) (C \oplus 1)</math>

Ausmultiplizieren: <math>AB \oplus AB \oplus A \oplus B \oplus 1 \oplus ABC \oplus AC \oplus AB \oplus A</math>

Durch „Wegstreichen“ von jeweils zwei gleichen Termen erhält man nach dem Umsortieren schließlich:
:<math>1 \oplus B \oplus A B \oplus A C \oplus A B C</math>

== Folgerungen ==

* Jede beliebige [[boolesche Funktion]] kann in Ringsummennormalform überführt werden.
* Die Ringsummennormalform einer booleschen Funktion ist (bis auf die Reihenfolge) eindeutig.

== Literatur ==
* Ingo Wegener: The complexity of Boolean functions. Wiley-Teubner, 1987, ISBN 3-519-02107-2, S. 6 ([http://ls2-www.cs.uni-dortmund.de/monographs/bluebook Online-Ausgabe])
* [http://www.is.informatik.uni-duisburg.de/courses/infoa_ss03/slides/02-slides.pdf#page=34 Präsentation der Uni Duisburg]
[[Kategorie:Logik]]
[[Kategorie:Normalform]]

Ringsummennormalform - Versionsgeschichte

imported>Neutronstar2 am 16. Oktober 2020 um 21:24 Uhr