А(x,y,z)= (ØхÚØyÚz) (ØxÚyÚØz)(xÚØyÚz) (xÚyÚØz) (xÚyÚz).

_{1.14 Логикалық байланыстардың толық жүйелері}

 

  D₁, D₂, …, D_n логикалық амалдардың символдары болсын. Егер тұжырымдар алгебрасының кез келген формуласы үшін оған пара-пар D₁, D₂, …, D_n  амалдарының көмегімен құрылған формула бар болса, онда <D₁, D₂, …, D_n> жүйе толық деп аталады.

   Тұжырымдар  алгебрасының кез келген формуласы үшін оған пара-пар ДНФ және КНФ болғандықтан, <Ø, Ù, Ú > – толық жүйе екендігі түсінікті.

   Лемма 9.1 Логикалық байланыстардың келесі жиындары:

    <Ø, Ù, Ú, ® >, <Ø, Ù >, <Ø, Ú >, <Ø, ®>

толық жүйе құрайды.

   Лемма 9.2 <Ù, Ú, ® >, <Ø > жиындары логикалық амалдардың толық жүйесін құрмайды.

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

 

1. Келесі импликациялардың  қайсысы жалған?

1) егер 2*2=4, онда 2>3;

2) егер 2*2=4, онда 2<3;

3) егер 2*2=5, онда 2<3;

4) егер 2*2=5, онда 2>3; 

2. Келесі сөйлемдердің қайсысы тұжырым болмайды?

1) «Информатика» кафедрасының студенті.

2) Париж –  Испания астанасы.

3) 3 саны А жиынына тиісті. 

3. Айнымалылардың қайсылары бір бірінің терістеулері болады:

1) 2>3, 2£3;

2) 6<9, 6>9;

3) f функциясы жұп, f функциясы тақ;

4) ABC үшбұрышы тікбұрышты, ABC үшбұрышы – тең бүйірлі. 

4. A®B тұжырымы ақиқат болсын. (ØAÙB ) ® ( ØAÚB ) тұжырымы қандай логикалық мәнге ие болады?

1) ақиқат

2) жалған 

5. Ø (ØPÚQ ) ® ((PÚQ ) ®P) формуланы ықшамдаңыз:

 1) 1

 2) 0

 3) Р

 4) Q 

_{6. Келесі өрнектердің қайсысы формула болады?:}

 _{1) ((PÙ( ØQ®R )) Ú ((ØP~ R ) ØQ ))}

 _{2) ((PÚQ) R) ®ØS} 

 _{7. КНФ-ті табыңыз: Ø(xÚz )Ù(x®y)}

 _{1) Øx(yÚØz)}

 _{2) (xÚy)(yÚz)}

 _{3) yÚz} 

_{8. 0 мәнді айнымалылардың тек (0,0) мәндер тобында қабылдайтын дизъюнктивті бірмүшені құрыңыз}:

1) xÚy

2) ØxÚy

3) xÚØy

4) Øx ÚØy 

_{9. формулаға пара-пар тек және амалдары көмегімен құрылған формуланы табыңыз:}

1)   Ø(ØxÙyÙØz )

2)  xÙy 

10. ДНФті табыңыз: (x~y) ÙØ ( z®T )

1) (xÙyÙzÙØT) Ú (ØxÙØyÙzÙØT);

2) x ÙyÚz

 

   2 тарау. тұжырымдар есептелімі

      2.1  Тұжырымдар есептелімі формуласының ұғымы

 

   Тұжырымдар  есептелімі бұл интерпретациясы  тұжырымдар алгебрасы болатын аксиоматикалық логикалық жүйе.

   Әрбір есептелімнің сипаттамасына бұл есептелімі символдарының, формулаларының сипаттамасы, дәлелденетін формулалардың анықтамасы енеді.

   Тұжырымдар  есептелімінің алфавиті үш түрлі символдардан тұрады:

   1. Бұл символдарды айнымалы тұжырымдар деп атаймыз.

   2. Бұл символдар логикалық байланыс деген жалпы атауға ие. Келтірілген символдардың біріншісі дизъюнкция (немесе логикалық қосу) белгісі, екіншісі – конъюнкция (немесе логикалық көбейту) белгісі, үшіншісі – импликация және төртіншісі – терістеу белгісі.

   3. Жақшалар деп аталатын символдар: (,   ).

   Тұжырымдар  есептелімінде басқа символдар  болмайды.

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

