Monoton boolesk funktion

En monoton boolsk funktion er en boolsk funktion , der øges monotont (mere præcist, ikke falder) med hvert argument. Klassen af alle monotone boolske funktioner er en af de fem prækomplette klasser .

Definition

En boolsk funktion siges at være monotonisk , hvis det følger af det faktum , at den tager en værdi på et sæt af argumenter , at den tager en værdi på et hvilket som helst sæt af argumenter , som fås fra sættet af argumenter ved at erstatte et vilkårligt antal af argumenter . nuller med enere [1] . $en$ $-en$ $en$ $b$ $-en$

Sættet siges at gå forud for sættet , ( højst ) hvis for alle . ${\tilde {\alpha }}=(\alpha _{1},...\alpha _{n})$ ${\tilde {\beta }}=(\beta _{1},...\beta _{n})$ ${\tilde {\alpha }}\preccurlyeq {\tilde {\beta }}$ ${\tilde {\alpha ))$ ${\tilde {\beta ))$ ${\displaystyle \alpha _{i}\leqslant \beta _{i))$ $i=1,...,n$

Hvis og , så siges sættet strengt at gå forud for sættet , . ${\tilde {\alpha }}\preccurlyeq {\tilde {\beta }}$ ${\tilde {\alpha }}\neq {\tilde {\beta }}$ ${\tilde {\alpha ))$ ${\tilde {\beta ))$ ${\tilde {\alpha }}\prec {\tilde {\beta }}$

Sættene og siges at være sammenlignelige, hvis enten . ${\tilde {\alpha ))$ ${\tilde {\beta ))$ ${\tilde {\alpha }}\preccurlyeq {\tilde {\beta }}$ ${\tilde {\beta }}\preccurlyeq {\tilde {\alpha }}$

I det tilfælde, hvor ingen af disse relationer holder, siges sættene at være uforlignelige .

En boolsk funktion kaldes monotonisk, hvis for to sammenlignelige mængder, og sådan at uligheden gælder . [2] $f({\tilde {x}}_{n})$ ${\tilde {\alpha }}_{n}$ ${\tilde {\beta }}_{n}$ ${\tilde {\alpha }}\preccurlyeq {\tilde {\beta }}$ $f({\tilde {\alpha }}_{n})\leqslant f({\tilde {\beta}}_{n})$

Mængden af alle monotone funktioner i logikkens algebra er betegnet med , og mængden af alle monotone boolske funktioner afhængigt af variabler $M$ $n$ ${\displaystyle M^{(n)))$

Se også

Noter

↑ Kapitonova Yu. V., Krivoy S. L., Letichevsky A. A. Forelæsninger om diskret matematik. - SPb., BHV-Petersburg, 2004. - ISBN 5-94157-546-7 , s. 112
↑ "Zhuravlev Yu. I., Flerov Yu. A., Fedko O. S." Diskret analyse. Kombinatorik. Algebra af logik. Grafteori: lærebog. godtgørelse - M. MIPT, 2012-248 s. — ISBN 978-5-7417-0423-3