Полные системы функций и теорема Поста

Замкнутые классы функций

Пусть $$\mathbf{P}=\bigcup_{n=0}^\infty \mathcal{P}_n$$ - это множество всех булевых функций. В предыдущем разделе мы установили, что любую функцию из $$\mathbf{P}$$ можно задать формулой над системой $$F_{B}=\{ \neg , \wedge , \vee \}$$ (в качестве таких формул можно, например, взять соответствующие ДНФ и КНФ). Такие системы функций называются полными.

Определение 5.1. Система булевых функций F называется полной,если формулами над этой системой можно задать любую булеву функцию из $$\mathbf{P}$$ .

Другим уже известным нам примером полной системы функций является система FJ={ 0, 1, *, +}, позволяющая задать произвольную булеву функцию с помощью многочлена Жегалкина. Разумеется, не всякая система является полной. Например, формулами над системой $$\{ \vee \}$$ невозможно выразить функцию тождественно равную 0 (почему?).Наша цель в этом разделе - найти критерий, позволяющий по системе функций определять ее полноту.

Для исследования полноты полезно следующее понятие.

Определение 5.2. Замыкание [F] системы функций F - это множество всех функций, которые можно задать с помощью формул над F .

Тогда определение полной системы можно переформулировать так:

система F является полной тогда и только тогда, когда $$[F] = \mathbf{P}$$ .

Замыкание обладает следующими основными свойствами.

Предложение 5.1.

$$F \subseteq [F]$$.

[[F]] = [F].

$$F \subseteq G \Rightarrow [F] \subseteq [G]$$.

Если система F является полной и $$F \subseteq [G]$$, то и система G является полной.

Доказательство. Все эти утверждения достаточно просто следуют из определения замыкания. Например, справедливость пункта (2) следует из того, что всякая функция из [F] задается некоторой формулой над F, а тогда всякая функция из [[F]], которая задается суперпозицией функций из [F], задается также некоторой формулой над F. Пункт (3) очевиден, а пункт (4) следует из (2) и (3):

$$F \subseteq [G] \Rightarrow [F] \subseteq [[G]] \Rightarrow [F] \subseteq [G]$$ и так как $$[F] = \mathbf{P}$$, то и $$[G] = \mathbf{P}$$.

Утверждение (4) позволяет устанавливать полноту некоторой системы, выражая с ее помощью все функции другой системы, полнота которой уже установлена.

Например, законы де Моргана позволяют выразить $$\vee$$ через пару $$\neg$$ , $$\wedge:$$ $$X \vee Y \equiv \neg (\neg X \wedge \neg Y)$$ и $$\wedge$$ - через пару $$\neg$$ , $$\vee:$$ $$X \wedge Y \equiv \neg (\neg X \vee \neg Y)$$. Поэтому каждая из систем $$F_{\wedge }=\{ \neg ,\wedge \}$$ и $$F_{\vee }=\{ \neg ,\vee \}$$ также является полной. Эквивалентности (7) и (8) позволяют выразить $$\vee$$ через пару $$\neg$$ , $$\to:$$ $$X \vee Y \equiv \neg X \to Y$$. Следовательно, полной будет и система $$F_{\to }=\{ \neg ,\to \}$$.

Имеются ли полные системы из одной двуместной функции? Да. Рассмотрим систему, { | }, включающую лишь штрих Шеффера. Напомним, что $$(X |Y) \equiv \neg (X \wedge Y)$$. Тогда нетрудно проверить, что $$\neg X \equiv (X | X)$$ и $$(X \wedge Y) \equiv ((X | Y)|(X | Y))$$. Следовательно, система { | } полная.

Определение 5.3. Система функций F называется замкнутой, если F = [F] .

Очевидно, что замкнутая система F, не содержащая всех функций из $$\mathbf{P}$$, не является полной.

Далее в этом разделе мы будем использовать верхний индекс в круглых скобках Для указания числа аргументов функции, т.е. f(n) означает, что $$f \in \mathcal{P}_n$$.

Определим пять важных замкнутых систем.

Определение 5.4.

(1,2) Функция $$f^{(n)} \in \mathbf{P}$$ сохраняет 0 (сохраняет 1),если f(0,0,... ,0)=0 ( f(1,1,...,1) = 1 ). Класс всех функций, сохраняющих 0, обозначим через $$\mathbf{S}_0$$, а класс всех функций, сохраняющих 1, - через $$\mathbf{S}_1$$.

(3) Функция $$f^{(n)} \in \mathbf{P}$$ называется самодвойственной, если для любого набора аргументов $$(\sigma_1, \sigma_2, \ldots, \sigma_n) \in \mathbf{B}^n$$ имеет место равенство:

$$f(\sigma_1, \sigma_2, \ldots, \sigma_n) = \neg f(\neg\sigma_1,\neg \sigma_2, \ldots,\neg \sigma_n).$$

Таким образом, самодвойственные функции принимают на противоположных наборах противоположные значения. Класс всех самодвойственных функций обозначим через $$\mathbf{S}$$.

(4) Функция $$f^{(n)} \in \mathbf{P}$$ называется линейной, если она может быть задана линейным многочленом Жегалкина вида

$$\alpha_0 + \alpha_1 X_1 + \alpha_2 X_2 + \ldots \alpha_n X_n,$$

где $$\alpha _{i} \in \{ 0, 1\}$$ при i=0, 1, 2, ..., n.

Класс всех линейных функций обозначим через $$\mathbf{L}$$.

(5) Функция $$f^{(n)} \in \mathbf{P}$$ называется монотонной, если для любых двух наборов аргументов $$(\sigma_1, \sigma_2, \ldots, \sigma_n)\in \mathbf{B}^n$$ и $$(\rho_1, \rho_2, \ldots, \rho_n) \in \mathbf{B}^n$$ таких, что для всех $$j \in [1,n]$$ $$\sigma _{j} \ge \rho _{j}$$, имеет место неравенство

$$f(\sigma_1, \sigma_2, \ldots, \sigma_n) \geq f(\rho_1, \rho_2, \ldots, \rho_n).$$

Класс всех монотонных функций обозначим через $$\mathbf{M}$$.

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

Функции f1, f2, f3, f4 и f5

X1	X2	X3	f1	f2	f3	f4	f5
0	0	0	1	1	0	0	0
0	0	1	0	1	0	1	0
0	1	0	0	0	1	1	1
0	1	1	1	0	0	0	1
1	0	0	1	0	1	1	0
1	0	1	0	0	0	0	0
1	1	0	0	1	1	0	1
1	1.	1	0	1	1	1	1

Из определений непосредственно следует, что f3, f4 и f5 сохраняют 0, т.е. входят в $$\mathbf{S}_0$$, а функции f2, f3, f4 и f5 сохраняют 1, т.е. входят в $$\mathbf{S}_1$$. Функция f3 является самодвойственной, а f2 - нет, так как f2(0,0,0) = f2(1,1,1). Функция f2 является линейной - она задается многочленом X1 + X2 +1. Функция f5 является монотонной, а f3 - нет, так как f3(0,1,1)=0 < 1=f3(0,1,0).

Теорема 5.1. Классы $$\mathbf{S}_0, \mathbf{S}_1, \mathbf{S},\mathbf{L}$$ и $$\mathbf{M}$$ являются замкнутыми.

Доказательство. Замкнутость всех указанных классов устанавливается индукцией по построению формул. Пусть $$F \in \{\mathbf{S}_0, \mathbf{S}_1, \mathbf{S}, \mathbf{L}, \mathbf{M}\}$$ и $$f \in [F]$$ задается некоторой формулой над F. Нужно показать, что тогда $$f \in F$$.

Базис индукции, когда эта формула есть переменная $$X$$, очевиден.

Пусть f(X1, ..., Xk)= g(f1(X1, ..., Xk), ..., fn(X1, ..., Xk)), и функции $$g^{(n)}, f_1^{(k)}, \ldots, f_n^{(k)}$$ входят в F. Требуется показать, что тогда и f входит в F.

Для $$F=\mathbf{S}_0$$ это просто:

$$f(0,0,\ldots,0)=g(f_1(0,\ldots,0),\ldots, f_n(0,\ldots, 0))= g(0,0,\ldots,0) = 0.$$

Аналогично проверяется случай $$F=\mathbf{S}_1$$.

Если $$F=\mathbf{S}$$ и $$(\sigma_1, \sigma_2, \ldots,\sigma_k)$$ - произвольный набор аргументов, то

$$f(\sigma_1, \sigma_2, \ldots, \sigma_k) = \neg g(\neg f_1(\sigma_1,\ldots, \sigma_k), \ldots, \neg f_n(\sigma_1, \ldots, \sigma_k))= \\ \ \ \neg g(\neg\neg f_1(\neg \sigma_1, \ldots, \neg\sigma_k), \ldots , \neg\neg f_n(\neg \sigma_1, \ldots, \neg\sigma_k)) = \\ \ \ \neg g( f_1(\neg \sigma_1, \ldots,\neg \sigma_k), \ldots, f_n(\neg \sigma_1, \ldots,\neg \sigma_k)) = \\ \ \ \ \neg f(\neg\sigma_1,\neg \sigma_2, \ldots,\neg \sigma_k).$$

Следовательно, $$f \in \mathbf{S}$$.

Пусть $$F=\mathbf{L}$$. Так как тогда g(n) и все $$f_i^{(k)}$$ линейны, то существуют коэффициенты $$\alpha _{0},\alpha _{1},\dots , \alpha _{n}$$ и $$\beta _{0i}, \beta _{1i}, \dots , \beta _{ki} (i=1,\dots ,n)$$ такие, что $$g(X_{1},\dots ,X_{n})=\alpha _{0} + \alpha _{1}X_{1} + \dots + \alpha _{n}X_{n}$$ и $$f_{i}(X_{1}, \dots , X_{k}) = \beta \_ \{ 0i\} + \beta \_ \{ 1i\} X_{1} + \beta \_ \{ ki\} X_{k} (i=1,\dots ,n)$$.

Подставив эти выражения в формулу для $$f^{(k)}$$, получим

$$f(X_1,\ldots,X_k)=\\= \alpha_0 +\alpha_1(\beta_{01} + \beta_{11}X_1 + \beta_{k1}X_k) + \ldots + \alpha_n(\beta_{0n} + \beta_{1n}X_1 + \beta_{kn}X_k) = \\=(\alpha_0 + \beta_{01}+ \ldots + \beta_{0n}) + (\alpha_1 \beta_{11}+ \ldots + \alpha_n\beta_{1n})X_1+ \ldots + \\+(\alpha_1 \beta_{k1}+ \ldots + \alpha_n\beta_{kn})X_k = \gamma_0 +\gamma_1X_1+ \ldots + \gamma_k X_k,$$

где $$\gamma _{0}, \gamma _{1}, \dots , \gamma _{k}$$ - значения сумм констант в соответствующих скобках.

Следовательно, $$f \in \mathbf{L}$$.

Наконец рассмотрим класс монотонных функций. Если $$g^{(n)}$$ и все $$f_i^{(k)} \in \mathbf{M}$$ и $$(\sigma _{1}, \sigma _{2}, \dots , \sigma _{k})$$ и $$(\rho _{1}, \rho _{2}, \dots , \rho _{k})$$ - два набора аргументов такие, что для всех $$j \in [1,k] \sigma _{j} \ge \rho _{j}$$, то

$$f_i(\sigma_1, \sigma_2, \ldots, \sigma_k)\geq f_i(\rho_1, \rho_2, \ldots, \rho_k)$$

и поэтому

$$f(\sigma_1, \sigma_2, \ldots, \sigma_k)= g(f_1(\sigma_1, \sigma_2, \ldots, \sigma_k), \ldots,\\ f_n(\sigma_1, \sigma_2, \ldots, \sigma_k)) \geq g(f_1(\rho_1, \rho_2, \ldots, \rho_k), \ldots, \\ f_n(\rho_1, \rho_2, \ldots, \rho_k)) =f(\rho_1, \rho_2, \ldots, \rho_k).$$

Таким образом, $$f \in \mathbf{M}$$.

Следствие 5.1.1. Классы функций $$\mathbf{S}_0, \mathbf{S}_1, \mathbf{S}, \mathbf{M}$$ и $$\mathbf{L}$$ не являются полными.

Критерий полноты (теорема Поста)

Оказывается, что всякая система, не содержащаяся внутри одного из указанных пяти классов полна.

Теорема 5.2. (Теорема Поста о полноте) Система булевых функций F является полной тогда и только тогда, когда она не содержится ни в одном из классов $$\mathbf{S}_0, \mathbf{S}_1, \mathbf{S}, \mathbf{M}$$ и $$\mathbf{L}$$, т.е. когда в ней имеется хотя бы одна функция, не сохраняющая 0, хотя бы одна функция, не сохраняющая 1, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.

Доказательство. Необходимость условия теоремы непосредственно следует из установленного выше следствия 5.1.1.

Для доказательства достаточности предположим, что F Содержит не сохраняющую 0 функцию $$f_0^{(i)}$$, не сохраняющую 1 функцию $$f_1^{(j)}$$, несамодвойственную функцию $$f_s^{(k)}$$, немонотонную функцию $$f_m^{(r)}$$ и нелинейную функцию $$f_l^{(p)}$$. Покажем, что с помощью этих функций всегда можно выразить функции одной из двух уже известных нам полных систем: $$\{ \neg ,\wedge \}$$ или $$\{ \neg , \vee \}$$. Для этого установим, что:

используя f0, f1 и fs, можно выразить константы 0 и 1;

с помощью констант из fm можно получить отрицание $$\neg$$ ;

с помощью констант и отрицания из fl можно получить конъюнкцию $$\wedge$$ или дизъюнкцию $$\vee.$$

Лемма 5.1. Формулами, построенными из функций f0, f1 и fs,можно задать константы 0 и 1.

Доказательство.. Рассмотрим два возможных значения $$f_0$$ на наборе аргументов, состоящем из одних единиц.

Случай 1. f0(1, ... , 1)= 0. Рассмотрим функцию g(X), заданную формулой f0(X,... , X). Тогда, очевидно, g(0) =f0(0, ... , 0) =1, а g(1) = f0(1, ... , 1)= 0. Таким образом, получили отрицание: $$g(X) = \neg X$$. Так как $$f_s^{(k)} \notin \mathbf{S}$$, то для некоторого набора значений аргументов $$(\sigma _{1}, \dots , \sigma _{k})$$ имеет место равенство $$f_{s}(\sigma _{1}, \dots , \sigma _{k}) = f_{s}(\neg \sigma _{1}, \dots ,\neg \sigma _{k})= const \in \{ 0, 1\}$$. Положим тогда $$h(X) = f_{s}(X^{\sigma 1}, \dots , X^{\sigma k})$$ (такая подстановка переменной X1 и ее отрицания X0 возможна, так как мы уже получили отрицание). Тогда h - это константа const. Действительно, $$h(1) =f_{s}(1^{\sigma 1}, \dots , 1^{\sigma k})=f_{s}(\sigma _{1}, \dots , \sigma _{k}) = f_{s}(\neg \sigma _{1}, \dots ,\neg \sigma _{k})= f_{s}(0^{\sigma 1}, \dots , 0^{\sigma k})=h(0)= const$$. Другая константа тогда задается формулой $$\neg h(X)$$.

Случай 2. f0(1, ... , 1)= 1. В этом случае формула f0(X,... , X) задает функцию g(X), тождественно равную 1, а формула f1(g(X), ... , g(X)) задает функцию h(X), тождественно равную 0. Действительно, $$h(\sigma )=f_{1}(g(\sigma ), \dots , (\sigma ))= f_{1}(1, \dots , 1) = 0$$ для любого $$\sigma \in \{ 0,1\}$$.

Лемма 5.2. Формулами, построенными из констант 0 и 1 и немонотонной функции $$f_m^{(r)},$$ можно задать отрицание $$\neg.$$

