Все выпуски

В данной работе представлен новый подход к интерпретации логических формул для синтеза алгоритмов и программ. Предложенный метод сочетает в себе черты реализации Клини и интерпретации Гёделя «диалектика», но не опирается на них непосредственно. Рассматривается простой вариант позитивного языка логики предикатов без функций, с конъюнкцией, дизъюнкцией, импликацией и кванторами всеобщности и существования. Описана новая реализационная семантика формул и секвенций, в которой рассматривается не просто реализация формулы, а реализация с дополнительной поддержкой. Реализация примерно соответствует реализации Клини. Поддержка предоставляет дополнительные данные в пользу того, что реализация корректна. Поддержка должна подтвердить, что реализация работает корректно для формулы в любых корректных условиях применения. Представлен язык доказательств, для которого доказана теорема о корректности, показывающая, что любая выводимая секвенция имеет реализацию и поддержку, подтверждающую, что эта реализация работает правильно для этой формулы в любых корректных условиях при подходящем интерпретаторе используемых программ.

This paper presents a novel approach to interpreting logical formulas for synthesizing algorithms and programs. The proposed method combines features of Kleene realizability and Gödel's “dialectica” interpretation but does not rely on them directly. A simple version of positive predicate logic without functions is considered, including conjunction, disjunction, implication, and universal and existential quantifiers. A new realizability semantics for formulas and sequents is described, which considers not just a realization of a formula, but a realization with additional support. The realization roughly corresponds to Kleene realizability. The support provides additional data in favor of the correctness of the realization. The support must confirm that the realization works correctly for the formula under any valid conditions of application. A proof language is presented for which a correctness theorem is proved showing that any derivable sequent has a realization and support confirming that this realization works correctly for this formula under any valid conditions with a suitable interpreter for the programs used.

Для общей краевой задачи функционально-дифференциального уравнения получены условия непрерывной зависимости решения от параметров. Результаты применены к исследованию корректности линейной общей краевой задачи для нелинейного дифференциального уравнения с отклоняющимся аргументом и непрерывной зависимости периодических решений управляемых систем от значений управления и отклонения аргумента.

Conditions for continuous dependence on parameters of solution of a general boundary value problem are obtained for a functional-differential equation. The results are applied to investigation of a correctness of a linear general boundary value problem for the nonlinear differential equation with divergentargument and to problem of continuous dependence of periodic solutions of controllable system on control and divergence values.

Работа посвящена исследованию свойства замкнутости относительно операции сложения множества равномерных почти периодических функций. Показано, что доказательство этого свойства, проведенное в монографии Б.П. Демидовича «Лекции по математической теории устойчивости», содержит пробел. Приведено корректное доказательство.

We study the property of the closedness of the set of uniformly almost periodic functions with respect to the operation of addition. It is shown that the proof of this property found in the monograph by B.P. Demidovich “Lectures on the mathematical theory of stability” is not quite correct. A valid proof is given.

