Справочник по математике. Справочник-по-математике-в-формулах-таблицах-рисунках-учебное-по. Справочник по математике в формулах, таблицах, рисунках учебное пособие Омск 2010

• Название: Справочник по математике в формулах, таблицах, рисунках учебное пособие Омск 2010
• Анкор: Справочник по математике
• Дата: 27.06.2022
• Размер: 2.16 Mb.
• Имя файла: Справочник-по-математике-в-формулах-таблицах-рисунках-учебное-по.pdf
• Тип: Справочник; #618006
• страница: 9 из 12

Правила и формулы комбинаторики Правила комбинаторики Правило умножения Если из некоторого конечного множества объекта можно выбрать способами, а объект
b
–
2
n
способами, то оба объекта (
a
и
b
) можно выбрать
2 1
n
n 
способами
Правило сложения Если из некоторого конечного множества объекта можно выбрать
1
n
способами, а объект
b
–
2
n
способами, причем способы не пересекаются, то любой из объектов (
a
или
b
) можно выбрать
2 1
n
n способами Формулы комбинаторики Схема выбора Размещения Перестановки Сочетания Без возвращения С возвращением
m
m
n
n
A

!
!...
!
!
)
,...,
,
(
m
m
n
n
n
n
n
n
n
n
P
2 1
2 1

m
m
n
m
n
C
C
1




106 Основные понятия теории графов Понятие Пример
Граф
)
,
(
X
V
G
представляет собой непустое множество вершин


n
v
v
v
V
,...,
,
2 1

и множество ребер Х, оба конца которых принадлежат множеству V Если
)
,
(
2 1
v
v
x 
– ребро графа, то вершины v
1
и
v
2
инцидентны ребру х
Вершины
4 2
v
и
v
инцидентны ребру Два ребра, инцидентные одной вершине смежные
Ребра
5 смежные, т.к. инцидентны вершине Степень вершины
)
(v
d
графа – число ребер, которым эта вершина инцидентна. Если
)
(v
d
=0, то вершина изолированная, если
)
(v
d
=1, то висячая вершина
5
v
– висячая, вершина
6
v
– изолированная Маршрут (путь для графа G(V,X) – последовательность Длина маршрута – количество ребер в нем
Если М=v
1
x
1
v
2
x
2
v
3
x
3
v
4
x
5
v
2
,то М Маршрут замкнутый, если его начальная и конечная точки совпадают, те.
1 Незамкнутый маршрут (путь) – цепь. Цепь, в которой все вершины попарно различны, называется простой цепью Замкнутый маршрут (путь) – цикл контур Цикл, в котором все вершины попарно различны, называется простым циклом. Две вершины графа связные, если существует соединяющая их простая цепь Вершины
1
v и
3
v связные, т.к.
 Два графа изоморфны, если существует взаимно-однозначное соответствие между множествами их вершин и ребер
1
x
3
x
4
v
2
x
4
x
1
v
3
v
2
v
5
x
6
x
5
v
7
x
6
v

107 Виды графов Вид графа
Примеры Граф связный, если каждые две его вершины связные Граф полный,если каждые две его вершины соединены одними только одним ребром Граф плоский (планарный если его можно изобразить на плоскости так, что все пересечения его ребер являются вершинами графа
)
,
(
1
V
X
G
– полный, связный и планарный – плоское изображение графа
)
,
(
1
V
X
G
Граф G называется деревом, если он является связными не имеет циклов.
Граф G, все компоненты связности которого являются деревьями, называется лесом
)
,
(
3
V
X
G
– лес
Если элементы множества Х упорядоченные пары, то граф называется ориентированным или орграфом. Если
)
,
(
2 1
v
v
x 
– дуга орграфа, то вершина v
1
– начало, а вершина v
2
– конец дуги х. Дуга
)
,
(
1 1
v
v
x 
– петля Степень входа вершины орграфа – число входящих в вершину ребер, степень выхода – число выходящих из вершины ребер
Источником
называется вершина, степень входа которой равна нулю, а степень выхода положительна
Стокомназывается вершина, степень входа которой положительна, а степень выхода равна нулю Путь в орграфе – последовательность ориентированных ребер. Вершина
2
v – источник, вершина
4
v – сток. Путь :
4 3
2
v
v
v


1
x
3
x
4
v
2
x
4
x
1
v
3
v
2
v
5
x
6
x

108 Цикл – замкнутый путь Типы графов Определение Условия существования Иллюстрирующие примеры Путь цикл, содержащий все ребра графа ипритом по одному разу, называется
эйлеровым путем циклом. Граф, обладающий эйлеровым циклом путем, называется эйлеровым Критерий существования
эйлерова цикла степени всех графа четные Критерий существования
эейлерова пути граф имеет ровно две вершины нечетной степени
Есть эйлеров и гамильтонов цикл. Есть эйлеров цикл, нонет гамильтонова цикла.

109 Путь цикл, содержащий все вершины графа по одному разу, называется
гамильтоновым. Граф, обладающий гамильтоновым циклом путем, называется гамильтоновым Достаточные условия существования
1. Всякий полный граф является гамильтоновым.
2. Если граф, помимо простого цикла, содержит и другие ребра, то он также является гамильтоновым.
3. Если граф имеет гамильнов цикл, то он может иметь и другие гамильтоновы циклы Есть гамильтонов, нонет эйлерова цикла. Нет ни эйлерова, ни гамильтонова цикла Операции над графами Название операции Обозначение Определение Дополнение Объединение графов
)
,
(
)
,
(
2 2
2 1
1 1
X
V
G
X
V
G

(






2 1
2 1
,
X
X
V
V
)
2 1
2 Пересечение графов
)
,
(
)
,
(
2 2
2 1
1 1
X
V
G
X
V
G

2 1
2 Сумма по модулю
)
,
(
)
,
(
2 2
2 1
1 1
X
V
G
X
V
G

(






2 1
2 1
,
X
X
V
V
)
2 1
2 1
,
:
)
,
(
X
X
X
V
V
V
X
V
G




Cпособы задания графов
Название
Способ задания
П р им ер
Аналити-
ческий
Бинарное отношение R на множестве
 
i
v
V 
,
n
i
,
1



4
,
3
,
2
,
1

V
"
"
,
y
x
R
y
x



4
x
1
v
2
v
1
x
4
v
2
x
3
v
3
x
5
x
6
x

110 Матрица смежности графа
)
,
(
X
V
G


n
v
v
V
,...,
1















nn
n
n
n
n
a
a
a
a
a
a
a
a
a
2 1
2 22 21 1
12 11








X
v
v
X
v
v
a
j
i
j
i
ij
)
,
(
если
,
0
;
)
,
(
если
,
1
v
i
1 2
3 4
1 0
1 1
1 2
0 0
1 1
3 0
0 0
1 4
0 0
0 0 Матрица инцидент-
ности орграфа
)
,
(
X
V
G


n
v
v
V
,...,
1



m
x
x
X
,...,
1















nm
n
n
m
m
a
a
a
a
a
a
a
a
a
2 1
2 22 21 1
12 11









i
j
i
j
i
j
ij
v
x
v
в
x
v
x
a
инцидентна не если
,
0
;
заходит если
,
1
;
из исходит если 1 1 0
0 1
0 1
2 -1 1
0 0
1 0
3 0
-1 1
0 0
-1 4 0 0
-1
-1
-1 0

101 Раздел 21. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ Операции над высказываниями Высказыванием Р называется предложение, к которому возможно применить понятия истинно И или ложно Л. Пример И « Москва – столица Казахстана – Л. Название операции и обозначение Определение Таблица истинности Отрицание
(

) связка не
Высказывание
Р

(или Р ) истинно

Р ложно Р

Р ИЛЛ И Конъюнкция или
&
) связка и Высказывание Р 
истинно

истинны оба высказывания Р
Q Р И И И ИЛЛ ЛИЛ Л Л Л Дизъюнкция
(

) связка
или Высказывание Р 
ложно

ложны оба высказывания Р
Q Р И И И ИЛИ ЛИ ИЛЛ Л Импликация
(

) связка
если …, то Высказывание Р 
ложно Р истинно, а Q – ложно Р
Q Р И И И ИЛЛ ЛИ ИЛЛ И
Эквиваленция
(

или

) связка
тогда и только тогда Высказывание Р
истинно истинности высказываний Р и Q совпадают Р
Q Р И И И ИЛЛ ЛИЛ Л ЛИС помощью таблиц истинности можно составлять таблицы истинности сложных формул. Формулы эквивалентны если им соответствуют одинаковые таблицы истинности.

102 Булевы функции Булева функция, X
2
,…,X
n
) – местная функция, аргументы и значения которой принадлежат множеству {0, 1}. Если логические высказывания могут принимать значения истинно или ложно, то для булевой функции аналогами этих значений будут значения 1 или 0. Для булевых функций справедливы таблицы истинности и основные равносильности алгебры высказываний. Дополнительно вводятся операции
2 1
| Х
Х
=
2 1
Х
Х 
– штрих
Шеффера и
2 1
Х
Х 
=
2 1
Х
Х 

стрелка Пирса
X
1
X
2

X
1
X
1

X
2
X
1

X
2
X
1

X
2
X
1

X
2 2
1
| Х
Х
2 1
Х
Х 
1 1
0 1
1 1
1 0
0 1
0 0
0 1
0 0
1 0
0 1
1 0
1 1
0 1
0 0
0 1
0 0
1 1
1 1 Основные законы математической логики Название Закон относительно операции конъюнкции Закон относительно операции дизъюнкции Тавтология
х
х
х


х
х
х


Коммутативность
х
у
у
х



х
у
у
х



Ассоциативность
)
(
)
(
z
y
x
z
у
х





)
(
)
(
z
y
x
z
у
х





Дистрибутив- ность
)
(
)
(
)
(
z
x
y
x
z
y
x






)
(
)
(
)
(
z
x
y
x
z
у
х






Законы де Моргана
y
x
y
х



y
x
y
x



Законы поглощения Операции си
х
х

 1
;
0 0 х 1 х
х
х

 Закон дополнительности х
х
Закон склеивания Закон ортогонализации Закон импликации
y
х
у
х



Инверсия
x
x 

103 Пример. Доказать с помощью таблиц истинности справедливость формул де Моргана
y
x
y
x



x
y
y
x 
y
x 
x
y
y
x 
0 0
0 1
1 1
1 0
1 1
0 1
0 0
1 0
1 0
0 1
0 1
1 1
0 0
0 0 Закон справедлив, так как совпадают столбцы истинности для формул
y
x 
и
y
x Формы представления булевых функций Пусть
,
,
1 0
x
x
x
x


 
1
,
0








0
если
,
1
если
,



x
х
х
– литера. Совершенные формы Формула Совершенная конъюнктивная нормальная форма (СКНФ)– конъюнкция конституент нуля













i
n
n
i
n
i
f
n
x
x
x
x
f







1 которых на
)
,...,
,
(
наборам всем по 1
2 1
2 Совершенная дизъюнктивная нормальная форма (СДНФ) – дизъюнкция конституент единицы













i
n
n
i
n
i
f
n
x
x
x
x
f







1 которых на
)
,...,
,
(
наборам всем по 1
2 1
2 Пример Элементарные конъюнкции
Элементарные дизъюнкции 0 1
y
x
y
x



0 0
0 1 0
y
x
y
x
y
x





0 1
1 0
1 0 0
y
x
y
x
y
x





1 0
0 1
1 1 0
y
x
y
x
y
x





0 0
1 1
СДНФ:

)
,
(
y
x
f
y
x 
,
СКНФ:

)
,
(
y
x
f
(
y
x 
)

(
y
x 
)

(
y
x 
).

104 Раздел 22. ТЕОРИЯ ВЕРОЯТНОСТЕЙ Случайные события и действия над ними Событие – явление, которое может произойти или не произойти при осуществлении определенной совокупности условий. Событие называется достоверным (  ), если оно обязательно произойдет в результате данного опыта. Событие называется невозможным, если оно заведомо не произойдет в результате данного опыта. Два события называются несовместными, если появление одного из них исключает появление другого события водном и том же опыте. В противном случае события называются совместными Полная группа событий ( ) – это совокупность единственно возможных событий испытания. Действия над событиями Название операции Определение Теоретико- множественная трактовка операций Сумма Событие C состоит в наступлении хотя бы одного из событий (или
A
, или
B
, или
A
и
B
вместе)
Произве- дение
B
A
C


Событие С состоит в совместном наступлении событий (
A
и
B
одновременно)
Разность
B
A
C


Событие С означает, что происходит событие
A
, ноне происходит событие Противоположное событие С Событие С происходит тогда и только тогда, когда не происходит событие
A

A
B
С

A
B
С

A
B

105 Вероятность события
1) Классическое определение вероятности
,
)
(
n
m
А
Р

здесь m  число случаев, благоприятствующих событию A ;
n  общее число равновозможных и попарно несовместных случаев. Следствия. АР Р Р,
 
 
A
P
A
P

 1 2) Статистическое определение вероятности.
n
m


– относительная частотасобытия, где m  число случаев наступления события (частота n  общее число испытаний. Статистической вероятностью события A в данном испытании называют число
)
( АР, около которого колеблется относительная частота события A при достаточно большом числе испытаний. Теоремы сложения и умножения вероятностей Теоремы сложения Теоремы умножения Если,
B
 несовместные события, то. Если,
B
 совместные события, то. Если
n
A
A
A
,...,
,
2 1
образуют полную группу событий, то
,
1
)
(
)
(
)
(
2 1




n
A
P
A
P
A
P
4. Если
n
A