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

Вопрос №1

Вопрос №2

Вопрос №3

Вопрос №4

Пусть 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

Бинарным отношением на мн-ве 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) совпадают с классами эквивалентности по этому отношению. Отношением предпорядка назыв. бинарное отнош., кот. рефл. и транз. Если это отношение антисимм., то оно назыв. отношением порядка.

Вопрос №5

Вопрос №6

Вопрос №7

Вопрос №8

Бинарным отношением на мн-ве 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).

Множества 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. Теорема. Множество всех отображений множества X на множество Y более мощно, чем множество X. Доказательство от противного. F(X,Y)X. f_x(t)={^{y0, xt}_{y1, x=t.} {f_x}~X. Пусть есть биекция F(x,y)X:Ф. g:XY g(x)=yФ_x(x) (Ф_x(x)=y). Мы получили противоречие.

Множества 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.

Вопрос №9

Вопрос №10

Вопрос №11

Вопрос №12

Группоидом называют любую алгебру, сигнатура кото­рой состоит из одной бинарной операции. Группоид, операция которого ассоциативна, называют полугруп­пой. Полугруппу 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|.

Группоидом называют любую алгебру, сигнатура которой состоит из одной бинарной операции. Группоид, операция ко­торого ассоциативна, называют полугруппой. Полугруппу 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. Теорема Лагранжа. Пусть G=<G,,1> - группа, а H=<H,,1>. Левым смежным классом подгруппы H по элементу aG называют множество aH={y|y=ah, hH}. Порядок конечной группы делится на порядок любой ее подгруппы. Для доказательства этого докажем сначала теорему: все левые классы смежности подгруппы H равномощны и их мощность равна мощности H. Для произвольного фиксированного aG зададим отображение _a:HaH следующим образом: _a(h)=ah. Отображение _a есть, во-первых, сюръекция, ибо xaH x=ah для некоторого hH; во-вторых, _a – инъекция, ибо из ah₁=ah₂ следует h₁=h₂ – в силу законов сокращения в каждой группе. Следовательно _a – биекция, и |aH|=|H|. В силу доказанного все левые классы смежности образуют разбиение множества на k равномощных подмножеств. Следовательно, |G|=k|H|, где k – число всех левых классов смежности подгруппы H, называемое левым индексом подгруппы H в группе 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 – класс вычетов по модулю простого числа.

Кольцом (ассоциативным) называется алгебра с двумя операциями – сложением (+) и умножением (), удовлетворяющими следующим условиям: 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. Примеры конечных полей: Z_P – класс вычетов по модулю простого числа.

Вопрос №13

Вопрос №14

Вопрос №15

Вопрос №16

Обозначим через 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 добавлением или изъятием фиктивных аргументов.

Пусть F – некоторое множество булевых функций.

Тогда формулой над множеством F считаем любую константу из F (если она там есть) и любое булево переменное. Далее, если известно, что Ф₁, … ,Ф_n (n>=1) – формулы над множеством F, а f – функция от n переменных, то выражение f есть формула над множеством F. Никаких других формул над множеством F, кроме определенных выше, не существует.

F={, , } – стандартный базис.

Теорема о разложении б.ф. Для б.ф. справедливо равенство: 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)

Теорема о разложении б.ф. Для б.ф. справедливо равенство: 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 ), ДНФ называется СДНФ.

Пусть 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 ).

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

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