Теоремы и идеи доказательства (2012) (1133349), страница 2
Текст из файла (страница 2)
Ïîñòðîèì öåïíóþ ôóíêöèþ f ÷åòíîé äëèíû t = 2k ≥ 2n − 2 ≥ 4,000äàëåå ïîëó÷èì öåïíûå ÔÀË f , fíå÷åòíîé äëèíû 2k − 1 óäàëåíèåì ïåðâîé è ïîñëåäíåéâåðøèíû èç ÔÀË f . Òîãäà êàæäîå ðåáðî Ni , ãäå i = 2, . . . , t − 1, âõîäèò â ÄÍÔ ΣM îäíîé èçíèõ, íî íå âõîäèò â ÄÍÔ ΣM äðóãîé.  êà÷åñòâå NK âîçüìåì Nk . êà÷åñòâå f íàäî áðàòü ÔÀË äëèíû (2n − 2), ó êîòîðîé Nf èç òàêèõ íàáîðîâ, ãäå ïåðâûåi ïåðåìåííûõ ðàâíû 1, îñòàëüíûå íóëè, i ∈ [1, n] è îòðèöàíèé ê ýòèì íàáîðàì (âñåãî 2n − 1íàáîðîâ).
Åå ðåáðà, (2n − 2) øòóêè, áóäóò èìåòü âèä {aj , aj+1 }. Ëåììà. Äëÿ ôîðìóëû F, F ∈ U Φ , âûïîëíÿþòñÿ íåðàâåíñòâà R(F) = L&,∨ (F) + 1 ≤L(F) + 1 ≤ 2D(F ) , ãäå L&,∨ (F) ÷èñëî ÔÑ & è ∨ â ôîðìóëå F .èìåþùèå îáùóþ ïðîñòóþ èìïëèêàíòóÄÍÔΣMK,n ∈ N, n ≥ 3,êîòîðàÿ âõîäèò â ÄÍÔäðóãîé èç ýòèõ ÔÀË è äëÿ êîòîðîéÝòàïû äîêàçàòåëüñòâà. Âû÷èñëèòü ÷èñëî ðåáåð, âõîäÿùèõ â âåðøèíû äåðåâà è âûõîäÿ-ùèõ èç âåðøèí è ïðèðàâíÿòü èõ. Âòîðîå ñîîòíîøåíèå èíäóêöèåé (íàèáîëüøèé ðàíã áóäåòïðè ïîëíîì äåðåâå èç áèíàðíûõ îïåðàöèé, è îí áóäåòÑëåäñòâèå.
D(F) ≥ dlog(L(F) + 1)e.Òåîðåìà. Äëÿ ëþáîé ôîðìóëû F ñ ïîäíÿòûìèåé ôîðìóëàF0òàêàÿ, ÷òî2D ). îòðèöàíèÿìè èçUΦñóùåñòâóåò ïîäîáíàÿD(F 0 ) ≤ dlog(L(F) + 1)e + Alt(F).Ýòàïû äîêàçàòåëüñòâà. Ïðîâåäåì äîêàçàòåëüñòâî èíäóêöèåé ïî ðàíãó. Äëÿ òðèâèàëüíîéôîðìóëû ïðèôîðìóëàFR=1óòâåðæäåíèå âûïîëíåíî. Ïóñêàé îíî âûïîëíåíî äëÿ ðàíãàèìååò ðàíãra.è àëüòåðíèðîâàíèåêîíúþíêöèè ôîðìóë ìåíüøåãî ðàíãà, ó êîòîðûõ àëüòåðíèðîâàíèå íå áîëüøå1)}. dðàâíî ñóììå ãëóáèíûFèa − a0 .
dir − 1.ÏóñòüÏðåäñòàâèì ôîðìóëó â âèäå äèçúþíêöèè èëè ãëóáèíàFi .tP2di ≤ 2d .a0 = max{0, (a −Äëÿ êàæäîé ôîðìóëûFii=1ïîñòðîèì ïîäîáíóþ åéF̌iD(F̌i ) ≤ di + a0 . Óïîðÿäî÷èì ôîðìóëû ïî âîçðàñòàíèþäâîè÷íîå d-ÿðóñíîå äåðåâî, óäàëèâ íå èñïîëüçóåìûå ÔÑ.òàêóþ, ÷òîãëóáèíû è ïîäñòàâèì èõ â ïîëíîåÒîãäàD(F̌) ≤ d + a0 ,Ñëåäñòâèå.÷òî è òðåáîâàëîñü äîêàçàòü.Äëÿ ëþáîé ÝÊ èëè ÝÄD(K) = dlog(L(K) + 1)e,Kñóùåñòâóåò ïîäîáíàÿ ôîðìóëàK0òàêàÿ, ÷òîêîòîðàÿ ìèíèìàëüíà ïî ãëóáèíå.Ñëåäñòâèå.
Äëÿ ëþáîé ÄÍÔ èëè ÊÍÔ Uñóùåñòâóåò ôîðìóëàU 0 , ÷òî D(U 0 ) = dlog(L(U)+1) + 1e.Ëåììà.F(x1 , . . . , xn ),Ëþáóþ ôîðìóëóñèñòåìû òîæäåñòâτîñíðåàëèçóþùóþ ÔÀËf,Ýòàïû äîêàçàòåëüñòâà. Ñíà÷àëà ïðèâåñòè ôîðìóëó ñ ïîìîùüþìè îòðèöàíèÿìè. Çàòåì, èñïîëüçóÿτÏÏAK= {τ , τ , τÏÊ,τñ ïîìîùüþ ÝÏ íà îñíîâåìîæíî ïðåîáðàçîâàòü â ñîâåðøåííóþ ÎÄÍÔ ÔÀËÎÏÏ, τ },DKτ&,∨, τ&τMfîò ÁÏX(n).ê ôîðìóëå ñ ïîäíÿòû-ðàñêðûòü ñêîáêè.
Íàêîíåö, ñ ïîìîùüþτ ÏÏ ,ãäåïðèâåñòè ïîäîáíûå â 3 øàãà: ïðèâåäåíèå âñåõ ÎÝÊ â êàíîíè-÷åñêèå ÎÝÊ, óñòðàíåíèÿ ïîâòîðíûõ âõîæäåíèé ðàâíûõ ÝÊ èëè ïîäôîðìóëx ∨ x̄, ïðèâåäåíèåïîãëîùåíèé ÝÊ; ñ ïîìîùüþ òîæäåñòâà äèñòðèáóòèâíîñòè äîïîëíèòü âñå ÊÍÔ äî íåîáõîäèìãî ðàíãà. Òîæäåñòâà àññîöèàòèâíîñòè, êîììóòàòèâíîñòè è ïîäñòàíîâêè êîíñòàíò äåéñòâóþòτîñí íà äâóõ ïîñëåäíèõ øàãàõ.Òåîðåìà.Ñèñòåìàïîëíàÿ ñèñòåìà òîæäåñòâ.Ýòàïû äîêàçàòåëüñòâà. Ïóñòü äâå ôîðìóëû ýêâèâàëåíòíû.
Ìîæíî ñâåñòè îáå ê ÎÄÍÔ ñïîìîùüþ ïðåäûäóùåé ëåììû, èñïîëüçóÿ òîëüêîτîñí . Çíà÷èò, îíà ïîëíàÿ ñèñòåìà òîæäåñòâ.Ëåììà.Σ, Σ ∈ U C , ñ îäíèì âûõîäîì, âûïîëíÿþòñÿR(Σ) ≤ L&,∨ (Σ) + 1 ≤ L(Σ) + 1 ≤ 2, ãäå L&,∨ (Σ) ÷èñëî ÔÑ & è ∨ â Σ.Äëÿ ïðèâåäåííîé ÑÔÝíåðàâåíñòâàD(Σ)Ýòàïû äîêàçàòåëüñòâà. Ýòà ëåììà ïðîñòî ïåðåíîñ íà êëàññ ÑÔÝ ëåììû èç 2.Ëåììà. Äëÿ ëþáûõ íàòóðàëüíûõ n, L, D âûïîëíÿþòñÿ íåðàâåíñòâà |U Φ (L, n)| ≤ (10n)L+1 ,D||U Φ (L, n)|| ≤ (8n)L+1 , |U Φ [D, n]| ≤ (8n)2.4Ýòàïû äîêàçàòåëüñòâà.
Ñîïîñòàâëÿåì êàæäîé âíóòðåííåé âåðøèíå äåðåâà íàáîð èç(äëÿ êîíúþíêöèé è äèçúþíêöèé) èëèäóãà ñ íîìåðîìi,B1(äëÿ îòðèöàíèé) åãîi-éB2ýëåìåíò ðàâåí 1, åñëèâûõîäÿùàÿ èç âåðøèíû, íà÷èíàåòñÿ ñ ëèñòà. Êðîìå òîãî, äëÿ âåðøèí ñB 2 , ñîïîñòàâèì ñèìâîë èç íàáîðà [∨, &]. Òîãäà ïîëó÷èòñÿ 4(÷èñëî íàáîðîâ â B 2 ) ×2(ñèìâîë îïåðàöèè) + 2(÷èñëî íàáîðîâ â B 1 ) = 10 âîçìîæíûõ âàðèàíòîâ àòðèáóòà âåðøèíû. Ïîëó÷àL+1L+1åì îöåíêó (10n). Îöåíêà (8n)ïîëó÷àåòñÿ èç-çà îòîæäåñòâëåíèÿ íàáîðîâ (01) è (10) â2B , òàì, ãäå ïîëó÷àëîñü 10, ïîëó÷àåòñÿ 3 × 2 + 2 = 8. Ïîñëåäíåå ïîëó÷àåòñÿ èç ïðåäïîñëåäíåãîè ïåðâîé ëåììû â 2. Ëåììà. Äëÿ ëþáûõ íàòóðàëüíûõ n è L âûïîëíÿåòñÿ íåðàâåíñòâî ||U C (L, n)|| ≤ (8(L +L+1n)).íàáîðàìè èçÝòàïû äîêàçàòåëüñòâà.
Ïîëó÷àåòñÿ èç ïðèâåäåííîé â ïðåäûäóùåé ëåììå îöåíêè ÷èñëàäåðåâüåâ è òîãî ôàêòà, ÷òî êàæäûé ëèñò ìîæíî ïðèñîåäèíèòü ëèáî êâíóòðåííèì âåðøèíàì.Òåîðåìà.ÑÂ{τ , τ , τ }ÅñëèτnLâõîäàì, ëèáî ê êîíå÷íàÿ ïîëíàÿ ñèñòåìà òîæäåñòâ äëÿ ÝÏ ôîðìóë èç êîíå÷íàÿ ïîëíàÿ ñèñòåìà òîæäåñòâ äëÿ ÝÏ ÑÔÝ èçUÑÁ.UÁΦ ,òîÝòàïû äîêàçàòåëüñòâà. C ïîìîùüþ òîæäåñòâ ñíÿòèÿ è âåòâëåíèÿ èçáàâëÿåìñÿ îò âñåõâíóòðåííèõ âåòâëåíèé è âèñÿ÷èõ âåðøèí, ïîëó÷àåì ñõåìó, êîòîðàÿ ìîäåëèðóåò ôîðìóëó. Àäëÿ ïðåîáðàçîâàíèÿ â ôîðìóëàõ èñïîëüçóåòñÿτ. Ñëåäñòâèå. Ñèñòåìà òîæäåñòâ {τ îñí , τ  , τ Ñ } ÊÏÑÒ äëÿ ÝÏ ÑÔÝ èç U Ñ .Φ0Òåîðåìà.
Òåîðåìà ïåðåõîäà. Ïóñòü τ ÊÏÑÒ äëÿ ÝÏ ôîðìóë èç UÁ, à Π è Π ñèñòåìû00òîæäåñòâ äëÿ ïåðåõîäà îò áàçèñà Á ê áàçèñó Á è îò áàçèñà Á ê áàçèñó Á ñîîòâåòñòâåííî. Òîãäàñèñòåìà òîæäåñòâ00{Π (τ ), Π (Π)}ÿâëÿåòñÿ ÊÏÑÒ äëÿ ÝÏ ôîðìóë èçUÁΦ0 .Ýòàïû äîêàçàòåëüñòâà. Êîíñòðóêòèâíî ïîêàçàòü ïðîöåññ ïåðåâîäà â äðóãîé áàçèñ (âñåòîæäåñòâà ïåðåâîäÿòñÿ â äðóãîé áàçèñ ñ ïîìîùüþ ñèñòåìû ôîðìóë ïåðåõîäà, íà èõ îñíîâåïðîèçâîäÿòñÿ òîæäåñòâåííûå ïðåîáðàçîâàíèÿ â äðóãîì áàçèñå), ïðåîáðàçîâàíèé â íåì, ïåðåâîä îáðàòíî.Ñëåäñòâèå.Èç ñèñòåìû òîæäåñòâτ îñíäëÿ ÝÔ ôîðìóë èçUΦóêàçàííûì â òåîðåìå ñïî-ñîáîì ìîæíî ïîëó÷èòü ÊÏÑÒ äëÿ ÝÏ ôîðìóë â ëþáîì áàçèñå Á.Ëåììà.Ëþáîéπ -ñõåìå Σìîæíî ñîïîñòàâèòü ýêâèâàëåíòíóþ åé ôîðìóëóíÿòûìè îòðèöàíèÿìè òàêóþ, ÷òîR(F) = L(Σ)FèçUΦñ ïîä-è îáðàòíî.Ýòàïû äîêàçàòåëüñòâà.
Îñíîâàíî íà ìîäåëèðîâàíèè áóêâ îäíèì ðåáðîì, äèçúþíêöèè ïàðàëëåëüíûì ñîåäèíåíèåì, êîíúþíêöèè ïîñëåäîâàòåëüíûì ñîåäèíåíèåì. Ñëîæíîñòü âûñ÷èòûâàåòñÿ ïðîñòûì ñëîæåíèåì.Ëåììà.Ïðè ëþáûõ íàòóðàëüíûõLènâûïîëíÿåòñÿ íåðàâåíñòâî||U π (L, n)|| ≤ (12n)L .Ýòàïû äîêàçàòåëüñòâà.
 ñèëó ïðåäûäóùåé ëåììû, ýòî ýêâèâàëåíòíî óòâåðæäåíèþ, ÷òî÷èñëî ïîïàðíî íåýêâèàëåíòíûõ ôîðìóë ñ ïîäíÿòûìè îòðèöàíèÿìè íå áîëåå(16n)L(12 âìåñòî16 ïîëó÷àåòñÿ èç-çà òîãî, ÷òî ÷òî ìû óìíîæàåì íà 2 íå 8 (êàê â îðèãèíàëüíîé îöåíêå), à 6,ïîòîìó ÷òî íåò îòðèöàíèé). Ðàññìîòðèì ôîðìóëû îò óäâîåííîãî êîëè÷åñòâà ÁÏ, âîñïîëüçóåìñÿ òåîðåìîé îá îöåíêå êîëè÷åñòâà íåýêâèâàëåíòíûõ ôîðìóë (âòîðîé èç òðåõ), ó÷òåì ñâÿçüìåæäó ðàíãîì è äëèíîé è ïîëó÷èì íóæíóþ îöåíêó.Ëåììà.||U K (L, n)|| ≤ (8nL)L .0Ýòàïû äîêàçàòåëüñòâà. Âûäåëèòü îñòîâíîå äåðåâî D , ïîòîì ïîëó÷èòü íàääåðåâî D , ïðèñîåäåíèâ êàæäîå íå âîøåäøåå â D ðåáðî ñõåìû ê îäíîé èç ñâîèõ êîíöåâûõ âåðøèí, îòëè÷íûõ00îò âõîäà, çàòåì ïîëó÷èòü D , îðèåíòèðîâàâ ðåáðà ïî íàïðàâëåíèþ ê êîðíþ. ×èñëî òàêèõ äåLðåâüåâ íå áîëåå (8n) .
Çàìåòèì òàêæå, ÷òî ÊÑ ìîæåò áûòü ïîëó÷åíà â ðåçóëüòàòå ïðèñîåäè00íåíèÿ êàæäîãî ëèñòà äåðåâà D ê îäíîé èç åãî âåðøèí, îòëè÷íîé îò âûõîäà. Ñëåäîâàòåëüíî,ïîëó÷àåì îöåíêó. (1) (2)Ëåììà. Èìååò ìåñòî âûâîäèìîñòü {t1 − t5 , t6 , t6 } ⇒ {t7 − t11 }.Ýòàïû äîêàçàòåëüñòâà. t7 âûâîäèòñÿ ïðèìåíåíèåì ê t5 ñ ñîâïàäàþùèìè âåðøèíàìè òîæ(2)äåñòâà t6 . t8 ïðèìåíèòü ê x1 t4 , ïîòîì ê îäíîðîäíûì ìåòåëêàì t5 , ïîòîì t3 . t9 t7 è t6 .t10 t7 è t5 . t11 ñ ïîìîùüþ t10 äåëàåì ïåðâûé òðåóãîëüíèê, êîòîðûé ïîòîì ðàñøèðÿåì ñïîìîùüþ t5 .
Ëåììà. Ïðè n ≥ 2 èìååò ìåñòî âûâîäèìîñòü τn ⇒ τ (n) .Ýòàïû äîêàçàòåëüñòâà. t2 , t9 î÷åâèäíî, èç ñàìèõ ñåáÿ. 8,3,4,5 ïî èíäóêöèè. 7 èç 2 è 5;10 è 11 èç 7 è 5. Ïðè ëþáûõ íàòóðàëüíûõLènâûïîëíÿåòñÿ íåðàâåíñòâî5Ëåììà.ΣëåíòíîéΣ, ãäå Σ ∈ U K è Σ = Σ(x1 , . . . , xn ; a1 , . . .
, am ), è ëþáîéΣ̂(x1 , . . . , xn ; a1 , . . . , am ) êàíîíè÷åñêîãî âèäà ñóùåñòâóåò ÝÏ Σ ⇒ Σ̂.Äëÿ ëþáîé ÊÑÊÑýêâèâà-τnΣ ⇒ Σ1 ⇒ Σ2 ⇒ Σ3 ⇒ Σ4 = Σ̂. Ñõåìà Σi îáëàäàåò ñâîéñòàâàìè 1(n) i êàíîíè÷åñêîé ÊÑ. Σ ⇒ Σ1 c ïîìîùüþ ïðèìåíåíèÿ ê êàæäîìó êîíòàêòó òîæäåñòâà t4 .Òåïåðü ÊÑ ñîñòîèò èç êàíîíè÷åñêèõ öåïåé ïîðÿäêà n. Σ1 ⇒ Σ2 ñ êàæäîé âíóòðåííåé âåðøèÝòàïû äîêàçàòåëüñòâà.íîé, èç êîòîðîé âûõîäèò íåêîòîðîå êîëè÷åñòâî (âîçìîæíî è 1) îäíîðîäíûõ çâåçä ðàçëè÷íûõöåïåé, ïðîâîäèì ñëåäóþùèå îïåðàöèè.
Êàæäóþ çâåçäó çàìåíÿåì íà öèêë ïî òîæäåñòâó(n)t11.(n)Äîáàâëÿåì íåíóæíûå âèñÿ÷èå âåðøèíû, ÷òîáû ìîæíî áûëî ïðèìåíèòü òîæäåñòâî t3è óäàëèòü ìåøàþùóþ âåðøèíó. Óäàëèâ òàêèì îáðàçîì âñå âíóòðåííèå âåðøèíû, íå ÿâëÿþùèåñÿâíóòðåííèìè âåðøèíàìè êàíîíè÷åñêèõ öåïåé, èçtn7 , Σ3 ⇒ Σ4èc ïîìîùüþÒåîðåìà.âèäà0Σ ⇒Σ00Σ1ïîëó÷èëèΣ2 . Σ2 ⇒ Σ3 ñ ïîìîùüþ(n)t6(n)t10 . Äëÿ ëþáûõ äâóõ ýêâèâàëåíòíûõ ÊÑΣ0èΣ00îò ÁÏx1 , . .
. , x nñóùåñòâóåò ÝÏ.τnÝòàïû äîêàçàòåëüñòâà. Ôàêòè÷åñêè, äâà ðàçà èñïîëüçîâàòü ëåììó è îäèí ðàç(n)t2.Ñëåäñòâèå. Ñèñòåìà τn ÿâëÿåòñÿ ÊÏÑÒ äëÿ ÝÏ ÊÑ èç U îò ÁÏ x1 , . . . , xn .Ñëåäñòâèå. Ñèñòåìà τ∞ ÿâëÿåòñÿ ÏÑÒ äëÿ ÝÏ ÊÑ èç U K .Ëåììà. Åñëè Σ0 (x1 , . . . , xn ) ⇒ Σ00 (x1 , . . . , xn ), òî Θ(Σ0 ) = Θ(Σ00 ), à åñëè Σ0 ⇒ Σ00 ,Kk < n,òîΘ(Σ0 ) − Θ(Σ00 )Ýòàïû äîêàçàòåëüñòâà. Äîêàçàòü, ÷òîãäåτk{t1 −t5 }n−käåëèòñÿ íà 2.Θ íå ìåíÿåòñÿ ïðè èñïîëüçîâàíèè òîæäåñòâ t1 . .
. t5α, òî îí ïðîâîäèòn−mn−käåëèòñÿ íà 2, à çíà÷èò, íà 2. ñ ïîìîùüþ ïðîñòîãî ïåðåáîðà. Çàòåì, çàìåòèòü, ÷òî åñëè ïðîâîäèò íà íàáîðåíà2n−míàáîðàõ, ñëåäîâàòåëüíî ðàçíîñòüÒåîðåìà. êëàññåUKíå ñóùåñòâóåò êîíå÷íîé ïîëíîé ñèñòåìû òîæäåñòâ.Ýòàïû äîêàçàòåëüñòâà. Îò ïðîòèâíîãî: åñëè îãðàíè÷èòü ÷èñëî ÁÏ, íàïðèìåð, ÷èñëîìòîtn+16Ðàçíîñòü ôóíêöèéíåò âûâîäà.Ëåììà.Θíå äåëèòñÿ íà 2, ÷òî ïðîòèâîðå÷èò ïðåäûäóùåé ëåììå, ñëåäîâàòåëüíîÏóñòü ÊÑΣΣ00Σ = Σ00 (Σ0 ), à F , F 0 è F 00 F ≥ F 0 · F 00 è F = F 0 · F 00 , åñëèÿâëÿåòñÿ ðåçóëüòàòîì ñòûêîâêè âèäàìàòðèöû, ðåàëèçóåìûå ÊÑÊÑn,íå âûâîäèòñÿ. ×òîáû ýòî äîêàçàòü, íàäî ðàññìîòðåòü ëåâóþ ÷àñòü ýòîãî òîæäåñòâà.Σ, Σ0èΣ00ñîîòâåòñòâåííî. Òîãäàðàçäåëèòåëüíàÿ ïî âõîäàì èëè ÊÑΣ0ðàçäåëèòåëüíàÿ ïî âûõîäàì.q êîëè÷åñòâî âûf ≥ f10 · f200 ∨ · · · ∨ fq0 · fq00 (ðàâåíñòâî ïðèÝòàïû äîêàçàòåëüñòâà.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
