2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Ограниченная суперпозиция булевых функций
Сообщение20.08.2021, 10:31 


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

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

Представим, что операцию суперпозиции можно проводить только по определенным переменным, от которых зависит функция. Иными словами, если есть функция $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

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

 Профиль  
                  
 
 Re: Ограниченная суперпозиция булевых функций
Сообщение11.10.2021, 16:11 


26/07/21
18
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.

 Профиль  
                  
 
 Re: Ограниченная суперпозиция булевых функций
Сообщение11.10.2021, 16:14 


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

 Профиль  
                  
 
 Re: Ограниченная суперпозиция булевых функций
Сообщение12.10.2021, 07:48 


21/05/16
4292
Аделаида
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.

 Профиль  
                  
 
 Re: Ограниченная суперпозиция булевых функций
Сообщение12.10.2021, 11:43 


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group