Как найти классы поста – Сайт, где вы сможете решить свои вопросы

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

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.

Источник

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

В середине 60-х годов почти одновременно в СССР и во Франции появились работы, где с иных позиций и в более доступной форме излагались результаты Поста. В 80-е годы сразу целому ряду исследователей с использованием различных подходов и различной техники удалось получить достаточно компактные доказательства результатов Поста.
Алгебраический подход в изучении замкнутых классов булевых функций (подалгебр итеративной алгебры Поста над множеством ${mathsf {B}}={0,1}$ ) принадлежит А. И. Мальцеву.

Алгебра Поста и замкнутые классы[править | править код]

Булева функция — это функция типа ${mathsf {B}}^{n}to {mathsf {B}}$ , где ${mathsf {B}}={0,1}$ , а $n$ — арность. Количество различных функций арности $n$ равно $2^{{2^{n}}}$ , общее же количество различных булевых функций бесконечно. Вместе с тем, очевидно, что многие функции могут быть выражены через другие с использованием оператора суперпозиции. Например, давно известно, что из дизъюнкции и отрицания можно, используя законы де Моргана, получить конъюнкцию. Кроме того, любая булева функция может быть представлена в виде ДНФ, то есть, в терминах конъюнкции, дизъюнкции и отрицания. Возникает естественный вопрос: как определить, будет ли данный набор функций достаточным, чтобы представить любую булеву функцию? Такие наборы называются функционально полными. Теорема Поста даёт ответ на этот вопрос. Поскольку условие теоремы является необходимыми и достаточным, её называют также критерием.

Идея теоремы состоит в том, чтобы рассматривать множество всех булевых функций ${mathsf {PA}}$ как алгебру относительно операции суперпозиции. Сейчас она носит имя алгебра Поста. Эта алгебра содержит в качестве своих подалгебр множества функций, замкнутых относительно суперпозиции. Их называют ещё замкнутыми классами. Пусть $R$ — некоторое подмножество ${mathsf {PA}}$ . Замыканием $[R]$ множества $R$ называется минимальная подалгебра ${mathsf {PA}}$ , содержащая $R$ . Иными словами, замыкание состоит из всех функций, которые являются суперпозициями $R$ . Очевидно, что $R$ будет функционально полно тогда и только тогда, когда $[R]={mathsf {PA}}$ . Таким образом, вопрос, будет ли данный класс функционально полон, сводится к проверке того, совпадает ли его замыкание с ${mathsf {PA}}$ .

Оператор $[_]$ является оператором замыкания. Иными словами, он обладает (среди прочих) свойствами:

Говорят, что множество функций $Q$ порождает замкнутый класс $R$ (или класс $R$ порождается множеством функций $Q$ ), если ${displaystyle [Q]=R}$ . Множество функций $Q$ называется базисом замкнутого класса $R$ , если ${displaystyle [Q]=R}$ и ${displaystyle [Q_{1}]neq R}$ для любого подмножества $Q_1$ множества $Q$ , отличного от $Q$ .

Если к подалгебре ${mathsf {PA}}$ , не совпадающей с ${mathsf {PA}}$ прибавить один элемент, ей не принадлежащий, и образовать замыкание, результатом будет новая подалгебра, содержащая данную. При этом, она совпадёт с ${mathsf {PA}}$ , в том и только в том случае, если между исходной подалгеброй, и ${mathsf {PA}}$ нет никаких других подалгебр, то есть, если исходная подалгебра была максимальной. Таким образом, для того, чтобы проверить, что данное множество функций $R$ функционально полно, достаточно убедиться, что оно не входит целиком ни в одну из максимальных подалгебр ${mathsf {PA}}$ . Оказывается, что таких подалгебр всего пять, и вопрос принадлежности к ним может быть решён просто и эффективно.

Двойственность, монотонность, линейность. Критерий полноты[править | править код]

Ниже приведены некоторые следствия, вытекающие из теорем о двойственных функциях.

Перейдем теперь к выяснению полноты конкретных наборов функций.

Основные классы функций: ${displaystyle S,M,L,T_{0},T_{1}}$ [править | править код]

Теорема о замкнутости основных классов функций[править | править код]

Отметим, что ни один из замкнутых классов ${displaystyle S,M,L,T_{0},T_{1}}$ целиком не содержится в объединении остальных четырёх. Это вытекает из следующих соотношений:

${{bar {x}},xyoplus xzoplus yz}subset Ssetminus (Mcup Lcup T_{0}cup T_{1})$
${0,1,xlor y}subset Msetminus (Scup Lcup T_{0}cup T_{1})$
${1,xoplus y}subset Lsetminus (Scup Mcup T_{0}cup T_{1})$
${xoplus y,xy}subset T_{0}setminus (Scup Mcup Lcup T_{1})$
${xoplus yoplus 1,xlor y}subset T_{1}setminus (Scup Mcup Lcup T_{0})$

Всякий нетривиальный (отличный от $P_2$ ) замкнутый класс булевых функций целиком содержится хотя бы в одном из классов ${displaystyle S,M,L,T_{0},T_{1}}$ .

Формулировка критерия[править | править код]

Система булевых функций F является полной тогда и только тогда, когда она целиком не принадлежит ни одному из замкнутых классов^[⇦] ${displaystyle S,M,L,T_{0},T_{1}}$ .

То есть когда в ней можно реализовать пять функций: несамодвойственную, немонотонную, нелинейную, не сохраняющую 0 и не сохраняющую 1.

Доказательство[править | править код]

Порядок перебора вариантов при доказательстве критерия Поста

Доказательство критерия Поста основано на том, что система функций (И, ИЛИ и НЕ) является полной. Таким образом, любая система, в которой реализуемы эти три функции, также является полной. Докажем, что в системе, удовлетворяющей критерию Поста, всегда можно реализовать конъюнкцию, дизъюнкцию и отрицание.

Имея функцию, не сохраняющую 0, получим инвертор или константу 1[править | править код]

