„Vollkonjunktion“ – Versionsunterschied

Versionsgeschichte interaktiv durchsuchen

[ungesichtete Version]

[gesichtete Version]

Inhalt gelöscht Inhalt hinzugefügt

Inline

Aktuelle Version vom 28. Oktober 2019, 22:00 Uhr

Als Vollkonjunktion (auch Minterm oder Elementarkonjunktion) bezeichnet man in der Aussagenlogik einen speziellen Konjunktionsterm, d. h. eine Anzahl von Literalen (booleschen Variablen), die alle durch ein logisches und ( $\wedge$ ) verknüpft sind. Dabei müssen alle $n$ Variablen der betrachteten $n$ -stelligen booleschen Funktion im Konjunktionsterm vorkommen. Vollkonjunktionen lassen sich zu einer disjunktiven Normalform zusammensetzen, beispielsweise beim Verfahren nach Quine und McCluskey.

Beispiele

Beispiele für 3-stellige boolesche Funktionen

$e_{1}\wedge e_{2}\wedge e_{3}$
$e_{1}\wedge \neg e_{2}\wedge e_{3}$
$\neg e_{1}\wedge e_{2}\wedge \neg e_{3}$

Standardnummerierung der Vollkonjunktionen

Vollkonjunktionen lassen sich auf natürliche Weise nummerieren. Man denkt sich dabei die Variablen in einer Reihe notiert, z. B. $X_{n}X_{n-1}...X_{2}X_{1}$ . Kommt für eine konkrete Vollkonjunktion das jeweilige Literal $X_{i}$ negiert vor, so ersetzt man es durch eine 0, sonst durch eine 1. Es entsteht eine Binärzahl, die man dezimal interpretieren kann. Diese Dezimalzahl bezeichnet man als die Nummer oder den Index des Minterms. Will man diesen Minterm über seinen Index $i$ bezeichnen, so schreibt man $m_{i}$ . Analog geht dies mit den Maxtermen $M_{i}$ bei Disjunktionen.

Vergleich Minterm / Maxterm

In folgender Tabelle ist der Unterschied zwischen der Maxterm- und Mintermdarstellung ersichtlich:

Index	$x_{2}$	$x_{1}$	$x_{0}$	Minterm	Maxterm
0	0	0	0	$\neg x_{2}\wedge \neg x_{1}\wedge \neg x_{0}$	$x_{2}\vee x_{1}\vee x_{0}$
1	0	0	1	$\neg x_{2}\wedge \neg x_{1}\wedge x_{0}$	$x_{2}\vee x_{1}\vee \neg x_{0}$
2	0	1	0	$\neg x_{2}\wedge x_{1}\wedge \neg x_{0}$	$x_{2}\vee \neg x_{1}\vee x_{0}$
3	0	1	1	$\neg x_{2}\wedge x_{1}\wedge x_{0}$	$x_{2}\vee \neg x_{1}\vee \neg x_{0}$
4	1	0	0	$x_{2}\wedge \neg x_{1}\wedge \neg x_{0}$	$\neg x_{2}\vee x_{1}\vee x_{0}$
5	1	0	1	$x_{2}\wedge \neg x_{1}\wedge x_{0}$	$\neg x_{2}\vee x_{1}\vee \neg x_{0}$
6	1	1	0	$x_{2}\wedge x_{1}\wedge \neg x_{0}$	$\neg x_{2}\vee \neg x_{1}\vee x_{0}$
7	1	1	1	$x_{2}\wedge x_{1}\wedge x_{0}$	$\neg x_{2}\vee \neg x_{1}\vee \neg x_{0}$

Realisierung von Decoder-Schaltungen mit Mintermen / Maxtermen:

	Minterm	Maxterm
0	NOR-Gatter	AND-Gatter
1	OR-Gatter	NAND-Gatter

Bezeichnungen

Minterme

Ein einziger Minterm:
- Für genau eine Belegung Funktionswert 1
- Minimalität:
  - maximale Anzahl an Nullen
  - minimale Anzahl an Einsen

(abgesehen von trivialer Nullfunktion)

Maxterme

Ein einziger Maxterm:
- Für genau eine Belegung Funktionswert 0
- Maximalität:
  - maximale Anzahl an Einsen
  - minimale Anzahl an Nullen

