DiM 2203 дискретті математика

5. 
2
1
х
х
    х
1 
 х
2
  
6. 
2
1
х
х
 х
1
 х
2
 
7.  Импликацияны  дизьюнкция,  коньюнкция  және  терістеу  арқылы 
байланыстыратын төмендегідей формулалар бар. 
7.1  x
 1
 
  х
 2 
1
х
 
 х
2
  
7.2  
1
х
 
  х
 2 
 х
1 
 х
2
  
7.3  
2
1
x
x
 
 х
1 
   х
2
 
7.4  x
 1
 
  х
 2 
2
1
x
x
 
8. Эквиваленцияның дизьюнкция , коньюнкция және  терістеу  арқылы 
өрнектелуі 
8.1  x
 1
 
 х
2
(х
1
 х
2
 )   (х
1
 х
2
 )
 (
1
х    х
2
 )   (
2
х     х
1
 ) 
8.2  x
 1
 
 х
2
(х
1
 х
2
 )   (
1
х
2
х   ) 
8.3  x 
1
 
 х
2
(
1
х
 х
2
 )   (
2
х
 х
1
 ) 
8.4  x
 1
 
 х
2
2
1
х
х
      
1
2
х
х
 
Кейде формулаларды қысқарту үшін конъюнкция белгісін жазбайды. 
Z
Y
X
)
(
-  өрнегін   
Z
XY
,  деп  ал   
X
Z
Y
X
)
(
  -  өрнегін 
X
Z
Y
X
))
(
(
  деп 
түсіну керек. 
Импликация  мен  эквиваленцияны  конъюнкция,  дизъюнкция, 
терістеу арқылы өрнектеу. 
,
 белгілері бар  кез-келген формуланы 
,
 белгілері жоқ басқа 
эквивалентті формуламен ауыстыруға болатының дәлелдейміз. 
Айталық   
Y
X
Y
X
    (1)     
Y
X
Y
X
      (2)  формулалары  белгілі 
болсын. Бірінші формулада импликация дизъюнкция мен терістеу арқылы, ал 
екінші  формуладағы  импликация    конъюнкция  мен  терістеу  арқылы  
өрнектеліп  тұр.  Мына  эквиваленцияны 
)
(
&
)
(
X
Y
Y
X
Y
X
  (3)  конъюнкция, 
импликация арқылы өрнектеуге болатындығын көрсетейік.  
Тексеру: 
X
 
Y
 
Y
X
 
X
Y
 
(
Y
X
)& 
(
X
Y
) 
 
Y
X
 
а 
а 
а 
а 
а 
а 
а 
ж 
ж 
а 
ж 
ж 
ж 
а 
а 
ж 
ж 
ж 
ж 
ж  
а 
а 
а 
а 
(3) пен (1) ден  
)
(
&
)
(
X
Y
Y
X
Y
X
 (4) ( конъюнкция, дизъюнк ция, терістеу) 
(3)-пен (2)-ден 
)
(
)
(
)
(
Y
X
Y
X
Y
X
  (5)  (конъюнкция, терістеу)
 
 
5-Дәріс.  Пікірлерді есептеу. Аксиомалар. Қорыту ережелері. 
 

Пікірлер  есептелімі  бұл  интерпретациясы  пікірлер  алгебрасы  болатын 
аксиоматикалық логикалық жүйе.  
Әрбір  есептелімнің  сипаттамасына  бұл  есептелімі  символдарының, 
формулаларының  сипаттамасы,  дәлелденетін  формулалардың  анықтамасы 
енеді.  
Пікірлер есептелімінің алфавиті үш түрлі символдардан тұрады: 
1. 


,
,
,
,
,
,
2
1
x
x
z
y
x
 Бұл символдарды айнымалы пікірлер деп атаймыз.  
2. 
.
,
,
,
  Бұл  символдар  логикалық  байланыс  деген  жалпы  атауға  ие. 
Келтірілген  символдардың  біріншісі  дизъюнкция  (немесе  логикалық  қосу) 
белгісі, екіншісі – конъюнкция (немесе логикалық көбейту) белгісі, үшіншісі 
– импликация және төртіншісі – терістеу белгісі.  
3. Жақшалар деп аталатын символдар: (,   ). 
Пікірлер есептелімінде басқа символдар болмайды. 
Пікірлер  есептелімінің  формуласы  пікірлер  есептелімі  алфавитінің 
символдарының  тізбегі  болады.  Формула  белгісі  үшін  латын  алфавитінің 
үлкен  әріптерін  қолданамыз.  Олар  өздері  есептелімнің  символдары  болмай, 
формулалардың тек шартты белгілері болады.  
Пікірлер есептелімі формуласының анықтамасы 
1. Кез келген 

,
,
,
z
y
x
  айнымалы формула б олады.  
2.  Егер  А  және  В  –  формулалар  болса,  онда 
А
В
А
В
А
В
А
,
,
,
 
сөздер де формулалар.  
3. Ешқандай басқа символдардың қатары формула болмайды. 
Айнымалы пікірлерды қарапайым формулалар деп атаймыз.  
Пікірлер есептелімі формуласына мысал келтірейік.  
z
y
x
,
,
  айнымалы  пікірлер  анықтаманың  1-ші  бөлімі  бойынша 
формулалар  болады.  Бірақ,  онда 
x
z
y
z
x
y
x
,
,
),
(
  сөздер  де  
анықтаманың  2-ші  бөлімі  бойынша  формулалар  бола  алады.  Сол  себепке 
байланысты 
z
y
y
x
z
y
z
x
y
x
,
,
  сөздер  де    формула 
бола алады. 
Формула түсінігі мен бірге ішформула немесе формула бөлігі түсінігі 
енгізіледі.  
1. Қарапайым формуланың ішформуласы оның өзі болады.  
2.  Егер  формула 
A
  көрінісінде  болса,  онда  оның  ішформулалары 
формуланың өзі, А формуласы және А формуланың барлық ішформулалары 
болады.  
3.  Егер  формула  (А*В)  (мұнда  *  –   
,
,
  үш  символдардың  бірі  деп 
түсінеміз) көрінісінде болса, онда оның ішформулалары формуланың өзі, А, 
В  формулалары  және  А  мен  В  формулалардың  барлық  ішформулалары 
болады. 
Формуладағы  логикалық  амалдарының  саны  формуланың  рангі  деп 
аталады. 
 

5.1. Дәлелденетін формула ұғымы 
 
Пікірлер  есептелімінің  құруда  келесі  кезең  дәлелденетін  (шығарылатын) 
формулалардың класын бөліктеу болады.  
Дәлелденетін  формула  анықтамасы  формулалар  анықтамасы  сияқты. 
Алдымен  бастапқы  дәлелденетін  шығарылатын  формулалар  (аксиомалар) 
анықталады,  ал  содан  кейін  бар  дәлелденетін  формулалардан  жаңа 
дәлелденетін  формулаларды  алуға  мүмкіндік  беретін  шығару  ережелері 
анықталады.  Бастапқы  дәлелденетін  формулалардан  шығару  ережелерін 
қолдану  көмегімен  жаңа  дәлелденетін  формуланы  алу  процесі  берілген 
формуланы аксиомалардан шығаруы (дәлелдеуі) деп аталады.  
            
5.2. Пікірлер есептелімінің аксиомалар жүйесі 
 
Пікірлер  есептелімінің  аксиомалар  жүйесі  төрт  топқа  бөлінетін  11 
аксиомадан тұрады.  
Аксималардың бірінші тобы (құрамыларыны тек импликация енеді). 
1
: 
x
y
x
.       
2
:
z
x
y
x
z
y
x
. 
Аксималардың екінші тобы ( импликацияға конъюнкция қосылды): 
1
:
.
x
y
x
     
2
: 
y
y
x
.    
3
: 
y
x
z
y
z
x
z
. 
Аксималардың үшінші тобы ( импликацияға дизъюнкция қосылды): 
1
: 
y
x
x
     
2
:
.
y
x
y
           
3
: 
)
(
z
y
x
z
y
z
x
. 
Аксималардың төртінші тобы (импликацияға терістеу қосылды): 
1
V
:
.
x
y
y
x
  
2
V
: 
x
x
                 
3
V
: 
.
x
x
 
 
5.3. Шығару ережелері 
 
1. Алмастыру ережесі (АЕ). 
Егер  А  формуласы  пікірлер  есептелімінде  шығарылатын    (дәлелденетін) 
формула,  х  –  айнымалы,  В  –  пікірлер  есептелімінің  кез  келген  формуласы 
болса,  онда  А  формуладағы  х    айнымалыны  В  формулаға  алмастыру 
нәтижесінде алынған формула да шығарылатын  (дәлелденетін) болады. 

А  формуладағы  х    айнымалыны  В  формулаға  алмастыру  амалы 
алмастыру деп аталады да келесі түрде жазылады: 
B
X
A)
(
 немесе 
B
X
A)
(
. 
Егер А – шығарылатын  (дәлелденетін) болса, онда ├А деп жазамыз. АЕ 
схематикалық түрде төмендегідей жазуға болады: 
├А____  . 
├
B
X
A)
(
 
Бұл  жазылу  былай  оқылады:  “Егер  А  формуласы  шығарылатын  
(дәлелденетін) болса, онда 
B
X
A)
(
 формуласы да шығарылатын  (дәлелденетін) 
болады. 
2 Қорытындылау ережесі (ҚЕ). 
Егер  А  және  А→В  формулалары  пікірлер  есептелімінде  шығарылатын  
(дәлелденетін)  болса,  онда  В  формуласы  да  шығарылатын    (дәлелденетін) 
болады. Бұл ереженің схематикалық жазылуы мынадай болады: 
├А;├А→В                            (Modus ponens) 
                                      ├В 
Бұл ереженің дұрыстығы айқын: егер импликация мен  шарт ақиқат болса, 
онда импликациядағы қорытынды тек ақиқат болуы мүмкін. 
5.4.  Дәлелденетін формуланың анықтамасы 
 
а) Әрбір аксиома дәлелденетін формула болады. 
б)  Кез  келген  В  формуласынан  х    айнымалының  орнына  алмастыруды 
қолдану  нәтижесінде алынған формула – дәлелденетін формула.  
в)  А  және 
B
A
  дәлелденетін  формулаларға      қорытындылау  ережесін 
