Классы Поста

^{Решение задач}

Классами Поста называются следующие классы:

T₀, T₁, L, S, М.

Класс функций, сохраняющих константу 0:

T₀ = {f ∈ P₂ | f(0,0,...,0) =0}.

Класс функций, сохраняющих константу 1:

T₁ = {f ∈ P₂ | f(1,1,...,1) =1}.

Класс линейных функций:

L = {f ∈ P₂ | f(x₁, x_{2, ..., x_n}) = a₀ + a₁x₁ + ... +a_nx_n}.

Класс самодвойственных функций:

S = {f ∈ P₂ | ∀_{(a₁,...,a_n}) f(a₁,...,a_n) = f(a₁,...,a_n)}.

Говорят, что набор α предшествует набору β, и пишут α ⪯ β, если a _iα b_i для i=1,2,...,n.

Класс монотонных функций:

M={f ∈ P₂|∀_α∀_β α ⪯ β → f(α) ≤ f(β)

Замыканием множества булевых функций и называется множество всех суперпозиций функций класса и, которое обознача ется [и].

Класс и называется функционально замкнутым, если [и] = и.

Теорема. Классы Поста функционально замкнуты.

Класс функций и называется функционально полным, если [и] = P₂.

Класс функций и называется функционально полным в слабом смысле, если добавление в и констант 0 и 1 превращает его в функционально полный класс.

Теорема Поста. Множество булевых функций и является функционально полным тогда и только тогда, когда для каждого из классов Поста найдётся во множестве и функция, не принадлежащая этому классу.

Задание 2.4.1

Доопределить функции f(x,y,z), g(x,y,z), h(x,y,z) так, чтобы f ∈ М, g ∈ L, h ∈ S.

Если построение какой-либо функции невозможно, докажите это.

Выясните вопрос о принадлежности построенных функций к классам Т₂ и T₂.

Таблица 2.4.1

№	f	g	h
1	(-10- 1---)	(-10- -0-0)	(-0-- 11-1)
2	(---0 1---)	(0--- 110-)	(11-- 10--)
3	(---0 -10-)	(---0 0-10)	(-1-- 01-0)
4	(-1-- --0-)	(01-0 -1--)	(101- 1---)
5	(---0 -01-)	(0-10 ---1)	(--10 --01)
6	(--1- -0--)	(-01- -1-1)	(-1-0 -1-0)
7	(-0-0 1---)	(1--- 011-)	(-00- 1--1)
8	(-1-1 --0-)	(---1 1-01)	(-1-- 10-0)
9	(-01- -0--)	(10-1 -0--)	(0--- 101-)
10	(---0 1-1-)	(1-01 ---0)	(1--1 -00-)
11	(-1-- --01)	(1-1- --00)	1-10 --1-)
12	(0--0 1---)	(--00 1-0-)	(--10 --00)
13	(0-1- -0--)	(--10 1-1-)	(-10- 0--1)
14	(01-- --0-)	(-00- 1-1-)	(11-1 -0--)
15	(---0 1--1)	(0--- 001-)	(-010 ---1)
16	(--1- -0-1)	(-10- 0--1)	(-1-- 10-0)
17	(-1-- -10-)	(0--1 -0-0)	(00-1 -1--)
18	(--00 1---)	(--1- 11-0)	(00-0 -0--)
19	(-01- -0--)	(---0 01-0)	(01-- 01--)
20	(-1-- 0-0-)	(1--0 -1-1)	(0-10 --0-)
21	(---0 1-1-)	(--0- 00-1)	(---1 -010)
22	(--11 -0--)	(---1 10-1)	(-1-- 10-0)
23	(-10- --0-)	(1--- 110-)	(0--1 -10-)
24	(-01- -0--)	(-01- 1--0)	(-1-0 -0-1)
25	(-0-0 1---)	(-1-0 1-01)	(1--0 -10-)
26	(-1-1 --0-)	(1--0 -01-)	(--01 --11)
27	(-0-0 1---)	(01-1 -0--)	(0-00 --0-)
28	(--11 -0--)	(-1-- 1-0-)	(0--1 -01-)
29	(-1-- 011-)	(01-- 1-0-)	(-101 ---0)
30	(---0 11--)	(-0-- 101-)	(00-0 -0--)

Пример решения задания 2.4.1

Решим задание 2.4.1 для f = (-101 - -0-), g = (---1-010), h = (1-10--1-).

