WikiSort.ru - Не сортированное

Основные классы функций: ${\displaystyle S,M,L,T_{0},T_{1}}$

• Функция ${\displaystyle f(x_{1},x_{2},\ldots ,x_{n})}$ называется сохраняющей ноль, если ${\displaystyle f(0,0,\ldots ,0)=0}$ . Обозначают, что ${\displaystyle f\in T_{0}}$ .
• Функция ${\displaystyle f(x_{1},x_{2},\ldots ,x_{n})}$ называется сохраняющей единицу, если ${\displaystyle f(1,1,\ldots ,1)=1}$ . Обозначают, что ${\displaystyle f\in T_{1}}$ .
• Функция называется самодвойственной, если на противоположных наборах она принимает противоположные значения, то есть для самодвойственной функции ${\displaystyle f(x_{1},x_{2},\dots ,x_{n})}$ выполняется тождество ${\displaystyle f(x_{1},x_{2},\dots ,x_{n})={\overline {f({\bar {x}}_{1},{\bar {x}}_{2},\dots ,{\bar {x}}_{n})}}}$ . Обозначают, что ${\displaystyle f\in S}$ .
• Функция называется монотонной: ${\displaystyle (\beta _{1},\beta _{2},\ldots ,\beta _{n})\geq (\alpha _{1},\alpha _{2},\ldots ,\alpha _{n})\Rightarrow f(\beta _{1},\beta _{2},\ldots ,\beta _{n})\geq f(\alpha _{1},\alpha _{2},\ldots ,\alpha _{n})}$ . Обозначают, что ${\displaystyle f\in M}$ .
  • ${\displaystyle (\beta _{1},\beta _{2},\ldots ,\beta _{n})\geq (\alpha _{1},\alpha _{2},\ldots ,\alpha _{n})\Leftrightarrow \forall i(\beta _{i}\geq \alpha _{i})}$
• Функция называется линейной, когда её можно представить полиномом Жегалкина первой степени, то есть ${\displaystyle f(x_{1},x_{2},\ldots ,x_{n})=\alpha _{0}\oplus \alpha _{1}x_{1}\oplus \alpha _{2}x_{2}\oplus \ldots \oplus \alpha _{n}x_{n};}$ ${\displaystyle \alpha _{0},\alpha _{i}\in {0,1}(i\in {\overline {1,n}})}$ . Обозначают, что ${\displaystyle f\in L}$ .

Теорема о замкнутости основных классов функций

Отметим, что ни один из замкнутых классов ${\displaystyle S,M,L,T_{0},T_{1}}$ целиком не содержится в объединении остальных четырёх. Это вытекает из следующих соотношений:

1. ${\displaystyle \{{\bar {x}},xy\oplus xz\oplus yz\}\subset S\setminus (M\cup L\cup T_{0}\cup T_{1})}$
2. ${\displaystyle \{0,1,x\lor y\}\subset M\setminus (S\cup L\cup T_{0}\cup T_{1})}$
3. ${\displaystyle \{1,x\oplus y\}\subset L\setminus (S\cup M\cup T_{0}\cup T_{1})}$
4. ${\displaystyle \{x\oplus y,xy\}\subset T_{0}\setminus (S\cup M\cup L\cup T_{1})}$
5. ${\displaystyle \{x\oplus y\oplus 1,x\lor y\}\subset T_{1}\setminus (S\cup M\cup L\cup T_{0})}$

Имея функцию, не сохраняющую 0, получим инвертор или константу 1

Рассмотрим функцию, не принадлежащую классу Т₀. Для неё

${\displaystyle f(0,0,...,0)=1.}$

Эта функция может принадлежать, а может не принадлежать классу Т₁.

• В первом случае ${\displaystyle f(1,1,...,1)=1,}$ тогда ${\displaystyle f(x,x,...,x)=1,}$ и мы имеем константу единицы.
• Во втором случае ${\displaystyle f(1,1,...,1)=0,}$ тогда ${\displaystyle f(x,x,...,x)={\overline {x}},}$ и мы имеем инвертор.

