Диссертация (1104034), страница 6
Текст из файла (страница 6)
Î÷åâèäíî,÷òî çà âðåìÿ O(|ϕ|) ìû ìîæåì íàéòè çàìêíóòóþ GLPn -ôîðìóëó ϕ0 òàêóþ, ÷òîGLP ` ϕ ↔ ϕ0 ,â ϕ0 èñïîëüçóþòñÿ òîëüêî ñâÿçêè ∧, ¬, [0], . . . , [n] è |ϕ0 | = O(|ϕ|). Äëÿâñÿêîé ïîäôîðìóëû ψ ôîðìóëû ϕ0 ìû íàéäåì êîä c(ψ) ∈ Cnωn+1 òàêîé,÷òî evnωn+1 (c(ψ)) = {w ∈ Uωnn+1 | Uωnn+1 , w ψ}.
Äëÿ ýòîãî ìû ðàññìàòðè-âàåì âñå ïîäôîðìóëû ôîðìóëû ϕ0 â òàêîì ïîðÿäêå, ÷òî âñÿêàÿ ôîðìóëàψ ðàññìàòðèâàåòñÿ ïîñëå âñåõ åå òî÷íûõ ïîäôîðìóë ψ 0 . Åñëè ψ ýòî ⊥,òî ïîëîæèì c(ψ) = EmpSn (ωn+1 ). Åñëè ψ èìååò âèä ¬ψ 0 äëÿ íåêîòîðîãîψ 0 , òî ïîëîæèì c(ψ) = Cmpln (ωn+1 , c(ψ 0 )). Åñëè ψ èìååò âèä [k]ψ 0 äëÿíåêîòîðûõ ψ 0 è k, òî ïîëîæèìc(ψ) = Cmpln (ωn+1 , Rk -Invn (ωn+1 , Cmpln (ωn+1 , c(ψ 0 )))). Åñëè ψ èìååò âèä ψ 0 ∧ ψ 00 äëÿ íåêîòîðûõ ψ 0 è ψ 00 , òî ïîëîæèìc(ψ) = Intrn (ωn+1 , c(ψ 0 ), c(ψ 00 )). Ìû ëåãêî äîêàçûâàåì èíäóêöèåé ïîäëèíå ïîäôîðìóë ψ , ÷òîwωnn+1 (c(ψ)) ≤ |ψ| èocnωn+1 (c(ψ)) ≤ n|ψ|.34Ðàññìîòðåíèåì ñëó÷àåâ äëÿ âíåøíåé ñâÿçêè ψ ìû ïîêàçûâàåì, ÷òî âû÷èñëåíèå c(ψ) èç êîäîâ ðàíåå ðàññìîòðåííûõ ôîðìóë çàíèìàåò âðåìÿO(|ϕ0 | · |ϕ0 |n+1 ).
Ïîëíîå âû÷èñëåíèå c(ϕ0 ) çàíèìàåò O(|ϕ0 |n+3 ) âðåìåíè.Î÷åâèäíî, ÷òî GLP ` ϕ òîãäà è òîëüêî òîãäà, êîãäàIsEmpn (ωn+1 , Cmpln (ωn+1 , c(ϕ0 ))) = 1.Òåì ñàìûì, ìû ïîëó÷àåì òðåáóåìûé àëãîðèòì ñî âðåìåíåì ðàáîòûO(|ϕ|n+3 ).35Ãëàâà 2Ýëåìåíòàðíûå òåîðèè ïîëóðåøåòîêGLP-ñëîâ2.1GLP-ñëîâà ýòîì ðàçäåëå ìû îïðåäåëÿåì ïîíÿòèå GLP-ñëîâà è èçó÷àåì íåêîòîðûåñâîéñòâà GLP-ñëîâ, êîòîðûå ìû â äàëüíåéøåì áóäåì èñïîëüçîâàòü äëÿïîëó÷åíèÿ ðåçóëüòàòîâ î ðàçðåøèìîñòè è íåðàçðåøèìîñòè ýëåìåíòàðíûõ òåîðèé ñòðóêòóð, îïðåäåëÿåìûõ íà îñíîâå GLP-ñëîâ.ÌûðàññìàòðèâàåììíîæåñòâîWâñåõôîðìóëâèäàhn1 ihn2 i . . .
hnk i>. Òàêèå ôîðìóëû íàçûâàþòñÿ GLP-ñëîâàìè; òàêæå äëÿ êðàòêîñòè â ðàìêàõ äàííîé äèññåðòàöèè ìû íàçûâàåì èõ ïðîñòîñëîâàìè. Äëÿ îáîçíà÷åíèÿ ñëîâ ìû èñïîëüçóåì áóêâû A, B, . . ..Èç ñîîáðàæåíèé óäîáñòâà ìû ÷àñòî áóäåì îïóñêàòü çíàêè ìîäàëüíîñòåé è >, çàïèñûâàÿ ñëîâî hn1 ihn2 i . . . hnk i> êàê n1 n2 . . . nk . Äëÿñëîâ A = n1 n2 . . . nk è B = m1 m2 .
. . ml çàïèñü AB îçíà÷àåò ñëîâîn1 n2 . . . nk m1 m2 . . . ml . ×åðåç Wn ìû îáîçíà÷àåì ìíîæåñòâî âñåõ ñëîâm1 m2 . . . ml , äëÿ êîòîðûõ âñå mi ≤ n.Íà ìíîæåñòâå âñåõ GLP-ôîðìóë èìåþòñÿ áèíàðíûå îòíîøåíèÿ<n , îïðåäåëÿåìûå ñëåäóþùèì îáðàçîì (ñì. [7]):defϕ <n ψ ⇐⇒ GLP ` ψ → hniϕ.Îáîçíà÷èì ÷åðåç Sn ìíîæåñòâî âñåõ ñëîâ, ëþáîé ñèìâîë êîòîðûõ36áîëüøå èëè ðàâåí n. Ìû îáîçíà÷àåì ÷åðåç ∼ îòíîøåíèå GLP-äîêàçóåìîéýêâèâàëåíòíîñòè íà ôîðìóëàõ è, â ÷àñòíîñòè, íà ñëîâàõ:defϕ ∼ ψ ⇐⇒ GLP ` ϕ ↔ ψ.Îòìåòèì, ÷òî âñÿêîå íåïóñòîå ñëîâî A ∈ Sk ìîæåò áûòü åäèíñòâåííûì îáðàçîì ïðåäñòàâëåíî â âèäå A = A1 kA2 k .
. . kAn , ãäå Ai ∈ Sk+1 .Ôóíêöèè on : Sn → On îäíîâðåìåííî îïðåäåëÿþòñÿ ñëåäóþùèìèðåêóððåíòíûìè ñîîòíîøåíèÿìè:• on (nk ) = k;• on (A1 nA2 n . . . nAk ) = ω on+1 (A1 ) + ω on+1 (A2 ) + · · · + ω on+1 (Ak ) , ãäå k ≥ 1,A1 , . . . , Ak ∈ Sn+1 è äëÿ íåêîòîðîãî i ñëîâî Ai 6= >.Íåòðóäíî âèäåòü, ÷òî â ñèëó òåîðåìû Êàíòîðà î íîðìàëüíîé ôîðìå îðäèíàëîâ, êàæäîå îòîáðàæåíèå on ÿâëÿåòñÿ ñþðúåêöèåé íà îðäèíàë ε0 .Ñ ïîìîùüþ ëåììû 15 ñëåäñòâèå 7 èç [8] ìû ïîëó÷àåì ñëåäóþùååïðåäëîæåíèå.Ïðåäëîæåíèå 2.1.Äëÿ âñÿêîãî n è ñëîâ A, B ∈ Sn , ìû èìååìA ∼ B ⇐⇒ on (A) = on (B),A <n B ⇐⇒ on (A) < on (B).Ìû â äàííîé äèññåðòàöèè èñïîëüçóåì îïðåäåëåíèå îðäèíàëîâ ïîôîí Íåéìàíó è ñîîòâåòñòâåííîα = {β ∈ On | β < α}.Òåì ñàìûì êàæäàÿ on çàäàåò èçîìîðôèçì (Sn /∼; <n ) è óïîðÿäî÷åííîãîìíîæåñòâà (ε0 ; <).
Òàêæå, îòñþäà íåñëîæíî âèäåòü, ÷òî äëÿ k, l ≤ nîãðàíè÷åíèÿ áèíàðíûõ îòíîøåíèé <k è <l íà ìíîæåñòâî Sn ñîâïàäàþò.Îïðåäåëèì ìíîæåñòâî NF âñåõ ñëîâ, íàõîäÿùèõñÿ â íîðìàëüíîéôîðìå. Çàäàäèì ïðèíàäëåæíîñòü ñëîâ ê NF èíäóêöèåé ïî äëèíå.1. > ∈ NF.372. Ïóñòü ìèíèìàëüíûé ñèìâîë ñëîâà A6= > ðàâåí k è A =A1 kA2 k . . .
kAn , ãäå âñå Ai ∈ Sk+1 . Òîãäà A ∈ NF, åñëè è òîëüêî åñëè A1 , . . . , An ∈ NF è Ai+1 <6 k+1 Ai ïðè i îò 1 äî n − 1.Äëÿ êàæäîãî ñëîâà A ñëîâî B ∈ NF íàçûâàåòñÿ íîðìàëüíîé ôîð-ìîé ñëîâà A, åñëè B ∼ A.Ïðåäëîæåíèå 2.2.[8, ñëåäñòâèå 5] Äëÿ êàæäîãî ñëîâà A ñóùåñòâóåòåäèíñòâåííîå ýêâèâàëåíòíîå åìó ñëîâî B ∈ NF.Ïðèâåäåì çäåñü áåç äîêàçàòåëüñòâà ïðîöåäóðó ïðèâåäåíèÿ ñëîâà ê íîðìàëüíîé ôîðìå, êîòîðàÿ ÿâëÿåòñÿ íåçíà÷èòåëüíî ïåðåñòðîåííîé ïðîöåäóðîé èç äîêàçàòåëüñòâà [8, ïðåäëîæåíèå 3]. Áóäåì ñâîäèòüïîñòðîåíèå íîðìàëüíîé ôîðìû ñëîâà ê ïîñòðîåíèþ íîðìàëüíûõ ôîðìñëîâ ìåíüøåé äëèíû.
Ïóñòîå ñëîâî óæå ïðèâåäåíî ê íîðìàëüíîé ôîðìå. Ïåðåéäåì ê ñëó÷àþ íåïóñòîãî ñëîâà A. Ïóñòü ìèíèìàëüíûé ñèìâîëñëîâà A ðàâåí k è îíî èìååò âèä A = A1 k . . . kAn , ãäå A1 , . . . , An ∈ Sk+1 .Ïðèâåäåì ñëîâà A1 è A2 k . . . kAn ê íîðìàëüíîé ôîðìå ýòî áóäóò ñëîâà B1 è B2 k . . . kBm ñîîòâåòñòâåííî, ãäå B1 , .
. . , Bm ∈ Sk+1 . ÏîëîæèìA = {s | 2 ≤ s ≤ m, Bs 6<k+1 B1 }. Åñëè ìíîæåñòâî A íåïóñòî, òî íîðìàëüíàÿ ôîðìà A ðàâíà B1 kBl k . . . kBm , ãäå l = min(A), èíà÷å íîðìàëüíàÿ ôîðìà A ðàâíà B1 .Èñïîëüçóÿ ýòî àëãîðèòì ìû íåïîñðåäñòâåííî ïîëó÷àåì ñëåäóþùóþ ëåììó.Ëåììà 2.3.Åñëè ñëîâî ïðèíàäëåæèò Sk , òî è åãî íîðìàëüíàÿ ôîðìàïðèíàäëåæèò Sk .Îïðåäåëèì ôóíêöèþ t : W → (N ∪ {−1}), ïåðåâîäÿùóþ ñëîâî âåãî ïåðâûé ñèìâîë:1. t(>) = −1;2. t(k1 . . . kn ) = k1 .Ëåììà 2.4.[8, ëåììà 1] Ïóñòü ñëîâà A è B òàêîâû, ÷òî A ∈ Sk èt(B) < k. Òîãäà GLP ` A ∧ B ↔ AB.38Îáîçíà÷èì ÷åðåç Bn ìíîæåñòâî {nA | A ∈ Sn } ∪ {>}.Ëåììà 2.5.Ïóñòü A ∈ Bk , B ∈ Sk è A <k B.
Òîãäà GLP ` B → A.Äîêàçàòåëüñòâî. Ìû èìååì GLP ` B → hkiA. Èñêîìîå ìû ïîëó÷àåìâ ñèëó òîãî, ÷òî â GLP äëÿ ëþáîé ϕ äîêàçóåìà ôîðìóëà hkihkiϕ →hkiϕ.Òàê êàê ñèëó ëåììû 2.1 âñÿêèå äâà ñëîâà èç Sk ëèáî ýêâèâàëåíòíû,ëèáî îäíî <k -áîëüøå äðóãîãî, èìååò ìåñòî ñëåäñòâèå 2.6.Ñëåäñòâèå 2.6.Ïóñòü A, B ∈ Bk . Òîãäà ëèáî GLP ` A → B, ëèáîGLP ` B → A. Êðîìå òîãî, A <k B âëå÷åò GLP ` B → A.Ñëåäñòâèå 2.7.Ïóñòü äàíû ñëîâà A ∈ Sk è B òàêèå, ÷òî t(B) ≤ k èB <0 A.
Òîãäà GLP ` A → B.Äîêàçàòåëüñòâî. Èñïîëüçóÿ ëåììó 2.4 ìû ïîëó÷àåì ñëîâà B0 ∈ B0 ,B1 ∈ B1 , . . ., Bk ∈ Bk òàêèå, ÷òîGLP ` B ↔ B0 ∧ . . . ∧ Bkè âñå Bi , êàê ñëîâà â àëôàâèòå èç íàòóðàëüíûõ ÷èñåë, ÿâëÿþòñÿ ïîäñëîâàìè B îò ïåðâîãî âõîæäåíèÿ i, âêëþ÷èòåëüíî, äî ïåðâîãî âõîæäåíèÿi − 1, íå âêëþ÷àÿ åãî (äî ïðàâîãî êîíöà äëÿ i = 0). Èç îïðåäåëåíèÿ o0âèäíî, ÷òî äëÿ âñåõ i ≤ k ìû èìååì o0 (Bi ) ≤ o0 (B). Òåì ñàìûì äëÿ âñåõi ≤ k Bi <0 A, à â ñèëó ñîãëàñîâàííîñòè <0 è <i íà Si ìû èìååì Bi <i A.Îòñþäà GLP ` A → Bi äëÿ âñåõ i ≤ k.
Ñëåäîâàòåëüíî GLP ` A → B.Ìûîáîçíà÷àåì÷åðåçWn ,ìíîæåñòâîâñåõñëîâA=hm1 ihm2 i . . . hmk i> äëÿ êîòîðûõ âñå mi ≤ n. Äëÿ âñåõ îðäèíàëîâ α ≤ ωîáîçíà÷èì ÷åðåç WNα ìíîæåñòâî Wα ∩ NF.Íåñëîæíàÿ ïðîâåðêà ïîêàçûâàåò, ÷òî äîêàçàòåëüñòâî ëåììû 9 èç[8] äàåò ñëåäóþùóþ ëåììó.Ëåììà 2.8.Ïóñòü äàíû îðäèíàë α ≤ ω ÷èñëî k ≤ α. Òîãäà äëÿ ëþáûõNñëîâ A, B ∈ Sk ∩ WNα ýôôåêòèâíî ñòðîèòñÿ ñëîâî C ∈ Sk ∩ Wα òàêîå,÷òî GLP ` A ∧ B ↔ C.39Ââåäåì îïåðàöèþ êîíúþíêöèè ñëîâ.
Ïóñòü A è B ñëîâà, à C åäèíñòâåííîå ñëîâî èç NF òàêîå, ÷òî GLP ` A ∧ B ↔ C. ÏîëîæèìA u B = C.Êðîìå òîãî, äëÿ âñåõ íàòóðàëüíûõ k ââåäåì ôóíêöèè dk : W → W.Äëÿ âñÿêîãî ñëîâà A ìû ïîëàãàåì dk (A) ðàâíûì åäèíñòâåííîìó ñëîâó èçNF ýêâèâàëåíòíîìó hkiA.Íåñëîæíî âèäåòü, ÷òî äëÿ ëþáûõ α ≤ ω è n ≤ α, äëÿ âñÿêîãîNNA ∈ WNα ìû èìååì dn (A) ∈ Wα è äëÿ âñÿêèõ A, B ∈ Wα ìû èìååìA u B ∈ WNα.Ñâÿçêà ∧ åñòåñòâåííûì îáðàçîì çàäàåò ôóíêöèþ íà êëàññàõ ýêâèâàëåíòíîñòè ñëîâ:[A]∼ ∧ [B]∼ = {C | C ∼ A ∧ B}.Àíàëîãè÷íî, ñâÿçêè hni çàäàþò ôóíêöèè íà êëàññàõ ýêâèâàëåíòíîñòèñëîâ:hni[A]∼ = {B | B ∼ hniA}.Îòìåòèì, ÷òî åñëè äàíû ñëîâà A, B ∈ Wn òàêèå, ÷òî äëÿ âñÿêîãîñëîâà B, åñëè B ∼ A, òî B ∈ Wn .
Òåì ñàìûì Wn /∼ ⊂ W/∼. Êðîìå òîãî,î÷åâèäíî, Wn /∼ çàìêíóòî îòíîñèòåëüíî h0i, h1i, . . . , hni è ∧.Êàê íåñëîæíî âèäåòü, ìîäåëü (WN ; <0 , >, u, d0 , d1 , . . . , dn , . . .)èçîìîðôíà ìîäåëè (W/∼; <0 , >, ∧, h0i, h1i, . . . , hni, . . .). Àíàëîãè÷íî,ïðè âñåõ n ìîäåëü (WNn ; <0 , >, u, d0 , d1 , . . . , dn ) èçîìîðôíà ìîäåëè(Wn /∼; <0 , >, ∧, h0i, h1i, . . . , hni).
Èç òåõíè÷åñêèõ ñîîáðàæåíèé ìû â îñíîâíîì èñïîëüçóåì ñòðóêòóðû ñ íîñèòåëÿìè WN è WNn.Öåíòðàëüíûì ïðåäìåòîì íàøåãî ðàññìîòðåíèÿ â ýòîé ãëàâå áóäóòíèæíèå ïîëóðåøåòêè Sα = (WNα ; u) äëÿ α ≤ ω .2.2Íåêîòîðûå ñâîéñòâà ïîëóðåøåòîê ñëîâÄëÿ êàæäîãî k ∈ N çàäàäèì ôóíêöèþ hk : W → Sk . Çàìåòèì, ÷òî äëÿâñÿêîãî ñëîâà A ñóùåñòâóåò è åäèíñòâåííî åãî ïðåäñòàâëåíèå â âèäå A =40BC, ãäå B ∈ Sk , à t(C) < k. Ïîëîæèì hk (A) = B.Ëåììà 2.9.Äëÿ âñÿêîãî ñëîâà At(A) = min({k | hk (A) ∼ >}) − 1.(2.1)Äîêàçàòåëüñòâî.
Çàìåòèì, ÷òî hk (A) 6= > òîãäà è òîëüêî òîãäà, êîãäàk ≤ t(A). Òàêæå äëÿ âñÿêîãî B:B = > ⇐⇒ B ∼ >.Îòñþäà ìû ïîëó÷àåì òîæäåñòâî (2.1).Ëåììà 2.10.Ïóñòü ñëîâà A è B òàêîâû, ÷òî A ∼ B. Òîãäà äëÿ âñÿêîãîk âûïîëíÿåòñÿ hk (A) ∼ hk (B).Äîêàçàòåëüñòâî. Äîêàæåì, ÷òî hk (A) ∼ hk (B) èíäóêöèåé ïî k. Ïðåäïîëîæåíèå èíäóêöèè äëÿ k = 0 î÷åâèäíî âûïîëíåíî; ïåðåéäåì ê ñëó÷àþk > 0.Ïðåäïîëîæèì, ÷òî hk (A) ∼ hk (B) è äîêàæåì, ÷òî hk+1 (A) ∼hk+1 (B). Ñëîâî hk (A) èìååò âèä hk (A) = hk+1 (hk (A))kA1 kA2 k . . . kAn , ãäåA1 , . . .
, An ∈ Sk+1 . Çàìåòèì, ÷òî hk+1 (A) = hk+1 (hk (A)) è òåì ñàìûìhk (A) = hk+1 (A)kA1 k . . . kAn .Ïóñòü ñëîâî C íîðìàëüíàÿ ôîðìà ñëîâà hk (A). Ðàññìîòðèì ïîñòðîåíèå C ïî îïèñàííîé ðàíåå ïðîöåäóðå ïðèâåäåíèÿ ñëîâà ê íîðìàëüíîé ôîðìå (ñì. ñòð. 38). Ïóñòü íîðìàëüíàÿ ôîðìà A1 kA2 k . . . kAn èìååò âèä C1 kC2 k . . . kCm , ãäå âñå Ci ∈ Sk+1 , à íîðìàëüíàÿ ôîðìà hk+1 (A)ðàâíà ñëîâó C0 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
