Лекции по дискретной математике. Математическая логика. Зарипова Э.Р - 8 стр.

UptoLike

ВУЗ: 

РУДН | Москва

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

Рубрика: 

8
обозначается f(A) . Если соответствие f при этом сюръективно, т.е.
каждый элемент В имеет прообраз в А, то говорят, что имеет место
отображение А на В (сюръективное отображение). Если f(A)
состоит из единственного элемента, то f называется функцией -
константой.
Пусть даны функции f: А
→
В и g: B
→
C. Функция h: А
→
C
называется композицией f и g (обозначение f
оg), если имеет место
равенство h(a)=g(f(a)), a
∈
A. Композиция f и g представляет собой
последовательное применение функций f и g .
Алгебры.
Функцию
ϕ
типа
ϕ
: M
n
→
M будем называть n-арной операцией
на множестве M; n называется арностью операции
ϕ
. Множество
М вместе с заданной на нем совокупностью операций
Φ
=
{ϕ
1
,…,
ϕ
m
}
, т.е. система A=
{
M;
ϕ
1
,…,
ϕ
m
}
, называется алгеброй;
М называется основным,
или несущим, множеством алгебры А.
Вектор арностей операций алгебры называется ее типом,
совокупность операций
Φ
-сигнатурой.
Множество L
⊆
M называется замкнутым относительно n-арной
операции
ϕ
на М, если
ϕ
(L
n
)
∈
L, т.е. если значения
ϕ
на аргументах
из L принадлежат L. Если L замкнуто относительно всех операций
ϕ
1
,…,
ϕ
m
алгебры А, то система A
′
=
{
L;
ϕ
1
,…,
ϕ
m.
}
называется
подалгеброй А
(при этом ,
ϕ
1
,…,
ϕ
m.
рассматриваются как операции
на L).
Пример1.1.
Пусть задано множество U. Множество всех его
подмножеств называется булеаном
U и обозначается через
Β
(U) .
Алгебра
Β
={
Β
(U);
∪
,
∩
, -} называется булевой алгеброй множеств
над U, ее тип (2,2,1). Элементами основного множества этой
алгебры являются подмножества U . Для любого U
′⊆
U
Β′
={
Β
(U
′
);
∪
,
∩
,-} является подалгеброй В. Например, если
U=
{
a,b,c,d
}
, то основное множество алгебры В содержит 16
элементов; алгебра
Β′
={
Β
(U
′
);
∪
,
∩
,-}, где U
′
=
{
a,b
}
- подалгебра B;
ее основное множество содержит четыре элемента.

Страницы