СВ в 10:56, 25 октября 2026

2026-10-25T10:56:27Z

← Предыдущая		Версия 10:56, 25 октября 2026
Строка 118:		Строка 118:
	</math>		</math>
	}}		}}

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

СВ в 10:56, 25 октября 2026

2026-10-25T10:56:07Z

← Предыдущая		Версия 10:56, 25 октября 2026
Строка 44:		Строка 44:
	Так как <math>\{\neg, \wedge\}</math> — полная система функций, то и система <math>\mathcal P</math> — полная.		Так как <math>\{\neg, \wedge\}</math> — полная система функций, то и система <math>\mathcal P</math> — полная.
	}}		}}

	{{Пример		{{Пример
	\|content=Требуется проверить на полноту систему функций <math>\mathcal P = \{0, 1, x y, x\oplus y\oplus z\}</math>.		\|content=Требуется проверить на полноту систему функций <math>\mathcal P = \{0, 1, x y, x\oplus y\oplus z\}</math>.
Строка 89:		Строка 88:
	если вычеркнуть в таблице хотя бы одну строку, появится столбец не имеющий минуса.		если вычеркнуть в таблице хотя бы одну строку, появится столбец не имеющий минуса.
	}}		}}

			[[Файл:p45-01-post-table.svg\|frame\|none\|900px\|alt=Таблица Поста для системы из 0, 1, xy и x ⊕ y ⊕ z с отмеченными минусами\|Рис. 1. В каждом столбце <math>T_0, T_1, S, M, L</math> есть «−», поэтому система <math>\mathcal P=\{0,1,xy,x\oplus y\oplus z\}</math> полна. Каждая строка — единственный минус в своём столбце, значит, ни одну функцию убрать нельзя.]]

	{{Определение		{{Определение
Строка 97:		Строка 98:
	# <math>\forall f\in \mathcal B \Rightarrow [\mathcal B\setminus \{f\}]\neq \mathfrak M</math>.</li>		# <math>\forall f\in \mathcal B \Rightarrow [\mathcal B\setminus \{f\}]\neq \mathfrak M</math>.</li>
	}}		}}


	{{Пример		{{Пример
	\|content= Система <math>\{0, 1, xy, x\oplus y\}</math> полная, но базисом <math>P_2</math> не является.		\|content= Система <math>\{0, 1, xy, x\oplus y\}</math> полная, но базисом <math>P_2</math> не является.

St001214: Новая страница: «Классы функций * $T_0$ {{---}} функции, сохраняющие ноль, *
2021-12-10T12:35:10Z

Новая страница: «Классы функций * <math>T_0</math> {{---}} функции, сохраняющие ноль, * <ma...»

Новая страница
Классы функций
* <math>T_0</math> {{---}} [[Функции сохраняющие ноль|функции, сохраняющие ноль]],
* <math>T_1</math> {{---}} [[Функции сохраняющие единицу|функции, сохраняющие единицу]],
* <math>S</math> {{---}} [[Самодвойственные функции|самодвойственные функции]],
* <math>M</math> {{---}} [[Монотонные функции|монотонные функции]],
* <math>L</math> {{---}} [[Линейные функции|линейные функции]].

{{Теорема
|author= Теорема Поста
|statement= Для полноты системы функций <math>\mathcal P\subseteq P_2</math> необходимо и достаточно, чтобы <math>\mathcal P</math> не лежал полностью
ни в одном из классов <math>T_0</math>, <math>T_1</math>, <math>S</math>, <math>M</math>, <math>L</math>:
<math>\mathcal P\not \subseteq T_0</math>, <math>\mathcal P\not \subseteq T_1</math>, <math>\mathcal P\not \subseteq S</math>, <math>\mathcal P\not \subseteq M</math>, <math>\mathcal P\not \subseteq L</math>.

|proof= '''Необходимость.''' Если система функций <math>\mathcal P</math> лежит полностью
в одном из классов <math>R\in\{T_0, T_1, S, M, L\}</math>, то, поскольку все эти классы
замкнуты и не совпадают с <math>P_2</math>, <math>[\mathcal P]\subseteq [R]\neq P_2</math>. Тогда
система <math>\mathcal P</math> — не является полной.

'''Достаточность.'''
Пусть <math>f_0, f_1, f_S, f_M, f_L\in\mathcal P</math> такие функции, что
<math>f_0\notin T_0</math>,
<math>f_1\notin T_1</math>,
<math>f_S\notin S</math>,
<math>f_M\notin M</math>,
<math>f_L\notin L</math> (некоторые из функций могут совпадать).
Проведем доказательство в несколько этапов.

1. Покажем, что с помощью <math>f_0</math>, <math>f_1</math>, <math>f_S</math> можно получить 0 и 1.

1.1. Пусть <math>f_0(1,...,1)=1</math>.
Пусть <math>\varphi(x) = f_0(x,...,x)</math>. Тогда <math>\varphi(0) = \varphi(1) = 1</math>.
Значит <math>\varphi(x) = 1</math> и, имея единицу, можно получить вторую константу <math>0=f_1(1,...,1)</math>.

1.2. Пусть теперь <math>f_0(1,...,1)=0</math>.
Тогда <math>\varphi(x) = f_0(x,...,x) = \overline x</math>.
Подставляя в <math>f_S</math> <math>x</math> и <math>\overline x</math> по лемме о несамодвойственной функции
получаем константу <math>0</math> или <math>1</math> и с помощью <math>\overline x</math> получаем вторую константу.

2. По лемме о немонотонной функции, подставляя константы в <math>f_M</math> можно получить <math>\neg x</math>.

3. Используя <math>f_L</math>, константы и <math>\neg x</math>, по лемме о нелинейной функции можно
получить <math>x\wedge y</math>.

Так как <math>\{\neg, \wedge\}</math> — полная система функций, то и система <math>\mathcal P</math> — полная.
}}

{{Пример
|content=Требуется проверить на полноту систему функций <math>\mathcal P = \{0, 1, x y, x\oplus y\oplus z\}</math>.

Рассмотрим принадлежность функций <math>\mathcal P</math> классам <math>T_0</math>, <math>T_1</math>, <math>S</math>, <math>M</math>, <math>L</math> и заполним таблицу.

<math>
\begin{array}{|c|c|c|c|c|c|}
\hline
& T_0 & T_1 & S & M & L\\
\hline
0 & + & - & - & + & + \\
\hline
1 & - & + & - & + & + \\
\hline
x y & + & + & - & + & - \\
\hline
x\oplus y \oplus z & + & + & + & - & + \\
\hline
\end{array}
</math>

Рассмотрим, например, проверку функции <math>x\oplus y \oplus z</math>:

a) <math>0\oplus 0 \oplus 0 = 0</math> <math>\Rightarrow</math> <math>x\oplus y \oplus z\in T_0</math>;

b) <math>1\oplus 1 \oplus 1 = 1</math> <math>\Rightarrow</math> <math>x\oplus y \oplus z\in T_1</math>;

c) <math>\overline{\overline x \oplus \overline y \oplus \overline z} =
1 \oplus (1\oplus x) \oplus (1\oplus y) \oplus (1 \oplus z) =
x\oplus y \oplus z</math> <math>\Rightarrow</math> <math>x\oplus y \oplus z\in S</math>;

d) <math>(1,0,0)\prec (1,1,0)</math>, но
<math>1 = 1\oplus 0 \oplus 0 \gt 1\oplus 1 \oplus 0 = 0</math>
<math>\Rightarrow</math> <math>x\oplus y \oplus z\notin M</math>;

e) Очевидно, функция является линейной: <math>x\oplus y \oplus z\in L</math>.

Теперь, заполнив и проанализировав таблицу, можно убедиться, что система функций
<math>\mathcal P</math> является полной, так как в каждом столбце, соответствующем одному
из классов присутствует хотя бы один минус.

В то же время ни одно подмножество <math>\mathcal P</math> полной системой не является, поскольку,
если вычеркнуть в таблице хотя бы одну строку, появится столбец не имеющий минуса.
}}

{{Определение
|definition= Пусть <math>\mathfrak M</math> — замкнутый класс функций.
Пусть <math>\mathcal B\subseteq \mathfrak M</math>.
<math>\mathcal B</math> называется базисом класса <math>\mathfrak M</math>, если
# <math>[\mathcal B] = \mathfrak M</math>;</li>
# <math>\forall f\in \mathcal B \Rightarrow [\mathcal B\setminus \{f\}]\neq \mathfrak M</math>.</li>
}}

{{Пример
|content= Система <math>\{0, 1, xy, x\oplus y\}</math> полная, но базисом <math>P_2</math> не является.
Базисом <math>P_2</math> будет ее подсистема <math>\{1, xy, x\oplus y\}</math>.

<math>
\begin{array}{|c|c|c|c|c|c|}
\hline
& T_0 & T_1 & S & M & L\\
\hline
0 & + & - & - & + & + \\
\hline
1 & - & + & - & + & + \\
\hline
x y & + & + & - & + & - \\
\hline
x\oplus y & + & - & - & - & + \\
\hline
\end{array}
</math>
}}

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

СВ в 10:56, 25 октября 2026

СВ в 10:56, 25 октября 2026