шпоры 1 (2) (шпоры в ворде на печать)

Вопрос №1 Множества

Вопрос №2 Отображения

Вопрос №3 Отображения

Вопрос №5 Графы и матрицы

Пусть J_n={1,2,…,n} – множество n первых натуральных чисел. Назовем конечным множество, эквивалентное одному из J_n (пустое множество также считается конечным). Множество называется счетным, если оно эквивалентно множеству натуральных чисел. Бесконечное множество, не являющееся счетным, называется несчетным. Не более чем счетным называется множество, которое либо конечно, либо счетно. Два множества A и B считаются равными, если любой элемент x из множества A (xA) является множеством элемента B (xB) и наоборот. A=B(x)(xAxB). Объединением двух множеств X и Y называется множество XY, состоящее из элементов, принадлежащих хотя бы одному из множеств X или Y. Пересечением двух множеств X и Y называется множество XY, состоящее из элементов, принадлежащих каждому из множеств X и Y. Разностью множеств X и Y называется подмножество X\Y множества X, состоящее из всех его элементов, не содержащихся в Y. Симметрической разностью множеств X и Y называется множество X∆Y=(X\Y)(Y\X). Пусть выбрано некоторое «универсальное » множество U, такое, что все рассматриваемые множества являются его подмножествами. Дополнением к множеству X называется множество X=U\X. Свойства операций над множествами:

1. (XY)Z=X(YZ) 2. (XY)Z=X(YZ) (свойство ассоциативности) 3. XY=YX 4. XY=YX (свойство коммутативности) 5. (XY)Z=(XZ)(YZ) 6. (XY)Z=(XZ)(YZ) (свойство взаимной дистрибутивности) 7. XX=X 8. XX=X (свойство идемпотентности) 9. XY=XY 10. XY=XY (законы де Моргана) 11. X(XY)=X 12. X(XY)=X (законы поглощения).

