1.10.5. Линейность. Класс l

Определение. Функция f (х ⁿ) называется линейной, если она представима в виде полинома Жегалкина: f(хⁿ ) = ₀  ₁ х₁ …  _nх_n , где ₀ ,  ₁ , ... ,  _n — логические константы, принимающие значения 0 или 1 .

Множество линейных функций n переменных обозначают Lⁿ, все множество линейных функций алгебры — L. Это множество является предполным классом в Р₂. Если функция f  L, то ее называют нелинейной. Проверить линейность любой функции можно путем её разложения ее в полином Жегалкина.

Из элементарных функций линейными являются константы 0 и 1, одноместные функции х их, двухместные функции  и .

В общем случае справедлива

Лемма о нелинейной функции

Если функция f(хⁿ)  L, то путем подстановки вместо ее переменных констант 0, 1, функций х,х и, возможно, навешивания общего отрицания из f(хⁿ) всегда можно получить двухместную функцию умножения ху.

Доказательство. Из f (х ⁿ)  L следует, что ее можно представить в виде f (х ⁿ) = L(х ⁿ ) + N (х ⁿ ), где L(х ⁿ ) — линейная часть (возможно, L(х ⁿ )  0 ), N (х ⁿ ) — нелинейная часть (N (х ⁿ )  0).

Рассмотрим самое короткое произведение, содержащееся в нелинейной части N (х ⁿ ). Выделим в нём две произвольные переменные (допустим, начальные) и обозначим их х и у. Данное произведение можно представить в виде хух_к1...х_кs. Другие произведения, содержащие х и у, будут обязательно включать и другие сомножители х_к(s+1) , _{. . .} , х_кm. Подставляя вместо переменных х_к1, _{. . .} , х_кs константу 1, а вместо остальных (включая х_к(s+1) , ... , х_кm ) константу 0, получим функцию двух переменных F(x,у), которая в общем случае имеет следующий вид:

F(x,у) = ху +₁ х +₂ у +₃ .

При ₁ = 1 выполняем подстановку у =у, если ₂ = 1, то выполняем подстановку х = х. В итоге получаем новую функцию F₁ (x,у) = ху + ₃ .

Если ₃ = 0 , то искомое умножение получено, если ₃ = 1 , то умножение получаем, навешивая общее отрицание:

 F₁ (x,у) = F₂ (x,у) = ху.

ЗАДАЧИ

1. Почему линейны все функции, у которых число переменных не превышает 1?

2. Какие из перечисленных систем линейных функций образуют базис в L: а) {0, х  у}, б) {1, х  у} в) {0, 1, х  у} ?

3. Доказать, что если f(хⁿ) линейна и не является константой, то в векторе значений f(х ⁿ) всегда будет равное число значений 1 и 0. Верно ли обратное? Ответ обосновать.

4. Проверить линейность функций:

а) ху  yz  xz ; б) х  у  х у; в) (10110110); г) х у х у; д) (10011001); е) (0001100111111011).

5. Найти мощность класса Lⁿ.

6. Сколько существует в Lⁿ функций, существенно зависящих ровно от k (k ≤ n) своих переменных ?

7. Доказать замкнутость класса L .

8. Доказать предполноту класса L в Р₂ , например, с использованием леммы о нелинейной функции и сведением дополненной системы к {f} = { , ,} .

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

Рассмотренные выше замкнутые классы функций Т₀, Т₁, S, M, и L исчерпывают все множество предполных классов в P₂. Они являются независимыми в том смысле, что ни один из них не может быть выражен с помощью теоретико-множественных операций через остальные. Поэтому для любого непустого множества функций справедлива

Теорема 2.1.2 (Пост). Система функций {f} полна в P₂ тогда и только тогда, когда она не содержится целиком ни в одном из замкнутых предполных классов Т₀ ,Т₁ ,S, M и L.

Доказательство. Необходимость. Пусть {f} полна в P₂ ([{f}]=P₂). Докажем, что {f} не содержится ни в одном из классов Т₀ ,Т₁ ,S, M и L. Допустим верно обратное и {f} входит полностью в один из этих классов, обозначим его через К. Но тогда [{f}]  К  P₂ , т.е. имеет место строгое включение [{f}]  P₂, что противоречит определению полноты {f}.

Достаточность. Пусть {f} целиком не содержится ни в одном из классов Т₀ , Т₁ , S, M , L. Докажем ее полноту. Из условия невхождения следует, что в {f} можно выделить подмножество из пяти функций {f₀, f₁, f_S, f_M, f_L}, таких, что f₀  Т₀ , f₁  Т₁ , f_S  S, f_M  M, f_L  L (функции не обязательно должны быть все различны). Для полноты достаточно доказать, что из этой подсистемы с помощью суперпозиции всегда можно выделить функции { ,  }, так как они образуют полную систему в P₂.

