1. p, q, r, … символдары –  1– ақиқат немесе 0 – жалған екі мәнді қабылдайтын айнымалы тұжырымдар;
2. x, y, z, … – кейбір М жиынына тиісті мәндерді қабылдайтын пәндік айнымалылар;

      x⁰, y⁰, z⁰ – пәндік тұрақтылар, яғни пәндік айнымалылардың мәндері.

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

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

P⁰(·), Q⁰(·,·, …,·) – тұрақты предикаттардың символдары.

4. Логикалық амалдардың символдары:    
5. Кванторлық амалдардың символдары:
6. Көмекші символдар: жақшалар, үтірлер.

 

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

   

1. Кез келген тұжырым (қарапайым) формула болады.
2. Егер F(·,·, …,·) – n-орынды предикатты айнымалы немесе тұрақты предикат, ал x₁, x₂,…, x_n – пәндік айнымалылар немесе пәндік тұрақтылар болса, онда F(x₁, x₂,…, x_n) – формула. Мұндай формула қарапайым деп аталады, бұл  формулада пәндік айнымалылар бос, кванторлармен байланбаған болады.
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) предикаттың мәнін бекітеміз: P⁰(x,y)= «x<y», ал х бос айнымалының мәні болсын. Онда у-тің x⁰=5 мәнінен кіші мәндерінде P⁰(x⁰,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. Е облыста анықталған ƒ(х) функцияның x₀ нүктедегі шегінің анықтамасы.: . үш орынды предикатты қолданып жазамыз:

, мұнда . 

   Мысал 2. Нүктедегі үзіліссіз функцияның анықтамасы.

Егер  , мұндағы , онда Е жиыныдағы анықталған функциясы нүктеде үзіліссіз деп аталады.

   Тесты по теме

 

1. Р(х) = «х²-4=0, хÎR» және Q(х)= «3х-2<16, хÎR» предикаттар берілген. Бұл предикаттардың ақиқаттық жиындарын табыңыз.

I_P = {2; -2}; I_Q = (-¥; 6)

I_P = {2}; I_Q = (-¥; 6)

I_P = {2}; I_Q = {1; 2; 3; 4; 5; 6} 

2. Р(х)= «х²-4=0, хÎN» және Q(х)= «3х-2<16, хÎN» предикаттар берілген. Бұл предикаттардың ақиқаттық жиындарын табыңыз.

I_P = {2}; I_Q = {1; 2; 3; 4; 5}

I_P = {2}; I_Q = {1; 2; 3; 4; 5; 6}

I_P = {2}; I_Q = (-¥; 6)

I_P = {2}; I_Q = {6} 

3. Пара-пар предикаттарды көрсетіңіз (пәндік айнымалылар R жиынына тиісті):

х² < 0  және 2^|x| = Cosx

 және

 және

 және  

4. Келесі өрнектердің қайсысы предикаттар логикасының формуласы болады?

 

5. формуладағы айнымалылардың түрін анықтаңыз:

х, z байланған, у бос

х, z бос, у байланған

х, у байланған, z бос

y, z байланған, x бос 

6. Предикаттардың қайсылары бір бірінің терістеулері болады?

«k бүтін саны тақ», «k бүтін саны жүп»

«f функциясы жұп», «f функциясы тақ»

«a<b», «a>b»

«n натурал саны – жай», «n натурал саны – құрама» 

7. Р(х,у) = «х натурал саны у натурал санына бөлінеді (қалдықсыз)». Келесі сөйлемдердің қайсысы ақиқат?

 

8. және – кез келген предикаттар болсын. Келесі формулалардың қайсысы формулаға пара-пар болады?

 

9. Р(х) = «х – жұп саны, хÎN» және Q(х)= « х 3 санына еселі, хÎN» болсын. Р(х)& Q(х) предикаттың ақиқаттық жиынын табыңыз. 

I_{Р& Q} = {6; 12; …; 6n; …}

I_{Р& Q} = {2; 3; 4; 6; …; 2n; 3n; …}

I_{Р& Q} = {1; 3; 5; …; 2n-1; …} 

10. предикаттың ақиқаттық жиынын табыңыз.

 

      VI тарау. АЛГОРИТМДЕР ТЕОРИЯСЫНЫҢ ЭлементтерІ

   4.1 Алгоритм түсінігі және оның қасиеттері

 

   Алгоритм  түсінігі негізігі математика  түсінігінің қатарына жатады. Бұл үлкен даму қатарынан өткен. Мұнда математика дамымай тұрып та таза механикалық қасиеттердің белгілі ережелерге сүйеніп, бүкіл кластың тапсырмалары есептелетін  әртүрлі есептеуіш процестері қалыптаса бастады. Алгоритм мысалдары болып мыналар табылады: