Microsoft Word - Manukian-revised.doc


Mathematical Problems of Computer Science 37, 64--74, 2012. 

 
64 

 

 
 

Some Algebraical and Logical Properties of Two-
dimensional Arithmetical Sets Representable in 

Presburger’s System1 
 

Seda N. Manukian 
 

Institute for Informatics and Automation Problems of NAS of RA 
e-mail: zaslav@ipia.sci.am 

 
 

Abstract 
 
 

A classification ...)2()1()0(  HHH  of arithmetical sets representable in 
M.Presburger’s system ([1]-[4]) and a classification ...)2()1()0(  HHH  of two-
dimensional sets of the same kind are considered. It is proved that these classifications 
are strictly monotone and complete. The operations  ,  , ,  , 1  on two-
dimensional arithmetical sets ([5]-[7]) and the algebras  0  and 1 based on these 
operations ([5]-[7]) are considered. The relations of these operations and algebras to 
the mentioned classifications are investigated. 

 
 
References 
 
[1] M. Presburger, “ Über die Vollstaendigkeit eines gewissen System der Arithmetik ganzer Zahlen, in 
welchem die Addition als einige Operation hervortritt”, Comptes Rendu du I Congres des Mathematiciens 
des Pays Slaves, Warszawa, pp. 92-101, 1930. 
[2] D. Hilbert und P. Bernays. Grundlagen der Mathematik. Band I. Zweite Auflage, Berlin-Heidelberg-
New York, Springer Verlag, 1968.  
[3] R. Stansifer. Presburger's Article on Integer Arithmetic: Remarks and Translation. Department of 
Computer Science, Cornell University, Ithaca, New York, 1984. 
[4] H. Enderton. A Mathematical Introduction to Logic. 2nd ed., San Diego, Harcourt, Academic Press, 
2001. 
[5] S. N. Manukian, “Algebras of  Recursively Enumerable Sets and Their Applications to Fuzzy 
Logic”, Journal of Mathematical Sciences, vol. 130, №2, pp. 4598-4606, 2005. 
[6] S. N. Manukian, “A Classification of Arithmetical Sets Expressible in Presburger's System”, 
Proceedings of the International Conference «Computer Science and Information Technologies», CSIT-
05, Yerevan, Armenia, pp. 161-162, 2005. 
[7] S. N. Manukian, “On the Representation of Recursively Enumerable Sets in Weak Arithmetic. 
Mathematical Problems of Computer Science, vol. 27, pp. 90-110, 2006. 

                                                
1 This work is supported by the grant 11-1b 189 of the Government of the Republic of Armenia. 



S. Manukian 
 

65 

[8] S. N. Manukian, “Classification of Many-dimensional Arithmetical Sets Represented in M. 
Presburger's System”,  Reports of the National Academy of Science of Armenia, vol. 111, №2, pp. 114-
120, 2011 (in Russian). 
[9] S. C. Kleene. Introduction to Metamathematics. D. Van Nostard Comp., Inc., New York-Toronto, 
1952.  
 
 
Մ. Պրեսբուրգերի համակարգում ներկայացվող երկչափ թվաբանական 

բազմությունների որոշ հանրահաշվական և տրամաբանական 
հատկություններ 

 
Ս. Ն. Մանուկյան 

 
Ամփոփում 

Դիտարկվում են ...)2()1()0(  HHH  դասերը, որոնց հաջորդականությունը 
ընդգրկում է Մ. Պրեսբուրգերի համակարգում ներկայացվող թվաբանական 
բազմությունների դասը ([1]-[4]) և ...)2()1()0(  HHH  դասերը, որոնց 
հաջորդականությունն ընդգրկում է նման տիպի երկչափ բազմությունների դասը: 
Ապացուցվում է, որ նշված դասակարգումները խիստ մոնոտոն են և լրիվ: 
Դիտարկվում են երկչափ թվաբանական բազմությունների վրա որոշված  ,  , ,  , 

1  գործողությունները ([5]-[7]) և այդ գործողությունների վրա հիմնված  0  և 1  
հանրահաշիվները ([5]-[7]): Հետազոտվում են այդ գործողությունների և 
հանրահաշիվների փոխհարաբերությունները նշված դասակարգումների հետ: 
 

 
О некоторых алгебраических и логических особенностях двумерных 

арифметических множеств, представимых в системе Пресбургера 
 

С. Н. Манукян 
 

Аннотация 
 
 
Рассматривается классификация ...)2()1()0(  HHH  арифметических множеств, 
представимых в системе Пресбургера ([1]-[4]), а также классификация 

...)2()1()0(  HHH  двумерных арифметических множеств аналогичного типа. 
Доказывается полнота и строгая монотонность этих классификаций. Рассматриваются 
операции  ,  ,  ,  , 1  на двумерных арифметических множествах ([5]-[7]), а также 
алгебры 0  и 1 ,  основанные на этих операциях ([5]-[7]). Исследуются 
взаимоотношения рассматриваемых операций и алгебр с вышеупомянутыми 
классификациями.