Представления нормализованных формул

Представления нормализованных формул

Рычков К. Л.
Дискретный анализ и исследование операций, 29, 4, 77-103 (2022)
Скачать статью

УДК 519.714 
DOI: 10.33048/daio.2022.29.751

Аннотация:

Определён класс названных $\Pi$-разбиениями объектов, которые в некотором вполне определённом смысле являются эквивалентами формул в базисе, состоящем из дизъюнкции, конъюнкции и отрицания, в которых отрицания возможны только над переменными (нормализованные формулы). $\Pi$-разбиения рассматриваются в качестве представлений этих формул подобно тому, как эквивалентами и графическими изображениями тех же самых формул можно считать $\Pi$-схемы. Разработана некоторая теория таких представлений, которая по сути является математическим аппаратом, ориентированным на описание класса реализующих линейные булевы функции минимальных нормализованных формул. 
Библиогр. 18.

Литература:
  1. Храпченко В. М. О сложности реализации линейной функции в классе $\Pi$-схем // Мат. заметки. 1971. Т. 9, № 1. С. 35–40. 
     
  2. Яблонский С. В. Реализация линейной функции в классе $\Pi$-схем // Докл. АН СССР. 1954. Т. 94, № 5. С. 805–806. 
     
  3. Рычков К. Л. О нижних оценках сложности параллельно-последовательных контактных схем, реализующих линейные булевы функции // Сиб. журн. исслед. операций. 1994. Т. 1, № 4. С. 33–52. 
     
  4. Черухин Д. Ю. К вопросу о логическом представлении счётчика чётности // Неформальная наука. 2009. № 2. С. 14–23. 
     
  5. Рычков К. Л. О нижних оценках формульной сложности линейной булевой функции // Сиб. электрон. мат. изв. 2014. Т. 11. С. 165–184. 
     
  6. Рычков К. Л. О сложности реализации линейной булевой функции в классе $\pi$-схем // Дискрет. анализ и исслед. операций. 2018. Т. 25, № 3. С. 36–94.
     
  7. Рычков К. Л. О минимальных $\pi$-схемах для линейных булевых функций // Методы дискретного анализа в синтезе схем булевых функций. Вып. 51. Новосибирск: Изд-во Ин-та математики, 1991. С. 84–104. 
     
  8. Рычков К. Л. Достаточные условия локальной бесповторности минимальных $\pi$-схем, реализующих линейные булевы функции // Дискрет. анализ и исслед. операций. 2015. Т. 22, № 5. С. 71–85. 
     
  9. Рычков К. Л. О совершенности минимальных правильных разбиений множества рёбер $n$-мерного куба // Дискрет. анализ и исслед. операций. 2019. Т. 26, № 4. С. 74–107. 
     
  10. Храпченко В. М. Об одном методе получения нижних оценок сложности $\Pi$-схем // Мат. заметки. 1971. Т. 10, № 1. С. 83–92. 
     
  11. Субботовская Б. А. О реализации линейных функций формулами в базисе $\lor , \land , -$ // Докл. АН СССР. 1961. Т. 136, № 3. С. 553–555. 
     
  12. Храпченко В. М. Упрощённое доказательство одной нижней оценки сложности // Дискрет. математика. 2013. Т. 25, № 2. С. 82–84. 
     
  13. Августинович С. В., Васильев Ю. Л., Рычков К. Л. Формульная сложность тернарной линейной функции // Дискрет. анализ и исслед. операций. 2012. Т. 19, № 3. С. 3–12. 
     
  14. Васильев Ю. Л., Рычков К. Л. Нижняя оценка формульной сложности тернарной линейной функции // Дискрет. анализ и исслед. операций. 2013. Т. 20, № 4. С. 15–26. 
     
  15. Сергеев И. С. Формульная сложность линейной функции в $k$-арном базисе // Мат. заметки. 2021. Т. 109, № 3. С. 419–435. 
     
  16. Razborov A. Applications of matrix methods to the theory of lower bounds in computational complexity // Combinatorica. 1990. V. 10, No. 1. P. 81–93. 
     
  17. Karchmer M., Wigderson A. Monotone circuits for connectivity require super-logarithmics depth // SIAM J. Discrete Math. 1990. V. 3, No. 2. P. 255–265. 
     
  18. Håstad J. The shrinkage exponent is 2 // SIAM J. Comput. 1998. V. 27. P. 48–64.

Исследование выполнено в рамках государственного задания ИМ СО РАН (проект № FWNF–2022–0017).

Рычков Константин Леонидович
  1. Институт математики им. С. Л. Соболева,
    пр. Коптюга, 4, 630090 Новосибирск, Россия

E-mail: rychkov@math.nsc.ru

Статья поступила 26 августа 2022 г. 
После доработки — 26 августа 2022 г. 
Принята к публикации 31 августа 2022 г.

Abstract:

