Спец часть (часть 1) (3 поток) (2015) (by Кибитова) (Ответы на спец часть)

представлениеf (x1 ,!, xn ) =&(σ 1 ,σ 2 ,!,σ n )(xσ11)∨ x2σ 2 ∨ ! ∨ xnσ n .f (σ 1 ,σ 2 ,!,σ n )= 01.Теоремао полнотесистемфункцийалгебре логики. полноты).§3. ПолныеПостасистемы.Примерыполныхсистем (св доказательством2006 г. Вопросы госэкзамена (дополнительная часть). Для кафедр АСВК, системногопрограммированияи алгоритмическихязыков алгебры логики A называется полнойОпределение.Множество функций2006 г. Вопросы госэкзамена (дополнительная часть). Для кафедр АСВК, системного системой(в P2), если любую функцию алгебры логики можно выразить формулой над A.программирования и алгоритмических языковСистемаA = {∨,систем&, ¬} является1. ТеоремаТеорема3.Постао полнотефункцийполной.в алгебре логики.Доказательство.

Если функция алгебры логики f отлична от тождественного нуля, то f21.ТеоремаПостасистем функцийв алгебрелогики.ОпределениеПустьA оPполноте. Тогда замыканиемA называетсямножествовсех функцийалгебрылогики,выражаетсяв1. видесовершеннойдизъюнктивнойнормальнойформы,в которуювходятлишь2дизъюнкция,Если жеf ≡ 0, то fмножество= x[A].⋅ x . Теоремадоказана.которыеможно1.конъюнкциявыразитьнадзамыканиемA.

ЗамыканиекакОпределениеПусть AформуламиPи .отрицание.ТогдаAобозначаетсяназываетсявсех функцийалгебры логики,Лемма2.ЕслисистемаA—полная,илюбаяфункциясистемыAможетбытьвыраженакоторые можновыразить формулами над A. Замыкание обозначается как [A].Свойствазамыкания:формулой над некоторой другой системой B, то B — также полная система.Свойства1)Доказательство.[A]замыкания:A;Рассмотрим произвольную функцию алгебры логики f (x1, …, xn) и две⊇1)[A]A; A = {g1, g2, …} и B = {h1, h2, …}.

В силу того, что система A полна, функсистемыфункций:2) A ⊇B ==> [A] ⊇[B], причём, если в левой части импликации строгое вложение, то из него вовсе], гдеция 2)f можетбыть[A]выраженав виденей: f строгое(x1 ,!, xвложение,g 2 из,!негоA B ==>[B], причём,если вформулылевой частинадимпликациивовсеn ) = ℑ[g1 , тоне следует строгое вложение в правой части — верно лишь A B ==> [A][B];g i = ℜ i [неh1 ,следуетh2 ,!], строгоето естьвложениефункцияв fправойпредставляетсяв виде, xn [A]) = ℑ⊇[ℜ[B];части — вернолишь Af (x1 B,!==>1 , ℜ 2 ,!], иначе3)[[A]]=[A].говоря,можетбыть представлена формулой над B. Перебирая таким образом все функции3) [[A]]= [A].алгебры логики, получим, что система B также полна. Лемма доказана.ТеоремаСледующиесистемыявляютсявполной,P2:еслиеслиОпределение2.2.4.СистемафункцийалгебрылогикиA называетсяполной,[A] =[A]P2. = P2.ОпределениеСистемафункцийалгебрылогикиA полныминазывается1) {x ∨ y, x };2) {x ⋅ 3.y, Пусть}; AA P2P.