Имея функцию, не сохраняющую 1, получим инвертор или константу 0

Рассмотрим функцию, не принадлежащую классу Т₁. Для неё

${\displaystyle f(1,1,...,1)=0.}$

Эта функция может принадлежать, а может не принадлежать классу Т₀.

• В первом случае ${\displaystyle f(0,0,...,0)=0,}$ тогда ${\displaystyle f(x,x,...,x)=0,}$ и мы имеем константу нуля.
• Во втором случае ${\displaystyle f(0,0,...,0)=1,}$ тогда ${\displaystyle f(x,x,...,x)={\overline {x}},}$ и мы имеем инвертор.

Имея инвертор и несамодвойственную функцию, получим одну из констант

Рассмотрим функцию, не принадлежащую классу S самодвойственных функций. Для неё найдётся такой набор входных переменных X, что

${\displaystyle f(x_{1},x_{2},...,x_{n})=f({\overline {x}}_{1},{\overline {x}}_{2},...,{\overline {x}}_{n}).}$

Пусть, например, ${\displaystyle f(0,1,0)=f(1,0,1)=1,}$ тогда ${\displaystyle f(x,{\overline {x}},x)=1}$ и мы имеем константу 1.

Аналогично, если, например, ${\displaystyle f(0,0,0,1)=f(1,1,1,0)=0,}$ тогда ${\displaystyle f(x,x,x,{\overline {x}})=0}$ и мы имеем константу 0.

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

Имея инвертор и одну из констант, получим другую константу

Если в одном из вышеперечисленных случаев мы получили инвертор и одну из констант, вторую константу получим с помощью инвертора: ${\displaystyle {\overline {0}}=1}$ или ${\displaystyle {\overline {1}}=0.}$

Имея немонотонную функцию и обе константы, получим инвертор

Для немонотонной функции обязательно найдётся такой набор входных переменных, что

${\displaystyle f(x_{1},x_{2},...,0,...,x_{n})=1}$ и

${\displaystyle f(x_{1},x_{2},...,1,...,x_{n})=0.}$

Пусть, например, ${\displaystyle f(1,1,0)=0}$ и ${\displaystyle f(1,0,0)=1}$ . Тогда ${\displaystyle f(1,x,0)={\overline {x}}}$ .

В любом случае, имея немонотонную функцию и обе константы, мы можем получить инвертор.

Имеем инвертор и обе константы

В предыдущих подразделах мы перебрали все возможные варианты (см. рисунок) и пришли к выводу, что имея функции, не принадлежащие классам Т₀, Т₁, S и M, мы всегда можем различными способами получить инвертор и обе константы.

Имея нелинейную функцию, инвертор и константу 1, получим конъюнкцию

Нелинейная функция по определению имеет в полиноме Жегалкина хотя бы один член, содержащий конъюнкцию нескольких переменных. Пусть, например, имеется некоторая нелинейная функция

${\displaystyle f(x_{1},x_{2},x_{3},x_{4},x_{5})=1\oplus x_{1}\oplus x_{1}x_{2}x_{3}\oplus x_{2}x_{3}x_{4}\oplus x_{2}x_{3}x_{5}\oplus x_{2}x_{3}x_{4}x_{5}.}$

Зададимся целью построить на её основе конъюнкцию ${\displaystyle c(x_{1},x_{2})=x_{1}x_{2}.}$

Присвоим переменным ${\displaystyle x_{3},x_{4},x_{5}}$ значения 1, получим:

${\displaystyle f(x_{1},x_{2},1,1,1)=1\oplus x_{1}\oplus x_{1}x_{2}\oplus x_{2}\oplus x_{2}\oplus x_{2}=1\oplus x_{1}\oplus x_{1}x_{2}\oplus x_{2}.}$

