10 – лекция

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

 

Предикаттарды тўжырымдарєа тїрлендіретін амалдарды ќарастырайыќ. М жиынында аныќталєан Р(х) предикат берілсін. Егер “а” – М жиыныныѕ ќандай да бір элементі болса, онда Р(х) предикатта х орнына а-ны ќою берілген  предикатты Р(а) тўжырымєа айналдырады. Мўндай предикатты бірлік деп атайды. Мысалы, Р(x): “х – жўп сан” – предикат, ал Р(6) – аќиќат тўжырым, Р(3) – жалєан тўжырым.

Жоєарыда айтылєанды n – орынды предикаттарєа жалпылау мїмкін: егер барлыќ хi, i=, пјндік айнымалылардыѕ орнына олардыѕ мјндері ќойылса, онда тўжырым алынады.

Квантификация амалдарын ќарастырамыз. Бўл амалдардар да предикаттарды тўжырымдарєа айналдырады.

 

Жалпылау кванторы

 

Р(х) – W жиынында аныќталєан предикат болсын. Бўл предикатќа предикат тепе-теѕ аќиќат болєанда єана аќиќат болатын  тўжырымын сјйкестікке ќоямыз.  тўжырымы былай оќылады: “Кез келген х їшін Р(х) аќиќат ”.  тўжырымы Р(х) предикатќа х айнымалы бойынша жалпылау кванторын ілу кґмегімен алынєан деп айтады.

 символын жалпылау кванторы деп атайды. Р(х) предикатќа х айнымалы бос болып, ал  тўжырымєа – х жалпылау кванторымен байланєан болып енеді деп айтады.

 

Бар болу кванторы

 

P(x) –  W жиынында аныќталєан предикат болсын. Бўл предикатќа предикат тепе-теѕ жалєан болєанда єана жалєан болатын  тўжырымын сјйкестікке ќоямыз.  тўжырымы былай оќылады:“ P(x) аќиќат болатын х табылады”.  символын бар болу (табылу) кванторы деп атаймыз.  тўжырымы Р(х) предикатќа х айнымалы бойынша бар болу кванторын ілу кґмегімен алынєан деп айтады. х айнымалы бўл квантормен байланєан болады.

Кванторлыќ амалдарды кґп орынды предикаттарєа да ќолдануєа болады. Мысалы, W жиынында екі орынды P(x,y) предикаты берілсін. Предикаттыѕ айнымалыларына кванторларды іліп, мынадай тўжырымдарды алуєа болады:

 

3.4  Предикаттар логикасыныѕ формуласыныѕ ўєымы

 

Предикаттар логикасында келесі символдарды пайдаланамыз:

1.     p, q, r, … символдары –  1– аќиќат немесе 0 – жалєан екі мјнді ќабылдайтын айнымалы тўжырымдар;

2.      x, y, z, … – кейбір М жиынына тиісті мјндерді ќабылдайтын пјндік айнымалылар;

x0, y0, z0 – пјндік тўраќтылар, яєни пјндік айнымалылардыѕ мјндері.

3.     P(·), Q(·), F(·), … - бір орынды предикаттыќ айнымалылар;

Q(·,·,…,·), R(·,·, …,·) – n-орынды предикаттыќ айнымалыла;р

P0(·), Q0(·,·, …,·) – тўраќты предикаттардыѕ символдары.

4.    Логикалыќ амалдардыѕ символдары:     

5.    Кванторлыќ амалдардыѕ символдары:

6.     Кґмекші  символдар: жаќшалар, їтірлер.

 

Предикаттар логикасы формуласыныѕ аныќтамасы

 

1.     Кез келген тўжырым (ќарапайым) формула болады.

2.     Егер F(·,·, …,·) – n-орынды предикатты айнымалы немесе тўраќты предикат, ал x1, x2,…, xn – пјндік айнымалылар немесе пјндік тўраќтылар болса, онда F(x1, x2,…, xn) –  формула. Мўндай формула ќарапайым деп аталады, бўл  формулада пјндік айнымалылар бос, кванторлармен байланбаєан болады.

3.     Егер А жјне В – формулалар (бўл формулаларєа айнымалылар бір тїрде кіреді – бос немесе байланєан), онда  сґздер –  формулалар.

4.     Егер А – формула болса, онда  да – формула, А формуладан  формулаєа ґтуде пјндік айнымалылардыѕ ену тїрі ґзгермейді.

5.     Егер А(х) – формула (бўл формулаєа х пјндік айнымалы бос болып енеді), онда  жјне  сґздер де формулалар.

6.     1 – 5 бґлімдерде айтылєан сґздерден басќа сґздер формула болмайды.

Мысалы, егер Р(х) жјне Q(x,y) – бір орынды жјне екі орынды предикаттар, ал q, r – айнымалы тўжырымдар болса, онда келесі сґздер (ґрнектер) формулалар болады: .

Мысалы,  сґзі формула емес. Мўнда їшінші бґлімніѕ шарты бўзылєан:  формулаєа х айнымалы байланєан болып, ал  Р(х) формулаєа бос болып енеді.

