Спец часть (часть 1) (3 поток) (2015) (by Кибитова) (1161601)
Текст из файла
представление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}.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