Доказательство. Так как $$f_m^{(r)}$$ немонотонна, то имеются два разных набора аргументов $$\tilde{\sigma}=(\sigma_1, \ldots , \sigma_r)$$ и $$\tilde{\rho}=(\rho_1, \ldots , \rho_r)$$ таких, что для всех $$j \in [1,r] \sigma _{j} \ge \rho _{j}$$ и при этом $$f_{m}(\sigma _{1}, \sigma _{2}, \dots , \sigma _{n}) =0$$, а $$f_{m}(\rho _{1}, \rho _{2}, \dots , \rho _{n})=1$$. Пусть i1, ... , il - это все индексы, для которых $$\sigma_{i_j} =1 > \rho_{i_j}=0$$. Так как $$\tilde{\sigma} \neq \tilde{\rho}$$, то l >= 1. Определим последовательность из (l+1) -го набора аргументов $$\tilde{\rho}_0, \tilde{\rho}_1, \ldots, \tilde{\rho}_l$$ следующим образом: $$\tilde{\rho}_0 = \tilde{\rho}$$, а далее каждый набор $$\tilde{\rho}_j$$ получется из предыдущего $$\tilde{\rho}_{j-1}$$ заменой ij -ой координаты с 0 на 1. Таким образом, последний из этих наборов $$\tilde{\rho_l}$$ совпадает с $$\tilde{\sigma}$$. Рассмотрим значения функции fm на этих наборах: $$f_m(\tilde{\rho_0}), f_m(\tilde{\rho_1}), \ldots, f_m(\tilde{\rho_l})$$. Так как первое из них $$f_m(\tilde{\rho_0})=f_m(\tilde{\rho})=1$$, а последнее $$f_m(\tilde{\rho_l})=f_m(\tilde{\sigma})=0$$, то найдутся два соседних набора $$\tilde{\rho}_{j-1}$$ и $$\tilde{\rho_{j}}$$ таких, что $$f_m(\tilde{\rho}_{j-1})= 1$$, а $$f_m(\tilde{\rho_{j}})= 0$$. Они отличаются только ij -ой координатой. Пусть $$\tilde{\rho}_{j-1}= (\alpha_1,\ldots, \alpha_{i_j-1},0,\alpha_{i_j+1}, \ldots , \alpha_r)$$, a $$\tilde{\rho}_{j}= (\alpha_1,\ldots, \alpha_{i_j-1},1,\alpha_{i_j+1}, \ldots , \alpha_r)$$. Положим тогда $$g(X)= f_m(\alpha_1,\ldots, \alpha_{i_j-1}, X,\alpha_{i_j+1}, \ldots, \alpha_r)$$. Тогда $$g(0) = f_m(\alpha_1,\ldots, \alpha_{i_j-1}, 0,\alpha_{i_j+1}, \ldots , \alpha_r)=1$$, a $$g(1) = f_m(\alpha_1,\ldots, \alpha_{i_j-1}, 1,\alpha_{i_j+1}, \ldots , \alpha_r)=0$$. Следовательно, $$g(X) = \neg X$$.

Лемма 5.3. Формулами, построенными из констант 0 и 1, отрицания $$\neg$$ и нелинейной функции $$f_l^{(p)},$$ можно задать дизъюнкцию $$\vee$$ или конъюнкцию $$\wedge.$$

Доказательство. Так как $$f_l^{(p)}\notin \mathbf{L}$$, то в представляющий ее многочлен Жегалкина обязательно входит слагаемое вида $$X_{i_1}*X_{i_2}*\ldots *X_{i_k}\ (k \geq 2)$$. Выберем самое короткое из таких слагаемых и рассмотрим функцию $$g_1(X_{i_1},X_{i_2}) = f_l(\sigma_1, \ldots, \sigma_{i_1 -1}, X_{i_1},\sigma_{i_1 +1},\ldots, \sigma_{i_2 -1}, X_{i_2},\sigma_{i_2 +1}, \ldots, \sigma_p)$$, где $$\sigma _{j}=1$$ при $$j \in \{ i_{3},\dots , i_{k}\}$$ и $$\sigma _{j}=0$$ в остальных случаях. При такой подстановке констант многочлен Жегалкина для g(X1,X2) = g1(X1,X2) имеет вид: $$\alpha _{0} +\alpha _{1} X_{1} + \alpha _{2} X_{2} + X_{1}*X_{2}$$, где $$\alpha _{0},\alpha _{1},\alpha _{2} \in \{ 0, 1\}$$. Таким образом, всего возможно 8 вариантов. Рассмотрим 4 из них в случае, когда $$\alpha _{0}=0$$. Тогда

