Дискретка. Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений

• Название: Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений
• Анкор: Дискретка
• Дата: 25.04.2023
• Размер: 1.99 Mb.
• Имя файла: DISKMATH.pdf
• Тип: Учебник; #1089730
• страница: 5 из 29

б) отношение перпендикулярности двух прямых?
28. Доказать, что отношение {((x
1
, y
1
), (x
2
, y
2
)) | x
2 1
+ y
2 1
= x
2 2
+ y
2 2
} являет- ся отношением эквивалентности на множестве R
2
. Определить классы этой эквивалентности.
29. Доказать, что отношение {(a, b) | (a − b) — рациональное число} явля- ется отношением эквивалентности на множестве вещественных чисел.
30. Пусть на множестве ω определено отношение 6, задаваемое следую- щим правилом:
m 6 n ⇔ m делит n.
Считая, что 0 делит 0, показать, что 6 — частичный порядок. Для произвольных натуральных чисел m и n найти inf{m, n} и sup{m, n}
относительно указанного порядка.
31. Для обычных отношений 6 и < на множестве ω показать, что
< ◦ < 6= <, 6 ◦ < = < и 6 ◦ > = ω
2 32. Построить пример ч.у.м. с единственным минимальным элементом, но без наименьшего.
33. Рассмотрим на множестве R
2
отношение Парето Π:
(x
1
, y
1
) Π (x
2
, y
2
) ⇔ x
1 6 x
2
и y
1 6 y
2
.
Для точек A(a
1
, a
2
) и B(b
1
, b
2
) найти множество нижних и верхних гра- ней множества {A, B}. Чему равен inf{A, B} и sup{A, B}?
34. Построить линейный порядок на множестве комплексных чисел.
35. Составить матрицу отношения полного порядка, при котором нумера- ция элементов ведется: а) по возрастанию; б) по убыванию.

50
Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ
36. Проверить, являются ли частичными порядками бинарные отношения со следующими матрицами:
а)





1 1 1 1 0 0 1 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1





; б)





1 0 0 1 1 1 1 1 1 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1





; в)





1 0 0 0 1 1 1 1 1 1 0 0 1 0 1 0 0 1 1 1 0 0 0 0 1





;
г)





1 0 0 0 1 1 1 0 0 1 1 1 1 1 1 0 0 0 1 1 0 0 0 0 1





; д)





1 0 0 0 0 1 1 1 1 1 1 0 1 0 0 1 0 1 1 1 1 0 1 0 1





; е)





1 0 1 1 1 0 1 1 1 1 0 0 1 0 0 0 0 1 1 0 0 0 1 0 1





;
ж)





1 0 1 0 0 1 1 1 0 1 0 0 1 0 0 1 0 1 1 0 1 0 1 0 1





; з)





1 0 0 0 0 1 1 1 1 1 0 0 1 0 1 1 0 0 1 0 0 0 0 0 1





; и)





1 1 0 1 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 0 1 1





;
к)





1 0 0 0 0 1 1 1 1 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1





; л)





1 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1





; м)





1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 1 1 1 0 0 0 1





Построить диаграммы Хассе для заданных порядков. Есть ли в со- ответствующих частично упорядоченных множествах наименьшие или наибольшие элементы? Какие из этих частичных порядков линейные?
37. Построить всевозможные попарно неизоморфные четырехэлементые ч.у.м. hA; 6i. Какие из этих ч.у.м. самодвойственны, т. е. изоморфны
hA; >i?

Глава 2
АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ
§ 2.1.
Определения и примеры
Часто объектом изучения в математике и ее приложениях служит мно- жество вместе с определенной на нем структурой. Читателю уже известны поля, формирующие основу обычной арифметики, линейные пространства,
обеспечивающие связь геометрических объектов с операциями над числами,
множества с введенными на них бинарными отношениями. Все эти струк- туры образуют алгебраические системы, представляющие собой некоторые миры с определенными в них законами. Перейдем к точному определению алгебраической системы.
Рассмотрим непустое множество A. В § 1.2 было введено понятие
n-местной операции на множестве A (f : A
n
→ A). Отметим, что, поскольку операция f является функцией, для любого набора (x
1
, . . . , x
n
) ∈ A
n
ре- зультат применения операции f (x
1
, . . . , x
n
) однозначно определен. Так как область значений операции f лежит в множестве A, то будем говорить, что операция f замкнута на множестве A.
Сигнатурой или языком Σ называется совокупность предикатных и функциональных символов с указанием их местности. При этом множе- ства предикатных и функциональных символов не пересекаются. 0-Местный функциональный символ называется константным символом или просто
константой. Если α — функциональный или предикатный символ, то его местность обозначается через µ(α). n-Местные предикатные и функциональ- ные символы часто будем обозначать соответственно через P
(n)
и f
(n)
. Если в рассматриваемой сигнатуре используются стандартные символы, такие,
например, как + для операции сложения, 6 для отношения порядка, | для

52
Глава 2. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ
отношения делимости, 0 для константного символа и другие, то мы просто пишем Σ = {6}, Σ = {6, +, ·, 0}, Σ = {+, −, |, 0, 1} и т. д.
Алгебраической системой A = hA; Σi сигнатуры Σ называется непустое множество A, где каждому n-местному предикатному (функциональному)
символу из Σ поставлен в соответствие n-местный предикат (соответственно операция), определенный на множестве A. Множество A называется носите-
лем или универсумом алгебраической системы hA; Σi. Предикаты и функ- ции, соответствующие символам из Σ, называются их интерпретациями.
Обозначать интерпретации будем теми же буквами, что и соответствую- щие символы сигнатуры. Заметим, что интерпретацией любого константного символа является некоторый элемент (константа) из A.
Алгебраические системы в дальнейшем будут обозначаться готическими буквами A, B, . . . (возможно, с индексами), а их носители — соответствующи- ми латинскими буквами A, B, . . . (с соответствующими индексами). Иногда мы будем отождествлять носитель с алгебраической системой.
Мощностью алгебраической системы A называется мощность ее носите- ля A. В дальнейшем будем часто опускать слово “алгебраическая” и назы- вать A системой или структурой.
Непустая сигнатура Σ называется функциональной (предикатной), если она не содержит предикатных (функциональных) символов. Система A на- зывается алгеброй (моделью или реляционной системой), если ее сигнатура функциональна (предикатна).
Пример 2.1.1. 1. Набор hω; +, ·i является алгеброй с двумя двухмест- ными операциями.
2. Набор hω; 6, +, ·,
0
, 0, 1i является системой с бинарным отношением 6
(µ(6) = 2), двухместными операциями +, · (µ(+) = µ(·) = 2), одноместной операцией
0
: n 7→ n + 1 (µ(
0
) = 1) и двумя нуль-местными операциями
(константами) 0, 1 (µ(0) = µ(1) = 0).
3. Набор hZ; +, :,
√
2i не образует алгебру, поскольку деление не является операцией на множестве Z (например, 2 : 3 /
∈ Z), а элемент
√
2 не принадле- жит Z.
4. Набор hP(U); ∩, ∪, , 0, 1i с двухместными операциями ∩, ∪, одномест- ной операцией : A 7→ A, константами 0 = ∅ и 1 = U является алгеброй,
называемой алгеброй Кантора.
5. Алгеброй является любое кольцо.
6. Пара
­
{f (x) | f : R → R};
d
dx
®
(где
d
dx
— операция дифференцирова- ния) не является алгеброй, поскольку не всякая функция дифференцируема,

