Спец часть (часть 1) (3 поток) (2015) (by Кибитова) (1161601), страница 3
Текст из файла (страница 3)
иДоказательство.f1∉ S. Тогдаn1 ,...,f (σ1 ,..., σn ) = f(σ1,…,σn). Построим функцию φ(x) так: φ(x) = f(x ⊕σ1, …, x ⊕σn).~ f(σ1,…σn) <==>~ φ(1)~= φ(1)φ(x)~= f(x Заметим,~φ(0)~так:f (σ(ασДействительно,f (σ~1 1,...,,…,σ= ,…,σ==>φ(x)= βconst.f=(σf(σПостроимφ(x)σ1, …,чтоx разряды⊕⊕σn).≠βДействительно,n1).,...,n )и иαфункциюn ) =естьβσn),n(тоβα= β1,!, β n φ(0), что<1,…,σ≤β)≠)иf>f. Выделимтечтоjjf (σ,...,σ)φ(0)= fα(σ), φ(1) =1 ∀jиφ(0)=φ(1)==>φ(x)=const.Заметим,1nподстановкаудовлетворяетусловиютеоремы,какf (σ1так,...,σn ) и φ(0)функцииДействительно,φ(0) =~f (σ1функции).,…,σ= любой= φ(1) ==>φ(x) =логикиconst.
Заметим,что~условиюn), φ(1)Лемма(онемонотоннойИзнемонотоннойалгебрыподстановкаудовлетворяеттеоремы,таккак~ этиααiподстановкаиβ,вкоторыхониразличаются.Очевидно,внабореразряды1, …, ik наборовxx,удовлетворяетσσ==00условию теоремы, так как,~ всех переменных функции x, 0, 1, можно получить функцию φ (x) ≡ x .xx⊕σσ =x=n),подставляя вместоf(x, …,1⊕равны0,аxxx,в,σ,σσнаборе===011 β — 1. Рассмотрим последовательность наборовx ⊕σ = Доказательство.f M. Тогда существуют~ наборы~ α = (α1,…,αn) и1 x, σ =Пусть α~0 ,α~такие1 ,α 2 ,!,α kЛемма(о(онемонотоннойфункции).ИзИз~любойфункциинемонотоннойфункции).любойнемонотоннойалгебрылогики они различаются.βЛемма= (β1,…,βчто α~< β и~f(α)>~ f(β). Выделимте~немонотоннойразрядынаборовалгебрыα и β,~влогикикоторыхn), ~kфункции~ i1, …,iαααααβααтаких,что=<<<!<=,гдеполучаетсяиззаменойЛеммаИз любойнемонотоннойалгебрыf(x11,,…,…,(оxxn),nнемонотонной),подставляяподставляявместопеременныхфункции1,можноможнополучитьполучитьфункциюодного0 вместо1функции).2всехпеременных1 x,0,0,1,функцииki +x,i логикиx.
.нулей,0 1f(xвсехфункциифункциюφ φ(x)(x)≡ ≡xизОчевидно,внабореαэтиразрядыравны0,авнабореβ—1.Рассмотримпоследовательностьнаборовα,α,~~f(xвместовсехпеременныхфункцииx,наборы0, 1, можнополучитьфункциюφ(x)≡.x1, …, xn), подставляя∉Доказательство.ПустьfM.Тогдасуществуюттакиеα=(α,…,α)и1n∉Доказательство.ПустьfM.Тогдасуществуюттакиенаборыα=(α,…,α)иααрасположенноговоднойизпозицийi,…,i,наединицу(приэтомнаборыи—соn1k0 1 2ki+1 ki 1ii +1…,α,таких,чтоα=α<α<α<…<α=β,гдеαполучаетсяизαзаменойодногоизнулейна1.∉Доказательство.ПустьfM.Тогдасуществуюттакиенаборыα=(α,…,α)и,…,βn),n),чточтоαα<<ββииf(α)f(α)>>f(β).f(β).ВыделимВыделимразрядыi1i,1…,i, …,ik наборов1 α и nβ, в которых они различаются.k наборов~ тетеразрядыββ==(β(β11,…,βα~и β,~ в которыхони различаются.0 1~~~ найдутсяii+1ii+1,в!αααααседние).Посколькуf=1,аβ,срединаборов,,,дваαсоседf=0Очевидно,внабореαэтиразрядыравны0,авнабореβ—1.РассмотримпоследовательностьнаборовβОчевидно,=(β,…,β),чтоα<βиf(α)>f(β).Выделимтеразрядыi,…,iнаборовαиβ,которыхони0α , 1α ,1n1k1f(α 2 ) = 0.
ПустьkПоскольку= 1, аα f(β)=разряды0, то2 найдутсяα βи —α 1., чтоf(α ) =i 01 ипоследовательностьониразличаются.различаютсявf(α)набореэтиравны k0,соседниеа в набореРассмотримнаборов,0 α ,1 вk01i+1…, αk ,~таких,чтоα=α<α<α<…<α=β,гдеαполучаетсяизαзаменойодногоизнулейна1.Очевидно,внабореαэтиразрядыравны0,авнабореβ—1.Рассмотримпоследовательностьнаборовα,α,012ki+1i~~~i α, =такиеi+1 f αα получается…,αkразряде:,αтаких,чтоαα0 2<,…,α1 что<r-1α,2 0,< f…<,…,α=k =α1nβ,),иαгдеизαi r+1i заменойна 1.
разряде:ααнихи0.Пустьониразличаютсявr-омi α=i+1i+1одного из нулейi+1r-омα=(α,αα=(α,,…,α,1,α,…,α).11++iiii1r+112r-1nПосколькуи αi+1 , что f(α1 и f(αi+1 одного) = 0. Пустьони различаютсяв…,α , таких,f(α)что=α1,= аαf(β)< α= <0,αто<найдутся… < α = соседниеβ, где α αi получаетсяизi α) =заменойиз нулейна 1.Посколькуf(α)=соседниевi 1, а f(β) = 0, то найдутсяi+1 α i и α i+1, что f(α i) = 1 и f(α i+1) = 0. Пусть они различаютсяi~~разряде:(αа1,f(β)α,!, αααr–1αα,1r-1r+1,f(α,α,1,…,Посколькуf(α)αi =,=α1,функцию= 0,φ(x)то, ,0,найдутся)α=r+1α1n,).…,f(ααn.).)Тогда= 0. Пустьони различаютсяr-1nf),1и2,,…,αr-омαопределимααr+1φ(x)α =αсоседниеα,,rx,что,0α,2α,…,,,…,=(ααi+1α1, 1α,=2α(α, (αα…,,иαДействительно,определимТогдатак:тогдаφ(0) функцию= f(α )i = в1 ,α 2 ,!21,,!−1r-1i =разряде:rα+1r+1,!nn).r-омαα,…,α,1,,…,αi = (αr −1,1 α2,…,r +α1r-1, 0, αnr+1,…, iα+n1), α i+1 =2Тогдаопределимфункциюφ(x)α=n),f α(α1,=α2(α, …,тогда φ(0) = f(αi ) =r-омразряде:αr+1,…,αr-1α,r+11,, …,αr+1,α…,αn).r–1, x,n).
Действительно,1, α2,…, αφ(x)r-1, 0,так:1, α2α,…,i+1i+1α = (αТогдаопределимфункциюφ(x)так:φ(x)=f(α,α,…,α,x,α,…,α).Действительно,тогда12r–1r+1nϕ φ(0)α~)ii)=== 1 ,φ1,φ(1)(x)так:φ(x)=f(α,α,…,α,x,,…,α).Действительно,тогда0 ===ff(α1,Тогда=f(α)=0,φ(x)≡.φ(1)определим= f(α ) = 0,φ (x) ≡1xφ(x)функциюφ(0)f(αx .2 так: φ(x)r –=1f (α1, α2r, +…,1 αr–1, x, αnr+1, …, αn). Действительно, тогдаφ(1) == f(αf(α~i+1i+1)) == 0,0, φφ (x)(x) ≡ .1,1,ϕ φ(1)1 = f α i+1 = 0 и ϕ≡ xxx≡.
x . Лемма доказана. Определение. Полиномом Жегалкина над x1, …, xn называется выражение вида K1 ⊕K2 ⊕K3 ⊕…Определение.ПолиномомЖегалкинанад…,xxnnnвиданазываетсявыражениевидаKKK111 ⊕…Определение.xx111,,…,называетсявидаKKK222 ⊕выражениевида⊕различны,⊕KKK3либо⊕1.……где l >= 1 иЖегалкинавсе Kj естьнадвыраженияxi1xi2…xвыражение⊕Kl, либо 0,Полиномом33⊕ik, где все переменные§10.о нелинейнойфункции.выражения вида x x …x , где0, гдеl >= 1 и все K естьгде всевсе переменныепеременныеразличны,различны,либолибо1.1.⊕KKЛеммаll,, либоl либо 0, где l >= 1 и все Kjj есть выражения вида xi1i1i1xi2i2i2…xikikik, где все переменные различны, либо 1.Теорема(теорема Жегалкина). Любую функцию алгебры логики f(x1, …, xn) можно единственнымобразомвыразитьполиномомЖегалкинанадx,…,x.1nЛемма (о Жегалкина).нелинейнойЛюбуюфункции).Из любойфункции алгебры логикиТеорема(теоремаf(x11,, …,…, xxnn)) можноможнофункцию алгебрылогикинелинейнойf(xединственнымобразомвыразитьполиномомЖегалкинанад…,xnyn..1,, 0,единственнымобразомвыразитьполиномомЖегалкинаxxx11,, ,…,f (x1, …, xn), подставляявместовсехфункциюпеременныхx,логикиy, xf(xТеорема(теоремаЖегалкина).Любуюалгебрынад…,1,xn)можноможно получить φ (x, y) = x·yЛемма (о нелинейной функции).
Из любой нелинейной функции алгебры логикиединственнымвыразитьполиномомЖегалкинаxnможно. логикиyx1,, …,f (x1, ϕ…,(оxx,нелинейной), подставляявместо всехx, x , y,над0, 1,алгебрыполучить φ(x, y) = xy или φ(x, y) =или=образомx ⋅ y . функции).nyЛеммаИзпеременныхлюбой нелинейнойнелинейнойфункцииЛемма(о нелинейнойфункции). Излюбойфункцииалгебры логики .Доказательство.y , 0, 1, можно получить φ(x, y) = xy или φ(x, y) =f (xxy1, …,xn), подставляя вместовсехпеременныхx,,y,xПусть(x1, …, xn) ∉x, L.x РассмотримполиномЖегалкинаf (x1, …, xn), подставляя вместовсехf переменных, y, y , 0, 1, можнополучитьφ(x, y) = xyэтойилифункции.φ(x, y) =Доказательство.Пусть f (x1, …, xn) ∉ L.
Рассмотрим полином Жегалкина этой функции.xy.Лемма(о нелинейнойследует,функции).Изчтолюбойфункциивидаалгебрылогикиxy еёИзнелинейностиследует,в нёмнелинейнойприсутствуютслагаемыеxi1 ⋅ xi2 ⋅! . Не ограни. нелинейностиИз еёчтоxnв) нёмxi1xi2 .этойНевидаограни∉ L.присутствуютДоказательство.Пусть f (x1, …,Рассмотрим слагаемыеполином Жегалкинафункции.∉Доказательство.Пустьf (x1, что…,всехxвn)нёмL.
Рассмотримполиномчиваяобщностирассуждений,будемсчитать,чтоx, присутствуетпроизведениеxфункции.fчивая(xеё1, …,xn), подставляявместопеременных,чтоy, yприсутствует, Жегалкина0,вида1, можнополучитьφ(x,Та-y) = xxy1 ·или=1x2 · ….xслагаемыеобщностирассуждений,будемсчитать,произведениеx2 ·φ(x,….y)ТаИзнелинейностиследует,присутствуютxi1xi2 .этойНеограниИзеёнелинейностиследует,чтовнёмприсутствуютслагаемыевидаxx.Неограниким образом,Жегалкинафункциивыглядиттак: произведениеi1 i2чиваяобщностиполиномрассуждений,будемэтойсчитать,присутствуетx1x2 · ….
Такимобразом,полиномЖегалкинаэтойчтофункциивыглядиттак:()(()()()∉()()( ))(( )()() ( )() ( )()⊕ ⊕ ⊕⊕( )xy)Лемма (о нелинейной функции). Из любой нелинейной функции алгебры логикиf (x1, …, xn), подставляя вместо всех переменных x, x , y, y , 0, 1, можно получить φ (x, y) = x·yили ϕ (x, y ) = x ⋅ y .Доказательство. Пусть f (x1, …, xn) ∉ L. Рассмотрим полином Жегалкина этой функции.Из её нелинейности следует, что в нём присутствуют слагаемые вида xi1 ⋅ xi2 ⋅ ! . Не ограничивая общности рассуждений, будем считать, что присутствует произведение x1 · x2 · …. Таким образом, полином Жегалкина этой функции выглядит так:f (x1, …, xn) = x1 · x2 · P1 (x3, …, xn) ⊕ x1 · P2 (x3, …, xn) ⊕ x2 · P3 (x3, …, xn) ⊕ P4 (x3, …, xn),причем P1 (x3, …, xn) ≠ 0.Иначе говоря, ∃ a3, a4, …, an ∈ E2 = {0, 1} такие, что P1 (a3, a4, …, an) = 1.
Рассмотрим вспомогательную функцию f (x1, x2, a3, a4, …, an) = x1 x2 · 1 ⊕ x1 · b ⊕ x2 · c ⊕ d. Тогда функцияf (x ⊕ с, y ⊕ b, a3, a4, …, an) = (x ⊕ c)(y ⊕ b) ⊕ (x ⊕ c)b ⊕ (y ⊕ b)c ⊕ d = xy, bc ⊕ d = 0= xyТеорема⊕ x · b ⊕ Постаy · c ⊕ bо ·полнотеc ⊕ x · b ⊕системыb · c ⊕ y функций· c ⊕ b · c ⊕алгебрыd = xy ⊕ (bc⊕ d) = .§11.логики. xy, bc ⊕ d = 1§11.Постаоополнотеалгебрылогики.Леммадоказана.§11. ТеоремаТеоремаПостаполнотесистемыфункцийалгебрылогики.Теорема12(теоремаПоста).системыСистема функцийфункцийалгебрылогикиA = {f1, f2, …} является §11.
Теорема Поста о полноте системы функций алгебры логики.полнойвPтогдаитолькотогда,когдаонанесодержитсяцеликомниводномизследуюТеорема12(теоремаПоста).СистемафункцийалгебрылогикиA={f,f,…}является212Теорема 12 (теорема Поста). Система функций алгебры логики A = {f1, f2, …} являетсяполнойвв PP22 тогдакогдаонацеликомнинив водномизизследуюполнойтогдатолькотогда,когдафункцийонаненесодержитсясодержитсяцеликомодномследующихклассов:T0, T1и,иS,толькоL,M. тогда,Теорема12(теоремаПоста).СистемаалгебрылогикиA={f,f,…}является1211щихTT00, ,TT11, ,S,S,L,L,M.щих классов:классов:M.Доказательство.Необходимость.Пусть— полнаяполнаясистема,— любойлюбойиз классовклассов полной вДоказательство.P2 тогда и толькоНеобходимость.тогда, когда онаПустьне содержитсяцеликомни NвNN—одномиз следуюAAA—система,изДоказательство.Необходимость.Пусть— полнаясистема,— любойиз классовщих Tклассов:TL,T1и,ииS,L, M.AAA⊆⊆T111,,,S,S,S,L,L,0,MMпустьN.Тогда[A][N]и [A][A] ≠≠PP22..2Полученноепротиворечиепусть22иTT000,,, TTMпусть⊆N.N.ТогдаТогда[A][A]⊆⊆⊆[N][N]===NNN≠≠≠PPP.ПолученноеПолученноепротиворечиепротиворечие2 и [A] ≠ Pзавершаетобоснованиенеобходимости.Доказательство.Необходимость.Пусть A — полная система, N — любой из классовзавершает обоснованиенеобходимости.необходимости.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