Рассмотрим функцию, не принадлежащую классу Т₀. Для неё

${displaystyle f(0,0,...,0)=1.}$

Эта функция может принадлежать, а может не принадлежать классу Т₁.

Имея функцию, не сохраняющую 1, получим инвертор или константу 0[править | править код]

Рассмотрим функцию, не принадлежащую классу Т₁. Для неё

${displaystyle f(1,1,...,1)=0.}$

Эта функция может принадлежать, а может не принадлежать классу Т₀.

Имея инвертор и несамодвойственную функцию, получим одну из констант[править | править код]

Рассмотрим функцию, не принадлежащую классу S самодвойственных функций. Для неё найдётся такой набор входных переменных X, что

${displaystyle f(x_{1},x_{2},...,x_{n})=f({overline {x}}_{1},{overline {x}}_{2},...,{overline {x}}_{n}).}$

Пусть, например, ${displaystyle f(0,1,0)=f(1,0,1)=1,}$ тогда ${displaystyle f(x,{overline {x}},x)=1}$ и мы имеем константу 1.

Аналогично, если, например, ${displaystyle f(0,0,0,1)=f(1,1,1,0)=0,}$ тогда ${displaystyle f(x,x,x,{overline {x}})=0}$ и мы имеем константу 0.

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

Имея инвертор и одну из констант, получим другую константу[править | править код]

Если в одном из вышеперечисленных случаев мы получили инвертор и одну из констант, вторую константу получим с помощью инвертора: ${displaystyle {overline {0}}=1}$ или ${displaystyle {overline {1}}=0.}$

Имея немонотонную функцию и обе константы, получим инвертор[править | править код]

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

${displaystyle f(x_{1},x_{2},...,0,...,x_{n})=1}$ и

${displaystyle f(x_{1},x_{2},...,1,...,x_{n})=0.}$

Пусть, например, ${displaystyle f(1,1,0)=0}$ и ${displaystyle f(1,0,0)=1}$ . Тогда ${displaystyle f(1,x,0)={overline {x}}}$ .

В любом случае, имея немонотонную функцию и обе константы, мы можем получить инвертор.

Имеем инвертор и обе константы[править | править код]

В предыдущих подразделах мы перебрали все возможные варианты (см. рисунок) и пришли к выводу, что имея функции, не принадлежащие классам Т₀, Т₁, S и M, мы всегда можем различными способами получить инвертор и обе константы.

Имея нелинейную функцию, инвертор и константу 1, получим конъюнкцию[править | править код]

Нелинейная функция по определению имеет в полиноме Жегалкина хотя бы один член, содержащий конъюнкцию нескольких переменных. Пусть, например, имеется некоторая нелинейная функция

${displaystyle f(x_{1},x_{2},x_{3},x_{4},x_{5})=1oplus x_{1}oplus x_{1}x_{2}x_{3}oplus x_{2}x_{3}x_{4}oplus x_{2}x_{3}x_{5}oplus x_{2}x_{3}x_{4}x_{5}.}$

Зададимся целью построить на её основе конъюнкцию ${displaystyle c(x_{1},x_{2})=x_{1}x_{2}.}$

Присвоим переменным $x_{3},x_{4},x_{5}$ значения 1, получим:

${displaystyle f(x_{1},x_{2},1,1,1)=1oplus x_{1}oplus x_{1}x_{2}oplus x_{2}oplus x_{2}oplus x_{2}=1oplus x_{1}oplus x_{1}x_{2}oplus x_{2}.}$

Очевидно, что в общем случае после такого преобразования получится функция вида

${displaystyle f(x_{1},x_{2},1,1,...,1)=x_{1}x_{2}[oplus x_{1}][oplus x_{2}][oplus 1],}$

где квадратные скобки означают, что выделенный ими член может присутствовать в окончательном выражении, а может и нет.

В простейшем случае при отсутствии других членов сразу получаем конъюнкцию: : ${displaystyle f(x_{1},x_{2},1,1,...,1)=x_{1}x_{2}.}$

Рассмотрим другие варианты.

${displaystyle x_{1}x_{2}oplus x_{1}=x_{1}{overline {x}}_{2};}$
${displaystyle x_{1}x_{2}oplus x_{2}={overline {x}}_{1}x_{2};}$
${displaystyle x_{1}x_{2}oplus x_{1}oplus x_{2}={overline {{overline {x}}_{1}{overline {x}}}}_{2}.}$
${displaystyle x_{1}x_{2}oplus 1={overline {x_{1}x}}_{2};}$ .
${displaystyle x_{1}x_{2}oplus x_{1}oplus 1={overline {x_{1}{overline {x}}}}_{2};}$
${displaystyle x_{1}x_{2}oplus x_{2}oplus 1={overline {{overline {x}}_{1}x}}_{2};}$
${displaystyle x_{1}x_{2}oplus x_{1}oplus x_{2}oplus 1={overline {x}}_{1}{overline {x}}_{2}.}$

Любое из этих выражений, используя инвертор, можно привести к конъюнкции.

Таким образом, имея нелинейную функцию, инвертор и константу 1 всегда можно получить конъюнкцию.

Имея конъюнкцию и инвертор, получим дизъюнкцию[править | править код]

Имея инвертор и конъюнкцию, всегда можно получить дизъюнкцию:

${displaystyle x_{1}+x_{2}={overline {{overline {x}}_{1}{overline {x}}}}_{2}.}$

Теорема доказана.

Следствие[править | править код]

Функция $f$ в одиночку является полной системой тогда и только тогда, когда:

$f(0,0,...,0)=1$
$f(1,1,...,1)=0$
$f$ не является самодвойственной

Примерами функций, в одиночку являющихся полной системой, будут штрих Шеффера ${displaystyle x|y={overline {xoperatorname {&} y}}}$ и стрелка Пирса ${displaystyle xdownarrow y={overline {xvee y}}}$ .

