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

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

Pdf көрінісі

бет	6/16
Дата	25.11.2019
өлшемі	3,62 Mb.
	#52396

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

Байланысты:
umkd (1)

4-дәріс. Пікірлер алгебрасы.

Математикалық  логика  жоғары  математиканың  бір  (бөлімі)  саласы
болып  табылады.  Математикалық  логиканың  заңдары  мен  әдістері  арқылы
түрлі  процестерге,  жүйелерге,  қүбылыстарға  зерттеулер  жүргізуге  болады.
Математикалық логиканың негізгі обьектілерінің бірі түжырымдар.
4.1. Пікірлер.

Анықтама.Пікірлер  деп  деп  ақиқаттығы  немесе  жалғандығы  туралы
айтуға болатын хабарлы сөйлемді айтамыз. Бүкіл ғылыми білімдер (физика,
химия,  биологияның  заңдары  мен  құбылыстары,  математика  т.б)  күнделікті
өмірде  болып  жатқан  оқиғалар,  экономика  мен  басқару  процесінде
туындайтын түрлі ситуациялар пікірлер түрінде формальданады.
Сұраулы,  лепті  не  болмаса  мағнасыз  сөйлемдер  тұжырым  бола
алмайды. Пікірлерге мысалдар:  «2 жерде 2-төрт» ,  «Біз 20 –шы ғасырда өмір
сүріп жатырмыз», «Қосылғыштардың орны ауысқаннан қосынды өзгермейді»
,  «Астана-  Қазақстаның  астанасы»,      «Теңге-Қазақстан  валютасы»    ,  «Бүгін
сейсенбі»,      «Егер  жаңбыр  жауып  тұрса  қол  шатыр  алыңыз»    т.б    Пікірлер.
«Математика-  қызықты  пән  немесе  қуырдақ  дәмді  тамақ»  деген  сөйлемдер
де тұжырым емес, себебі бірдей пікір жоқ. «Бөлменің ауданы  20 м
2
», «Қар
жауып  тұр»,«а
2
=4»  деген  сөйлемдер  түжырым  емес  ,  1-  сөйлемде  нақтылы
қандай бөлме екендігі көрсетілуі керек, екінші сөйлемде     қайда қар жауып
тұрғанын  көрсететін  қосымша  сөз  керек,  үшінші      сөйлем      а  =  2    (а-
тұжырымдылық  айнымалысы  )  болғандықтан    тұжырым  бола  алмайды.  Бұл
сөйлемдермен  амалдар  орындау  үшін  олардың  әрқайысысының  ақиқаттық
мәнін білу керек.
Пікірлер логикасының негізгі логикалық байланыстырушылары.
Табиғи  қарапайым  сөйлемдерден  құрмалас  сөйлемдер  құру  үшін      “
және “, “ немесе “, “егер … онда “, “ сонда … тек
сонда ғана “ сияқты шылаулар қолданылатындығы
белгілі.
Пікірлертеориясында
да
элементар
Пікірлердан
күрделі
Пікірлер
құрастыруға
болады. Айталық P,Q логикалық Пікірлер болсын.
Оларға  кестедегідей  логикалық  байланыстар  қолданылады:    Логикалық
байланыстырушылар  арқылы  құрылған  құрама  Пікірлердың    ақиқат  не
жалғандығы  ,  оның  құрамына  кіретін        қарапайым  Пікірлердың  ақиқаттық
мәндерімен  анықталады.
4.2. Пікірлерге қолданылатын амалдар
1.  Анықтама.  Терістеу  (инверциясы)  А-ның  инвер-
сиясы деп А жалған болса мәні ақиқат, ақиқат болса жалған
болатын тұжырымды айтады.
А
болып белгіленеді, А емес
, А деген дүрыс емес болып оқылады    Мысалы,
1. «3-2 ге тең» тұжырымын А десек, «3-2 ге тең емес»
тұжырымын
А
- дейміз.
2. Кез келген шеңберге іштей үшбүрыш сызуға болады дегенді-А десек,
кез келген шеңберге іштей үшбүрыш сызуға болады деу дұрыс емес-
А
.
Конъюнкция  мен  дизъюнкция.Айталық,  А  мен  В  кез-келген  Пікірлер
болсын. Тұжырымның ақиқат белгісін а әрпімен, жалған белгісін  ж әрпімен
белгілейік.
2.  Анықтама.  А  мен  В  Пікірлерының  коньюнкциясы  деп  (логикалық
көбейтінді  немесе  «және»  операциясы)  А  мен  В  екеуі  де
ақиқат болса мәні ақиқат, әйтпесе (екеуі де жалған болса )
жалған болатын тұжырымды айтамыз.