A class of objects called $\Pi$-partitions is defined. These objects, in a certain well-defined sense, are the equivalents of formulas in a basis consisting of disjunction, conjunction and negation, in which negations are possible only over variables (normalized formulas). $\Pi$-partitions are seen as representations of formulas, just as equivalents and graphical representations of the same formulas can be considered $\Pi$-schemes. Some theory of such representations has been developed which is essentially a mathematical apparatus focused on describing a class of minimal normalized formulas implementing linear Boolean functions. 
Bibliogr. 18.

References:
  1. V. M. Khrapchenko, Complexity of the realization of a linear function in the class of $\Pi$-circuits, Mat. Zametki 9 (1), 35–40 (1971) [Russian] [Math. Notes Acad. Sci. USSR 9 (1), 21–23 (1971)].
     
  2. S. V. Yablonskii, Realization of a linear function in the class of $\Pi$-circuits, Dokl. Akad. Nauk SSSR, Nov. Ser. 94 (5), 805–806 (1954).
     
  3. K. L. Rychkov, Lower bounds on the complexity of parallel-sequential switching circuits that realize linear Boolean functions, Sib. Zh. Issled. Oper. 1 (4), 33–52 (1994) [Russian] [Discrete Analysis and Operation Research (Kluwer Acad. Publ., Dordrecht, 1996), pp. 217–234 (Math. Its Appl., Vol. 355)].
     
  4. D. Yu. Cherukhin, To the question of a logical representation for the parity counter, Neform. Nauka, No. 2, 14–23 (2009).
     
  5. K. L. Rychkov, Lower bounds on the formula complexity of a linear Boolean function, Sib. Elektron. Mat. Izv. 11, 165–184 (2014).
     
  6. K. L. Rychkov, Complexity of the realization of a linear boolean function in the class of $\pi$-schemes, Diskretn. Anal. Issled. Oper. 25 (3), 36–94 (2018) [Russian] [J. Appl. Ind. Math. 12 (3), 540–576 (2018)].
     
  7. K. L. Rychkov, On minimal $\pi$-schemes for linear Boolean functions, Methods of Discrete Analysis in Synthesis of Schemes for Boolean Functions, Vol. 51 (Izd. Inst. Mat., Novosibirsk, 1991), pp. 84–104 [Russian] [Sib. Adv. Math. 3 (3), 172–185 (1993)].
     
  8. K. L. Rychkov, Sufficient conditions for the minimal $\pi$-schemes for linear Boolean functions to be locally non-repeating, Diskretn. Anal. Issled. Oper. 22 (5), 71–85 (2015) [Russian] [J. Appl. Ind. Math. 9 (4), 580–587 (2015)].
     
  9. K. L. Rychkov, On the perfectness of minimal regular partitions of the edge set of the $n$-dimensional cube, Diskretn. Anal. Issled. Oper. 26 (4), 74–107 (2019) [Russian] [J. Appl. Ind. Math. 13 (4), 717–739 (2019)].
     
  10. V. M. Khrapchenko, A method of determining lower bounds for the complexity of $\Pi$-schemes, Mat. Zametki 10 (1), 83–92 (1971) [Russian] [Math. Notes Acad. Sci. USSR 10 (1), 474–479 (1971)].
     
  11. B. A. Subbotovskaya, Realization of linear functions by formulas using $\lor, \land, -$, Dokl. Akad. Nauk 136 (3), 553–555 (1961).
     
  12. V. M. Khrapchenko, A simplified proof of a lower complexity estimate, Discrete Math. 25 (2), 82–84 (2013) [Russian] [Discrete Math. Appl. 23 (2), 171–174 (2013)].
     
  13. S. V. Avgustinovich, Yu. L. Vasil’ev, and K. L. Rychkov, The computation complexity in the class of formulas, Diskretn. Anal. Issled. Oper. 19 (3), 3–12 (2012) [Russian] [J. Appl. Ind. Math. 6 (4), 403–409 (2012)].
     
  14. Yu. L. Vasil’ev and K. L. Rychkov, A lower bound on formula size of a ternary linear function, Diskretn. Anal. Issled. Oper. 20 (4), 15–26 (2013) [Russian] [J. Appl. Ind. Math. 7 (4), 490–499 (2013)].
     
  15. I. S. Sergeev, Formula complexity of a linear function in a $k$-ary basis, Mat. Zametki 109 (3), 419–435 (2021) [Russian] [Math. Notes 109 (3), 445–458 (2021)].
     
  16. A. Razborov, Applications of matrix methods to the theory of lower bounds in computational complexity, Combinatorica 10 (1), 81–93 (1990).
     
  17. M. Karchmer and A. Wigderson, Monotone circuits for connectivity require super-logarithmic depth, SIAM J. Discrete Math. 3 (2), 255–265 (1990).
     
  18. J. Håstad, The shrinkage exponent is 2, SIAM J. Comput. 27 (1), 48–64 (1998).