Алгебралық тұжырымдау туралы түсінік

 

Формулалардың Н={А₁,А₂,…,А_n} ақырлы жиынын қарастырамыз.

Н жиынынан шығарылатын формула анықтамасы.

1) A_iÎH формуласы Н-тан шығарылатын формула деп аталады.

2) Әрбір дәлелденетін формула Н-тан шығарылатын болады.

3) Егер С және С→В формулалар Н-тан шығарылатын болса, онда В формуласы да Н-тан шығарылатын болады.

Егер кейбір В формуласы формулалардың Н жиынынан шығарылатын болса, онда бұл былай жазылады: Н├В.

Н жиыны бос немесе тек дәлелденетін формулалардан тұратын жағдайда Н жиынынан шығарылатын формулалардың класы дәлелденетін формулалардың класымен сәйкес келеді.

Егер де Н жиынында кем дегенде бір дәлелденбейтін формула болса, онда Н-тан шығарылатын формулардың класы дәлелденетін формулалар класынан кең болады.

Мысал.

Формулалардың Н={А, В} жиынынан формуласы шығатынын дәлелдеу керек.

AÎH және BÎH болғандықтан, дәлелденетін формуланың анықтамасы бойынша

 Н├А,                                   (1) 

 Н├В.               (2)

және аксиомаларды алып, және алмастыруларды орындаймыз.

Нәтижесінде Н-тан шығарылатын дәлелденетін формулаларды аламыз, яғни

Н├(А→А)→((А→В)→(А )),                   (3)

Н├В→(А→В),             (4)

А→А формуласы дәлелденетін, онда Н├А→А.                (5)

(5) және (3) формулалардан қорытындылау ережесі бойынша                                                          Н├(А→В)→(А ))            (6)

алынады.

(2) және (4) формулалардан қорытындылау ережесі бойынша: 

           Н├А→В .              (7)

(7) және (6) формулалардан қорытындылау ережесі бойынша:               Н├А .                               (8)

Соңында (1) және (8) формулалардан

                 Н├             (9)

алынады.

Формуланың шығарылатынын  дәлелдеуде тек қана қорытындылау ережесін емес, күрделі қорытындылау ережесін пайдалануға мүмкін екендігі түсінікті. Онда бұл ережені пайдаланып, (9) тұжырымды (5), (7), (1) және (3) тұжырымдардан алуға болады.

Анықтама. Формулалардың Н ақырлы жиынынан шығаруы деп әрбір мүшесі келесі шарттарды қанағаттандыратын формулалардың В₁,В₂,…,В_к тізбегін айтамыз:

1) ол Н жиынының бір формуласы болады,

2) ол дәлелденетін формула болады,

3) ол В₁,В₂,…,В_к тізбегінің алдынғы кез келген екі мүшесінен қорытындылау ережесі бойынша шығады.

Алдынғы мысалда көрсеткеніміздей, формулалардың Н={А,В} жиынынан шығаруы формулалардың келесі ақырлы тізбегі болады:

А, В, (А→А)→((А→В)→(А )), (А→В), А→А, (А→В)→(А )), А→В, А , . (1,2,3,7,5,6,8 формулалар).

Егер күрделі қорытындылау ережесін пайдалансақ, онда шығаруды былай жазуға болады:

 А, В, (А→А)→((А→В)→(А )), В→(А→В), А→А, А→В, . (5, 7, 1, 3 формулалар).

Шығарылатын формула  анықтамасынан және формулалар жиынынан шығару анықтамасынан шығарудың келесі қасиеттері келіп шығады:

1) Н жиынынан шығарудың әрбір бастапқы кесіндісі – Н-тан шығару болады.

2) Егер Н тан шығарудың екі көршілес мүшелерінің арасында (басында немесе соңында) кейбір Н тан шығаруді қойсақ, онда формулалардың алынған жаңа тізбегі Н тан шығару болады.