қолдану нәтижесінде алынған В формуласы –  дәлелденетін формула болады. 
г) Пікірлер есептелімінің ешқандай басқа формуласы дәледенетін болып 
саналмайды. 
Дәлелденетін  формулаларды  шығару  процесін  формулалардың  дәлелдеуі 
(шығаруы)  деп  атаймыз.  Бұл  бір  дәлелденетін  формуладан  әр  қадамда 
аксиомаларды,  алмастыру  және  қорытындылау  ережелерін  қолдану 
көмегімен  басқа  дәлелденетін  формулаға  өту  процесі  (белгілі  мағынада 
логика  алгебрасындағы  тепе-тең  түрлендірулердің  аналогі),  сондықтан 
қарапайым формуланың шығаруы да көпқадамды, күрделі болуы мүмкін. 
Туынды  шығару  ережелері,  қарастырылған  шығару  ережелері  сияқты, 
жаңа  дәлелденетін  формулаларды  алуға  мүмкіндік  береді.  Бұл  ережелер 
алмастыру  және  қорытындылау  ережелері  көмегімен  алынған,  сондықтан, 
олар туынды ережелер деп аталады. 
А – дәлелденетін формула, 
n
x
x
,
,
1

– айнымалылар, ал 
n
B
B
,
,
1