Предикаттар логикасы формуласы аныќтамасынан тўжырымдар алгебрасыныѕ јрбір формуласы предикаттар логикасыныѕ формуласы болатыны тїсінікті.

 

Предикаттар логикасыныѕ формуласыныѕ мјні

 

Формуланыѕ логикалыќ мјні жайлы бўл формулаєа кіретін предикаттардыѕ М аныќталу аймаєы берілгенде єана айтуєа болады. Формуланыѕ логикалыќ мјні їш тїрлі айнымалылардыѕ мјндеріне тјуелді: 1) формулаєа енетін айнымалы тўжырымдардыѕ мјндеріне, 2) М жиынына тиісті бос пјндік айнымалылардыѕ мјндеріне, 3) предикатты айнымалылардыѕ мјндеріне.

Осы їш тїрлі айнымалылардыѕ аныќ мјндерінде предикаттар логикасыныѕ формуласы аќиќат немесе жалєан мјн ќабылдайтын тўжырым болады.

Мысал ретінде келесі формуланы ќарастырамыз:

,                                                (1)

Бўл формулада екі орынды Р(x, y) предикаты M´M  жиынында аныќталєан, мўнда  M={0,1,2,…,n,…}, яєни M´M=N´N.

 (1) формулаєа кіретін P(x,y) айнымалы предикаттыѕ їш x,y,z  пјндік айнымалыларынан екеуі – у жјне z кванторлармен байланєан, ал їшіншісі х – бос.

P(x,y) предикаттыѕ мјнін бекітеміз: P0(x,y)= «x<y», ал х бос айнымалыныѕ мјні  болсын. Онда у-тіѕ x0=5 мјнінен кіші мјндерінде P0(x0,y)  предикаты “жалєан” мјнін, ал импликация  барлыќ  їшін “аќиќат” мјнін ќабылдайды, яєни  тўжырымы аќиќат.

3.5 Предикаттар логикасыныѕ формулаларыныѕ тепе-теѕдігі

 

Аныќтама 1. Егер предикаттар логикасыныѕ А жјне В формулалары М аймаќќа тиісті айнымалыларыныѕ барлыќ мјндерінде бірдей логикалыќ мјн ќабылдаса, онда бўл формулалар М аймаќта тепе-теѕ деп айтады.

Аныќтама 2. Егер предикаттар логикасыныѕ А жјне В формулалары кез келген аймаќта тепе-теѕ болса, онда бўл формулалар тепе-теѕ деп аталады. Тїсінікті, егер тўжырымдар алгебрасыныѕ тепе-теѕдіктеріне айнымалы тўжырымдардыѕ орындарына предикаттар логикасыныѕ формулалары ќойылса, олар дўрыс болады. Біраќ, олардан басќа, предикаттар логикасыныѕ ґзініѕ тепе-теѕдіктері орынды болады. Олардыѕ негізгілерін ќарастырайыќ.

А(х) жјне В(х) – айнымалы предикаттар, ал С – айнымалы тўжырым болсын (немесе х ке тјуелді емес формула). Онда келесі тепе-теѕдіктер орынды:

1.              

2.

3.

4.

5.

6. .

7.

8.

9.

10.

11.

     12.

13.

14.

15.

 

3.6  Пренекстік нормал форма

 

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

Тўжырымдар алгебрасыныѕ жјне предикаттар логикасыныѕ тепе-теѕдіктерін пайдаланып, предикаттар логикасыныѕ кез келген формуласын нормал формаєа келтіру мїмкін.

Мысал 1.

формуланы нормал формаєа келтірейік.

Тепе-теѕ тїрлендірулерді пайдаланып, келесіні аламыз:

.

Предикаттар логикасы формулаларыныѕ арасында пренекстік (префикстік) нормал форма деп аталатын формулаларды бґліктейді. Бўл формада кванторлыќ амалдар жоќ болады немесе олар логика алгебрасы барлыќ амалдарынан кейін ќолданылады, яєни предикаттар логикасы формуласыныѕ ПНФ келесі тїрде болады:

,

мўнда  символы – немесе , ал А формуласында кванторлар жоќ.

Теорема. Предикаттар логикасыныѕ кез келген формуласын пренекстік нормал формаєа келтіру мїмкін.

 

 

3.7 Математикалыќ тўжырымдар мен аныќтамаларды предикаттар логикасыныѕ формулалары тїрінде жазу

 

Предикаттар логикасыныѕ тілі математикалыќ тўжырымдар мен аныќтамаларды жазу їшін ыѕєайлы. Ол ўєымдар арасындаєы логикалыќ байланыстарды ґрнектеу, аныќтамаларды, теоремаларды, дјлелдеулерді жазу мїмкіндігін береді. Мўндай жазылулардыѕ бірнеше мысалдарын келтірейік. Мысал 1. Е облыста аныќталєан ƒ(х) функцияныѕ x0 нїктедегі  шегініѕ аныќтамасы.: .  їш орынды предикатты ќолданып жазамыз:

, мўнда .

 

Мысал 2. Нїктедегі їзіліссіз функцияныѕ аныќтамасы.

Егер , мўндаєы , онда Е жиынындаєы аныќталєан  функциясы  нїктеде їзіліссіз деп аталады.