8 – лекция

2.8  Шыєарылу ережелері

 

Бўл ережелер шыєарудыѕ ќасиеттерінен алмастыру жјне ќорытындылау ережелерін ќолдану арќылы тікелей келіп шыєады.

Н жјне W – тўжырымдар есептелімі формулаларыныѕ екі тобы болсын.

Н, W  арќылы олардыѕ бірігуін белгілейміз, яєни Н,W=.

Мысалы, W  жиыны тек бір С формуласынан тўратын жаєдайда   біріктіруді Н, С тїрінде жазамыз.

Негізгі шыєарылу ережелерін кґрсетейік.

 

1.  H ├ A              Бўл ереже формулалар жиынынан шыєарудыѕ аныќтамасынан                                                   H,W├A           келіп шыєады: “Егер А формуласы Н-тан шыєарылатын болса,  онда ол  тан да шыєарылады. ”.

 

    2. H,C ├ A,H├C 

                H├A          .

 

    3.  H,C ├ A, W├C 

               H,W├A       .

 

    4. H ├ C→A 

              H,C├A    .

 

    5. Дедукция теоремасы:                  H, C├ A  .

                                                               H├C→A

  5A. Жалпыланєан дедукция теоремасы:            {C1, C1, …, Ck}├ A 

                                                                           ├C1→(C2→(C3→…(Ck→A)…))

  

  6. Конъюнкцияны енгізу ережесі:   H├A,H├B   .

                                                                 H├

 

  7. Дизъюнкцияны енгізу ережесі:                  H,A├C;Н,B├C   .

                                                                                  H,├C

 

 

2.9 Тўжырымдар алгебрасы мен тўжырымдар есептелімі
арасындаєы байланыс

 

Тўжырымдар есептелімініѕ формулаларын тўжырымдар алгебрасыныѕ формулалары ретінде ќарастыруєа болады. Ол їшін тўжырымдар есептелімініѕ айнымалыларын тўжырымдар алгебрасыныѕ айнымалысындай, яєни екі аќиќат жјне жалєан мјн ќабылдайтын, ќарастырамыз.

 операцияларын  тўжырымдар алгебрасында сияќты аныќтаймыз. Тўжырымдар есептелімініѕ формулалары тўжырымдар алгебрасыныѕ ережелері бойынша есептелетін 1 немесе 0 мјндерініѕ біреуін єана ќабылдайды.

Тўжырымдар есептелімі формуласыныѕ мјні тїсінігін енгіземіз. А – тўжырымдар есептелімініѕ формуласы, х1,х2,…,хn – ґзара јртїрлі А формуласына енетін айнымалылар болсын. а1, а2,…,аn арќылы бўл айнымалыларыныѕ мјндер тобын белгілейміз. (а1, а2,…,аn) векторы 2n мјн ќабылдайтыны айќын.

Келесі їш теорема орынды.

Теорема 1. Јрбір тўжырымдар есептелімінде дјлелденетін формула тўжырымдар алгебрасында тепе-теѕ аќиќат болады.

Теорема 2. (шыєарылу туралы). А – тўжырымдар есептелімініѕ ќандай да бір формуласы болсын; х1,х2,…,хn  – А формулаєа енетін айнымалылардыѕ тобы; а1, а2, …, аn – бўл айнымалылар мјндерініѕ кез келген бекітілген тобы. Н арќылы формулалардыѕ аќырлы жиынынын белгілейміз:

, где

Онда:

1)     Егер Ra1,a2,..,an(A)=1 болса, онда H├A .

2)     Егер Ra1,a2,..,an(A)=0 болса, онда H├, мўнда Ra1,a2,..,an(A) – А формуланыѕ а1, а2,…,аn  топтаєы мјні.

 

Теорема 3.  Тўжырымдар алгебрасыныѕ јрбір тепе-теѕ аќиќат формуласы тўжырымдар есептелімінде дјлелденетін формула болады.

 

2.10. Тўжырымдардыѕ аксиоматикалыќ есептелімініѕ проблемалары

 

Кез-келген аксиоматикалыќ теория ґэін-ґзі дјйектеу їшін келесі тґрт проблемалардыѕ ќарастырылуын талап етеді:

1)     шешімділік проблемасы,

2)     ќайшылыќсыздыќ проблемасы,

3)     толыќтылыќ проблемасы,

4)     тјуелсіздік проблемасы.

 

2.10.1. Тўжырымдар есептелімініѕ шешімділік проблемасы

 

Тўжырымдар есептелімініѕ шешімділік проблемасы кез-келген берілген тўжырымдар есептелімініѕ формуласы їшін оныѕ дјлелденетінін немесе дјлелденбейтінін аныќтайтын алгоритмніѕ бар болуыныѕ дјлеледеуінен тўрады.Келесі теорема орынды: тўжырымдар есептелімініѕ шешімділік проблемасы шешімді.