Конъюнкция  ,  ,& белгілерімен белгіленеді.
А&В; А В; А В.
3.  Анықтама.  А  мен  В  дизъюнкциясы  деп  мәні  А  мен  В
тұжырымының  екеуі  де  жалған  болғанда  мәні  жалған,  ал
қалған  жағдайларда  ақиқат  болатын  тұжырымды  айтамыз.
Дизъюнкция   белгісімен белгіленеді. А  В;  А немесе В –
болып  оқылады.  Сонымен  «және»,  «немесе»  логикалық
байланыстырушылар  арқылы  байланысқан
Пікірлер
құрама  тұжырым  дар    болады.  «Және»,  «немесе»  логикалық
байланыстырушылар      арқылы  жаңа  құрама  Пікірлер    алуды  логикалық
операция  дейміз.  Арифметикалық  операцияларда    операция  және  оның
нәтижелері  әртүрлі  аталады:  қосылғыш,  қосынды,көбейтінді.  А  логикалық
операцияларда  операнд  пен  нәтиже бірдей аталады.Сонымен конъюнкция
мен  дизъюнкция  анықтамасын  құрама  тұжырымның  қайсысына  болса  да
қолдануға болады.
N  тұжырымның конъюнкциясы деп
n
A
A
A
....
2
1
    түріндегі    сөйлем
құрамындағы барлық Пікірлер ақиқат болғанда ғана ақиқат болатын сөйлемді
айтамыз.
N  тұжырымның  дизъюнкциясы  деп
An
A
A
....
2
1
  түріндегі  сөйлем
құрамындағы барлық Пікірлер жалған болған сөйлемді айтамыз.
Импликация және эквиваленция
4.  Анықтама.  Импликация  (логика).  Екі  А  мен  В
Пікірлерының  импликациясы  деп  А–ақиқат,  В  жалған
болғанда мәні жалған, ал қалған жағдайда ақиқат болатын
тұжырымды  айтамыз.Операция
  (Егер…  онда)  белгімен
белгіленеді. А  В, А   В ( егер  А болса, онда  В)  (А дан
В)  болып  оқылады.Мұнда  А–тұжырымының  алғы  шарты  деп  ал  В
қорытындысы деп аталады.
5. Анықтама. Эквиваленция А мен В тұжырымының
ақиқаттық  мәндері  бірдей  болғанда,  мәндері  ақиқат,  әр
түрлі  болғанда  (А,В)  жалған  болатын  тұжырым
эквивалентті  тұжырым  деп  аталады.  Белгілеулері:  А В;
А В;  А
В;  А  эквивалентті  В-ға  ;  Егер  тек  В  болғанда  А  ;    А  мен  В  бір
мәнді, А мен В   сонда ғана ақиқат, егер А,В түжырымдары ның екеуі де не
ақиқат, не жалған болса. болып оқылады.
6.  Анықтама.  2-нің  модулі  бойынша  қосу.  Бір  мәнді  емес  тұжырым.
(«немесе»-ні  терістеу,антиэквиваленция,  2–ң  модулі
бойынша  қосу).  А-мен  В-  ң  ақиқаттық  мәндері  бірдей
болмаса  мәні  ақиқат,  керісінше  бірдей  болса  жалған
болатын  тұжырым бір мәнді емес тұжырым деп аталады.
А  В,  А В,А В    болып  белгіленеді  (  не  А,  не  В  болып
оқылады).
Шеффер штрихы және Пирс стрелкасы

7.Анықтама
В
А

Шеффер
штрихы
деп
аталады
В
А &

(антиконъюнкция).
8.
Анықтама.
А В–Пирс
стрелкасы
(антидизъюнкция)
В
А


Логика алгебрасы.
Логика  алгебрасы  математикалық  логиканың  бір  бөлімі.  Логика
алгебрасында    күрделі  логикалық  пікірлердің  (логикалық  формулалардың)
құрылымы  және  алгебралық  әдістердің  көмегімен  олардың  ақиқаттығын
анықтау әдістері қарастырылады.
Бұл бөлімде негізінен логика алгебралық формулаларын  қарастыратын
боламыз.
Формулалар  әріптерден,  логикалық  операциядан    және  жақшадан
тұрады.  Әріптер  тек  “ақиқат”,    “жалған  “  деген  екі  мәннің  бірін    ғана
қабылдай  алатын  логикалық  айнымалылар.  Операция  белгілері  логикалық
амалдарды белгілейді. Әр формула логикалық функцияны береді, ал функция
өз  кезегінде  2    мәннің  бірін  қабылдайды  (0,1).  Логика  алгебрасы  дегеніміз
өзінің  барлық  мүмкін  операцияларымен  бірге  қарастырылатын    {0,1}
жиынынан құралған  алгебра.
Пікірлер логикасының тілі  Айталық Х,У және Z орындарына кез –
келген  тұжырымды  қоюға  болатын  айнымалылар  болсын.  Мұндай
айнымалылар тұжырымдылық айнымалылары деп аталады. Тұжырымдылық
айнымалылар  мен  логикалық  операциялар  символдарының  көмегімен  кез  –
келген  тұжырымды  формальдандыруға,  яғни  формуламен  алмастыруға
болады.
Мысалы,  мына  тұжырымды  егер  100  2-ге  және  5ке  бөлінсе,  онда  100
10ға  бөлінеді   деген  тұжырым    берілсін:  Х  : 100 2-ге  бөлінеді;  У :  100 5-ке
бөлінеді; Z : 100 10-ға бөлінеді
Бұл тұжырымды ( Х У) Z формуласы  арқылы кескіндеуге болады.
Енді  Пікірлер  логикасының  формуласы  ұғымын  ттолықтырайық.  Ол
үшін Пікірлер логикасында қолданылатын алфавит   ұғымын енгізейік.
X,Y,Z,    x
i
,y
i
,z
i
    (і-  натурал  сан)  (x
1
,x
2
,…,x
т
)  тұжырымдылық
айнымалылары;
а,ж – ақиқат, жалған логикалық тұрақтларды белгілейтін символдар;
,
,
,
,
- логикалық операциялар символдары;
( , )-логикасы операциясының ажыратушы;
Пікірлер логикасы формуласының анықтамасы
Анықтама.  Егер  А  –  формуласының  барлық  айнымылылары

1
i
,…,x
ik
>   реттелген жиынтығына жатса, онда бұл
1
i
,…,x
ik
> жиынтығы
А
формуласының
айнымалылар
тізімі
деп
аталады.
Тізімдегі
айнымалылардың  бір  бөлігі  А  ға  айқын  кірмеу  мүмкін.  Оларды  жасанды
айнымалы дейміз.

Анықтама.    Тізімдегі  әр  айнымалыға  ақикаттық  мән  сәйкестендіруді
айнымалылар  тізімін  бағалау  дейміз.  Егер  А  формуласының  айнымалылар
тізімінде к айнымалы болса онда 2
k
– ке тең бағалар болады, демек ақикаттың
кестесінде 2
k
– тең жол болады.
Пікірлерды  белгілейтін  әріптер,  логикалық  байланыстар,  жақшалар
логикалық  тұжырым  тілінің  алфавиті  деп  аталады.  Алфавит  элементтерінің
көмегімен  түрлі  формулалар  құруға  болады.  Математикалық  логикада
қабылданғандай  формулаға нақтылы анықтама берейік:
Анықтама.
Пікірлердың
белгілері
және
логикалық
байланыстырушылармен  (жақшада  көрсетілген)    құрылған  өрнек  логикалық
формула деп аталады,егер ол төмендегі шарттарды  қанағаттандырса:
Пікірлерды белгілейтін кез келген логикалық айнымалы - формула;
А, Ж – символдары  формула
Егер А – формула болса, онда  А формула
Егер  А и В – формулалар болса ,онда (А & В), (А   В), (А), (А   В), (А ~
В), (Р   Q) – формула болады;
Алдыңғы төрт пункттегіден  басқа формула жоқ.
Тұжырымды формальдау процедурасы
Егер  тұжырым  қарапайым  болса,  оған  қарапайым  формула
сәйкестендіріледі.
Егер тұжырым құрама болса, онда оған сәйкес формула құру үшін
а)  Құрама  тұжырым  құрып  тұрған  барлық  қарапайым  Пікірлерды
байланыстырушылардан бөліп алу керек;
б) Оларды сәйкес символдармен алмастыру керек;
в)  Пікірлердың  мағынасына  қарай  жақшалар  қою  керек.  Формула
қарапайым  болу  үшін  сыртқы  жақшаларды  жазбауға  болады;  Жақшалар
сыңарлары  тең  болу  керек.  Мысалы,
1
3
2
1
)
(
x
x
x
x
-формула  емес;
1
2
1
)
(
x
x
x
- формула;
~
(
1
x
3
2
)
x
x
-формула.
Логикалық Пікірлер формулаларының эквиваленттілігі.
Анықтама.  Айталық  А  мен  В  бір  айнымалылар  тізіміне    <
k
i
i
x
x ,...,
1
>
тәуелді  екі  формула  болсын.  Егер  олар  <
k
i
i
x
x ,...,
1
>  тізімінің  кез-  келген
бағасында  бірдей  мәндер  қабылдаса    оларды  эквивалентті  формулалар  деп
атайды.
Анықтама.
Егер
F1(x1,x2,…,xn)
және
F2
(x1,x2,…,xn)
формулаларының    ақиқаттық  кестелері  бірдей  болса  бұл  формулалар
эквивалентті  деп  аталады  және  «~, ,
»  белгілерінің  бірімен  көрсетіледі.
Екі  формуланың  эквиваленттілігін  білудің  стандартты  тәсілі  екеуінің
ақиқаттық  кестесін  құрып,  алынған  нәтижені  салыстыру  болып  табылады.
Мысалы:  (x
  y)  ~(
y

x
)    формулаларының  эквиваленттігін  мына
ақиқаттық кестеден  көруге болады.
Алынған  ақиқаттық  кесте  әрбір  құрама  бойынша  салыстырылады.
Эквивалент формулалардың  мынадай қасиеттері бар:
х
у
x
y
x

y

y

x

0
1
1
1
1
0
1
1
1
0
1
1
0
0
0
1
0
1
1
1
0
0
1

Буль алгебрасының негізгі эквивалентті қатынастары  (заңдары)
1. Коньюнкция мен дизьюнкцияның ассоциативтілігі
а) x
1
(x
2
x
3
)=(x
1
x
2
) x
3
=x
1
x
2
x
3
;  б)x
1
(x
2
x
3
)=(x
1
x
2
) x
3
=x
1
x
2
x
3

2. Коньюнкция мен дизьюнкцияның  коммутативтілігі
а) x
1
x
2
=x
2
x
1
;  б)x
1
x
2
=x
2
x
1

3.Коньюнкцияның
дизьюнкцияға
қатысты
дистрибутивтілігі
(Дизьюнкцияның коньюнкцияға қатысты дистрибутивтілігі).
а) x
1
(x
2
x
3
)=(x
1
x
2
)
x
1
x
3
; б) x
1
(x
2
x
3
)=(x
1
x
2
)
x
1
x
3

4. Идемпотенттілік
а) x

x х; б) x

x   х
5. Қос терістеу заңы.
х

х

6. 0 мен 1 константаларының қасиеттері:
а) x

1 х ; в) x

x 1; д)
0
1;
б) x

0 0 ;  г) x

0 х ; е)
0
1
;
7. Морган заңдары:
а)
2
1
2
1
х
х
х
х
;  б)
2
1
2
1
х
х
х
х

Қарама- қарсылық заңдары:
а)
х
х &
0      (
х
х &
ж)
б)
х
х
1     (
х
х
а)
Бұл негізгі эквиваленттік қатынастардың ерекшелігі, олар бір –бірінен
шықпайды,  олардың  дұрыстығына,  стандартты  әдіспен  ғана    (ақиқат  тық
кесте) көз жеткізуге болады.
2-модулі  бойынша  қосу,  импликация,  Шеффер  және  Веб
операцияларының қасиеттері.
Импликация мен 2 модулі бойынша қосу функцияларының қасиеттері
дискретті құрылғыларды анализдеу, синтездеу кезінде пайдалы.
2-нің  модулі  бойынша  қосу  операциясы  үшін  ассоциативті,  коммута
тивті заңдар және коньюнкцияға қатысты дистрибутивті (распределит) заңы
бар.
1. x
1
    х
2
х
2
  x
1
коммутативтілік
2. x
1
      х
2
  x
3
       x
1
    х
2
     х
3
  ассоциативтілік
3. x
1
      х
2
  x
3
       x
1
   х
2
        x
1
   х
2

бұларға қоса
1. x

    х

0;  2. х

0

х;   3. x

   1

х
;  4. х


х
1;
және x
1
    х
2
х
1
  x
2

x
1
   х
2

x
1

х
2

2
1
~ x
x

)
(
)
(
2
1
2
1
x
x
x
x

формулалары бар.
Импликация үшін коммутативті, ассоциативті заңдар жоқ.

x

х

1;
х

х
х
;   x

  1

1;
x

0

х;    0
  х

1;   1

  х

х;
1
2
2
1
x
x
х
х
;   x
1

  х
2
х
1
х
1

Шеффер  және  Веб  функциялары  үшін  коммутативті  (переместит)  заң
бар.
x
1
    х
2
  х
2
х
1

x
1
   х
2
х
2
х
1

ассоциативті заң бұлар үшін орындалмайды.
x
1
     х
2
х
3
     х
1
х
2
)   х
3

x
1
     х
2
х
3
     х
1
х
2
)   х
3

Және мына заңдар орындалады.

Шеффер  мен  Веб  функциялары  бір-бірімен  дизьюнкция  мен
коньюнкцияға  арналған    Морган  заңдары  сияқты  заңдылықтармен
байланысқан.
а) x
1
    х
2

2
1
x
x
;   в) x
1
х
2
2
1
x
x

Жалпылама  формулалар.
,

операциялары  ассоциативті
болғандықтан
,
&
&
&
2
1
n


n

2
1


  өрнектерінде  жақша
қоймауға болады. Бірінші өрнек көп мүшелі коньюнкция, екіншісі көпмүшелі
дизьюнкция. Бұлар дистрибутивті заңға және Морган заңдарына бағынады:
Дистрибутивті  заң:
(А
1
   А
2
   ...   А
к
)   (В
1
   В
2
   ...   В
l
)  ( А
1
   В
1
)   ( А
1
   В
2
)   ...  (
А
1
   В
l
)  ( А
2
   В
1
)   ( А
2
   В
2
)   ...  ( А
2
   В
l
)
...    ...  ...            ...( А
к
   В
1
)   ( А
к
   В
2
)   ...  ( А
к
   В
l
)  (А
1
   А
2
   ...
А
к
)   (В
1
   В
2
   ...   В
l
)
( А
1
   В
1
)   ( А
1
   В
2
)   ...  ( А
1
   В
l
) ( А
2
   В
1
)   ( А
2
   В
2
)   ...  ( А
2

В
l
)
...       ...             ...( А
к
   В
1
)   ( А
к
   В
2
)   ...  ( А
к
   В
l
)

Көп  мушелі  коньюнкция  мен  дизьюнкцияға  да  Морган  заңдарын
қолдануға болады.
1.  (
к
А
А
А
...
2
1
)   (
к
А
А
А
...
2
1
)
2.  (
к
А
А
А
...
2
1
)   (
к
А
А
А
...
2
1
)
3.  x

   х   ...     х  х
4.  x

   х   ...     х  х

5.  x
1
   х
2
...     х
n

n
х
х
х
...
2
1

6.  x
1
   х
2
...     х
n

n
х
х
х
...
2
1

Эквивалентті түрлендірулер. Формулаларды ықшамдау.
Эквивалентті  формулаларда  бір  айнымалыны  (барлық  жерінде)  басқа
бір  формуламен  ауыстырсақ,  жаңадан  алған  формула  тағы  да  эквивалентті
болып шығады.
Мысалы,        мына формуланың
Y
X
Y
X
  эквиваленттігін  жоғарыда
стандартты  әдіспен    дәлелдедік  яғни  ол  тавтология  .    Ал  енді  бұл
формуладағы  х-ң  орнына
x
  қойсақ,
y
-ң  орнына
y
x
  қойсақ  жаңа
эквивалентті формула аламыз.
Y
X
X
Y
X
X
)
(

Егер  қандай  да  бір  F  формуланың  құрамына  кіретін  F1-ді  оған
эквивалентті    F2  формуласымен  алмастырсақ,  алынған  формула  F-ке
эквивалентті болып шығады.
Осыған байланысты
Y
X
X
Y
X
X
-қос терістеу заңы бойынша
Y
X
X

)
(
Y
X
X
-Де Морган заңы бойынша
)
(
)
(
Y
X
X
Y
X
X
-қос терістеу заңы
Y
X
X
Y
X
X
)
(
)
(
-ассоциативті заң бойынша
Y
X
Y
X
X
)
(
-идемпотентті заңы бойынша
Эквиваленттік  қатынастың  транзитивті  қасиетіне  байланысты
жоғарыдағы  формулалар  тізбегінің  1-шісімен  соңғының  эквиваленттігін
жазуға болады.
Y
X
Y
X
X

Логиканың    аталған  заңдарына  формулаларды  қысқартқанда  жиі
қолданылатын тағы бірнеше эквиваленттіктерді қосуға болады.
Анықтама.  Формуланы    оған    эквивалентті  (мәндес)  басқа
формуламен ауыстыруды эквивалентті түрлендіру дейміз.
Формулаларды ықшамдау.
Формуланы    ықшамдау  деп  (
,
,
-қос  терістеу  белгілері  жоқ
формулаға  түрлендіретін  немесе  алғашқыға  қарағанда
,   белгілері  аз
формулаға түрлендіруді айтамыз. Негізгі эквиваленттік  қатынастардан басқа
формулаларды  ықшамдау  үшін  төмендегідей  эквивалентті  қатынастар
қолданылады.
1. Жұтылу заңдары.
X
Y
X
X
)
(
;
2. Желімдеу заңдары.
1.
;
)
(
)
(
Y
Y
X
Y
X

3. Жалпылама желімдеу заңы.
Z
Y
XZ
XY
Z
Y
XZ

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

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

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