Пусть X и Y – множества. Отображением f:XY из множества X в множество Y называется правило f, сопоставляющее каждому элементу xX однозначно определенный элемент f(x)Y. Множество X называется областью определения. Элемент f(x) называется образом элемента x при отображении f. Отображение f:XY называется сюръективным, если f(X)=Y, т.е., если у каждого элемента из Y есть прообраз. Это отображение называется инъективным, если из f(x)=f(x^|) следует x=x^|, т.е., если каждый элемент из области его значений имеет единственный прообраз. Отображение называется биективным (или взаимно однозначным соответствием), если оно одновременно и сюръективно, и инъективно. Характеристической функцией множества XU называется функция, определенная следующим образом: _A(x)={^{1,если xA,} _{0, если xA.} Функции _A(x) и _B(x) совпадают только тогда, когда A=B. Свойства характеристической функции: 1. _A(x)=1-_A(x) 2. _AB(x)= _A(x) _B(x)

3. _AB(x)= _A(x)+ _B(x)- _A(x) _B(x) 4. _A\B(x)= _A(x) - _A(x) _B(x) 5. _{A ∆ B}(x) = _A(x)+ _B(x)-

-2_A(x) _B(x)

Пусть X и Y – множества. Отображением f:XY из множества X в множество Y называется правило f, сопоставляющее каждому элементу xX однозначно определенный элемент f(x)Y. Множество X называется областью определения. Элемент f(x) называется образом элемента x при отображении f. Отображение f:XY называется сюръективным, если f(X)=Y, т.е., если у каждого элемента из Y есть прообраз. Это отображение называется инъективным, если из f(x)=f(x^|) следует x=x^|, т.е., если каждый элемент из области его значений имеет единственный прообраз. Отображение называется биективным (или взаимно однозначным соответствием), если оно одновременно и сюръективно, и инъективно. Пусть f:XY и g:YX – отображения. Отображение g называется обратным к f (а f – обратным к g), если fg=id_X и gf= id_Y. Если обратное отображение существует, то оно единственно. Теорема. Отображение обладает обратным тогда и только тогда, когда оно биективно. Достаточность. Пусть f:XY – биективное отображение. Определим отображение g:YX, полагая g(y)=x, если f(x)=y. Вследствие биективности f отображение g корректно определено, и ясно, что g=f^-1. Необходимость. Пусть f:XY и g:XY – взаимно обратные отображения. Пусть yY и g(y)=x. Тогда f(x)=f(g(y))=y, т.е. f сюръективно. Инъективность f также легко проверить: если x,x^|X, причем f(x)=f(x^|), то g(f(x))=g(f(x^|)), откуда e_X(x)=e_X(x^|), т.е. x=x^|. Теорема доказана.

Пусть f:XY и g:YZ – отображения. Суперпозицией называется отображение gf:XZ, определенное следующим образом: (gf)(x)=g(f(x)) (xX). Суперпозиция определена не для любых пар отображений. Но суперпозиция двух преобразований одного и того же множества всегда определена. Отображение, обратное к суперпозиции: (fg)^-1=f^-1g^-1

Неориентированный (ориентированный) граф G – это пара множеств G=<V,E>, где V – конечное множество, элементы которого называют вершинами или узлами. E – множество неупорядоченных (упорядоченных) пар на V, т.е. подмножество множества двухэлементных подмножеств V (VV), элементы которого называют ребрами (дугами). Граф (неориентированный и ориентированный) может быть представлен в виде следующей матрицы, называемой матрицей инциденции размера nm, где n – число вершин, а m – число ребер (или дуг): a_ij={^{1, если j-ое ребро инцидентно i-й вершине,}_{0, иначе.} (неориентированный граф); a_ij={^{1, если j-я дуга выходит из I-й вершины,}_{-1, если j-я дуга заходит в i-ю вершину,}^{0, иначе} (ориентированный граф). Матрица смежности вершин – это квадратная матрица B n-го порядка, элементы которой определяются для неориентированного графа следующим образом: b_ij={^{1, если i-я и j-я вершины соединены ребром,}_{0, иначе}. Для орграфа – аналогично. Для неорграфа матрица смежности вершин симметрична.

Вопрос №4 Графы

Вопрос №6 Маршруты

Вопрос №13 Бинарные отнош.

Вопрос №14 Бин. Отншон. Порядка

Неориентированный (ориентированный) граф G – это пара множеств G=<V,E>, где V – конечное множество, элементы которого называют вершинами или узлами. E – множество неупорядоченных (упорядоченных) пар на V, т.е. подмножество множества двухэлементных подмножеств V (VV), элементы которого называют ребрами (дугами). Граф (неориентированный или ориентированный) G₁=<V₁,E₁> называют подграфом графа G=<V,E> (соответственно, неориентированного или ориентированного), если V₁V и E₁E. Если V₁=V₂, то G₁ называется остовным подграфом графа G. Отображение h:V₁V₂ множества вершин графа G₁=<V₁,p₁> в множество вершин графа G₂=<V₂,p₂> называют изоморфизмом графа G₁ в G₂, если любые две вершины смежны в первом графе тогда и только тогда, когда их образы смежны во втором графе, т.е. если (u,vV₁)(up₁vh(u)p₂h(v)). Цепь в неориентированном (путь в ориентированном) графе G – это последовательность вершин v₁,v₂,…,v_n,…, такая, что для любого i v_i-()v_i+1. Простая цепь (все входящие в нее ребра попарно различны и все входящие в нее вершины, кроме, быть может, первой и последней, попарно различны) неориентированного(ориентированного) графа ненулевой длины с совпадающими концами называется циклом(контуром). Неориентированный (ориентированный) граф называют связным, если любые две его вершины соединены цепью (для любых его двух вершин u,v вершина u достижима из v или v достижима из u: u*v или v*u). Компонента неориентированного (ориентированного) графа G – это его максимальный связный подграф. Диаметр графа D(G) – это расстояние между двумя наиболее удаленными друг от друга вершинами.

Чередующаяся последовательность v₁, e₁, v₂ , e₂, ..., e_l, v_l+1(1) вершин и ребер графа, такая что e_i = v_iv_i+1 (i = ), называется маршрутом, соединяющим вершины v₁ и v_l+1 (или (v₁, v_l+1)-маршрутом). Очевидно, что маршрут (1) можно задать последовательностью v₁, v₂ , ..., v_l+1 (2) его вершин, а также последовательностью e₁, e₂, ..., e_l ребер.

Маршрут называется цепью, если все его ребра различны, и простой цепью, если все его вершины, кроме, возможно, крайних, различны. Маршрут (1) называется циклическим, если v₁ = v_l+1. Циклическая цепь называется циклом, а циклическая простая цепь — простым циклом. Число l ребер в маршруте (1) называется его длиной. Простой цикл длины l называется l-циклом, 3-цикл часто называют треугольником. Длина всякого цикла не менее трех, если речь идет о простом графе, поскольку в таком графе нет петель и кратных ребер. Минимальная из длин циклов графа называется его обхватом.

Очевидно, что любую цепь графа можно рассматривать как его подграф.

Пусть P — некоторая цепь вида (2) в графе G, v_i и v_j — входящие в нее вершины, i < j. Очевидно, что часть v_i, v_i+1, ..., v_j цепи P, начинающаяся в вершине v_i и заканчивающаяся в v_j, сама является цепью графа G. Эта цепь называется (v_i , v_j)-подцепью цепи P.

Бинарным отношением на мн-ве X называется произвольное подмн-во RX². Бин. отн. R наз. рефлексивным, если xRx для всех x. Бин. отн. R называется симметричным, если xRy тогда и только тогда, когда yRx. Бин. отношение называется транзитивным, если из xRy и yRz следует xRz. Бин. отн. R называется антисимметричным, если из xRy и yRx следует x=y. Бин. отн. называется отношение эквивалентности, если оно рефл., симм. и транз. Пусть в множестве X введено отношение эквивалентности. Подмножество [x]={yX|y~x}, состоящее из всех элементов, эквивалентных данному, называется классом эквивалентности, содержащим x. Теорема. Множество классов эквивалентности по отношению эквивалентности на множестве X есть разбиение этого множества. Обратно, если задано разбиение множества X на попарно непересекающиеся подмножества, то эти подмножества будут классами эквивалентности по некоторому отношению эквивалентности на X. Так как x[x], то X есть объединение классов [x] (xX). Покажем, что любые два класса либо не пересекаются, либо совпадают. Пусть [x][y]0, z[x][y]. Это значит, что z~x и z~y. Ввиду транз. отношения эквивалентности имеем x~y. Пусть теперь t – произвольный элемент из [x]. Это значит, что t~x. Поэтому t~y и t[y], откуда [x][y]. Аналогично доказ. и включение [y][x]. Следов., [x]=[y]. Обратно, пусть подмножества C_(A) образуют разбиение на множества X. Положим x~y тогда и только тогда, когда x и y лежат в одном и том же подмножестве C_. Полученное отношение рефл., симм. и транз., т.е. является отношением эквивалентности. Ясно, что подмножества C_(A) совпадают с классами эквивалентности по этому отношению. Отношением предпорядка назыв. бинарное отнош., кот. рефл. и транз. Если это отношение антисимм., то оно назыв. отношением порядка.

Бинарным отношением на мн-ве X называется произвольное подмн-во RX². Бин. отн. R наз. рефлексивным, если xRx для всех x. Бин. отн. R называется симметричным, если xRy тогда и только тогда, когда yRx. Бин. отношение называется транзитивным, если из xRy и yRz следует xRz. Бин. отн. R называется антисимметричным, если из xRy и yRx следует x=y. Бин. отн. называется отношение эквивалентности, если оно рефл., симм. и транз. Если это отношение антисимметрично, то оно называется отношением порядка. Пусть X упорядоченное множество. Элемент x называется наибольшим, если yx для всех yX. Если наибольший элемент существует, то он единствен. Не в каждом упорядоченном множестве существует наибольший элемент. Элемент aX называется максимальным, если из ax следует x=a. Аналогично определяется наименьший и минимальные элементы. Пусть <A,> - упорядоченное множество, и BA. Элемент aA называется верхней (соответственно, нижней) гранью множества B, если (xB) (xa) (соответственно, (xB) (xa) ). Наименьший элемент множества всех верхних граней (соответственно, наибольший элемент множества всех нижних граней) множества B называют точной верхней гранью B (соответственно, точной нижней гранью B) и обозначают supB (infB).

Вопрос №15 Мощн. множества

Вопрос №16 Сравнен. Мощн. множ

Вопрос №19 алг.сис.: группы, полугр.

Вопрос №20 алг.сис.: полукольц поля

Множества A и B называют равномощными, если между ними может быть установлено взаимно однозначное соответствие, т.е. существует биекция одного из них на другое. Если мы обозначим через |A| класс эквивалентности множества A по отношению ~, то утверждение о равномощности множеств A и B можно записать так: |A|=|B|. Тогда договоримся сам класс эквивалентности |A| называть мощностью множества A. Множество называется счетным, если оно эквивалентно множеству натуральных чисел. Свойства счетных множеств: 1. Любое бесконечное множество содержит счетное подмножество. 2. Любое бесконечное множество содержит два не пересекающихся между собой счетных подмножества. 3. Любое подмножество счетного множества конечно или счетно. Если множество конечно или счетно, его называют не более чем счетным.

4. Объединение любого не более чем счетного семейства счетных множеств счетно. 5. Если M – счетное множество, а K – его конечное подмножество, то M\K – счетно. 6. Если M – бесконечное множество, а N – его не более, чем счетное подмножество, причем множество M\N – бесконечно, то M\N~M. 7. Если M – бесконечное множество, а N – не более, чем счетное множество, то M~MN.

8. Множество 2^N всех подмножеств множества натуральных чисел не есть счетное множество.

9. Прямое произведение конечного

Множества A и B называют равномощными, если меж-ду ними может быть установлено взаимно однозначное соответствие, т.е. существует биекция одного из них на другое. Если мы обозначим через |A| класс эквивалентности множества A по отношению ~, то утверждение о равномощности множеств A и B можно записать так: |A|=|B|. Тогда договоримся сам класс эквивалентности |A| называть мощностью множества A. Множество называется счетным, если оно эквивалентно множеству натуральных чисел. Теорема. Множество всех действительных чисел отрезка [0,1] равномощно множеству всех подмножества множества натуральных чисел: [0,1]~2^N. Мощность множества 2^N называют мощностью континуума, а любое множество, эквивалентное множеству 2^N множеством мощности континуума, или континуальным. Рассмотрим теперь множество действительных чисел отрезка [0,1]. Каждое такое число представим в виде бесконечной дроби в двоичной системе исчисления. Число 1 представим в виде периодической дроби, содержащей бесконечное число единиц - 0,1(1). Конечные рациональные дроби дополним справа бесконечным числом нулей. Кроме этого, выбросим счетное множество всех периодических дробей вида 0,₀₁…_k0(1) (k1), так как каждая такая дробь представляет то же самое число, что и дробь 0,₀₁…_k1(0) (k1), где для всякого i=1,…,k a_i{0,1}. Полученное таким образом множество двоичных дробей равномощно (в силу теоремы о равномощности) множеству {0,1}^. Следствие. 1. [0,1]~(0,1). Для доказательства используем теорему: Если M – бесконечное множество, а N – его не более, чем счетное подмножество, причем множество M\N – бесконечно, то M\N~M. 2. [0,1]~(0,1)~[a,b]~(a,b). Для доказательства используем биекцию y=(b-a)x+a.

Группоидом называют любую алгебру, сигнатура кото­рой состоит из одной бинарной операции. Группоид, операция которого ассоциативна, называют полугруп­пой. Полугруппу G=<G,> называют моноидом, если в ней существует единица (нейтральный элемент) по опе­рации. Моноид G=<G,>, называют группой, если в нем для каждого элемента существует обратный по опера­ции , т.е. для каждого xG существует такой элемент x^|G, называемый обратным к x, что xx^|=x^|x=, где  - единица моноида G. Если операция коммутативна, по­лугруппа называется коммутативной. Группой назы­вается полугруппа с единицей, в которой каждый эле­мент обратим. Группу H=<H,,^-1,1> называют подгруп­пой группы G=<G,,^-1,1>, если H есть подмножество G, замкнутое относительно операции , содержащее еди­ницу 1 группы G и вместе с каждым элементом xH со­держащее элемент x^-1, обратный к x. Множество всех биекций некоторого множества A на себя с операцией композиции есть группа. Это следует из того, что отно­шение, обратное биекции, есть биекция, а также из того, что для всякой биекции f:AA имеет место равенство ff^-1=f^-1f=id_A. id_A (диагональ) – нейтральный элемент по операции композиции. Эту группу называют симметри­ческой группой множества A, а в том случае, когда мно­жество A конечно – группой подстановок множества A. Теорема Кели. G~HS_|G|. Любая конечная группа изо­морфна некоторой группе H, принадлежащей группе пе­рестановок на G. G~HS_|G|.

Кольцом (ассоциативным) называется алгебра с двумя операциями – сложением (+) и умножением (), удовлетворяющими следующим условиям: 1. <X,+> - коммутативная группа 2. <X,> - полугруппа 3. (дистрибутивность) Для любых x, y,zX имеют место неравенства (x+y)z=xz+yz, z(x+y)=zx+zy. Если существует нейтральный элемент для умножения, I, то кольцо называют кольцом с единицей. Если умножение коммутативно, то кольцо называется коммутативным. Коммутативное кольцо с I0, в котором каждый ненулевой элемент обладает обратным относительно умножения, называется полем. Кольцо <X,+,> называется булевым, если оно имеет единицу и для всех элементов xX справедливо равенство x²=x. Делители нуля – ненулевые элементы, произведение которых равно 0. Областью целостности называют коммутативное кольцо без делителей нуля. Например, кольцо целых чисел есть область целостности. Конечная область целостности является полем. Примеры конечных полей: Z_P – класс вычетов по модулю простого числа.

Вопрос №23 бул. фун., спос зад.

Вопрос №25 кон. дет. автом.

Вопрос №26 бул. фун. разлож.

Вопрос №27 алфавит, слово…

Обозначим через B множество из двух элементов: B={0,1}. Функция, определенная на множестве Bⁿ со значениями в B, называется n –арной булевой функцией. Переменную x, принимающую значения из B, будем называть булевой переменной. Из определения булевой функции f(x₁,x₂,…,x_n) следует, что для ее задания достаточно узнать, какое значение функции соответствует каждому из наборов значений аргументов (булеву вектору – табл.).

x₁…x_n-1 x_n f(x₁,…,x_n-1,x_n) Число всех булевых функций от n переменных равно 2^2ⁿ. Унарных

0 … 0 0 f(0,…,0,0) функций всего четыре.

0 … 0 1 f(0,…,0,1)

0 … 1 0 f(0,…,1,0)

0 … 1 1 f(0,…,1,1)

…………………

1 … 1 1 f(1,…,1,1)

Функция f(x₁,…,x_i-1,x_i,x_i+1,…,x_n) из P₂ зависит существенным образом от аргумента x_i, если существуют такие значения ₁,… _i-1, _i, _i+1,… _n, переменных x₁,…,x_i-1,x_i,x_i+1,…,x_n, что

f(₁,… _i-1,0, _i+1,… _n)f(₁,…_i-1,1, _i+1,… _n). В этом случае переменная x_i называется существенной. Переменная, не являющаяся существенной, называется несущественной, или фиктивной. Функции

f и g называются равными, если функцию f можно получить из g добавлением или изъятием фиктивных аргументов.

Конечный автомат – орграф, размеченный над полу­кольцом R(V) регулярных языков в алфавите V, с выде­ленной вершиной q₀ , которая называется начальной и ограниченным набором заключительных вершин.

Конечный автомат называется детерминированным, если в нем нет дуг с меткой  и из любого состояния по любому входному символу возможен переход ровно в одно состояние. Отношение 0-эквивалентности: q₁  ⁰ q₂  (q₁ F)(q₂ F) или (q₁ F)(q₂ F). Т.е. оба сост. одновр. являются или нет заключит. Отношение К-эквивалентности: q₁  ^k q₂  q₁  ^k-1 q₂ и aV(q₁,a) ^k-1 (q₁,a), k1. Т.е К-экв. состояния по лю­бому входному символу переходят из (к-1) обратно в (к-1) класс эквивалентности. Минимальный автомат – КА, содержащий наименьшее число состояний среди эквивалентных ему (т.е. реали­зующих тот же язык). Минимизация КДА состоит в разбиении множества со­стояний автомата на классы эквивалентности до тех пор, пока не получится минимальное разбиение. Тогда мы получим КДА с наименьшим числом состояний, экви­валентный исходному. Алгоритм: Строим КДА, эквивалентный исходному КА. Если в нем есть состояния, недостижимые из начального, удаляем их. Полученный КА разбиваем на классы эквивалентности (сначала на 0, потом дробим на К).

Теорема о разложении б.ф. Для б.ф. справедливо равенство: f(x₁,x₂,…,x_n)=x^1₁ x^2₂…x^m_m f(₁,…,_m,x_m+1,…x_n), где дизъюнкция производится по всем возможным наборам (₁,…,_m) Доказательство.

Для  набора (₁,…, _n) правая часть дает f(₁,…, _n), а левая-^1₁ …^m_m f(₁,…,_m, _m+1,… _n)= ^1₁ …^m_m f(₁,…  _n)=f(₁,…  _n)

ДНФ от переменных x₁,…,x_n – это формула вида K₁…K_m, где K_i –элементарная конъюнкция, содержащая некоторые из литералов из x₁,…,x_n. Когда в каждую конъюнкцию K_i входит в точности один из литералов x_j (x_j ), ДНФ называется СДНФ.

Алфавит – произвольное непустое конечное множество V={a₁ ,…,a_n }, элементы которого называют буквами или символами.

Словом или цепочкой в алфавите V называют произвольный кортеж из множества V^К (К-ой декартовой степени алфавита V) для различных К=0, 1, … .

Длина слова – число компонент кортежа.

Языком в алфавите V называется произвольное подмножество множества V*.

Множество всех языков в алфавите V, т.е. 2 ^V*, есть булеан счетного множества и имеет мощность континуума.

Операции над языками:

Соединение (конкатенация) слов: для х=х(1) х(2)… и у= у(1) у(2)… соединение ху = х=х(1) х(2)…у(1) у(2)… . Из определения следует, что конкатенация ассоциативна и множество V* всех слов в алфавите V образует моноид. Конкатенация языков L₁ и L₂ – язык L₁L₂, состоящий из всех возможных соединений слов ху, где слово хL₁, а yL₂ .

Итерация языка L - объединение всех его степеней. L* = Lⁿ, где n = 0….

Вопрос №28 двойств. бул. фун.

Вопрос №29 Классы Поста о полн.

Вопрос №30 Полином Жегалк.

Вопрос №31 Полин. Жег. неопр. коэф

Пусть f(x₁,x₂,…,x_n) – булева функция. Функция f * (x₁,x₂,…,x_n ) называется двойственной f(x₁,x₂,…,x_n), если f * (x₁,x₂,…,x_n ) = f(x₁,x₂,…,x_n).

Принцип двойственности: Функция, двойственная суперпозиции функций, равна суперпозиции двойственных функций.

Пусть Ф= f₁(x₁,…,x_i-1, f₂(x₁,…,x_m),x_i+1,…,x_n), тогда Ф*= f*₁(x₁,…,x_i-1, f*₂(x₁,…,x_m),x_i+1,…,x_n)

Доказательство: расписать Ф*, учитывая, что Ф(x₁, …,x_n )= f₁(x₁,…, x_i-1,  f₂(x₁,…, x_m), x_i+1,…, x_n)

Функция называется самодвойственной, если f (x₁,x₂,…,x_n )= f * (x₁,x₂,…,x_n ).

Если мы применим принцип двойственности к СДНФ, то получим выражение:

, а так как , то: . Полученное выражение является СКНФ.

T0 – класс ф-ий, сохр 0: f(0…0)=0

T1 – класс ф-ий, сохр 1: f(1…1)=1

S – класс всех самодвойственных ф-ий, т.е. ф-ий, совпад. Со своими двойств. ф-ями. f*=f. Ф-ия самодв. т.и.т.т., когда на взаимопротивоположн. наборах она приним. противоположн. значения.

М – класс всех монотон. ф-ий. Ф-ия монотон, если f(a1 a2 …an)<= f(b1 b2 …bn) при (a1 a2 …an)<= (b1 b2 …bn)

L – класс всех линейн. ф-ий. Лин. ф-ия – фун., выраженная в виде f(x1 x2 …xn) = a1x1 + a2x2 + … + anxn (плюс в кружочке).

Теорема Поста о функциональной полноте.

Система F={f₁, f₂, …,f_n} полна тогда и только тогда, когда она целиком не содержится ни в одном из пяти замкнутых классов: T₀, T₁, S, M, L .

Полиномом Жегалкина называется выражение вида:  _i1…is x_i1,…x_is (_i1…is B), где суммирование производится по различным наборам 1<1<…<i_s, и среди слагаемых имеется константа ₀ B, отвечающая пустому множеству.

Теорема: Любая б.ф. реализуется подходящим полиномом Жегалкина.

Доказательство: Учитывая, что тождества в булевом кольце дают возможность свободного обращения с выражениями, содержащими сложение и умножение и то, что х=х1, получим:

Последнее выражение после раскрытия дает полином Жегалкина.

Полиномом Жегалкина называется выражение вида:  _i1…is x_i1,…x_is (_i1…is B), где суммирование производится по различным наборам 1<1<…<i_s, и среди слагаемых имеется константа ₀ B, отвечающая пустому множеству.

Для нахождения коэффициентов есть смысл использовать метод неопределенных коэффициентов для чего нужно использовать таблицу истинности.

Теорема: всякую функцию можно реализовать единственным полиномом Жегалкина, т.е. ПЖ однозначно определяет БФ.

Доказательство: Поскольку число наборов переменных х1, х2, …, хn совпадает с числом подмножеств множества { х1, х2, …, хn} и равно 2ⁿ и каждый коэффициент полинома Жегалкина равен 0 или 1, то число полиномов от переменных совпадает с числом характеристических функций на множестве указанных наборов. Т. образом число полиномов в точности равно числу булевых функций от n переменных. Поскольку каждая функция реализуется полиномом (т.к. через полином могут быть получены функции стандартного базиса, через который реализуется любая б.ф. что легко показать), теорема доказана.

Вопрос №33 Пол.Жег. существ. перем

Вопрос №34 ДНФ, карты Карно

Вопрос №35 Замкн. классы: монот,лин

Вопрос №35 Теор. Поста

Полиномом Жегалкина называется выражение вида:  _i1…is x_i1,…x_is (_i1…is B), где суммирование производится по различным наборам 1<1<…<i_s, и среди слагаемых имеется константа ₀ B, отвечающая пустому множеству. Функция f(x₁,…,x_i-1,x_i,x_i+1,…,x_n) из P₂ зависит существенным образом от аргумента x_i, если существуют такие значения ₁,… _i-1, _i, _i+1,… _n, переменных x₁,…,x_i-1,x_i,x_i+1,…,x_n, что

f(₁,… _i-1,0, _i+1,… _n)f(₁,…_i-1,1, _i+1,… _n). В этом случае переменная x_i называется существенной. Переменная, не являющаяся существенной, называется несущественной, или фиктивной.Теорема: Пусть реализуемая полиномом Жегалкина функция f(x₁,x₂,…,x_n) зависит только от переменных, входящих в полином. Тогда все переменные функции f существенны. Доказательство: От противного. Пусть х_i – фиктивная переменная. Группируя все слагаемые полинома, содержащие х_i, представим функцию f в виде: f(x₁,x₂,…,x_n)=x_i g(x₁,…,x_i-1,x_i+1,…x_n) h(x₁,…,x_i-1,x_i+1,…x_n), где g и h – полиномы Жегалкина. Так как функция g не равна тождественно нулю, существует набор (₁,… _I-1, _I+1,…,_m) на котором она принимает значение 1, из чего следует, что f существенно зависит от xi, что противоречит условию. Следствие: равные функции реализуются одним и тем же полиномом Жегалкина.

Задача о минимизации ДНФ сводится к отысканию такой формы, которая содержит наименьшее число литералов( функций х или х) по сравнению с другими эквивалентными ей ДНФ.

Функция f называется импликантой g, если для любых наборов значений переменных из f=1 g=1, но не наоборот. ДНФ называется тупиковой, если удаление любой простой импликанты нарушает эквивалентность этой ДНФ исходной. Простую импликанту называют ядровой, если она покрывает некоторую импликату исходной СДНФ, не покрываемую никакими другими импликатами, т.е. на карте Карно, если мы ее удалим, возникнет непокрытая единица.ТДНФ – ДНФ без избыточных импликант, т.е. содержащая только ядровые импликаты.

Для определения МДНФ от 3 или 4 переменных можно использовать карту Карно, которая является одной из форм таблицы истинности. Процесс склейки выглядит так: на карте Карно 2, 4 или 8 соседних единиц обводятся прямоугольником, который обозначает склейку. Таким образом, мы получаем все простые импликанты исходной функции. Карты Карно для 3 и 4 переменных:

Пусть F – некоторое множество булевых функций. Замыканием [F] множества F называется совокупность всех функций из P, реализуемых формулами над F. Множество F булевых функций называется функционально замкнутым классом, если [F]=F. Функция называется монотонной, если для любых двух наборов  и  f(А₁,А₂,…,А_n)  f(В₁,В₂,…,В_n), при А В (А  В если А₁  В₁, …, А_n  В_n ). Пример: f = 0; f = 1; f = х; f = х₁х_2ъ. Класс монотонных функций обозначается через M. Доказательство замкнутости: если f(х₁,…,х_n)М и g(х₁,…,х_n)М, то f(g(х₁,…,х_n),х₂,…,х_n ) М. Пусть АВ, тогда g(А) g(В)  (g(А),a₂,…,a_n )  (g(В),b₂,…,b_n )  f(g(А),а₂,…,а_n )  f(g(B),b₂,…,b_n ) что и требовалось доказать. К классу лин. ф-ций L относят ф-ции, реализ. полиномом Жегалкина вида: ₀  ₁х₁  … _nх_n (_iB). Лемма о немонотонной функции: из любой немонотонной функции путем подстановки в нее констант и х можно получить отрицание. Доказательство: возьмем два набора А  В для которых f(А)  f(В) и которые различаются K компонентами. Меняя последовательно в наборе А 0 на 1 мы будем приближаться к В и на j замене получим, что f(А₁,…,А_j-1,0, А_j+1,…,А_n)> f(А₁,…,А_j-1,1, А_j+1,…,А_n). Положим (х)= f(А₁,…,А_j-1,х, А_j+1,…,А_n), которая и будет функцией отрицания. Лемма о нелинейной функции: из любой нелинейной функции путем подстановки в нее констант и использования отрицания можно получить конъюнкцию. Доказательство: Пусть f нелинейна, тогда она содержит хотя бы одну конъюнкцию. Пусть К=х_i1 … x_is , s>1 – самая короткая из них. Положим х_i3 … x_is = 1, а для всех х_j, не входящим в К положим х_j =0. Поэтому f примет вид: (х_i1, х_i2) = х_i1 х_i2   х_i1   х_i2  , где  ,  и  - константы, равные 0 или 1. Положим теперь (х_i1 ,х_i2 ) = (х_i1   ,х_i2  )     . При раскрытии (х_i1 ,х_i2 ) получим (х_i1 ,х_i2 )= х_i1  х_i2. Лемма доказана.

Теорема Поста о функциональной полноте.

Система F={f₁, f₂, …,f_n} полна тогда и только тогда, когда она целиком не содержится ни в одном из пяти замкнутых классов: T₀, T₁, S, M, L .

Доказательство: 1) Пусть F полна, т.е. [F]= F. Предположим, что F содержится в одном из пяти классов – обозначим его через Q, т.е. F Q. Тогда в силу свойства замыкания и замкнутости Q, получим P₂=[F] Q = Q. С другой стороны замкнутые классы T₀, T₁, S, M и L попарно различны и отличны от P₂ (P₂ – стандартный набор из И, ИЛИ и НЕ). Таким образом P₂  Q. Полученное противоречие доказывает необходимость. (Также можно показать, что существуют функции, не лежащие ни в одном классе Поста (например, штрих Шеффера), а из [F] Q следует, что всякая суперпозиция над F также лежит в Q).

2) Пусть F не содержится целиком ни в одном из 5 классов. Это значит, что в системе есть 5 функции _I, _j, _k, _l и _m, не принадлежащие этим классам. Такая подсистема будет полна:

• Пусть _I T₀T_1.Тогда мы получим либо константу 1, либо отрицание. В последнем случае возьмем несамодвойств. функцию _k S и в силу леммы о несамодв. ф-ции получим константу, а используя отрицание, получим и другую.

• Теперь, на основе леммы о немонотонной функции, мы можем получить отрицание, подставляя в _l M константы и х.

• На основе леммы о нелинейной функции мы можем получить конъюнкцию, подставляя в константы, х и отрицание в _m  L.

Таким образом, мы получили полную систему из И и НЕ. Следовательно, теорема доказана.

Вопрос №36 контактн. схемы

Задача о минимизации ДНФ сводится к отысканию такой формы, которая содержит наименьшее число литералов( функций х или х) по сравнению с другими эквивалентными ей ДНФ. Алгоритм Квайна-Мак-Клоски. 1. Операция склейки: Пусть К1 и К2 – две элементарные конъюнкции, входящие в исходную СДНФ, причем К₁=хК , К₂=хК, где К – некоторая элементарная конъюнкция. Тогда К₁К₂=хК(хК)=(хх)К=К. Процесс склейки можно выполнить, используя карты Карно, которая является одной из форм таблицы истинности. Процесс склейки выглядит так: на карте Карно 2, 4 или 8 соседних единиц обводятся прямоугольником, который обозначает склейку. Поучаем сокр. ДНФ. 2. Определение ядра. Простую импликанту называют ядровой, если она покрывает некоторую импликату исходной СДНФ, не покрываемую никакими другими импликатами. 3. Перечисление тупиковых ДНФ. ДНФ называется тупиковой, если удаление любой простой импликанты нарушает эквивалентность этой ДНФ исходной (т.е. ДНФ содержит все ядровые импликанты и не содержит ни одной избыточной). Получить ТДНФ можно, используя КНФ функцию Патрика К1… Kn. Раскрывая скобки в КНФ и применяя правило поглощения, получим ДНФ, элементарные конъюнкци которой определяют ТДНФ. 4. Отыскания среди ТДНФ минимальных ДНФ. Операцию получения сокр. ДНФ можно провести по алгоритму Блейка. Он состоит в том, что к любой ДНФ, представляющей функцию применяются следующие тождества: правило обобщенного склеивания: х К₁х К₂= хК₁ х К₂  К₁ К₂ правило поглощения: К₁  К₁ К₂ = К₁ Сам алгоритм следующий: сначала к ДНФ применяют правило обобщенного склеивания до тех пор, пока не перестанут появляться новые элементарные конъюнкции, а затем, применяют правило поглощения. В результате получаем сокращенную ДНФ.