Замкнутые классы. Свойства замыкания.

Определение:

Множество М логических функций называется замкнутым классом, если:

1) для любой ф-ции fÎM любая замена переменных не выводит функцию из множества М.

2) любая суперпозиция ф-ций f1, f2 … fn Î М снова принадлежит М

Всякая система F логических ф-ций пораждает некоторый замкнутый класс, а именно класс, состоящий из вех ф-ций, которые можно получить при помощи суперпозиций из F.

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

1. FÌ[F]

2. [[F]]=[F]

3. F1ÌF2=[F1]Ì[F2]

4. [F1] È [F2]=[F1ÈF2]

Класс ф-ций F называется замкнутым если его замыкание равно ему самому [F]=F.

Существует 5 наиболее важных замкнутых классов:

1. Класс ф-ций, сохраняющих значение 0;

2. Класс ф-ций, сохраняющих значение 1;

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

4. Класс монотонных ф-ций;

5. Класс линейных ф-ций.

 

Класс функций, сохраняющих значение 0.

Т₀ – класс бул. ф-ций сохраняющих 0:

fÎT₀ <=> f(0,…,0)=0.

входят: 0, x, x&y, xÚy.

невходят: 1, Øx, xºy, ®, ­, ¯.

Число ф-ций входящих в класс Т₀ равно 2^{(2^n)-1}

Класс Т₀ – замкнут: [T₀]=T₀.

Для док-ва класса Т₀ достаточно показать, что элементарная суперпозиция ф-ций из класса Т₀ также принадлежат Т₀:

Ф(x₁,x₂,…x_n)=f₀(f₁(…),…f_k(…))ÎT₀, т.е.

Ф(0,…,0)=f₀(0,…,0)=0, что верно.

Поэтому [T₀]=T₀.

Класс функций, сохраняющих значение 1.

Т₁ – класс бул. ф-ций сохраняющих 1:

fÎT₁ <=> f(1,…,1)=1.

входят: 1, x, x&y, xÚy, x®y, xºy.

невходят: Øx, xÅy, x­y, x¯y.

Класс Т₁ – замклут: [T₁]=T₁.

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

Ф(x₁,x₂,…x_n)=f₀(f₁(…),…f_k(…)), f₀, f₁,…,f_kÎT₁.

Ф(1,…,1)=f₀(f₁(1),…,f_k(1))=f₀(1,…,1)=1, т.е. ФÎТ₁.

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

Класс самодвойст. ф-ций: f^*=f

fÎS <=> f^*=f.

входят: x, Øx.

невходят: 0, 1, ®, &, Ú, ­, ¯.

Из определения самодвойственной ф-ции следует, что для ее задания достаточно определить значения f только для половины наборов, поэтому: |S|=2^{(2^n)/2}.

Класс самодвойст. ф-ций замкнут: [S]=S.

Ф(x₁,x₂,…x_n)=f₀(f₁(…),…f_k(…))

Ф^*(x₁,x₂,…x_n)=f₀^*(f₁^*(…),…f_k^*(…))

по принципу двойственности.

Ф^*(x₁,x₂,…x_n)=f₀(f₁(…),…f_k(…))=Ф(x₁,x₂,…x_n). T.к. f_i (i=1,k) – самодв.: f_i^*=f_i.

Лема о несамодвойственных ф-ях: Если ф-ция f не самодв., то из нее путем подстановки вместо переменных тождественных ф-ций и отрицания можно получить константу.

Док-во: Пусть f^*¹f, т.е. f^*=Øf(Øx₁,…Øx_n)¹f(x₁,…x_n) или $ набор (a₁,…,a_n): f^*(a₁,…,a_n)¹f(a₁,…,a_n), f(Øa₁,…,Øa_n)=f(a₁,…,a_n)

Построем ф-цию j(x)=f(x^a1,x^a2,…,x^an). Ф-ция j получена из f в результате подстановки вместо аргументов тождественной ф-ции или отрицания

j(1)=f(f^a1,f^a2,…,f^an), 1^ai={(1, если a_i=1), (0, если a_i=0)} т.е. 1^ai=a_i, тогда j(1)=f(a₁,a₂,…,a_n)=f(Øa₁,Øa₂,…,Øa_n) =f(0^a1,0^a2,…,0^an)=j(0) т.е. j – константа. ч.т.д.

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

М – класс монотонных ф-ций.

Пусть a=(a₁,…,a_n) и b=(b₁,…, b_n).

Набор a меньше набора b (a<b), {(< – такой треугольничек)} если a₁£b₁, a₂£b₂,…,a_n£b_n. Например: (1001)<(1011).