при $$\alpha _{1}=0$$ и $$\alpha _{2}=0$$ получаем, что $$g(X_{1}, X_{2}) \equiv X_{1} \wedge X_{2}$$ ;

при $$\alpha _{1}=0$$ и $$\alpha _{2}=1$$ получаем, что $$g(\neg X_{1}, X_{2}) \equiv X_{2} + \neg X_{1} * X_{2} \equiv (1 + \neg X_{1})*X_{2} \equiv X_{1} \wedge X_{2}$$ ;

при $$\alpha _{1}=1$$ и $$\alpha _{2}=0$$ получаем, что $$g( X_{1}, \neg X_{2}) \equiv X_{1} + X_{1} * \neg X_{2} \equiv X_{1} *(1 + \neg X_{2}) \equiv X_{1} \wedge X_{2}$$ ;

при $$\alpha _{1}=1$$ и $$\alpha _{2}=1$$ имеем $$g(X_{1}, X_{2}) \equiv X_{1} + X_{2} + X_{1}*X_{2} \equiv X_{1} \vee X_{2}$$.

Остальные 4 варианта в случае, когда $$\alpha _{0}=1$$, получаются как отрицания соответствующих вариантов для $$\alpha _{0}=0$$.

Из приведенных трех лемм, очевидно, следует достаточность условия теоремы Поста.

Пример 5.2. Рассмотрим набор функций f, g и h, представленный в следующей таблице:

Функции f, g и h

X1	X2	X3	f	g	h
0	0	0	1	1	0
0	0	1	0	1	0
0	1	0	0	0	1
0	1	1	1	0	0
1	0	0	0	0	1
1	0	1	1	1	0
1	1	0	1	1	1
1	1	1	0	1	0

Функция f, очевидно, не сохраняет 0 и 1, но является самодвойственной. Функция g(X1,X2,X3)= 1+X1+X2 + X1 * X3 + X1 * X2 * X3 является несамодвойственной, немонотонной и нелинейной. По лемме 5.1 получаем, что $$f(X,X,X) = \neg X$$, функция $$g_{1}(X)=g(X,X,X) \equiv 1$$, а функция $$g_{0}(X) = \neg g_{1}(X) \equiv 0$$. Подставив X2=0 в g получим g3(X1,X3)= g(X1,0,X3)= 1 + X1 + X1 * X3. Тогда $$h(X_{1},X_{2}) = \neg g_{3}(X_{1}, \neg X_{2}) = \neg (1 + X_{1} + X_{1} * \neg X_{2}) \equiv \neg (1 + X_{1}*(1+ \neg X_{2})) \equiv X_{1}*X_{2}$$. Таким образом, мы с помощью f и g сумели выразить обе функции полной системы $$\{ \neg , *(= \wedge )\}$$ и, следовательно, система функций {f, g } полная.

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

Например, система $$\{ \neg , \wedge , \vee \}$$ не является базисом, а каждая из систем $$\{ \neg , \wedge \} , \{ \neg , \vee \}$$ является. Мы уже знаем, что имеются полные системы, состоящие из одной функции (например, система { | } ). Они, конечно, являются базисами. Имеются и полные системы, включающие 3 функции, например, система { 1, *, +}, на которой основаны многочлены Жегалкина (отметим, что константу 0 можно выразить как 1+1). Из теоремы Поста следует, что никакая минимальная система не содержит более 5 функций. Оказывается, что для полноты всегда достаточно четырех функций.

Теорема 5.3. Во всяком базисе F содержится не более 4-х функций.

