Дискретная математика. Кулаков Ю.В - 13 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

Задачи и упражнения
1 Установить, является ли группоидом, идемпотентным группоидом, абелевым группоидом,
полугруппой, абелевой полугруппой, группой, абелевой группой алгебра A =
〈
M, S
〉
с носителем М и
сигнатурой S:
а) М = {0, 1}, S = {
⊕
}, где
⊕
– операция сложения по модулю 2;
б) М = {0, 1}, S = {
⊗
}, где
⊗
– операция умножения по модулю 2;
в) М = {
∅
,{a}}, S = {
∪
}, где
∪
– операция объединения множеств;
г) М = {
∅
,{a}}, S = {
∩
}, где
∩
– операция пересечения множеств.
2 Установить, является ли кольцом, телом, полем алгебра A =
〈
M, S
〉
с носителем М и сигна-
турой S:
а) М = {0, 1}, S = {
⊕
,
⊗
}, где
⊕
,
⊗
– операции сложения и умножения по модулю 2 соответ-
ственно;
б) М = {
∅
,{a}}, S = {
∪
,
∩
}, где
∪
,
∩
– операции объединения и пересечения множеств соот-
ветственно.
3. ОТНОШЕНИЯ. СПОСОБЫ ЗАДАНИЯ И СВОЙСТВА.
ПОНЯТИЕ МОДЕЛИ
Фундаментальным понятием дискретной математики является понятие отношения, которое исполь-
зуют для обозначения связи между какими-либо объектами.
Квадратом множества М называется декартово произведение двух равных между собой множеств:
М × М = М
2
. Бинарным отношением Т в множестве М называется подмножество его квадрата: Т ⊂ М
2
.
Говорят, что элементы m
i
и m
j
находятся в отношении T, если (m
i
, m
j
) ∈ T. Совокупность множества М с
заданным в нем бинарным отношением Т ⊂ М
2
называется графом G:
G = 〈M, T〉,
где M – носитель графа (множество вершин); T – сигнатура графа (множество дуг).
Рассмотрим задание бинарного отношения с помощью матрицы смежности и фактор-множества.
При матричном задании используют двумерную таблицу – матрицу смежности, каждой строке
(столбцу) которой взаимно однозначно сопоставляют элемент множества М. Тогда каждая клетка (i, j)
таблицы взаимно однозначно соответствует элементам множества М
2
. Клетку (i, j), которая соответст-
вует элементу, принадлежащему Т ⊂ М
2
, как-то отличают, например зачерняют или помещают в нее
единицу; остальные клетки оставляют незачерненными или записывают в них нули.
Рассмотрим предложенную фон Нейманом блок-схему ЭВМ, которая состоит из множества уст-
ройств
M = {a, b, c, d, e},
где a – устройство ввода; b – арифметическое устройство (процессор); c – устройство управления; d –
запоминающее устройство; e – устройство вывода.

Страницы