Функции и отношения, их свойства
Пусть 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) Кроме перечисленных в теории и практике программирования могут вводится и другие операции над отношениями.