После статьи Молодцова [Molodtsov D. Soft set theory — First results // Computers and Mathematics with Applications. 1999. Vol. 37. No. 4-5. P. 19-31.] теория мягких множеств начала стремительно развиваться. Несколько авторов ввели различные операции, отношения, результаты и т.д., а также другие аспекты в теории мягких множеств и гибридных структур некорректно, несмотря на их широкое применение в математике и смежных областях. В своей работе [Molodtsov D.A. Equivalence and correct operations for soft sets // International Robotics and Automation Journal. 2018. Vol. 4. No. 1. P. 18-21.], Молодцов, отец теории мягких множеств, указал на несколько неверных результатов и понятий. Молодцов [Молодцов Д.А. Структура мягких множеств // Нечеткие системы и мягкие вычисления. 2017. Т. 12. Вып. 1. С. 5-18.] также заявил, что понятие мягкого множества не везде было полностью понято и использовано. В связи с этим важно пересмотреть причуды этих представлений и дать формальное изложение понятия эквивалентности мягкого множества. Молодцов уже исследовал многие корректные операции над мягкими множествами. Мы используем некоторые понятия и результаты Молодцова [Молодцов Д.А. Структура мягких множеств // Нечеткие системы и мягкие вычисления. 2017. Т. 12. Вып. 1. С. 5-18.] для создания матричных представлений, а также связанных с ними операций над мягкими множествами, и для количественной оценки сходства между двумя мягкими множествами.

After the paper of Molodtsov [Molodtsov D. Soft set theory — First results, Computers and Mathematics with Applications, 1999, vol. 37, no. 4-5, pp. 19-31.] first appeared, soft set theory grew at a breakneck pace. Several authors have introduced various operations, relations, results, etc. as well as other aspects in soft set theory and hybrid structures incorrectly, despite their widespread use in mathematics and allied areas. In his paper [Molodtsov D.A. Equivalence and correct operations for soft sets, International Robotics and Automation Journal, 2018, vol. 4, no. 1, pp. 18-21.], Molodtsov, the father of soft set theory, pointed out several wrong results and notions. Molodtsov [Molodtsov D.A. Structure of soft sets, Nechetkie Sistemy i Myagkie Vychisleniya, 2017, vol. 12, no. 1, pp. 5-18.] also stated that the concept of soft set had not been fully understood and used everywhere. As a result, it is important to revisit the quirks of those conceptions and provide a formal account of the notion of soft set equivalency. Molodtsov already explored many correct operations on soft sets. We use some notions and results of Molodtsov [Molodtsov D.A. Structure of soft sets, Nechetkie Sistemy i Myagkie Vychisleniya, 2017, vol. 12, no. 1, pp. 5-18.] to create matrix representations as well as related operations of soft sets, and to quantify the similarity between two soft sets.

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

An alternative way for describing reaction-diffusion systems of chemical kinetics on the basis of ordinary differential equations is considered in this paper. Under this approach, diffusion of matter and heat transfer in the model are taken into account without going to the partial derivatives, but only by increasing the number of variables and the addition of corrective coefficients in the original equations. As a base model of chemical kinetics was chosen the one, in which there was no such drawbacks of classical models, as the inconsistency of the equations on the dimension or scale.

Рассматривается процедура встраивания оптимизируемых фрагментов маршрутных решений в глобальные решения «большой» задачи, определяемые эвристическими алгоритмами. Постановка задачи маршрутизации учитывает некоторые особенности инженерной задачи о последовательной резке деталей, имеющих каждая один внешний и, возможно, несколько внутренних контуров. Последние должны подвергаться резке раньше внешнего, что приводит к большому числу условий предшествования. Данные условия активно используются в интересах снижения сложности вычислений. Тем не менее размерность задачи остается достаточно большой, что, в частности, не позволяет применять «глобальное» динамическое программирование и вынуждает к использованию эвристических алгоритмов (исследуемая задача относится к числу труднорешаемых в традиционном понимании). Поэтому представляет интерес разработка методов коррекции решений, получаемых на основе упомянутых алгоритмов. В настоящей работе такая коррекция реализуется посредством замены фрагментов (упомянутых решений), имеющих умеренную размерность, оптимальными «блоками», конструируемыми на основе динамического программирования с локальными условиями предшествования, которые согласуются с ограничениями исходной «большой» задачи. Предлагаемая замена не ухудшает, а, в типичных случаях, улучшает качество исходного «эвристического» решения, что подтверждается вычислительным экспериментом на многоядерной ПЭВМ.

Предложенный алгоритм реализован в итерационном режиме: полученное после первой вставки на основе динамического программирования решение в виде пары «маршрут-трасса» принимается за исходное, для которого вновь конструируется вставка. При этом начало этой новой вставки выбирается случайно в пределах, определяемых возможностями формирования скользящего «окна» ощутимой, но все же достаточной для применения экономичной версии динамического программирования размерности. Далее процедура повторяется. Работа итерационного алгоритма иллюстрируется решением модельных задач, включая варианты с достаточно плотной «упаковкой» заготовок деталей на листе, что типично для машиностроительного производства.

The article is concerned with the procedure of insertion of optimizable fragments of route solutions into the global solutions of the «big» problem defined by heuristic algorithms. Setting of the route problem takes into account some singularities of the engineering problem about the sequential cutting of details each having one exterior and probably several interior contours. The latter ones must be subjected to cutting previously in comparison with the exterior contour, which leads to a great number of given preceding conditions. These conditions are actively used to decrease the computational complexity. Nevertheless, the problem dimensionality remains sufficiently large that does not permit to use “global’’ dynamic programming and forces heuristic algorithms to be used (the problem under investigation is a hard-solvable problem in the traditional sense). Therefore, it is interesting to develop the methods for correction of solutions based on the above-mentioned algorithms. In the present investigation, such correction is realized by the replacement of fragments (of the above-mentioned solutions) having a moderate dimensionality by optimal “blocks’’ constructed by dynamic programming with local preceding conditions which are compatible with the constraints of the initial “big’’ problem. The proposed replacement does not deteriorate, but, in typical cases, improves the quality of the initial heuristic solution. This is verified by the computing experiment on multi-core computer.

The proposed algorithm is realized in the iterated regime: the solution (in the form of “route-trace’’) obtained after the first insertion on the basis of dynamic programming is taken as an initial solution for which the insertion is constructed again. In addition, the beginning of the new insertion is chosen randomly in the bounds defined by the possibilities of formation of a sliding “window’’ of the appreciable dimensionality which is in fact sufficient for the employment of the economical version of dynamic programming. Further, the procedure is repeated. The operation of the iterated algorithm is illustrated by solution of model problems including the versions with sufficiently dense “packing’’ of parts on a sheet, which is typical for the engineering production.

Рассматривается новое конструктивное понимание логических формул, согласованное с интуицией и с традиционными средствами конструктивного логического вывода. Новое понимание логически проще традиционной реализуемости (в смысле кванторной глубины), но является также естественным с точки зрения алгоритмического решения задач. Это понимание, кроме свидетельства (реализации, подтверждения) понимаемой формулы, привлекает понятия теста (противодействия, препятствия) этой реализации на данной формуле. Для понимания формулы $A$ рассматриваются предложения вида $a:A:b.$ Это предложение означает, что объект $a$ (выдвигаемый в подтверждение формулы $A$) выигрывает у объекта $b$ (который противодействует выполнению формулы $A$) формулу $A$ в процессе осуществления специальной процедуры сопоставления этих объектов друг с другом и с данной формулой. Данная процедура может считаться некоторой процедурой арбитража для вынесения необходимого решения. Базис процедуры арбитража для атомарных формул задается интерпретацией языка. Процедура для сложных предложений задается специальными правилами определения смысла логических связок. При наиболее естественном определении процедура арбитража имеет полиномиальную временную сложность. Формула $A$ считается истинной в новом смысле этого слова, если имеется подтверждение, выигрывающее ее у всех возможных противодействий. Рассматривается логический язык без отрицаний. Доказана теорема о корректности в новом смысле традиционных интуиционистских аксиом и правил вывода. При этом рассматривается секвенциальное логическое исчисление, ориентированное на обратный метод поиска вывода.

A new constructive understanding of logical formulas is considered. This understanding corresponds to intuition and traditional means of constructive logical inference. The new understanding is logically simpler than traditional realizability (in the sense of quantifier depth), but it also natural with respect to algorithmic solution of tasks. This understanding uses not only witness (realization) of the formula to understand but it also uses notion of test (counteraction) of this realization at the given formula. The main form of a sentence to understand a formula $A$ is $a:A:b$, that means that “the witness $a$ wins the obstacle $b$ while trying to approve the formula $A$”. This procedure can be regarded as a procedure of arbitration for making the necessary solution. The basis of the arbitration procedure for atomic formulas is defined by the interpretation of the language. The procedure for complex sentences is given by special rules determining the meaning of logical connectives. In the most natural definition of the arbitration procedure it has polynomial time complexity. A formula $A$ is considered to be true in the new sense if there is a witness of the formula that wins all possible obstacles at the formula. A language without negation is considered. A theorem of correctness of traditional intuitionistic axioms and inference rules is proved. The system of logical inference is formulated in sequent form. It is oriented to the inverse method of logical inference search.

Продолжаются исследования автора по теории правильных функций и *-интеграла. Изучается возможность представления правильной функции в виде суммы непрерывной справа и непрерывной слева функций ($rl$-представимости). Доказывается предельная теорема для *-интеграла, позволяющая приближать разрывные интегрируемую и интегрирующую функции последовательностями абсолютно непрерывных функций. Доказана новая теорема о $\delta$-корректности решения обыкновенного линейного дифференциального уравнения с обобщенными функциями в коэффициентах, определяемого с помощью квазидифференциального уравнения. Получена формула для вычисления полной вариации неопределенного *-интеграла от $\sigma$-непрерывной функции по функции ограниченной вариации, обобщающая известную формулу для полной вариации абсолютно непрерывной функции. Формула интересна и в случае неопределенного $RS$-интеграла.

This work continues the author's research on the theory of regulated functions and *-integral. The possibility to express a regulated function as a sum of right-continuous and left-continuous functions (called $rl$-representation) is studied. A limit theorem for the *-integral is proved. It allows approximating discontinuous integrands and integrators by sequences of absolutely continuous functions. A new result on $\delta$-correctness of the solution of an ordinary linear differential equation with generalized functions in coefficients is proved. This solution is defined via a quasi-differential equation. A formula for the total variation of an indefinite *-integral of a $\sigma$-continuous function with respect to a function of bounded variation is given. It generalizes the well-known formula for computing the total variation of an absolutely continuous function. The formula is also interesting in the case of an indefinite $RS$-integral.

В данной статье для одного дифференциального уравнения в частных производных высокого четного порядка с оператором Бесселя в прямоугольной области сформулированы две нелокальные начально-граничные задачи. Исследована корректность одной из поставленных задач. При этом применением метода разделения переменных к изучаемой задаче получена спектральная задача для обыкновенного дифференциального уравнения высокого четного порядка. Доказана самосопряженность последней задачи, откуда следует существование системы ее собственных функций, а также ортонормированность и полнота этой системы. Далее, построена функция Грина спектральной задачи, с помощью чего она эквивалентно сведена к интегральному уравнению Фредгольма второго рода с симметричным ядром. С помощью этого интегрального уравнения и теоремы Мерсера исследована равномерная сходимость некоторых билинейных рядов, зависящих от найденных собственных функций. Установлен порядок коэффициентов Фурье. Решение изучаемой задачи выписано в виде суммы ряда Фурье по системе собственных функций спектральной задачи. Доказана равномерная сходимость этого ряда, а также рядов, полученных из него почленным дифференцированием. Методом спектрального анализа доказана единственность решения задачи. Получена оценка для решения задачи, откуда следует его непрерывная зависимость от заданных функций.

In the present paper, two non-local initial-boundary value problems have been formulated for a partial differential equation of high even order with a Bessel operator in a rectangular domain. The correctness of one of the considered problems has been investigated. To do this, applying the method of separation of variables to the problem under consideration, the spectral problem was obtained for an ordinary differential equation of high even order. The self-adjointness of the last problem was proved, which implies the existence of the system of its eigenfunctions, as well as orthonormality and completeness of this system. Further, the Green's function of the spectral problem was constructed, with the help of which it was equivalently reduced to the Fredholm integral equation of the second kind with symmetrical kernel. Using this integral equation and Mercer's theorem, the uniform convergence of some bilinear series depending on found eigenfunctions has been studied. The order of the Fourier coefficients was established. The solution of the considered problem has been written as the sum of a Fourier series with respect to the system of eigenfunctions of the spectral problem. The uniform convergence of this series and also the series obtained from it by term-by-term differentiation was proved. Using the method of spectral analysis, the uniqueness of the solution of the problem was proved. An estimate for the solution of the problem was obtained, from which its continuous dependence on the given functions follows.

В теории игр и теории исследования операций часто появляется минимакс от функции $f(x,y)$, зависящей от двух векторных переменных $x$, $y$. Изучению свойств минимакса (или максимина) посвящено много работ. Минимакс можно трактовать как наименьший гарантированный результат для минимизирующего игрока (минимизирующей оперирующей стороны). При изучении минимаксных задач определенный интерес представляют различные вопросы о корректности. Одному из таких вопросов посвящена настоящая статья. В ней векторы $x$, $y$ принадлежат компактам $P$, $Q$ из соответствующих евклидовых пространств $R^k$, $R^l$, а функция $f(x,y)$ непрерывна на произведении пространств $R^k\times R^l$. В статье рассматривается вопрос о зависимости минимакса от малых изменений компактов $P$, $Q$ в метрике Хаусдорфа. Обосновывается непрерывность зависимости минимакса от малых вариаций множеств $P$, $Q$.

In game theory and operations research theory, a minimax often appears for a function $f(x,y)$ that depends on two vector variables $x$, $y$. Many works have been devoted to the study of the properties of minimax (or maximin). A minimax can be interpreted as the smallest guaranteed result for the minimizing player (the minimizing operator). In the study of minimax problems, various correctness issues are of some interest. This paper is devoted to one of these issues. In it, vectors $x$, $y$ belong to compacts $P$, $Q$ of corresponding Euclidean spaces $R^k$, $R^l$, and function $f(x,y)$ is continuous on product of spaces $R^k\times R^l$. The paper considers the dependence of minimax on small changes of compacts $P$, $Q$ in the Hausdorff metric. The continuity of the dependence of minimax on small variations of compacts $P$, $Q$ is proved.