Тогда2ОпределениесистемаA называетсязамкнутымклассом,если еслизамыканиеA AОпределение3.xПусть. ТогдасистемаA называетсязамкнутымклассом,замыкание3) {x | y};совпадаетсссамимсамимA:A:[A][A]= =A.A.совпадает4) {x · y, x ⊕ y , 1}.Доказательство. 1) Известно (теорема 3),что система A = {x ∨ y, x ⋅ y, x } полна. Пока2⊂⊇⊇⊂⊇⊃ ⊃⊇⊂⊂Утверждение. Пусть A — замкнутый класс, ≠A ≠2 P и B ⊂ A. Тогда B — неполная система(подмножествонеполнойнеполной системыбудетбудеттакженеполнойсистемой).(подмножествотакженеполнойсистемой).лучаем,что x ⋅ y = x ∨ системывыражаетсячерез дизъюнкцию и отрицание, иy , то есть конъюнкцияДоказательство.

B ⊂ A ==> [B] ⊂ [A] = A ≠ P2 ==> [B] ≠ P2.Следовательно, B — неполная система.Доказательство.B A ==>[B] [A] = AформуламиP2 ==> [B]над≠ системойP2. Следовательно,B — неполная≠всефункции системыA выражаютсяB. Согласнолемме система.2 системаУтверждениедоказано.B полна.⊂Утверждение.ПустьA — замкнутыйP и B A. ТогдаB — неполнаясистемаx ⋅ y = x ∨ y пожем,что полнасистемаB = {x ∨класс,y, x}.AДействительно,из законаде Моргана⊂Утверждение доказано.⊂2) Аналогично пункту 1: x ∨ y = x ⋅ y ⇔ x ∨ y = x ⋅ y и из леммы 2 следует истинностьТеорема. Класс T0 = {f (x1, …, xn) | f (0, …, 0) = 0} —замкнутый.утвержденияТеорема.КласспунктаT0 =Пусть{f (x2.1,{f(x…, x,..,x(0,(y…,,...y0) = 0}),…,g—замкнутый.n) | f),gДоказательство.n(yn1,…,yn,mn)} ⊂ T0.

Рассмотрим3) x | x = x , x ⋅ y = x | 1y = n(x |1 y )11| (x |1,m1y ) и согласносистема полна.Доказательство.Пусть {f(x1,..,x,...y1,m1n(y),…,g,…,yn,mn)}леммеT0.2Рассмотримn),g1(y11),…,gn(yn1функциюh(yпеременныхфункций gi1,…,yr ) = f(g1(y11,…,y1,m1n1,…,ym,nn)). Среди4) x = x ⊕ 1 и согласно лемме 2 система полна.функциюh(y1,…,yf(g1(y11,…,y1,m1поэтому),…,gn(yn1в,…,yпеременныхфункцийgi всемогутТеоремавстречатьсякачествепеременныхфункцииh возьмёмr )и=одинаковые,m,nn)).

Средидоказана.различныеиз них.и Тогдаh (0, …,поэтому0) = f (gв 1качестве(0, …, 0),переменных…, gn(0, …,функции0)) = f(0,h …,0) = 0все, следовательно, функциямогутвстречатьсяодинаковые,возьмёмh такжесохраняетноль.hРассмотрен(без переменныхкачествеполиномом.аргументов).§4.ТеоремаЖегалкинафункцииалгебры влогикиразличныеиз них.Тогда(0, …,о0)представимости= f только(g1(0, …,частный0), …, gслучайn(0, …, 0)) = f(0, …, 0) = 0 , следовательно, функцияпосколькуноль.тождественнаяфункциясохраняетподстановкапеременныхhОднако,такжесохраняеттолькочастныйслучайноль,(безпеременныхпеременных впростыхаргументов).эквивалентнаОпределение1.РассмотренМонотоннойконъюнкциейотxкачестве1,…, xn называется любоеподстановкетождественнойфункции,теоремадоказана.Однако,посколькутождественнаяфункциясохраняетноль, подстановка простых переменных эквивалентна⊂выражение вида xi1 ⋅ xi2 ⋅ xi3 " xis , где s ≥ 1, 1 ≤ ij ≤ n ∀j = 1, 2, …, s, все переменные различнытождественнойфункции, теорема доказана.(iподстановкеj ≠ k);j ≠ ik, еслиТеорема.КлассT1 =либо{f (x1просто, …, xn) |1.f (1, 1, …, 1) = 1} замкнут.Доказательство повторяет доказательство аналогичной теоремы для класса T0.Теорема.

