Ամսագրի կամ հրապարակման վերնագիր:
Հրապարակման ամսաթիվ:
Հատոր:
ISSN:
Լրացուցիչ տեղեկություն:
սեղմիր այստեղ կապին հետևելու համար
Վերնագիր:
On some proporties of Frege proofs
Այլ վերնագիր:
Ֆրեգեյի արտածումների մի հատկության մասին
Ստեղծողը:
Sona R. Aleksanyan ; Anahit A. Chubaryan
Խորագիր:
Չվերահսկվող բանալի բառեր:
Ալեքսանյան Ս. Ռ. ; Չուբարյան Անահիտ Ա.
Ծածկույթ:
Ամփոփում:
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.