– пікірлер 
есептелімінің  кез  келген  формулалары  болсын.  Онда  А  формулада 
n
x
x
,
,
1

  

айнымалыларын 
n
B
B
,
,
1

  формулаларға  алмастыру  нәтижесі  дәлелденетін 
формула болады. 
КАЕ схематикалық түрде былай жазылады: 
├А______ 
├
n
n
B
B
X
X
A
,
,
,...
1
1
)
(

 
5.5.  Күрделі қорытындылау ережесі 
 
Қорытындылау  ережесін  де  жалпылау  мүмкін.  Жалпылау  нәтижесінде 
алынған туынды ереже  

L
A
A
A
A
n
...(
3
2
1
 
түрдегі формулаларға қолданылады да былай анықталады: 
егер 
n
A
A
A
,...,
,
2
1
        және     

L
A
A
A
A
n
. . (
3
2
1
  формулалар 
дәлелденетін болса, онда L формуласы да дәлелденетін формула.    
Күрделі қорытындылау ережесі былай жазылады: 
├А
1
, ├А
2
, …,├А
n
, ├A
1
→(A
2
→(A
3
→(...(A
n
→L) …)))  . 
├ L 
 
Силлогизм ережесі 
 
Егер А→В және В→С формулалары дәлелденетін болса, онда А→С 
формуласы да дәлелденеді, яғни  
├А→В,├В→С . 
├А→С 
 
Контрапозиция ережесі 
 
Егер  А→В  формуласы  дәлелденетін  болса,  онда 
A
B
  формула  да 
дәлелденеді, яғни 
├ А →В . 
├
A
B
 
Бұл  ереженің  мысалында  пікірлер  есептелімінде  мұндай  пікірлердың 
дәлелдеу жолын көрсетеміз. 
B
A
Y
X
V
,
,
1
)
(
 алмастыруын орындап,  
                ├(А→В)→├(
A
B
)   
 
               
(1) 
дәлелденетін формуланы аламыз. 
Ал шарт бойынша  
                            ├А→В                                                             (2) 
– дәлелденетін формула. 
 
 
 
 
  
Онда (2) және (1) формулаларынан қорытындылау ережесі бойынша 
├
A
B
. 
 
Екі еселі терістеу ережесі 

 
а) Егер 
B
A
 формуласы дәлелденетін болса, онда 
B
A
 формуласы да 
дәлелденетін. 
б) Егер  
B
A
 формуласы дәлелденетін болса, онда 
B
A
 формуласы да 
дәлелденетін. 
Схематикалық жазылулары:      ├ А →
B
    және      ├ 
A
→В 
                                                       ├
B
A
                    ├
B
A
     . 
 
 
5.6. Формулаларды гипотезалардан қорытып шығару 
 
Формулалардың Н={А
1
,А
2
,…,А
n
} ақырлы жиынын қарастырамыз.  
Н жиынынан шығарылатын формула анықтамасы.  
1) A
i
H формуласы Н-тан шығарылатын формула деп аталады. 
2) Әрбір дәлелденетін формула Н-тан шығарылатын болады. 
3)  Егер  С  және  С→В  формулалар  Н-тан  шығарылатын  болса,  онда  В 
формуласы да Н-тан шығарылатын болады. 
Егер  кейбір  В  формуласы  формулалардың  Н  жиынынан  шығарылатын 
болса, онда бұл былай жазылады: Н├В. 
Н жиыны бос немесе тек дәлелденетін формулалардан тұратын жағдайда 
Н 
жиынынан 
шығарылатын 
формулалардың 
класы 
дәлелденетін 
формулалардың класымен сәйкес келеді.  
Егер де Н жиынында кем дегенде бір дәлелденбейтін формула болса, онда 
Н-тан шығарылатын формулардың класы дәлелденетін формулалар класынан 
кең болады.  
Мысал. 
Формулалардың  Н={А,  В}  жиынынан 
B
A
  формуласы  шығатынын 
