Билет 1. Основные определения. Способы задания. Операции над множествами.

Множество - Совокупность объектов определенной природы

Элементы множества - отдельные объекты, из которых состоит множество

(Бес)Конечное множество - Число элементов (бес)конечно

Множества равны, если состоят из одних и тех же элементов

Семейства множеств - Множества, содержащие в качестве элементов другие множества

Универсум - множество, содержащее все элементы какой-либо системы множеств

Операции:

1.Объединение

2. Пересечение

3. Дополнение

4.Разность

5. Симметрическая разность

Способы задания:

1.Перечисление

2.Характеризующее св-во

3.Порождающая процедура

Билет 2. Свойства операций над множествами. Диаграммы Эйлера-Венна. Декартово произведение множеств.

Св-ва:

1. Идемпотентность A^A=A, AvA=A

2. Двойное дополнение Not(Not(A))=A

3. Коммутативность A^B=B^A, AvB=BvA

4. Ассоциативность Av(BvC)=(AvB)vC, A^(B^C)=(A^B)^C

5. Дистрибутивность A^(BvC)=A^BvA^C, Av(B^C)=(AvB)^(AvC)

6. Тождество Av(NULL)=A, A^U=A

7. Дополнение AvNot(A)=U, A^Not(A)=(NULL)

8. Поглощение (A^B)vA=A, (AvB)^A=A

9. Де Морган

Декартово произведение - мн-во пар элементов, у которых первая компонента принадлежит первому множеству, а вторая - второму

Диаграммы Эйлера-Венна - геометрическая схема, с помощью которых можно изобразить отношения между подмножествами U для наглядного представления

Билет 3. Основные определения. Способы задания отношений. Композиция отношений. Свойства бинарных отношений.

Бинарное отношение - Множество упорядоченных элементов множество, подмножество декартового произведения

Область определения - множество x, для которых существует как минимум 1 y, что xRy

Область значений - Наоборот

Способы задания:

1. Перечисление

2. Правило

3. Таблица

4. Граф

Композиция отношений - Rc=AxB, Sc=BxC

T=R(комп)S Tc=AxC

(a,b)∈R, (b,c)∈S то (a,c)∈T

Св-ва бин. отношений

1. Рефлексивность - aRa для любого

2. Антирефлексивность - нет aRa

3. Симметричность - если есть aRb, то есть bRa

4. Антисимметричность - если есть aRb и bRa, то a=b

5. Асимметричность - если aRb, то нет bRa

6. Транзитивность - если aRb, bRc, то aRc

7. Антитранзитивность - если aRb, bRc, то нет aRc

Билет 4. Отношения эквивалентности. Разбиение. Отношения строгого\нестрогого порядка. Упорядоченные множества. Отношения соответствия. Функциональные отношения.

Эквивалентность - отношение эквивалентно, если оно рефлексивно, транзитивно и симметрично

Разбиение - система непустых подмножеств множества M, такое что

M=M1vM2vM3...vMn

Mi^Mj=(NULL) i!=j

Множества M1,M2..Mn - классы разбиения

Отношения строгого порядка - антирефлексивно, антисимметрично, транзитивно

Отношения нестрогого порядка - рефлексивны, антисимметричны, транзитивны

Упорядоченные множества - Упорядоченное множество (англ. ordered set) представляет собой коллекцию элементов, каждому из которых присваивается определенный ключ, отвечающий за порядок этого элемента в множестве. Бинарное отношение на упорядоченном множестве является отношением порядка.

Частично упорядоченные - мн-ва, на которых задано отношение порядка

Линейно упорядоченные - те, на которых для любых a, и либо aRb, лиибо bRa

Отношения соответствия:

1:1

1:М

М:1

М:М

Функциональные отношения - каждому x соотв. не более 1 y

Недоопределенные ф. - не каждому x соотв. y

Билет 5. Принцип математической индукции.

Д-ть:P(n)-верно

1. База индукции - верно ли P(1)?

2. Предположение(шаг индукции) -допустим, верно P(k)

3. Индукционный переход - а P(k+1) верно?

Билет 6. Высказывание. Булева алгебра. Аксиомы булевой алгебры. Теоремы одной переменной. Свойства дизъюнкции и конъюнкции.

Высказывание - выражение, относительно которого можно сделать вывод, что оно либо истинно, либо ложно