Изобразим развёрнутую таблицу данных функций.

Доопределим функцию f, используя определение монотонной функции.

Так как f(1,1,0) = 0, то на всех на- борах, предшествующих набору (1,1,0), функция f тоже должна равняться 0, т.е. f(0,0,0) = f(1,0,0) = 0.

Так как f(0,0,1) = 1, то на всех наборах, которым предшествует набор (0,0,1), функция f должна принять значение 1, т. е. f(1,0,1) = f(1,1,1) = 1.

Получаем: f(x,у,z) = (01010101).

Таблица 2.4.1a

xyz	f	g	h
000	-	-	1
001	1	-	-
010	0	-	1
011	1	1	0
100	-	-	-
101	-	0	-
110	0	1	1
111	-	0	-

Доопределим функцию g, учитывая, что она — линейная. Общий вид линейной функции от переменных х, у, z имеет вид: g(x,y,z) = a₀ + a₁x + a₂y + a₃z.

Будем подставлять наборы значений аргументов, на которых функция определена.

Получим систему соотношений:
или

Заменяя a₀ + a₁x + a₂ на 1 в 4 уравнении системы, имеем:

1 + a₃ = 0 ⇒ a₃ = 1.

Сложив первые три уравнения и учитывая, что х + х = 0, получим: а₀ + 0 = 0 ⇒ а₀ = 1.

Подставляя в 1 уравнение найденные значения а₀ и а₃, получим: 0 + а₂ + 1 = 1 или а₂ +1 = 1, откуда а₂ = 0.

Подставив значения а₀ и а₃ во 2 уравнение, получим:

0 + а₁+1 = 0 или а₁ +1 = 0, откуда а₁ =1.

Итак, g(x,y,z) = 0 + 1⋅х + 0⋅у + 1⋅z = x + z.

Исходя из этой формулы, найдём значения функции g на тех наборах, на которых она была не определена: g(0,0,0) = 0 + 0 = 0; g(0,0,1) = 0 + 1 = 1; g(0,1,0) = 0 + 0 = 0; g(1,0,0) = 1 + 0 = 1.

В итоге имеем: g(x,y,z) = (01011010).

Доопределим функцию h, используя определение самодвойственной функции. Так как наборы (0,0,0) и (1,1,1) противоположны и h(0,0,0) = 1 ⇒ h(1,1,1) = 0.

Противоположными парами наборов значений переменных являются также (0,0,1) и (1,1,0), (0,1,0) и (1,0,1), (0,1,1) и (1,0,0).

Используя известные значения функции h, получим:

h(0,0,1) = h(1,1,0) = 1 = 0, h(1,0,1) = h(0,1,0) = 1 = 0.

Итак, h(x,y,z) = (10101010).

Так как f(0,0,0) = g(0,0,0) = 0 ≠ h(0,0,0), то f ∈ T₀, g ∈ T₀, h ∉ T₀.

Так как g(1,1,1) = h(1,1,1) = 0, f(1,1,1) = 1, то f ∈ T₁, g ∉ T₁, h ∉ T₁.

Задание 2.4.2

1. Можно ли из функции f(x,y,z) с помощью суперпозиций получить g(x,y,z) ?

2. Верно ли, что f(x,y,z) ∈ [g] ? ([g] — замыкание класса {g}).

Таблица 2.4.2

№	f	g
1	1001 0110	1110 0110
2	1001 0100	1101 0100
3	0111 1010	1000 0110
4	1101 1010	1010 1010
5	0110 1111	1010 0110
6	1000 0110	1001 1000
7	0110 1110	1001 0010
8	1000 0110	1101 1001
9	1100 0111	1001 1001
10	1010 0110	1001 0110
11	1110 1000	1100 1000
12	1000 0000	1100 0011
13	0111 1110	1101 0000
14	1110 0000	1011 0010
15	1110 1111	1100 0010
16	1010 0100	1000 1110
17	0101 1110	1011 0000
18	1101 0000	1101 0100
19	1100 0001	1101 1000
20	1001 1000	1110 1000
21	1011 0010	1100 0110
22	1000 1100	0011 1010
23	100 0110	1111 0010
24	1100 1110	1000 0001
25	1100 0011	1001 1000
26	1001 0110	1101 1100
27	0111 1010	1001 1010
28	1101 0000	1110 1000
29	1111 0111	1010 1000
30	1000 1000	1001 0110