дәлелдеу керек. 
A H және B H болғандықтан, дәлелденетін формуланың анықтамасы 
бойынша 
 Н├А,  
 
 
 
 
 
 
                      
     (1)   
 Н├В. 
 
 
 
 
 
 
 
 
 
     (2) 
3
және 
1
  аксиомаларды  алып, 
A
B
A
Z
Y
X
,
,
,
,
3
)
(
және 
A
B
Y
X
,
,
1
)
(
  алмастыруларды 
орындаймыз. 
Нәтижесінде Н-тан шығарылатын дәлелденетін формулаларды аламыз, 
яғни 
Н├(А→А)→((А→В)→(А
B
A
)),  
 
 
               (3) 
Н├В→(А→В),   
 
 
 
 
 
 
     (4) 
А→А  формуласы дәлелденетін, онда Н├А→А.   
              (5) 
 (5) 
және  (3)  формулалардан  қорытындылау  ережесі  бойынша                                                          
Н├(А→В)→(А
B
A
)) 
 
 
 
 
 
 
     (6) 
алынады. 

 (2) және (4) формулалардан қорытындылау ережесі бойынша:   
           Н├А→В .  
 
 
 
 
 
 
 
     (7) 
(7) және (6) формулалардан қорытындылау ережесі бойынша:               
Н├А
B
A
 . 
 
 
 
 
 
 
                        (8) 