Аксиомы б.а.

1. Закон коммутативности A*B=B*A, A+B=B+A

2. Ассоциативность A(BC)=(AB)C, A+(B+C)=(A+B)+С

3. Дистрибутивность A(B+C)=AB+AC, A+BC=(A+B)(A+C)

4. Тождество A+0=A, A*1=A

5. Дополнение A+Not(A)=1, A*Not(A)=0

Теоремы одной переменной:

1. A+A=A

Доказательство:

A+A=(A+A)*1=(A+A)(A+Not(A))=A+(A*Not(A))=A+0=A

2. A*A=A

Доказательство:

A*A=A*A+0=A*A+A*Not(A)=A(A+Not(A)=A*1=A

3.A+1=1

Доказательство:

A+1=(A+1)*1=(A+1)(A+Not(A))=A+1*Not(A)=A+Not(A)=1

4.A*0=0

5. Закон Инволюции Not(Not(A))=A

Св-ва конъюнкции: Если принимает значение 1, то с обеих сторон единицы

Св-ва дизъюнкции: наоборот

Билет 7. Теорема единственности дополнения. Теорема поглощения. Теоремы склеивания, де Моргана.

Теорема единственности дополнения:

NOT(X)*X=0, X+NOT(X)=1

Пусть существует (X*):

(X*)*X=0, X+(X*)=1

Тогда Not(X)=(X*)

ДОКАЗАТЕЛЬССТВО:

NOT(X)=NOT(X)*1=NOT(X)(X+(X*))=NOT(X)*X+NOT(X)*(X*)

(X*)=(X*)*1=(X*)(X+NOT(X))=(X*)*X+(X*)*NOT(X)

Т.о. NOT(X)=(X*)

Теорема ПОглощения

x(x+y)=x

x+(xy)=x

Доказательство:

x+xy=x*1+xy=x(1+y)=x*1=x

Теорема склеивания

xy+x*Not(y)=x

(x+y)(x+not(y))=x

Доказательство:

Доказательство де-Моргана

M=A+B

Not(M)=Not(A)*Not(B)

То если MvNot(M)=1, то закон доказан

A+B+Not(A)+Not(B)=A+Not(A)+B+Not(B)=1

Аналогично для коъюнкции, но с учетом M^Not(M)=0

Билет 8. Понятие булевой функции. Способы задания булевой функции. Минтермы. СДНФ. Алгоритм построения СДНФ.

Булева функция - Произвольная n-местная функция из множества {0,1} во множество {0,1}

Способы задания

1. Аналитический

2. Таблица

3. Векторы

4. Карты Карно и Вейча?

Минтерм - функция, которая принимает единичное значение на одном наборе

СДНФ - ДНФ, представленная в виде дизъюнкций минтермов

Теорема о разложении для ДНФ

f(A1...An)=A:f(A1...1,..An)+Not(A)f(A1...0...An)

Через подстановку 0 и 1 -?

Билет 9. Дизъюнктивные и конъюнктивные формы. Разложение Шеннона. Теорема о единственности представления функции в СДНФ.

ДНФ - дизъюнкция элементарных конъюнктов

КНФ - конъюнкция элементарных дизъюнктов

разложением Шеннона или декомпозицией Шеннона по переменной называется метод представления булевой функции от переменных в виде суммы двух подфункций от (n-1) остальных переменных.

Основано на том, что т.и. можно разбить на две части, где ф. принимает 0 и 1

Пусть дана функция

Ее можно переписать как

Или же

Теорема Для любой булевой функции , не равной тождественному нулю, существует СДНФ, ее задающая.

Для любой булевой функции выполняется следующее соотношение, называемое разложением Шеннона:

.

Данное соотношение легко проверить подстановкой возможных значений ( и ). Эта формула позволяет выносить за знак функции. Последовательно вынося , ,.., за знак , получаем следующую формулу:

Так как применение данного соотношения к каждой из переменных увеличивает количество конъюнктов в два раза, то для функции от переменных мы имеем конъюнктов. Каждый из них соответствует значению функции на одном из возможных наборов значений переменных. Если на некотором наборе , то весь соответствующий конъюнкт также равен нулю и из представления данной функции его можно исключить. Если же , то в соответствующем конъюнкте само значение функции можно опустить. В результате для произвольной функции была построена СДНФ.

Билет 10. Карты Вейча. Упрощение высказываний картами. Поиск сокращенных, минимальных и тупиковых форм картами.

Карта Вейча - Представление таблицы истинности в виде карты

Сокращенная ДНФ - ни один из конъюнктов не содержится в другом

Билет 11. Макстермы. СКНФ. Построение СКНФ. Нахождение через СДНФ. Методы посроения сокращенных форм.

Макстерм - функция, которая равна 0 на одном значении

СКНФ - состоит из макстермов

Построение по СДНФ:

1. Построить СДНФ для f

2. Построить СДНФ для Not(f)

3. Построить сокращенную ДНФ для нее

4. Инвертировать по Де-Моргану

Метод получения сокращенных форм - Квайн(Петрик)

Билет 12. Унарные и бинарные булевы функции. Суперпозиции. Полные системы функций. Классы эквивалентности.

Арность - количество аргументов функции

Унарные - 1,0,x, Not(x)

Бинарные - 2^(2^n)

Суперпозиция - это функция, полученная из некоторого множества функций путем подстановки одной функции в другую или отождествления переменных.

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

Подстановка функции в функцию называется замена -того аргумента функции значением функции :

Пример: Исходные функции:

1. 

2. 

— подстановка функции вместо второго аргумента функции .

Отождествлением переменных (англ. identification of variables) называется подстановка -того аргумента функции вместо -того аргумента:

Пример: — исходная функция

— функция с отождествленными первым и вторым аргументами

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

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

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

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

Классы эквивалентности: T0,T1,S,M,L

Билет 13. Теорема Поста с доказательством.

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

Необходимость.

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

Достаточность.

Докажем, что если набор не содержится полностью ни в одном из данных классов, то он является полным.

1. Рассмотрим функцию, не сохраняющую ноль — (то есть функцию, для которой ). Тогда может принимать два значения:

   1. , тогда .

   2. , тогда .

2. Рассмотрим функцию, не сохраняющую один — (то есть функцию, для которой ). Тогда может принимать два значения:

   1. , тогда .

   2. , тогда .

Таким образом, возможны четыре варианта:

• Мы получили функцию .

Используем несамодвойственную функцию . По определению, найдется такой вектор , что . Где .

Рассмотрим , где либо , при . Либо , при . Нетрудно заметить, что . Таким образом мы получили одну из констант.

• Мы получили и имеем константу, равную , поскольку .

• Мы получили и имеем константу, равную , поскольку .

• Мы получили и .

Рассмотрим немонотонную функцию . Существуют такие , что , , зафиксируем все , тогда .

В итоге имеем три функции: , , .

Используем нелинейную функцию . Среди нелинейных членов (ее представления в виде полинома Жегалкина), выберем тот, в котором минимальное количество элементов. Все аргументы кроме двух в этом члене приравняем единице, оставшиеся два назовем и . Все элементы, не входящие в данный член, примем равными нулю. Тогда эта функция будет представима в виде , где в квадратных скобках указаны члены, которые могут и не присутствовать (остальные слагаемые будут равны нулю, поскольку в них есть как минимум один аргумент, не входящий в выбранный член, так как в выбранном члене минимальное число элементов).

Рассмотрим несколько вариантов:

1. Присутствует член . Возьмем отрицание от и член исчезнет.

2. Присутствуют три члена, без : . Составив таблицу истинности для этой функции нетрудно заметить, что она эквивалентна функции .

3. Присутствуют два члена, без . Построив две таблицы истинности для двух различных вариантов, заметим, что в обоих случаях функция истинна только в одной точке, следовательно, СДНФ функции будет состоять только из одного члена. Если это так, то не составляет труда выразить через и . Например, если функция принимает истинное значение, когда аргументы c номерами ложны, а все остальные истины, то функцию можно выразить как , где ставится перед аргументами с номерами .

4. Присутствует один член. Выразим через и аналогично пункту 3.

В итоге получим функцию , а также либо функцию , либо функцию . Поскольку функцию можно выразить через и , а функцию через и , то мы получили базис , , . Любую булеву функцию, не равную тождественному нулю, можно представить в форме СДНФ, то есть выразить в данном базисе. Если же функция равна тождественному нулю, то ее можно представить в виде .

Значит, полученные функции образуют полную систему, поскольку с их помощью можно выразить любую булеву функцию. Из этого следует, что K — полная система функций, что и требовалось доказать.

Билет 14. Алгебра Жегалкина. Единственность представления полиномом. Построение методом треугольника и Паскаля. Полином Жегалкина - представление б.ф. с помощью базиса

Теорема о единственности полинома. Заметим, что различных булевых функций от переменных штук. При этом конъюнкций вида существует ровно , так как из возможных сомножителей каждый или входит в конъюнкцию, или нет. В полиноме у каждой такой конъюнкции стоит или , то есть существует различных полиномов Жегалкина от переменных.

Теперь достаточно лишь доказать, что различные полиномы реализуют различные функции. Предположим противное. Тогда приравняв два различных полинома и перенеся один из них в другую часть равенства, получим полином, тождественно равный нулю и имеющий ненулевые коэффициенты. Тогда рассмотрим слагаемое с единичным коэффициентом наименьшей длины, то есть с наименьшим числом переменных, входящих в него (любой один, если таких несколько). Подставив единицы на места этих переменных, и нули на места остальных, получим, что на этом наборе только одно это слагаемое принимает единичное значение, то есть нулевая функция на одном из наборов принимает значение 1. Противоречие. Значит, каждая булева функция реализуется полиномом Жегалкина единственным образом.

*Метод Паскаля и треугольника*

Билет 15. Основные комбинаторные объекты. Принципы умножения и сложения (принцип включения исключений).

Комбинаторные объекты (англ. combinatorial objects) — конечные множества, на элементы которых могут накладываться определённые ограничения, такие как: различимость или неразличимость элементов, возможность повторения одинаковых элементов и т. п.

Основные объекты:

1. Битовые вектора

2. Перестановки

3. Размещения

4. Сочетания

5. Разбиение числа на неупорядоченные слагаемые (англ. partition) — представление числа в виде суммы слагаемых.

6. Разбиение множества на подмножества (англ. partition of a set) — семейство непустых множеств , где — некоторое множество индексов, если:

1. для любых , таких что ;

2. .

Принципы сложения и умножения: сложение используется, когда нужно получить один из объектов, а умножения - когда несколько сразу

Принцип включения исключений:

Билет 16. Перестановки. Размещения. Сочетания. Биномиальная теорема. Получение коэффициентов через треугольник Паскаля. Теорема Вандермонда.

Бином Ньютона:

Теорема Вандермонда:

Билет 17. Лексикографический порядок. Генерация следующего в лексикографическом порядке объекта (сочетания и перестановки).

Последовательности записаны в лексикографическом порядке (англ. lexicographical order), если для любых выполняется неравенство , где и последовательности с номерами и .

Билет 18. Определения: выборочное про-во, событие, вероятность. Свойства вероятности. Вероятность объединения событий.

Выборочное пространство - множество всех элементарных событий, связанных экспериментом

Событие - исход эксперимента

Вероятность - степень возможности наступления события

Св-ва вероятности:

1. P(A)=|A|/|S|

2. 0<=P(A)<=1

3. P(Not(A))=1-P(A)

4. P(AvB)=P(A)+P(B)-P(A^B) (Вероятность объединения событий)

5. P(Достоверное)=1

6. P(Null)=0

Билет 19. Независимые и несовместные события. Независимость попарная и в совокупности. Схема Бернулли. Теорема об осуществлении k успехов в n испытаниях.

Независимые события - наступление одного не влияет на наступление другого

Несовместные события - наступление одного приводит к невозможности наступления другого

Несовместные события и являются независимыми, тогда и только тогда если хотя бы одно из них является пустым множеством.

:

Если несовместные события являются независимыми, то выполняется . Также для несовместных событий выполняется . Следовательно . А это выполняется тогда и только тогда когда или .

:

Допустим является пустым множеством, тогда . Значит и . Следовательно события и являются независимыми.

Попарная независимость - события попарно независимы, если для любого i!=j Ai и Aj независимы

События называются независимыми в совокупности, если для любого и любого набора различных меж собой индексов имеет место равенство:

Схемой Бернулли (англ. Bernoulli scheme) называется последовательность независимых испытаний, в каждом из которых возможны лишь два исхода — «успех» и «неудача», при этом успех в каждом испытании происходит с одной и той же вероятностью , а неудача — с вероятностью .