Функции и отношения, их свойства

Пусть E произвольное множество и пусть декартова степень равняется: En=ExEx…E {n раз}, объект f(x1,…,xn): En→E есть n местная функция fn или функция n переменных определённая на множестве E. Нульместная функция есть константа из E.

Определение: Пусть F есть некоторое множество функций из PE (множество всех функций определённых на E), тогда:

1. Всякая функция из E есть суперпозиция над F.

2. Если функция f(x1,…,xn) принадлежит F и каждая из A1,…,An есть либо суперпозиция над F либо переменная, то f(A1,…,An) есть суперпозиция над F.

Замечание: Суперпозиция над F есть обычная подстановка построенная из функций множества F. Суперпозиция над F допускает переименование переменных.

Определение: Класс M функций из PE функционально замкнут, если вместе с любыми своими функциями класс M содержит и любую их суперпозицию.

Определение: Замыкание [M] множества функций M из PE есть множество всех суперпозиций над M.

Замечание:
1. M принадлежит [M].
2. [[M]]=[M](свойство идемпотентности).
3. M1 принадлежит M2 следует, что [M1] принадлежит [M2].

Обозначение: D(f) – область определения функции f.
R(f), Im(f) – область значений функции f.

Пусть A1,…,An – произвольные множества. Отношение ρ есть некоторое подмножество декартова произведения A1xA2x…xAnρ ⊆A1xA2x…xAn.

Значение отношения ρ может быть истинным или ложным:
— 1 означает принадлежность набора (a1,…, an) ∈ ρ декартову произведению.
— 0 – наоборот.

Пусть E- произвольное множество.
Определение: n-арное (n-местное) отношение определённое на множестве E есть подмножество ρ ⊆En=Ex…xE (n раз).

Замечание: Возможно предикатное от ρ(x1,…, xn) и множественная (x1,…, xn) принадлежит ρ записи для отношения ρ. (Предикат есть отношение). Пусть RE есть класс всех отношений определённых на множестве E.

Замечание: Предикат (отношение), определенный на множестве Е, есть функция, определенная на множестве Е принимающая только два значения [И,Л или T,F или 1,0].
Множество истинности предиката, есть множество всех тех наборов на котором предикат истинен.

Введем следующие операции (Мальцева):

1) ζρ(x1,x2,…,xn) = ρζ(x1,x2,…,xn) = ρ(x2,x3,…,xn,x1) – циклическая перестановка аргументов.

2) τρ(x1,x2,…,xn) = ρτ(x1,x2,…,xn) = ρ(x2,x1,x3,…,xn) – транспозиция (перестановка аргументов x1 и x2).

3) Δρ(x1,x2,…,xn) = ρΔ(x1,x2,…,xn) = ρ(x1,x1,x2,…,xn-1) – отождествление двух первых аргументов.

4) ∇ρ(x1,x2,…,xn) = ρ(x1,x2,…,xn) = ρ(x2,…,xn+1) – введение фиктивной переменной.

5) ρ(x1, x2,…,xn)*δ(x1, x2,…,xm) = ρ*(x1,…,xn+m-2) =
= {(a1,…,an+m-2) ∈ En+m-2: ∃ a ∈ E, (a1,…,an-1,a) ∈ ρ & (a,an,…,an+m-2) ∈ δ} – свертка отношений δ и ρ.

Замечание:

1) С помощью операций ζ, τ можно получить произвольную перестановку переменных.

2) С помощью операций ζ, τ, Δ отождествленных переменных может быть осуществлена на ∀ аргументах местах отношения.

3) С помощью операций ζ, τ, ∇ — фиктивные переменные могут быть введены на ∀ аргументых местах отношения.

4) С помощью ζ, τ, * свертка может быть осуществлена по ∀ переменным в обоих отношениях.

5) Кроме перечисленных в теории и практике программирования могут вводится и другие операции над отношениями.


Оставить комментарий

Реклама: Ремонт дверных замков автомобиля www.zamki-moskva.ru



Статистика

Рейтинг@Mail.ru