Función booleana monótona

Una función booleana monótona es una función booleana que aumenta monótonamente (más precisamente, no disminuye) con cada argumento. La clase de todas las funciones booleanas monótonas es una de las cinco clases precompletas .

Definición

Se dice que una función booleana es monótona si se sigue del hecho de que toma un valor en algún conjunto de argumentos , que toma un valor en cualquier conjunto de argumentos , que se obtiene del conjunto de argumentos reemplazando un número arbitrario de ceros con unos [1] . $una$ $a$ $una$ $b$ $a$

Se dice que el conjunto precede al conjunto , ( a lo sumo ) si para todos . ${\tilde {\alpha }}=(\alpha _{1},...\alpha _{n})$ ${\tilde {\beta }}=(\beta _{1},...\beta _{n})$ ${\tilde {\alpha }}\preccurlyeq {\tilde {\beta }}$ ${\tilde {\alpha ))$ ${\tilde {\beta))$ ${\ estilo de visualización \ alfa _ {i} \ leqslant \ beta _ {i}}$ ${\ estilo de visualización i = 1,..., n}$

Si y , entonces se dice que el conjunto precede estrictamente al conjunto , . ${\tilde {\alpha }}\preccurlyeq {\tilde {\beta }}$ ${\tilde {\alpha}}\neq {\tilde {\beta}}$ ${\tilde {\alpha ))$ ${\tilde {\beta))$ ${\tilde {\alpha }}\prec {\tilde {\beta }}$

Se dice que los conjuntos y son comparables si . ${\tilde {\alpha ))$ ${\tilde {\beta))$ ${\tilde {\alpha }}\preccurlyeq {\tilde {\beta }}$ ${\tilde {\beta }}\preccurlyeq {\tilde {\alpha }}$

En el caso de que no se cumpla ninguna de estas relaciones, se dice que los conjuntos son incomparables .

Una función booleana se llama monótona si para cualesquiera dos conjuntos comparables y tales que , se cumple la desigualdad . [2] $f({\tilde {x}}_{n})$ ${\tilde {\alfa}}_{n}$ ${\tilde {\beta}}_{n}$ ${\tilde {\alpha }}\preccurlyeq {\tilde {\beta }}$ $f({\tilde {\alpha }}_{n})\leqslant f({\tilde {\beta }}_{n})$

El conjunto de todas las funciones monótonas del álgebra lógica se denota por , y el conjunto de todas las funciones monótonas booleanas dependientes de variables $METRO$ $norte$ ${\ Displaystyle M^{(n)))$

Véase también

Notas

↑ Kapitonova Yu. V., Krivoy S. L., Letichevsky A. A. Conferencias sobre matemáticas discretas. - SPb., BHV-Petersburg, 2004. - ISBN 5-94157-546-7 , página 112
↑ "Zhuravlev Yu. I., Flerov Yu. A., Fedko O. S." Análisis discreto. Combinatoria. Álgebra de la lógica. Teoría de grafos: libro de texto. subsidio - M. MIPT, 2012-248 p. — ISBN 978-5-7417-0423-3