Алгебралық тұжырымдау туралы түсінік

 

Предикаттарды тұжырымдарға түрлендіретін амалдарды қарастырайық. М жиынында анықталған Р(х) предикат берілсін. Егер “а” – М жиынының қандай да бір элементі болса, онда Р(х) предикатта х орнына а ны қою берілген  предикатты Р(а) тұжырымға айналдырады. Мұндай предикатты бірлік деп атайды. Мысалы, Р(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, … – кейбір М жиынына тиісті мәндерді қабылдайтын пәндік айнымалылар;

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 Алгоритм түсінігі және оның қасиеттері

 

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

Сандармен жұмыс жасалатын  арифметикалық әрекеттердің ережесі.

Ең үлкен ортақ бөлгішті табу ережесі.(Евклид алгоритмі).

Квадраттық түбірден құтылу ережесі.

Квадраттық түбірдің шешімін табатын ереже.

Әрбір келтірілген мысалдардың  біртекті шешім кластарымен немесе массалық проблемаларымен жұмыс істеуге тура келеді. Кластың мұндай шешімдері бір-бірімен параметрге кіретін мәндермен ажыратылады. Осылайша, квадраттық теңдеудің шешімін табуда   мынадай үш параметр қатысады және с; бұларды ауыстыра отырып бір кластың әртүрлі шешімдерін таба аламыз.

Айтылғандарға қарап  алгоритм түсінігінің келесі анықтамасын  беруімізге болады.

Алгоритм дегеніміз  бір образды және берілген массалық проблеманың кез-келген тапсырмасының дәлме-дәл шешімі. Мұндай анықтаманы қатаң деп қарауға болмайды. Шынында да, мұнда дәл мағынасы берілмеген сөздер де кездеседі. Жекелей бұл «әдіс» сөзіне қатысты. Алгоритмнің мұндай қатаң емес анықтамасы интуитивтік деп аталады.

Алгоритм түсінігінің нақты қасиеттерін қарастырайық.

1. Жалпылық – бұл алгоритмнің жеке тапсырмаға емес, бүкіл класс тапсырмаларына қолданылады.

2. Дискреттік – четкая разбивка на отдельные этапы (шаги).

3. Анықталғандық – такая организация этапов выполнения, при которой для перехода от одного этапа к другому не приходится прибегать к датчикам случайных чисел, гаданию на кофейной гуще, подбрасыванию монеты и т.п.

4. Конечность – Алгоритм қолданысындағы нақты тапсырмалардың шешімін алу үшін алгоритм қадамдарында орындалады.

 «Алгоритм дегеніміз не?», «Алгоритмнің шешілген және шешілмеген проблемалары дегеніміз не?» сұрақтары ЭВМ-мен байланысқан ХХ ғасырда және анализдің жаратылыс мүмкіндігінің актуальдылығы болып табылады. Алгоритм теориясы америкалық, ағылшындық және совет математиктерінің бірігуінен (параллельдік) туылған. Алгоритм түсінігінің мағынасын ашу үшін көптеген философиялық ойлар керек болды. Барлық кезде адам жұмыс істегенде «баспен» ойлай ма? Егер біздің бастың жұмысының жартысы машинаға өтілген болса, онда машина ойлайды деп ойлаймыз ба? Мұндай философиялық проблемалардың шешімін ХХ ғ., бірегей ұлы математиктері кибернетик Н. Винер, американдық математик Э. Пост және ағылшын математигі А. Тьюринг тапқан.