Класс T1 = {f (x1, …, xn) | f (1, 1, …, 1) = 1} замкнут.Доказательствоповторяеталгебрыдоказательствотеоремы длялинейной,класса T0. еслиОпределение. Функциялогикианалогичнойf(x1, …, xn) называетсяf (x1, …, xn) = a0 ⊕a1x1 ⊕… ⊕anxn, где ai ∈ {0,6 1}.

Иными словами, в полиноме линейной функции нетОпределение.Функция алгебрылогики f(x1, …, xn) называется линейной, еслислагаемых, содержащихконъюнкцию.f (x1, …, xn) = a0 ⊕a1x1 ⊕… ⊕anxn, где ai ∈ {0, 1}. Иными словами, в полиноме линейной функции нетТеорема. КлассL замкнут.слагаемых,содержащихконъюнкцию.Доказательство. Поскольку тождественная функция — линейная, достаточно рассмотреть только случайподстановкиТеорема.Классв формулыL замкнут.функций: пусть f (x1, …, xn) L и gi L.

Достаточно доказать, что f (g1, …, gn) L.Действительно, еслине учитыватьслагаемыхс коэффициентамиai = 0, то всякуюлинейнуюДоказательство.Посколькутождественнаяфункция— линейная, достаточнорассмотретьтолькофункциюслучай∈∈∈hфункциютакжевстречатьсясохраняет(безпеременныхпеременныхв качествеh(y1,…,yноль.f(gРассмотрен),…,gnв(yчастный)).Средиgвсеr и) =1(y11,…,yпоэтому1,m1толькоn1,…,ym,nnслучайi аргументов).могутодинаковые,качествепеременныхфункции hфункцийвозьмёмОднако,посколькутождественнаяноль,подстановкапростыхэквивалентнамогутвстречатьсяодинаковые,в сохраняеткачествеh0)возьмёмвсеразличныеиз них.

иТогдаh (0, …, поэтому0)функция= f (g1(0,…, 0), …,переменныхgn(0, …,0))функции= f(0, …,= 0 ,переменныхследовательно,функцияразличныеизних.Тогдаh(0,…,0)=f(g(0,…,0),…,g(0,…,0))=f(0,…,0)=0,следовательно,функция1nподстановкетождественнойфункции,теоремадоказана.h также сохраняет ноль. Рассмотрен только частный случай (без переменных в качестве аргументов).hОднако,также сохраняетРассмотренфункциятолько частныйпеременныхв качествеаргументов).посколькуноль.тождественнаясохраняетслучайноль,(безподстановкапростыхпеременныхэквивалентнаОднако,посколькутождественнаяфункциясохраняетноль,подстановкапростыхпеременныхэквивалентнаподстановкетождественнойТеорема.КлассT1 = {f (x1, …,функции,xn) | f (1, теорема1, …, 1) доказана.= 1} замкнут.подстановке тождественной функции, теорема доказана.Доказательство повторяет доказательство аналогичной теоремы для класса T0.Теорема. Класс T1 = {f (x1, …, xn) | f (1, 1, …, 1) = 1} замкнут.Теорема.Класс повторяетT1 = {f (x1, доказательство…, xn) | f (1, 1, …,1) = 1} замкнут.Доказательствоаналогичнойтеоремы для класса T0.Определение.Функцияалгебрылогикиf(x,…,xn) называется1Доказательство повторяет доказательство аналогичнойтеоремылинейной,для классаеслиT0.fОпределение.(x1, …, xn) = a0 Функцияanxn,f(xгде1, …,ai x{0,1}.