Пример решения задания 2.4.2

Решим задание 2.4.2 для функций f = (10010100), g=(1001 0110).

Проверим f(x,y,z) на принадлежность к классам Поста.

f(0,0,0) = 1 ⇒ f ∉ T₀; f(1,1,1) =1 ⇒ f ∉ T₁;

(0,0,0) ⪯ (0,0,1) и f(0,0,0) > f(0,0,1) ⇒ f ∉ M;

(0,0,1) и (1,1,0) — противоположные наборы,

f(0,0,1) = f(1,1,0) ⇒ f ∉ S;

f(x,y,z) = (x + 1)(y + 1)(z +1) + (x + 1)yz + x(y + 1)z =

= 1 + x+y + z + xy + xz + yz + xyz + xyz + yz + xyz + xz =

= 1 + x+y + z + xy + xyz.

Так как в полиноме функции f присутствуют конъюнкции, то f ∉ L.

Итак, мы видим, что функция f(x,y,z) не принадлежит ни одному из классов Поста, значит, система {f} функционально полна, и с помощью суперпозиций из f можно получить любую булеву функцию, в частности, g(x,y,z).

Проверяя значения функции g(x,y,z) на всех парах противоположных наборов, видим:

g(0,0,0) = 1 = g(1,1,1), g(0,0,1) = 0 = g(1,1,0),

g(0,1,0) = 1 = g(1,0,1), g(0,1,1) = 1 = g(1,0,0).

Значит, g ∈ S.

Так как S — функционально замкнутый класс, то [g] ⊆ S, но f ∉ S, значит, f ∉ [g].

Задание 2.4.3

Для функций f(x,y,z) и g(x,y,z) выяснить вопрос об их принадлежности к классам Т₀, T₁, L, S, М.

В случае, если некоторая функция представляет из себя функционально полный класс, выразить из неё с помощью суперпозиций константы 0,1, отрицание и конъюнкцию ху.

В случае, если некоторая функция представляет из себя функционально полный в слабом смысле класс, выразить из неё с помощью суперпозиций и фиксирования переменных отрицание и конъюнкцию ху.

Полученные результаты проверить с помощью построения таблиц.

Таблица 2.4.3

№	f	g
1	1100 0111	1101 1000
2	1110 1010	00110101
3	0100 1101	1100 1110
4	1111 0100	1001 0110
5	0110 1001	1101 0100
6	1000 0010	0000 1101
7	1011 1101	1100 0100
8	1111 1010	0101 1111
9	1000 0001	1110 1010
10	1101 1100	0001 1010
11	0010 0000	1100 1000
12	1001 0000	1000 0011
13	0111 1110	1101 0000
14	1110 0000	1011 0011
15	1110 1111	1100 0010
16	0010 0100	1000 1110
17	1101 1110	1011 0011
18	1101 0000	1101 0100
19	1100 0001	1101 1110
20	1001 1000	1110 1000
21	1011 0011	1100 0110
22	1000 1100	0011 1010
23	0001 0110	1111 0010
24	1100 1110	1000 0001
25	1100 0011	1101 1100
26	1001 1110	0101 0100
27	0111 1010	1011 1010
28	1101 0000	1110 1001
29	1111 0111	1011 1100
30	1000 1100	1001 0111

Пример решения задания 2.4.3

Решим задание 2.4.3 для функций f = (0010 1000), g = (1001 0010).

Выпишем развёрнутую таблицу функций f и g (табл. 2.4.3а).

Таблица 2.4.3a

xyz	f	g
000	0	1
001	0	0
010	1	0
011	0	1
100	1	0
101	0	0
110	0	1
111	0	0

1. Исследуем функцию f(x,y,z). Проверим f(x,y,z) на принадлежность к классам Поста.

f(0,0,0) = 0 ⇒ f ∈ T₀.

Заметим, что отсюда следует, что {f} не является функционально полным классом.

f(1,1,1) = 0 ⇒ f ∉ T₁.

Так как наборы (0,0,0) и (1,1,1) противоположны и f(0,0,0) = f(1,1,1), то f ∉ S.

Имеем, что (0,1,0) ⪯ (0,1,1), но f(0,1,0) > f(0,1,1), значит, f ∉ M.

Найдём полином для f(x,y,z):

= xyz + xy + yz + y + xyz + xy + xz + x = xz + yz + x+ y.

Так как полином функции f содержит конъюнкцию, то f ∉ L.

Как было отмечено ранее, {f} не является функционально полным классом, но, так как функция f нелинейна и немонотонна, {f} — функционально полный в слабом смысле класс.

Выразим из f отрицание с помощью фиксирования переменных. На соседних наборах (0,1,0) и (0,1,1) нарушается монотонность, рассмотрим функцию р(х) = f(0,1,х).

Найдём все значения функции р(х):

р(0) = f(0,1,0) = 1, p(1) = f(0,1,1) = 0 ⇒ р(х) = x.

Отрицание построено, x = f(0,1, х).

Для построения конъюнкции зафиксируем одну переменную и переобозначим оставшиеся переменные так, чтобы полином принял вид

xy + αx + βy +γ, где α,β,γ ∈ {0,1}.

Например, можно сделать так: f(1,y,x) = 1⋅х + ху + 1 + у = = ху + х+у + 1. В этом случае α = β = γ =1.

Введём функцию h(x, у) = f(1, у + α,х + β) + αβ + γ = f(1, y, x) = = f(1,f(0,1,у), f(0,1,x)).

Найдём значения функции h на всех её наборах.

h(0,0) = f(1,f(0,1,0), f(0,1,0)) = f(1,1,1) = 0;

h(0,1) = f(1 f(0,1,1), f(0,1,0)) = f(1,0,1) = 0;

h(1,0) = f(1, f(0,1,0), f(0,1,1)) = f(1,1,0) = 0;

h(1,1) = f(1, f(0,1,1),f(0,1,1)) = f(1,0,0) = 1.

Как видим, таблица функции h(x,y) совпадает с таблицей конъюнкции, следовательно, х⋅у = f(1, f(0,1,у), f(0,1,х)).

2. Исследуем g(x,y,z) на принадлежность к классам Поста.

g(0,0,0) = 1 ⇒ g ∉ T₀.

g(1,1,1) = 0 ⇒ g ∉ T₁.

Наборы (1,0,1) и (0,1,0) противоположны и g(1,0,1) = g(0,1,0) ⇒ g ∉ S.

Так как (0,0,0) ⪯ (0,0,1), но g(0,0,0) > g(0,0,1) ⇒ g ∉ M.

Найдём полином для g(x,y,z):

g(x,y,z) = (x + 1)(y + 1)(x + 1) + (x + 1)yz + xy(z + 1) =

= xyz + xy + xz + yz + x+y + z + 1 + xyz + yz + xyz + xy =

= 1 + x + у + z + xz + xyz.

Так как в полиноме функции g содержится конъюнкция, то g ∉ L.

Итак, функция g не принадлежит ни одному из пяти классов поста, значит, {g} —функционально полный класс.

Выразим из g отрицание с помощью одних лишь суперпозиций. Рассмотрим функцию s(x) = g(x,x,x).

Найдём все значения функции s(x):

s(0) = g(0,0,0) = 1, s(1) = g(1,1,1) = 0 ⇒ s(x) = x

Отрицание построено, x = g(x,x,x).

Строим константу 0. Для этого возьмём набор из пары проти- воположных наборов, на которых функция g равна 0, например, (1,0,1), и рассмотрим функцию о(х): о(х) = g(x¹, x⁰, x¹) = g(x, x, x) = g(x, g(x, x, x) x).

Найдём значения функции о(х) на её наборах.

о(0) = g(0, g(0,0,0),0) = g (0,1,0) = 0;

o(1) = g(1, g(1, g(1,1,1)1) = g(1,0,1) = 0.

Константа 0 построена, g(x, g(x,x,x),x) = 0.

Для построения константы 1 возьмём отрицание от функции о(х) и обозначим полученную функцию через е(х).

е(х) = g(o(x),o(x),o(x)) =

= g(g(x,g(x,x,x,),x),g(x,g(x,x,x,))x),g(x,g(x,x,x),x)).

Итак, койстанта 1 получена,

g(g(x,g(x,x,x,),x),g(x,g(x,x,x,),x),g(x,g(x,x,x,),x)) ≡ 1.

Для построения конъюнкции зафиксируем переменную z, придав ей значение 1.