Очевидно, что в общем случае после такого преобразования получится функция вида

${\displaystyle f(x_{1},x_{2},1,1,...,1)=x_{1}x_{2}[\oplus x_{1}][\oplus x_{2}][\oplus 1],}$

где квадратные скобки означают, что выделенный ими член может присутствовать в окончательном выражении, а может и нет.

В простейшем случае при отсутствии других членов сразу получаем конъюнкцию: :${\displaystyle f(x_{1},x_{2},1,1,...,1)=x_{1}x_{2}.}$

Рассмотрим другие варианты.

• ${\displaystyle x_{1}x_{2}\oplus x_{1}=x_{1}{\overline {x}}_{2};}$
• ${\displaystyle x_{1}x_{2}\oplus x_{2}={\overline {x}}_{1}x_{2};}$
• ${\displaystyle x_{1}x_{2}\oplus x_{1}\oplus x_{2}={\overline {{\overline {x}}_{1}{\overline {x}}}}_{2}.}$
• ${\displaystyle x_{1}x_{2}\oplus 1={\overline {x_{1}x}}_{2};}$ .
• ${\displaystyle x_{1}x_{2}\oplus x_{1}\oplus 1={\overline {x_{1}{\overline {x}}}}_{2};}$
• ${\displaystyle x_{1}x_{2}\oplus x_{2}\oplus 1={\overline {{\overline {x}}_{1}x}}_{2};}$
• ${\displaystyle x_{1}x_{2}\oplus x_{1}\oplus x_{2}\oplus 1={\overline {x}}_{1}{\overline {x}}_{2}.}$

Любое из этих выражений, используя инвертор, можно привести к конъюнкции.

Таким образом, имея нелинейную функцию, инвертор и константу 1 всегда можно получить конъюнкцию.

Имея конъюнкцию и инвертор, получим дизъюнкцию

Имея инвертор и конъюнкцию, всегда можно получить дизъюнкцию:

${\displaystyle x_{1}+x_{2}={\overline {{\overline {x}}_{1}{\overline {x}}}}_{2}.}$

• Теорема доказана.

Доказательство

1) Докажем, что из любой полной системы функций можно выделить полную подсистему, состоящую не более чем из четырёх функций.

Согласно критерию Поста, в полной системе должны присутствовать пять функций:

${\displaystyle f_{0}\not \in T_{0};f_{1}\not \in T_{1};f_{S}\not \in S;f_{M}\not \in M;f_{L}\not \in L.}$

Рассмотрим функцию ${\displaystyle f_{0}}$ . Возможны два случая:

• ${\displaystyle f_{0}\in T_{1},}$ тогда : ${\displaystyle f_{0}\not \in S}$ и система ${\displaystyle [f_{0},f_{1},f_{M},f_{L}]}$ полна.
• ${\displaystyle f_{0}\not \in T_{1},}$ тогда : ${\displaystyle f_{0}\not \in M,T_{1}}$ и система ${\displaystyle [f_{0},f_{S},f_{L}]}$ полна.

2) Покажем, что существует базис из четырёх функций. Рассмотрим систему функций ${\displaystyle \{0,1,x\cdot y,x\oplus y\oplus z\}}$ . Эта система полна:

${\displaystyle 0\not \in T_{1},S;1\not \in T_{0};x\cdot y\not \in L;x\oplus y\oplus z\not \in M.}$

Однако ни одна его подсистема не полна:

• ${\displaystyle \{0,1,x\cdot y\}\subseteq M;}$
• ${\displaystyle \{0,1,x\oplus y\oplus z\}\subseteq L;}$
• ${\displaystyle \{0,x\cdot y,x\oplus y\oplus z\}\subseteq T_{0};}$
• ${\displaystyle \{1,x\cdot y,x\oplus y\oplus z\}\subseteq T_{1}.}$

Теорема доказана.