„Ringsummennormalform“ – Versionsunterschied
[ungesichtete Version] | [ungesichtete Version] |
Inhalt gelöscht Inhalt hinzugefügt
QS+ |
kleinere Korrekturen |
||
Zeile 1: | Zeile 1: | ||
⚫ | |||
{{QS-Antrag|26. September 2008|2= ''Meine OMA versteht nur Bahnhof!'' <span style="white-space:nowrap;">-- [[Benutzer:Johnny Controletti|Johnny Controletti]] <small>14:06, 26. Sep. 2008 (CEST)</small></span>}} |
|||
⚫ | |||
== Definition == |
== Definition == |
||
Die Operatoren <math>\{\oplus,\wedge\}</math> bilden eine vollständig Basis der [[Boolesche Funktion|booleschen Funktionen]]. Damit wird die folgende Definition möglich. |
|||
⚫ | |||
⚫ | |||
<center><math>\bigoplus_{T\subseteq\{1,...,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.</center> |
<center><math>\bigoplus_{T\subseteq\{1,...,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.</center> |
||
== Folgerungen == |
== Folgerungen == |
||
* Jede beliebige [[boolesche Funktion]] kann in Ringsummennormalform überführt werden. |
|||
* Die Ringsummennormalform ist eindeutig. |
* Die Ringsummennormalform ist eindeutig. |
Version vom 26. September 2008, 14:20 Uhr
Die Ringsummennormalform (kurz RSNF) (auch: Reed-Muller-Entwicklung oder Ringsummenexpansion) ist eine Normalform der Aussagenlogik.
Definition
Die Operatoren bilden eine vollständig Basis der booleschen Funktionen. Damit wird die folgende Definition möglich.
Eine Formel ist in Ringsummennormalform, wenn sie eine Kontravalenz () von Konjunktionen () der Eingabevariablen und der Konstanten ist. Eine Formel in RSNF hat folgende Form:
Folgerungen
- Jede beliebige boolesche Funktion kann in Ringsummennormalform überführt werden.
- Die Ringsummennormalform ist eindeutig.