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

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

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

2. Если функция f(x₁,…,x_n) принадлежит F и каждая из A₁,…,A_n есть либо суперпозиция над F либо переменная, то f(A₁,…,A_n) есть суперпозиция над F.

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

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

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

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

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

Пусть A₁,…,A_n – произвольные множества. Отношение ρ есть некоторое подмножество декартова произведения A₁xA₂x…xA_nρ ⊆A₁xA₂x…xA_n.

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

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

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

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

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

1) ζρ(x₁,x₂,…,x_n) = ρ_ζ(x₁,x₂,…,x_n) = ρ(x₂,x₃,…,x_n,x₁) – циклическая перестановка аргументов.

2) τρ(x₁,x₂,…,x_n) = ρ_τ(x₁,x₂,…,x_n) = ρ(x₂,x₁,x₃,…,x_n) – транспозиция (перестановка аргументов x₁ и x₂).

3) Δρ(x₁,x₂,…,x_n) = ρ_Δ(x₁,x₂,…,x_n) = ρ(x₁,x₁,x₂,…,x_n-1) – отождествление двух первых аргументов.

4) ∇ρ(x₁,x₂,…,x_n) = ρ_∇(x₁,x₂,…,x_n) = ρ(x₂,…,x_n+1) – введение фиктивной переменной.

5) ρ(x₁, x₂,…,x_n)*δ(x₁, x₂,…,x_m) = ρ_*(x₁,…,x_n+m-2) =
= {(a₁,…,a_n+m-2) ∈ E^n+m-2: ∃ a ∈ E, (a₁,…,a_n-1,a) ∈ ρ & (a,a_n,…,a_n+m-2) ∈ δ} – свертка отношений δ и ρ.

Замечание:

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

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

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

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

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

Комментарии запрещены.