СВ: Новая страница: «{{Определение |definition= Система функций $\mathcal P\subseteq P_2$ называется полной, если любую функци...»

2026-10-25T10:06:44Z

Новая страница: «{{Определение |definition= Система функций $\mathcal P\subseteq P_2$ называется полной, если любую функци...»

Новая страница

{{Определение
|definition=
Система функций $\mathcal P\subseteq P_2$ называется полной, если любую функцию
из $P_2$ можно представить в виде формулы над $\mathcal P$.
}}

{{Замечание
|content=Удобно доказывать полноту системы функций, показывая, что она сводится к уже известной полной системе.
}}
{{Лемма
|statement=Пусть даны две системы функций $\mathcal P\subseteq P_2$ и $\mathcal Q\subseteq P_2$.
Пусть функция $f(x_1, x_2, ..., x_n)$ представима в виде формулы над $\mathcal P$,
и любая функция из $\mathcal P$ представима в виде формулы над $\mathcal Q$.
Тогда функция $f$ представима в виде формулы над $\mathcal Q$.
|proof=
Пусть, $\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$,
поскольку они отличаются заменой подформул на эквивалентные.

{{Теорема
|statement=Пусть даны две системы функций $\mathcal P\subseteq P_2$
и $\mathcal Q\subseteq P_2$.
Пусть $\mathcal P$ {{---}} полная система функций,
и любая функция из $\mathcal P$ представима в виде формулы над $\mathcal Q$.
Тогда, $\mathcal Q$ {{---}} полная система функций.
}}

Приведем несколько примеров полных систем функций.
{{Утверждение
|statement=$\{\neg, \vee, \wedge\}$ {{---}} полная система функций.
|proof=
Рассмотрим произвольную функцию $f\in P_2$.
Если $f = 0$, то $f=f_{\mathcal U}$, где $\mathcal U=x\wedge \overline x$.
В противном случае $f\neq 0$. Тогда по утверждению
$f=f_{\mathcal U}$, где <math>\mathcal U= \bigvee_{\substack{(\sigma_1,...,\sigma_n)\\f(\sigma_1,...,\sigma_n)=1}} x_1^{\sigma_1}\cdots x_n^{\sigma_n}</math>.
}}
{{Следствие
|statement=$\{\neg, \wedge\}$ и $\{\neg, \vee\}$ {{---}} полные системы функций.
|proof=
Доказательство очевидно следует из утверждения
и правил де Моргана, если заметить, что
<math>
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\}$.
}}
{{Утверждение
|statement=1. Системы функций <math>\{|\}</math> и $\{\downarrow\}$ {{---}} полные системы функций.<br>
2. Других полных систем, состоящих из одной функции от двух переменных нет.
|proof=
1) а) <math>\overline x=x | x</math>, <math>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>
\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$.
Поскольку система из одной функции отрицания не является полной системой функций,
утверждение доказано.
}}
{{Утверждение
|statement= $\{0, 1, \oplus, \wedge\}$ {{---}} полная система функций.
|proof=
Истинность этого утверждения следует из того, что любая функция из $P_2$ представима в виде полинома Жегалкина.
}}
{{Следствие
|statement=Так как $1\oplus 1 = 0$, полной системой функций является и $\{1, \oplus, \wedge\}$.
}}
{{Определение
|definition=
Пусть
<math>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>
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>
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$.
}}
{{Определение
|definition=
Суперпозицией функций из $K_0$ будем называть суперпозицию любого ранга.
Другими словами, $f$ {{---}} суперпозиция функций $f_1$, ..., $f_m$, если $\exists t\in \mathbb{N}$ такое, что $f\in K_t$.
}}
{{Замечание
|content=По сути дела утверждение, что $f$ является суперпозицией функций из $K_0$, эквивалентно утверждению, что $f$ представима в виде формулы над $K_0$.
}}
Таким образом, мы можем переформулировать определение полной системы.
{{Определение
|definition=
Система функций $\mathcal P\subseteq P_2$ называется полной, если любая функция из $P_2$ является суперпозицией функций из $\mathcal P$.
}}
{{Определение
|definition=
Пусть $\mathfrak M \subseteq P_2$. Замыканием $\mathfrak M$ называется множество
<math>
[\mathfrak M] = \{f | f - \textrm{ суперпозиция функций из }\mathfrak M\}.
</math>
}}
{{Определение
|definition=
Пусть $\mathfrak M \subseteq P_2$. $\mathfrak M$ {{---}} замкнутое множество функций,
если $\mathfrak M = [\mathfrak M]$.
}}
{{Пример
|content=
1) $M = \{x,\overline x\}$. Тогда $[M] = \{x,\overline x\}=M$ и $M$ {{---}} замкнуто.

2) $M = \{\overline x\}$. Тогда $[M] = \{x,\overline x\} \neq M$.
}}
Множество $M$ {{---}} не замкнуто.

Несложно проверить нижеследующие свойства операции замыкания.

[[Файл:p39-01-closure-examples.svg|frame|none|900px|alt=Слева M = {x, ¬x} совпадает с замыканием, справа M = {¬x} даёт [M] = {¬x, x}: класс не замкнут, но [[M]] = [M]|Рис. 1. Замыкание добавляет к <math>M</math> все суперпозиции. Для <math>M=\{x,\overline x\}</math> новых функций нет: <math>M=[M]</math>, класс замкнут. Для <math>M=\{\overline x\}</math> появляется <math>x</math>, так как <math>\overline{\overline x}=x</math>, поэтому <math>M\neq[M]</math>, а второе замыкание уже ничего не меняет.]]

Пусть $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].$

{{Замечание
|content=Заметим, что для доказательства замкнутости некоторого класса функций $\mathfrak M$ достаточно показать, что любая суперпозиция ранга 1 функций из $\mathfrak M$ лежит в $\mathfrak M$.
}}
Обозначим множество суперпозиций ранга $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.
С учетом определения замкнутости можно дать еще одно альтернативное определение полноты.
{{Определение
|definition=
Система функций $\mathcal P\subseteq P_2$ {{---}} полная, если $[\mathcal P] = P_2$.
}}

Конспект: [[Дискретная математика]]

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

СВ: Новая страница: «{{Определение |definition= Система функций $\mathcal P\subseteq P_2$ называется полной, если любую функци...»