2.1. ОПРЕДЕЛЕНИЯ И ПРИМЕРЫ
53
но если рассмотреть множество A = {f (x) | f (x) дифференцируема беско- нечное число раз}, то отображение дифференцирования
d
dx
: f 7→
df
dx
является операцией на A и пара
­
A;
d
dx
®
образует алгебру. ¤
Заметим, что частичную операцию f , отображающую A
n
в A, можно рассматривать как (n + 1)-местное отношение
R
f
­ {(x
1
, x
2
, . . . , x
n
, y) | (x
1
, . . . , x
n
) ∈ A
n
и y = f (x
1
, . . . , x
n
)}.
Поэтому в последнем примере пару
­
{f (x) | f : R → R};
d
dx
®
можно считать алгебраической системой, если рассматривать
d
dx
как бинарное отношение
©
(f, g) | g =
df
dx
ª
Алгебра A сигнатуры Σ = {f }, где µ(f ) = 2, называется группоидом.
Единственная здесь операция f обычно обозначается символом ·: A = hA; ·i.
Если A — конечное множество, действия операции · можно задать квадрат- ной таблицей, в которой для каждой пары (a
i
, a
j
) ∈ A
2
записан результат действия ·(a
i
, a
j
). Такая таблица называется таблицей Кэли группоида A.
Группоид A называется полугруппой, если · — ассоциативная операция, т. е.
для всех элементов x, y, z ∈ A верно x · (y · z) = (x · y) · z. Полугруппа A на- зывается моноидом, если существует элемент e ∈ A, называемый единицей,
такой, что e · x = x · e = x для всех x ∈ A. Полугруппы и моноиды имеют особое значение в теории языков при обработке слов.
Пример 2.1.2. Пусть W (X) — множество слов алфавита X. Определим на W (X) операцию конкатенации ˆследующим образом: если α, β ∈ W (X),
то αˆβ = αβ, т. е. результатом является слово, полученное соединением слов
α и β (например, xyzˆzx = xyzzx). Операция ˆ ассоциативна, т. е. для лю- бых слов α, β, γ верно (αˆβ)ˆγ = αˆ(βˆγ). Следовательно, система hW (X);ˆi
является полугруппой. Так как для всех α ∈ W (X) верно Λˆα = αˆΛ = α,
где Λ — пустое слово, то Λ удовлетворяет свойству единицы. Таким образом,
система hW (X);ˆi является моноидом. ¤
Моноид A = hA; ·i называется группой, если для любого элемента
x ∈ A существует элемент x
−1
∈ A, называемый обратным к x, такой, что
x · x
−1
= x
−1
· x = e. Группа A называется коммутативной или абелевой,
если x · y = y · x для всех x, y ∈ A.
Пример 2.1.3. 1. Если hK; +, ·i — кольцо, то hK; +i — абелева группа.
2. Система hGL
n
(K); ·i, где GL
n
(K) ­ {A | A — матрица порядка n
над полем K, и det A 6= 0} является группой, которая некоммутативна при
n > 2. ¤

54
Глава 2. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ
§ 2.2.
Морфизмы
Пусть даны алгебраические системы A = hA; Σi и B = hB; Σi. Отобра- жение ϕ: A → B называется гомоморфизмом системы A в систему B, если выполняются следующие условия:
1) для любого функционального символа f
(n)
∈ Σ, соответствующих функций f
A
и f
B
в системах A и B и любых a
1
, a
2
, . . . , a
n
∈ A выполня- ется
ϕ(f
A
(a
1
, a
2
, . . . , a
n
)) = f
B
(ϕ(a
1
), ϕ(a
2
), . . . , ϕ(a
n
));
2) для любого предикатного символа P
(n)
∈ Σ, соответствующих преди- катов P
A
и P
B
в системах A и B и любых a
1
, a
2
, . . . , a
n
∈ A выполняется
(a
1
, a
2
, . . . , a
n
) ∈ P
A
⇒ (ϕ(a
1
), ϕ(a
2
), . . . , ϕ(a
n
)) ∈ P
B
.
Если ϕ: A → B — гомоморфизм, то будем его обозначать через
ϕ: A → B.
При гомоморфизме сохраняются действия операций и отношения. Это позволяет переносить изучение свойств с одной системы на другую.
Пример 2.2.1. Рассмотрим системы A = hZ; +, 6i и B = hZ
2
; +, 6i, где в системе B сложение задается по правилу
(a
1
, b
1
) + (a
2
, b
2
) = (a
1
+ a
2
, b
1
+ b
2
),
а отношение порядка —
(a
1
, b
1
) 6 (a
2
, b
2
) ⇔ a
1 6 a
2
и b
1 6 b
2
.
Отображение ϕ: Z → Z
2
, при котором ϕ(a) = (a, 0), является гомоморфиз- мом. Действительно, для любых a, b ∈ Z имеем
ϕ(a + b) = (a + b, 0) = (a, 0) + (b, 0) = ϕ(a) + ϕ(b),
и если a 6 b, то (a, 0) 6 (b, 0), т. е. ϕ(a) 6 ϕ(b). ¤
Гомоморфизм ϕ: A → B, являющийся инъекцией, называется мономор-
физмом. Гомоморфизм ϕ: A → B, являющийся сюръекцией, называется
эпиморфизмом, и при этом система B называется гомоморфным образом