Доказательство. Действительно, по теореме Поста в базисе $$F$$ имеется функция $$f_0^{(i)}\notin \mathbf{S}_0$$. Поэтому f0(0,0, ..., 0) =1. Если она хотя бы на одном наборе значений аргументов принимает значение 0, то она немонотонна, т.е. $$f_0^{(i)}\notin \mathbf{M}$$. В противном случае, f0 на всех наборах значений аргументов равна 1. Но тогда она несамодвойственна , так как f0(0, 0, ..., 0)=1 = f0(1,1,..., 1). Во всех случаях $$f_0\notin \textbf{M}$$ или $$f_0 \notin \textbf{S}$$ и, следовательно, в системе F содержится не более 4-х функций.

Может быть, в минимальной системе можно обойтись тремя функциями? Это не так. Рассмотрим, например, систему $$F^{(4)}=\{ 0, 1, X \wedge Y, X+Y+Z\}$$. В этой системе, $$0 \notin \textbf{S}_1\cup \textbf{S}, 1 \notin \textbf{S}_0, X+Y+Z \notin \textbf{M}, X \wedge Y \notin \textbf{L}$$. Легко проверить, что при удалении любой из функций система F(4) перестает быть полной. Таким образом, теорема 5.3 дает наилучшую верхнюю оценку числа функций в базисе.

Замечание. Е. Пост в работах, опубликованных в 1921 и 1941 гг. не только установил критерий полноты, но и описал структуру всех замкнутых классов функций в $$\mathbf{P}$$. Он показал, что число таких классов счетно и что в каждом из них имеется собственный конечный базис.

Задачи

Задача 5.1. Докажите полноту системы $$\{ \downarrow \}$$, включающей только стрелку Пирса, непосредственно выразив через нее отрицание, дизъюнкцию и конъюнкцию.

Задача 5.2. Определите принадлежность каждой из функций f1, f2, f3, f4 и f5, представленных в таблице 5.1, каждому из классов $$\mathbf{S}_0, \mathbf{S}_1, \mathbf{S}, \mathbf{L}$$ и $$\mathbf{M}$$.

Задача 5.3. Используя результаты задачи 5.2, определите, какие из троек функций, представленных в таблице 5.1, являются полными системами. Имеются ли среди них полные системы из двух функций? Из одной функции?

Задача 5.4. Проверьте полноту системы функций {g, h}, представленных в таблице 5.2. Если она полна, выразите с помощью этих функций обе константы, отрицание $$\neg$$ и импликацию $$\to.$$

Задача 5.5. Докажите, что система $$\{ \vee , \wedge , \to \}$$ не является полной. Можно ли ее сделать полной, добавив некоторую константу?

Задача 5.6. Выразите функции $$\{ 0, 1, \vee , \wedge , ~\}$$ с помощью формул, построенных из функций полной системы $$\{ \neg , \to \}$$.

Задача 5.7. Определите количество функций из $$\mathcal{P}_n$$, принадлежащих каждому из классов $$\mathbf{S}_0, \mathbf{S}_1, \mathbf{S}$$ и $$\mathbf{L}$$.

Задача 5.8. Доказать, что для монотонных функций $$f^{(n)} \in M$$ справедливо представление $$f(X_{1},\dots , X_{n})= (X_{i} \wedge f(X_{1},\dots , X_{i-1}, 1, X_{i+1},\dots , X_{n}) ) \vee f(X_{1},\dots , X_{i-1}, 0, X_{i+1},\dots , X_{n}), (1 \le i \le n)$$. Вывести отсюда (индукцией по n ), что для всякой монотонной функции, отличной от константы, существует задающая ее ДНФ, не содержащая отрицаний переменных.

Задача 5.9. Докажите, что число монотонных функций в $$\mathcal{P}_n$$ не меньше $$2^{C_n^{[n/2]}}$$.

Задача 5.10. Найдите все базисы, которые можно получить, удаляя функции из системы $$\{ 0, 1, \wedge , \vee , \to \}$$.

Задача 5.11. Найти число булевых функций от n переменных, являющихся одновременно самодвойственными и линейными.

Задача 5.12. Найти число булевых функций от n переменных, являющихся одновременно монотонными и линейными.

Задача 5.13. Доказать, что если f(X1, ..., Xn) - линейная функция, отличная от константы, то $$|N^+_f| = 2^{n-1}$$. Верно ли обратное?