Соңында (1) және (8) формулалардан 
                 Н├
B
A
 
 
 
 
 
 
 
     (9) 
алынады. 
Формуланың  шығарылатынын  дәлелдеуде  тек  қана  қорытындылау 
ережесін емес, күрделі қорытындылау ережесін пайдалануға мүмкін екендігі 
түсінікті. Онда бұл ережені пайдаланып, (9) тұжырымды (5), (7), (1) және (3) 
пікірлердан алуға болады. 
Анықтама.  Формулалардың  Н  ақырлы  жиынынан  шығаруы  деп  әрбір 
мүшесі  келесі  шарттарды  қанағаттандыратын  формулалардың  В
1
,В
2
,…,В
к
  
тізбегін айтамыз: 
1) ол Н жиынының бір формуласы болады, 
2) ол дәлелденетін формула болады, 
3) ол В
1
,В
2
,…,В
к
  тізбегінің алдынғы кез келген екі мүшесінен қорытындылау 
ережесі бойынша шығады.  
Алдынғы мысалда көрсеткеніміздей, формулалардың Н={А,В} жиынынан 
шығаруы формулалардың келесі ақырлы тізбегі болады: 
А, 
В, 
(А→А)→((А→В)→(А
B
A
)), 
(А→В), 
А→А, 
(А→В)→(А
B
A
)), А→В, А
B
A
, 
B
A
. (1,2,3,7,5,6,8 формулалар). 
Егер күрделі қорытындылау ережесін пайдалансақ, онда шығаруды былай 
жазуға болады: 
 А, В, (А→А)→((А→В)→(А
B
A
)), В→(А→В), А→А, А→В, 
B
A
. (5, 
7, 1, 3 формулалар). 
Шығарылатын  формула  анықтамасынан  және  формулалар  жиынынан 
шығару анықтамасынан шығарудың келесі қасиеттері келіп шығады: 
1) Н жиынынан шығарудың әрбір бастапқы кесіндісі – Н-тан шығару болады.  
2)  Егер  Н  тан  шығарудың  екі  көршілес  мүшелерінің  арасында  (басында 
немесе  соңында)  кейбір  Н  тан  шығаруді  қойсақ,  онда  формулалардың 
алынған жаңа тізбегі Н тан шығару болады.  
3)  Н  жиынынан  шығарудың  әрбір  мүшесі  Н  тан  шығарылатын  формула 
болады.  Н  тан  кез  келген  шығару  оның  соңғы  формуласының  шығаруы 
болады.  
4) Егер 
W
H
 болса, онда Н тан кез келген шығару W  дан шығару болады.  
5)  В  формуласы  Н  жиынынан  шығарылатын  болуы  үшін  бұл 
формуланың Н тан шығаруы бар болуы қажетті және жеткілікті. 
5.7. Шығарылу ережелері 
 