2.2. МОРФИЗМЫ
55
системы A. Гомоморфизм ϕ: A → A называется эндоморфизмом. Сюръек- тивный мономорфизм ϕ: A → B, для которого ϕ
−1
— гомоморфизм, называ- ется изоморфизмом A на B и обозначается через ϕ: A ∼
→ B. Если существует изоморфизм ϕ: A ∼
→ B, то системы A и B называются изоморфными и обо- значается это так: A ' B.
Таким образом, условие A ' B означает, что существует биекция
ϕ: A ↔ B, удовлетворяющая следующим условиям:
1) для любого функционального символа f
(n)
∈ Σ, соответствующих функций f
A
и f
B
в системах A и B и любых a
1
, a
2
, . . . , a
n
∈ A выполня- ется
ϕ(f
A
(a
1
, a
2
, . . . , a
n
)) = f
B
(ϕ(a
1
), ϕ(a
2
), . . . , ϕ(a
n
));
2) для любого предикатного символа P
(n)
∈ Σ, соответствующих преди- катов P
A
и P
B
в системах A и B и любых a
1
, a
2
, . . . , a
n
∈ A выполняется
(a
1
, a
2
, . . . , a
n
) ∈ P
A
⇔ (ϕ(a
1
), ϕ(a
2
), . . . , ϕ(a
n
)) ∈ P
B
.
Изоморфизм ϕ: A ∼
→ A называется автоморфизмом системы A. Заметим,
что, поскольку изоморфизм ϕ: A ∼
→ B является биекцией A ↔ B, изоморф- ные системы равномощны.
Утверждение 2.2.1. 1. id
A
: A ∼
→ A.
2. Если ϕ: A ∼
→ B, то ϕ
−1
: B ∼
→ A.
3. Если ϕ: A
1
∼
→ A
2
и ψ: A
2
∼
→ A
3
, то ϕ ◦ ψ: A
1
∼
→ A
3
. ¤
Таким образом, отношение изоморфизма ' является эквивалентностью на любом множестве алгебраических систем (отметим, что класс всех алгеб- раических систем не является множеством, поскольку не существует множе- ства всех множеств). Это означает, что отношение изоморфизма разбивает множества алгебраических систем на классы эквивалентности, в каждом из которых содержатся системы, имеющие “одинаковое устройство”. Это да- ет возможность переносить изучение свойств с одной системы на другую,
изоморфную ей. Так, используя факт изоморфизма геометрического вектор- ного пространства пространству строк, работу с геометрическими объекта- ми можно свести к действиям с наборами чисел, что позволяет применять компьютеры.
Пример 2.2.2. 1. Рассмотрим множество векторов E
3
геометрическо- го векторного пространства с операциями сложения векторов и умножения

56
Глава 2. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ
векторов на вещественные числа. Получим систему A = hE
3
; +, {λ·}
λ∈R
i бес- конечной сигнатуры, где одноместные функции λ· ставят в соответствие век- тору

a вектор