(abgesehen von trivialer Einsfunktion)

Bezug zum Karnaugh-Veitch-Diagramm

Man spricht auch vom Minterm einer Funktion $F$ , wenn dieser $F$ impliziert, d. h. wenn gilt

M(X)=1\Rightarrow F(X)=1

.

Dabei ist $X$ der Vektor der Eingangsvariablen. Derartige Minterme $M$ entsprechen umkehrbar eindeutig denjenigen Feldern eines Karnaugh-Veitch-Diagramms, die für die betrachtete Funktion den Wert 1 enthalten.

@@ Zeile 1: / Zeile 1: @@
-Als '''Vollkonjunktion''' (auch: '''Minterm''', '''Miniterm''' oder '''Elementarkonjunktion''') bezeichnet man in der [[Aussagenlogik]] einen speziellen [[Konjunktionsterm]], d.h. eine Anzahl von [[Literal|Literalen]], die alle durch ein [[Konjunktion (Logik)|logisches ''und'']] (<math>\wedge</math>) verknüpft sind. Dabei müssen alle n Variablen der betrachteten n-stelligen [[Boolesche Funktion|Booleschen Funktion]] im Konjunktionsterm vorkommen, um von einer Vollkonjunktion sprechen zu können. Vollkonjunktionen lassen sich zu einer [[Disjunktive Normalform|disjunktiven Normalform]] zusammensetzen, was unter anderem beim [[Verfahren nach Quine und McCluskey]] vonnöten ist.
+Als '''Vollkonjunktion''' (auch '''Minterm''' oder '''Elementarkonjunktion''') bezeichnet man in der [[Aussagenlogik]] einen speziellen [[Konjunktionsterm]], d.&nbsp;h. eine Anzahl von Literalen ([[Boolesche_Variable|booleschen Variablen]]), die alle durch ein [[Konjunktion (Logik)|logisches ''und'']] (<math>\wedge</math>) verknüpft sind. Dabei müssen alle <math>n</math> Variablen der betrachteten <math>n</math>-stelligen [[Boolesche Funktion|booleschen Funktion]] im Konjunktionsterm vorkommen. Vollkonjunktionen lassen sich zu einer [[Disjunktive Normalform|disjunktiven Normalform]] zusammensetzen, beispielsweise beim [[Verfahren nach Quine und McCluskey]].
-==Beispiele==
+== Beispiele ==
+Beispiele für 3-stellige boolesche Funktionen
-*<math>e_1 \wedge e_2</math>
+*<math>e_1 \wedge e_2 \wedge e_3</math>
 *<math>e_1 \wedge \neg e_2 \wedge e_3</math>
