Matematické Fórum

Prochycz · 05. 03. 2016 10:08

Zdravím zdejší diskutující, :-)

setkal se někdo s pojmem "minimální polynom" v booleově algebře? Mám následující příklad:

Je zadána funkce $f(x_3,x_2,x_1,x_0)$ s příslušnými indexy 1, 3, 5, 10, 12, 13, 15.

Otázka:
Kolik je minimálních polynomů?

Pořádně nerozumím tomu, co se po mě chce. Jediný co mě napadlo, je minimalizovat funkci, což není pro zadanou funkci problém.

$f(x_3,x_2,x_1,x_0)=\bar{x_3}\bar{x_2}x_0+x_3\bar{x_2}\bar{x_1}\bar{x_0}+x_3 x_2 \bar{x_1}+x_3 x_2 x_0 +\bar{x_3}\bar{x_1} x_0$

Správná odpověď je 2, ale nevím, jak se na to přišlo.

Ale, co pořádně znamená ten minimální polynom nevím. Myslel jsem si, že to bude počet členu v minimalizovaný funkci, ale tak to asi nebude.

Definici minimální polynom pro booleovu algebru jsem našel v německé literatuře:

Sei M ein Polynom für $f: B^n \rightarrow B^1$
M heißt Minimalpolynom (für f), wenn es kein Polynom geringer Länge für f gibt.
Die Länge eines Polynoms ist definiert als die Anzahl der Literale, die es enthält.

Do češtiny, pravděpodobně:
Buď M polynom pro $f: B^n \rightarrow B^1$
M znamená minimální polynom (pro f), když není žádný polynom nepatrné délky pro f.
Délka polynomu je definována jako množství literálů, které obsahuje.

Děkuji za případné rady. :-)

Prochycz · 05. 03. 2016 11:24

Tak už jsem na to asi přišel. Divím se, že mě to nenapadlo dřív. Pravděpodobně to znamená, kolika způsoby můžu napsat minimalizovanou funkci. Jelikož funkci můžu zapsat ve dvou formách (podle toho, jakou smyčku si v karnaghově mapě vyberu):
$f(x_3,x_2,x_1,x_0)=\bar{x_3}\bar{x_2}x_0+x_3\bar{x_2}\bar{x_1}\bar{x_0}+x_3 x_2 \bar{x_1}+x_3 x_2 x_0 +\bar{x_3}\bar{x_1} x_0$
$f(x_3,x_2,x_1,x_0)=\bar{x_3}\bar{x_2}x_0+x_3\bar{x_2}\bar{x_1}\bar{x_0}+x_3 x_2 \bar{x_1}+x_3 x_2 x_0 +x_2\bar{x_1} x_0$

Matematické Fórum

#1 05. 03. 2016 10:08

Booleova algebra - Minimální polynom

#2 05. 03. 2016 11:24

Re: Booleova algebra - Minimální polynom

Zápatí