ВПОРЯДКУВАННЯ ТА ВПОРЯДКОВУВАННЯ В ДИСКРЕТНІЙ МАТЕМАТИЦІ ТА ІНФОРМАТИЦІ

https://doi.org/10.23939/ujit2021.03.037
Надіслано: Березень 17, 2021
Прийнято: Червень 01, 2021
1
Українська академія друкарства, м. Львів, Україна
2
National University of Culture and Arts, Kyiv, Ukraine
3
Українська академія друкарства, м. Львів, Україна

Досліджено наявні засоби впорядкувань й впорядковувань в деяких важливих розділах дискретної математики та інформатики, а саме: в теорії множин, класичній математичній логіці, теорії доведень (доказів), теорії графів, методі Поста, системі алгоритмічних алгебр, алгоритмічних мовах об'єктного і асемблерного програмування. Наведено де­кар­тів добуток множин, впорядковані пари і впорядковані n-ки, опис засобами теорії множин впорядкованої пари, які виконані Вінером, Хаусдорфом і Куратовським. Описано вимоги до відношень, якими впорядковуються множини. Важливість впорядкувань в класичній математичній логіці і теорії доведень проілюстровано прикладами обчислень значень істинності логічних формул і формальним виводом формули на підставі правил виводу і правил заміни. Впорядкування в теорії графів показано на прикладі блок-схеми алгоритму Евкліда, призначеного для знаходження найбільшого спільного дільника двох натуральних чисел. Описано впорядкування та впорядковування як настанов, утворених двома, трьома і чотирма впорядкованими полями так і наявне впорядкування настанов в програмі метода Поста. Показано, що програма, утворена пронумерованими настановами, з неповторюваними номерами настанов і наявністю єдиної настанови з номером 1.

Проілюстровано засоби системи алгоритмічних алгебр, які застосовуються для виконання впорядкувань й впо­ряд­ковувань в теорії алгоритмів. Наведено операції системи алгоритмічних алгебр, які включають узагальнені на трьохзначний алфавіт операції Булевої алгебри та операторні операції операторної алгебри. Описано властивості операції композиції, яка призначена для опису впорядкувань операторів операторної алгебри системи алгоритмічних алгебр. Впорядкування виконувані засобами алгоритмічних мов програмування проілюстровано на гіпотетичному застосуванні сучасної мови об'єктного програмування C#. Програма має містити тільки один метод Main(), з якого починається виконання програми. Асемблерна програма мікропроцесора ARM має мати тільки одну директиву ENTRY, з якої починається виконання програми. Настанови впорядковуються послідовно зверху вниз у вигляді стовпця і записуються в оперативну пам'ять під послідовно впорядкованими адресами. Для виконання переходів застосовуються адреси, записані в настановах переходів. Вектор переривань містить фіксовані адреси комірок пам'яті, в яких записані початкові адреси програм опрацювання переривань.

  1. Gluschkow, W. M., Zeitlin, G. E., & Justchenko, J. L. (1980). Algebra. Sprachen. Programmierung. Akademie-Verlag, Berlin.
  2. Graph (discrete mathematics). Retrieved from https://uk.wikipedia.org/wiki/Граф_(математика)
  3. Hohl, W. (2014). Asembler dla procesorów ARM. Gliwice: Helion.
  4. Kriviy, S.D. (2014). Discrete mathematics. Chernivtsi-Kyiv: Bookrek. [In Ukrainian].
  5. Kuratovsky, K., & Mostovsky, A. (1970). Set theory. Moscow: Mir, 360 p. [In Rusian].
  6. Ordered_pair. Retrieved from https://ru.other.wiki/wiki/Orde red_pair#Wiener%27s_definition
  7. Proof theory. Retrieved from https://uk.wikipedia.org/wiki/ Теорія доведення
  8. Ross, K.A., & Wright, C.R.B. (2008). Matematyka dyskretna. Warszawa: Wydawnictwo naukowe PWN.
  9. Troelsen, E. (2011). C # 2010 programming language and .NET 4.0 platform. Moscow: OOO I. D. Williams. [In Rusian].
  10. Troelsen, E. (2007). C # 2005 programming language and .NET 2.0 platform. Moscow: OOO I. D. Williams. [In Rusian].
  11. Vinogradov, I. M. (Ed.). (1977–1985). Mathematical encyclopedia (Vol. 1–5). Moscow: Soviet Encyclopedia. [In Rusian].
  12. Zeitlin, G. E. (2003). Algebraic Algorithmics: Theory and Applications. Cybernetics and Systems Analysis, 39(1), 6–15. [In Rusian]. https://doi.org/10.1023/A:1023860707232