Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Лекция № 11. Продукциялық есептеулер модельдері, логикалық есептеулер модельдері
1930-жылдардан бастап алгоритмдер теориясының теориясының негізі қалана бастады.Оның негізін қалаушылар: К. Гедель, С. Клини, А. Тьюринг, А. Черч, Э. Пост, А. Марков, А. Колмогоров және т.б. Көптеген логикалық проблемалардың алгоритмдік шешімі болмайтыны анықталғанына қарамастан, есептеу техникасы мен техникалық кибернетикада логиканы, продукцияны қолдануға сұраныс артты.
Талдаудың қатаң әдістерін ұсына отырып, логикалық теория ойлау процестеріне сәйкес келетін салада объективті талдауға ықпал етеді.
Логикалық пікірлердің элементтеріне не ақиқат (А) не жалған (Ж) болатын пікірлер жатады.
Мұндай пікірлер қарапайы пікірлер деп аталады, логикалық байланыстырушылар арқылы олардан құрама пікірлер құралады. Логикалық байланыстырушыларға жататындар: терістеу (“емес” деп оқылады, “” деп белгіленеді), конъюнкция (“ЖӘНЕ” деп оқылады, “&” деп белгіленеді), дизъюнкция (“НЕМЕСЕ” деп оқылады, “V” деп белгіленеді), импликация (“ЕГЕР… ОНДА деп оқылады, “” деп белгіленеді). Дұрыс құрылған құрама пікірлер формулалар (пропозициональды) деп аталады. Формулалардың синтаксисі:
<формула > :: = А | Ж |
<пропозиц. айнымалы > | ( <формула>) |
(<формула>&<формула>)|
(<формула>V<формула>)|
(<формула> <формула>|
Формуланың ақиқаттығы мәндердің ақиқаттығымен анықталады. Пікірлер логикасында формулаларды қорытып шығару: егер қайбір формула алдын ала ақиқат болса, солардың негізінде келесі формулаларды ақиқат ретінде қорытып шығаруға болады. Осы байланысты арнайы белгімен ├ белгілейді, шығару символы деп атайды. А формуласы Н формуласынан қорытып шығарылады дегеннің жазылуы: Н ├ А.
Егер А бос жиыннан қорытылып шығарылса оның жазылуы: ├ А.
x1,.., xn айнымалылыарының қабылдайтын ақиқат мәндердің жинағы А формуласының интерпретациясы деп аталады.
Формула бір интерпретацияда ақиқат, басқа біреуінде жалған болуы мүмкін. Қандай да бір интерпретацияда ақиқат болатын формуланы орындалатын деп атайды. Барлық мүмкін интерпретацияларда жалған болатын формула тавтология немесе жалпымаңызды деп аталады. мүмкін интерпретацияларда ақиқат болатын формула орындалмайтын немесе қарама-қайшылық деп аталады.
Алфавит формулалар жиыны, аксиомалар мына үш формуланы құрайды:
А1: (а(ва));
А1: ((а(вс))((ав)(ас))):
А1: ((в а)((ва)в)).
├ А V А (Tertium non datur);
{В, ВVВ}├ C (Modus ponens);
Предикат – ақиқат не жалған мәні болатын бульдік бір аргументтен тұратын функция.
Мысалы x IBM_ өндіреді (x) бағасы аз (x, 100).
<формула>:: = <атом>
<формула>
(<формула><формула>)
<айнымалы><формула>
< айнымалы ><формула>
<атом>::=<предикат>(< терм тізімі>)
<список термов>::=<терм><терм>,< терм тізімі >
<терм>::=<константа> терм тізімі
< айнымалы >
<функтор>(< терм тізімі >)
A және A түріндегі формулалар литерал формулалар (литералдар) деп аталады.
Резолюциялар әдісін Эрбран 1930 ж ұсынды, ал ЭВМ_де Дж. Робинсон 1963 жылы жүзеге асырды. Оның негізінде «қарама қарсыдан дәлелдеу» жатыр. Бұл әдіс логикалық программалау тілдерінің негізінде жатыр. Ол не істеу керектігін көрсетпейді, тек элементтер мен олардың арасындағы байланыстарды сипаттап ,нақты мақсат қояды, ал компьютер қойылған есепті шешудің стратегиясын өзі табады.
Формальды-логикалық модельдер:
1. Мүмкін болу логикасы
2. Уақыттық логикалар
3. Динамикалық логикалар
4. Сенім мен білімнің логикасы.
Резолюциялар әдісі логикалық программалау тілінің негізі болып табылады.басты ерекшелігі программа есепті қалай шешудің жолын көрсетпейді, тек элементер мен олардың арасындағы байланыстарды сипаттайды, нақты мақсат қояды, компьютер қойылған мәселені шешу стратегиясын өзі таңдайды
Әмбебап функциялар
Әмбебап функциялар (берілген функция класында) –берілген кластан туындайтын барлық функциялар. Әмбебап функцияның мәні функцияның кешенді сипатын береді. Әмбебап функциялар көптеген теоремаларды дәлелдеудің қуатты аппараты болып табылады.
Айталық, n- жергілікті функцияның K(n) – туынды класы. Анықтама ( [Успенский,1960,с.203;Матросов,1989,с.103] бойынша). Әмбебап функциялар K(n) функция класы үшін U типті Nn+1®N жеке функциясы деп, р үшін келесі шарт орындалады.
(а) U(m,x1,...,xn)ÎK(n) кез келген m натурал сан үшін ;
(б) кез келген fÎK(n) функция үшін U (y0,x1,...,xn)=f(x1,...,xn) мәнде , y0ÎN болады.
Әмбебап функция мысалы) [Матросов,1989,с.103].
1. K(1)«{xn|nÎN} кластары үшін U(y,x)=xy функциясы әмбебап болып табылады.
2. K(2)«{x+ny|nÎN} кластары үшін U(z,x,y)=x+zy функция әмбебап болып табылады.
3. (2)«{[sin pn(x+y)]|nÎN} кластары үшін U(z,x,y)=[sin pz(x+y)] функциясы әмбебап болып табылады.
Мұнан көретініміз кез келген жұп кластар үшін әмбебап функциялар болады.
Анықтама [Верещагин,Шень,1999,с.17].
Егер берілгендер сәйкесінше дұрыс болса, екі натураль аргументті U функциясы бір аргументті есептелетін функция классы үшін әрбір n функция үшін әмбебап болып табылады делінген.
Un:x|®U(n,x) (n-да фиксирленген кездегі U функциясының "қиылысу"), есептелетін болып табылады және егер барлық есептелетін функциялар (бір аргументті) Un бар болса есептелетін болып табылады. (еске түсірсек U функциясы да, есептелетін функциялар да барлық жерде анықталған болуы міндетті емес )
Әрі қарай Тьюринга тезисін қолданамыз. [Верещагин,Шень,1999,с.17].
Бір аргументті есептелетін функциясы кластары үшін әмбебап функция болып табылатын, екі аргументті есептелетін фугкциялар бар.
Бір аргументті есептелетін функцияны p0,p1,p2,... (мысалы, олардың үзындықтарының кему реті бойынша ) есептеу тізбегі бойынша барлық бағдарламаны Тьюринг машинасына арнап жазамыз.
х аргументі үшін і-ші бағдарлама нәтижесі U(i,x) мәніне тең функция құрайық және U функциясы ізделінген есептелетін әмбебап функция екенін көрсетеміз.Біріншіден, Ui=U(i,x) функциясы pi есептелетін программамен есептелетін есептелетін функция болып табылады; екіншіден U функциясының өзін есептейтін алгоритм бар: ол бірінші аргументті екіншіге «қолданады», (мағыздылығы бойынша Тьюринг машинасы үшін интерпретатор бар)
Ескерту.Программалау термини бойынша U(p,x) –бұл қолдану нәтижесі, мысалы, Pascal-программаларында x кірісінде
Примитивтік-рекурсивтік функция класы үшін әмбебап функция
KПРФ(n) (nÎN) – барлық n- жергілікті примитивтңк-рекурсивтік функциялардың класын белгілейміз.
Ұсыныс(Р.Петер,1935) [Успенский,1960,с.204].
Кез келген натуралы n үшін KПРФ(n) классы үшін әмбебап. Жалпырекурсивтік U(n+1) функциясы бар.
Салдар (очевидное).
KПРФ(0) класы үшін әмбебап жалпырекурсивтік функция болып I1 табылады.
мысалдар (жалпырекурсивтік, бірақ примитивтік-рекурсивтік емес).
1. Мұндай функцияның бірінші мысалы Аккерман функциясы болып табылады.
2. [Успенский,1960,с.237-238] Жалпырекурсивтік функция (ол алдынғы Ұсыныста! Бойынша болады) f(x)=U(2)(x,x) примитивтік-рекурсивтік болып табылмайды. Керісінше деп алсақ, онда g(x)=f(x)+1=U(x,x)+1 функциясы ол да примитивтік-рекурсивтік болады. Осыдан кейбір k үшін келесі теңдік орындалуы керек.
U(k,x)=g(x), (1)
U(k,x)=U(x,x)+1. (1')
Бұл теңдік барлық х үшін орындалуы тиісті, сонымен қатар U және g функциялары барлық жерде анықталған. (1')-ден x=k кезінде қарама-қайшылық туындайды:
U(k,k)=U(k,k)+1.
3. [Успенский,1960,с.238] U(2) жалпы рекурсивтік функция примитивтік-рекурсивтік функция болып табылмайды. Қарсы жағдайда f(x)=U(x,x) функциясы да примитивтік-рекурсивтік болар еді.
4. [Успенский,1960,с.238-239] Функция h(x)=sg-(U(x,x)) функциясы жалпырекурситік болып табылады, бірақ примитивтік-рекурсивтік емес. Қарсы жаңдайда кейбір k кезінде және барлық х кезінде U(k,x)=h(x), (2)
U(k,x)=sg-(U(x,x)). (2') болады.
(2')-ден x=k кезде 0арама -қайшылық туындайды:
U(k,k)=sg-(U(k,k)).
5. [Успенский,1960,с.239] sg(U(x,x)) функциясы сонымен қатар жалпырекурсивтік болып табылады, бірақ примитивтік-рекурсивтік емес.
Ұсыныс [Успенский,1960,с.238].
n аргументті примитивтік-рекурсивтік функция үшін әмебеп ешқайсыдай n³1 примитивтік-рекурсивтік функция жоқ.
n=1 үшін бұл мысал 3 көрсетілген. n>1 үшін бұл ұқсас.
Жартылай рекурсивтік функциялар класына арналған әмбебап функциялар.
Осы машинамен осы машинамен есептелетін сәйкес жартылай рекурсивтік есептелетін функцияны jk(x) k Гёделдік нөмерлі Тьюринга барлық машиналарына Mk ( Mk машинасының программасында) қоямыз. Оны былай жасаймыз (әріне арнай кодтауды таңдау арқылы) [Матросов,1989,с.106-107].
Айталық, Mk машина таспасында x«(x1,...,xn) жиыны жазылған, бастапқы конфигурациясы x1Ù...Ùxn . ол келесі жағдайлардың бірінде болуы мүмкін:
(1) jk(x1,...,xn)«y,егер Mk машинасында x1Ù...Ùxn бастапқы конфигурациядан жұмысты бастап арқырғы қадам саны арқылы x1Ù...Ùxn,y конфигурацияға алып келеді;
(2) егер Mk машинасында x1Ù...Ùxn бастапқы конфигурациядан жұмысты бастап, арқырғы қадам саны тоқтатса, jk(x1,...,xn) анықталмаған, бірақ конфигурация стандартты нәтижеден жақсы;
(3) егер бастапқы конфигурациядан x1Ù...Ùxn жұмысты бастап, Mk машинасы тоқтамаса, jk(x1,...,xn) анықталмаған болады.
Кез келген nÎN үшін нәтижесінде M0,M1,...,Mk,...машинасымен анықталатын n- жергілікті функцияның шексіз тізбегін аламыз.
j0n,j1n,...,jkn,... (*)
Осылайша біз барлық n-жергілікті жеке рекурсивтік функция нөмірлерін жүзеге асырамыз.
Ұсыныс [Успенский,1960,с.249;Матросов,1989,с.107].
Кез келген nÎN\ { 0} класс үшін n-жергілікті рекурсивтік функцияның әмбебап жеке рекурсивтік функциясы бар.
Айталық, кез келген kÎN U жергілікті функцияның (n+1)-анықтайық
U(k,x1,...,xn)«jkn(x1,...,xn).
Осы анықтама және (*) тізбек құру әдісі бойынша U функциясы барлық n-жергілікті жеке рекурсивтік функцияның кластары үшін әмбебап болып табылады. U функциясы жеке рекурсивті екенін көрсетейк. Ол үшін алдымен U функциясы Тьюринг машинасынде есептелетінін көрсетеміз:
(1) айталық (y,x1,...,xn) – кез келген жиын;
(2) y саны бойынша Тьюринг машинасының ny Гёдель нөмірін анықтаймыз;
(3) ny Гёдель нөмірі бойынша бір ғана түрде My машинасына сәйкес программаны қалпына келтіреміз;
(4) применим машину к жиыны үшін My машинасын U(y,x1,...,xn)«jy(x1,...,xn) есептеу үшін қолданамыз. Осылайша U жеке рекурсивтік функция болып табылады
Қолданылған әдебиеттердің тізімі: [1]-[24]