< – рефликсивно, транзитивно, антисиметрично, т.е. это отношение частичного порядка, но в общем случае не линейного порядка. Ф-ция f наз. монотонной, или всегда из того, что a<b следует f(a)£f(b).

входят: 0, 1, x, &, Ú.

невходят: Øx, ®, ­, ¯.

Для проверки ф-ции на монотонность необходимо проверить, что f(a)£f(b) для всевозможных пар сравнимых наборов.

Класс мон. ф-ций замкнут: [M]=M.

Соотношение a<b индуцирует это же соотношение на всевозможных поднаборов a и b.

(a_j1, a_j2, …,a_jij)<(b_j1, b_j2, …,b_jij).

Пусть g_i=f_j(a_j1, a_j2, …,a_jij), d_i=f_j(b_j1, b_j2, …,b_jij) тогда из того, что f_jÎM, g_i£d_j (j=1,k), т.е. g<d но f₀ÎM т.е. f₀(g)£f₀(d), а, значит Ф(g)£Ф(d). ч.т.д.

Лема о немонотонных ф-циях: Если ф-ция f немонотонна, то из нее путем подстановки вместо переменных констант и тождественной ф-ции можно подставить отрицание.

Пусть fÏM т.е. $a<b: f(a)<f(b), поэтому f(a)=1, f(b)=0. Покажем, что найдутся два соседних набора (по некоторой переменной) a и b такие, что a<b, а f(a)>f(b). Предположим обратное: пусть a<b и они отличаются, например, по первым t переменным.

a=(0, 0, …, 0, a_t+1,…,a_n)

b=(1, 1, …, 1, b_t+1,…, b_n)

По a и b построим последовательность наборов a⁽⁰⁾=a, a⁽¹⁾ – соседний с a⁽⁰⁾ по 1-й переменной, a⁽²⁾ – по 2-й переменной и т.д., a^(t)=b.

a=a⁽⁰⁾<a⁽¹⁾<…<a^(t)=b, причем f(a⁽⁰⁾)>f(a^(t)), поэтому в этой последовательности найдутся два соседних набора a⁽ⁱ⁾<a⁽ⁱ⁺¹⁾, а f(a⁽⁰⁾)>f(a⁽ⁱ⁺¹⁾).

Поэтому будем предпологать, что a и b – два соседних набора, для которых нарушается монотонность. Эти наборы можно найти по таблице истинности. Построим ф-цию j(x)=(a₁,…,a_i-1,x,a_i+1,…,a_n) (наборы и соседние по х).

j(0)=(a₁,…,a_i-1,0,a_i+1,…,a_n)=f(a)=1

j(1)=(a₁,…,a_i-1,1,a_i+1,…,a_n)=f(b)=0

т.е. j(x)=Øx ч.т.д.

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

L – класс ленейных ф-ций.

Ф-ция f(x₁,…x_n) наз. линейной, если ее представление в виде полинома Жегалкина имеет вид:

f(x₁,…x_n)=a₀Åa₁x₁Åa₂x₂Å…Åa_nx_n.

Слогаемые a_i×x_i наз. линейными, а все остальные – нелинейными.

линейные: 0, 1, x, Øx=xÅ1, Å.

нелинейные: &, Ú, ®, ­, ¯.

Каждая линейная ф-ция однозначно определяется своими коэфициэнтами, поэтому |L|=2ⁿ⁺¹.

т.к. суперпозиция линейных ф-ций – линейная ф-ция, то класс линейных ф-ций замкнут: |L|=L.

Лема о нелинейных ф-циях: Если ф-ция нелинейна, то из нее путем подстановки вместо переменных, констант, тождественной ф-ции и отрицания самой ф-ции можно получить коньюнкцию.

Док-во: Пусть fÏL. Тогда в ее представлении в виде полинома Жегалкина имеется наименьшее слагаемое. Будем предполагать, что в это слогаемое входят переменные x₁ и x₂. Тогда $(a₃, a₄,…,a_n):

f(x₁, x₂, a₃, a₄,…,a_n)=x₁×x₂Åa×x₁Åb×x₂Åg.

(в противном случае, переменные x₁, x₂ были бы фиктивными).

j(x₁, x₂)= x₁×x₂Åa×x₁Åb×x₂Åg.

По ф-ции построем ф-цию S:

S(x₁, x₂)=j(x₁Åb, x₂Åa)Åa×bÅg.

Можно показать, что S(x₁, x₂)=x₁&x₂.

	T0	T1	S	M	L
	-	+	+	+	+
x	+	+	+	+	+
Øx	-	-	-	-	+

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