D:\sbornik\...\S_Arm1.DVI


Mathematical Problems of Computer Science 28, 2007, 141{145.

On P olynomially E quivalence of M inimal

Fr ege Systems

S e r g e y M. S a ya d ya n a n d A r m in e A . Ch u b a r ya n

Department of Informatics and Applied Mathematics,
Yerevan State University

e-mail: sayadyans@yahoo.com, chubarm@ysu.am

Abstract

In this paper is shown that any two minimal Frege systems polynomially simu-
late each other. This result is the extension of the similar result about polynomially
equivalence of intuitionistic Frege system. The latter is proved by G. Mints and A. Ko-
jevnikov [1].

Refer ences

[1 ] G. Min t s , A . K o je vn iko v, In t u it io n is t ic Fr e g e s ys t e m s a r e p o lin o m ia lly e qu iva le n t ,
Çàïèñêè íàó÷íûõ ñåìèíàðîâ ÏÎÌÈ, 3 1 6 ( 2 0 0 4 ) , 1 2 9 { 1 4 5 .

[2 ] S . B u s s , P . P u d la k, On t h e c o m p u t a t io n a l c o n t e n t o f in t u it io n is t ic p r o p o s it io n a l p r o o fs ,
Annals of P ure and Applied L ogic 109, N o s . 1 -2 ( 2 0 0 1 ) , 4 9 { 6 4 .

[3 ] S . A . Co o k, A . R . R e c kh o w, Th e r e la t ive e ± c ie n c y o f p r o p o s it io n a l p r o o f s ys t e m s , The
J ournal of Symbolic L ogic 4 4 , N o . 1 ( 1 9 7 9 ) , 3 6 { 5 0 .

[4 ] A . Go e r d t , Co m p le xit y o f t h e in t u it io n is t ic s e qu e n t c a lc u lu s , Theoretische Informatik,
TCK Ch e m n it z ( 2 0 0 5 ) , 3 { 1 3 .

[5 ] R . H a r r o p , Co n c e r n in g fo r m u la s o f t h e t yp e s A ! B _C, A ! ( Ex ) B ( x ) in in t u it io n is t ic
fo r m a l s ys t e m s , The J ournal of Symbolic L ogic 25, N o 1 ( 1 9 6 0 ) , 2 7 { 3 2 .

[6 ] H . Fr ie d m a n , On e H u n d r e d a n d Two P r o b le m s in Ma t h e m a t ic s L o g ic , The J ournal of
Symbolic L ogic 40, N o 2 ( 1 9 7 5 ) , 1 1 3 { 1 2 9 .

[7 ] R . Ie m h o ®, On t h e a d m is s ib le r u le s o f in t u it io n is t ic p r o p o s it io n a l lo g ic , The J ournal of
Symbolic L ogic 66, N o 1 ( 2 0 0 1 ) , 2 3 1 { 2 4 3 .

[8 ] S . C. K le e n e , In t r o d u c t io n t o m e t a m a t h e m a t ic s , D . Van Nostrand company, IN C, 1 9 5 2 .

[9 ] ê. ê³Û³¹Û³Ý, ÆÝïáõÇóÇáÝÇëï³Ï³Ý ³ëáõÛóÛÇÝ Ñ³ßíÇ áñáß Ñ³Ù³Ï³ñ·»ñÇ
ѳٻٳïáõÙ, ºäÐ ¶Çï³Ï³Ý ï»Õ»Ï³·Çñ, 2, 2005, 25-30.

1 4 1



1 4 2 On Polynomially Equivalence of Minimal Frege Systems

ØÇÝÇÙ³É ³ëáõóÛÇÝ Ñ³ßíáõÙ üñ»·»ÛÇ Ñ³Ù³Ï³ñ·»ñÇ
µ³½Ù³Ý¹³Ù³ÛÇÝ Ñ³Ù³ñÅ»ùáõÃÛ³Ý í»ñ³µ»ñÛ³É

ê. ê³Û³¹Û³Ý ¨ ². âáõµ³ñÛ³Ý

²Ù÷á÷áõÙ

êáõÛÝ Ñá¹í³ÍáõÙ ³å³óáõóíáõÙ ¿, áñ ÙÇÝÇÙ³É ³ëáõóÛÇÝ Ñ³ßíÇ Ï³Ù³Û³Ï³Ý
»ñÏáõ üñ»·»ÛÇ Ñ³Ù³Ï³ñ·»ñ µ³½Ù³Ý¹³Ùáñ»Ý ѳٳñÅ»ù »Ý: ²Ûë ³ñ¹ÛáõÝùÁ
ÇÝïáõÇóÇáÝÇëï³Ï³Ý ³ëáõóÛÇÝ Ñ³ßíÇ Ñ³Ù³ñ ØÇÝóÇ ¨ ÎáÅ»íÝÇÏáíÇ [1] ÏáÕÙÇó
ëï³óí³Í ÝٳݳïÇå ³ñ¹ÛáõÝùÇ ÁݹɳÛÝáõÙÝ ¿: