5 – лекция

1.11  Логика алгебрасыныѕ функциялары

 

Жоєарыда айтылєандай, логика алгебрасы формуласыныѕ мјні бўл формулаєа кіретін тўжырымдардыѕ мјндеріне тјуелді. Сондыќтан логика алгебрасыныѕ формуласы оєан кіретін ќарапайым тўжырымдардыѕ функциясы болады.

Мысалы,  формуласы їш айнымалыныѕ f(x,y,z) функциясы болады. Бўл функция жјне оныѕ аргументтері тек нґл немесе бір екі мјнніѕ біреуін ќабылдайды.

Аныќтама  n айнымалы логика алгебрасыныѕ функциясы (немесе Буль функциясы) деп n айнымалы функция айтылады,мўнда јрбір айнымалы жјне функцияныѕ ґзі 0 мен 1 мјндерініѕ бірін єана ќабылдай алады.

Логика алгебрасыныѕ тепе-теѕ аќиќат жјне тепе-теѕ жалєан формулалары тўраќты функциялар болатыны,ал екі пара-пар функциялар бір функцияны ґрнектейтіні айќын.

 n айнымалы функциялардыѕ санын аныќтаймыз. Логика алгебрасыныѕ јрбір функциясын (логика алгебрасыныѕ формуласы сияќты) 2n  ќатардан тўратын аќиќаттыќ кестесі кґмегімен беруге болады, яєни логика алгебрасыныѕ јрбір n айнымалы функциясы 2n  јртїрлі мјн ќабылдайды. Сондыќтан, n айнымалы функциясы ўзындыєы 2n болєан нґл жјне бір мјндерінен тўратын кейбір тобымен толыєымен аныќталады, ал ўзындыєы 2n болєан нґл жјне бірден тўратын топтарыныѕ жалпы саны  теѕ. Демек, логика алгебрасыныѕ барлыќ n айнымалы функциялардыѕ саны  санына теѕ.

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

Бір айнымалы барлыќ функциялардыѕ аќиќаттыќ кестесін ќарастырамыз. Ол келесі кґріністе болады:

 

x

f1(x)

f2(x)

f3(x)

f4(x)

1

1

1

0

0

0

1

0

1

0

 

Бўл кестеден кґрінгендей, бір айнымалы екі функциясы тўраќтылар болады: f1(x)=1, f4(x)=0, ал .

Барлыќ мїмкін болєан екі айнымалы функциялардыѕ аќиќаттыќ кестесі келесі тїрде болады:.

 

x

Y

f1

f2

f3

f4

f5

f6

f7

f8

F9

f10

f11

f12

f13

f14

f15

f16

1

1

1

1

1

1

0

1

1

0

0

0

1

0

0

0

1

0

1

0

1

1

1

0

1

1

0

0

1

1

0

0

0

1

0

0

0

1

1

1

0

1

1

0

0

1

1

0

1

0

1

0

0

0

0

0

1

0

1

1

1

0

1

1

0

1

0

1

0

0

0

0

 

Тїсінікті, бўл функциялардыѕ аналитикалыќ ґрнектері келесі тїрде жазылуы мїмкін:

,                 ,           ,                  ,

,           ,                ,                                    ,

,                  ,           ,                                  ,

,         ,                 ,                              .

 функциясы Пирс функциясы деп аталады жјне былай белгіленеді:  (Пирс баєыты), ал  функциясы Шеффер функциясы деп аталады,  арќылы белгіленеді (Шеффер сызыєы). Осы екі функциялардыѕ јрбірі барлыќ бульдік функциялардыѕ жиынын туындатады.

 

1.12  Нормал жјне жетілдірілген формалар

 

А(а1, а2, …, аn) n тўжырымныѕ формуласын ќарастырайыќ.

Аныќтама 1. n  тўжырымныѕ ќарапайым конъюнкциясы (ќарапайым дизъюнкциясы) деп тўжырымдардыѕ немесе олардыѕ терістеулерініѕ конъюнкциясын (дизъюнкциясын) айтады.

Мысал 1. xyz, Øxy – ќарапайым конъюнкция;

ØxÚyÚz, yÚz, xÚØz –ќарапайым дизъюнкция.

Аныќтама 2. Егер А формуладаєы ќарапайым дизъюнкциялар бір-бірімен конъюнкцияныѕ кґмегімен байланысќан болса, онда формуланы конъюнктивті нормал форма (КНФ) деп атаймыз.

Аныќтама 3. Егер А формуладаєы ќарапайым конъюнкциялар бір-бірімен дизъюнкцияныѕ кґмегімен байланысќан болса, онда формуланы дизъюнктивті нормал форма (ДНФ) деп атаймыз.

Тўжырымдар алгебрасыныѕ кез келген формуласы їшін тепе-теѕ тїрлендірулер кґмегімен оныѕ ДНФ немесе КНФ алуєа болады, бўл формалар жалєыз болмайды.

Аныќтама 4 Егер дизъюнктивті нормал формадаєы ќарапайым конъюнкцияныѕ ќўрамына јрбір ќарапайым тўжырымныѕ ґзі немесе кері шамасы міндетті тїрде енетін болса, формуланы  жетілдірілген дизъюнктивті нормал форма (ЖДНФ) деп атаймыз.

Аныќтама 5 Егер конъюнктивті нормал формадаєы ќарапайым дизъюнкцияныѕ ќўрамына јрбір ќарапайым тўжырымныѕ ґзі немесе кері шамасы міндетті тїрде енетін болса, формуланы  жетілдірілген конъюнктивті нормал форма (ЖКНФ) деп атаймыз.

Мысал 2. А(x,y,z)= xyzÚØxy – дизъюнктивті нормал форма;

B(x,y,z)= (ØxÚyÚz)( yÚz)( xÚØz) – конъюнктивті нормал форма;

C(x,y,z)= xyzÚØxyz – жетілдірілген дизъюнктивті нормал форма;

D(x,y,z)= (ØxÚyÚz)( xÚyÚz)( xÚyÚØz) – жетілдірілген конъюнктивті нормал форма.

Теорем 1 Тўжырымдар алгебрасыныѕ кез келген формуласыныѕ оєан пара-пар ДНФ жјне КНФ бар.

Теорема 2 Тўжырымдар алгебрасыныѕ кез келген тепе-теѕ жалєан емес формуласыныѕ  бірмјнді ЖДНФ тїрінде ґрнектелуі бар.

Теорема 3 Тўжырымдар алгебрасыныѕ кез келген тепе-теѕ аќиќат емес формуласыныѕ  бірмјнді ЖКНФ тїрінде ґрнектелуі бар.

 

1.13 Формулаларды аќиќаттыќ мјндер кестесі бойынша ќалпына келтіру

 

Есеп. А(x,y,z) формуласыныѕ аќиќаттыќ кестесі берілсін.

 

х

у

z

А(x,y,z)

1

1

1

1

1

1

0

0

1

0

1

0

0

1

1

1

1

0

0

1

0

1

0

0

0

0

1

0

0

0

0

0

 

 

 

 

 

 

 

 

 

 

 

Формуланыѕ аќиќаттыќ кестесі бойынша оныѕ ґзін аныќтайыќ. Берілген формула ќарпайым тўжырымдардыѕ 1, 4, 5 жолдардаєы їлестірулерінде аќиќат мјн ќабылдайды. Конъюнкцияныѕ аќиќаттыќ кестесін пайдаланып, осы жолдардан ќарапайым конъюнкция ќўрайыќ.

Бірінші жолдаєы мјндерде  xyz аќиќат,

Тґртінші жолдаєы мјндерде Øxyz аќиќат,

Бесінші жолдаєы мјндерде xØyØz аќиќат.

Енді, осы ќарапайым конъюнкциялардан жетілдірілген нормал дизъюнктивті форма ќўрайыќ:

хyz Ú Øxyz Ú xØyØz.

Бўл формуланыѕ аќиќаттыќ кестесініѕ  А(x,y,z) формуласыныѕ аќиќаттыќ кестесімен сјйкес келетіндігін тексеру ќиын емес. Себебі, басќа жолдардаєы ќарапайым тўжырымдардыѕ мјндерініѕ їлестірулерінде жоєарыдаєы ќарапайым конъюнкциялардыѕ јрќайсысы жалєан мјн ќабылдайды.

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

Демек, тепе-теѕ жалєан емес формуланы жетілдірілген нормал дизъюнктивті формаєа келтіру їшін оныѕ аќиќаттыќ кестесіндегі аќиќат мјндерге сјйкес келетін жолдардан ќарапайым конъюнкциялар ќўру ќажет. Бўл ќарапайым конъюнкцияларда, егер ќарапайым тўжырым аќиќат мјн ќабылдаса, онда оныѕ ґзін, ал жалєан мјн ќабылдаса, онда оныѕ кері шамасын аламыз. ЖКНФ ќўру алгоритмін келтірейік.

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

Мјселен, жоєарыда ќарастырылєан формуланыѕ ЖКНФ келесі тїрде болады:

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

1.14 Логикалыќ байланыстардыѕ толыќ жїйелері

 

D1, D2, …, Dn логикалыќ амалдардыѕ символдары болсын. Егер тўжырымдар алгебрасыныѕ кез келген формуласы їшін оєан пара-пар D1, D2, …, Dn  амалдарыныѕ кґмегімен ќўрылєан формула бар болса, онда <D1, D2, …, Dn> жїйе толыќ деп аталады.

Тўжырымдар алгебрасыныѕ кез келген формуласы їшін оєан пара-пар ДНФ жјне КНФ болєандыќтан, <Ø, Ù, Ú > – толыќ жїйе екендігі тїсінікті.

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

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

толыќ жїйе ќўрайды.

Лемма 9.2 <Ù, Ú, ® >,  <Ø > жиындары логикалыќ амалдардыѕ толыќ жїйесін ќўрмайды.