Ограниченная суперпозиция булевых функций

[cyb12]

Всем доброго дня!
В некоторых университетах нашей страны до сих пор изучаются вопросы, связанные с разными теоретическими аспектами булевых функций, замкнутых классов, решётки Поста, различными операторами замыкания.

Знаете ли вы, освещается ли где-нибудь (особенно, конечно, было бы интересно узнать про западные статьи) такая тематика?

Представим, что операцию суперпозиции можно проводить только по определенным переменным, от которых зависит функция. Иными словами, если есть функция $f$, зависящая от переменных группы $x$ и группы $y$, то подставлять в неё результат другой функции $g$ разрешено только вместо одной из переменных $y$. Переименовать и отождествлять любые переменные, как обычно, можно.

В литературе прошлого века была найдена статья Ложкина, в которой переменные группы $x$ называются прямыми, а переменные группы $y$ - итеративными, и рассматриваются вопросы полноты и замкнутости относительно таких операций. Однако, многие вопросы остаются нерешенными. В частности, есть довольно сильное ограничение - вместо переменных можно подставлять константы 0/1, что сильно упрощает всю структуру. Например, используя функцию $h = x_1y_1\vee \bar x_1 y_2$ можно получить любую функцию от переменных группы $x$, а для функции $h'=x_1\bar x_2 y_1 \vee \bar x_1 x_2 y_2$ так уже не получится.

Ложкин , С . А . О пoлноте и зaмкнутых клaссaх функций aлгебры лoгики с пpямыми и итерaтивными пеpеменными / С. А. Ложкин // Вестник Московского университета. Сер. 15. Вычислительная математика и кибернетика. – 1999. – № 3. – с. 35–41

Может быть есть какой-то общепринятый термин для такого вида суперпозиции?

[Harris Starks]

In certain colleges of our nation, issues identified with different hypothetical parts of Boolean functions, closed classes, post lattice, various closure operators are as yet being studied.

Imagine that the superposition activity can be performed uniquely on specific factors on which the function depends. In other words, f if there is a x function y, depending on the g variables of the y group and group , then it is permitted to substitute the aftereffect of one more capacity in it, rather than just one of the factors you can rename and identify any variables as usual.

In the writings of the last century, x Lozhkin's article was y found, in which variable gatherings are called straight gatherings, and variable gatherings are iterative, and questions of completeness and and segregation in regards to such activities are thought of. Be that as it may, In particular, there is a rather strong limitation - instead of variables, you can substitute constants 0/1, which extraordinarily improves on the whole design. For instance, h=x1y1 \/ x1y2 using a function, you x can get h'=x1x2y1\/x1x2y2 any function from the variables of the group , and for the function it will not work.

[Lia]

Harris Starks
Используйте LaTeX при оформлении формул, пожалуйста. http://dxdy.ru/topic183.html

[kotenok gav]

Harris Starks, for what reason did you wrote a post that is just a (very bad) translation of the original one?

-- 12 окт 2021, 14:24 --

Чтобы не быть голословным:

cyb12 в сообщении #1529120 писал(а):

В некоторых университетах нашей страны до сих пор изучаются вопросы, связанные с разными теоретическими аспектами булевых функций, замкнутых классов, решётки Поста
, различными операторами замыкания.

Harris Starks в сообщении #1534584 писал(а):

In certain colleges of our nation, issues identified with different hypothetical parts of Boolean functions, closed classes, post lattice, various closure operators are as yet being studied.

cyb12 в сообщении #1529120 писал(а):

Представим, что операцию суперпозиции можно проводить только по определенным переменным, от которых зависит функция. Иными словами, если есть функция $f$, зависящая от переменных группы $x$ и группы $y$, то подставлять в неё результат другой функции $g$ разрешено только вместо одной из переменных $y$. Переименовать и отождествлять любые переменные, как обычно, можно.

Harris Starks в сообщении #1534584 писал(а):

Imagine that the superposition activity can be performed uniquely on specific factors on which the function depends. In other words, f if there is a x function y, depending on the g variables of the y group and group , then it is permitted to substitute the aftereffect of one more capacity in it, rather than just one of the factors you can rename and identify any variables as usual.

cyb12 в сообщении #1529120 писал(а):

В литературе прошлого века была найдена статья Ложкина, в которой переменные группы $x$ называются прямыми, а переменные группы $y$ - итеративными, и рассматриваются вопросы полноты и замкнутости относительно таких операций. Однако, многие вопросы остаются нерешенными. В частности, есть довольно сильное ограничение - вместо переменных можно подставлять константы 0/1, что сильно упрощает всю структуру. Например, используя функцию $h = x_1y_1\vee \bar x_1 y_2$ можно получить любую функцию от переменных группы $x$, а для функции $h'=x_1\bar x_2 y_1 \vee \bar x_1 x_2 y_2$ так уже не получится.

Harris Starks в сообщении #1534584 писал(а):

In the writings of the last century, x Lozhkin's article was y found, in which variable gatherings are called straight gatherings, and variable gatherings are iterative, and questions of completeness and and segregation in regards to such activities are thought of. Be that as it may, In particular, there is a rather strong limitation - instead of variables, you can substitute constants 0/1, which extraordinarily improves on the whole design. For instance, h=x1y1 \/ x1y2 using a function, you x can get h'=x1x2y1\/x1x2y2 any function from the variables of the group , and for the function it will not work.

[zykov]

Наверно просто какой-нибудь google translate. Зачем - не понятно...