Полнота системы функций
Пусть функция $f(x_1, x_2, ..., x_n)$ представима в виде формулы над $\mathcal P$, и любая функция из $\mathcal P$ представима в виде формулы над $\mathcal Q$.
Тогда функция $f$ представима в виде формулы над $\mathcal Q$.Пусть, $\mathcal U$ — формула над $\mathcal P$, реализующая функцию $f$. $\mathcal U_1$, $\mathcal U_2$, ..., $\mathcal U_k$ — формулы над $\mathcal Q$, реализующие все функции $g_1$, $g_2$, ..., $g_k$ множества $\mathcal P$. Тогда каждое вхождение функции $g_i$ в формулу $\mathcal U$ можно заменить формулой $\mathcal U_i$. Проведя такую замену, получим формулу $\mathcal U'$ над $\mathcal Q$.
Очевидно, формула $\mathcal U'$ эквивалентна формуле $\mathcal U$, поскольку они отличаются заменой подформул на эквивалентные.
и $\mathcal Q\subseteq P_2$. Пусть $\mathcal P$ — полная система функций, и любая функция из $\mathcal P$ представима в виде формулы над $\mathcal Q$.
Тогда, $\mathcal Q$ — полная система функций.
Приведем несколько примеров полных систем функций.
Рассмотрим произвольную функцию $f\in P_2$. Если $f = 0$, то $f=f_{\mathcal U}$, где $\mathcal U=x\wedge \overline x$. В противном случае $f\neq 0$. Тогда по утверждению $f=f_{\mathcal U}$, где [math]\displaystyle{ \mathcal U= \bigvee_{\substack{(\sigma_1,...,\sigma_n)\\f(\sigma_1,...,\sigma_n)=1}} x_1^{\sigma_1}\cdots x_n^{\sigma_n} }[/math].
Доказательство очевидно следует из утверждения и правил де Моргана, если заметить, что [math]\displaystyle{ x\vee y = \overline{\overline{x}\wedge\overline{y}},\quad \textrm{ и }\quad x\wedge y = \overline{\overline{x}\vee\overline{y}}. }[/math] Таким образом, подставив в любую формулу, выражающую функцию $f$ в виде формулы над $\{\neg, \vee, \wedge\}$, указанные выражения для $\vee$ или $\wedge$, можно получить эквивалентную формулу над $\{\neg, \wedge\}$ или над $\{\neg, \vee\}$.
2. Других полных систем, состоящих из одной функции от двух переменных нет.
1) а) [math]\displaystyle{ \overline x=x | x }[/math], [math]\displaystyle{ x\vee y = \overline x | \overline y = (x | x) | (y | y) }[/math]. б) $\overline x = x\downarrow x$, $x\wedge y = \overline x\downarrow\overline y=(x\downarrow x)\downarrow (y\downarrow y)$. 2) Пусть $h(x,y)\in P_2$ и $\{h\}$ — полная система функций. Пусть $h(0,0)=0$. Тогда, если $f(x)$ задана в виде формулы над $\{h\}$, то $f(0)=0$. Действительно, функция $f$ имеет вид $f(x) = h(\mathcal U_1,\mathcal U_2)$, где $\mathcal U_i$ — переменная $x$, или формула того же вида, что и $f$, $i=1,2$. Таким образом, в конце концов оказывается, что $f(0)=h(0,0)=0$. Тогда, с помощью только функции $h(x,y)$ не может быть функция отрицания, поскольку $\neg 0 = 1$. Следовательно $h(0,0)=1$. Аналогично можно показать, что $h(1,1)=0$. Теперь рассмотрим все функции от двух переменных, удовлетворяющие полученному условию: $h(0,0)=1$, $h(1,1)=0$. Всего таких функций четыре.
[math]\displaystyle{ \begin{array}{cc|cccc} x & y & \downarrow & | & \overline x & \overline y\\ \hline 0 & 0 & 1 & 1 & 1 & 1\\ 0 & 1 & 0 & 1 & 1 & 0\\ 1 & 0 & 0 & 1 & 0 & 1\\ 1 & 1 & 0 & 0 & 0 & 0\\ \end{array} }[/math]
Как видно из таблицы, две из этих функций известны нам как стрелка Пирса и штрих Шеффера, а две другие представляют из себя функцию отрицания от аргументов $x$ и $y$. Поскольку система из одной функции отрицания не является полной системой функций, утверждение доказано.
Истинность этого утверждения следует из того, что любая функция из $P_2$ представима в виде полинома Жегалкина.
[math]\displaystyle{ K_0 = \{f_1(x_1,...,x_{k_1}), f_2(x_1,...,x_{k_2}), ..., f_m(x_1,...,x_{k_m})\}. }[/math] $f$ — суперпозиция ранга 1 (элементарная суперпозиция) функций $f_1$, ..., $f_m$, если $f$ получена одним из способов:
a) переименованием некоторой переменной $x_j$ функции $f_i$, $i\in\{1,...,m\}$, $j\in\{1,...,k_i\}$: [math]\displaystyle{ f_i(x_1,...,x_{j-1},y,x_{j+1},...,x_{k_i}), }[/math] где $y$ может совпасть с любой переменной;
b) подстановкой некоторой функции $f_l$ вместо переменной $x_j$ функции $f_i$, $l,i\in\{1,...,m\}$, $j\in\{1,...,k_i\}$: [math]\displaystyle{ f_i(x_1,...,x_{j-1},f_l(x_1,...,x_{k_l}),x_{j+1},...,x_{k_i}). }[/math]
Множество суперпозиций ранга 1 функций из $K_0$ обозначим $K_1$.
Также, множество суперпозиций ранга 1 функций из $K_{i-1}$ обозначим $K_{i}$, $i=\overline{1,\infty}$. Функции из множества $K_i$ будем называть суперпозициями ранга $i$ функций из $K_0$.
Таким образом, мы можем переформулировать определение полной системы.
Множество $M$ — не замкнуто.
Несложно проверить нижеследующие свойства операции замыкания.
![Слева M = {x, ¬x} совпадает с замыканием, справа M = {¬x} даёт [M] = {¬x, x}: класс не замкнут, но M = [M]](/wiki/%D0%A4%D0%B0%D0%B9%D0%BB:P39-01-closure-examples.svg)
Пусть $M, N\subset P_2$.
- 1) Замыкание множества содержит само множество: $\mathfrak M \subseteq [\mathfrak M].$
- 2) Замыкание произвольного множества замкнуто: $[{[\mathfrak M]}] = [\mathfrak M].$
- 3) Замыкание сохраняет включение множеств: $\mathfrak M \subseteq \mathfrak N\quad \Rightarrow [\mathfrak M] \subseteq [\mathfrak N].$
- 4) Замыкание объединения содержит объединение замыканий: $[\mathfrak M]\cup [\mathfrak N]\subseteq [\mathfrak M \cup \mathfrak N].$
Обозначим множество суперпозиций ранга $i$ функций из $\mathfrak M$ за $\mathfrak M_i$. Пусть $\mathfrak M_1 = \mathfrak M$. Тогда $\mathfrak M_2$ — множество суперпозиций ранга 1 функций из $\mathfrak M_1 = \mathfrak M$. Следовательно, $\mathfrak M_2 = \mathfrak M_1 = \mathfrak M$. Аналогично можно убедиться, что $\mathfrak M_i = \mathfrak M$, $i=\overline{1,\infty}$. Далее, когда мы будем доказывать замкнутость классов функций, будем ограничиваться только рассмотрением суперпозиций ранга 1. С учетом определения замкнутости можно дать еще одно альтернативное определение полноты.
Конспект: Дискретная математика