Shpori_eshe
.doc|
1. Множества. Операции над множествами. Булева алгебра множеств. 1.1 Булева алгебра множеств
Основными
понятиями этой главы являются понятия
множества и элемента множества (эти
понятия считаем неопределяемыми).
Синонимами слова множество являются
слова совокупность,
набор, коллектив и т.д. Множества мы
будем обозначать большими буквами
латинского
алфавита (X,
У, Z,...),
элементы множества малыми буквами
(х,
у, z,...).
Принадлежность элемента х
множеству
X
(неопределяемое понятие) будем
обозначать х
Определение 1.1. Множество X является подмножеством множества Y (обозначим
X
Определение
1.2. Множества
Х и Y
равны (X
= Y)
тогда и только тогда, когда X
Будем
считать, что мы выбрали некоторое
достаточно большое множество, называемое
универсальным,
за пределы которого мы не будем
выходить. Понятие универсального
множества,
обозначим его U
также
неопределяемое, но любое рассматриваемое
нами множество X
удовлетворяет условию: X
Определим следующие операции над множествами:
объединением
двух
множеств Х и Y
называется множество Х
Определение
1.3. Назовем
пустым
множеством (множеством,
в котором нет ни одного элемента)
множество Ø = Рисунки, интерпретирующие операции над множествами, называются диаграммами (кругами) Виенна.
Объединение Пересечение Дополнение
Теорема 1.4. Множества относительно операций дополнения, объединения и пересечения удовлетворяют следующим равенствам
4.
X
8.
9.
13.
X∩U
= X;
14.
X
Все эти равенства следуют непосредственно из определения и демонстрируются с помощью кругов Виенна. Множество с операциями, удовлетворяющими 19 приведенным выше равносильностям, называется булевой алгеброй; сами операции в этом случае называются булевыми. Из теоремы 1.4 следует, что множество всех множеств образует булеву алгебру относительно операций дополнения, объединения и пересечения. Заметим, что в дальнейшем мы будем рассматривать и другие множества, образующие булеву алгебру. Кроме булевых, над множествами определяются следующие операции.
|
3. Конечные множества. Правила суммы для конечных множеств. Комбинаторика - это раздел математики, посвященный способам подсчета числа элементов в конечном множестве. В этом параграфе все множества предполагаются конечными, то есть в них конечное число элементов. Будем обозначать |Х| число элементов множества X. В качестве аксиом в комбинаторике принимаются следующие:
Если |Х| = п, то элементы множества X можно пронумеровать, то есть определить биективное отображение φ : {1,2,...,п}→ Х и обозначить φ(1) = х1 φ(2) = х2,..., φ(п) = хп. Ясно, что нумерация не однозначна.
Теорема
1.19. Пусть
X
uY
-
конечные
множества и X
∩
Y
= Ø.
Тогда
|X
Доказательство.
Действительно,
если X
= {х1,х2,
...,хп},
Y
= {у1,у2,
...,ут},
то
X
{х1, ...,хп, у1,..., ут}. (Мы пронумеровали множества X и Y и воспользовались тем, что
xi
≠ xj
для любых
i
Теорема
1.20 (Правило суммы). Пусть
X
u
Y
- конечные множества. Тогда |X
Доказательство.
Очевидно,
что X
Теорема 1.21. Пусть A1,A2,... ,Ап - конечные множества. Тогда
|A1
- (|A1 ∩ A2| + |A2 ∩ A3| + . . . + |An−1 ∩ An|)+ (|A1 ∩ A2 ∩ A3| + . . . + |An−2 ∩ An−1 ∩ An|)+ . . . + (−1)n−1 |A1 ∩ A2 ∩ . . . ∩ An| . Теорема доказывается с помощью индукции и использования предыдущей теоремы.
Задача. В студенческой группе 25 человек. 14 студентов изучают английский язык, остальные 16 студентов изучают немецкий язык. Сколько студентов изучают два языка: английский и немецкий?
Решение.
Обозначим
через X
множество студентов, изучающих
английский язык, через Y
- множество
студентов, изучающих немецкий. Тогда
|Х| = 14, |Y|
= 16,
|Х
4. Декартово произведение множеств. Количество элементов в декартовом произведении конечных множеств.
Определение
1.22. Декартовым
произведением двух множеств X
uY
называется
множество пар (х,у)
таких,
что х
Итак
X
× Y
= {(х,у) | х
Определение 1.23. Декартовым произведением п множеств {Х1,Х2, ...,Хп} называется множество
X1
× X2
× ... × Xn
= {(x1,x2,...,xn)
| xi
то есть множество упорядоченных строк из п элементов. Заметим, что множество X × X × ... × X обычно обозначают Хп. Теорема 1.24. Если X u Y - конечные множества, то X × Y - конечное множество и |Х × Y| = |Х| ∙ |Y|. Доказательство. Зафиксируем в X нумерацию, то есть X = {х1,х2, ...,хп}. Тогда
X
×
Y
=
По
правилу суммы |Х × Y|
= Следствие. Если Х1,Х2, ...,Хп - конечные множества, то |Х1×Х2×...×Хп| = |Х1|∙|Х2|∙...∙|Хп|
Задача. Из города А в город В ведет 3 дороги, из города В в город С - 4 дороги. Сколько различных дорог ведет из города А в город С ? Решение.
Обозначим
через X
множество
дорог из А
в
В,
Y
- множество
дорог из В
в
С.
Тогда
X
= {х1,x2,хз}
, Y
=
{y1,y2,yз}.
Каждая дорога из А
в
С
является
парой (xi,yj),
где
xi
|
6. Множество инъективных отображений: In YX и |In YX|. 7. Множество биективных отображений Bi YX и |Bi YX| Определение 1.27. Пусть X и Y непустые множества. Отображение f : X → Y называется иньективным, если из условия х1 ≠ х2 (х1, х2 - любые элементы множества X) следует, что f{x1) ≠ f(x2). Множество всех инъективных отображений обозначим InYX Теорема 1.28. Пусть X uY - конечные непустые множества. Тогда l)InYX ≠ Ø тогда и только тогда, когда |Y| > |Х|; 2) если |Х| = |Y|, то InYX = BiYX. Доказательство. Пусть X = {x1,x2 ,…,хт} и Y = {y1,y2 ,…,ym}. Докажем =>. Итак, InYx ≠ Ø. Тогда существует инъективное отображение f : X → У.
Следовательно
f(X)
= {f(x1),
f(x2),…,
f(xm)}
Пусть
теперь п
>
т. Тогда
мы можем построить такое отображение
из множества X
в множество Y:
f(xi)
= уi
если
i 2)Очевидно, что, если п = m, то любое инъективное отображение будет биективным. Теорема 1.29. Пусть X ,Y - конечные непустые множества и |Y| > |Х|. Пусть |Х| = т, |Y| = п. Тогда |InYX| =n ∙ (п- 1) ∙ ... ∙ (п – т + 1)
Доказательство.
Пусть
X
= {х1,х2,...
,хт},
Y
= {у1,
y2,,…,
уп}.
Любое
отображение f
: X
→
Y
определяется
тем, куда попадет каждый элемент
множества X,
то есть набором элементов {f(x1),
f(x2),...,
f(xm)}
из
множества Y.
При
этом отображения f
и g
различны,
если f(xi)
≠
g(xi)
хотя
бы для одного i
Так как мы рассматриваем инъективные отображения множества X в множество Y, то два разных элемента множества X при любом отображении попадут в две разные ячейки. Задача о нахождении InYX превращается в задачу о нахождении количества способов размещения элементов {х1,х2 ,..., хт} по п различным ячейкам. Зафиксируем элемент х1. Существует п различных способов размещения этого элемента, так как он может попасть в любую из ячеек {y1, у2 ,...,уп}. Предположим, что элемент х1 в ячейку yj. Тогда элемент x2 может попасть при размещении в любую ячейку, за исключением уj. Таким образом получаем п ∙ (п — 1) различных способов размещения элементов {х1,x2}. При размещении элементов {х1, x2, х3} мы получаем п ∙ (п — 1) ∙ (п — 2) различных способа размещения, так как элемент x3 можно разместить в любой из (п — 2) ячеек (две ячейки уже заняты элементами х1 и x2). Продолжая этот процесс, получаем, что число различных размещений т элементов по п ячейкам вычисляется по формуле: n ∙ (п- 1) ∙ ... ∙ (п – т + 1).
В
комбинаторике это число обозначается
Следствие. Пусть X и Y такие множества, что |Х| = |Y|. Если обозначить BiYX множество всех биективных отображений из множества X в множество Y, то |BiY X| = n! Доказательство. Действительно, если существует биективное отображение из множества X в множество Y, то |Х| = |У| = n |BiY X |= n!/(n-m)! = п!. Заметим, что в этом случае BiYX = InYX. Каждое биективное отображение множества X = {х1,х2,..., хп} в множество Y = {y1,y2,,…, уп} является некоторым размещением элементов {x1, x2,..., хп} по ячейкам {у1, у2,..., уп}, то есть некоторой перестановкой элементов множества X. Число всех перестановок п различных элементов обозначают Рп, таким образом Рп = п!. Задача. В кабину лифта девятиэтажного дома вошли 4 пассажира. Сколько существует способов разгрузки лифта, если каждый пассажир может выйти на любом из 8 этажей, но при этом на любом этаже может выйти не более одного человека? Решение. Пусть X - множество пассажиров, Y - множество этажей. Каждый способ разгрузки лифта в нашей задаче - это некоторое инъективное отображение множества X в множество Y: два разных пассажира обязательно выйдут на двух разных этажах. Следовательно число различных способов разгрузки лифта совпадает с числом различных инъективных отображений из множества X в множество Y и равно |InYX|=8!/(8-4)!= 8∙7∙6∙5= 1680. Задача. В аудитории 50 мест. Сколько существует способов размещения в аудитории 1) студенческой группы из 25 человек; 2) студенческого потока из 50 человек? Решение. Пусть X - множество студентов, Y - множество мест в аудитории. Тогда в случае 1) количество различных способов размещения студентов в аудитории равно |InYX| =50!/25!. В случае 2) количество различных способов размещения студентов в аудитории равно |BiYX| = 50!. Рассмотрим следующую задачу: сколькими способами из конечного множества X такого, что |Х| = п, можно выбрать m-элементные подмножества (m < п)?
Пусть
X
= {х1,х2,...,
хп}.
Рассмотрим
множество Т
=
{1,2,..., m}
и множество всех инъективных отображений
из Т
в
X.
Количество
таких отображений равно |InYX|
= n!/(n-m)!.
Заметим,
что каждое инъективное отображение
f
: Т
→
X
выделяет
некоторое подмножество множества
X.
А
именно, если f(j)
= xij
при
j
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Очевидно, что имеют место следующие равенства:
1)Х\Ø
= Х; 2) X\U = Ø;
3) Ø\Х
= Ø;
4)Х\Х=
Ø;5)U\X
=
7) X
Δ
U
=
Рассмотрим более подробно свойства подмножеств данного множества.
Теорема
1.7. Пусть
X
и Y
-
множества.
Тогда X
Теорема 1.8. Пусть X, Y, Z - множества. Тогда:
Доказательства приведенных выше теорем следуют непосредственно из определений. Замечание: понятия коммутативности, ассоциативности, дистрибутивности, рефлексивности, транзитивности и антисимметричности будут подробно рассмотрены в последующих главах этой книги.
2. Отображения множеств. Типы отображений. Композиция. Обратимость отображений. Определение 1.9. Пусть X и Y - множества. Отображением f из множества X в множество Y мы будем называть правило, по которому каждому элементу х множества X ставится в соответствие вполне определенный (единственный) элемент y = f(x) множества Y. Обозначать данное отображение будем f: X → Y. Заметим, что отображение надо обязательно понимать как набор из трех элементов (X, Y, f), где X и Y - множества, f - закон.
Определение
1.10.
Пусть f:
X
→
Y
-
отображение,
А
1)
образом множества А
при отображении f
называется множество
f(A)=
{f(x
) | x
2)
прообразом
множества В
при отображении f
называется множество f
-1
(B)
=
{x
Теорема
1.11.
Пусть
f
: X
→
Y
- отображение;
А1,
А2
1)
f(A1
3)
f(A1
∩
A2)
Доказательство.
Приведем
доказательство утверждений 1) и 3),
утверждения 2) и 4) доказываются
аналогично 1). Итак, пусть у
Пример. Пусть f: R→R такое отображение, что f(x) = sin x; A1 = [0,π], А2 = [2π,3π]. Тогда
А1
∩
А2
= Ø,
следовательно и f(A1
∩
А2)
= Ø
но f(F1)
∩
f(А2)
= [0,1]
Определение 1.12. Отображение f : X → Y называется инъективным, если для любых x1 ≠ x2 из множества X следует, что f(x1) ≠ f(x2). Определение 1.13. Отображение f : X → Y называется сюрьективным, если для любого элемента у из множества Y существует непустой прообраз, то есть f -1(y )≠ Ø Определение 1.14. Отображение f : X → Y называется биективным, если оно инъективно и сюръективно. Примеры. Отображение f : R → {0,1} такое, что f(n) = (1+(-1)n)/2 является сюръективным, но не инъективным. Заметим, что множество {0,1} обычно обозначают Е2.
Определение 1.15. Пусть f : X → Y, g : Y → Z - отображения, тогда композицией этих отображений называется отображение g о f : X → Z такое, что для любого элемента х из множества X его образ в множестве Z определен следующим образом (g o f)(x) = g(f(x)). Теорема 1.16 (ассоциативность композиции отображений). Если f : X → Y, g : Y → Z, h : Z → V — отображения, то справедливо следующее равенство: h о (g о f) = (h о g) о f.
Доказательство.
Действительно,
для любого х
(h o (g o f))(x) = h((g о f)(x)) = h(g(f(x))), ((h о g) о f)(x) = (h о g)(f(x)) = h(g(f(x))). Определение 1.17. Тождественным отображением множества X на себя называется отображение eX : X →X такое, что для любого х из множества X выполняется равенство eX(x) = х. Теорема 1.18. Если f : X →Y - биективное отображение, то существует такое биективное отображение g : Y→X, что: 1) для любого элемента х из множества X вып-ся равенство х = (д о f)(x), то есть g о f = еХ, 2)для любого элемента у из множества Y вып-ся равенство у = (f о д)(у), то есть f о g = еY, Отображение g в этом случае называют обратным отображением к отображению f и обозначают f -1. Доказательство. Искомое отображение f : Y → X определим следующим образом: g(у) = х, где х прообраз элемента у в множестве X. Этот прообраз существует и единственен для любого элемента у из множества Y, так как отображение f - биективно. Таким образом отображение g определено, и биективность его очевидна. Из определения отображения g получаем 1) g(f(x)) = х. Аналогично выполняется 2) (f оg)(у)= f(g(y))= f(x) = y |
5. Множество YX, и количество элементов |YX| в этом множестве. Определение 1.25. Пусть X и Y - непустые множества. Множество всех отображений из X в Y назовем множество степень и обозначим YX, то есть YX = {f | f : X → Y} . Теорема 1.26. Пусть X uY - конечные непустые множества. Тогда |YX| = |Y||X|.
Доказательство.
Для
доказательства теоремы применим
индукцию по количеству элементов
в множестве X.
Пусть
|Х|
=
1, то есть X
= {х},
Y
=
{y1,y2,…,ym}.
Каждое отображение f
: X
→
Y
определяется тем, куда попадет элемент
х.
В
этом случае все различные отображения
из множества X
в
множество Y
можно
просто перечислить: f1
- такое отображение, что f1(x)
=
y1;
f2
-
такое, что f2
(x)
= у2;
...;
fm
- такое,
что fm(x)
= уm.
Ясно,
что все эти отображения разные и |YX|
= m1
=
|Y||X|.
Предположим далее, что
для
любого множества X
такого,
что |Х|
< п. Пусть
теперь |Х|
= п, то
есть X
= {x1,x2
,…,xn}.
Множество
YX
разобьем
на непересекающиеся подмножества: YX
= A1
Тогда |Y X| = m · mn−1 = mn = |Y ||X|, что и требовалось доказать. Задача. В кабину лифта девятиэтажного дома вошли 4 пассажира, каждый из которых может выйти на любом из 8 этажей. Сколько существует способов разгрузки лифта? Решение. Обозначим через X множество пассажиров, через Y - множество этажей, на которых они могут выйти. Тогда каждая разгрузка лифта - это некоторое отображение f : X —> Y (каждому пассажиру поставлен в соответствие этаж, на котором он выходит при этой разгрузке). Следовательно число различных способов разгрузки лифта совпадает с числом различных отображений из множества X в множество Y, то есть равно |YX| = 84 = 4096. Задача. Пусть X - конечное множество. Найти количество всех различных подмножеств множества X.
Решение.
Пусть
Е2
= {0,1}. Для любого подмножества А
fA
: X
—>
Е2
следующим образом: fA(х)
=
1, если х
Заметим,что множество всех подмножеств множества X обозначают 2Xl и мы доказали, что |2Х| = 2|X|.
8. Число сочетаний из n элементов по m элементам (Cnm)
Число
различных m-элементных
подмножеств множества, состоящего из
п
элементов,
называют числом
сочетаний длины т из п элементов и
обозначают
Следствие.
Пусть |Х| = п.
Тогда
число всех различных подмножеств
множества X
равно
Задача. В группе 25 человек. Сколько существует способов выбора из них делегации из трех человек для участия в профсоюзной конференции?
Решение.
Ясно,
что выбор делегации - это выбор
3-элементного подмножества из множества
студентов группы. Поэтому число
способов выбора равно
Задача. В кондитерской продаются пирожные пяти видов: бисквитные, корзиночки, песочные, эклеры, трубочки. Сколькими способами можно купить 12 пирожных?
Решение.
Каждая
покупка однозначно определяется
набором неотрицательных чисел {x1,
x2,
x3,
x4,
x5},
где
xi
- число
покупаемых пирожных i-ого
вида. Тогда наша задача равносильна
задаче о числе решений уравнения x1
+
x2
+
x3
+
x4
+
x5
= 12
при
условии, что xi
где
для любого i
число
ni
• • | • | • • • • | • • • • • • | • • • •
Ясно,
что соответствие между решениями и
картинками - биективное. Но каждая
картинка определяется выбором 4-х
промежутков, где ставится черта, из
имеющихся 16. В нашем примере по решению
(2, 1, 4, 6, 4) мы выбрали 4-элементное
подмножество промежутков {2, 3, 7, 13}.
Число способов выбора 4-элементных
подмножеств множества, состоящего из
16 элементов, равно
Задачи,
сводящиеся к нахождению числа решений
уравнения x1
+
x2
+
. . . + xm
= n,
xi
Теорема
1.30. Число
сочетаний с повторениями длины п из
т видов равно
|
11. Кольца. Поля. Определение и примеры. 12. Кольцо Zm и кольцо Zp. Определение 2.13. Алгебраическая система (К, +, ∙) с двумя бинарными операциями, сложением и умножением, называется кольцом, если:
а
∙ (b
+
с) = а
∙ b
+
а
∙ с,
(b
+ с) ∙ а
= b
∙ а +
с ∙ а, Vа,
b,с
Если в кольце К есть 1 по умножению так, что а ∙ 1 = 1 ∙ а = а для любого элемента а из К, то К называют кольцом с единицей; если операция умножения в кольце К - коммутативна, то есть а∙b = b∙ а для любых элементов а и b из К, то кольцо К называют коммутативным. Примеры.
3)Пусть п - натуральное число. На множестве Z определим отношение эквивалентности:
z1
~
z2
тогда
и только тогда, когда z1
— z2
= п ∙ z
для
некоторого z
Тогда множество Z разобьется на непересекающиеся классы эквивалентности:
Z
= nZ
Класс
эквивалентности m
+ nZ
обозначим
Заметим,
что операции заданы корректно, так
как для любого числа к
Определение
2.14. 1) Элемент
к
≠
0
в кольце К
называется
делителем
0,
если в кольце К
найдется
такой элемент b
≠
0,
что b∙k
=
0 или k∙b
=
0. 2) Элемент k
≠
0
в кольце К
называется
нильпотентным,
если
kп
=
0 для некоторого n
Примеры.
Заметим, что в кольце с единицей делители нуля и нильпотентные элементы не могут быть обратимыми. Определение 2.15. Ненулевое коммутативное кольцо Р с единицей называется полем, если любой его ненулевой элемент - обратим. Примеры.
Обобщим последний пример. Теорема 2.16. Кольцо Zn будет полем тогда и только тогда, когда п - простое число.
Доказательство.
=> Пусть
Zn
- поле
и п
= k∙т,
где
k,т
то
есть
<=
Пусть р
- простое
число. Докажем, что Zp
- поле.
Так как известно, что Zp
- коммутативное
кольцо с единицей, достаточно доказать,
что любой ненулевой элемент в Zp
-обратим.
Пусть
и элемент т - обратим. Заметим, что единичный элемент всегда обратим. Без доказательства сформулируем следующую теорему.
Теорема
2.17. Пусть
1
и
0
- единица
и нуль поля Р. Тогда либо п ∙
1 ≠
0
для
любого натурального
числа п, либо существует простое
натуральное число р такое, что р ∙ 1
= 0. Впервом
случае говорят, что поле Р имеет нулевую
характеристику и пишут charP
=
0; во
втором случае, говорят, что поле Р
имеет характеристику р и пишут charP
= p,
в этом случае аддитивная группа, или
группа по сложению, порожденная
элементом 1, изоморфна полю Zp
и состоит из элементов k
∙ 1, k
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
9. Множество с операциями. Алгебраические структуры. Полугруппа. Моноид. Группа. Определение и примеры. 10. Группа подстановок. Определение 2.1. Бинарной операцией на множестве X называется правило, по которому любым двум элементам x, y из множества X ставится в соответствие некоторый, однозначно определенный, элемент из X, обозначаемый х * у. Заметим, что на множестве X могут быть определены и так называемые унарные операции: каждому элементу множества X ставится в соответствие некоторый, однозначно определенный, элемент множества X. Таким образом задание унарной операции - это задание некоторого отображения f : X —> X. Точно также на множестве определяются нуль-арные операции: выделение какого-то элемента множества. По аналогии можно определить п-арную операцию на множестве X как некоторое отображение f : Хп → X. На одном и том же множестве могут быть определены несколько операций. Например, на множестве Z определены две бинарные операции: сложение и умножение; унарная операция: каждому элементу z множества Z ставится в соответствие элемент (—z); две нуль-арные операции: выделение 0 и 1. Определение 2.2. Операция * на множестве X называется
1)
ассоциативной,
если
для любых элементов х,
у, z
2)коммутативной,
если
для любых элементов х,у
Определение 2.3. Элемент e в множестве X называется нейтральным, единицей, относительно операции * на X, если для любого элемента х из множества X выполняется равенство х*е=е*х= х. Заметим, что выделение нейтрального элемента в множестве задает нуль-арную операцию на этом множестве. Если операция * - обычное умножение на множестве N, Z или R, то е = 1 называют единицей; если же * - обычное сложение, то е = 0 называют нулем. Примеры. 1) Бинарные операции сложения и умножения на множестве Z - ассоциативны и коммутативны. Нейтральным эл-ом относительно операции сложения яв-ся 0, а относительно умножения – 1. 2) Рассмотрим множество матриц порядка 2×2 (таблица, состоящая из действительных чисел), такое множество обычно обозначают M2(R). На этом множестве определены две бинарные операции: сложение и умножение. Операция сложения - ассоциативна и коммутативна; операция умножения - ассоциативна, но не коммутативна. Нейтральным элементом относительно сложения является матрица
Определение 2.4. Непустое множество X с заданной на нем ассоциативной операцией *, обозначаем (X, *), называется полугруппой. Полугруппу (X, *), в которой относительно операции * существует нейтральный элемент, называют моноидом. Пример. Рассмотрим набор букв (алфавит) и множество слов в этом алфавите, которое обозначим М. На множестве М зададим бинарную операцию * следующим образом: для любых слов u иvиз мн-ва М определим и * v = uv, то есть слово и * v получено приписыванием к слову и слова v. Тогда (М, *) - полугруппа. Доб. к мн-ву М пустое слово е, тогда ({М, е}, *) - моноид. Теорема 2.5. Нейтральный элемент в моноиде - единственен. Доказательство. Пусть (М, *) - моноид; е, f - два нейтральных элемента в (М, *). Тогда е = е*f = f по определению. Определение 2.6. Пусть (М, *, е) - моноид. Элемент b называется обратным к элементу а, если а*b=b*а=е. Элемент а в этом случае называют обратимым элементом; элемент b обозначают а -1. Заметим, что, если * - операция сложения, то вместо а -1 пишут — а и называют этот элемент противоположным к элементу а. Например, в моноиде (Z, +,0) любой элемент z имеет противоположный элемент — z, то есть на множестве Z определена унарная операция: f(z) = —z. В моноиде (Z, ∙, 1) обратимы только два элемента: 1 и -1. Теорема 2.7. Пусть (М, *,е) - моноид. Тогда:
Доказательство.
1)
Предположим b1,
b2
- обратные элементы к элементу а
b1 = b1 * e = b1 * (a * b2) = (b1 * a) * b2 = e * b2 = b2. Утверждения 2) и 3) - очевидны. 4) Так как (а * b) * (b -1 * а -1) = а * (b * (b -1 * b -1)) = а * ((b * b -1) * a -1) = а * (е * a -1) = а * a -1 = е, то 4) доказано. Определение 2.8. Алгебраической системой называют непустое множество с семейством операций и отношений, заданных на нем. Мы уже рассматривали примеры алгебраических систем: полугруппы, моноиды, линейно или частично упорядоченные множества, множества с отношением эквивалентности. Пример более богатой структуры: (Z, +, ∙, 0,1, ≤).Здесь определены две бинарные операции: + и ∙ ; две 0-арные операции: выделены 0 и 1 ; определено также отношение порядка ≤ Рассмотрим три основных способа построения новых алгебраических из уже имеющихся. Определение 2.9. Пусть М - алгебраическая система, N является подмножеством множества М, N ≠ Ø. N называется подсистемой алгебраической системы М, если
Заметим, что, если алгебраическая система имеет специальное название: моноид, группа, кольцо, поле, то подсистема называется соответственно: подмоноид, подгруппа, подкольцо, подполе.
|
13. Отношения на множестве. Отношения порядка. Определение и примеры. 14. Отношение эквивалентности. Определение и примеры.
Определение
1.31. Пусть
{X1,
X2,...
,Хп}
- непустые
множества. Тогда п-местным
отношением, заданным
на декартовом произведении Х1
×
Х2
×
... × Хп,
называют
подмножество S
Примеры.
1) На
декартовой плоскости R2
= R
×
R
рассмотрим
подмножество S
- прямую,
являющуюся
биссектрисой первой и третьей четверти.
Ясно, что пара чисел {х1,х2}
из
R
связана
двуместным
отношением S
тогда
и только тогда, когда (х1,х2)
Рисунок.
2) Рассмотрим
3-местное отношение на R3,
заданное следующим образом: (х1,х2,x3)
тогда
и
только тогда, когда
Рисунок.
Двуместные
отношения называют бинарными.
Для
бинарных отношений вместо записи
(х,у)
Определение
1.32. Пусть
α
- бинарное
отношение на X
× Y,
β
- бинарное
отношение на Y
×
Z.
Тогда
композицией
отнтшенип α
и
β
называется
бинарное отношение, обозначаемое
α
о β,
на X
× Z,
определенное
следующим образом: х(а
о β)y
тогда
и только тогда, когда существует такой
элемент у
Для композиции отношений выполняется свойство ассоциативности, то есть (α о β) о γ = α о (β о γ) для любых бинарных отношений α, β,γ - Заметим, однако, что для произвольных бинарных отношений α и β не выполняется коммутативность то есть α о β ≠ β о α. Определение 1.33. Бинарным отношением на множестве X называется бинарное отношение на X × X. Примеры. 1)Пусть X = R. Тогда на этом множестве можно определить следующее бинарное отношение α: хαу тогда и только тогда, когда х2 = у2 (х и у - элементы множества R.) 2) Пусть X = N. Тогда на множестве N определим следующем образом бинарное отношение <:
п1
≤
n2
тогда
и только тогда, когда (n2
— n1)
3) Пусть X = N. Тогда на множестве N определим следующем образом бинарное отношение <:
п1
< п2
тогда
и только тогда, когда (п2
—
п1)
Далее сформулируем определения основных свойств бинарных отношений: рефлексивности, транзитивности, симметричности и антисимметричности. С помощью этих свойств выделяются два важнейших вида бинарных отношений: отношение порядка и отношение эквивалентности. Определение 1.34. Бинарное отношение α на множестве X называется рефлексивным, если для любого элемента х из множества X выполняется отношение хαх. Определение 1.35. Бинарное отношение α на множестве X называется транзитивным, если для любых элементов х, у, z из множества X таких, что хαу и yαz, следует, что xαz. Определение 1.36. Бинарное отношение α называется симметричным, если для любых элементов x, у из множества X таких, что хαу, следует, что уαх. Определение 1.37. Бинарное отношение α на множестве X называется антисимметричным, если для любых элементов х, у из множества X таких, что хαу и уαх, следует, что x = у. Примеры.
Определение 1.38. Бинарное отношение α на множестве X называется отношением порядка, если оно рефлексивно, транзитивно и антисимметрично. При этом, если для любых элементов х, у из множества X справедливо либо хαу, либо уαх, то α называют линейным порядком, а пару (X, α) (множество X с линейным порядком α) - линейно упорядоченным множеством; в противном случае α - частичный порядок, а (Х,α) - частично упорядоченное множество. Примеры.
Определение 1.39. Бинарное отношение α на множестве X называется отношением эквивалентности, если оно рефлексивно, транзитивно и симметрично. Примеры.
Определение
1.40.
Пусть
α
- отношение
эквивалентности на множестве X,
х
- произвольный
элемент множества X.
Тогда классом
эквивалентности (смежности) элемента
х по отношению эквивалентности α
называется
множество [х]α
= {у
|
15. Определение графа. Виды графов. Подграфы. Операции над графами. 16 . Изоморфизм. Помеченные и непомеченные графы. Матрицы, ассоциативные с помеченными графами. Определение графа
Пусть
задано конечное множество V
,
которое будем называть множеством
вершин. Некоторые
из этих вершин соединим ребрами,
т.е.
выделим
в множестве V(2)
всех
двухэлементных подмножеств множества
V
некоторое
подмножество Е,
которое
и будем называть множеством ребер
графа. Итак, граф
- это
пара (V,
Е), где
V
- конечное
множество, а Е
Говорят, что две вершины u и v смежны, если множество {u,v} является ребром, и не смежны в противном случае. Если е = {u,v} - ребро, то вершины и и v называют его концами и говорят, что ребро е соединяет вершины u и v, Такое ребро обозначается символом uv. Два ребра называются смежными, если они имеют общий конец. Вершина о и ребро е называются инцидентными, если и является концом ребра е (т.е. е = uv) и не инцидентными в противном случае. Множество всех вершин графа G, смежных с некоторой вершиной v, называется окружением вершины v и обозначается через NG(v) или N(v).
Рис.1 Графы удобно изображать в виде рисунков, состоящих из точек (вершины графа) и линий, соединяющих некоторые из этих точек (ребра графа). Приведем примеры некоторых графов специального вида. Граф G называется полным, если любые две его вершины смежны, т.е. EG = (VG)(2). Полный граф порядка п обозначим Кп, число ребер в нем равно Сn2 = п(п — 1)/2. На рис.1, а изображен полный граф К5. Граф называется пустым , если в нем нет ребер. Пустой граф порядка п обозначим Оn. На рис.1 б,в показаны также простые циклы Сп для n = 3,4 , а на рис.1 г, д - простые цепи Рп для п = 4,5. Очевидно, что К2 = Р2 и К3 = С3.
Рис.2 На рис.2, а,б приведены два изображения простого цикла С5 , а также колее Wn для п = 3,4 (в,г).
К
Напомним,
что разбиением
множества
S
называется
представление его
в виде объединения подмножеств, никакие
два из которых не пересекаются.
Граф называется двудольным,
если
существует разбиение множества
его вершин на части (доли)
такие,
что концы каждого ребра
принадлежат разным частям. Если при
этом любые две вершины, входящие в
разные доли, смежны, то граф, доли
которого состоят из р
и
q
вершин,
обозначается символом Kp,q
. При
р
=
1 получаем звезду
К1,q.
Легко
проверить, что K1,1
=
К2
= P2
,
K1,2
= Р3.
На
рис. 3 изображены звезда K1,5
и двудольный граф K3,3.
Как
видно из определения, граф - это
алгебраическая система с одним
отношением
специального
вида. Следовательно, к графам применимы
понятия
гомоморфизма, изоморфизма и автоморфизма.
В частности, два графа G
и
Н
называются
изоморфными,
если
существует биекция φ: VG
→
VH
такая,
что две вершины u,v
Для
произвольного графа G
определяется
дополнительный
граф
И |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Определение 2.10. Пусть М и N - алгебраические системы с одинаковым набором операций и без отношений. Тогда декартово произведение М × N будет такой же алгебраической структурой, если для любой k-арной операции f(a1,..., ak), определенной на множествах М и N, на множестве М × N следующим образом определим операцию: f((m1, n1), . . . , (mk, nk)) = (f(m1, . . . ,mk), f(n1, . . . , nk)). Аналогично опеделяются операции на произведении п алгебраических систем. Определение 2.11. Пусть М - алгебраическая система, в которой нет отношений. Предположим, что на М можно задать отношение эквивалентности ~, согласованное с операциями на М, а именно: для любой n-арной операции f(a1,... ,ап), определенной в алгебраической системе М и любых элементов из М таких, что m1 ~ т1’,..., тп ~ тп’ выполняется отношение f(m1,..., тп) ~ f(rn1’,..., тп’). Тогда множество классов эквивалентности (М/ ~) превращается в алгебраическую систему с теми же операциями, что действуют на множестве М : f([m1]~ , [m2]~, . . . , [m2]~) = [f(m1,m2, . . . ,mn)]~. Такая алгебраическая система называется фактор-системой алгебраической системы М по отношению эквивалентности ~. Пример. Всем с детства известна алгебраическая система, где множество М = {чет, нечет}; задана бинарная операция + : чет + чет = нечет + нечет = чет, чет + нечет = нечет + чет = нечет; выделен нулевой элемент: 0 = чет. Такая алгебраическая система фактически является фактор-системой алгебраической системы (Z, +, 0) по отношению эквивалентности ~: z1 ~ z2 тогда и только тогда, когда z1 - z2 делится нацело на 2. Определение 2.12. Группой называется множество G с бинарной операцией, обозначаемой обычно ∙, удовлетворяющей трем условиям: 1)операция ∙ - ассоциативна;
2)существует
единичный элемент е такой, что g
•
е
= е
• g
= g
для
любого g
3)все
элементы множества G
обратимы,
то есть для любого g Итак, группа - это моноид, в котором каждый элемент обратим. Заметим, что группа G называется абелевой, если операция ∙ коммутативна.
В
группе G
можно
решить любое уравнение вида а∙х
= b
или
х∙а
= b
(a,b
Примеры.
Такую
группу называют группой
подстановок на
множестве X.
Рассмотрим
ее более подробно. Пусть σ
Группу подстановок на множестве из п элементов обозначают Sn. Таким образом, BiXX = Sn. Известен порядок этой конечной группы: |Sn| = |ВiХX| = п!. Если п > 3, то группа Sn не является абелевой группой.
|
Примеры.
Теорема 1.41. Пусть α отношение эквивалентности на множестве X, X ≠ Ø. Тогда:
3)
Доказательство.
1)
Отношение α
- рефлексивно,
следовательно, для любого х
из
множества X
выполняется хαх.
Таким
образом х
3) Так
как х
2)
Пусть [х]α
Определение 1.42. Пусть α - отношение эквивалентности на множестве X. Фактор-множеством множества X по отношению эквивалентности α называется множество, обозначаемое Х/α, элементами которого являются классы эквивалентности [х]α множества X по отношению эквивалентности α.
Определение
1.43. Пусть
α
- отношение
эквивалентности на множестве X.
Множество
X'
(X'
Заметим, что можно выбирать различные системы представителей по отношению эквивалентности α на множестве X, однако количество элементов в каждой такой системе одно и тоже. Справедлива следующая теорема, которую мы сформулируем без доказательства.
Теорема 1.44. Если α - отношение эквивалентности на множестве X, X' - система различных представителей по отношению эквивалентности α на множестве X, то существует биективное отображение φ : Х/α → X'. В частности, если Х/α -конечное множество, то |Х/α| = |Х'| .
Отношение эквивалентности на множестве обычно обозначают знаком ~.
Пример. На множестве Z рассмотрим следующее отношение эквивалентности: z1 ~ z2 тогда и только тогда, когда z1 — z2 делится нацело на 2. Тогда множество Z разбивается на два непересекающихся класса эквивалентности: [0]~ = {0,±2,±4,...,±2n,...}, [1]~ = {±1,±3,...,±(2n+1),...}.
Любая система различных представителей в этом случае содержит 2 элемента. Например, {0,1} и {4,-5} - системы различных представителей множества Z по отношению эквивалентности ~. |
Подграфы
Граф
Н
называется
подграфом
графа
G,
если
VH
Важный
класс подграфов составляют подграфы,
полученные в результате
удаления вершины v
Гипотеза
реконструируемости (П. Кэлли,
С. Улам, 1945 г.). Пусть G
и
H
- два графа одного порядка п
>
2 и система {Gv|v
Подтверждена реконструируемость графов для 3 ≤ п ≤ 10. Заметим, что для п = 2 эта гипотеза не верна. Операции над графами Удаление вершины или ребра - это пример операций, уменьшающих число элементов графа. Рассмотрим теперь операции над графами, увеличивающими число вершин или ребер. Такова, например, операция добавления ребра е = uv, если вершины u и v графа G не являются смежными. В результате получается граф G + е, у которого эти вершины уже соединены ребром.
Г
О
Пусть
Gi
m
(Vi,
Ei)
(i
=
1, 2)- два графа. Произведением
G1
Очевидно, что |G1
С
помощью операции произведения вводится
рекуррентным образом важный
класс графов – п-мерные
кубы Qn:
Q1=K2;
Qn=K2 Граф Qn имеет порядок 2п, вершины его можно представить (0,1)-векторами длины п таким образом, что две вершины будут смежны тогда и только тогда , когда соответствующие векторы различаются ровно в одной координате. Матрицы, ассоциированные с графом
В
этом
параграфе и далее (i,j)-й
элемент
матрицы М
обозначается
Mij.
Пусть
G
- помеченный
граф порядка п,
VG
=
{1,2,... ,п}.
Определим
п
A(G) называется матрицей смежности графа G. Это симметрическая матрица с нулями на главной диагонали. Теорема. Графы изоморфны тогда и только тогда, когда их матрицы смежности получаются друг из друга одинаковыми перестановками строк и столбцов. Так как при такой перестановке строк и столбцов не меняется ранг, характеристический многочлен и корни характеристического многочлена, то имеет смысл для графа G определить ранг - rankG, как ранг матрицы A(G), характеристический полином графа и спектр графа как множество всех корней характеристического полинома (корни вещественны в силу симметричности матрицы A(G)).
Если
спектры двух графов различны, то они
не изоморфны. Обратное,
однако, не верно, как показывает пример
неизоморфных графов K1,4
и С4
Вторая из матриц В = B(G) графа G называется матрицей Кирхгофа
Сумма элементов в каждой строке и в каждом столбце матрицы B(G) равна 0. Теорема остается справедливой и для матрицы Кирхгофа. |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
17. Метрические характеристики графов. Деревья. Планарность графов. Метрические характеристики графа В этом параграфе G - связный граф. 1. Пусть и и v - две несовпадающие вершины графа G. Длина кратчайшего (u,v) - маршрута называется расстоянием между вершинами и и v и обозначается через d(u,v). Положим также d(u,u) = 0. Теорема 1. Расстояние d(u, v) удовлетворяет аксиомам метрики: а) d(u,v) ≥ 0; б) d(u, v) = 0 тогда и только тогда, когда и = v; в)d(u,v) = d(v,u); г) d(u,v) + d(v,w) ≥ d(u, w) для любых вершин и, и, w графа G. Понятие расстояния между вершинами позволяет определить k-ю степень графа G. Граф Gk имеет то же множество вершин, что и G и несовпадающие вершины u и v смежны в графе Gk в том и только том случае, если d(u,v) ≤ k. Диаметром d(G) графа G называется наибольшее из расстояний. Ясно, что d(G) ≤ |G|. Теорема 2. Если k ≥ d(G), то Gk - полный граф. Теорема 3. Для любого связного графа G имеет место неравенство: d(G) ≤ rankG. 2. Критерий двудольности графа. Теорема 3 (Кениг, 1936 г.). Для двудольности графа необходимо и достаточно, чтобы он не содержал циклов нечетной длины. Деревья Деревом называется связный граф, не содержащий циклов. Любой граф без циклов называется ациклическим или лесом. Следующая теорема характеризует и дает эквивалентные определения дереву. Теорема 1. Для (п, т)-графа G следующие условия эквивалентны: а) G - дерево; б) G - связный граф и т = п - 1; в) G - ациклический граф и т = п - 1; г) любые две несовпадающие вершины графа G соединяет единственная простая цепь. Следствие. В любом дереве порядка п ≥ 2 имеется не менее двух концевых вершин. Пусть Н - остовной подграф произвольного графа G. Если на каждой области связности графа G графом H порождается дерево, то Н называется остовом или каркасом графа G. Очевидно, что в любом графе существует остов: разрушая в каждой компоненте циклы, т.е. удаляя лишние ребра, придем к остову. Теорема 2. Число ребер произвольного графа G, которые необходимо удалить для получения остова, не зависит от последовательности их удаления и равно m(G) - |G| + k(G), где m(G) и k(G) - число ребер и число компонент графа G соответственно. Планарность Встречаются ситуации (например в радиоэлектронике при проектировании путей коммуникаций), когда важно выяснить, возможно ли нарисовать граф на плоскости так, чтобы его изображение удовлетворяло определенным требованиям. Таким образом возникает понятие плоского графа. Плоским графом назовем граф, вершины которого являются точками плоскости, а ребра - непрерывными плоскими линиями без самопересечений, соединяющими соответствующие вершины так, что никакие два ребра не имеют общих точек, кроме инцидентной им обоим вершины. Любой граф, изоморфный плоскому графу, будем называть планарным. О планарных графах говорят, что они укладываются на плоскости. Имеет смысл рассматривать укладки и на других поверхностях (например, сфере, торе, сфере с п ручками), а также в пространстве. Теорема 1. Для любого графа найдется натуральное число п такое, что данный граф укладывается на сфере с п ручками. Тем более любой граф укладывается в пространстве. Наименьшее натуральное число п со свойством, указанным в теореме 1, называется родом графа G и обозначается γ(G). В случае γ(G) = 1 говорят о тороидальных графах. Что касается взаимоотношений планарности и возможности укладки на сфере, то ответ дается в следующей теореме. Теорема 2. Граф укладывается на сфере тогда и только тогда, когда он планарен, что в свою очередь эквивалентно равенству γ(G) = 0. Доказательство легко получается с помощью стереографической проекции. Южный полюс сферы помещаем на плоскость и проектиру ем из северного полюса. При этом, если граф уложен на сфере, считаем, что северный полюс не принадлежит ни одному ребру графа, а если граф уложен на плоскости, то южный полюс обладает таким же свойством (очевидно, что даже малым сдвигом графа можно обеспечить соблюдение этого условия) Существуют ли непланарные графы? Да, существуют, граф K3,3 не является планарным, как мы увидим позже. Более того, почти все графы непланарны в том смысле, что предел отношения
количество непланарных графов порядка n количество всех графов порядка п
равен
единице при п
→ Гранью плоского графа называется максимальное по включению множество точек плоскости, каждая пара которых может быть соединена непрерывной кривой, не пересекающей ребра графа. Границей грани будем считать множество вершин и ребер, принадлежащих этой грани. Далее будем пользоваться следующими обозначениями: n, m, f -соответственно число вершин, ребер и граней плоского графа. Теорема 3 (Эйлер, 1758 г.). Для всякого связного плоского графа верно равенство (формула Эйлера) п - т + f = 2. Именно с помощью формулы Эйлера доказывается непланарность некоторых графов. Предложение. Графы К5 и К3,3 непланарны. Особая роль непланарных графов К5, К3,3 заключается в том, что эти графы являются минимальными непланарными графами и играют важную роль во многих критериях планарности. Имеется несколько критериев планарности графа. Мы рассмотрим только один. Теорема 4 (Понтрягина - Куратовского). Граф планарен тогда и только тогда, когда он не содержит подграфов, гомоморфных К5 или К3,3.
|
18. Высказывание. Операции над высказываниями. Булева алгебра высказываний. Алгебра высказываний. Основным понятием в этом параграфе является высказывание. В определении, которое следует далее, мы используем интуитивные представления о том, что есть истина и что - ложь. Определение 3.1. Высказывание - это повествовательное предложение, о котором можно сказать, истинно оно или ложно. Рассмотрим следующие предложения.
Предложения 1) и 3) - истинные высказывания; 2) - ложное высказывание; предложения 4) и 5) не являются высказываниями. Пусть А - множество всех высказываний, Е2 = {0,1}. Определим отображение â : А —> Е2 следующим образом: â = 0, если a - ложное высказывание; â = 1, если а - истинное высказывание. При этом â назовем значением истинности высказывания а.
Определение
3.2.
Выск-ия а
и
b
будем
называть равносильными и писать а
≡
b,
если â
=
Заметим, что это определение - естественно, так как при рассмотрении высказываний нас не интересует содержательная часть, заключенная в предложении, а интересует только значение его истинности. На множестве всех высказываний с помощью значений истинности определим следующие операции, которые называют логическими.
Определение
3.3. Отрицанием
высказывания а называется
высказывание, обозначаемое
Очевидно,
что
0
1
1
0
Заметим,
что отрицание - это унарная операция,
определенная на множестве высказываний
А
и
соответствующая конструкции
Определение
3.4. Конъюнкцией
высказываний аиb
называется
высказывание, обозначаемое
а
Очевидны следующие свойства конъюнкции:
Заметим, что здесь, и в дальнейшем символом 0 мы обозначаем ложное высказывание, а символом 1 - истинное. Конъюнкция, логическое умножение, соответствует союзу "и" в русском языке. Например, если высказывание а ≡ (− − −), b ≡ (***), то высказывание
а
Определение
3.5. Дизъюнкцией
высказываний а и
b
называется
высказывание, обозначаемое а
Очевидны следующие
свойства дизъюнкции:
а
b
а
0
0
0
0
1
1
1
0
1
1
1
1
1) а
2) а
3)
a
Дизъюнкция,
логическое сложение, соответствует
союзу "или" в русском языке. Если
высказывание
а
=
(-----), высказывание b
=
(***), то высказывание а
Определенные
нами на множестве высказываний А
операции:
отрицание, конъюнкция, дизъюнкция,
- называются булевыми операциями.
Алгебраическая структура (А,
|
21. Двойственность в алгебре высказываний. Теорема о общем принципе двойственности для булевых формул.
Определение
3.17. Пусть
f(x1,
x2,...,
хп)
- формула
алгебры высказываний. Двойственной
к
ней будем называть формулу f*(x1,
x2,...
,хп)
=
Утверждение. Справедливы следующие равносильности:
Доказательство каждого из пунктов следуют непосредственно из определения. Например,
1)
(0*) ≡
Теорема 3.18. f1(x1, x2,... ,хп) ≡ f2(x1, x2,... ,хп) - равносильные формулы в алгебре высказываний тогда и только тогда, когда f1*(x1, x2,...,хп) ≡ f2*(x1, x2,... хп) - равносильные формулы в алгебре высказываний.
Доказательство.
Заметим,
что столбец
Отсюда сразу следует, что, если совпадают таблицы истинности формул f1 и f2, то совпадают и таблицы истинности формул f1* и f2* . Теорема доказана. Теорема 3.19. Общий принцип двойственности. Пусть G(x1, x2,... ,xn) = F(f1(x1, x2,... ,xn),f2(x1, x2,... ,xn),... ,fm(x1, x2,... ,xn)) .
Тогда G*(x1 , x2,... ,хп) = F*(f1*(x1, x2,... ,хп), f2*(x1, x2,... ,хп),,..., fm*(x1, x2,... ,хп)), где F*(у1, у2, …, yт) - формула, двойственная к формуле F(y1, y2,... ,ут). Доказательство. Действительно, G*(x1, x2 ,... ,xn) = (F(f1(x1,x2,... ,xn), f2(x1,x2,... ,xn),... , fm(x1, x2,...,xn)))* =
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
19. Формула алгебры высказываний. Равносильность формул алгебры высказываний. 20. Теоремы о формулах алгебры высказываний.
Определение
3.10. Формулой
алгебры высказываний называются:
1) сами высказывания и символы
высказывательных переменных; 2)
выражения вида
Замечание. Для того, чтобы не перегружать формулы скобками, принято соглашение об упрощении записи формул:
Пусть
F(x1,
х2,...,
хп)
- формула,
в которой п
высказывательных
переменных. Множество всех
возможных наборов значений истинности
высказывательных переменных,
содержащихся
в данной формуле, - это множество
Такая таблица называется таблицей истинности формулы F(x1,x2,... ,хп). Определение 3.11. Формулы F1(x1,x2,... ,хп) и F2(x1,x2,... ,хп) в алгебре высказываний называются равносильными, если совпадают их таблицы истинности. Определение 3.12. Формула F(x1,x2,... ,хп) в алгебре высказываний называется булевой, если в ней присутствуют только булевы операции.
Без доказательства приведем три важнейшие теоремы алгебры высказываний. Доказательства этих теорем довольно громоздки, хотя формулировки достаточно очевидны на интуитивном уровне. Теорема 3.13. Теорема о фиксации значений в формуле. Если F(x1,x2,... ,хп) - формула в алгебре высказываний, то при подстановке в эту формулу вместо всех высказывательных переменных xi высказываний ( фиксации значений переменных) формула превращается в высказывание. Таким образом формула задает отображение: F : Ап → А, где А - алгебра высказываний. Теорема 3.14. Теорема о подстановке формул в формулу. Пусть F(y1, y2,... , ym), f1(x1, x2,... ,xn),... , fm(x1, x2,... ,xn) - формулы алгебры высказываний. Тогда F(fi(x1,x2,…, хп),..., fm(x1, х2,..., хп)) - формула алгебры высказываний, полученная из формулы F(y1, y2,…, ут) подстановкой формул fi(x1, х2,..., хп) вместо высказывателъных переменных yi (i = 1, 2,..., т). Теорема 3.15. Теорема о равносильной подстановке. Пусть F(y1, y2,..., ут) ≡ G(y1, y2,..., ут), f1(x1, x2,... ,xn) ≡ g1(xi,x2,...,xn), f2(x1, x2,... ,xn) ≡ g2(x1,x2,... ,хп), ... fm(x1,x2,... ,xn) ≡ gm{х1, х2,... ,хп) - равносильные формулы алгебры высказываний. Тогда F(f1(x1,x2,... ,xn),... ,fm(x1, x2,... ,xn)) = G(g1(x1, x2,... ,xn),... ,gm(x1, x2,... ,xn)). Теорема 3.16. Любая формула в алгебре высказываний равносильна некоторой булевой..
Доказательство.
Назовем
рангом
формулы F,
обозначим rangF}
количество
логических операций, входящих в F.
Доказательство
проведем индукцией по рангу формулы
F.
Пусть
rangF
= 1,
Тогда формула F
может
быть только одной из следующих:
|
Теорема 3.6. Справедливы следующие 19 равносильностей для булевых операций алгебры высказываний:
• 9) а а ≡ а - законы идемпотентности;
• 10)
Любую из перечисленных равносильностей получаем с помощью таблиц истинности, определяющих булевы операции. Кроме булевых, в алгебре высказываний определяются еще две очень важные логические операции: импликация и эквиваленция. Если а = (-----), b = (***) - высказывания, то импликации этих высказываний соответствует конструкция (если(-----),то(***)), а эквиваленции соответствует конструкция ((-----)тогда и только тогда, когда(***)).
Определение
3.7. Импликацией
высказываний а и
b
называется
высказывание, обозначаемое
а→bи
определяемое следующей таблицей:
а
b
а
→
b
0
0
1
0
1
1
1
0
0
1
1
1 Очевидны следующие свойства импликации высказываний: 1) a →b≠ b→a; 2) a →a≡1; 3) 0 →a≡1; 4) 1 →a≡a 5) a →1≡1
6)
a→0≡
Определение 3.8. Эквиваленцией высказываний а и b называется высказывание, обозначаемое а ~ b и определяемое следующей таблицей:
Очевидны следующие свойства эквиваленции высказываний:
Теорема 3.9. Справедливы следующие равносильности:
а
b
а
~
b
0
0
1
0
1
0
1
0
0
1
1
1 Теорема легко доказывается с помощью таблиц истинности, определяющих операции.
|
Теорема (двойственность для булевых функций)
f(x1,x2,…,xn)
– булева функция. Тогда f*(x1,x2,…,xn)
получается из f
следующим образом 0→1, 1→0,
Доказательство по индукции по количеству булевых операций в этой формуле.
Ранг f≤1,
0*≡1, 1*≡0, (
(x
Предположим, что
теорема справедлива для формулы rang
f
≤n-1.
Докажем ее для формулы rang=n.
Любая такая формула имеет один из
следующих видов, либо F1
1). Для
Формула F rang≤n-1, поэтому теорема для нее справедлива
2). Ф(y1,y2)
= y1 3). Аналогично. Пример: Написать двойственную функцию
f(x,y,z)=x(
f*(x,y,z)= Нормальная форма алгебры высказывания.
Пусть σ
Уравнение х σ
= 1 имеет решение х= σ,
Рассмотрим уравнение:
Т.к. конъюнкция равна 1 <=> , когда каждый множитель =1 , то это уравнение равносильно системе
( Рассмотрим уравнение вида
Решением этого уравнения будет:
Лемма (о разложении формулы в алгебре высказываний по переменным)
Пусть f(x1,x2,…,xn)
– формула в алгебре высказываний.
Тогда f(x1,x2,…,xn)≡
xif(x1,x2,…,xi-1,
1, xi+1,
… xn)
Доказательство:
Чтобы
доказать равносильность формул, надо
доказать их равенство на любом наборе
значений истинности (совпадение таблиц
истинности) {α=( α1,
α2,
…, αn)}
αk
Если докажем лемму для множества I отдельно и для множества II, то она будет доказана 1) I => i = 1 => f(1,..,n) 1f(1,..,(i-1),1,(i+1),..,n)1f(1,..,n) f(1,..,n) - верно 2) II => i = 0 => f(1,..,n) 0f(1,..,n)0f(1,..,(i-1),0,(i+1),..,n) 1f(1,..,i,..,n) – верно
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
22. Нормальные формы в алгебре высказываний: СДНФ, СКНФ. СДНФ Теорема: Для любой Формулы в алгебры высказываний, отличной от тождественно ложной существует ее представление в виде: f(x1,x2,..,xn) (x11.x22….xnn),
сн(1,2,..,n Пусть f(x1,x2,..,xn) - формула в алгебры высказываний Разложим эту формулу по переменной x1 Тогда: f(x1,x2,..,xn)снизу(1E2) x11(1,x2,..,xn) (разложим по x2 и подставим в разложение) снизу (1E2)( снизу (2E2) x11.x22f(1,2,x3,..,xn))…и т.д.
снизу
(1,2,..,n где f(1,2,..,n) - 0 or 1 Мы можем опустить те слагаемые, для которых f(1,1,..,n)0, и получим f(x1,x2,..,xn) снизу [(1,2,..,n) | f(1,2,..,n)1] x11.x22….xnn СКНФ, КНФ, ДНФ Теорема: Для любой формулы в алгебры высказываний, отличной от тождественно истинной существует ее представление в виде: f(x1,x2,..,xn) (x11x22…xnn) снизу [(1,2,..,n) | f(1,2,..,n)0] - СКНФ данной формулы. При доказательстве используем принцип двойственности СКНФ->СДНФ Двойной двойственностью: f(x1,x2,..,xn)(f*( x1,x2,..,xn))*[не явл.≡0=>СДНФ](x11.x22….xnn)*≡ (1,2,..,nE2)|f*(1,2,..,n)1 ≡ [f(x1,x2,..,xn)] x11x22…xnn, (1,2,..,n)|f(1,2,..,n)0
Пр:
x1→x2
≡ (
≡ КНФ, ДНФ Обозначим V={x1,x1,x2,x 2,..,xn,xn} Элементарная конъюнкция - конъюнкция всех элементов множества υ V По опр: ДНФ –дизъюнкция элементарных конъюнкций Пр: x1x2x3 Аналогично: Элементарная дизъюнкция - дизъюнкция всех элементов множества υ V КНФ – конъюнкция элементарных дизъюнкций. Змч.: СДНФ является ДНФ, СКНФ является КНФ
|
23. Алгебра предикатов. О: Пусть задана некоторая область U – предметная область. Пусть заданы некоторые переменные x1,x2,..xn, которые называются предметными. Тогда n – местным предикатом P(x1,x2,..xn) мы будем называть отображение мн-ва эл-тов предметной области в множество высказываний. x1,x2,..,xnU => P(x1,x2,..,xn) - высказывание. О: 1) (P, U) – называется тождественно истинным, если все прообразы P-1({1})=U
Операции над предикатами Над множеством предикатов можно ввести те же операции, что и в АВ P(x1, x2,.., xn), Q(x1, x2,.., xn), U По опр.:
Т.: Множество n-местных предикатов на предметной области U образует булеву алгебру предикатов (выполняются 19 основных равносильностей):
0.
Змч.: формула в АВ Ф(x1,.., xn) от n-переменных также является n-местным предикатом. Сами высказывания также можно считать 0-местными предикатами. Кванторы Кванторы – это операции понижающие местность предикатов. Опр. Пусть P(x)- одноместный предикат (). Тогда определим по нему высказывание x P(x) – истина <=> P(x)=1 Опр. Пусть P(x)- одноместный предикат. Определим по нему высказывание x P(x) – ложно <=> P(x)=0 Заметим, что операции кванторы связаны с обычными операциями над предикатами, а именно, если ={ x1,x2,..,xn }, то xP(x)≡P(x1)P(x2)….. P(xn) (P(x)-одноместный предикат) Аналогично xP(x)≡P(x1) P(x2) ….. P(xn). Далее, зная операцию фиксации переменных можно определить (n-1) – местный предикат xiP(x1,x2,.. xi-1,xi,..,xn) и xiP(x1,x2,.. xi-1,xi,..,xn) по любому конечному предикату на xjxiP (x1,x2,..,xn), xixiP(x1,x2,..,xn), xj xiP (x1,x2,..,xn), xixiP(x1,x2,..,xn) D(x1,x2)={натуральное число x1 делится без остатка на натуральное число x2}, =N x1 D(x1,x2)-каждое натуральное число x1 делится без остатка на натуральное число x2 (переменная x2)
|
Вопросы:
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
X.
Аналогично
х
X
обозначает,
что элемент х
не
принадлежит множеству X.
Y),
если для любого х
X
следует,
что х
Y.
Y
и
Y
Х.
U.
Это
утверждение мы принимаем без
доказательства.
Заметим, что утверждения, которые
считаются верными без доказательства,
называются аксиомами.
Y
= {х
U
| х
X
или
х
Y};
пересечением
двух
множеств Х и Y
называется множество Х ∩
Y
=
{х
U|
х
X
и
х
Y};
дополнением
множества
X
называется множество
=
{х
U
| х
X}.
,
то есть дополнение к универсальному
множеству.
=
X
-
закон
двойного отрицания;
Y
= Y
X
- коммутативность;
(Y
Z)
=
(X
Y)
Z
- ассоциативность;
(Y
∩
Z)
= (X
Y)
∩
(X
Z)
- дистрибутивность;
Z)
= (X
∩
Y)
(X
∩
Z)-
дистрибутивность;
=
∩
- закон
де Моргана;
=
-
закон
де Моргана;
X
= X-
закон
идемпотентности;
U=
U;
Ø
= X;
(X∩Y)
= X
-
закон
поглощения;
Y)
= X
- законы поглощения;
= U
- законы дополнения;
= Ø - законы
дополнения.
X
и
х
Y}
(Y\X).
Y|
= |Х|
+ |Y|.
Y
=
{1,…,n},
j
{1,…,m}.
Y|
= |X|
+ |Y|
- |X
∩
Y|
Y
= X
(Y
\ X)
и
X
∩
(Y
\ X)
=
Ø.
Тогда |Х
Y|
= |X|
+ |Y
\ X|
по
предыдущей теореме. Аналогично, |Y|
= |Y
\ Х| + |У ∩
Х|.
Следовательно |Y
\ X|
= |Y|
- |Y
∩
X|
и |X
Y|
= |X|
+
|Y|
- |X
∩
Y|.
Теорема доказана.
A2
. . .
An|
= |A1|
+ |A2|
+ . . . + |An|
-
Y|
= 25.
Следовательно 25 = 14+16 - |Х∩Y|
и
количество студентов, изучающих два
языка равно |Х∩Y|
= 5.
X,
у
Y.
Обозначим
это множество X
× Y.
X,
у
Y}
. Равенство
элементов в множестве X
× Y
понимается
следующим образом: (x1,
y1)
= (x2,
y2)
тогда
и только тогда, когда x1
= х2
и
у1
= у2.
Очевидно,
что X
× Y
≠
Y
×
X,
если X
≠
У.
Xi
Vi=
1,...,n}
,
×
Y
и
(xi
×
Y)
(xj
×
Y)
= Ø,
если i≠j.
|xi
× Y|.
Так
как отображение
fi
:xi
× Y
→Y
такое,
что fi((xi,
y))
= y,
является
биекцией для любого i
(i=1,…,n),
то
|xi
× Y|
= |Y|
и |Х
×
Y|
= |Х| ∙
|Y|.
X,
yj
Y.
Таким
образом множество всех дорог из А
в
С
является
декартовым произведением X
×Y.
Следовательно
|Х
× Y|
= |Х| ∙ |Y|
=
12.
Y
и |f(Х)|
= |Х| <
|У|. Заметим, что мы использовали
инъективность отображения f
:
f(xi)
≠
f(xj),
если
xi
≠
xj.
{1,2,...,m}.
Так как f
InYX,
то InYX
Ø.
{1,
2,..., m}.
Будем считать элементы множества Y
ячейками.
и
называется числом размещений длины
т
на
множестве из п
элементов
(число ячеек). Итак, мы доказали, что
|InYX|
=
= n
∙
(п-
1)
∙
... ∙
(п
– т + 1) =n!/(n-m)!.
Т,
то Xf
= {хi1,
хi2,...,
хim}
- выделенное
подмножество. С другой стороны по
каждому подмножеству А
= {хj1,
хj2,...,
хjm}
можно
построить отображение f
: Т
→
X
такое, что f(k)
= xjk
для
к
Т. Будет
ли число различных m-элементных
подмножеств множества X
совпадать с |InYX|?
Ответ на этот вопрос отрицательный.
Действительно, подмножество Хо
= {хi1,
хi2,...,
хim}
совпадает
с подмножеством Х1
= {хi2,
хi3,...,
хim,
xi1},
однако
fx0
≠
fx1.
Количество
различных инъективных
отображений, соответствующих
подмножеству Хо,
совпадает с числом различных
перестановок элементов множества Хо
и равно га!. Заметим, что это утверждение
верно
для любого m-элементного
подмножества множества X.
Таким образом, получаем, что число
различных m-элементных
подмножеств множества X
равно
;
6) X
ΔY
= Y
Δ
Х;
;
8) X
\ Ø = X
Y
тогда и только тогда, когда X\Y
= Ø
X
-
рефлексивность;
Y)
и (Y
Z)
следует
X
Z
- транзитивность;
Y)
и (Y
X)
следует
X
= Y
-
антисимметричность.
X,
В
У.
Тогда:
A};
X
| f(x)
B}.
X;
B1;
B2
Y.
Тогда:
A2)
= f(A1)
f(A2);
2)
f
−1(B1
B2)
= f −1(B1)
f −1(B2);
f(A1)
∩
f(A2);
4)
f
−1(B1
∩
B2)
= f −1(B1)
∩
f −1(B2).
f(A1
А2).
Это равносильно тому, что существует
х
А1
А2
такой,
что f(x)
= у, то
есть или существует х
А1
или
существует х
А2
с
условием у
= f(x).
Но
это равносильно тому, что или у
f(A1)
или
у
f(A2),
то
есть у
f(A1)
f(A2).
Первое
утверждение теоремы доказано. Пусть
теперь х
-
произволь ный
элемент множества А1
∩
А2.
Тогда
элемент х
одновременно
принадлежит множествам А1
и
А2,
и
следовательно элемент f(x)
одновременно
принадлежит множествам f(A1)
и
f(A2),
но
по определению это и означает, что
f(x)
f(A1)
∩
f(A2).
Таким
образом доказали 3), то есть f(A1
∩
А2)
f(A1)
∩
f(A2).
Обратное
включение в общем случае неверно, что
показывает следующий пример.
Ø.
X
справедливо:
A2
...
Am,
где
m
= |Y|,
Y
= {y1,
y2,…,ym}.
Aj
= {f
: X
→
Y
| f(x1)
= yj
}.
Ясно,
число Aj
∩
Ak
= Ø,
если j
≠
k.
По
правилу суммы |YX|
= |А1|
+
|А2|
+
... + |Ат|.
Посчитаем
теперь количество элементов в каждом
множестве Aj.
При
любом отображении f
Aj
образ
элемента х1
фиксирован
(f(x1)
= yj),
следовательно
отображение f
определяется только тем, куда
попадут элементы множества Х
\ {x1}.
Таким
образом отображение f
однозначно определяется своим
ограничением на Х
\ {х1},
поэтому
для любого j
количество
элементов в множестве Aj
совпадает
с количеством всех различных отображений
из множества Х
\ {х1}
в
множество Y.
По
предположению индукции |Aj|
= |Y
X\{x1}|
= mn−1.
X
определим
отображение
A;
fA(х)
=
0, если х
А.
Заметим,
что множество всех таких отображений
совпадает с множеством Е2X.
Действительно, очевидно,
что {
fA
| А
X}
Е2X.
С
другой стороны, если f
: X
→
Е2
- произвольное отображение, то f
= fA,
где
А
= {х
X
| f(x)
=
1}.
Очевидно, что отображение φ:
{А
|
А
X}
→
Е2X
такое, что φ(А)
= fA,
является
биекцией. Следовательно количество
всех различных подмножеств множества
X
равно |Е2X|
= 2|X|.
.
Итак,
=
n!/(m!(n-m)!)
- число различных m-элементных
подмножеств множества, состоящего из
п
элементов.
= 25!/(3!∙22!)=
2300.
Z,xi
>
0 для
i
{1,2,3,4,5}.
Сделаем замену xi
+
1 = ni.
В
результате
получили задачу, равносильную
первоначальной, о нахождении числа
решений уравнения
n1+n2
+ n3
+ n4
+ n5
= 17,
N.
Нарисуем прямую и отметим на ней 17
точек. Каждому решению
нашего уравнения сопоставим картинку,
состоящую из точек и черточек, которая
строится следующим образом. Если
(
,
,
,
,
)
- решение, то отсчитаем слева направо
отмеченных
точек и за последней из них поставим
черту. Затем отсчитаем
точек и за последней из них также
поставим черту, и так далее. Договоримся
последнюю черточку
не рисовать. Например, решению (2, 1, 4,
6, 4) соответствует рисунок
=
16!/(4!∙12!)
= 1820
Z,
xi
≥ 0Vi
называют
задачами на сочетания с повторениями
длины п
из
т
видов.
.
При
доказательстве
используется
та же схема, что и при решении предыдущей
задачи.
К.
Z.
(1 + nZ)
...
((n
- 1)
+ nZ),
(m
+ nZ
= {m
+
nz
| z
Z}.)
для т
{0,1,...
,п — 1},
то есть
= m
+ nZ.
Кольцом классов вычетов по модулю п
назовем
множество Zn={
,
,...,
}co
следующими
операциями сложения и умножения:
Z
найдется
такое число т
{0,1,...,
п
— 1},
что
k
= nq
+
m,
q
Z,
следовательно
k
+
nZ
= т +
nZ
= т. Кольцо
Zn
- это
коммутативное кольцо с единицей. Нулем
в этом кольце будет элемент
,
а единицей – эл.
.
N.
и
являются делителями 0, так как
.
является нильпотентным элементом и
делителем 0, так как
.
N,
k,
т ≠
1,
n.
Тогда
и элемент
k
не
может быть обратим. Действительно,
предположив, что существует элемент
такой, что
,
получим
,
и т
= п. Итак,
если п
- составное
число, п
= k∙т,
то
элемент
- необратим,
что противоречит условию: Zn
- поле.
-
произвольный элемент из Zp.
Так
как т
< р и
р
- простое
число,
то натуральные числа тир-
взаимно
просты. Тогда, используя алгоритм
Евклида, можно
найти такие числа a
,b
N,
что
а
∙ т +
b∙
р = 1.
Следовательно
{0,1,...
,р
— 1}.
X
выполняется
равенство (x*y)*z=х*
(y*z);
X
выполняется
равенство х*у
= у*х.
М обратный элемент, если он существует,
-
единственен;
М. Тогда
N;
N,
то
n1
SN
n2
тогда
и только тогда, когда n1
Sn2
Х1
×
Х2
×
... × Хп,.
При
этом, если (х1,2,...,
хп)
S,
то
говорят, что элементы {х1,
x2,...,
хп}
множества
X
связаны
отношением S;
если
же (х1,2,...,
хп)
S
то
говорят, что элементы {х1,
x2
,...,
хп}
не
связаны отношением S.
S,to
есть
х1
= х2.
=
x3.
Ясно, что в этом случае подмножество
S
–параболоид
вращения.
S
принята
запись хαу:
элементы
х
и
у
находятся
в отношении α.
За
наиболее
распространенными бинарными отношениями
закреплены специальные обозначения:
{=,≤,<,>,≥,С,~}.
Y,
что
хαу
и
yβz.
N
{0} .
N.
(Х1
Х2).
Это
бинарное отношение
будет рефлексивным, транзитивным и
антисимметричным.
)
- частично упорядоченное множество,
если |А|
> 1.
Если же |А|
=
1, то (2A,
)
-
линейно упорядоченное множество.
X
| хαу}.
V(2).
Более
подробно множества V
и
Е
обозначаются
как VG
и
EG
соответственно.
Число card(VG)
вершин
графа G
называют
его порядком и обозначают через |G|.
расивыми
примерами являются графы
пяти платановых тел (т.е.
правильных многогранников): тетраэдра,
куба, октаэдра, додекаэдра, икосаэдра.
VG
соединены
ребром тогда и только тогда, когда их
образы φ(и),
φ(v)
соединены
ребром в H.
В этом случае пишем G
H,
Например, граф К3,3
на рис.3
изоморфен графу "а" на рис.4, а
графы "б" и "в" на этом же
рис. 4
не изоморфны. В некоторых ситуациях
все же приходится различать изоморфные
графы, и тогда полезно понятие
помеченного графа. Граф порядка
п
называется
помеченным,
если его вершинам присвоены некоторые
метки, например, номера 1,2,... , п.
Отождествим
каждую из вершин
графа с ее номером и определим равенство
помеченных
графов
G
и
Н
одного
и того же порядка: G
= Н тогда,
когда EG
= EH.
Различные
помеченные графы могут быть изоморфны
между собой.
:
множество
вершин у него то же самое, что и у графа
G,
a
E
=
V(2)
\ EG,
т.е.
две вершины в
смежны
тогда и только тогда, когда они не
являются смежными в G.
Граф,
изоморфный своему дополнению, называется
самодополнительным.
Например,
K1,P4,C5
-
самодополнительные графы.
ногда
приведенное выше определение графа
недостаточно и приходится
рассматривать более общие объекты, в
которых две вершины могут
быть соединены более чем одним ребром.
Так возникает понятие "мультиграф".
Дальнейшее
обобщение состоит в том, что кроме
кратных
ребер допускаются еще и петли, т.е.
ребра, соединяющие вершину саму
с собой. Такой объект называется
псевдографом.
Изучаются
также
ориентируемые
графы: это
пара, состоящая из множества вершин
V
и
из нек. подмнож. А
декартова
квадрата V2
(вместо
V(2)),
Если
а = (u,v)
А, то
а изобр. дугой со стрелкой; и назыв.
началом,
а
v
- концом
этой
дуги.
G;
G
найдется
такой элемент g
-1
G,
что
g
∙ g
-1
= g
-1
∙ g =
е.
G).
Решением
первого уравнения будет х
= а -1∙b,
а
второго - х
= b
∙ а -1.
Если
операция в группе - сложение, то
рассмотренные выше уравнения имеют
вид: а
+
х
= b
или
х
+
а
= b;
соответственно
решениями будут х
= (-а) +
b
или
х=b+(-а),
где (-а)
- противоположный
(обратный) элемент к элементу а.
GLn(R)
|
detA
=
1} - группа относительно обычной
операции умножения матриц, являющаяся
подгруппой группы GLn(R).
Такая
группа называется
специальной линейной группой.
Z,
∙) - группа из двух элементов относительно
обычной операции умножения на Z.
ВiХX
и
σ(1)
= i1,
σ(2)
= i2,...,
σ(п)
= in.
Отображение
σ
назовем
подстановкой и обозначим (i1,
i2,...,
in).
Подстановка
е
= (1, 2,..., п),
называемая
тождественной
подстановкой, будет
нейтральным элементом, или единицей
в группе подстановок
на множестве X.
Для
любого элемента а
= (i1,
i2,...,
in)
из
группы подстановок определен
обратный элемент σ
-1
так,
что σ−1(ij)
= j, (j
{1, 2,…, n}).
[у]а
≠
Ø;
следует,
что [х]а
=
[у]а
[x]α
и [x]α
≠
Ø.
[х]α,
то
,
следовательно
[у]α
≠
Ø.
Тогда найдется такой элемент z
множества
X,
что xαz
и
yαz.
Пусть
t
- произвольный
элемент из класса [х]α
Тогда
xαt
и
xαz,
следовательно,
выполняется tαz
(мы
воспользовались транзитивностью и
симметричностю). Аналогично, так как
tαz
и
yαz,
то
tαy.
Таким
образом [х]α
[у]α.
Точно
также доказывается, что [у]α
[х]а
,
и
свойство 2) доказано.
X)
называется системой
различных представителей по отношению
эквивалентности α,
если
для любого х
из
множества X
выполняется условие: |Х'
[х]α
| =
1.
VG,
ЕН
EG.
Подграф
Н
называется
остовным
подграфом (или
фактором),
если
VH
=
VG.
Если
множество ребер U
=
ЕН
совпадет
с множеством всех ребер графа G,
оба
конца которых принадлежат VH,
то
Н
называется
подграфом,
порожденным множеством U.
На
рис.5 изображены граф G
и
три его подграфа H1,
Н2
и
H3,
среди которых H3
является
остовным, a
Н2
-
порожденным.
VG.
Граф
Gv
=
G
- v
получается
из графа G
в
результате удаления вершины v
и
всех инцидентных ей ребер. С графами
Gv
связана
знаменитая гипотеза.
VG}
совпадает
с системой {Hu|u
VH}
в
том смысле, что вершины можно
перенумеровать так, что Gv
Hu,
для всех i.
Тогда G
Н.
раф
H
называется объединением
(или
наложением)
графов
F
и
G,
если
VH
=
VF
VG
и
ЕН
=
EF
EG
(рис.6).
В этой ситуации пишут H=F
G
бъединение
F
G
называется
дизъюнктным, если VF
VG
= Ø.
G2
= G
называется
граф, для которого VG
= V1
V2
-
декартово
произведение множеств вершин
исходных графов, a
EG
определяется
следующим образом: вершины (и1
, и2)
и
(w1
, w2)
смежны в графе G
тогда
и только тогда, когда или и1=w1
, а
и2
и
w2
смежны в G2
,
или
и2=w2
, а
и1
и
w1
смежны в G1
(см.
рис.7).
Рис. 7
G2
| = |G1|
|G2
|, |E(G1
G2
)| = |G1
| |EG2
| + |G2
| |EG1
|
Qn-1
(n>l).
n
-
матрицу А
= A(G),
положив
O1,
у
которых один и тот же характеристический
полином х3(x2
- 4).
.
R,
то x2
- 1
< 0.
.
,
определяемое следующей таблицей:
= а. Сформулированное
равенство называют законом
двойного отрицания.
=
{Не ... }, если а
= {…}
- высказывание. Далее
на множестве высказываний А
определим
бинарные операции.
b
или
а
∙ b
и
определяемое таблицей:
b≡
b
а-
коммутативность;
(b
с) = (а
b)
с
- ассоциативность;
1 ≡а;
0
≡
0;
a
≡
а.
b
= ((−
− −) и
(*
*
*)).
b
и
определяемое следующей таблицей
истинности:
b
b
=
b
а - коммутативность;
(b
с) ≡
(а
b)
с -
ассоциативность;
1
≡
1;
4) a
0
≡
а;
5) a
a
≡
а.
b
=
((-----)или(***)).
,
,
)
называется булевой алгеброй, так как
в ней выполняются следующие 19
равносильностей для
булевых операций.
.
у)*
≡
х V
у,
7)
(x
у)* ≡
x
у.
≡
1; 7) (x
у)*
=
=
= x
y.
*
в таблице истинности формулы f*
может быть получен из столбца
в таблице истинности формулы f
с помощью инвертирования, то есть
симметрии относительно середины
таблицы по строкам и отрицания:
*
=
=
=
.
,
(F1
F2),
(F1
F2),
(F1
→F2),
(F1
~ F2),
где Fl,
F2
- формулы алгебры высказываний.
= {(α1,
α2,...,
αп)
|
αi
Е2}.
Известно,
что
это множество конечно и количество
элементов в нем равно 2п.
Таким
образом, отображение
:
→Е2,
которое
определяется формулой F
{x1,
x2,...
,хп),
можно
задать таблицей, состоящей из 2п
строк
и п
+
1 столбцов. Каждая строка имеет вид:
(α1,
α2,...
,αп|
(α1,
α2,
. . ., αп)).
,
х
у,
х∙у, х →
у, х
~
у.
Все
эти формулы равносильны булевым по
теореме v2.
Итак, основание индукции доказано.
Предположим теперь, что любая формула
ранга, меньшего n,
равносильна булевой
формуле. Пусть rangF
= п. Тогда
F
имеет
одну из следующих конструкций:
,
F1
F2
,
F1
∙ F2
, F1
→
F2,
F1
~
F2
,
где
формулы F1
и
F2
имеют
ранг, меньший п.
По
предположению индукции F1
≡
G1,
F2
≡
G2
,
где
формулы G1
и
G2
- булевы.
Тогда по теореме о равносильной
подстановке
≡
,
F1
F2
≡G1
G2
,
F1
∙ F2
≡
G1
∙
G2
,
F1
→
F2
≡
G2,
F1
~ F2
+ (G1
∙ G2)
(
•
).
Все перечисленные формулы являются
булевыми, таким образом
теорема доказана.
≡
а - закон двойного отрицания;
≡
,
≡
-
законы
де Моргана;
≡
0 - закон
противоречия;
=
1 - закон
исключения третьего.
~
;
b;
→
,
→
, а структуру и скобки оставлять.
)*≡
,
(x)*
≡x
y)*
≡x
y,
(x
y)*
≡x
y
F2,
либо
,
либо
,
где F,
F1,
F2
– формулы ранга ≤ 1 будем использовать
общий принцип двойственности.
:
=Ф(y),
g=F,
(Ф(F))*=Ф*(F*)≡
y2,
Ф*= y1
y2,
Ф*(F1,F2)=F1*
F2*
z)
=
=x
(
z)
E2={0;1}
Обозначим
…
=1
,
…
)-
решение.
…
=1,
(
,
…
)
,
={(
,
…
)}
f(x1,x2,…,xi-1,
0, xi+1,
… xn)
≡
f(x1,x2,…,xi-1,
,
xi+1,
… xn).
σi
E2
E2.
Множество всех наборов значений
истинности разобьем на 2 неперекрещивающихся
подмножества: I={
α | αi
=1}, II={
α | αi
=0}
)
| f(1,2,..,n)1
- СДНФ данной формулы.
)
x11.x22….xnn
f(1,2,..,n),
x2)
[CКНФ]
≡
(x2
)x2(x1
)≡
x2
x1x2
x2
≡
x2
x1x2
[СДНФ]