Покажем, что из функций f₀, f₁, f_S всегда можно получить константы 0 и 1. Из условий f₀ Т₀ , f₁  Т₁ следует: f₀ (0,... ,0) =1, f₁ (1,...,1) = 0. Рассмотрим все возможные варианты значений f₀ и f₁ на противоположных наборах и применим к этим функциям дублирующие подстановки вида f(х,х,...,х).

1. f₀(1,...,1) = 1, f₁(0,...,0) = 0. Дублирующие подстановки f₀ (х, ... , х) и f₁ (х, ... , х) дают новые функции, являющиеся искомыми константами: f₀  1, f₁  0.

2. f₀ (1,...,1) = 1, f₁(0,...,0) =1. Дублирующие подстановки дают: f₀  1, f₁ х. Подставляя далее, получим f₁ (f₀ (х))  0.

3. f₀ (1, ... ,1) = 0, f₁ (0, ... ,0) = 0. Из дублирующих подстановок следует: f₀  х , f₁  0. Применяя взаимную подстановку, получим f₀ (f₁ (х))  1.

4. f₀ (1, ... ,1)=0, f₁ (0, ... ,0) = 1. После дублирующих подстановок получим: f₀  х , f₁ х . По лемме о несамодвойственной функции из f_S подстановкойх всегда можно получить одну из констант. Вторую получаем при помощи функциих .

Таким образом, доказано, что {0,1}[{f₀, f₁, f_S}]. По лемме о немонотонной функции из f_M путем подстановки констант 0,1 всегда может быть получена функциях. Отсюда следует: {0, 1,х} [{f₀, f₁, f_S ,f_M}]. По лемме о нелинейной функции из f_L путем подстановки функций 0, 1,х всегда может быть получена функция умножения ху. В итоге получаем: { ,  } [{f₀, f₁, f_S , f_M , f_L }]. Так как [{ ,  }] = P₂ , то отсюда следует [{f₀, f₁, f_S , f_M , f_L}]=P₂ и [{f}]=P₂ , что и требовалось доказать.

Пример 1. Проверить полноту системы функций {f} = {f ₁ = х  у , f ₂ = х у } в P₂ .

Решение. Используем теорему Поста. Функция f₁ = х  у не входит в классы S, L, но входит в классы Т₀, Т₁, M. Следовательно, у функции f₂ = х у достаточно проверить ее вхождение в Т₀, Т₁, M. Так как f₂ входит в Т₁, то отсюда следует, что вся система {f} целиком содержится в Т₁. Следовательно, по теореме Поста она не полна в P₂.

Пример 2. Можно ли с помощью операции суперпозиции из системы функций {f}={f₁ = (1010), f₂ = (0110), f₃ = (0011)} получить функции g₁ = (1011), g₂ = (1111).

Решение. Для наглядности решения рассмотрим таблицу истинности функций f₁ , f₂ , f₃ и g₁, g₂. Переменные обозначим х и у.

x	y	f1	f2	f3	g1	g2
0	0	1	0	0	1	1
0	1	0	1	0	0	1
1	0	1	1	1	1	1
1	1	0	0	1	1	1

Как следует из векторов истинности, f₁ =у, f₂ = х у, f₃ = х. Проверка вхождения данных функций в предполные классы показывает, что все они принадлежат классу L линенйых функций. Так как данный класс замкнут относительно операции суперпозиции, то её применение к функциям f₁, f₂, f₃ будет давать только линейные функции.

Разложение функции g₁ в полином Жегалкина дает выражение 1 у ху. Данная функция нелинейна и не может быть получена из системы {f} с помощью операции суперпозиции. g₂ является линейной функцией - константой 1. Выражение для неё с использованием {f} может быть получено, например, в результате следующей подстановки: 1 = xx = f₂(f₃(х),f₁ (х)).

Ответ:1) функция g₁ не может быть получена из системы {f} с помощью операции суперпозиции, 2) g₂ = f₂(f₃(х), f₁(х)).

Cистема, состоящая из одной функции х у - ‘штрих Шеффера’, полна в P₂. Это следует из возможности представления любой функции алгебры логики в виде ШНФ. Также данная функция не входит ни в один из предполных классов Т₀ , Т₁ , S, M и L .

Определение. Если система, содержащая одну функцию f, полна в P₂, то функцию f называют шефферовой.

ЗАДАЧИ

1. Проверить полноту в P₂ систем функций: а) {, ху}; б) {,}; в) { , ху z}; г) {, 1,}; д) {, 0}; е){,}; ж) { ,,}; з) {ху,ху}; и) {(1011), (10010110)}; к) {х у z, (1001)} ; л) {(1010), (11011101)}.

2. Дополнить систему функций до полной в P₂ при помощи функций, не являющихся шефферовыми: а) {(1001), (0110)}, б) { , х уz}.

3. Проверить, можно ли только с помощью операции суперпозиции получить:

а) из функции (0001) функцию (1001);

б) из функции {ху} функцию ху ;

в) из функции {х у} функцию ху ;

г) из функций {ху, ху} функцию ху.

4. Найти все шефферовы функции от двух переменных.