Ալեքսանյան, Սոնա Ռաֆիկի

Математика

Աշխատությունը նվիրված է ֆորմալ համակարգերում արտածումների բարդության ուսումնասիրությանը՝ նպատակ ունենալով բացահայտել այն պայմանները, որոնց դեպքում տրամաբանական արտածումների կառուցումը, ստուգումը կամ օպտիմալացումը պահանջում է զգալի հաշվարկային և կառուցվածքային ռեսուրսներ։ Ֆորմալ համակարգը բաղկացած է հստակ սահմանված սիմվոլներից, արտահայտությունների կառուցման կանոններից, աքսիոմներից և արտածման կանոններից, որոնց միջոցով հնարավոր է որոշակի սկզբնական դրույթներից ստանալ նոր դատողություններ։ Նման համակարգերի ուսումնասիրությունը կարևոր նշանակություն ունի մաթեմատիկական տրամաբանության և տեսական համակարգչային գիտության համար, քանի որ հնարավորություն է տալիս հասկանալու, թե որքան արդյունավետ կարող են մեքենայացվել տրամաբանական ապացույցների կառուցման և ստուգման գործընթացները։ Հետազոտության հիմնական խնդիրը արտածման բարդության տարբեր ձևերի բացահայտումն ու դասակարգումն է։ Միևնույն տրամաբանական հետևությունը տարբեր ֆորմալ համակարգերում կարող է ստացվել էապես տարբեր երկարության կամ բարդության ապացույցով։ Այդ պատճառով ուսումնասիրության ժամանակ կարևոր է ոչ միայն որոշել՝ արդյոք տվյալ բանաձևը արտածելի է, այլև գնահատել դրա ապացույցի չափը, քայլերի քանակը, օգտագործվող միջանկյալ բանաձևերի թիվը և ապացույցի կառուցման համար անհրաժեշտ հաշվարկային ռեսուրսները։ Աշխատության մեջ կարող է ուսումնասիրվել արտածման երկարության հասկացությունը։ Որոշ ֆորմալ համակարգերում գոյություն ունեն դատողություններ, որոնց ապացույցները կարող են լինել շատ երկար, նույնիսկ այն դեպքում, երբ համապատասխան մաթեմատիկական կամ տրամաբանական պնդումը ինքնին համեմատաբար պարզ է։ Այս երևույթը կարևոր է ապացույցների տեսության համար, քանի որ ցույց է տալիս ֆորմալ համակարգի արտահայտչական հնարավորությունների և ապացույցների արդյունավետության միջև եղած տարբերությունը։ Հետազոտության կարևոր ուղղություն է տարբեր ֆորմալ համակարգերի համեմատությունը։ Կարող են ուսումնասիրվել դասական և ոչ դասական տրամաբանական համակարգեր, աքսիոմատիկ տեսություններ, բնական արտածման համակարգեր, սեկվենտային հաշվարկներ և այլ ձևական ապացուցման համակարգեր։ Համեմատության նպատակն է պարզել, թե ինչպես է արտածման կանոնների ընտրությունը ազդում ապացույցների երկարության, կառուցման բարդության և ստուգման արդյունավետության վրա։ Այս համատեքստում կարևոր է նաև համակարգերի միջև սիմուլյացիաների ուսումնասիրությունը, երբ մի համակարգի ապացույցները փոխակերպվում են մեկ այլ համակարգում գործող ապացույցների։ Արտածումների բարդությունը սերտորեն կապված է հաշվարկային բարդության հետ։ Տրամաբանական խնդիրների մի մասը կարող է ունենալ որոշման արդյունավետ ալգորիթմներ, մինչդեռ մյուսների համար անհրաժեշտ հաշվարկային ռեսուրսները կարող են արագ աճել խնդրի չափի մեծացմանը զուգընթաց։ Այդ պատճառով հետազոտության շրջանակում կարող են դիտարկվել բարդության դասեր, ալգորիթմական սահմանափակումներ և արտածման խնդիրների լուծման ժամանակային ու տարածական բարդությունը։ Առանձնահատուկ նշանակություն ունի արտածման կառուցման և արտածման ստուգման տարբերակումը։ Որոշ դեպքերում արդեն գոյություն ունեցող ապացույցի ճիշտությունը կարելի է ստուգել համեմատաբար արագ, մինչդեռ այդ ապացույցի ինքնուրույն կառուցումը կարող է պահանջել շատ ավելի մեծ հաշվարկային ռեսուրսներ։ Այս տարբերությունը կարևոր է ավտոմատացված ապացուցման համակարգերի նախագծման և արդյունավետության գնահատման տեսանկյունից։ Աշխատության մեջ կարող է ուսումնասիրվել նաև ապացույցների նորմալացումը և ապացույցների կառուցվածքի պարզեցումը։ Որոշ ֆորմալ համակարգերում հնարավոր է բարդ արտածումները վերափոխել ավելի կանոնավոր ձևի՝ պահպանելով դրանց տրամաբանական վավերականությունը։ Նորմալ ձևերի ուսումնասիրությունը հնարավորություն է տալիս ավելի լավ հասկանալ ապացույցների ներքին կառուցվածքը, հեռացնել ավելորդ քայլերը և որոշ դեպքերում բարելավել ապացույցների ավտոմատ կառուցման գործընթացը։ Կարևոր ուղղություն է նաև արտածումների ավտոմատացումը։ Համակարգչային ծրագրերը կարող են որոնել տրամաբանական հետևությունների ապացույցներ՝ օգտագործելով նախապես սահմանված կանոններ և ռազմավարություններ։ Սակայն հնարավոր արտածումների տարածքի արագ աճը հաճախ առաջացնում է որոնման բարդության խնդիր։ Այդ պատճառով անհրաժեշտ է մշակել արդյունավետ որոնման ռազմավարություններ, էվրիստիկ մեթոդներ և ապացույցների տարածքի սահմանափակման եղանակներ։ Աշխատության մեջ կարող են քննարկվել նաև ավտոմատ թեորեմների ապացուցման համակարգերի, տրամաբանական ծրագրավորման և ֆորմալ վերիֆիկացիայի հետ կապված խնդիրները։ Ֆորմալ վերիֆիկացիայի դեպքում կարևոր է ստուգել ծրագրերի, ալգորիթմների կամ համակարգերի համապատասխանությունը նախապես սահմանված հատկություններին։ Այստեղ տրամաբանական արտածումները դառնում են համակարգի ճիշտության հիմնավորման միջոց, իսկ դրանց բարդությունը կարող է ուղղակիորեն ազդել վերիֆիկացիայի գործընթացի արդյունավետության վրա։ Հետազոտության տեսական նշանակությունը կայանում է նրանում, որ արտածումների բարդության ուսումնասիրությունը հնարավորություն է տալիս սահմանել ֆորմալ համակարգերի հնարավորությունների և սահմանափակումների ավելի հստակ պատկեր։ Այն կարող է բացահայտել այնպիսի դեպքեր, երբ որոշ համակարգերում պնդումների ապացույցները չափազանց երկար են, մինչդեռ ավելի հզոր կամ այլ կերպ կառուցված համակարգում նույն պնդումները հնարավոր է ապացուցել զգալիորեն կարճ եղանակով։ Այսպիսի համեմատությունները կարևոր են ապացույցների համակարգերի արդյունավետության գնահատման և նոր ֆորմալ մեխանիզմների մշակման համար։ Գործնական տեսանկյունից ստացված արդյունքները կարող են օգտակար լինել ավտոմատացված ապացուցման, ծրագրային ապահովման ֆորմալ ստուգման, տրամաբանական վերլուծության, արհեստական բանականության որոշ ուղղությունների և վստահելի ծրագրային համակարգերի մշակման համար։ Արտածումների բարդության նվազեցումը կարող է նպաստել ավելի արագ և արդյունավետ ապացույցների որոնմանն ու ստուգմանը, ինչպես նաև մեծացնել ֆորմալ մեթոդների կիրառելիությունը բարդ համակարգերում։ Ընդհանուր առմամբ, աշխատանքը ուսումնասիրում է ֆորմալ համակարգերում արտածումների կառուցման, չափման, ստուգման և օպտիմալացման հետ կապված բարդությունները։ Տարբեր տրամաբանական համակարգերի, ապացույցների կառուցվածքների և հաշվարկային մեթոդների համադրական ուսումնասիրությունը հնարավորություն է տալիս բացահայտել արտածումների բարդության հիմնական օրինաչափությունները և սահմանափակումները՝ միաժամանակ ձևավորելով տեսական հիմք ավելի արդյունավետ ապացուցման և ֆորմալ վերիֆիկացիայի մեթոդների մշակման համար։