Бұл ережелер шығарудың қасиеттерінен алмастыру және қорытындылау 
ережелерін қолдану арқылы тікелей келіп шығады.  
Н және W – пікірлер есептелімі формулаларының екі тобы болсын.  
Н, W  арқылы олардың бірігуін белгілейміз, яғни Н,W=
W
H
. 

Мысалы, W  жиыны тек бір С формуласынан тұратын жағдайда  
C
H
 
біріктіруді Н, С түрінде жазамыз.  
Негізгі шығарылу ережелерін көрсетейік.  
 
1.    H  ├  A                            Бұл  ереже  формулалар  жиынынан  шығарудың 
анықтамасынан                                                   H,W├A           келіп шығады: 
“Егер  А  формуласы  Н  тан  шығарылатын  болса,    онда  ол 
W
H
  тан  да 
шығарылады. ”. 
 
    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
1
, C
1
, …, C
k
}├ A   
                                                                           ├C
1
→(C
2
→(C
3
→…(C
k
→A)…)) 
    
  6. Конъюнкцияны енгізу ережесі:   H├A,H├B   . 
                                                                 H├
B
A
 
   
  7. Дизъюнкцияны енгізу ережесі:                  H,A├C;Н,B├C   . 
                                                                                  H,
B
A
├C 
 
 
5.8. Пікірлер алгебрасы мен пікірлер есептелімі арасындағы 
байланыс 
 
Пікірлер 
есептелімінің 
формулаларын 
пікірлер 
алгебрасының 
формулалары  ретінде  қарастыруға  болады.  Ол  үшін  пікірлер  есептелімінің 
айнымалыларын  пікірлер  алгебрасының  айнымалысындай,  яғни  екі  ақиқат 
және жалған мән қабылдайтын, қарастырамыз.  
,
,
,
  операцияларын    пікірлер  алгебрасында  сияқты  анықтаймыз. 
Пікірлер  есептелімінің  формулалары  пікірлер  алгебрасының  ережелері 
бойынша есептелетін 1 немесе 0 мәндерінің біреуін ғана қабылдайды.  
Пікірлер  есептелімі  формуласының  мәні  түсінігін  енгіземіз.  А  –  пікірлер 
есептелімінің  формуласы,  х
1
,х
2
,…,х
n
  –  өзара  әртүрлі  А  формуласына  енетін 
айнымалылар  болсын.  а
1
,  а
2
,…,а
n
  арқылы  бұл  айнымалыларының  мәндер 
тобын белгілейміз. (а
1
, а
2
,…,а
n
) векторы 2
n
 мән қабылдайтыны айқын.  

Келесі үш теорема орынды.  
Теорема  1.  Әрбір  пікірлер  есептелімінде  дәлелденетін  формула  пікірлер 
алгебрасында тепе-тең ақиқат болады.  
Теорема 2. (шығарылу туралы).  А – пікірлер есептелімінің қандай да бір 
формуласы болсын; х
1
,х
2
,…,х
n   
– А формулаға енетін айнымалылардың тобы; 
а
1
,  а
2
,  …,  а
n
  –  бұл  айнымалылар  мәндерінің  кез  келген  бекітілген  тобы.  Н 
арқылы формулалардың ақырлы жиынынын белгілейміз: 
an
n
a
a
x
x
x
H
,...,
,
2
2
1
1
, где 
.
0
 
,
,
1
 
,
i
i
i
i
ai
i
a
если
x
a
если
x
x
 
Онда: 
1)  Егер R
a1,a2,..,an
(A)=1 болса, онда H├A . 
2)  Егер  R
a1,a2,..,an
(A)=0  болса,  онда  H├
A
,  мұнда  R
a1,a2,..,an
(A)  –  А 
формуланың а
1
, а
2
,…,а
n
  топтағы мәні.  
 
Теорема 3.  Пікірлер алгебрасының әрбір тепе-тең ақиқат формуласы 
пікірлер есептелімінде дәлелденетін формула болады.
 
 

жүктеу/скачать 3,62 Mb.

Достарыңызбен бөлісу: