D:\sbornik\...\Alex_Chub1.DVI Mathematical Problems of Computer Science 26, 2006, 117{122. On Some P r opor ties of Fr ege P r oofs S o n a R . A le ks a n ya n a n d A n a h it A . Ch u b a r ya n Department of Applied Mathematics, State Engineering University of Armenia, Department of Informations and Applied Mathematics, Yerevan State University, e-mail: sonush@rambler.ru, achubaryan@ysu.am Abstract In [4] a measure s on propositional formula was de¯ned such that for every tautology ' "high" value of s(') requires the large size of proof in the "weak" propositional systems. In this paper it is shown, that there is a tautology ', the measure s(') of which has exponential dependence on the size of ', but its proof complexity in Frege systems is polynomially bounded. Refer ences [1 ] S . R . B u s s , P o lyn o m ia l s iz e p r o o fs o f t h e p r o p o s it io n a l p ig e o n h o le p r in c ip le , J ournal of Symbolic L ogic, 5 2 , 1 9 8 7 , 9 1 6 { 9 2 7 . [2 ] A . A . Ch u b a r ya n , On t h e p r o o f c o m p le xit y in s o m e s ys t e m o f c la s s ic a l p r o p o s it io n a l lo g ic , Izvestija NAN Armenii, M athematika, V o l. 3 7 , N 5 , 1 9 9 9 , 1 6 { 2 6 . [3 ] A . A . Ch u b a r ya n , On t h e c o m p le xit y o f p r o o fs in Fr e g e s ys t e m s , CSIT Conference, Yerevan, 2 0 0 1 , 1 2 9 { 1 3 2 . [4 ] A . A . Ch u b a r ya n , R e la t ive e ± c ie n c y o f a p r o o f s ys t e m in c la s s ic a l p r o p o s it io n a l lo g ic , Izvestija NAN Armenii, M athematika, V o l. 3 7 , N 5 , 2 0 0 2 , 7 1 { 8 4 . [5 ] 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 , J ournal of Symbolic L ogic, 1 9 7 9 , 4 4 , 3 6 { 5 0 . [6 ] E . Me n d e ls o n , In t r o d u c t io n t o Ma t h e m a t ic a l L o g ic , D . Van Nostrand company, INC. üñ»·»ÛÇ ³ñï³ÍáõÙÝ»ñÇ ÙÇ Ñ³ïÏáõÃÛ³Ý Ù³ëÇÝ ê. è. ²É»ùë³ÝÛ³Ý ¨ ²Ý³ÑÇï ². âáõµ³ñÛ³Ý ²Ù÷á÷áõÙ Úáõñ³ù³ÝãÛáõñ ' ÝáõÛݳµ³ÝáõÃÛ³Ý Ñ³Ù³ñ [4]-áõÙ Ý»ñÙáõÍí»É ¿ ³ÛÝåÇëÇ s( ') Ù»ÍáõÃÛáõÝ, áñ s( ') -Ç ”µ³ñÓñ” ³ñÅ»ùÇ ¹»åùáõÙ '-Ç ³ñï³ÍÙ³Ý »ñϳñáõÃÛáõÝÁ »ÃáõÛÉ» ѳٳϳñ·»ñáõÙ ÝáõÛÝå»ë Ù»Í ¿: êáõÛÝ Ñá¹í³ÍáõÙ óáõÛó ¿ ïñíáõÙ, áñ ·áÛáõÃÛáõÝ áõÝÇ ³ÛÝåÇëÇ ' ÝáõÛݳµ³ÝáõÃÛáõÝ, áñÇ Ñ³Ù³ñ s( ') -Ý áõÝÇ óáõóã³ÛÇÝ Ï³Ëí³ÍáõÃÛáõÝ '-Ç »ñϳñáõÃÛáõÝÇó, ë³Ï³ÛÝ Ýñ³ ³ñï³ÍáõÙÁ üñ»·»ÛÇ Ñ³Ù³Ï³ñ·»ñáõÙ áõÝÇ µ³½Ù³Ý¹³Ù³ÛÇÝ µ³ñ¹áõÃÛáõÝ: 1 1 7