Шынында, тўжырымдар есептелімініѕ кез-келген формуласын тўжырымдар алгебрасыныѕ формуласы ретінде ќарастыруєа болады.Демек оєан кіретін айнымалылардыѕ јртїрлі мјндерініѕ жиынтыєында формуланыѕ логикалыќ мјндерін ќарастыруєа болады.

А – тўжырымдар есептелімініѕ ќандай да бір формуласы ,ал  х1,х2,…,хn – оєан кіретін айнымалылардыѕ тізімі болсын. Оєан кіретін а1, а2,…,аn айнымалылар мјндерініѕ барлыќ жиынтыќтарында Ra1,a2,..,an(A)  есептейміз. Егер барлыќ

а1, а2,…,аn  жиынтыќтар їшін Ra1,a2,..,an(A)=1 болса,онда  А формуласы– тепе-теѕ аќиќат,демек тепе-теѕ аќиќат формуланыѕ дјлелденетіні жайлы теоремасы бойынша ол дјлелденетін формула болады.Ал егер болатын  айнымалылар мјндерініѕ жиынтыєы табылса,онда А – формуласы тепе-теѕ аќиќат емес,демек ол дјлелденбейді.

 

2.10.2. Тўжырымдар есептелімініѕ ќайшылыќсыздыќ проблемасы

Логикалыќ есептелім ќайшылыќсыздыќ деп аталады,егер онда біреуі екіншісініѕ терістеуі болып табылатын ешќандай екі формула дјлелденбейтін болса.Басќаша айтќанда,аксиоматикалыќ есептелім ќайшылыќсыздыќ деп аталады,егер онда А мен  формулаларын біруаќытта шыєаруєа мїмкіндік болмаса.

Ќайшылыќсыздыќ проблемасы келесі сўраќќа жауап беруден тўрады: берілген есептелім ќайшылыќсыз бола ма жоќ па?

Егер есептелімде А мен  тїріндегі дјлелденетін формулалар бар болса,онда есептелім ќайшылыќты деп аталады.Ќарастырылєан тўжырымдар есептелімінде А мен   формулаларын біруаќытта шыєару мїмкін емес,яєни бўл тўжырымдар есептелімі ќайшылыќсыз.

 

2.10.3.  Тўжырымдар есептелімініѕ толыќтылыќ проблемасы

Аныќтама 1. Тўжырымдардыѕ аксиоматикалыќ есептелімі тар маєынада толыќ деп аталады,егер оныѕ аксиомаларыныѕ тізіміне жаѕа аксиома ретінде бўл есептелімде кез-келген дјлелденбейтін формуланы ќосуы ќайшылыќты есептелімге келтірсе.

Аныќтама 2. Тўжырымдар есептелімі кеѕ маєынада толыќ деп аталады,егер онда кез-келген тепе-теѕ аќиќат формула дјлелденетін болса.

Бўл аныќтамалардан тўжырымдар есептелімініѕ толыќтылыќ проблемасы екі сўраќты ќамтитындыєы шыєады:

1)    Аксиоматикалыќ есептелімніѕ аксиомаларыныѕ жїйесін оєан жаѕа аксиома ретінде бўл есептелімде дјлелденбейтін формуланы ќосып кеѕейтуге бола ма?

2)    Тўжырымдар алгебрасыныѕ кез-келген тепе-теѕ аќиќат формуласы тўжырымдар есептелімінде дјлелденетін бола ма?

Ќарастырылєан тўжырымдар есептелімі тар маєынада да,кеѕ маєынада да толыќ болады.

2.10.4. Тўжырымдар есептелімі аксиомаларыныѕ тјуелсіздік проблемасы

 

Кез-келген аксиоматикалыќ есептелімі їшін оныѕ аксиомаларыныѕ тјуелсіздігі туралы сўраќ пайда болады.Сўраќ былай ќойылады: берілген жїйеніѕ шыєару ережелерін ќолданып ќандай да бір аксиоманы ќалєан аксиомалардан шыєаруєа бола ма?

Егер жїйеніѕ кейбір аксиомасы їшін бўл мїмкін болса,онда бўл аксиоманы жїйеніѕ аксиомалары тізімінен алып тастауєа болады жјне мўнымен логикалыќ есептелім ґзгермейді,яєни дјлелденетін формулалар класы ґзгеріссіз ќалады.

 Аныќтама 3.  А аксиомасы есептелімніѕ ќалєан барлыќ аксиомаларынан тјуелсіз деп аталады,егер ол ќалєан аксиомалардан шыєарылмайтын болса. Егер жїйеніѕ јрбір аксиомасы тјуелсіз болса,онда есептелімніѕ аксиомалар жїйесі тјуелсіз деп аталады.

Тўжырымдар есептелімініѕ ќарастырылєан аксиомалар жїйесі тјуелсіз.