Тұжырымдар  есептелімі формуласының анықтамасы

1. Кез келген айнымалы формула б олады.

2. Егер А және В – формулалар болса, онда сөздер де формулалар.

3. Ешқандай басқа символдардың қатары формула болмайды.

   Айнымалы  тұжырымдарды қарапайым формулалар деп атаймыз.

Тұжырымдар есептелімі формуласына мысал келтірейік.

       айнымалы тұжырымдар анықтаманың 1-ші бөлімі бойынша формулалар болады. Бірақ, онда сөздер де анықтаманың 2-ші бөлімі бойынша формулалар бола алады. Сол себепке байланысты сөздер де формула бола алады.

   Формула түсінігі мен бірге ішформула немесе формула бөлігі түсінігі енгізіледі.

1. Қарапайым формуланың ішформуласы оның өзі болады.

2. Егер формула көрінісінде болса, онда оның ішформулалары формуланың өзі, А формуласы және А формуланың барлық ішформулалары болады.

3. Егер формула (А*В) (мұнда * – үш символдардың бірі деп түсінеміз) көрінісінде болса, онда оның ішформулалары формуланың өзі, А, В формулалары және А мен В формулалардың барлық ішформулалары болады.

   Формуладағы логикалық амалдарының саны формуланың рангі деп аталады.

      2.2. Дәлелденетін формула ұғымы

 

   Тұжырымдар  есептелімінің құруда келесі кезең  дәлелденетін (шығарылатын) формулалардың  класын бөліктеу болады.

   Дәлелденетін  формула анықтамасы формулалар анықтамасы сияқты. Алдымен бастапқы дәлелденетін шығарылатын формулалар (аксиомалар) анықталады, ал содан кейін бар дәлелденетін формулалардан жаңа дәлелденетін формулаларды алуға мүмкіндік беретін шығару ережелері анықталады. Бастапқы дәлелденетін формулалардан шығару ережелерін қолдану көмегімен жаңа дәлелденетін формуланы алу процесі берілген формуланы аксиомалардан шығаруы (дәлелдеуі) деп аталады.

             

_{2.3 Тұжырымдар есептелімінің аксиомалар жүйесі}

 

   Тұжырымдар  есептелімінің аксиомалар жүйесі төрт топқа бөлінетін 11 аксиомадан тұрады.

Аксималардың  бірінші тобы (құрамыларыны тек импликация енеді).

: .     

: .

Аксималардың  екінші тобы ( импликацияға конъюнкция қосылды):

:    

: .  

: .

Аксималардың  үшінші тобы ( импликацияға дизъюнкция қосылды):

:    

:          

: .

Аксималардың  төртінші тобы (импликацияға терістеу қосылды):

:

:                

:

_{2.4 Шығару ережелері}

 

1. Алмастыру ережесі (АЕ).

   Егер А формуласы тұжырымдар есептелімінде шығарылатын (дәлелденетін) формула, х – айнымалы, В – тұжырымдар есептелімінің кез келген формуласы болса, онда А формуладағы х айнымалыны В формулаға алмастыру нәтижесінде алынған формула да шығарылатын (дәлелденетін) болады.

   А формуладағы х айнымалыны В формулаға алмастыру амалы алмастыру деп аталады да келесі түрде жазылады:

 немесе .

   Егер А – шығарылатын (дәлелденетін) болса, онда ├А деп жазамыз. АЕ схематикалық түрде төмендегідей жазуға болады: