• Ешқандай Нәтиже Табылған Жоқ

АЛМАТИНСКИЙ ИНСТИТУТ ЭНЕРГЕТИКИ И СВЯЗИ

N/A
N/A
Protected

Academic year: 2024

Share "АЛМАТИНСКИЙ ИНСТИТУТ ЭНЕРГЕТИКИ И СВЯЗИ"

Copied!
101
0
0

Толық мәтін

(1)

Министерство образования и науки Республики Казахстан

«Алматинский университет энергетики и связи имени Гумарбека Даукеева»

Некоммерческое акционерное общество

Л.Н. Астраханцева, М.Ж. Байсалова ДИСКРЕТНАЯ МАТЕМАТИКА

Учебное пособие

Алматы АУЭС

2021

(2)

УДК 519.6(075.8) ББК 22.1 я 73 А 91

Рецензенты:

доктор физико-математических наук,

профессор кафедры «Математика» КазНУ имени аль-Фараби М.К.Дауылбаев

кандидат физико-математических наук,

доцент кафедры «Математика» КазНУ имени аль-Фараби У.К.Койлышов

кандидат физико-математических наук,

доцент кафедры «Математика и математическое моделирование»

Алматинский университет энергетики и связи имени Гумарбека Даукеева Р.Е.Ким

Астраханцева Л.Н., Байсалова М.Ж.

А 91 Дискретная математика: Учебное пособие. – Алматы: Алматинский уни- верситет энергетики и связи имени Гумарбека Даукеева, 2021. – 100 с.: табл – 18, иллюстраций – 69, библиогр. – 18.

ISBN 978-601-7939-79-3

Учебное пособие предназначено для студентов всех форм обучения и специальностей, в программу которых входит предмет «Дискретная математика».

УДК 519.6(075.8)

ББК 22.1я73

А 91

© АУЭС, 2021

Л.Н. Астраханцева, М.Ж. Байсалова, 2021

(3)

3 1 Элементы теории множеств.

1.1 Множества

Понятия “множество”, “отношение”, “функция” и некоторые другие являются базовыми понятиями дискретной математики, составляют её основной словарь. Множество и элемент множества первичные понятия, т.е. не определяются с помощью других, более простых понятий, такие как, например, точка и прямая. Под множеством понимается совокупность некоторых объектов (предметов), которые называются элементами множества. Элементы множеств различны и различимы. Приняты следующие обозначения: A, B, X,…

- множества; a, b, x, x1, x2,…- элементы множеств; 𝑎 ∈ A - элемент 𝑎 принадлежит А, 𝑏 ∉ A - элемент 𝑏 не принадлежит А; N (или 𝜛) – множество натуральных чисел; Z – множество целых чисел; Q – множество рациональных чисел; I - множество иррациональных чисел; R – множество действительных чисел; C – множество комплексных чисел; Ø – пустое множество (не содержит ни одного элемента).

Конечные и бесконечные множества состоят соответственно из конечного и бесконечного числа элементов.

Способы задания множеств:

а) перечислением элементов, например, X = {x1, x2,…, xn}, A = {2,4,5,6,8,…};

б) с помощью характеристического свойства: A={x| Р(x)}, где P(x) – свойство Р, которым обладает элемент x, например, A = {x| x = 𝜋

2+ 𝜋𝑘; 𝑘 ∈ 𝑍 };

в) порождающей процедурой, которая описывает способ получения элементов из уже имеющихся элементов, например, множество M={1,2,4,8,16,…} можно задать так: 1) 1 ∈ M; 2) m ∈ M → 2m ∈ M.

Определения:

а) множество В называется подмножеством множества А (обозначается В ⊆ А), если каждый элемент множества В является элементом множества А:

B ⊆ A ⇔ ∀𝑥(𝑥 ∈ B ⇒ 𝑥 ∈ A), ⊆ - знак включения;

б) множества А и В называют равными, если они состоят из одних и тех же элементов: А =В ⇔ В ⊆ А и А ⊆В;

в) если В⊆ А и А ≠ В, то В является собственным подмножеством множества А: В ⊂ А - строгое включение.

(4)

4

Заметим, что для обозначения отношения включения применяют как знак строгого, так и не строгого включения, как для собственных, так и для несобственных подмножеств. И только если требуется различить эти подмножества, различают и эти знаки. Не следует путать знаки ∈ и ⊆:

1 ∈ {1,2,3}

{𝑎} ∈ {{𝑎}}

{1} ⊂ {1,2,3}

} - верно,

1 ⊆ {1,2,3}

1 ∉ {1,2,3}

{𝑎} ∈ {𝑎, 𝑏}

}- не верно.

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

Р

(А) или 2А. Итак,

Р

(А) = {B | B ⊆ A}. Булеан множества из n элементов, содержит 2n элементов.

П р и м е р 1.1.1A = {1,2,3},

Р

(А) ={Ø,{1},{2},{3},{1,2},{1,3},{2,3}, A}.

Р

(А) содержит 8 элементов, 8 = 23.

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

Операции над множествами.

∀A, B ∈

Р

(U) следующие операции определяются так:

а) объединение (сумма) (обозначается ∪, +): А∪В = {x| x А или x ∈В};

б) пересечение (произведение) (∩, ): А ∩ В = {x | x ∈ А и x ∈ В};

в) разность ( А \ В; А – В): А \ В = {x | x ∈ А и x ∉ В};

г) симметрическая разность или кольцевая сумма (⊕, , +):

А ⊕ В = (А \ В) ∪ (В \ А) = {x | (x ∈ А и x В) или (x ∈ В и x ∉ А)};

д) дополнение множества А (А): А= {x | x ∈ 𝑈 и x ∉ А}=U \ A.

Иллюстрация операций над множествами диаграммами Эйлера-Венна на рисунке 1.1.1.

АВ AB

U В

B A

(5)

5

А \ В АВ А

Рисунок 1.1.1

Операции объединения и пересечения допускают обобщения:

A1 ∪ A2 ∪ … ∪ An =

n

1 i

Ai

= , A1 ∩ A2 ∩… ∩ An =

n

1 i

Ai

= .

Свойства операций над множествами

Для преобразования теоретико-множественных выражений, упрощения записей, доказательств теорем и свойств необходимо знать свойства операций над множествами. Рассмотрим важнейшие из этих свойств. Пусть задан универсум U и множества A, B, C ⊂ U.

Таблица 1.1.1 – Свойства операций над множествами

Идемпотентность А ∪ А = А А ∩ А = А

Коммутативность А ∪ В= В ∪ А А ∩ В=В ∩ А Дистрибутивность А ∪ (В ∩ С) =

( А ∪ В) ∩ ( А ∪ С)

А ∩ (В ∪ С) = ( А ∩ В) ∪ ( А ∩ С) Ассоциативность А ∪ (В∪С) = ( А∪ В) ∪ С А ∩ (В∩С) = ( А∩В) ∩ С Свойства поглощения А ∪ (В ∩ А) = А А ∩ (В ∪ А) = А

Свойства нуля и единицы

А ∪ Ø=А А ∪ U=U

А ∩ Ø= Ø А ∩ U= A Законы де Моргана A ∪ B=A ∩ B A ∩ B=A ∪ B

Закон двойного отрицания или

инволютивности A = A

Свойства дополнения A ∪ A=U A ∩ A= Ø

Доказать эти свойства можно либо с помощью диаграмм Эйлера-Венна, либо формальными рассуждениями, опирающимися на определение операций, например, докажем 𝐴 ∪ 𝐵=𝐴 ∩ B.

U A

(6)

6

1 Доказательство с помощью диаграмм:

а) А∪ В 𝐴 ∪ 𝐵

в) A B

A ∩ B

Рисунок 1.1.2

На последних рисунках в пунктах а) и в) отмечена одна и та же область, что доказывает тождество.

2 Докажем A ∪ B=A ∩ B формальными рассуждениями.

В формальных рассуждениях исходят из того, что А = В А ⊆ В и В ⊆ А, а последнее имеет место по определению отношения включения: А ⊆ В

(x ∈ A x ∈ B) и В ⊆ А (x ∈ B x ∈ A), поэтому:

а) x ∈ A ∪ B x А∪В x A и x ∉ B x ∈ A и x ∈ B x ∈ A ∩ B;

б) x ∈ A ∩ B x ∈ A и x ∈ B x A и x ∉ B xА ∪ В ⇒ 𝑥 ∈ 𝐴 ∪ 𝐵.

Теорема. Для любых множеств А и В следующие условия эквивалентны:

а) А ⊆ В; б) А ∩ В = А; в) А ∪ В = В;

г) А \ В = Ø; д) A ∪ В = U.

В примере 1.1.2 свойства операций использованы для упрощения выражения.

П р и м е р 1.1.2 - 𝐴 ∩ 𝐵 ∪ 𝐵 = 𝐴 ∪ 𝐵 ∪ 𝐵 = 𝐴 ∪ 𝐵 ∪ 𝐵 = 𝐴 ∪ 𝐵.

Разбиения и покрытия множеств

Пусть дано множество А. А = {A1, A2, A3, …,An}- множество подмножеств А (семейство подмножеств).

U B

A

(7)

7

Определение. А называется покрытием множества A, если 1. ∀Ai ∈ А (Ai ⊂ A, Ai ≠ Ø); 2. A =

n

1 i

Аi

=

.

Определение. А называется разбиением множества А, если 1. ∀Ai ∈ А (Ai ⊂ A, Ai≠Ø); 2. A=⋃𝑛𝑖=1А𝑖; 3. ∀ Ai, Aj∈ А [Ai ≠ Aj Аi ∩ Аj = Ø].

Элементы разбиения, т.е. подмножества множества А также называются блоками разбиения.

П р и м е р 1.1.3 - А = {1, 2, 3}. А1 = {{1,2},{2,3},{1,3}} – покрытие;

А2= {{1},{2},{3}} – разбиение; А3= {{1},{2,3}} – разбиение; А4= {{1},{3}} – множество подмножеств множества А (ни булеан, ни покрытие, ни разбиение).

П р и м е р 1.1.4. - N– множество натуральных чисел. N0 , N1 - множества чётных и нечётных чисел. N = { N0, N1}- разбиение N.

Прямое произведение множеств

Упорядоченную последовательность из элементов x1, x2,…, xn будем обозначать (x1, x2,…, xn) или <x1, x2,…, xn> и называть кортеж длины n, упорядоченный набор или последовательность (конечная) из n элементов, вектор длины n, n-ка (энка). xii-ая координата или компонента. Если n = 2, то (x1,x2) – пара, упорядоченная двойка; n = 3 - (x1, x2, x3) – тройка, упорядоченная тройка; n = 0 - < >= Ø - кортеж, не содержащий элементов.

Если 𝑥⃗ = (x1,…xn), 𝑦⃗ = (y1,…,yn), то 𝑥⃗ = 𝑦⃗ ⇔ (𝑥1 = 𝑦1, 𝑥2 = 𝑦2, … , 𝑥𝑛 = 𝑦𝑛). Ясно, что (1,2) ≠ (2,1), {1,2}={2,1}.

Определение. Прямым (декартовым) произведением множеств А и В (обозначается А×В) называется множество таких пар (a, b), что a ∈ A и b ∈ В:

А×В = {(a, b) | a ∈ A и b ∈ В}.

Обобщение прямого произведения: A1×A2×…×An={(a1, a2,…,an)| a1 ∈ A1, a2 ∈ A2 ,…, an ∈ An}. Если A=B, то A×A=A2 ; A×A×…×A=An ; A1 =A; A0 ={Ø}.

n

П р и м е р 1.1.5 - A={1,2}, B={1,2,3}.

A×B={(1;1), (1;2), (1;3), (2;1), (2;2), (2;3)};

B×A={(1;1), (1;2), (2;1), (2;2), (3;1), (3;2)};

A×B ≠ B×A; A2 ={(1,1), (1,2), (2,1), (2,2)};

П р и м е р 1.1.6 - R×R = R2 = {(a,b) | a,b ∈ R, (a,b) – точки плоскости}.

(8)

8 1.2 Отношения

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

Например, если имеем множество стран мира, то можно рассматривать между странами такие отношения: «в стране x населения больше, чем в стране y» или

«страны х и у имеют общую границу»; если имеем множества мужчин, женщин и детей, то можно рассматривать отношение «х и у родители z» и т.д.

Определение. n-местным отношением P (n-местным предикатом) на множествах А1, А2, …, Аn называется любое подмножество прямого произведе- ния этих множеств: P ⊆ A1×A2×…×An и P = {(x1, x2,…, xn) | 𝑥1 ∈ A1,…, xn ∈ An}.

То, что элементы x1, x2,…, xn связаны соотношением Р записывается в виде:

(x1,…,xn) ∈ P или P(x1,…,xn). Если P ⊆ An, то Р – n-местное отношение на множестве А. n = 1, то P ⊆ A1 - одноместное (унарное) отношение или свойство;

n = 3, то P ⊆ A1×A2×A3 – трёхместное (тернарное) отношение.

Наиболее часто встречаются и хорошо изучены бинарные отношения (n=2) или соответствия P ⊆ A1×A2 или P = {(x, y) | x ∈ A1, y ∈ A2}. Записывают P(x,y) или xPy . Например, вместо <(x, y) или (x, y) ∈ < записывают x < y. Далее будем рассматривать бинарные отношения, называя их просто отношениями.

Определение. Областью определения отношения Р (обозначается DP) называется DP ={ x | (x,y) ∈ P для некоторого y}; областью значений (обознача- ется EP) называется EP ={y | (x,y) ∈ P для некоторого x} (т.е. DP – это множество первых координат пар Р, EP – вторых).

Отношение можно задать перечислением элементов, характеристическим свойством, графически, с помощью матриц.

Бинарные отношения на конечных множествах обычно задаются либо списком пар, либо матрицей, либо графически.

Определение. Пусть A={a1, a2,…, am}, B={b1, b2,…, bn} и P A×B.

Матрица [P] =(pij), размера m × n, называется матрицей отношения Р , если 𝑝𝑖𝑗 = {1,если (𝑎𝑖, 𝑏𝑗) ∈ 𝑃

0,если (𝑎𝑖, 𝑏𝑗) ∉ 𝑃 , i =1,2,…,m; j =1,2,…,n.

Графически отношение Р можно задать по-разному:

а) на координатной плоскости по осям координат отмечают элементы множеств А и В, тогда точки с координатами (x, y) представляют элементы отношения P ⊆ A×B, x ∈ A, y ∈ В;

б) на плоскости изображают две ограниченные области, в которых точками отмечают элементы множеств А и В, затем, если (x, y) ∈ P ⊆ A×B, то точки x и y соединяют стрелкой;

(9)

9

в) отношение P A2 можно задать ориентированным графом, т.е.

элементы x, y ∈ A, изображённые точками, соединяют стрелками.

П р и м е р 1.2.1 - A={a,b,c}, B={1,2,3,4}, P1={(a,1), (b,1), (b,3), (c,2)} ⊆ A×B, P2 ={(1,1), (1,2), (2,3), (3,1), (4,3)} ⊆ B2.

Матричное задание отношений:

 

1

1 0 0 0

1 0 1 0

0 1 0 0

P

 

 

=   ,

 

2

1 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 P

 

 

 

= 

 

 

;

Графическое задание отношений:

а)

б)

в)

Рисунок 1.2.1

Определения. Пусть P ⊆ A × B, P = {(a, b) | a ∈ A, b ∈ B}.

а) P-1 – обратное Р P-1 = {(b, a) | (a, b) ∈ P}, P-1 ⊆ B×A;

б) Р - дополнение PР ={(a, b) | (a, b) ∉ P}, Р ⊆ A×B;

в) I – тождественное отношение на множестве А (иногда обозначается idA). I = {(a, a) | a ∈ A}, I ⊆ A2 (называют также диагональю в A2 , т.к. его матрицей является единичная матрица);

г) U – универсальное отношение U ={(a,b) | a ∈ A и b ∈ A}, т.е. U=A2. Определение. Композицией (произведением) бинарных отношений P1 ⊆ A×B и P2 ⊆ B×C (обозначается P1 ∘ P2) называется отношение

Р = P1 ∘ P2 = {(a, c) | a ∈ A, c ∈ C и ∃ b ∈ B, что (a, b) ∈ P1 и (b, c) ∈ P2}.

P1 a

b c

4 3

2

1

A B

(10)

10

Рисунок 1.2.2

П р и м е р 1.2.2 - A = {1,2,3,4}, B = {6,7,8}; C = { 10,11,12}.

Пусть P1 = {(1,7), (4,6), (2,8)}⊆ A×B,

P2 = {(6,10), (6,11), (7,10), (8,12)} ⊆ B×C, тогда P11 = {(7,1), (6,4), (8,2)}; т.к.

A×B = {(1,6), (1,7), (1,8), (2,6), (2,7), (2,8), (3,6), (3,7), (3,8), (4,6), (4,7), (4,8)}, то Р1= ( A × B) / P1 = {(1,6), (1,8), (2,6), (2,7), (3,6), (3,7), (3,8), (4,6), (4,7), (4,8)};

P1 ∘ P2 = {(1,10), (4,10), (4,11), (2,12)}. Эта композиция получается так: для первого элемента (1,7) отношения P1 находим элементы отношения P2 , у которых число 7 стоит на первом месте – это (7,10), делаем вывод, что элемент (1,10) входит в композицию; для второго элемента (4,6) находим элементы P2 , у которых 6 стоит на первом месте – это (6,10) и (6,11), тогда (4,10), (4,11) входят в композицию и т.д. P2 ∘ P1 = Ø.

Теорема. Для любых бинарных отношений P, Q, R выполняются следующие свойства:

а) (P-1)-1=P;

б) (P ∘ Q)-1=Q-1 ∘ P-1;

в) (P ∘ Q) ∘ R=P ∘ (Q ∘ R) (ассоциативность);

г) PQ QP (свойство коммутативности в общем случае не выполня- ется).

Основные свойства матриц бинарных отношений

1 Если P,Q ⊆ A×B, [P] =(pi,j), [Q]=(qi,j), то [P ∪ Q] =(pij + qij) =[P]+[Q], где элементы матриц складываются по правилам: 0 + 0 = 0, 1 + 0 = 0 + 1 = 1 + 1 =1;

[P ∩ Q]= = (pij * qij) = [P] * [Q], где элементы матриц перемножаются по обычным правилам: 0*0=0*1=0*1=0, 1*1=1.

P1 o P2

c b C

B A

a

P1 P2

(11)

11

2 Если P ⊆ A×B, Q ⊆ B × C, то [P ∘ Q]=[𝑃] ⋅ [𝑄] - обычное умножение матриц, но элементы матриц [P] и [Q] складываются и умножаются по правилам из свойства 1.

3 Если P-1 отношение, обратное к P, то [P-1] = [P]T. 4 Если P ⊆ Q и [P] = (pij), [Q] = (qij), тогда pij qij.

5 Если I–тождественное отношение, то [ I ] =





1 0 0 0

...

...

...

...

0 0 1 0

0 0 0 1

- единичная матрица.

6 Если P - дополнение Р, то [P] равна матрице отношения Р, в которой нули заменены единицами и единицы нулями.

П р и м е р 1.2.3 –

[𝑃] = (1 0

0 1), [𝑄] = (0 1

0 1), тогда [𝑃 ∪ 𝑄] = [𝑃] + [𝑄] = (1 0

0 1) + (0 1

0 1) = (1 1 0 1);

[𝑃 ∩ 𝑄] = [𝑃] ∗ [𝑄] = (1 0

0 1) ∗ (0 1

0 1) = (0 0 0 1); [𝑃 ∘ 𝑄] = [𝑃] ⋅ [𝑄] = (1 0

0 1) ⋅ (0 1

0 1) = (0 1

0 1); [𝑄−1] = (0 0

1 1), [𝑄] = (1 0 1 0). Свойства отношений

Таблица 1.2.1 – Свойства отношения P ⊆ A2

P определение [P]

рефлексивное ∀a ∈ A (a,a) ∈ P I ⊆ P





1 1

1

антирефлексивное ∀a ∈ A (a,a) ∉ P Р ∩ I = Ø





0 0

0

симметричное ∀a,b ∈ A (a,b) ∈ P

(b,a) ∈ P

P = P-1, [P] = [P]T; антисимметричное ∀a,b ∈ A[(a,b) ∈ P и

(b,a) ∈ P a = b]

Р ∩ Р-1 ⊆I [PP-1]=[P]*[P-1]=

=





* 0 0 0

0 0

* 0

0 0 0

*

транзитивное ∀a,b,c ∈ A [ (a,b) ∈ P и (b,с) ∈ P (a,c) ∈ P]