Теорема о максимальном числе функций в базисе[править | править код]

Максимальное число функций в базисе алгебры логики равно 4^[1].

Доказательство[править | править код]

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

Согласно критерию Поста, в полной системе должны присутствовать пять функций:

${displaystyle f_{0}not in T_{0};f_{1}not in T_{1};f_{S}not in S;f_{M}not in M;f_{L}not in L.}$

Рассмотрим функцию ${displaystyle f_{0}}$ . Возможны два случая:

2) Покажем, что существует базис из четырёх функций. Рассмотрим систему функций ${displaystyle {0,1,xcdot y,xoplus yoplus z}}$ . Эта система полна:

${displaystyle 0not in T_{1},S;1not in T_{0};xcdot ynot in L;xoplus yoplus znot in M.}$

Однако ни одна его подсистема не полна:

${displaystyle {0,1,xcdot y}subseteq M;}$
${displaystyle {0,1,xoplus yoplus z}subseteq L;}$
${displaystyle {0,xcdot y,xoplus yoplus z}subseteq T_{0};}$
${displaystyle {1,xcdot y,xoplus yoplus z}subseteq T_{1}.}$

Теорема доказана.

Примечания[править | править код]

↑ Алексеев В.Б. (2002), с. 12.

Литература[править | править код]

Марченков С. С. Замкнутые классы булевых функций. — М.: Физматлит, 2000.
Фудзисава Т., Касами Т. Математика для радиоинженеров: теория дискретных структур. — М.: Радио и связь, 1984. — 240 с.
Алексеев В. Б. Дискретная математика (II семестр). — М., МГУ, 2002. — 44 с.
Белоусов А. И., Ткачев С. Б. Дискретная математика. — М.: МГТУ, 2006. — 744 с. — ISBN 5-7038-2886-4.
Гиндикин С. Г. Алгебра логики в задачах. — М.: Наука, 1972. — 288 с.

Ссылки[править | править код]

Учебник по дискретной математике. Суперпозиция функций. Замыкание набора функции.Замкнутые классы функций. Полные наборы. Базисы, mini-soft.ru

См. также[править | править код]

Булева функция
Законы де Моргана
Алгебра логики
Стрелка Пирса
Дискретная математика

Источник

Классы Поста

Определим
5 классов булевых функций (классов
Поста).

1.
Классом

булевых функций
(,…,),
сохраняющих
константу 0,
называется множество:
:={(,…,)|(0,…,0)=0}.

2.
Классом

булевых функций
(,…,),
сохраняющих
константу 1,
называется множество:
:={(,…,)|(1,…,1)=1}.

3.
Классом L
линейных
булевых функций
(,…,)
называется множество:

L:={(,…,)|(,…,)=…}

где
,{0,1},
i=.

Коэффициенты
,,..,
линейной функции

определяются из следующих соотношений:

=(0,…,0)=0,
=(1,0,…,0),…,=
(0,…,0,1).

Пример
2. Определить, будет ли линейной функция:

f
(x,y,z)=.

Имеем
(x,y,z)=()==
==()=1=(x

1) z 
x (y 
1)(z 
1) = xz 
1z

xyz 
xz 
xy 
x = x 
z 
xy 
xyz.

Полученный
полином Жегалкина является нелинейным,
и, следовательно, функция f также
нелинейна.

4.
Классом S самодвойственных
булевых функций
(,…,)
называется множество:

S:={(,…,)|(,…,)=(,…,)}.

Пример.
В нижеследующей
таблице функции f₁,
f₂являются
самодвойственными функциями, а функции
f₃,
f₄
– нет.

x	y	f₁	f₂	f₃	f₄
0	0	0	0	0	1
0	1	1	0	1	0
1	0	0	1	1	0
1	1	1	1	0	1

5.
Классом M
монотонных
булевых функций
(,…,)
называется множество:

:={(,…,)|(,…,)(,…,)(,i=)
(,…,)(,…,)}.

Пример.
В нижеследующей
таблице функции f₁,
f₂являются
монотонными функциями, а функции f₃,
f₄
– нет.

x	y	f₁	f₂	f₃	f₄
0	0	0	0	0	1
0	1	1	0	1	0
1	0	0	1	1	0
1	1	1	1	0	1

Естественный
порядок переменных обеспечивает тот
факт, что если какой-то набор меньше
другого набора, то он обязательно
расположен в таблице истинности выше
“большего” набора.
Поэтому если в таблице
истинности (при
естественном порядке набора переменных)
вверху стоят нули,
а затем единицы,
то эта функция точно является монотонной.
Однако возможны инверсии, т. е. единица
стоит до каких-то нулей,
но функция является
все равно монотонной
(в этом случае наборы, соответствующие
“верхней” единице и “нижнему” нулю
должны быть несравнимы;
можно проверить, что
функция, задаваемая таблицей истинности
при естественном
порядке набора переменных (00010101),
является монотонной);

Пример
3. Определим, к каким классам Поста
относится булева функция
(x,y)=x|y.

f
(0,0)=1, т.е.
f (x,y).

f
(1,1)=0, т.е.
f (x,y).

f
(1,0)f
(0,1), т.е.
f (x,y)S.

f
(0,0)>f (1,1), т.е.
f (x,y)M.

f
(x,y)=1
xy, т.е.
f (x,y)L.

Отметим,
что каждый класс Поста замкнут относительно
операций замены переменных и суперпозиций,
т.е. с помощью этих операций из функций,
принадлежащих данному классу, можно
получить только функции из этого же
класса.

Для
установления полноты системы S:={,…,}
булевых функций используют критерий
полноты Поста–Яблонского:

Система
F:={,…,}
булевых функций тогда и только тогда
является полной, когда для каждого из
пяти классов
,,S,
M, L в системе F найдется функция
,
не принадлежащая этому классу.

В
силу критерия полноты функция f (x,y)x|y
образует полную систему, т.е. с помощью
функции Шеффера (x|y) можно получить любую
функцию. В частности,

x|x,
x&y(x|y)|
(x|y).

Система
булевых функций F:={,…,}
называется базисом, если она полна, а
для любой функций
S
система F{}
– неполна.

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

{○},{|},{,},{,○},{,},{,},{,},{,},{&,},{,},
{,1},{,&,0},{,,0},{,&,},{,,},{,&,1},{,,1}.

Наиболее
хорошо изученным является базис {&,,}.

Из
критерия полноты
следует довольно
простой способ выяснения полноты
некоторого набора функций. Для каждой
из этих функций выясняется принадлежность
к перечисленным выше классам. Результаты
заносятся в так называемую
таблицу Поста (в нашем
примере эта таблица составлена для 4-х
функций, причем знаком “+” отмечается
принадлежность функции соответствующему
классу, знак “–” означает, что функция
в него не входит).

f	T₀	T₁	L	M	S
f₁	+	–	+	–	–
f₂	+	–	–	–	+
f₃	–	+	–	–	–
f₄	+	+	–	+	–

В
соответствии с теоремой Поста набор
функций будет полным тогда и только
тогда, когда в каждом столбце таблицы
Поста имеется хотя бы один минус. Таким
образом, из приведенной таблицы следует,
что данные 4 функции образуют полный
набор, но эти функции не являются базисом.
Из этих функций можно образовать 2
базиса: f₃,
f₁и f₃,
f₂.
Полными наборами будут любые наборы
содержащие, какой-либо базис.

Теорема.
Каждый базис содержит не более четырех
булевых функций.

Для
доказательства функциональной полноты
предъявленной системы F:={,…,}
достаточно показать, что через функции
F
можно выразить все функции из базиса
{&,,}.
Справедливо и более общее утверждение.

Теорема.
Если все функции функционально полной
системы *
представимы формулами над ,
то 
также функционально полна.

Пример.
В алгебре Жегалкина (;={&,,1})
определить, является ли сигнатура 
функционально полной системой.

Чтобы
выяснить функциональную полноту системы
={&,,1},
достаточно показать, что через операции

можно выразить операции булевого базиса
*={&,,}:

1)
=,

2)
=

Построенные
таблицы истинности подтверждают
справедливость формул 1) и 2).


	x	x	1	x1
	0	1	1	1
	1	0	1	0

x1	x2	x₁x₂	x₁x₂	x₁x₂x₁	x₁x₂x₁x₂
0	0	0	0	0	0
0	1	1	0	0	1
1	0	1	0	1	1
1	1	1	1	0	1

Двойственность.
Функция f*(,…,)
называется двойственной к функции f
(,…,),
если f*(,…,)=(,…,).

Отношение
двойственности между функциями
симметрично, т.е. если f* двойственна к
f, то f двойственна к f*:

(,…,)=(,…,)=f*(,…,).

Функция,
двойственная к самой себе, называется
самодвойственной.

Принцип
двойственности:
если в формуле F, представляющей функцию
f, все знаки функций заменить соответственно
на знаки двойственных функций, то
полученная формула F* будет представлять
функцию f*, двойственную f.

Принцип
двойственности в булевой алгебре: если
в формуле F, представляющей функцию f,
все конъюнкции заменить на дизъюнкции,
дизъюнкции на конъюнкции, 1 на 0, 0 на 1,
то получим формулу F*,
представляющую функцию f*,
двойственную f.

Пример.
Доказать справедливость принципа
двойственности в булевой алгебре, исходя
из общего принципа двойственности.

Найдем
для каждой операции булевой алгебры
(;
&, ,
)
двойственные им операции.

а)
Пусть f (x,y)=xy.
Тогда f*(x,y)xy.

б)
Пусть f (x,y)=xy.
Тогда f*(x,y)xy.

в)
Пусть f (x).
Тогда f*(x).

Таким
образом, конъюнкция двойственна
дизъюнкции, дизъюнкция – конъюнкции,
а отрицание самодвойственно.

Наконец,
константы 0 и 1 принадлежат множеству
логических функций
,
поэтому 0 и 1 могут содержаться в булевой
формуле и являются двойственными друг
к другу: если
(,…,)=0,
то f*(,…,)(,…,)1.
Аналогично, если f =1, то f*=0.

Отсюда
следует справедливость принципа
двойственности в булевой алгебре.

Пример.
Пусть f (x,y,z)
.
Найти ДНФ двойственной функции f*(x,y,z),
исходя из:

а)
определения двойственности функции;

б)
принципа двойственности в булевой
алгебре.

а)
f*(x,y,z)

xz;

б)
f*(x,y,z)
xz.

Источник

Необходимость.

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

Достаточность.

Докажем, что если набор не содержится полностью ни в одном из данных классов, то он является полным.

Рассмотрим функцию, не сохраняющую ноль — (то есть функцию, для которой ). Тогда может принимать два значения:
1. , тогда .
2. , тогда .
Рассмотрим функцию, не сохраняющую один — (то есть функцию, для которой ). Тогда может принимать два значения:
1. , тогда .
2. , тогда .

Таким образом, возможны четыре варианта:

Мы получили функцию .

Используем несамодвойственную функцию . По определению, найдется такой вектор , что . Где .

Рассмотрим , где либо , при . Либо , при .
Нетрудно заметить, что .
Таким образом мы получили одну из констант.

Мы получили и имеем константу, равную , поскольку .
Мы получили и имеем константу, равную , поскольку .
Мы получили и .

Рассмотрим немонотонную функцию . Существуют такие , что , , зафиксируем все , тогда .

В итоге имеем три функции: , , .

Используем нелинейную функцию . Среди нелинейных членов (ее представления в виде полинома Жегалкина), выберем тот, в котором минимальное количество элементов. Все аргументы кроме двух в этом члене приравняем единице, оставшиеся два назовем и . Все элементы, не входящие в данный член, примем равными нулю.
Тогда эта функция будет представима в виде , где в квадратных скобках указаны члены, которые могут и не присутствовать (остальные слагаемые будут равны нулю, поскольку в них есть как минимум один аргумент, не входящий в выбранный член, так как в выбранном члене минимальное число элементов).

Рассмотрим несколько вариантов:

Присутствует член . Возьмем отрицание от и член исчезнет.
Присутствуют три члена, без : . Составив таблицу истинности для этой функции нетрудно заметить, что она эквивалентна функции .
Присутствуют два члена, без . Построив две таблицы истинности для двух различных вариантов, заметим, что в обоих случаях функция истинна только в одной точке, следовательно, СДНФ функции будет состоять только из одного члена. Если это так, то не составляет труда выразить через и . Например, если функция принимает истинное значение, когда аргументы c номерами ложны, а все остальные истины, то функцию можно выразить как , где ставится перед аргументами с номерами .
Присутствует один член. Выразим через и аналогично пункту 3.

В итоге получим функцию, а также либо функцию , либо функцию . Поскольку функцию можно выразить через и , а функцию через и , то мы получили базис , , . Любую булеву функцию, не равную тождественному нулю, можно представить в форме СДНФ, то есть выразить в данном базисе. Если же функция равна тождественному нулю, то ее можно представить в виде .

Значит, полученные функции образуют полную систему, поскольку с их помощью можно выразить любую булеву функцию. Из этого следует, что K — полная система функций, что и требовалось доказать.

Источник

Теорема Поста и классы

В силу теоремы о представлении любой булевой функции дизъюнктивной или конъюнктивной нормальной формой стандартный базис {lor,cdot,overline{phantom{A}}} является полным множеством. Поскольку, согласно законам де Моргана, можно выразить конъюнкцию через дизъюнкцию и отрицание, равно как и дизъюнкцию можно выразить через конъюнкцию и отрицание, то при удалении из стандартного базиса одной функции, дизъюнкции или конъюнкции, при сохранении отрицания, получим снова полное множество.

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

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

Из условия теоремы следует, что каждая функция fin F может быть представлена некоторой формулой Psi над , т.е.

f(x_1,ldots,x_n)=Psi(x_1,ldots,x_n).

(6.17)

Докажем, что всякая формула над эквивалентна некоторой формуле над , т.е. всякая функция varphi , представляемая формулой над , может быть представлена также и некоторой формулой над . Доказательство проведем по такой схеме: сначала убедимся в справедливости утверждения для “базисных” формул, т.е. для переменных и констант из , а затем в предположении, что оно уже доказано для формул Phi_1,ldots,Phi_n , где ngeqslant1 , докажем его для любой формулы вида f(Phi_1,ldots,Phi_n) , где fin F . Такой метод доказательства называют доказательством индукцией по построению формулы.

Пусть varphi — какая-то формула над . Если varphi=x , где — булево переменное из множества , то, поскольку каждое переменное есть, по определению, и формула над , функция varphi представляется формулой над .

Если varphi есть константа из , то представляющая varphi формула над существует ввиду (6.17).

Рассмотрим формулу над вида f(Phi_1,ldots,Phi_n) , где n>0,~fin F , а — формулы над . Согласно предположению индукции, каждая формула $Phi_1,~i=overline{1,n}$ , может быть заменена эквивалентной ей формулой Theta_i над (т.е. имеет место тождество Phi_1=Theta_i над Fcup G ). Тогда, используя правила эквивалентных преобразований формул (см. теорему 6.1), получим тождество

f(Phi_1,ldots,Phi_n)= f(Theta_1,ldots,Theta_n),

а в соответствии с (6.17) будем иметь

f(Theta_1,ldots,Theta_n)= Psi(Theta_1,ldots,Theta_n).

(6.18)

Правая часть тождества (6.18) и есть формула над , эквивалентная исходной формуле над .

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

Пример 6.17. Рассмотрим базис Жегалкина {oplus,cdot,1} . Чтобы доказать полноту этого множества, заметим, что

xlor y=xcdot yoplus xoplus y,qquad overline{x}=xoplus1,

т.е. каждый элемент стандартного базиса может быть представлен формулой над базисом Жегалкина. Отсюда и следует (ввиду полноты стандартного базиса и теоремы 6.3) полнота базиса Жегалкина.

Любую формулу над базисом Жегалкина называют полиномом Жегалкина. Полином Жегалкина от переменных может быть записан в виде

$P(x_1,ldots,x_n)= bigopluslimits_{{i_1,i_2,ldots,i_m }subseteq{1,2,ldots,n}} (operatorname{mod}2)a_{i_1i_2ldots i_m} x_{i_1}x_{i_2}ldots x_{i_m},$

где коэффициенты полинома $a_{i_1i_2ldots i_m}in{0;1}$ индексированы всеми возможными подмножествами множества {1,2,ldots,n} (коэффициент a_0 соответствует пустому множеству). В частности, при n=3 будем иметь:

$a_{123}x_1x_2x_3oplus a_{12}x_1x_2oplus a_{13}x_1x_3oplus a_{23}x_2x_3oplus a_1x_1oplus a_2x_2oplus a_3x_3oplus a_0$

(6.19)

(общий вид полинома Жегалкина от трех переменных). Формула вида

$bigopluslimits_{i=1}^{n}(operatorname{mod}2)a_ix_ioplus a_0$

(6.20)

называется полиномом Жегалкина первой степени от переменных. В таком полиноме отсутствуют “нелинейные” слагаемые, т.е. все коэффициенты, индексированные более чем одноэлементными подмножествами, равны 0 (и вместе с ними равны 0 все слагаемые, содержащие конъюнкции переменных).

Можно доказать следующее достаточно простое, но важное утверждение.

Теорема 6.4. Полином Жегалкина для любой булевой функции определен однозначно.

Для функций от небольшого числа переменных (не превышающего 4) можно использовать метод неопределенных коэффициентов, позволяющий получить полином Жегалкина данной функции. Проиллюстрируем этот метод на примере.

Пример 6.18. Пусть вектор значений булевой функции равен 11001011 . Найдем полином Жегалкина, представляющий . Поскольку размерность вектора значений равна 2^3=8 , то задана как функция от трех переменных. Тогда она представляется некоторым полиномом Жегалкина третьей степени, общий вид которого дает формула (6.19). Наша задача — найти такие значения коэффициентов этого полинома, при которых он представляет функцию . Ясно, что значение функции на наборе 000 равно коэффициенту a_0 в формуле (6.19). Но, согласно заданному вектору значений, оно равно 1. Следовательно, a_0=1 . Далее,

f(0,0,1)=a_3oplus a_0=a_3oplus 1=1,

откуда, решая уравнение относительно a_3 в поле $mathbb{Z}_2$ , получим a_3=0 ;

f(0,1,0)=a_2oplus1=0 , то есть a_2=1 и f(1,0,0)= a_1oplus 1=1 и a_1=0 .

Чтобы найти коэффициенты $a_{12},,a_{13}$ и $a_{23}$ , нужно рассмотреть значения функции на наборах 110,,101 и 011 соответственно. Так, для первого набора получим

$f(1,1,0)=a_{12}x_1x_2oplus a_1x_1oplus a_2x_2oplus a_0= a_{12}oplus a_{2}oplus a_0=a_{12}oplus1oplus1=a_{12}$

(сумма по модулю 2 любого четного числа равных слагаемых равна 0). Поскольку в то же время f(1,1,0)=1 , то a_0=1 . Аналогично $f(1,0,1)=a_{13}oplus a_0=0$ , откуда $a_{13}=1$ ; $f(0,1,1)=a_{23}oplus a_2oplus a_0=0$ , и, так как $a_2=a_0=1,~a_{23}=0$ . Наконец,

$f(1,1,1)=a_{123}oplus a_{12}oplus a_{13}oplus a_2oplus a_0=a_{123}=1.$

Итак, окончательно имеем f=x_1x_2x_3oplus x_1x_2oplus x_1x_3oplus x_2oplus 1 .

Как видно из примера 6.18, суть метода неопределенных коэффициентов состоит в следующем. Записывая полином Жегалкина сначала в общем виде, с неопределенными коэффициентами, мы выражаем значение полинома на фиксированных наборах через коэффициенты и приравниваем его заданному значению функции. Начинаем с нулевого набора и находим коэффициент a_0 , равный значению заданной функции на нулевом наборе. Зная его, из рассмотрения значений функции на наборах, содержащих в точности одну единицу, находим коэффициенты а,- при “одиночных” переменных (коэффициенты “линейной части” полинома). Зная их, из рассмотрения значений функции на наборах, содержащих в точности две единицы, находим коэффициенты при конъюнкциях двух переменных и т.д. При этом выполняются вычисления и решаются простейшие линейные уравнения в поле вычетов по модулю 2.

Пример 6.19. а. Рассмотрим множество {mid} , состоящее из единственной функции (штриха Шеффера). Полнота этого множества следует из легко проверяемых тождеств

xcdot y=(x|y)|(x|y),qquad overline{x}=(x|x).

б. Полнота множества {downarrow} , единственным элементом которого является стрелка Пирса, проверяется аналогично.

Теперь мы сформулируем и докажем критерий (необходимое и достаточное условие) полноты для произвольного множества булевых функций. Для этого нам потребуется сначала рассмотреть некоторые специальные множества функций.

Определение 6.8. Функцию называют функцией, сохраняющей константу 0 (соответственно константу 1), если f(widetilde{0})=0 (соответственно: f(widetilde{1})=1 , где — нулевой, а — единичный наборы значений переменных функции .

Например, мажоритарная функция является функцией, сохраняющей и константу 0, и константу 1. Отрицание не сохраняет ни 0, ни 1, а эквивалентность сохраняет 1, но не сохраняет 0. Множество всех функций, сохраняющих константу 0 (константу 1), обозначается T_0 (соответственно T_1 ).

Наборы widetilde{alpha} и overline{widetilde{alpha}} из булева куба $mathbb{B}^n={0;1}^n$ (для произвольного фиксированного ) будем называть взаимно противоположными, говоря при этом также, что набор есть инверсия (или отрицание) набора widetilde{alpha} (в силу единственности дополнения любого элемента булевой алгебры набор будет, очевидно, инверсией набора overline{widetilde{alpha}} ).

Определение 6.9. Функцию $ginmathcal{P}_{2,n}$ называют двойственной к функции $finmathcal{P}_{2,n}$ , если для всякого $widetilde{alpha}in {0;1}^n$ имеет место g(widetilde{alpha})= overline{f} (overline{widetilde{alpha}}) .

Полагаем также, что константа 0 является двойственной к константе 1 и наоборот.

Пример 6.20. а. Стрелка Пирса есть функция, двойственная к штриху Шеффера, так как

xdownarrow y=overline{xlor y}= overline{overline{overline{x}cdot overline{y}}}= overline{overline{x}|overline{y}}.

б. Сумма по модулю 2 двойственна к эквивалентности, так как xsim y=overline{xoplus y}=overline{overline{x}oplus overline{y}} .

Эти две функции являются и отрицанием друг друга, но неверно в общем случае, что функция д, будучи отрицанием функции , двойственна к штрих Шеффера не есть функция, двойственная к конъюнкции, а стрелка Пирса не есть функция, двойственная к дизъюнкции, но конъюнкция двойственна к дизъюнкции и наоборот, а стрелка Пирса двойственна к штриху Шеффера и наоборот.

В общем случае в силу уже упомянутого свойства единственности дополнения в булевой алгебре функция , двойственная к функции , которая двойственна к , равна .

Определение 6.10. Функцию $finmathcal{P}_{2,n}$ называют самодвойственной, если она двойственна к себе самой, т.е.

$bigl(forallwidetilde{alpha}in{0;1}^nbigr)bigl(f(widetilde{alpha})= overline{f}(overline{widetilde{alpha}})bigr)$ , или $bigl(forall widetilde{alpha}in{0;1}^nbigr)bigl(f(overline{widetilde{alpha}})= overline{f}(widetilde{alpha})bigr).$

Таким образом, функция самодвойственна тогда и только тогда, когда на взаимно противоположных наборах она принимает взаимно противоположные значения. Следовательно, для того чтобы убедиться в несамодвойственности заданной функции , достаточно найти хотя бы одну пару взаимно противоположных наборов widetilde{alpha} и overline{widetilde{alpha}} , таких, что значения функции на них совпадают, т.е. f(widetilde{alpha})=f(overline{widetilde{alpha}}) . Так, мажоритарная функция является самодвойственной, а эквивалентность — нет, поскольку при widetilde{alpha}=(0;0) имеем 0sim0=1 и 1sim1=1 .

Множество всех самодвойственных функций (при всех ngeqslant1 ) обозначим .

Определение 6.11. Функцию $finmathcal{P}_{2,n}$ называют монотонной, если для любых наборов $widetilde{alpha},widetilde{beta}inmathcal{B}^n$ , таких, что widetilde{alpha}leqslant widetilde{beta} , имеет место f(widetilde{alpha})leqslant f(widetilde{beta}) .

Другими словами, функция монотонна тогда и только тогда, когда для любого набора widetilde{alpha} имеет место следующее свойство: если значение функции на наборе равно 1, то оно равно 1 и на всех наборах, строго больших (по отношению булева порядка на $mathbb{B}^n$ ) набора widetilde{alpha} . Любой минимальный (относительно того же порядка) набор , для которого значение f(widetilde{alpha}) монотонной функции равно 1, называют нижней единицей функции . Очевидно, что вектор значений монотонной булевой функции полностью определяется множеством ее нижних единиц*. Мажоритарная функция монотонна, и множество ее нижних единиц есть {011,101,110} . Штрих Шеффера — немонотонная функция, так как 00<11 , но 0|0=1 , а 1|1=0 . Множество всех монотонных функций принято обозначать через .

*Нетрудно понять, что множество нижних единиц монотонной функции есть множество всех минимальных элементов множества C_f^1 — конституент единицы функции .

Определение 6.12. Функцию $finmathcal{P}_{2,n}$ называют линейной, если она может быть представлена полиномом Жегалкина первой степени от п переменных, т.е. формулой вида (6.20).

Множество всех линейных функций принято обозначать через .

Любая булева константа и любая проектирующая функция х являются линейными функциями. Такова, разумеется, сумма по модулю 2. Отрицание также линейно, ибо overline{x}= xoplus1 . Конъюнкция и дизъюнкция не являются линейными функциями, так как не могут быть представлены полиномом Жегалкина первой степени (см. теорему 6.4).

Определение 6.13. Множества функций T_0,,T_1,,S,,M,,L называются классами Поста.

Замечание 6.9. Каждый класс Поста состоит из функций с соответствующим свойством для любого числа переменных. Можно доказать также, что если функция принадлежит какому-то классу Поста , то и любая функция, равная функции , принадлежит этому же классу. Другими словами, добавление или удаление фиктивных переменных не выводит за пределы любого из классов Поста.

Полезно еще заметить, что любая проектирующая функция х принадлежит одновременно всем пяти классам Поста. Действительно, если f(x)=x , то f(0)=0 и f(1)=1 , то есть fin T_0cap T_1 . Отсюда же вытекает и самодвойственность функции . Монотонность следует из того, что 0<1 и f(0)=0<f(1)=1 . Линейность очевидна.

В то же время существуют функции, не принадлежащие ни одному из классов Поста. Таков, например, штрих Шеффера. Все свойства, кроме нелинейности, следуют прямо из таблицы этой функции. Нелинейность же доказывается выводом полинома Жегалкина для штриха Шеффера: x|y=overline{xcdot y}=xcdot yoplus1 , что не есть полином Жегалкина первой степени.

Фундаментальным свойством каждого класса Поста является его замкнутость (в смысле определения 6.3). Это означает для любого из классов Поста , что всякая суперпозиция над снова есть элемент .

Теорема о замкнутости классов Поста

Теорема 6.5. Каждый класс Поста замкнут.

Нужно для каждого класса Поста $Cin{T_0,T_1,S,M,L}$ доказать, что замыкание [ C] множества булевых функций совпадает с . Пусть f(g_1,ldots,g_n) — какая-то суперпозиция над . Обозначим ее через varphi . Без ограничения общности можно считать, что все функции $f,g_1,ldots, g_nin mathcal{P}_{2,n}$ (для некоторого ).

Рассуждаем, используя индукцию по определению суперпозиции. Если для каждого i=overline{1,n} функция g_i=x_i , где x_i — переменное, то varphi=f(x_1,ldots,x_n)in C . Предположим, что в суперпозиции varphi все функции g_i есть элементы класса Поста (в частности, это может быть и соответствующая проектирующая функция, которая ввиду замечания 6.9 принадлежит всем классам Поста). Докажем, что и varphi=f(g_1,ldots,g_n)in C .

1. Если C=T_0 , то $varphi(widetilde{0})= f(g_1(widetilde{0}),ldots, g_2(widetilde{0}))= f(0,ldots,0)=0$ , так как f,g_1,ldots,g_nin T_0 . Следовательно, varphiin T_0 .

2. При C=T_1 рассуждаем точно так же.

3. Пусть C=S . Фиксируем произвольно набор $widetilde{alpha}in {0;1}^n$ . Вычислим (используя само двойственность всех функций):

$varphibigl(overline{widetilde{alpha}}bigr)= fbigl(g_1(overline{widetilde{alpha}}), ldots, g_2(overline{widetilde{alpha}})bigr)= fbigl(overline{g_1}(widetilde{alpha}),ldots, overline{g_n}(widetilde{alpha})bigr)= overline{f}bigl(g_1(widetilde{alpha}), ldots g_n(widetilde{alpha})bigr)= overline{varphi}(widetilde{alpha}).$

Следовательно, varphiin S .

4. C=M . Берем произвольно наборы widetilde{alpha} и widetilde{beta} так, что widetilde{alpha}leqslant widetilde{beta} . Докажем, что varphiin M . Имеем

$varphi(widetilde{alpha})= fbigl(g_1(widetilde{alpha}), ldots g_n(widetilde{alpha}) bigr)leqslant fbigl(g_1(widetilde{beta}), ldots g_n(widetilde{beta})bigr)= varphi(widetilde{beta}).$

так как все функции $g_i,~i=overline{1,n}$ , монотонны и тем самым вектор $(g_1(widetilde{alpha}), ldots g_n(widetilde{alpha}))$ не больше вектора $(g_1(widetilde{beta}), ldots g_n(widetilde{beta}))$ , а функция также монотонна. Тогда ясно, что varphiin M .

5. Если же C=L , то очевидно, что при подстановке в линейную функцию (полином Жегалкина первой степени) вместо ее переменных произвольных линейных функций получится снова линейная функция. Итак, мы доказали замкнутость каждого класса Поста.

Докажем теперь теорему, характеризующую одно важное свойство немонотонных функций.

Теорема 6.6. Если функция не является монотонной, т.е. fin M , то найдутся два таких набора widetilde{alpha},widetilde{beta} , что

$begin{aligned}widetilde{alpha}&= (alpha_1,ldots, alpha_{i-1},0, alpha_{i+1},ldots, alpha_n),\ widetilde{beta}&= (alpha_1,ldots, alpha_{i-1},1, alpha_{i+1},ldots, alpha_n), end{aligned}$

и f(widetilde{alpha})=1,~f(widetilde{beta})=0 , т.е. эти два набора различаются значениями в точности одной компоненты, а значение функции равно О на большем наборе и равно 1 на меньшем.

Так как функция не является монотонной, то найдутся такие два набора widetilde{gamma} и widetilde{delta} , что widetilde{gamma}<widetilde{delta} , но f(widetilde{gamma})=1,~ f(widetilde{delta})=0 . Строгое неравенство widetilde{gamma}< widetilde{delta} означает, что найдутся такие номера (не меньше одного) 1leqslant i_1<i_2<ldots< i_kleqslant n , что

$begin{aligned}widetilde{gamma}&=bigl(gamma_1,ldots, gamma_{i_1-1}, 0, gamma_{i_1+1},ldots, gamma_{i_2-1},0,ldots, gamma_{i_2+1},ldots, gamma_{i_k-1},0, gamma_{i_k+1},ldots, gamma_n bigr),\[2pt] widetilde{delta}&=bigl(gamma_1,ldots, gamma_{i_1-1}, 1, gamma_{i_1+1},ldots, gamma_{i_2-1},1,ldots, gamma_{i_2+1},ldots, gamma_{i_k-1},1, gamma_{i_k+1},ldots, gamma_n bigr).end{aligned}$

т.е. все компоненты наборов, кроме выделенных, с номерами i_1,i_2,ldots,i_k соответственно совпадают, а все компоненты с выделенными номерами у меньшего набора равны 0, а у большего равны 1. Построим монотонно возрастающую последовательность наборов

$widetilde{gamma}=widetilde{gamma}_0<widetilde{gamma}_1<widetilde{gamma}_2<ldots <widetilde{gamma}_k=widetilde{delta}.$

так что для каждого sin{1,2,ldots,k} набор $widetilde{gamma}_s$ получается из набора $widetilde{gamma}_{s-1}$ заменой нулевого значения компоненты с номером i_s единичным. Поскольку f(widetilde{gamma})=1 , а f(widetilde{delta})=0 , то обязательно найдется такое sin{1,2,ldots,k} , что $f(widetilde{gamma}_{s-1})=1$ , а $f(widetilde{gamma}_s)=0$ (на наборе $widetilde{gamma}_{s-1}$ значение функции еще равно 1, а на наборе $widetilde{gamma}_{s}$ оно уже равно 0). Полагая $widetilde{alpha}= widetilde{gamma}_{s-1}$ и $widetilde{beta}= widetilde{gamma}_{s}$ получим доказываемое.

Математический форум (помощь с решением задач, обсуждение вопросов по математике).

Кнопка "Поделиться"

Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.

Источник

Алгебра Поста и замкнутые классы[править | править код]

Двойственность, монотонность, линейность. Критерий полноты[править | править код]

Основные классы функций: [править | править код]

Теорема о замкнутости основных классов функций[править | править код]

Формулировка критерия[править | править код]

Доказательство[править | править код]

Имея функцию, не сохраняющую 0, получим инвертор или константу 1[править | править код]

Имея функцию, не сохраняющую 1, получим инвертор или константу 0[править | править код]

Имея инвертор и несамодвойственную функцию, получим одну из констант[править | править код]

Имея инвертор и одну из констант, получим другую константу[править | править код]

Имея немонотонную функцию и обе константы, получим инвертор[править | править код]

Имеем инвертор и обе константы[править | править код]

Имея нелинейную функцию, инвертор и константу 1, получим конъюнкцию[править | править код]

Имея конъюнкцию и инвертор, получим дизъюнкцию[править | править код]

Следствие[править | править код]

Теорема о максимальном числе функций в базисе[править | править код]

Доказательство[править | править код]

Примечания[править | править код]

Литература[править | править код]

Ссылки[править | править код]

См. также[править | править код]

Необходимость.

Достаточность.

Теорема Поста и классы

Теорема о замкнутости классов Поста

Вам также может понравиться

Как составить формулу периметра треугольника учи ру

Как найти работу без навыков

Как составить существительные от глаголов в английском языке

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

Основные классы функций: ${displaystyle S,M,L,T_{0},T_{1}}$ [править | править код]