Получим: g(x,у,1) = 1 + x+y + 1 + x⋅1 + xy⋅1 = xy + y + 1, т. е. мы получили выражение вида ху + αх + βу + γ, где α = γ = 0, β = 1.

Рассмотрим функцию k(х,у) = g(x + β, y + α,1) + αβ + γ =

= g(x + 1,y,1) + 0⋅l + 0= g(g(x,x,x),y,1) =

= g(g(x,x,x),y,g(g(x,g(x,x,x),x),g(x,g(x,x,x),x),g(x,g(x,x,x),x))).

Найдём значения функции к на всех её наборах.

k(0,0)=g(g(0,0,0),0, g(g0, g(0,0,0),0x g(0, g(0,0,0),0), g(0, g(0,0,0),0)))=

=g(1,0,g(g(0,1,0), g(0,1,0), g(0,1,0)) = g(1,0,0) = 0;

k(0,1) = g(g(0,0,0), 1, g(g(0, g(0,0,0),0), g(0, g(0,0,0),0), g(0, g(0,0,0),0)))=

= g(1,1, g(g(0,1,0), g(0,1,0), g(0,1,0))) = g(1,1,g(0,0,0)) = g(1,1,1) = 0;

k(1,0) = g(g(1,1,1),0,g(g(1, g(g(1,1,1),1),g(1,g(1,1,1),1,g(1,g(1,1,1),1))) =

= g(0,0,g(g(1,0,1), g(1,0,1), g(1,0,1))) = g(0,0, g(0,0,0)) = g(0,0,1) = 0;

k(1,1)=g(g(1,1,1),1, g(g(1, g(1,1,1),1),g(1,g(1,1,1),1),g(1,g(1,1,1),1))) =

=g(0,1, g(g(1,0,1), g(1,0,1),g(1,0,1))) = g(0,1,g(0,0,0)) = g(0,1,1) = 1.

Как видим, таблица функции к(х,у) совпадает с таблицей конъюнкции, следовательно,

х⋅y = g(g(x,x,x),y,g(g(x,g(x,x,x)x),g(x,g(x,х,х)х), g(x,g(x,х,х),х))).

Задание 2.4.4

Подсчитать число различных булевых функций от п переменных, принадлежащих данному множеству A.

Таблица 2.4.4

№	A	№	A	№	A
1	(L∪T₀)\T₁	11	SΔL	21	(S∩T₁)∪L
2	(S∪T₀)\T₁	12	(S∩L)∪T₀	22	(T₁∪T₀)∩L
3	S∪T₀∪T₁	13	(S∩L)∪T₁	23	(T₁∩T₀)∪L
4	(S∪T₀)∩T₁	14	(S∪L)∩T₁	24	(L∩T₀)∪(S∩T₁)
5	SΔT₁	15	(S∪L)∩T₀	25	(S∩T₁)(L∩T₀)
6	(L∪T₁)\T₀	16	(L∪T₀)∩S	26	(T₁∪T₀)\S
7	LΔT₁	17	(L∩T₀)∪S	27	(T₁∪T₀)\L
8	(ST₀)∪T₁	18	(L∪T₁)∩S	28	(L∪T₀)\S
9	(S∩T₁)∪T₀	19	(L∩T₁)∪S	29	T\₀(S∪L)
10	(S∪L)\T₀	20	(S∪T₀)∩L	30	(T₀\S)\T₁

Примеры решения задания 2.4.4

Пример 1. Подсчитать число различ ных булевых функций от n переменных, принадлежащих множеству L\(T₀∩S).

Обозначим через L⁽ⁿ⁾ , T⁽ⁿ⁾⁰ , S⁽ⁿ⁾ соответственно множества линейных, сохраняющих ноль и самодвойственных функций от n переменных.

Заштрихованная область соответствует функциям искомого класса. Очевидно, выполнено равенство:

|L⁽ⁿ⁾\(T⁽ⁿ⁾⁰∩S⁽ⁿ⁾)|=|L⁽ⁿ⁾|-|L⁽ⁿ⁾∩T⁽ⁿ⁾⁰∩S⁽ⁿ⁾|

Каждая функция из L⁽ⁿ⁾ имеет вид: а₀ + а₁х₁ + а₂х₂ +... + а_nх_n.

Поставим в соответствие каждой такой функции вектор её двоичных коэффициентов (а₀, а₁, а₀, ..., а₀). Очевидно, что это соответствие — биекция, значит, количество различных линейных функций от п переменных равно количеству различных двоичных наборов размерности n + 1, т.е. 2ⁿ⁺¹ итак, |L(n) |=2ⁿ⁺¹.

Если линейная функция сохраняет константу 0, то а₀ + а₁ ⋅ 0 + а₀ ⋅ 0 + ... + а_n ⋅ 0 = 0 ⇒ а₀=0, и она имеет вид а₁х₁+а₂х₂+... + а_nх_n. Для самодвойственной функции выполняется свойство f(х₁,..., х_n) = f(х₁,...,х_n). Учитывая, что х = х + 1, посмотрим, как будет выглядеть это равенство в случае линейной, сохраняющей ноль функции:

а₁(х₁ +1) + а₂(х₂ + 1) + ... + а_n(х_n +1) = 1 + a₁x₁ + а₂х₂ +... + а_nх_n.

Раскроем скобки:

а₁х₁ +а₁+ а₂х₁ + а₂ +... + а_nх_n + а_n = 1 + а₁х₁ + а₂х₂ +... + а_nх_n.

Прибавим по модулю 2 к обеим частям полученного равенства выражение а₁х₁ + а₂х₂ +... + а_nх_n, учтём, что х + х = 0. Тогда после упрощений будем иметь: а₁ + а₁ + ... + а₁ =1. (*)

Из коэффициентов а₁, а₁, ..., а_n произвольным образом можно назначать n-1 коэффициент, а значение n-го коэффициента однозначно определяется из равенства (*). Итак, между множеством булевых функций класса L⁽ⁿ⁾∩T⁽ⁿ⁾⁰∩S⁽ⁿ⁾ и множеством двоичных векторов размерности n-1 существует биекция, значит, верно равенство | L⁽ⁿ⁾∩T⁽ⁿ⁾⁰∩S⁽ⁿ⁾ |= 2^n-1.

В итоге получаем:

| L⁽ⁿ⁾\T⁽ⁿ⁾⁰ ∩ S⁽ⁿ⁾) |=|L⁽ⁿ⁾| - | L⁽ⁿ⁾ ∩ T⁽ⁿ⁾⁰ ∩ S⁽ⁿ⁾| = 2ⁿ⁺¹ - 2^n-1 = 2^n-1(4-1) = 3⋅2^n-1.

Пример 2. Подсчитать число различных булевых функций от n переменных, принадлежащих множеству S ∪ T¹.

Обозначим через S⁽ⁿ⁾ и T⁽ⁿ⁾¹ соответственно множества самодвойственных и сохраняющих единицу функций от n переменных.

Изобразим множества S⁽ⁿ⁾ и T⁽ⁿ⁾¹ (рис. 2.4.4, б).

Очевидно,

| S⁽ⁿ⁾ ∪ T⁽ⁿ⁾¹ | = | S⁽ⁿ⁾ | + | T⁽ⁿ⁾¹ | - | S⁽ⁿ⁾ ∩ T⁽ⁿ⁾¹ |.

Пусть f ∈ S⁽ⁿ⁾, g ∈ T⁽ⁿ⁾¹, h ∈ S⁽ⁿ⁾∩T⁽ⁿ⁾¹, изобразим таблицы этих функций.

Таблица 2.4.4а

x¹	x²	...	x^n-1	xⁿ	f	g	h
0	0	...	0	0	a¹	b¹	0
0	0	...	0	1	a²	b²	c¹
...	...	...	...	...	...	...	...
0	1	...	1	1	a^{2^n-1}	...	c^{2^n-1-1}
1	0	...	0	0	¬a^{2^n-1}	...	¬c^{2^n-1-1}
...	...	...	...	...	...	...	...
1	1	...	1	0	¬a²	b^2ⁿ-1	¬c¹
1	1	...	1	1	¬a¹	1	1

Значит, мощности множеств S⁽ⁿ⁾, T⁽ⁿ⁾¹, S⁽ⁿ⁾ ∩ T⁽ⁿ⁾¹ равны соответственно 2^{2ⁿ-1^{, 2^2ⁿ-1 и 2^{2^n-1-1}.}}

В итоге: | S⁽ⁿ⁾ ∪ T⁽ⁿ⁾¹ | = 2^{2^n-1} + 2^2ⁿ-1 - 2^{2^n-1-1} = 2^{2^n-1-1} + 2^2ⁿ-1.