P ∘ P ⊆ P если [P∘P] = (aij), [P]=(pij), то aij pij

(12)

12

Проверить, какими свойствами обладает отношение, на практике лучше всего по его матрице.

П р и м е р 1.2.4 - Пусть дано отношение:

P = {(1,2), (2,3), (3,2)} ⊆ A2, А = {1,2,3}.

Проверим, какими свойствами оно обладает.

Составим матрицу этого отношения [P] = (

0 1 0

0 0 1

0 1 0

).

• P не рефлексивное, т.к. на главной диагонали матрицы нет единиц;

• P антирефлексивное, т.к. на главной диагонали матрицы все нули;

• P не симметричное, т.к. (1;2) ∈ P, но (2;1) ∉ P или [P] ≠ [P]T = (

0 0 0 1 0 1 0 1 0

);

• P не антисимметричное, т.к. (2;3) ∈ P, (3;2) ∈ P, но 2 ≠ 3, или в матрице [𝑃] ∗ [𝑃]𝑇 = (

0 1 0

0 0 1

0 1 0

) ∗ (

0 0 0 1 0 1 0 1 0

) = (

0 0 0 0 0 1 0 1 0

)

не все элементы вне главной диа-гонали нули;

• P не транзитивное, т.к., например, (1,2) ∈ P, (2,3) ∈ P, но (1,3) ∉ P или для:

[P] = (

0 1 0

0 0 1

0 1 0

) = (рij),

[PP]= (

0 1 0

0 0 1

0 1 0

) ⋅ (

0 1 0

0 0 1

0 1 0

) = (

0 0 1

0 1 0

0 0 1

) = (aij), условие

aij pij не выполняется для всех i,j, например, a13 =1, р13 = 0, т.е. a13 > р13. Многие отношения обладают определённым набором указанных выше свойств, и этот набор встречается так часто, что обладающие им отношения заслуживают специального названия и отдельного изучения.

Отношение эквивалентности

Определение. Отношение P называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно (обозначается ~, E, ≡).

Примеры отношений эквивалентности:

а) отношение равенства на любом множестве:

1) x = x;

2) x = yy = x;

3) x = y; y = zx = z;

(13)

13

б) отношение параллельности на множестве прямых на плоскости.

Определение. Пусть Е – отношение эквивалентности на множестве А и х А. Подмножество элементов множества А, эквивалентных x, называется классом эквивалентности элемента х. Обозначается: [x]E, E(x). Таким образом, E(x)={y | yEx}.

Определение. Множество классов эквивалентности называется фактор - множеством множества А относительно эквивалентности Е, обозначается А/Е:

А/Е={E(x) | x A}. Фактор –множество является подмножеством булеана.

П р и м е р 1.2.5 - А – множество студентов в университете. Е – отношение принадлежности к одной группе. [x]E-студенты одной группы. А/Е– множество студенческих групп университета.

Из определений ясно, что

1) любой элемент класса эквивалентности порождает класс эквивалентности, т.е. b ∈ [a] → [a]=[b];

2) каждый класс эквивалентности содержит хотя бы один элемент, т.е. ∀ а ∈ А, [a] ≠ Ø;

3) никакой элемент множества А не может принадлежать двум различным классам: aEb → [a] = [b].

Теорема. Фактор – множество А/Е является разбиением множества А.

Обратно, если А ={Ai} какое-то разбиение множества А, то ему соответствует некоторое отношение эквивалентности Е: xEyx,y ∈ Ai для некоторого i или E={(x;y) | x, y ∈ Ai для некоторого i }.

Таким образом, существует взаимно однозначное соответствие между множеством всех разбиений А и множеством всех отношений эквивалентности на множестве А.

П р и м е р 1.2.6 - А={1,2,3,4}. А ={{1}, {2,3,4}}={A1,A2}- разбиение А.

E={(x; y) | x, y ∈ Ai, i = 1,2} ={(1,1), (2,2), (2,3), (2,4), (3,2), (3,3), (3,4), (4,2), (4,3), (4,4)}- отношение эквивалентности, соответствующее данному разбиению.

П р и м е р 1.2.7 - A = {1, 2, 3, 4, 5, 6}, P ⊆ A2,

P ={(1;1); (2;2); (3;3); (4;4); (5;5); (6;6); (1;2); (1;4); (2;1); (2;4); (3;5); (5;3); (4;1);

(4;2)}.

Покажем, что данное отношение является отношением эквивалентности.

По его матрице

(14)

14 [P] =

1 0 0 0 0 0

0 1 0 1 0 0

0 0 1 0 1 1

0 1 0 1 0 0

0 0 1 0 1 1

0 0 1 0 1 1

определяем, что P рефлексивно, симметрично, транзитивно (см. выше), и следовательно Р есть отношение эквивалентности на множестве А. Построим классы эквивалентности и фактор – множество:

[1]P ={x | (x;1) ∈ P} ={1,2,4}; [2]P ={x | (x;2) ∈ P} ={1,2,4};

[3]P ={x | (x;3) ∈ P} ={3,5}; [4]P ={x | (x;4) ∈ P} ={1,2,4};

[5]P ={x | (x;5) ∈ P} ={3,5}; [6]P ={x | (x;6) ∈ P} ={6}.

