30. Қорыту.

а) Қорытудың табиғи құрылымдық ережелері.

в) Қорытуға 1-3 мысалдар

Егер ,...,формулалар тізбегінде әрбір формула аксирма немесе өзінің алдындағы формулалардың тікелей салдары болса,жоғарыдығы тізбекті предикаттар есептеуінің қорытуы д.а. соңғы формуласыболатын предикаттар есептеуінің қорытуы табылса,формуласын предикаттар есептеуінің теоремасы д.а. Белгіленуі : |-.

Тепе-теңдік заңы: |-;

Алмастыру ережесі: Г,\:Г,;

Қысқарту ережесі: Г,\:Г;

Қима ережесі:Г\:Г;

Математикалық практикада осы қорыту ережелері аты аталмай-ақ қолдана береді. Оларды табиғи қорытудың құрылымдық ережелері д.а.

Корыту мысалдары:

1-мысал: Келесі қорытудың ақиқаттығын дәлелде

∀x(P1(x)→(⌐P2(x))); ∀x(P3(x)→P(x))\ ∀x(P3(x)→(⌐P2(x));

1) F1= ∀x(P1(x)→(⌐P2(x))- себеп;

2) F2=∀x(P3(x)→P1(x))-себеп;

3)F3= ∀x(P1(t)→(⌐P2(t))-F1 формуласынан жалпылау кванторын аластау ережесі бойынша;

4)F4= ∀x(P3(t)→P1(t) – F2 формуласынан жалпылау кванторын аластау ережесі бойынша;

5)F5= ∀x(P3(t)→ ⌐P2(t)-F4 және F3 формулаларына силогизм заңын қолдану арқылы алынды;

6)F6=∀x(P3(x)→(⌐P2(x)- F5 формуласынан жалпылау кванторын енгізу ережесі бойынша;

Сонымен ∀x(P3(x)→⌐P2(x)) формуласының ақиқаттығын дәлелдедік!

31.Тъюринг машиналары. а) Тъюринг машиналарының программалары. в) Нөлді көшіру программасы.

1936 жылы Тюринг кез келген есептеуді орындай алады деген жорамалмен теориялык машиналар класын енгізді. Олардың сипаттамасын берейік.

Көз алдымызға квадратттарға бөлінген акырлы лентаны елестетейік. Машинаның алфавиті болып аталатын S₀, S₁ ..., S_n символдары беріледі. Әр кезде әр квадратқа 6ip символ жазылады. Әр кезде квадратта бip символдан артық болмайды. Машинаның ішкі жағдайлары болып табылатын {q₀,..., q_m} жиыны болады. Әр кезде машина сол ішкі жағдайлардың біреуінде ғана болады. Сонымен бipгe кез келген уақытта квадраттардың бipeyiн ғана қарастыратын оқу тетігі бар. Машина бip мезетте бip ғана қимыл істейді. Егер машинаның оқу тетігі қарастырылып тұрган квадратта S_i. символы тұрса, ал машинаның ішкі жағдайы q_j болса, онда ол келесі кимылдардың бipeyiн істейді.

Осы квадраттағы S_i символын көшіріп , S_j символын осы квадратка жазады;

Оң жактағы көрші квадратка көшеді

Сол жактағы көрші квадратка көшеді

Токтайды.

Алдыңғы үш жағдайда машина баска q_r ішкі жағдайға көшіп, келесі кимылға дайын. Екінші немесе үшінші қимыл кезінде көрші квадрат жок болса, онда керек квадрат пайда болады деп есептейміз.

Бос клеткада S₀ символы бар деп есептейік. Онда кез келген уакыт­та кез келген клеткада символ бар. Алдыңғы үш қимылды болашакта бұйрық деп атайтын келесі реттелген төрттіктермен белгілеуге болады:

(1 )q.S_tS_kq_r, (2)q.S.Lq_r, (3)q_j S_iRq_r

Бұл жерде алдыңғы eкi символ – машинаның ішкі жағдайы мен карастырылып отырған квадраттағы символ, үшіншіci - кандай символ жазылатындығының немесе оқу тетігінің не солға не оңга жылжуының белгісі, ал төртінші кандай iшкі жағдайға көшетінін көрсетеді.

Сонымен енді біз кез келген Тьюринг машинасы мен осы машинаның алфавитінде құрылған алгоритмді байланыстыра аламыз. Осы алфавиттен кез келген сөзді солдан оңға карай жазамыз. Оку тетігі ең сол шеткі квадратты карастырып тұрған кезде машина q₀ iшкі жағдайында жұмысты бастайды. Әр кадамда не символ өшіріп, басқа символ жазады, не көрші квадраттардың біріне көшеді. Егер машина жұмысын токтатса, онда лентадағы сөз алгоритмнің нәтижесі болып есептеледі. Енді Тьюринг машинасының дәл анықтамасын берейік.

Келесі екі шартты канағаттандыратын акырлы төрттіктер жиынын Тьюринг машинасы деп атаймыз:

Төрттіктердің кез келген не q_j S_i S_k q_r, не q_j S_i L q_r, не

q_j S_i R q_r түрінде болады.

Алдыңғы eкi символдары бірдей болатын төрттіктер жок.

Әр тертік бұйрык деп аталады. Бұйрықтарға енетін S_m символдары сытркы жағдайлар деп аталады. Бұйрыктардағы q_s символдары ішкі жағдайлар деп аталады. Q₀ кез келген машинаның жағдайы болып табылады.

Егер Р - бос болуы мумкін, ал Q бос емес сөз болса және q_s машинаның ішкі жағдайы болса, онда Pq_sQ машинаның конфигурациясы деп аталады. Егер келесі шарттардың бipeyi орындалса, онда машина α конфигурациясын β конфигурациясына көшеміз дейміз:

α конфигурациясы Pq_jS_i Q туршде, β конфигурациясы Pq_r S_kQ түрінде, ал q_jS_i S_kq_r - машинаның бұйрықтарының бipeyi;

2) α - PS_kq_jS_iQ түрінде, β – Pq_rS_kS_iQ түрінде, ал q_jS_iLq_r - машина­ның бұйрықтарының бipeyi;

3) α –q_jS_iQ түрінде, β – q_rS₀S_iQ түрінде және q_iS_iLq_r - машинаның бұйрыщтарының бipeyi;

α- Pq_jS_iS_kQ түрінде, β – PS_iq_k S_kQ түрінде және q_jS_iRq_r - машинаның бұйрыщтарының бipeyi;

5) α – Pq_jS_i түрінде, β – PS_iq_jS₀ түрінде және q_jS_iRq_r - машинаның бұрыщтарының бipeyi.

Егер #Д.-ден басталатын буйрык болмаса, онда машина PqS.Q конфигурациясында токтайды деп атаймыз.

φ_t (P) = Q орындалуы ушш q₀P конфигурациясынан басталы R₁ R₂ теңдігі орындалатын R₁ q_r R₂ конфигурациясымен аякталуы

керек.

Кез келген Тьюринг машинасын кез келген n саннан тұратын тізбекке пайдалануға болады. Бершген f(х) функциясын есептейтін Тьюринг машинасына екі сан берсек, ол машина баска функцияны есептейді