Теормин (2012) (1133351), страница 4
Текст из файла (страница 4)
Ëþáóþ ôîðìóëó F(x1 , . . . , xn ), ðåàëèçóþùóþ ÔÀË f , ñ ïîìîùüþ ÝÏ íà îñíîâåþíêöèé, ñîäåðæàùóþ, â îáùåì ñëó÷àå, ïîâòîðÿþùèåñÿ ¾ñëàãàåìûå¿, (ÎÄÍÔ).Îáû÷íóþ ÝÊ (ÄÍÔ) è ôîðìóëóñèñòåìû òîæäåñòâτîñíx1 x̄1áóäåì ñ÷èòàòüìîæíî ïðåîáðàçîâàòü â ñîâåðøåííóþ ÎÄÍÔ ÔÀËÝòàïû äîêàçàòåëüñòâà. Ñíà÷àëà ïðèâåñòè ôîðìóëó ñ ïîìîùüþìè îòðèöàíèÿìè. Çàòåì, èñïîëüçóÿτÏÏAK= {τ , τ , τÏÊ,τÎÏÏ, τ },DKτ&,∨, τ&τMfîò ÁÏX(n).ê ôîðìóëå ñ ïîäíÿòû-ðàñêðûòü ñêîáêè.
Íàêîíåö, ñ ïîìîùüþτ ÏÏ ,ãäåïðèâåñòè ïîäîáíûå â 3 øàãà: ïðèâåäåíèå âñåõ ÎÝÊ â êàíîíè-÷åñêèå ÎÝÊ, óñòðàíåíèÿ ïîâòîðíûõ âõîæäåíèé ðàâíûõ ÝÊ èëè ïîäôîðìóëx ∨ x̄, ïðèâåäåíèåïîãëîùåíèé ÝÊ; ñ ïîìîùüþ òîæäåñòâà äèñòðèáóòèâíîñòè äîïîëíèòü âñå ÊÍÔ äî íåîáõîäèìãî ðàíãà. Òîæäåñòâà àññîöèàòèâíîñòè, êîììóòàòèâíîñòè è ïîäñòàíîâêè êîíñòàíò äåéñòâóþòτîñí íà äâóõ ïîñëåäíèõ øàãàõ.Òåîðåìà.Ñèñòåìàïîëíàÿ ñèñòåìà òîæäåñòâ.Ýòàïû äîêàçàòåëüñòâà. Ïóñòü äâå ôîðìóëû ýêâèâàëåíòíû.
Ìîæíî ñâåñòè îáå ê ÎÄÍÔ ñïîìîùüþ ïðåäûäóùåé ëåììû, èñïîëüçóÿ òîëüêîτîñí . Çíà÷èò, îíà ïîëíàÿ ñèñòåìà òîæäåñòâ.4Ñõåìîé èç ôóíêöèîíàëüíûõ ýëåìåíòîâ íàä áàçèñîì Áíàÿ àöèêëè÷åñêàÿ óïîðÿäî÷åííàÿ ñåòüΣ,íàçûâàåòñÿ îðèåíòèðîâàí-âõîäíàÿ âûáîðêà êîòîðîé ñîñòîèò èç âñåõ èñòîêîâΣ,à âåðøèíû ïîìå÷åíû ñëåäóþùèì îáðàçîì: êàæäîìó âõîäó (âûõîäó)èçX(ñîîòâåòñòâåííîZ ),Σñîïîñòàâëåíà ÁÏÿâëÿþùàÿñÿ ïîìåòêîé ñâÿçàííîé ñ íèì âåðøèíû, ïðè÷åì ðàçëè÷-íûì âõîäàì (âûõîäàì) ñîïîñòàâëåíû ðàçëè÷íûå ÁÏ, à óïîðÿäî÷åííîñòü âåðøèí âî âõîäíîéè âûõîäíîé âûáîðêàõΣîïðåäåëÿåòñÿ óïîðÿäî÷åííîñòüþ ñîïîñòàâëåííûõ èì ÁÏ; êàæäàÿ îò-ëè÷íàÿ îò èñòîêà âåðøèíàvñõåìûΣïîìå÷åíà ÔÑ10ϕi .ÑõåìàΣ,êîòîðàÿ ïîëó÷àåòñÿ èç äåðåâàD,ñâÿçàííîãî ñ ôîðìóëîéFèçU Φ,â ðåçóëüòàòåîòîæäåñòâëåíèÿ ëèñòüåâ ñ îäèíàêîâûìè ïîìåòêàìè è ïðèïèñûâàíèÿ åãî êîðíþ âûõîäíîé ÁÏèçZ,íàçûâàåòñÿêâàçèäåðåâîì, ñîîòâåòñòâóþùèì ôîðìóëå F .âèñÿ÷åé, åñëè îíà ÿâëÿåòñÿ ñòîêîì,Âåðøèíà ÑÔÝ íàçûâàåòñÿíî íå ÿâëÿåòñÿ âûõîäîìñõåìû.
Ñõåìà íàçûâàåòñÿ ïðèâåäåííîé, åñëè â íåé íåò âèñÿ÷èõ âåðøèí.L(Σ) ñëîæíîñòü Σ, òî åñòü ÷èñëî âñåõ åå ÔÝ; D(Σ) ãëóáèíà Σ, òî åñòü ìàêñèìàëüíàÿR(Σ) ðàíã Σ, òî åñòü ÷èñëî äóã,èñõîäÿùèõ èç åå âõîäîâ.Ëåììà. Äëÿ ïðèâåäåííîé ÑÔÝ Σ, Σ ∈ U C , ñ îäíèì âûõîäîì, âûïîëíÿþòñÿ íåðàâåíñòâàR(Σ) ≤ L&,∨ (Σ) + 1 ≤ L(Σ) + 1 ≤ 2D(Σ) , ãäå L&,∨ (Σ) ÷èñëî ÔÑ & è ∨ â Σ.Ýòàïû äîêàçàòåëüñòâà. Ýòà ëåììà ïðîñòî ïåðåíîñ íà êëàññ ÑÔÝ ëåììû èç 2. Ëåììà. Äëÿ ëþáûõ íàòóðàëüíûõ n, L, D âûïîëíÿþòñÿ íåðàâåíñòâà |U Φ (L, n)| ≤ (10n)L+1 ,DΦ||U (L, n)|| ≤ (8n)L+1 , |U Φ [D, n]| ≤ (8n)2 .2Ýòàïû äîêàçàòåëüñòâà.
Ñîïîñòàâëÿåì êàæäîé âíóòðåííåé âåðøèíå äåðåâà íàáîð èç B1(äëÿ êîíúþíêöèé è äèçúþíêöèé) èëè B (äëÿ îòðèöàíèé) åãî i-é ýëåìåíò ðàâåí 1, åñëèäóãà ñ íîìåðîì i, âûõîäÿùàÿ èç âåðøèíû, íà÷èíàåòñÿ ñ ëèñòà. Êðîìå òîãî, äëÿ âåðøèí ñ2íàáîðàìè èç B , ñîïîñòàâèì ñèìâîë èç íàáîðà [∨, &]. Òîãäà ïîëó÷èòñÿ 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)).ãëóáèíà åå âåðøèí.Ýòàïû äîêàçàòåëüñòâà. Ïîëó÷àåòñÿ èç ïðèâåäåííîé â ïðåäûäóùåé ëåììå îöåíêè ÷èñëàäåðåâüåâ è òîãî ôàêòà, ÷òî êàæäûé ëèñò ìîæíî ïðèñîåäèíèòü ëèáî êâíóòðåííèì âåðøèíàì.nâõîäàì, ëèáî êL5Ïîäñòàíîâêè ðÿä ¾ïðîñòåéøèõ¿ ïðåîáðàçîâàíèé, ñîõðàíÿþùèõ ýêâèâàëåíòíîñòü ñõåì.Ïîäñòàíîâêà òîæäåñòâà t òîæäåñòâî t̂ : Σ̂0 ∼ Σ̂00 , êîòîðîå ïîëó÷àåòñÿ â ðåçóëüòàòåt : Σ0 ∼ Σ00 .0Ñõåìà Σ íàçûâàåòñÿ ïîäñõåìîé ñõåìû Σ, åñëè V (Σ ) ⊆ V (Σ), E(Σ ) ⊆ E(Σ) è ëþáàÿ0âåðøèíà v, v ∈ V (Σ ), êîòîðàÿ ëèáî îòíîñèòñÿ ê ìíîæåñòâó âõîäîâ (âûõîäîâ) Σ, ëèáî ñëóæèò0êîíå÷íîé (ñîîòâåòñòâåííî íà÷àëüíîé) âåðøèíîé íåêîòîðîãî ðåáðà èç E(Σ) \ E(Σ ), ÿâëÿåòñÿ0âõîäîì (ñîîòâåòñòâåííî âûõîäîì) Σ .ΦÒåîðåìà.
Åñëè τ êîíå÷íàÿ ïîëíàÿ ñèñòåìà òîæäåñòâ äëÿ ÝÏ ôîðìóë èç UÁ, òîÑÂÑ{τ , τ , τ } êîíå÷íàÿ ïîëíàÿ ñèñòåìà òîæäåñòâ äëÿ ÝÏ ÑÔÝ èç UÁ .ïðèìåíåíèÿ îäíîé è òîé æå ïîäñòàíîâêè ê îáåèì ÷àñòÿì òîæäåñòâà00Ýòàïû äîêàçàòåëüñòâà. C ïîìîùüþ òîæäåñòâ ñíÿòèÿ è âåòâëåíèÿ èçáàâëÿåìñÿ îò âñåõâíóòðåííèõ âåòâëåíèé è âèñÿ÷èõ âåðøèí, ïîëó÷àåì ñõåìó, êîòîðàÿ ìîäåëèðóåò ôîðìóëó. Àτ. {τ îñí , τ  , τ Ñ } ÊÏÑÒ äëÿ ÝÏ ÑÔÝ èç U Ñ .0bÏóñòü ïîìèìî áàçèñà Á = {ϕi }i=1 ó íàñ èìååòñÿ äðóãîé êîíå÷íûé ïîëíûé áàçèñ Á =0 b00Φ0{ϕi }i=1 , è ïóñòü ôîðìóëà Φi (x1 , .
. . , xki0 ) èç UÁ0 , ãäå ki ≥ ki , ðåàëèçóåò ÔÀË ϕi , i = 1, . . . , b.00Çàìåòèì, ÷òî â ñëó÷àå ki > ki ÁÏ xki +1 , . . . , xk0 ÿâëÿþòñÿ ôèêòèâíûìè ÁÏ ôîðìóëû Φi . Ïîi00000000ëîæèì Φ = (Φ1 , . . . , Φb ), Π = (Π1 , . . . , Πb ), ãäå Πi òîæäåñòâî âèäà ϕi = Φi , i = 1, . . . , b, è00ôîðìóëû èç Φ (òîæäåñòâà èç Π ) áóäåì íàçûâàòü ôîðìóëàìè (ñîîòâåòñòâåííî òîæäåñòâàäëÿ ïðåîáðàçîâàíèÿ â ôîðìóëàõ èñïîëüçóåòñÿÑëåäñòâèå.Ñèñòåìà òîæäåñòâìè) ïåðåõîäà îò áàçèñà Á ê áàçèñó Á0 .F, F ∈ UÁΦ , îáîçíà÷èì ÷åðåç Π0 (F) ôîðìóëó íàä áàçèñîì Á0 , êîòîðàÿ ïîëó÷àåòñÿ èç F çàìåíîé êàæäîé åå ïîäôîðìóëû âèäà ϕ(F1 , .
. . , Fki ) ôîðìóëîéΦ0i (F1 , . . . , Fki , xki +1 , . . . , xki0 ), òî åñòü ÿâëÿåòñÿ ðåçóëüòàòîì ïîäñòàíîâêè ôîðìóëû Fj âìå00ñòî ÁÏ xj â ôîðìóëó Φi äëÿ âñåõ j, j = 1, . . . , ki . Ïåðåõîä îò ôîðìóëû F ê ôîðìóëå Π (f )0áóäåì íàçûâàòü ñòðóêòóðíûì ìîäåëèðîâàíèåì ôîðìóëû F â áàçèñå Á íà îñíîâåôîðìóë ïåðåõîäà Φ0 èëè, èíà÷å, íà îñíîâå òîæäåñòâ ïåðåõîäà Π0 .Φ0Òåîðåìà. Òåîðåìà ïåðåõîäà. Ïóñòü τ ÊÏÑÒ äëÿ ÝÏ ôîðìóë èç UÁ, à Π è Π ñèñòåìûÄëÿôîðìóëû00òîæäåñòâ äëÿ ïåðåõîäà îò áàçèñà Á ê áàçèñó Á è îò áàçèñà Á ê áàçèñó Á ñîîòâåòñòâåííî.
Òîãäà11ñèñòåìà òîæäåñòâ{Π0 (τ ), Π0 (Π)}ÿâëÿåòñÿ ÊÏÑÒ äëÿ ÝÏ ôîðìóë èçUÁΦ0 .Ýòàïû äîêàçàòåëüñòâà. Êîíñòðóêòèâíî ïîêàçàòü ïðîöåññ ïåðåâîäà â äðóãîé áàçèñ (âñåòîæäåñòâà ïåðåâîäÿòñÿ â äðóãîé áàçèñ ñ ïîìîùüþ ñèñòåìû ôîðìóë ïåðåõîäà, íà èõ îñíîâåïðîèçâîäÿòñÿ òîæäåñòâåííûå ïðåîáðàçîâàíèÿ â äðóãîì áàçèñå), ïðåîáðàçîâàíèé â íåì, ïåðåâîä îáðàòíî.Ñëåäñòâèå.Èç ñèñòåìû òîæäåñòâτ îñíäëÿ ÝÔ ôîðìóë èçUΦóêàçàííûì â òåîðåìå ñïî-ñîáîì ìîæíî ïîëó÷èòü ÊÏÑÒ äëÿ ÝÏ ôîðìóë â ëþáîì áàçèñå Á.6xi (x̄i ) íàçûâàåòñÿ çàìûêàþùèì (ñîîòâåòñòâåííî ðàçxi .000000Ñåòü Σ ñ âõîäàìè a1 , . . . , ap è âûõîäàìè a1 , . . .
, aq , â êîòîðîé âñå ðåáðà (äóãè)ïîìå÷åíû ïåðåìåííûìè x1 , . . . , xn èëè èõ îòðèöàíèÿìè x̄1 , . . . , x̄n , íàçûâàåòñÿ (p, q)êîíòàêòíîé ñõåìîé (ÊÑ) îò ÁÏ x1 , . . . , xn è îáîçíà÷àåòñÿ Σ = Σ(x1 , . . . , xn ) èëè Σ =Σ(x1 , . . . , xn ; a01 , . . . , a0p ; a001 , . . . , a00q ).×èñëî êîíòàêòîâ íàçûâàåòñÿ ñëîæíîñòüþ ÊÑ Σ è îáîçíà÷àåòñÿ ÷åðåç L(Σ).nÏóñòü Σ ÊÑ îò ÁÏ X(n) è α = (α1 , . . .
, αn ) íàáîð èç B . Îïðåäåëèì ñåòü Σ|α êàêᾱ1ᾱñåòü, ïîëó÷àþùóþñÿ èç Σ â ðåçóëüòàòå óäàëåíèÿ âñåõ ðåáåð (äóã) ñ ïîìåòêàìè x1 , . . . , xn n ,òî åñòü ðåáåð, êîòîðûå íå ïðîâîäÿò íà íàáîðå α, è ñíÿòèÿ ïîìåòîê ñ îñòàëüíûõ ðåáåð Σ. Äëÿâåðøèí v è u ÊÑ Σ ââåäåì ôóíêöèþ ïðîâîäèìîñòè îò âåðøèíû v ê âåðøèíå u êàênÔÀË gu,v (x1 , . . . , xn ), êîòîðàÿ ðàâíà 1 íà íàáîðå α = (α1 , . .
. , αn ) ∈ B òîãäà è òîëüêî òîãäà,êîãäà â ñåòè Σ|α ñóùåñòâóåò (v − u)-öåïü, òî åñòü òîãäà è òîëüêî òîãäà, êîãäà â Σ èìååòñÿ öåïüα1αèç ïðîâîäÿùèõ íà íàáîðå α êîíòàêòîâ âèäà x1 , . . . , xn n , èäóùàÿ èç v â u. Áóäåì ãîâîðèòüòàêæå, ÷òî ÔÀË gv,u ÿâëÿåòñÿ ôóíêöèåé äîñòèæèìîñòè âåðøèíû u èç âåðøèíû v ,èëè, èíà÷å, ðåàëèçóåòñÿ ìåæäó âåðøèíàìè v è u.D(x1 , . . . , xn ; 1; a0 , . . . , a2n −1 ) (1, 2n )-êîíòàêòíîå äåðåâî ïîðÿäêà n îò ÁÏ X(n).000Ñõåìû Σ è Σ ñ÷èòàþòñÿ èçîìîðôíûìè, åñëè èçîìîðôíû ñîîòâåòñòâóþùèå èì ãðàôû,Ðåáðî èëè äóãà ãðàôà ñ ïîìåòêîéìûêàþùèì)èêîíòàêòîì ÁÏýêâèâàëåíòíû,åñëè îíè ðåàëèçóþò ðàâíûå ñèñòåìû ÔÀË.C , ñîñòîÿùåãî èç êîíòàêòîâ âèäà xσi11 , . . .
, xσirr â ÊÑ Σ, îïðåäåëèì åãî ôóíêσr1öèþ ïðîâîäèìîñòè K(C) è ôóíêöèþ îòäåëèìîñòè J(C) êàê ÔÀË âèäà xσi1 · · · xir èxσ̄i11 ∨ · · · ∨ xσ̄irr ñîîòâåòñòâåííî. Ìíîæåñòâî C íàçûâàåòñÿ ïðîâîäÿùèì (îòäåëèìûì), åñëèK(C) 6= 0(J(C) 6= 1), è íóëåâûì (ñîîòâåòñòâåííî åäèíè÷íûì) â ïðîòèâíîì ñëó÷àå.Ëåììà. Ëþáîé π -ñõåìå Σ ìîæíî ñîïîñòàâèòü ýêâèâàëåíòíóþ åé ôîðìóëó F èç U Φ ñ ïîäíÿòûìè îòðèöàíèÿìè òàêóþ, ÷òî R(F) = L(Σ) è îáðàòíî.Äëÿ ìíîæåñòâàÝòàïû äîêàçàòåëüñòâà.
Îñíîâàíî íà ìîäåëèðîâàíèè áóêâ îäíèì ðåáðîì, äèçúþíêöèè ïàðàëëåëüíûì ñîåäèíåíèåì, êîíúþíêöèè ïîñëåäîâàòåëüíûì ñîåäèíåíèåì. Ñëîæíîñòü âûñ÷èòûâàåòñÿ ïðîñòûì ñëîæåíèåì.f,Ñõåìà, ìîäåëèðóþùàÿ ñîâåðøåííóþ ÄÍÔ ÔÀËíàçûâàåòñÿêàíîíè÷åñêîéÊÑ äëÿýòîé ÔÀË.Áóäåì íàçûâàòü(1, m)-ÊÑ ïðèâåäåííîé,Σ ÿâëÿþòñÿΣ ïðèíàäëåæàò ïðîñòûì ïðîâîäÿùèìÊÑ Σ̂, êîòîðàÿ ïîëó÷àåòñÿ èç ÊÑ Σ óäà-åñëè âñå èçîëèðîâàííûå âåðøèíûåå ïîëþñàìè, à âñå êîíòàêòû è îñòàëüíûå âåðøèíûöåïÿì, ñîåäèíÿþùèì åå âõîä è âûõîäû. Ïðè ýòîìëåíèåì ¾ëèøíèõ¿, òî åñòü íå ïðèíàäëåæàùèõ öåïÿì óêàçàííîãî âèäà, íåïîëþñíûõ âåðøèí èêîíòàêòîâ, ÿâëÿåòñÿ ýêâèâàëåíòíîéËåììà.ΣÏðè ëþáûõ íàòóðàëüíûõïðèâåäåííîé ÊÑ òàêîé, ÷òîLènL(Σ̂) ≤ L(Σ).||U π (L, n)|| ≤ (12n)L .âûïîëíÿåòñÿ íåðàâåíñòâîÝòàïû äîêàçàòåëüñòâà.
 ñèëó ïðåäûäóùåé ëåììû, ýòî ýêâèâàëåíòíî óòâåðæäåíèþ, ÷òî÷èñëî ïîïàðíî íåýêâèàëåíòíûõ ôîðìóë ñ ïîäíÿòûìè îòðèöàíèÿìè íå áîëåå(16n)L(12 âìåñòî16 ïîëó÷àåòñÿ èç-çà òîãî, ÷òî ÷òî ìû óìíîæàåì íà 2 íå 8 (êàê â îðèãèíàëüíîé îöåíêå), à 6,ïîòîìó ÷òî íåò îòðèöàíèé). Ðàññìîòðèì ôîðìóëû îò óäâîåííîãî êîëè÷åñòâà ÁÏ, âîñïîëüçóåìñÿ òåîðåìîé îá îöåíêå êîëè÷åñòâà íåýêâèâàëåíòíûõ ôîðìóë (âòîðîé èç òðåõ), ó÷òåì ñâÿçüìåæäó ðàíãîì è äëèíîé è ïîëó÷èì íóæíóþ îöåíêó.Ëåììà.Ïðè ëþáûõ íàòóðàëüíûõLènÝòàïû äîêàçàòåëüñòâà.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