Таким образом, имеется только три различных класса эквивалентности:

[1] = [2] = [4] = {1,2,4}, [3] = [5] = {3,5}, [6] = {6}.

Фактор – множество A/Р = {[1], [3], [6]} = {{1,2,4}, {3,5},{6}} является разби-ением множества А, которое соответствует данному отношению эквивалентности.

Отношение порядка

Определение. Отношение Р на множестве А называется отношением порядка если оно антисимметрично и транзитивно. Часто обозначается символом <.

Если к тому же оно:

1) рефлексивно, то называется частичным или нестрогим порядком ( ≤ );

2) антирефлексивно, то называется отношением строгого порядка ( < ).

Определение. Пусть на множестве А задано отношение порядка <, если для любых двух элементов a и b этого множества имеет место a < b или b < a, то элементы называются сравнимыми, в противном случае несравнимыми.

Определение. Частичный порядок на множестве А называется линейным или цепью, если любые два элемента этого множества сравнимы.

Множество А, на котором определен частичный (линейный) порядок, называется частично упорядоченным множеством (ч.у.м) (линейно упорядоченным множеством (л.у.м)). Обозначается (А, <).

П р и м е р 1.2.8 – A ={a, b, c}. P ={(a,a), (a,b), (b,b), (c,c)} – отношение частичного порядка (т.е. рефлексивно, антисимметрично, транзитивно), что легко проверить по его матрице [P] = (

1 1 0 0 1 0 0 0 1

). Р не является линейным

порядком, т.к. a и c, b и c не сравнимы.

(15)

15

Примерами линейно упорядоченных множеств являются множества N, Z, Q, R, где определён естественный порядок.

Определение. Элемент a упорядоченного множества А называется наибольшим (наименьшим), если xa (ax) для всех ∀х ∈ А. Л.у.м. называется вполне упорядоченным множеством (в.у.м), если любое его непустое подмножество имеет наименьший элемент.

П р и м е р 1.2.9 - (N; ≤) – в.у.м. ([0;1]; ≤) – не является в.у.м., т.к., например, (0;1] ⊆ [0;1], но (0;1] не содержит наименьшего элемента.

Определение. Рассмотрим ч.у.м. (Х, ≤). Говорят, что элемент у покрывает элемент х, если ху и не существует такого элемента z, что х < z < y.

В случае конечного множества Х, ч.у.м. (Х, ≤) можно представить в виде схемы, в которой каждый элемент изображается точкой на плоскости. Если у покрывает х, то точки х и у соединяют отрезком, причём точку, соответствующую х, располагают ниже точки у. Если отношение порядка нестрогое, то в каждой точке изображается петля. Кроме того, т.к. отношение порядка транзитивное, например, (a, b) ∈ P, (b, с) ∈ P и (a, c) ∈ P, то точки а и с не надо соединять отрезком, т.к. они соединены через точку b. Такие схемы называют диаграммами Хассе.

П р и м е р 1.2.10 - Рассмотрим ч.у.м. (

Р

(А), ⊆) = {(𝐴𝑖, 𝐴𝑗) | 𝐴𝑖 ⊆ 𝐴𝑗}, где A = {𝑎, 𝑏, 𝑐},

Р

(А) булеан А. Диаграмма Хассе для (

Р

(А), ⊆) на рисунке 1.2.3 а); для л.у.м. ({1, 2, 3, 4}, ≤) с обычным отношением порядка на множестве натуральных чисел, не превосходящих четырёх, диаграмма Хассе изображена на рисунке 1.2.3 б); диаграмма Хассе для отношения из примера 1.2.8 на рисунке 1.2.3 в).

а) б)

в)

Рисунок 1.2.3

c

a b

(16)

16 Лексикографический порядок

Лексикографический порядок лежит в основе упорядочения слов в различных словарях. Рассмотрим непустое множество символов Х ={x, y, …}, называемое алфавитом. Словами будем называть конечные наборы написанных друг за другом элементов Х. Элемент xi слова x1, x2,…, xn назовём его i-ой координатой, а число n - его длиной.

Определение. Пусть W(X) – множество слов алфавита Х, пусть ≤ - отношение порядка на множестве Х, т.е. (Х, ≤) – упорядоченное множество.

Отношение лексикографического порядка (обозначается < или L) на W(X) зада- ётся по правилу: x1, х2, …, xm L y1, y2, …, yn , если выполнено одно из условий:

а) x1 < y1;

б) xi = yi i: 1 ≤ i m, m < n;

в) xi = yi i: 1 ≤ i k, xk+1 < yk+1.

Функциональные отношения (функции)

Определение. Бинарное отношение f ⊆ А×В называется функциональным или функцией из множества А в множество В, если:

а) (x, y1) ∈ f, (x, y2) ∈ fy1 = y2 или ∀x ∈ A ∃! y ∈ B, (x, y) ∈ f;

б) Df = A, Ef ⊆ B, где Df - область определения функции, Ef - область значений.

В этом случае функцию иногда называют тотальной или всюду определённой; если Df ⊆ A, то f называют частичной функцией или частично определённой. В математике, как правило, рассматривают тотальные функции и называют их просто функциями.

П р и м е р 1.2.11– A = {1,2,3}, 𝑓 = {(1,2), (2,3), (3,2)} ⊆ 𝐴2 - функция, т.к.

