Характеристические векторы подмножеств конечного множества

Пусть U – конечное множество и n=|U| – число его элементов. Занумеруем элементы множества U числами от 1 до n и будем обозначать элементы их номерами, полагая, что U={1, 2, …, n}.

Всякое подмножество X⊂U может быть описано двоичным вектором ξ = (ξ₁,ξ₂,…,ξ_n)∈{0,1}ⁿ, в котором ξ_i=1, если i∈X, и ξ_i=0, если i∉X. По существу, это представление подмножества его характеристической функцией. Такой вектор будем называть характеристическим. Обратно, каждый двоичный вектор ξ=(ξ₁,ξ₂,…,ξ_n) может рассматриваться как характеристический вектор соответствующего подмножества X:

i∈X ⇔ ξ_i=1.

Пустому множеству соответствует нулевой вектор; характеристический вектор множества U состоит из одних единиц. Очевидно, число элементов множества X равно весу его характеристического вектора ξ, |X|=w(ξ).

Пример.Пусть U={1,2,3}. Тогда

∅↔(0,0,0); {1}↔(1,0,0); {2}↔(0,1,0); {3}↔(0,0,1);

{1,2}↔(1,1,0); {1,3}↔(1,0,1); {2,3}↔(0,1,1); {1,2,3}↔(1,1,1).

􀀀

Пусть α=(α₁,α₂,…,α_n) и β=(β₁,β₂,…,β_n) – двоичные векторы. Мы пишем α≤β (или β≥α), если α_i≤β_i для всех i=1,2,…, n.

Определим на множестве векторов операции конъюнкции и дизъюнкции, выполняя их покоординатно. Например, для дизъюнкции имеем:

α∨β = (α₁∨β₁, α₂∨β₂, …, α_n∨β_n).

Очевидно, α≤β тогда и только тогда, когда α∨β=β (равносильно, α∧β=α). Дизъюнкцию двух или большего числа векторов будем называть их верхней гранью. Так, α∨β – верхняя грань векторов α и β; α∨β∨γ – верхняя грань векторов α, β и γ и т.п. Каждый вектор является верхней гранью не превосходящих его векторов канонического базиса.

Пусть ξ и η – характеристические векторы подмножеств X, Y⊂U. Тогда условие X⊂Y равносильно условию ξ≤η. Характеристическим вектором множества X∪Y является вектор ξ∨η, а множества X∩Y – вектор ξ∧η.

Пусть V – конечное множество, содержащее m элементов, V={1,2,…,m}, и f:U→V – произвольное отображение. Для множества X⊂U обозначим через ξ его характеристический вектор, а через F(ξ) – характеристический вектор множества f(X)⊂V. Этим определяется отображение F:{0,1}ⁿ→{0,1}^m. Непосредственно из определений вытекает, что отображение F обладает следующими свойствами:

1) F(ξ)=0 тогда и только тогда, когда ξ=0;

2) w(F(ξ))≤w(ξ) для любого вектора ξ;

3) F(ξ∨η)=F(ξ)∨F(η) для любой пары векторов ξ и η.

Обратно, всякое отображение F:{0,1}ⁿ→{0,1}^m, обладающее перечисленными свойствами, порождается некоторым однозначно определенным отображением f:U→V. В самом деле, если ξ – вектор канонического базиса, то F(ξ)≠0 и w(F(ξ))≤w(ξ)=1. Следовательно, w(F(ξ))=1, то есть F(ξ) – вектор канонического базиса. Но векторы канонического базиса являются характеристическими векторами одноточечных множеств. Таким образом, сужение F на канонический базис дает отображение f:U→V.

Назовем матрицу двоичной, если все ее элементы нули или единицы. Определим булево умножение двоичных матриц подобно тому, как определяется произведение числовых матриц с заменой суммы дизъюнкцией. Пусть A=(a_ij) и B=(b_jk) – двоичные матрицы размера m×n и n×p. Их булевым произведением называется матрица C=(c_ik) размера m×p, элементы которой определяются формулами

c_ik=a_i1b_1k∨ a_i2b_2k∨… ∨a_inb_1n.

Пример.

Пусть R – некоторое соответствие из множества U={1,2,…,n} в множество V={1,2,…,m}. Положим a_ij=1, если (i,j)∈R и a_ij=0 в противном случае. Назовем двоичную матрицу A=(a_ij), i=1,2,…n, j=1,2,…m, характеристической матрицей соответствия R. Пусть ξ=(ξ₁,ξ₂,…,ξ_n) – характеристический вектор некоторого множества X⊂U (рассматриваемый как двоичная матрица размера 1×n). Тогда двоичный вектор η=ξA определяется уравнениями

η_k=ξ₁a_1k∨ξ₂a_2k∨… ∨ξ_na_nk, k=1,2,…,n,

и является характеристическим вектором множества R(X)⊂V.