-*<math>\neg e_1 \wedge e_2 \wedge e_3</math>
+*<math>\neg e_1 \wedge e_2 \wedge \neg e_3</math>
-==Standardnummerierung der Vollkonjunktionen==
+== Standardnummerierung der Vollkonjunktionen ==
-Vollkonjunktionen lassen sich auf natürliche Weise nummerieren. Man denkt sich dabei die Variablen in einer Reihe notiert, z.B. <math>X_nX_{n-1}...X_2X_1</math>. Kommt für eine konkrete Vollkonjunktion das jeweilige Literal <math>X_i</math> negiert vor, so ersetzt man es durch eine 0, sonst durch eine 1. Es entsteht eine [[Binärzahl]], die man dezimal interpretieren kann. Diese Dezimalzahl bezeichnet man als die Nummer oder den Index des Minterms. Will man diesen Minterm über seinen Index i bezeichnen, so schreibt man <math>M_i</math>.
+Vollkonjunktionen lassen sich auf natürliche Weise nummerieren. Man denkt sich dabei die Variablen in einer Reihe notiert, z.&nbsp;B. <math>X_nX_{n-1}...X_2X_1</math>. Kommt für eine konkrete Vollkonjunktion das jeweilige Literal <math>X_i</math> negiert vor, so ersetzt man es durch eine 0, sonst durch eine 1. Es entsteht eine [[Binärzahl]], die man dezimal interpretieren kann. Diese Dezimalzahl bezeichnet man als die Nummer oder den Index des Minterms. Will man diesen Minterm über seinen Index <math>i</math> bezeichnen, so schreibt man <math>m_i</math>. Analog geht dies mit den Maxtermen <math>M_i</math> bei Disjunktionen.
+== Vergleich Minterm / Maxterm ==
+In folgender Tabelle ist der Unterschied zwischen der [[Maxterm]]- und Mintermdarstellung ersichtlich:
+{| class="wikitable"
+|-------
+! Index ||<math>x_2</math> ||  <math>x_1</math> || <math>x_0</math> || Minterm || Maxterm
+|------------------------------------------------------------------------------------------
+| 0 || 0  || 0 || 0 || <math>\neg x_2\wedge\neg x_1\wedge \neg x_0</math>|| <math> x_2\vee x_1\vee x_0</math>
+|-------
+|1|| 0 ||  0 ||  1 || <math>\neg x_2\wedge\neg x_1\wedge x_0</math> ||<math> x_2\vee x_1\vee\neg x_0</math>
+|-------
+|2|| 0 ||  1 ||  0|| <math>\neg x_2\wedge x_1\wedge \neg x_0</math>||<math> x_2\vee\neg x_1\vee x_0</math>
+|-------
+|3|| 0 ||  1 ||  1|| <math>\neg x_2\wedge x_1\wedge x_0</math>|| <math> x_2\vee\neg x_1\vee\neg x_0</math>
+|-------
+|4|| 1 ||  0 ||  0|| <math>x_2\wedge\neg x_1\wedge \neg x_0</math>||<math> \neg x_2\vee x_1\vee x_0</math>
+|-------
+|5|| 1 ||  0 ||  1|| <math>x_2\wedge\neg x_1\wedge x_0</math>||<math>\neg x_2\vee x_1\vee \neg x_0</math>
+|-------
+|6|| 1 ||  1 ||  0|| <math>x_2\wedge x_1\wedge \neg x_0</math>||<math>\neg x_2\vee \neg x_1\vee x_0</math>
+|-------
+|7|| 1 ||  1 ||  1|| <math>x_2\wedge x_1\wedge x_0</math>||<math>\neg x_2\vee \neg x_1\vee \neg x_0</math>
+|}
+Realisierung von Decoder-Schaltungen mit Mintermen / Maxtermen:
+{| class="wikitable"
+|-------
+! ||Minterm||Maxterm
+|-----
+|0||NOR-Gatter || AND-Gatter
+|-----
+|1||OR-Gatter || NAND-Gatter
+|}
+=== Bezeichnungen ===
+==== Minterme ====
+* Ein einziger Minterm:
+** Für genau eine Belegung Funktionswert 1
+** Minimalität:
+*** maximale Anzahl an Nullen
+*** '''''minimale''' Anzahl an '''Einsen'''''
+(abgesehen von trivialer Nullfunktion)
+==== Maxterme ====
+* Ein einziger Maxterm:
+** Für genau eine Belegung Funktionswert 0
+** Maximalität:
+*** '''''maximale''' Anzahl an '''Einsen'''''
+*** minimale Anzahl an Nullen
+(abgesehen von trivialer Einsfunktion)
+== Bezug zum Karnaugh-Veitch-Diagramm ==
+Man spricht auch vom ''Minterm einer Funktion <math>F</math>'', wenn dieser ''<math>F</math> impliziert'', d.&nbsp;h. wenn gilt
+:<math>M(X) = 1 \Rightarrow F( X) = 1</math>.
+Dabei ist <math>X</math> der Vektor der Eingangsvariablen. Derartige Minterme <math>M</math> entsprechen umkehrbar eindeutig denjenigen Feldern eines [[Karnaugh-Veitch-Diagramm]]s, die für die betrachtete Funktion den Wert 1 enthalten.
-==Bezug zum Karnaugh-Veitch-Diagrammen==
-Man spricht auch vom ''Minterm einer Funktion F'', wenn dieser ''F impliziert'', d.h. wenn gilt
-:<math>M(\underline X) = 1 \Rightarrow F(\underline X) = 1</math>.
-Dabei ist <math>\underline X</math> der Vektor der Eingangsvariablen. Derartige Minterme M entsprechen umkehrbar eindeutig denjenigen Feldern eines [[Karnaugh-Veitch-Diagramm]]s, die für die betrachtete Funktion den Wert 1 enthalten.
-==Siehe auch==
-*[[Volldisjunktion]]
 [[Kategorie:Logik]]