𝐷𝑓 = 𝐴, 𝐸𝑓 ⊆ 𝐴;

𝑃 = {(1,1), (1,2), (2,3)} ⊆ A2– не функция, т.к. содержит пары (1,1) и (1,2) с одинаковыми первыми и разными вторыми элементами;

отношение 𝑃 = {(𝑥; 𝑥2+ 𝑥 + 1) |𝑥 ∈ 𝑅} - функция, т.к. из того, что 𝑥 = 𝑦 следует 𝑥2+ 𝑥 + 1 = 𝑦2+ 𝑦 + 1;

𝑃 = {(𝑥2; 𝑥) | 𝑥 ∈ 𝑅} – не функция, т.к. содержит пары с одинаковыми первыми и разными вторыми элементами, например, (1, −1) ∈ 𝑃, (1,1) ∈ 𝑃; 𝑃 = {(𝑥; √𝑥) | 𝑥 ∈ 𝑅} - частичная функция, т.к. 𝐷𝑃 = [0; +), 𝐷𝑃 ⊆ 𝑅.

Если задана функция f = {(x,y) | x ∈ A, y ∈ B}, то x- аргумент, y- значение функции. Различные обозначения функции: y = f (x), f: A→B, f: x y; A f B, x f у. Говорят также, что f ставит в соответствие элементу х элемент у.

(17)

17

Пусть f = {(x, y) | x ∈ A, y ∈ B} – функция. Она называется:

а) инъективной (инъекцией, разнозначной), если (x1, y) ∈ f и (x2, y) ∈ fx1 = x2 (или x1 x2f (x1) ≠ f (x2)), при этом 𝑓−1- частичная функция;

б) сюръективной (сюръекцией, отображением А на В), если ∀y ∈ B,

x ∈A, что (x; y) ∈ f, т.е. Ef = B;

в) биективной (биекцией, взаимно-однозначным соответствием), если она является и инъективной и сюръективной (для тотальной функции).

Обозначается: АВ.

Заметим, что если функция частичная, то, в случае её инъективности и сюръективности, она не всегда биективна, например, 𝑃 = {(𝑥; 𝑦)|𝑦 = 𝑙𝑛 𝑥 , 𝑥, 𝑦 ∈ 𝑅} (𝑃 ⊆ 𝑅 × 𝑅) - частичная функция, т.к. 𝐷𝑃 = (0, +), 𝐷𝑃 ⊆ 𝑅. Она инъективна, т.к. для любых 𝑥1 ≠ 𝑥2 из области определения выполняется 𝑙𝑛 𝑥1 ≠ 𝑙𝑛 𝑥2 ; она сюръективна, т.к. 𝐸𝑃 = 𝑅, но биекции нет, т.к. существуют 𝑥 ∈ 𝑅 ( например, 𝑥 = −1), которым не соответствует ни один 𝑦 ∈ 𝑅.

Если биекция f : АА, то она называется подстановкой множества А.

Простейший пример подстановки есть тождественное отношение I.

П р и м е р 1.2.12 - Рассмотрим три функции 𝑓𝑖 : 𝑅 → 𝑅(𝑖 = 1,2,3).

1) 𝑓1(𝑥) = 𝑒𝑥 - инъективна, т.к. для любых 𝑥1 ≠ 𝑥2 выполняется 𝑒𝑥1 ≠ 𝑒𝑥2; но не сюръективна, т.к. 𝐷𝑓1 = 𝑅, 𝐸𝑓1 ⊆ 𝑅 ( см. рисунок 1.2.4);

2) 𝑓2(𝑥) = 𝑥3− 4𝑥 - сюръективна, т.к. 𝐸𝑓2 = 𝑅, но не инъективна, поскольку существуют 𝑥1 ≠ 𝑥2, но 𝑓2(𝑥1) = 𝑓2(𝑥2) (см. рисунок 1.2.5);

3) 𝑓3(𝑥) = 𝑥 + 3 - биективна, каждому 𝑥 ∈ 𝑅 соответствует один 𝑦 = 𝑓3(𝑥) ∈ 𝑅 и, наоборот, (график – прямая линия).

Рисунок 1.2.4 Рисунок 1.2.5

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

П р и м е р 1.2.13 - Рассмотрим функции 𝑓𝑖: [0,1] → [0,1], (𝑖 = 1,2,3,4), графики которых изображены на рисунке 1.2.6:

(18)

18

Рисунок 1.2.6 По графикам можно установить, что

а) 𝑓1(𝑥) - сюръекция (не инъекция); б) 𝑓2(𝑥) - инъекция (не сюръекция);

в) 𝑓3(𝑥) - биекция; г) 𝑓4(𝑥) - не инъективная и не сюръективная функция.

1.3 Понятие о мощности множеств

Часто возникает необходимость сравнивать множества по числу элементов. В этом случае возникает понятие мощности множества.

Определение. Множества А и В называются эквивалентными (обозначается А~В) если существует биекция f : АВ (т.е. между ними можно установить взаимно однозначное соответствие (в.о.с.)).

Очевидно, что два конечных множества эквивалентны тогда и только тогда, когда они имеют одинаковое число элементов. Если два множества бесконечны и между ними можно установить в.о.с., то они обладают также чем- то общим, что мы будем называть мощностью. Итак, любые два эквивалентных множества (конечные или бесконечные) имеют одинаковую мощность или являются равномощными. Или более точное определение.

