Как составить таблицу поста

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

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, …, xn}) = a₀ + a₁x₁ + … +a_nx_n}.

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

S = {f ∈ P₂ | ∀_(a1,…,an) 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∪T0)T1		11	SΔL		21	(S∩T1)∪L
2	(S∪T0)T1		12	(S∩L)∪T0		22	(T1∪T0)∩L
3	S∪T0∪T1		13	(S∩L)∪T1		23	(T1∩T0)∪L
4	(S∪T0)∩T1		14	(S∪L)∩T1		24	(L∩T0)∪(S∩T1)
5	SΔT1		15	(S∪L)∩T0		25	(S∩T1)(L∩T0)
6	(L∪T1)T0		16	(L∪T0)∩S		26	(T1∪T0)S
7	LΔT1		17	(L∩T0)∪S		27	(T1∪T0)L
8	(ST0)∪T1		18	(L∪T1)∩S		28	(L∪T0)S
9	(S∩T1)∪T0		19	(L∩T1)∪S		29	T0(S∪L)
10	(S∪L)T0		20	(S∪T0)∩L		30	(T0S)T1

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

Пример 1. Подсчитать число различ ных булевых функций от n переменных, принадлежащих множеству L(T0∩S). Обозначим через L(n) , T(n)0 , S(n) соответственно множества линейных, сохраняющих ноль и самодвойственных функций от 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(n) и T(n)1 (рис. 2.4.4, б). Очевидно, | S(n) ∪ T(n)1 | = | S(n) | + | T(n)1 | – | S(n) ∩ T(n)1 |. Пусть f ∈ S(n), g ∈ T(n)1, h ∈ S(n)∩T(n)1, изобразим таблицы этих функций.

Таблица 2.4.4а

x1	x2	…	xn-1	xn	f	g	h
0	0	…	0	0	a1	b1	0
0	0	…	0	1	a2	b2	c1
…	…	…	…	…	…	…	…
0	1	…	1	1	a2n-1	…	c2n-1-1
1	0	…	0	0	¬a2n-1	…	¬c2n-1-1
…	…	…	…	…	…	…	…
1	1	…	1	0	¬a2	b2n-1	¬c1
1	1	…	1	1	¬a1	1	1

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

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

Классы Поста

Определим
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	f1	f2	f3	f4
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	f1	f2	f3	f4
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	T0	T1	L	M	S
f1	+	–	+	–	–
f2	+	–	–	–	+
f3	–	+	–	–	–
f4	+	+	–	+	–

В
соответствии с теоремой Поста набор
функций будет полным тогда и только
тогда, когда в каждом столбце таблицы
Поста имеется хотя бы один минус. Таким
образом, из приведенной таблицы следует,
что данные 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	x1x2	x1x2	x1x2x1	x1x2x1x2
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.

Чтобы составить таблицу Поста, нужно решить вопрос о принадлежности каждой из четырёх рассматриваемых функций к классам (  large P_0, P_1, S, L, M ). Если некоторая функция принадлежит тому или иному классу, то на пересечении соответствующей строки и соответствующего столбца ставится знак “плюс”, если не принадлежит, то ставится знак “минус”

1) Представим все функции в полиномиальной форме и решим вопрос об их линейности. Используя основные тождества теории булевых функций, получим:

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

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

2) Решим вопрос о принадлежности функций к классу (  large P_0 ). Имеем:

Итак, функции (  large f_2 ) и (  large f_3 ) сохраняют нуль, а функции (  large f_1 ) и (  large f_4 ) — не сохраняют.

3) Проверим, какие из функций принадлежат к классу (  large P_1 ). Имеем:

Вывод: все рассматриваемые функции, кроме (  large f_2 ), сохраняют единицу.

4) Выясним, какие функции принадлежат к классу (  large S ). Используя определение самодвойственной функции, получим:

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

5) Используя определения элементарных булевых функций, составим таблицы значений для функций (  large f_1, f_2, f_3, f_4 ) и выясним, являются ли они монотонными.

Рассмотрим первую и вторую строки таблицы. Функция (  large f_1 ) не является монотонной, так как

но

Рассмотрев третью и четвертую строки таблицы, делаем вывод, что функция (  large f_2 ) также не является монотонной, поскольку

но

Рассмотрим третью и седьмую строки таблицы. Функция (  large f_3 ) не является монотонной, так как

но

Рассмотрев первую и вторую строки таблицы, замечаем, что 

но

Значит, функция (  large f_4 ) также не является монотонной.

Используя полученные выше данные, составим таблицу Поста:

Согласно теореме Поста, системы (  large { f_1,f_2,f_3,f_4 } ), (  large { f_1,f_2,f_3 } ), (  large { f_1,f_2,f_4 } ), (  large { f_2,f_3,f_4 } ), (  large { f_1,f_2 } ), (  large {f_2 ,f_4 } ) полны, поскольку в каждой из них есть функция, не сохраняющая нуль, есть функция, не сохраняющая единицу, есть функция, не являющаяся самодвойственной, есть нелинейная функция, есть немонотонная функция.

стемы (  large {f_1 ,f_3,f_4 } ), (  large { f_1,f_3 } ), (  large { f_1,f_4 } ), (  large { f_2,f_3 } ), (  large { f_3,f_4 } ), (  large { f_1 } ), (  large { f_2 } ), (  large { f_3 } ), (  large {f_4 } ), в силу той же теоремы, не являются полными. Но являются ли перечисленные выше полные системы базисами? Будем рассуждать, используя определение базиса булевых функций. Системы (  large { f_1,f_2 } ), (  large {f_2 ,f_4 } ) есть базисы, поскольку после удаления из них любой функции они превращаются в систему из одной функции, а все такие системы, как сказано выше, не полны. Удаляя из системы (  large { f_1,f_2,f_3 } ) функцию (  large f_3 ) получаем полную систему, удаляя из системы (  large { f_1,f_2,f_4 } ) функцию (  large f_1 ) получаем полную систему, удаляя из системы (  large { f_2,f_3,f_4 } ) функцию (  large f_3 ) получаем полную систему. Следовательно, системы (  large { f_1,f_2,f_3 } ), (  large { f_1,f_2,f_4 } ), (  large { f_2,f_3,f_4 } ) не являются базисами. Система (  large {f_1, f_2,f_3,f_4 } ) не базис, так как, например, удаление из неё функции (  large f_4 ) приводит к полной системе.

Итак, базисами являются только две системы: (  large { f_1,f_2 } ) и (  large {f_2 ,f_4 } ).

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

maths24.net

Система булевых функций F={f₁,…,f_n} называется полной, если любая булева функция представима в виде терма сигнатуры (f₁,…,f_n}, т.е в виде суперпозиции функций из F.

Классы Поста:

1) P₀={f|f(0,…,0)=0} — класс булевых функций, сохраняющих ноль

2) P₁={f|f(1,…,1)=1} – класс булевых функций, сохраняющих 1

3) S={f|f⁺=f} – класс самодвойственных функций

4) M – класс монотонных функций. Булева функция f(x₁,…,x_n) называется монотонной, если для любых наборов нулей и единиц (α₁,…,α_n) и (β₁,…,β_n) из условий α_i≤β_i следует f(α₁,…,α_n)≤f(β₁,…,β_n)

5) Класс I – это класс линейных функций. Булева функций f(x₁,…,x_n) называется линейной, если в булевом кольце функция f представима в виде .

Каждый класс Поста замкнут относительно операций замены переменных и суперпозиции.

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

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

Доказательство: Предположим, что существует базис F, состоящий более чем из четырех функций. По теореме Поста тогда получаем, что F состоит ровно из пяти функций, каждая из которых не принадлежит ровно одному классу Поста. Пусть f – функция из F, не принадлежащая классу P₀. Тогда f(0,…,0)=1 и f(1,…,1)=1, но тогда f не принадлежит классу самодвойственных функций, а это противоречит предположения.

studopedia.ru

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача 2. Привести данные выражения к ДНФ, пользуясь правилами де Моргана. Если возможно, сократить ДНФ, используя свойство поглощения и правило Блейка:

Задача 12.а) Написать по данной ДНФ полином Жегалкина, от ДНФ перейти к КНФ, а затем перейти к СКНФ; б) перейти от данной КНФ к ДНФ, а затем перейти к СДНФ.

Задача 22.Составить таблицу истинности данной функции, написать для нее СДНФ и СКНФ (если возможно); найти по таблице истинности полином Жегалкина для данной функции; составить карту Карно для данной функции и найти сокращенную ДНФ.

Задача 32. С помощью карт Карно по данной таблице истинности для функции 4-х переменных найти ее сокращенную ДНФ.
а)

б)

Задача 42. Составить таблицу Поста и найти базисы из следующих функций:

Задача 52. Составить структурную матрицу для данного орграфа (или графа) и, методами булевой алгебры, найти все пути P_ij из вершины i в вершину j, затем найти все сечения S_ij между этими вершинами.

Дан орграф. Имеется 2 ориентированных ребра: (2-3) и (2-4); i=4, j=6.

Задача 62. Найти в данной сети максимальный поток из вершины с номером 1 в вершину с наибольшим номером.

Download (PDF, 369KB)

21 февраля, 2014

Posted In: Дискретная математика, Контрольная работа, Математика, СПб ГУТ

Метки: Вариант 2