22.Пренексті нормаланған форма туралы теорема.

а)Пренексті нормаланған форма. Анықтама және мысалдар.

в) Пренексті нормаланған форма туралы теорема.

Аныктама. Егер \|/ кванторсыз формула болса, онда Q.€ {Ɏ,Ȩ} (i = 1, т) кванторлары ушин φ= Q₁x₁ – Q ₁х₁ \|/ туріндегі формуланы npeнeкcmi нормаланган форма (ПНФ) деп атаймыз. Егер ПНФ- дагы кванторлардың барлығы Ɏ (Ȩ) болып келсе, ондай формуланы Ɏ -формула (Ȩ -формула) немесе универсалды (экзистенсиалды) формула деп атаймыз.

Мысалы, Ȩ v Ɏ y(Q²(x,y)—>¬P¹(х)) формуласы пренексі норма­ланган формада тұр, ал пренексті нормаланған формада турған Ɏ v Ɏ y(P¹(x)}˄¬Q²(x,y) ˄ P¹(z)) формуласы универсалды формула да, Ȩ x Ȩ y(Q²(x,y) —> (P¹(v) ˄¬ P¹(x)) формулаеы экзистенциалды формула болады.

Теорема 5.7 (пренексті нормаланған форма туралы): Кез келген формула ушін осы формулаға эквивалентті пренексті нормаланған форма табылады.

Дәлелдеуі: Бул теореманы да логикалык амалдар мен кванторлар саны бойынша индукцияны колданып дәлелдейміз. п = п (φ) саны φ формуласындағы барлық логикалык амалдар мен кванторлар санын білдірсін.

1) п = 0 болғанда, φ кванторсыз формула, сондықтан оның өзi пренексті нормаланган форма болады.

2) Кез келген к< п = п (φ) ушін теореманың тұжырымы орындалсын деп есептейік те, теореманы φ формуласында п квантор болған жағдайда дәлелдейміз. φ формуласы төмендегі үш жағдайдың бірінде тұр деп есептесек жеткілікті.

а) φ = ¬\(/.

Бұл жағдайда п (\|/) = п (φ) = п-1<п болгандықтан, \|/ формуласы ушин теореманың тұжырымы орындалады, яғни кванторсыз ʘ формуласы табылып, \|/ = Q₁x₁... Q ₁х _sʘ (x₁ ..., x_s) болса, онда

φ =¬ \|/ =¬ Q₁x₁... Q ₁х _sʘ(x₁ ..., x_s) = ¬ Q₁x₁... Q ₁х _sʘ(x₁ ..., x_s) = | Q'₁ = Ɏ, егер Q₁ = Ȩ, Q'₁ = Ɏ | = Q'₁ x₁... Q'₁х _s¬ʘ(x₁ ..., x_s).

Демек φ формуласы пренексті нормаланған түрге келтірілді. Сонымен бұл жағдай ушин теорема тужырымы дұрыс.

б) φ = \|/ ˄ʘ. Ендеше п (φ) = п (ʘ) + п (\|/)+ 1. Онда п (\|/) және п (ʘ) сандары п (φ) = п санынан кіші болады. Демек \|/ жэне ʘ формулалары үшін , индукцияның жоруы бойынша теореманың тұжырымы дұрыс, яғни кванторсыз \|/ ₁ және ʘ₁ формулалары табылып,

\|/ = Q₁x₁... Q ₁х _s\|/ (x₁ ..., x₁), ʘ Q₁x₁... Q _kх _k ʘ (x₁ ..., x_k), мұндағы Q _iQ j€{ Ɏ ,Ȩ } болады. Онда ф ~Q ¹ x₁ … Q ¹ x₁ \|/ ₁(x₁ ..., x₁) ˄ Q ² x₁ … Q ² x₁ ʘ ₁(x₁ ..., x₁).

Бұл теңдіктің оң жағына 3°, 4° эквивaлeнттiлiктepiн бірнеше рет

колдансак, ф ~Q ¹ x₁ … Q ^s x_s( \|/ ₁(x₁ ..., x₁) ˄ ʘ ₁(x₁ ..., x₁)) болатынын

кореміз. Яғни ф формуласы ПНФ-га эквивалентті.

с) ф = Ɏ v\|/(v) жагдайында \|/ формуласы индукция жоруы бойынша пренексті нормаланған форма ʘ формуласы табылады және \|/~ ʘ. Онда

ф ~ Ɏ v ʘ. Ал бул эквиваленттіліктің оң жағы пренексті нормаланган форма. Теорема дәлелденді.

23. А)Тьюринг машыналарының программалары. 1936 жылы Тюринг кез келген есептеуді орындай алады деген жорамалмен теориялық машиналар класын енгізді. Олардың сипаттамасын берейік. Көз алдымызға квадратттарға бөлінген ақырлы лентаны елестетейік. Машинаның алфавиті болып аталатын   символдары беріледі. Әр кезде әр квадратқа бір символ жазылады. Әр кезде квадратта бір символдан артық болмайды. Машинаның іùкі жағдайлары болып табылатын   жиыны болады. Әр кезде машина сол ішкі жағдайлардың біреуінде ғана болады. Сонымен бірге кез келген уақытта квадраттардың біреуін ғана қарастыратын оқу тетігі бар. Машина бір мезетте бір ғана қимыл істейді. Егер машинаның оқу тетігі қарастырылып тұрған квадратта   символы тұрса, ал машинаның ішкі жағдайы   болса, онда ол келесі қимылдардың біреуін істейді: 1.    Осы квадраттағы   символын өшіріп,   символын осы квадратқа жазады; 2.    Оң жақтағы көрші квадратқа көшеді; 3.    Сол жақтағы көрші квадратқа көшеді; 4.    Тоқтайды. Алдыңғы үш жағдайда машина басқа   ішкі жағдайға көшіп, келесі қимылға дайын. Екінші немесе үшінші қимыл кезінде көрші квадрат жоқ болса, онда керек квадрат пайда болады деп есептейміз. Бос клеткада   символы бар деп есептейік. Онда кез келген уақытта кез келген клеткада символ бар. Алдыңғы үш қимылды болашақта бұйрық деп атайтын келесі реттелген төрттіктермен белгілеуге болады:  (1)  , (2)  ,  (3)  .  Бұл жерде алдыңғы екі символ - машинаның ішкі жағдайы мен қарастырылып отырған квадраттағы символ, үшіншісі - қандай символ жазылатындығының немесе оқу тетігінің не солға не оңға жылжуының белгісі, ал төртіншісі қандай ішкі жағдайға көшетінін көрсетеді.  Сонымен енді біз кез келген Тьюринг машинасы мен осы машинаның алфавитінде құрылған алгоритмді байланыстыра аламыз. Осы алфавиттегі кез келген сөзді солдан оңға қарай жазамыз. Оқу тетігі ең сол шеткі квадратты қарастырып тұрған кезде машина   ішкі жағдайында жұмысты бастайды. Әр қадамда не символ өшіріп, басқа символ жазады, не көрші квадраттардың біріне көшеді. Егер машина жұмысын тоқтатса, онда лентадағы сөз алгоритмнің нәтижесі болып есептеледі. Енді Тьюpинг машинасының дәл анықтамасын берейік. Келесі екі шартты қанағаттандыратын ақырлы төрттіктер жиынын Тьюринг машинасы деп атаймыз: 1. Төрттіктердің кез келгені не  , не   не   түрінде болады. 2. Алдыңғы екі символдары бірдей болатын төрттіктер жоқ. Әр төрттік бұйрық деп аталады. Бұйрықтарға енетін   символдары сытрқы  жағдайлар деп аталады. Бұйрықтардағы   символдары ішкі жағдайлар деп аталады.   кез келген машинаның ішкі жағдайы болып табылады.  Егер Р - бос болуы мүмкін, ал Q бос емес сөз болса және  - машинаның ішкі жағдайы болса, онда  машинаның конфигурациясы деп аталады. Егер келесі шарттардың біреуі орындалса, онда машина  конфигурациясын  конфигурациясына көшіреді дейміз: 1)     конфигурациясы   түрінде,  конфигурациясы   түрінде, ал  - машинаның бұйрықтарының біреуі; 2)     -  түрінде,  -  түрінде, ал  - машинаның бұйрықтарының біреуі; 3)     -  түрінде,  -  түрінде және  - машинаның бұйрықтарының біреуі; 4)     -  түрінде,  -  түрінде және  - машинаның бұйрықтарының біреуі; 5)     -  түрінде,  -  түрінде және  - машинаның бұйрықтарының біреуі. Егер  -ден басталатын бұйрық болмаса, онда машина   конфигурациясында тоқтайды деп атаймыз. Егер  конфигурациясына енетін ішкі жағдай  болса, кез келген 0  і  m-1 шартын қанағаттандыратын і үшін машина   конфигурациясын   конфигурациясына көшірсе, ал   конфигурациясында тоқтаса, онда ақырлы   конфигурациялар тізбегі машинаның есептеуі деп аталады. Және    есептеуі  -ден басталып,  -мен аяқталады дейміз. Т машинаның   алгоритмін келесі түрде анықтаймыз:  (Р) = Q орындалуы үшін   конфигурациясынан басталып,  =Q теңдігі орындалатын   конфигурациясымен аяқталуы керек. Ескерту.   сөздеріндегі   символдарын ескермейміз. Себебі барлық уақытта бұл символ бос квадратты білдіреді. Енді натурал сандарға қолданылатын алгоритмдерге көшейік. Кез келген натурал m санына m+1 - бірліктен тұратын тізбекті сәйкес қоямыз және оны   деп белгілейміз. Мысалы, 2-ге 111, 5-ке 111111. Егер кез келген  сандары үшін   =   теңдігі орындалса, онда Тьюринг машинасы жартылай анықталған арифметикалық ( ) функциясын есептейді дейміз.  Берілген функцияны есептейтін Тьюринг машинасы табылса, ол функция Тьюринг бойынша есептеледі деп аталады.  Кез келген Тьюринг машинасын кез келген n саннан тұратын тізбекке пайдалануға болады. Берілген (х) функциясын есептейтін Тьюринг машинасына екі сан берсек, ол машина басқа функцияны есептейді.

В)Транспозициялау программасы. Тьюринг машиналарының программасы.