3) Н жиынынан шығарудың әрбір мүшесі Н тан шығарылатын формула болады. Н тан кез келген шығару оның соңғы формуласының шығаруы болады.

4) Егер болса, онда Н тан кез келген шығару W дан шығару болады.

5) В формуласы Н жиынынан шығарылатын болуы үшін бұл формуланың Н тан шығаруы бар болуы қажетті және жеткілікті.

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. Жалпыланған дедукция теоремасы:            {C₁, C₁, …, C_k}├ A 

                                                                           ├C₁→(C₂→(C₃→…(C_k→A)…))

  

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

                                                                 H├

 

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

                                                                                  H, ├C

 

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

 

Тұжырымдар есептелімінің  формулаларын тұжырымдар алгебрасының формулалары ретінде қарастыруға болады. Ол үшін тұжырымдар есептелімінің айнымалыларын тұжырымдар алгебрасының айнымалысындай, яғни екі ақиқат және жалған мән қабылдайтын, қарастырамыз.

 операцияларын тұжырымдар алгебрасында сияқты анықтаймыз. Тұжырымдар есептелімінің формулалары тұжырымдар алгебрасының ережелері бойынша есептелетін 1 немесе 0 мәндерінің біреуін ғана қабылдайды.

Тұжырымдар есептелімі формуласының мәні түсінігін енгіземіз. А – тұжырымдар есептелімінің формуласы, х₁,х₂,…,х_n – өзара әртүрлі А формуласына енетін айнымалылар болсын. а₁, а₂,…,а_n арқылы бұл айнымалыларының мәндер тобын белгілейміз. (а₁, а₂,…,а_n) векторы 2ⁿ мән қабылдайтыны айқын.

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

Теорема 1. Әрбір тұжырымдар есептелімінде дәлелденетін формула тұжырымдар алгебрасында тепе-тең ақиқат болады.

Теорема 2. (шығарылу туралы). А – тұжырымдар есептелімінің қандай да бір формуласы болсын; х₁,х₂,…,х_n  – А формулаға енетін айнымалылардың тобы; а₁, а₂, …, а_n – бұл айнымалылар мәндерінің кез келген бекітілген тобы. Н арқылы формулалардың ақырлы жиынынын белгілейміз:

, где 

Онда:

1. Егер R_a1,a2,..,an(A)=1 болса, онда H├A .
2. Егер R_a1,a2,..,an(A)=0 болса, онда H├ , мұнда R_a1,a2,..,an(A) – А формуланың а₁, а₂,…,а_n топтағы мәні.

 

Теорема 3. Тұжырымдар алгебрасының әрбір тепе-тең ақиқат формуласы тұжырымдар есептелімінде дәлелденетін формула болады.

 

Тақырып бойынша тесттер

 

1. формуланың рангін табыңыз

7

6

5

4

 

2. формуланың рангін табыңыз

 8

6

7

5

 

_{3. Дұрыс құрылған формуланы көрсетіңіз:}

 

 

 

4. Келтірілген өрнектердің қайсысы формула болады?

Барлық жауаптар дұрыс

 

5. формула үшін алмастыру нәтижесін жазыңыз

 

6. формула үшін алмастыру нәтижесін жазыңыз

 

Глава 3. предикаттар логикасы

3.1 Предикат ұғымы

 

Анықтама 1. x₁, x₂, …, x_n – пәндік айнымалылардың символдары болсын. Пәндік айнымалылардың (x₁, x₂, …, x_n) топтары пәндік аймақ деп аталатын W жиыныны тиісті болсын. W пәндік аймағында анықталған n-орынды предикат деп,  W-ның тұжырымдар жиынына бейнелеуін айтады.

Мысалдарды қарастырар алдын n-орынды предикаттарға квазианықтама  берейік:

Анықтама. «n  айнымалыға тәуелді және келесі қасиетке ие болған баяндамалы байланысты сөйлемі: айнымалылардың орнына анық мәндер қойылғанда ақиқат немесе жалған болсын».

Мысал 1. D(x₁, x₂) = «x₁ натурал саны x₂ натурал санына бөлінеді (қалдықсыз)» - N N жиынында анықталған екі орынды предикат. Түсінікті, D(4, 2)=1, D(3, 5)=0.

Мысал 2. Q(x) = «х₂<-1, x R» - R нақты сандар жиынында анықталған бір орынды предикат. Q(-1)=0, Q( )=0. Q(x) – тепе-тең жалған екендігі түсінікті, яғни Q(x) 0.

Мысал 3. R(x, y, z)= «x²+ y² z; x, y, z R» - R³ жиынында анықталған үш орынды предикат. R(1, 1, -2)=0, R(1, 1, 2)=1.

Мысал 4. S(x, y) = «sin2ху>-3; x, y R» - екі орынды тепе-тең ақиқат предикат.

Р(x₁, x₂, …, x_n) - W аймағында анықталған n-орынды предикат болсын_{. Онымен келесі түрде анықталған екі жиынды байланыстырамыз:}

_IP={( x₁, x₂, …, x_n )Î W _{| Р(}x₁, x₂, …, x_{n)=1} – Р предикаттың ақиқаттық жиыны,}

_LP={( x₁, x₂, …, x_n)Î W _{| Р(}x₁, x₂, …, x_{n)=0} – Р предикаттың жалғандық жиыны.}

_{Анықтама  2. Р –} W-да анықталған предикат болсын. Егер _IP=W _{(LP=Æ) болса, онда Р тепе-тең ақиқат, егер LP=}W _{(IP=Æ) болса, онда Р тепе-тең жалған предикат деп аталады.}

_{Егер  IP ¹} W _{және LP ¹ Æ болса, онда Р орындалатын предикат деп айтамыз.}

R³ кеңістікте 3 мысалдағы      R(x, y, z) предикаттың  _{IP  және LP жиындарын көрсетейік (1 сурет)}.                                                         

                                                                 z                        I_P

 

 

 

1 сурет

                             

                                                                                        у

                                             х                                                                   

3.2 Предикаттарға логикалық амалдарды қолдану

 

Анықтама 3. _{Р –} W-да анықталған предикат болсын. Р предикаттың терістеуі дегеніміз _{белгіленетін және} W-да _{келесі түрде анықталған предикат:}

P және Q – W-да анықталған предикаттар болсын_.

P және Q _{предикаттардың дизъюнкциясы (конъюнкциясы, импликациясы, эквиваленциясы) дегеніміз былай белгіленетін , ( ( , , PQ), , ) және -да келесі түрде анықталатын предикат:}

( )

( )

( )

 

Анықтама 4. Егер _{аймағына тиісті кез келген (} x₁, x₂, …, x_n ) пәндік айнымалылардың топтары үшін _Р( x₁, x₂, …, x_n ) _Q( x₁, x₂, …, x_n ) болса, онда P және Q предикаттар _{аймағында анықталған пара-пар предикаттар деп аталады (P Q).}

 

Теорема 1. _{аймағында анықталған} n – орынды предикаттардың жиыны предикаттардың бульдік алгебрасық құрайды, яғни олар үшін бульдік алгебраның келесі 19 негізгі тепе-теңдіктер орынды_:

 

0. 1. 2. 3. 4. 5. 6. 7. 8. 9.

10. 11. 12. 13. 14. 15. 16. 17. 18.

_{Мұнда 1 – -дағы тепе-тең ақиқат предикаттың, ал 0 – тепе-тең жалған предикаттың белгілері.}

Бұл теореманың дұрыстығы айқын. Өйткені предикаттарға қолданылатын амалдар тұжырымдарға қолданылатын амалдар көмегімен енгізілген, ал тұжырымдар бульдік алгебраны құрайды.

3.3 Кванторлық амалдар