Определение. Мощностью множества А называется класс всех множеств, эквивалентных множеству А (мощность обозначается |𝐴|).

Имеется три возможности:

а) если А - конечное множество, имеет n элементов, то |𝐴|= n;

б) если А - бесконечное множество и эквивалентно множеству нату- ральных чисел N, то А называют счётным множеством, записывают |𝐴|=. Таким образом, у счётного множества все элементы можно пронумеровать;

в) существуют бесконечные множества, которые нельзя привести во в.о.с.

с множеством натуральных чисел. Например, установлено, что множество всех

(19)

19

действительных чисел отрезка [0,1] не является счётным (теорема Кантора).

Принято мощность этого множества называть континуум (часто обозначается с), а множества такой мощности континуальными.

Доказано, что если А континуальное множество, то |𝐴| = 𝑐 = 2𝜔, т.е.

мощность континуума равна мощности множества всех подмножеств счётного множества. Вообще, для любого множества А: |

Р

(А)| = 2|𝐴|, где

Р (А) – булеан.

Примеры счётных множеств:

а) множество целых чисел Z, а также 𝑍+, 𝑍; б) множество рациональных чисел Q;

в) любое бесконечное подмножество множества N, например, {2,4,6,8,…};

г) 𝑁2 ( вообще 𝑁𝑛~𝑁).

Примеры континуальных множеств:

а) множество всех действительных чисел R или множество точек числовой оси;

б) множество всех точек плоскости (пространства) 𝑅 × 𝑅(𝑅 × 𝑅 × 𝑅);

в) множество всех подмножеств счётного множества ( т.е. булеан счётного множества).

Как показано в теории множеств, для множества любой мощности множество его подмножеств имеет более высокую мощность. Поэтому не существует множества максимальной мощности. На мощность множеств можно смотреть как на новый объект, называемый кардинальным числом или кардиналом. Примерами кардиналов могут быть:

а) любое натуральное число (как мощность конечного множества);

б) 𝜔, 2𝜔 = 𝑐, 22𝜔и т.д.

Отметим, что существование биекции между двумя множествами позволяет перенести изучение свойств с одного множества на другое, что многое упрощает, например, некоторые свойства конечного множества А,

|𝐴| = n можно изучать по множеству {0, 1, 2, 3,…, n-1}.

(20)

20 2 Элементы математической логики

2.1 Высказывания и логические операции

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

Определение. Высказыванием называется повествовательное предложение, о котором в данной ситуации можно говорить, что оно истинно или ложно.

П р и м е р 2.1.1 – Высказывание: «дважды два – четыре» - истинно;

высказывание: «тенге – российская валюта» - ложно.

Определение. Простое (элементарное) высказывание рассматривается как некое неделимое целое. Обозначается А, В, С, ... , Р, … ; сложным (составным) называется высказывание, составленное из простых с помощью логических связок (операций).

Основными логическими операциями (связками) являются:

а) конъюкция (операция «и», логическое произведение).

Конъюнкцией двух высказываний P и Q (обозначается 𝑃 ∧ 𝑄, 𝑃 ⋅ 𝑄, 𝑃𝑄, 𝑃&𝑄, читается “Р и Q”) называется высказывание, истинное тогда и только тогда, когда истинны оба высказывания и ложное во всех остальных случаях;

б) дизъюнкция (операция «или», логическая сумма). Дизъюнкцией двух высказываний P и Q (обозначается 𝑃 ∨ 𝑄, 𝑃 + 𝑄, читается “Р или Q”) называется высказывание, ложное, если оба высказывания ложные и истинное во всех остальных случаях;

в) отрицание (инверсия). Отрицанием высказывания P (обозначается P, ¬P, читается “не Р”) называется высказывание, истинное, когда P ложное и ложное, когда P истинное;

г) импликация (логическое следование). Импликацией двух высказываний P и Q (обозначается 𝑃 → 𝑄, 𝑃 ⊃ 𝑄, читается, “если Р, то Q”, “Р влечёт Q”) называется высказывание, ложное, когда Р истинное, а Q ложное и истинное во всех остальных случаях;

Ақпарат көздері

СӘЙКЕС КЕЛЕТІН ҚҰЖАТТАР

Если сегмент стека создан , а комбинированный тип STACK не используется программист должен явно загрузить в регистр ss адрес сегмента ( подобно

Рисунок 2.12 - Главное окно программы в подключенном состоянии.. Далее отключите программу от лабораторной установки; для этого выберите

5) Щелкнуть по кнопке ОК для сохранения и активизации сделанных изменений... Выше говорилось об удалении временных файлов Интернета. Удобно, если

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

Наличие перемычек между магистралями отдельных п/ст обеспечивает надежность электроснабжения при минимальных затратах на устройство резервирования (для

Более того, если щели не являются соседними и расстояние между их центрами равно не d, а 2d, 3d, 4d..., то из геометрических соображе- ний очевидно, что разность хода увеличится в целое

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

Изобразите на рисунке траекторию и покажите для двух ее произвольных точек направления Рисунок А.2 Рисунок А.1... 11 векторов скорости 𝑣⃗ и ускорения