Спец часть (часть 1) (3 поток) (2015) (by Кибитова) (1161601), страница 4
Текст из файла (страница 4)
ПустьAA⊄⊄TT0[A],0,AA⊆⊄⊄T⊄N⊄M,AA⊄L,L,A≠⊄PS..S.Тогдав вA Aсуществуютфункции1,1,A=Достаточность.ПустьTAM,⊄A⊄ТогдасуществуютфункцииT0, T1, S, Достаточность.L,MипустьA⊆N.Тогда[N]≠Pи[A]Полученноепротиворечие22Достаточность.ПустьA ⊄fS T∉0,S.A Достаточно⊄ T1, A ⊄ M, A ⊄ L, A что⊄ S. Тогдав A существуют функцииff00 ∉ff11∉∉ TT11,,fMfLfL∉∉L,∉ TT00,,обоснованиеfM∉∉M,M,L, fS ∉ S.
Достаточнопоказать,показать, что[A][A]⊇⊇[f0[f, 0f,1,f1f,Mf,Mf,L,fLf,S]fS=] =P2P. 2Разо. Разозавершаетнеобходимости.бьёмнатричасти:получениеотрицания,константиконъюнкции.fбьём,f∉T,f∉M,f∉L,f∉S.Достаточнопоказать,что[A]⊇[f,f,f,f,f]=P.Разо0 ∉ Tдоказательство011MLS01MLS2доказательство на три части: получение отрицания, констант и конъюнкции.Достаточность.Пусть .AРассмотрим⊄ T0, A ⊄ T1функцию, A ⊄ M, Af0⊄(xL,1, A…,⊄ S.существуютфункции =Получениеxnx)Тогда∉ T ви Aконъюнкции.введёмбьёмa)a)доказательствочасти: получениеотрицания,Получение xнаx .триРассмотримфункциюf0 (x1, …,константвведёмфункциюфункциюφ0φ(x)n) ∉ 0T0и и0 (x) =f0 ∉ T0, f1 ∉ T=1=, fff0M0(x,∉M,f∉L,f∉S.Достаточнопоказать,что[A]⊇[f,f,f,f,f]=P.Разоx,…,x).Таккакфункцияfнесохраняетнуль,φ(0)=f(0,0,…,0)=1.ВозLS01MLS200(x, x, …,xx).Так как функцияf0 неf сохраняетφ0 (0) = f (0,функцию0, …, 0) =a) можныПолучение.части:Рассмотримфункцию(x1,констант…,φ0xnнуль,)(x)∉и Tконъюнкции.φ01.(x)Воз=0 либо0 и1.введём()ϕдваслучая:либоx=x,≡Рассмотримфункциюбьём доказательствонатриполучениеотрицания,0можны два случая: либо ϕ 0 (x ) = x , либо φ0 (x) ≡ 1.
Рассмотрим функциюf01(x,как функциюфункция образомff00неφ0 (0)φ1=(x)fфункцию(0, 0, …,x,0)φ…,=(x)x).1. =Возff=, …,x,x x.…,∉x).T1Таки аналогичнымвведёмфункциюТакa) Получение(x1сохраняет, …,xn) ∉нуль,Tфункцию1 (xn)Рассмотрим0 и введёмвведёмφ1 (x)= =f1 f(x,1 (x1, …, xn) ∉ T1 и аналогичным образом1 (x, x,0…, x). Таккакфункцияfнесохраняетединицу,φ(1)=f(1,1,…,1)=0.Возможнытакже(x )сохраняетϕ0 0неможныдваТак1fслучая:либо fединицу,= x ,φ1 1либо(x)≡ =1)1.f =(0,Рассмотрим= f0 (x,x, функция…, x).функция…, 0) = 1.функциюВоз-два0 φкакне сохраняет(1) нуль,= fφ(1,1,0 (0)…,0.0,Возможнытакжедва1 какϕслучая:либо(x)=x,либоφ(x)≡0.Еслихотябыводномслучаеполучилосьис1случая:=аналогичнымx , либо0.
Еслибыв одномисϕ 0 (x )φ=1 (x)можныслучая:xобразом, ≡либоφ0 хотя(x)функцию≡ 1.Рассмотримфункциюf (x два, …,либоx ) ∉ϕ1T1 (xи)либовведёмφ (x)случае= f (x,получилосьx, …, x). Так1 1n111комоекомое отрицание,отрицание,пунктпунктзавершён.завершён.ЕслиЕслижежев вобоихобоихслучаяхслучаяхполучилисьполучилиськонстанты,константы,f1 (x1то,как…,xn) ∉ T1леммеиf1 аналогичнымобразомфункции,введёмфункциюφ1)= Возможныf1 (x, x,fM…,x).Так двафункциянесохраняетединицу,φ(1)=f(1,1,…,=0.также1 в(x)согласноонемонотоннойподставляяфункцию∉M1то согласно лемме о немонотонной функции, подставляя в функцию fM ∉ Mвместовместокак функцияf1 не ϕсохраняетединицу,φ=f(1,1,…,1)=0.Возможнытакжедвавсехпеременныхконстантыиφитождественныефункции,можнополучитьотрицание.1 (1)случая:либоx=x,либо(x)≡0.Еслихотябыводномслучаеполучилосьисвсехпеременныхконстантытождественныефункции,можнополучитьотрицание.11Отрицаниеполучено.ϕслучая:либо(x)=x,либоφ(x)≡0.Еслихотябыводномслучаеполучилосьис1Отрицание1 получено.комое отрицание,пунктжеСогласнов обоих случаяхконстанты,b) Получениеконстант0 и завершён.1.
Имеем ЕслиfS ∉ S.лемме ополучилисьb)Получениеконстант0и1. ИмеемfS ∉в обоихS. Согласнолеммеонесамодвойственнойнесамодвойственнойкомоеотрицание,пунктзавершён.Еслижеслучаяхполучилиськонстанты,функции,подставляявсех переменныхфункции fS отрицаниеполуто согласнолемме о вместонемонотоннойфункции, подставляяфункцию(котороеfM(которое∉ M вместофункции,подставляявместо всехпеременныхфункцииfSв отрицаниеполуто согласнолеммеонемонотоннойфункции,подставляявфункциюf∉Mвместочено в пункте a) и тождественную функцию, можно получитьконстанты:Mченовпунктеa)итождественнуюфункцию,можнополучитьконстанты:всехпеременныхконстантыи тождественныефункции,можнополучитьотрицание.всех[f[fпеременныхтождественныефункции,можнополучитьотрицание.Константыиполучены.S, x ] ∋ [0, 1].константы,x]∋[0,1].Константыполучены.SОтрицаниеполучено.
x · y. Имеем функцию fL ∉ L. Согласно лемме о нелинейной c) ПолучениеконъюнкцииОтрицаниеполучено.c) Получениеконъюнкции x · y. Имеем функцию fL ∉ L. Согласно лемме о нелинейнойподставляявместопеременныхконстантыи отрицанияb) функции,Получениеконстант0вфункциюифункцию1. ИмеемfSS.∉СогласноS.всехСогласнолеммеоконстантынесамодвойственнойb) Получениеконстант0 и в1.ИмеемffSLf∉леммео несамодвойственнойфункции,подставляявсехпеременныхи отрицанияL вместо(которые были получены на предыдущих шагах доказательства), можно получитьфункции,подставляявместовсехпеременныхфункцииfотрицание(котороеполу(которыебылиполученынапредыдущихшагахдоказательства),можнополучитьфункции,подставляя вместовсех переменныхфункцииfS отрицаниеполуS первом(котороелибо конъюнкцию,либо отрицаниеконъюнкции.Однаконаэтапе отрицаниелибоконъюнкцию,либоотрицание конъюнкции.Однакона первомэтапеотрицаниеченоужев пунктеa) иa)следовательно,тождественнуюфункцию,можнополучитьконстанты:ченовполучено,пунктеи тождественнуюфункцию,можнополучитьконстанты:всегдаможнополучитьконъюнкцию:уже получено, следовательно, всегда можно получить конъюнкцию:[fS, x[f[f]LS,∋, 0,[0,получены.∋1].[xy,xy ].
Конъюнкцияx 1,] ∋1].x[0,]КонстантыКонстантыполучены.получена. [fL, 0, 1, x ] ∋ [xy, xy ]. Конъюнкция получена.c) Получениеконъюнкцииx·y.Имеемфункциюf∉L.СогласнолеммеонелинейнойВc)результатеполучено,что [xf 0·, y.f1 ,Имеемf , f , f S ] ⊇ [xL , xyfL] =∉ PL.. ПоследнеелеммеравенствоследуетПолучениеконъюнкциио нелинейнойВ результатеполучено,что [ f 0 , f1 , Mf M , Lf Lфункцию, f S ] ⊇ [x , xy ] = 2P2Согласно. Последнее равенствоследуетфункции,подставляяв функциювместовсехвсехпеременныхконстантыи отрицанияиз пункта2 теоремы4.
В силулеммы2fLдостаточностьдоказана.функции,подставляявфункциюfвместопеременныхконстантыиотрицанияLиз пункта 2 теоремы 4. В силу леммы 2 достаточностьдоказана.()(которые были получены на предыдущих шагах доказательства), можно получить(которыебылилибополученына предыдущихдоказательства),можнополучить§12.либоТеоремао максимальномчислефункций вшагахбазисеалгебрыконъюнкцию,отрицаниеконъюнкции.Однаконапервомлогики.этапеотрицание§12. Теоремаомаксимальномчислефункцийвбазисеалгебрылогики.либо конъюнкцию, либо отрицание конъюнкции.
Однако на первом этапе отрицаниеужеполучено,следовательно,всегдаполучитьбазисомконъюнкцию:Определение.Системафункций алгебрылогикиможноA ⊆ P2 называется(в P2), еслиужеполучено,следовательно,всегдаможнополучитьконъюнкцию:Определение.СистемафункцийалгебрылогикиA⊆Pназываетсябазисом(в P2), если2[fL, 0,1)1,[A]x ]=∋P[xy,xy ]. Конъюнкция получена.2;b) Получение констант 0 и 1. Имеем fS ∉ S. Согласно лемме о несамодвойственнойфункции, подставляя вместо всех переменных функции fS отрицание (которое получено в пункте a) и тождественную функцию, можно получить константы:[fS, x ] ∋ [0, 1].
Константы получены.c) Получение конъюнкции x · y. Имеем функцию fL ∉ L. Согласно лемме о нелинейнойфункции, подставляя в функцию fL вместо всех переменных константы и отрицания(которые были получены на предыдущих шагах доказательства), можно получитьлибо конъюнкцию, либо отрицание конъюнкции. Однако на первом этапе отрицаниеуже получено, следовательно, всегда можно получить конъюнкцию:[fL, 0, 1, x ] ∋ [xy, xy ]. Конъюнкция получена.В результате получено, что [ f 0 , f1 , f M , f L , f S ] ⊇ [x , xy ] = P2 . Последнее равенство следуетиз пункта 2 теоремы 4.
В силу леммы 2 достаточность доказана. §12. Теорема о максимальном числе функций в базисе алгебры логики. Определение. Система функций алгебры логики A ⊆ P2 называется базисом (в P2), если 1) [A] = P2; 2) ∀f ∈ A ([A \ {f}] ≠ P2). Теорема 13. Максимальное число функций в базисе алгебры логики равно 4. Доказательство. 1) Докажем, что из любой полной системы можно выделить полную подсистему, содержащую не более четырёх функций. Действительно, если A — полная сис тема ([A] = P2), то согласно теореме Поста в ней существуют пять функций f0 ∉ T0, f1 ∉ T1, fS ∉ S, fM ∉ M, fL ∉ L.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
