\documentclass[11pt,reqno]{amsart}
\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{xcolor}
\usepackage[colorlinks]{hyperref}


\usepackage{titlesec}
\titlespacing{\section}{0pt}{2.5ex}{1.5ex}
\titlespacing{\subsection}{0pt}{1.5ex}{1ex}
\titlespacing{\subsubsection}{0pt}{1.5ex}{1ex}
\titleformat{\section}{\large\bfseries\centering}{\thesection}{1em}{}
\titleformat{\subsection}[runin]{\bfseries}{\thesubsection.}{0.5em}{}[.\mbox{\ }]
\titleformat{\subsubsection}[runin]{\bfseries}{\thesubsubsection.}{0.4em}{}[.\mbox{\ }]



%%%%%---------- ORCiD
\newcommand\orcidicon[1]{\href{https://orcid.org/#1}{\includegraphics[scale=0.02]{orcid.pdf}}}

\def\udcs{519.714} %Здесь автор определяет УДК своей работы
\def\mscs{03D15} %Здесь автор определяет классификаторы AMS своей работы
\setcounter{page}{144}

\newtheorem{lemma}{Лемма}
\newtheorem{theorem}{Теорема}
\newtheorem{definition}{Определение}
\newtheorem{corollary}{Следствие}
\newtheorem{proposition}{Предложение}


\definecolor{myblue}{rgb}{0.03, 0.27, 0.79}

\hypersetup{linkcolor=blue,filecolor=black,urlcolor=blue, citecolor=blue}

\def\logo{\textcolor{blue}{{\bf\Huge S\raisebox{0.2ex}{\hspace{0.55ex}\raisebox{0.05ex}e\hspace{-1.65ex}$\bigcirc$}MR}}}

\def\semrtop
     {
  \vbox{
     \noindent\logo \hspace{-3mm}  \parbox{12cm}{     \begin{center}
     {\LARGE \textsf{СИБИРСКИЕ ЭЛЕКТРОННЫЕ}} \\[2mm]
     {\LARGE \textsf{МАТЕМАТИЧЕСКИЕ ИЗВЕСТИЯ}} \\[2mm]
     {\Large \textsf{Siberian Electronic Mathematical Reports}} \\[1mm]
     {\Large\tt{\textcolor{blue}{http://semr.math.nsc.ru}}}\\[1mm]
     \raisebox{1ex}{ISSN 1813-3304 }
     \vspace*{-3mm}
%     {\small Институт математики им. С.Л.Соболева СО РАН}\\[-1mm]
%     {\small Sobolev Institute of Mathematics SB RAS}
     \end{center}
}
     \vspace{-1mm}
     \noindent
      \begin{tabular}{c}
     \hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!} \\
     \hline\hline
     \end{tabular}

     \vspace{3mm}
     {\flushleft\it Том 20, № 2, стр. 144--145 (2023) \hspace{\fill}{\rm\small УДК \udcs \hspace{-4mm}}}
     \newline
        {\rm\small \textcolor{blue}{https://doi.org/10.33048/semi.2023.20.???}}\hphantom{aaaaaaaaaaaaaaaaaaaaaaaa\;}{\rm\small MSC\ \ \mscs }
  }%\vbox
}



\begin{document}
\renewcommand{\refname}{References}


\thispagestyle{empty}

\title[\sc О свойстве одного класса формул]{\large О характеристическом свойстве одного класса нормализованных формул, реализующих линейные булевы функции}
\author[К.Л. РЫЧКОВ]{{\bf \large \textsc{К.Л. Рычков}}\protect\orcidicon{0000-0001-8827-2630}\\ \\
\textit{Представлено} \textsc{П.П. Петровым}
%\textit{(заполняется редактором)}
}%
\address{Konstantin Leonidovich Rychkov  % Контактные данные всех авторов и место работы указываются только на английском языке
\newline\hphantom{iii} Sobolev Institute of Mathematics,
\newline\hphantom{iii} pr. Koptyuga, 4,
\newline\hphantom{iii} 630090, Novosibirsk, Russia}%
\email{\textcolor{blue}{rychkov@math.nsc.ru}}%

\thanks{\sc Rychkov, K.L.,
On the characteristic property of one class of normalized formulas
calculating linear Boolean functions}
\thanks{\copyright \ 2024 Рычков К.Л}
\thanks{\rm Работа выполнена в рамках государственного задания ИМ СО РАН, тема
FWNF-2022-0017}
\thanks{\it Поступила 1 января 2023 г., опубликована 31 декабря 2023 г.}%


\semrtop \vspace{1cm}
\maketitle {\small
\begin{quote}
\noindent{\bf Abstract:} By means of a modification of the method
proposed by S. V. Yablonsky for constructing an economical
(hypothetically minimal) normalized formula ($\Pi$-circuit) that
calculates a given linear Boolean function, a whole class of similar
formulas was constructed -- the class of so-called optimal perfect
normalized formulas. Presumably it is the class of all minimal
normalized formulas that compute this function. To prove this
conjecture, we consider extending this class to the class of perfect
normalized formulas that also compute the same function. It is
established that a normalized formula is perfect if and only if it
has a perfect representation on the own rectangle of the specified
function.\medskip

\noindent{\bf Keywords:} boolean functions, $\pi$-circuits,
normalized formulas, lower bounds on complexity, formula
representations, $\Pi$-partitions.
 \end{quote}
}

\bigskip

%%------ 1.
\section{Введение}

Нормализованной формулой называют формулу в базисе
$\{\vee,\wedge,^-\}$, в которой отрицания встречаются только над
переменными. Для определённости полагаем, что переменными любой
нормализованной формулы являются некоторые буквы из множества
$\{x_1,x_2,x_3,\dots\}$. Отрицание $\overline{x}_i$ переменной $x_i$
обычно обозначают через  $x_i^0$, а саму переменную -- через
$x_i^1$. В этом смысле нам будет удобно понимать {\it
нормализованную формулу} как формулу в базисе $\{\vee,\wedge\}$,
переменные которой принадлежат множеству литералов
$\mathfrak{X}=\{x_i^\delta\mid
i\in\{1,2,3,\dots\},\delta\in\{0,1\}\}$.

{\it Сложность} $\mathrm{L}(G)$ нормализованной формулы $G$ это
число вхождений в неё литералов из $\mathfrak{X}$.

Через $\mathfrak{N}$ обозначим множество всех нормализованных
формул.

В дальнейшем нормализованные формулы будем называть просто {\it
формулами}.

По определению равенство $G=F$ для $G,F\in\mathfrak{N}$ означает,
что $G$ и $F$ это одна и та же формула.

{\it Линейной булевой функцией с множеством образующих}
$Z\subseteq\{1,\dots,n\}$, $Z\neq\emptyset$, и {\it показателем}
$\delta\in\{0,1\}$ называется функция
$$
f_Z^\delta(x_1,\dots,x_n)=\bigoplus\nolimits_{i\in Z}
x_i\oplus\delta\oplus1. \ \footnote{$\oplus$ -- сумма по модулю 2.}
$$
Булеву функцию будем называть просто {\it линейной}, если она
является одной из функций $f_Z^\delta$.

Наша сверхзадача заключается в том, чтобы описать класс всех
реализующих функцию $f_Z^\delta$ {\it минимальных} (т. е. имеющих
наименьшую сложность) формул. С этой целью определим следующие два
класса реализующих $f_Z^\delta$ формул: класс {\it оптимальных
совершенных формул} $\mathbb{O}^\delta_Z$ и класс {\it совершенных
формул} $\mathbb{P}^\delta_Z$.

Для произвольных $\mathbb{K}_1,\mathbb{K}_2\subseteq\mathfrak{N}$
классы формул $\mathbb{K}_1\wedge\mathbb{K}_2$ и
$\mathbb{K}_1\vee\mathbb{K}_2$ определим следующими равенствами:
$$
\mathbb{K}_1\wedge\mathbb{K}_2=\{(F_1\wedge F_2) \mid
F_1\in\mathbb{K}_1,F_2\in\mathbb{K}_2\},
$$
$$
\mathbb{K}_1\vee\mathbb{K}_2=\{(F_1\vee F_2) \mid
F_1\in\mathbb{K}_1,F_2\in\mathbb{K}_2\}.
$$

Формулу $G\in\mathfrak{N}$ назовём {\it коммутативным эквивалентом}
формулы $F\in\mathfrak{N}$, если для некоторых двух формул
$H,T\in\mathfrak{N}$ справедливы равенства $F=(H\vee T)$, $G=(T\vee
H)$ или равенства $F=(H\wedge T)$, $G=(T\wedge H)$.

Формулу $G\in\mathfrak{N}$ назовём {\it правым ассоциативным
эквивалентом} формулы $F\in\mathfrak{N}$, а формулу $F$ -- {\it
левым ассоциативным эквивалентом} формулы $G$, если для некоторых
$H,T,K\in\mathfrak{N}$ справедливы равенства $F=((H\vee T)\vee K)$,
$G=(H\vee (T\vee K))$ или равенства $F=((H\wedge T)\wedge K)$,
$G=(H\wedge (T\wedge K))$.

Формулу $G\in\mathfrak{N}$ назовём {\it ассоциативным эквивалентом}
формулы $F\in\mathfrak{N}$, если $G$ является либо правым либо левым
ассоциативным эквивалентом $F$.

{\it Подформулой} формулы $F\in\mathfrak{N}$ мы называем то, что
обычно называют вхождением подформулы в эту формулу. Таким образом
{\it подформула} формулы $F\in\mathfrak{N}$ это некоторая формула
$F'\in\mathfrak{N}$ вместе с местом её расположения в $F$ (т. е.
вместе с множеством номеров подряд идущих разрядов $F$, в которых
записана $F'$).

{\it Коммутативным преобразованием} формулы $F\in\mathfrak{N}$
назовём замену некоторой подформулы этой формулы на её коммутативный
эквивалент.

{\it Ассоциативным преобразованием} формулы $F\in\mathfrak{N}$
назовём замену некоторой подформулы этой формулы на её ассоциативный
эквивалент.

По определению формула $G\in\mathfrak{N}$ $\Pi$-{\it эквивалентна}
формуле $F\in\mathfrak{N}$, если $G$ можно получить из $F$
посредством некоторой цепочки коммутативных и ассоциативных
преобразований или если $G=F$.

Очевидно отношение $\Pi$-эквивалентности формул действительно
является отношением эквивалентности и для любых двух
$\Pi$-эквивалентных формул $F,G\in\mathfrak{N}$ справедливо
равенство $\mathrm{L}(F)=\mathrm{L}(G)$.

$\Pi$-{\it замыканием} $\overline{\mathbb{S}}$ множества формул
$\mathbb{S}\subseteq\mathfrak{N}$ назовём класс формул, состоящий из
всех формул множества $\mathbb{S}$ и из всех им $\Pi$-эквивалентных
формул.

{\it Замкнутым относительно} $\Pi$-{\it эквивалентности} классом
формул называется такое множество формул
$\mathbb{S}\subseteq\mathfrak{N}$, что
$\mathbb{S}=\overline{\mathbb{S}}$.

Теперь сформулируем индуктивное определение классов формул
$\mathbb{O}^\delta_Z$ и $\mathbb{P}^\delta_Z$.

а) При $|Z|=1$ для любых $Z\subseteq\{1,2,3,\dots\}$ и
$\delta\in\{0,1\}$ классы формул $\mathbb{O}^\delta_Z$ и
$\mathbb{P}^\delta_Z$ определяются равенством
$\mathbb{O}^\delta_Z=\mathbb{P}^\delta_Z=\{x^\delta_i\}$, $i\in Z$,
т. е. они состоят из единственной однобуквенной формулы
$x^\delta_i$.

б) Пусть $m>1$ и при $1\leq|Z|\leq m-1$ для любых $Z\subseteq
\{1,2,3,\dots\}$ и $\delta\in\{0,1\}$ классы формул
$\mathbb{O}^\delta_Z$ и $\mathbb{P}^\delta_Z$ уже определены. Тогда
для любых таких $I,J\subseteq\{1,2,3,\dots\}$, что $1\leq|I|,|J|\leq
m-1$, и любого $\delta\in\{0,1\}$ определены классы формул
$$
\mathbb{OL}^\delta_\vee(I,J)=
(\mathbb{O}^0_I\wedge\mathbb{O}^\delta_J)\vee(\mathbb{O}^1_I\wedge\mathbb{O}^{\delta\oplus1}_J),
\ \ \ \ \ \mathbb{OL}^\delta_\wedge(I,J)=
(\mathbb{O}^0_I\vee\mathbb{O}^{\delta\oplus1}_J)\wedge(\mathbb{O}^1_I\vee\mathbb{O}^\delta_J),
$$
$$
\mathbb{PL}^\delta_\vee(I,J)=
(\mathbb{P}^0_I\wedge\mathbb{P}^\delta_J)\vee(\mathbb{P}^1_I\wedge\mathbb{P}^{\delta\oplus1}_J),
\ \ \ \ \ \mathbb{PL}^\delta_\wedge(I,J)=
(\mathbb{P}^0_I\vee\mathbb{P}^{\delta\oplus1}_J)\wedge(\mathbb{P}^1_I\vee\mathbb{P}^\delta_J),
$$
Поэтому при вышеуказанных $I$, $J$ и $\delta$ определены также и
классы формул
$$
\mathbb{O}^\delta_\vee(I,J)=\overline{\mathbb{OL}^\delta_\vee(I,J)},
\ \ \ \ \ \ \ \ \
\mathbb{O}^\delta_\wedge(I,J)=\overline{\mathbb{OL}^\delta_\wedge(I,J)},
$$
$$
\mathbb{P}^\delta_\vee(I,J)=\overline{\mathbb{PL}^\delta_\vee(I,J)},
\ \ \ \ \ \ \ \ \
\mathbb{P}^\delta_\wedge(I,J)=\overline{\mathbb{PL}^\delta_\wedge(I,J)}.
$$
При $|Z|=m$ для любых $Z\subseteq \{1,2,3,\dots\}$ и
$\delta\in\{0,1\}$ классы формул $\mathbb{O}^\delta_Z$ и
$\mathbb{P}^\delta_Z$ определяются равенствами
$$
\mathbb{O}^\delta_Z=\bigcup\limits_{\substack{I \\ I\subseteq Z \\
2^{\lfloor\log m\rfloor-1}\leq|I|, |Z\setminus I|\leq 2^{\lfloor\log
m\rfloor}}}\left(\mathbb{O}^\delta_\vee(I,Z\setminus
I)\cup\mathbb{O}^\delta_\wedge(I,Z\setminus I)\right), \
\footnote{$\lfloor k\rfloor$ -- наибольшее целое непревосходящее
$k$.}
$$
$$
\mathbb{P}^\delta_Z=\bigcup\limits_{\substack{I \\ \emptyset\subset
I\subset Z}}\left(\mathbb{P}^\delta_\vee(I,Z\setminus
I)\cup\mathbb{P}^\delta_\wedge(I,Z\setminus I)\right).
$$

Очевидная индукция по $|Z|$ показывает, что все формулы из класса
$\mathbb{P}^\delta_Z$ реализуют функцию $f_Z^\delta$. Кроме того
также индукцией по $|Z|$ нетрудно установить, что класс
$\mathbb{O}^\delta_Z$ является множеством всех формул наименьшей
сложности из класса $\mathbb{P}^\delta_Z$, и при $|Z|=m$ эта
сложность равна
$m^2+(m-2^{\lfloor\log_2m\rfloor})m-2(m-2^{\lfloor\log_2m\rfloor})^2$.

Заметим, что классы $\mathbb{O}^\delta_Z$ и $\mathbb{P}^\delta_Z$ по
определению являются объединениями замкнутых относительно
$\Pi$-эквивалентности классов формул и, значит, сами являются
замкнутыми относительно $\Pi$-эквивалентности классами формул.

Заметим также, что приведённое определение классов
$\mathbb{O}^\delta_Z$ и $\mathbb{P}^\delta_Z$ по сути является
некоторой естественной модификацией метода С. В. Яблонского \cite{1}
построения реализующей функцию $f_Z^\delta$ $\Pi$-схемы. При этом
построенная самим С. В. Яблонским формула ($\Pi$-схема) принадлежит
классу $\mathbb{O}^\delta_Z$.

Из нижних оценок сложности \cite{2,3,4,5,6} следует, что при $|Z|$
равном целой степени двойки и при $|Z|=3,5,6,7$ все формулы класса
$\mathbb{O}^\delta_Z$ являются минимальными.




Настоящая статья является третьим шагом доказательства гипотезы о
том, что при указанных значениях $|Z|$ классом $\mathbb{O}^\delta_Z$
исчерпываются все реализующие $f_Z^\delta$ минимальные формулы.
Основным результатом статьи является необходимое для этого
доказательства приведённое ниже характеристическое свойство формул
класса $\mathbb{P}^\delta_Z$. Первые два шага были сделаны в статьях
\cite{7,8}.



Учитывая, что цель работы -- приблизиться к полному описанию
минимальных формул для линейной функции, уместно упомянуть, что Ю.
А. Комбаров в \cite{9} получил подобное описание в классе схем из
функциональных элементов в базисе $\{\vee,\wedge,^-\}$.



%%------ 2.
\section{Основные определения и формулировка результата}

Напомним некоторые определения из статей \cite{7,8}.

Множество двоичных наборов
$$
\mathrm{B}^n=\{\alpha=(\alpha_1, \ \dots \ \alpha_i, \ \dots \
\alpha_n) \mid \alpha_i\in\{0,1\}, 1\leq i\leq n\}
$$
называется $n$-{\it мерным единичным кубом} или {\it кубом}
$\mathrm{B}^n$.

Для наборов с единственной единичной компонентой введём следующие
обозначения
$$
\mathbf{e}^1=(1,0, \ \dots \ 0), \ \mathbf{e}^2=(0,1, \ \dots \ 0),
\ \ \ \dots \ \ \ \mathbf{e}^n=(0, \ \dots \ 0,1).
$$

Сумму наборов $\alpha,\beta\in\mathrm{B}^n$ определим равенством
$$
\alpha+\beta=(\alpha_1\oplus\beta_1, \alpha_2\oplus\beta_2, \dots
,\alpha_n\oplus\beta_n).
$$

Пара наборов $(\alpha,\beta)\in\mathrm{B}^n\times\mathrm{B}^n$
называется {\it ребром направления} $i$ куба $\mathrm{B}^n$, если
выполнено равенство $\beta=\alpha+\mathbf{e}^i$. При $\alpha_i=1$
это ребро будем называть {\it отрицательным}, при $\alpha_i=0$ --
{\it положительным}; $i=1, \dots ,n$. Пара наборов
$(\alpha,\beta)\in\mathrm{B}^n\times\mathrm{B}^n$ называется просто
{\it ребром} куба $\mathrm{B}^n$, если она является ребром
направления $i$ для некоторого $i\in\{1, \dots n\}$.

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

Через $\mathrm{R}$ обозначим множество всех рёбер куба
$\mathrm{B}^n$.

Через $\mathrm{R}_i$, $\mathrm{R}_i^0$ и $\mathrm{R}_i^1$ обозначим
множество всех рёбер направления $i$, множество всех отрицательных и
всех положительных рёбер направления $i$ куба $\mathrm{B}^n$
соответственно, $i=1, \dots ,n$.

Непустое подмножество $P\subseteq\mathrm{B}^n\times\mathrm{B}^n$
называется {\it прямоугольным подмножеством} декартова квадрата куба
$\mathrm{B}^n$, если $P=A\times B$ для некоторых
$A,B\subseteq\mathrm{B}^n$. Для краткости будем называть его {\it
прямоугольником размерности} $n$ или просто {\it прямоугольником}.
При этом множества $A$ и $B$ называются соответственно {\it
вертикальной} и {\it горизонтальной сторонами прямоугольника} $P$;
для произвольных $\alpha\in A$ и $\beta\in B$ множества
$\{(\alpha,\gamma)\mid \gamma\in B\}$ и $\{(\gamma,\beta)\mid
\gamma\in A\}$ -- его {\it строкой с индексом $\alpha$} и его {\it
столбцом с индексом $\beta$}; подмножество $D\subseteq P$, которое с
каждой строкой и каждым столбцом этого прямоугольника имеет ровно по
одному общему элементу называется его {\it диагональю}.

Очевидно прямоугольник $P=A\times B$ тогда и только тогда имеет
диагональ, когда $|A|=|B|$, т. е. когда он является {\it квадратом}.

Через $\mathrm{REC}^n$ обозначим множество всех прямоугольников
размерности $n$. Для произвольного прямоугольника
$P\in\mathrm{REC}^n$ через $\mathrm{REC}(P)$ обозначим множество
всех таких $K\in\mathrm{REC}^n$, что $K\subseteq P$.

Прямоугольник $P\in\mathrm{REC}^n$ называется $(i,\delta)$-{\it
центрированным}, если для некоторой его диагонали $D$ выполнено
включение $D\subseteq\mathrm{R}_i^\delta$; и называется {\it
центрированным}, если существуют такие $i\in\{1,\dots,n\}$ и
$\delta\in\{0,1\}$, что $P$ является $(i,\delta)$-центрированным.

Прямоугольник $\mathrm{X}=\mathrm{B}^n\times\mathrm{B}^n$ называется
{\it главным прямоугольником размерности} $n$ или просто {\it
главным прямоугольником}.

Прямоугольники
$$
\mathrm{X}_i^0=\{(\alpha,\beta)\in\mathrm{X}\mid\alpha_i=1,\beta_i=0\}
\ \ {\mbox и} \ \
\mathrm{X}_i^1=\{(\alpha,\beta)\in\mathrm{X}\mid\alpha_i=0,\beta_i=1\}
$$
называются соответственно {\it отрицательной} и {\it положительной
компонентами с номером} $i$ главного прямоугольника $\mathrm{X}$;
$i=1,\dots,n$.

Множество $M\subseteq \mathrm{X}$  называется $(i,\delta)$-{\it
однородным}, если выполнено включение $M\subseteq
\mathrm{X}_i^\delta$; и  называется просто {\it однородным}, если
существуют такие $i\in\{1,\dots,n\}$ и $\delta\in\{0,1\}$, что $M$
является $(i,\delta)$-однородным.



Прямоугольники $P_1,P_2\in\mathrm{REC}^n$ называются {\it
горизонтально соседними}, если вертикальная сторона $P_1$ равна
вертикальной стороне $P_2$ и выполнено равенство $P_1\cap
P_2=\emptyset$; и называются {\it вертикально соседними}, если
горизонтальная сторона $P_1$ равна горизонтальной стороне $P_2$ и
выполнено равенство $P_1\cap P_2=\emptyset$.

Прямоугольники $P_1,P_2\in\mathrm{REC}^n$ называются просто {\it
соседними}, если они являются либо горизонтально, либо вертикально
соседними.


Очевидно для любых двух соседних прямоугольников
$P_1,P_2\in\mathrm{REC}^n$ их объединение является прямоугольником,
т. е. справедливо включение $P_1\cup P_2\in\mathrm{REC}^n$.

{\it Горизонтальным} ({\it вертикальным}) {\it разрезом}
прямоугольника $P\in\mathrm{REC}^n$ называется такая пара
$\{P_1,P_2\}\subseteq\mathrm{REC}^n$ горизонтально (вертикально)
соседних прямоугольников, что $P_1\cup P_2=P$. Эта пара называется
просто {\it разрезом} прямоугольника $P$, если она является либо
горизонтальным либо вертикальным его разрезом. При этом
прямоугольники $P_1$, $P_2$ называются {\it компонентами}
соответствующего разреза.

{\it Разбиением} (конечным) множества $P$ называется, такое
семейство $U=\{Q_1,\dots Q_k\}$ непустых попарно непересекающихся
его подмножеств, что справедливо равенство $Q_1\cup\dots\cup Q_k=P$.
Подмножества $Q_1,\dots Q_k$ называются {\it блоками} этого
разбиения.

Разбиение $U$ прямоугольника $P\in\mathrm{REC}^n$ называется {\it
прямоугольным}, если все его блоки являются прямоугольниками.

{\it Сужением} $U|K$ прямоугольного разбиения $U$ прямоугольника
$P\in\mathrm{REC}^n$ на прямоугольник $K\subseteq P$ называется
множество прямоугольников
$$
U|K=\{Q\cap K\mid Q\in U, \ Q\cap K\neq\emptyset\}.
$$
Если при этом неравенство $Q\cap K\neq\emptyset$ справедливо для
каждого $Q\in U$, то сужение $U|K$ называется {\it строгим}.

 {\it Гиперблоком} прямоугольного разбиения $U$ прямоугольника
$P\in\mathrm{REC}^n$ называется такой прямоугольник
$K\in\mathrm{REC}(P)$, что выполнено включение $U|K\subseteq U$.

{\it Прямоугольным фрагментом} или просто {\it фрагментом}
прямоугольного разбиения $U$ прямоугольника $P\in\mathrm{REC}^n$
называется такое подсемейство блоков $S\subseteq U$, что множество
$\bigcup\nolimits_{Q\in S}Q$ является прямоугольником.

Через $\mathcal{H}(U)$ и $\mathcal{F}(U)$ обозначим множество всех
гиперблоков и всех прямоугольных фрагментов прямоугольного разбиения
$U$ прямоугольника $P\in\mathrm{REC}^n$ соответственно.

Гиперблок $K\in\mathcal{H}(U)$ и прямоугольный фрагмент
$F\in\mathcal{F}(U)$, $F=U|K$, называются {\it соответствующими}
друг другу. Очевидно, это соответствие является взаимно однозначным.

Очевидно сами блоки прямоугольного разбиения $U$ являются его
гиперблоками. Эти гиперблоки  называются {\it элементарными}. Все
остальные гиперблоки $U$ называются {\it составными}. Кроме того сам
прямоугольник $P$ является гиперблоком. Этот гиперблок называется
{\it главным} и обозначается $\widehat{U}$. Отличные от
$\widehat{U}$ гиперблоки $U$ называются {\it неглавными}.

В дальнейшем прямоугольное разбиения $U$ прямоугольника $P$ для
краткости будем также называть просто {\it прямоугольным разбиением}
$U$, имея в виду, что $U$ является прямоугольным разбиением
прямоугольника $\widehat{U}$.

Два гиперблока $P_1,P_2\in\mathcal{H}(U)$ прямоугольного разбиения
$U$ будем называть {\it горизонтально} ({\it вертикально}) {\it
соседними}, если горизонтально (вертикально) соседними являются
прямоугольники $P_1$, $P_2$; и -- просто {\it соседними}, если они
являются либо горизонтально либо вертикально соседними.

Очевидно объединение любых двух соседних гиперблоков
$P_1,P_2\in\mathcal{H}(U)$ прямоугольного разбиения $U$ также
является гиперблоком $U$. Он называется их {\it горизонтальным}
({\it вертикальным}) {\it соединением}, если $P_1$ и $P_2$
горизонтально (вертикально) соседние; или просто -- их {\it
соединением}.

{\it Горизонтальным} ({\it вертикальным}) {\it разрезом гиперблока}
$P\in\mathcal{H}(U)$ прямоугольного разбиения $U$ называется такой
горизонтальный (вертикальный) разрез прямоугольника $P$, что его
компоненты являются гиперблоками $U$. Как горизонтальный так и
вертикальный разрез гиперблока $P$ будем также называть просто {\it
разрезом гиперблока} $P$.


{\it Горизонтальным} ({\it вертикальным}) {\it разрезом
прямоугольного разбиения} $U$ назовём любой горизонтальный
(вертикальный) разрез главного гиперблока $\widehat{U}$ этого
прямоугольного разбиения.



Через $\mathrm{C}_h(P,U)$ и $\mathrm{C}_v(P,U)$ обозначим
соответственно множество всех горизонтальных и множество всех
вертикальных разрезов гиперблока $P$ прямоугольного разбиения $U$.

Через $\mathrm{C}_h(U)$ и $\mathrm{C}_v(U)$ обозначим соответственно
множество всех горизонтальных и множество всех вертикальных разрезов
прямоугольного разбиения $U$.


Гиперблок $P$ прямоугольного разбиения $U$ называется {\it
горизонтально} ({\it вертикально}) {\it разделимым}, если
$\mathrm{C_h}(P,U)\neq\emptyset$ (если
$\mathrm{C_v}(P,U)\neq\emptyset$); в противном случае он называется
{\it горизонтально} ({\it вертикально}) {\it неразделимым}.

Гиперблок прямоугольного разбиения $U$ называется {\it разделимым},
если он либо горизонтально либо вертикально разделим; в противном
случае он называется {\it неразделимым}.

Прямоугольное разбиение называется {\it разделимым}, если каждый его
составной гиперблок является разделимым.

Прямоугольное разбиение называется {\it однородным}, если каждый его
блок является однородным множеством.

$\Pi$-{\it разбиением} называется такое прямоугольное разбиение,
которое является одновременно однородным и разделимым.

$\Pi$-разбиение называется {\it совершенным}, если каждый его блок
является центрированным прямоугольником.

{\it Размерностью} $\Pi$-разбиения назовём размерность его главного
гиперблока.

Через $\Pi^n$ обозначим множество всех $\Pi$-разбиений размерности
$n$.


{\it Класс} $\mathfrak{N}(U)$ {\it порождаемых} $\Pi$-{\it
разбиением} $U\in\Pi^n$ {\it формул} определим, опираясь на
следующее доказанное в \cite{7} утверждение.




%%---Лемма 1.
\begin{lemma}
Для любого прямоугольника $\Phi\in\mathrm{REC}^n$ сужение $U|P$
любого его $\Pi$-разбиения $U$ на любой прямоугольник
$P\subseteq\Phi$ является  $\Pi$-разбиением $P$.
\end{lemma}

Сформулируем индуктивное определение класса $\mathfrak{N}(U)$.

а) При $|U|=1$ класс формул $\mathfrak{N}(U)$ состоит из всех таких
литералов $x_i^\delta$, что единственный блок $Q$ этого разбиения
является $(i,\delta)$-однородным множеством. Другими словами, для
$\Pi$-разбиения вида $U=\{Q\}$ по определению справедливо равенство
$$
\mathfrak{N}(U)=\{x_i^\delta\mid Q\subseteq
\mathrm{X}_i^\delta,i\in\{1,\dots,n\},\delta\in\{0,1\}\}.
$$

б) Пусть $m>1$ и класс формул $\mathfrak{N}(U)$ определён для всех
$U\in\Pi^n$ мощности $|U|\leq m-1$. Определим его для произвольного
$\Pi$-разбиения $U\in\Pi^n$ мощности $|U|=m$.

В силу леммы 1 для каждого горизонтального разреза $\{P_1,P_2\}$
этого $\Pi$-разбиения соответствующие его гиперблокам $P_1$ и $P_2$
прямоугольные фрагменты $U|P_1$ и $U|P_2$ являются
$\Pi$-разбиениями. Поэтому справедливы включения $U|P_1\in\Pi^n$,
$U|P_2\in\Pi^n$ и очевидно выполнены неравенства $|U|P_1|\leq m-1$,
$|U|P_2|\leq m-1$. Следовательно для каждого
$\{P_1,P_2\}\in\mathrm{C}_h(U)$ определены классы формул
$\mathfrak{N}(U|P_1)$ и $\mathfrak{N}(U|P_2)$ а, значит, определены
и классы формул
$$
\mathfrak{M}_\vee(U,P_1,P_2)=\mathfrak{N}(U|P_1)\vee\mathfrak{N}(U|P_2)
 \ \ {\mbox и} \ \
\mathfrak{M}_\vee(U,P_2,P_1)=\mathfrak{N}(U|P_2)\vee\mathfrak{N}(U|P_1).
$$
И точно также для каждого вертикального разреза
$\{P_1,P_2\}\in\mathrm{C}_v(U)$ определены классы формул
$\mathfrak{N}(U|P_1)$ и $\mathfrak{N}(U|P_2)$ а, значит, определены
и классы формул
$$
\mathfrak{M}_\wedge(U,P_1,P_2)=\mathfrak{N}(U|P_1)\wedge\mathfrak{N}(U|P_2)
\ \ {\mbox и} \ \
\mathfrak{M}_\wedge(U,P_2,P_1)=\mathfrak{N}(U|P_2)\wedge\mathfrak{N}(U|P_1).
$$
Поэтому определены классы формул
$$
\mathfrak{N}_\vee(U)= \bigcup\limits_{\{P_1,P_2\}\in\mathrm{C}_h(U)}
\bigl(\mathfrak{M}_\vee(U,P_1,P_2)\cup\mathfrak{M}_\vee(U,P_2,P_1)\bigl),
$$
$$
\mathfrak{N}_\wedge(U)=
\bigcup\limits_{\{P_1,P_2\}\in\mathrm{C}_v(U)}
\bigl(\mathfrak{M}_\wedge(U,P_1,P_2)\cup\mathfrak{M}_\wedge(U,P_2,P_1)\bigl).
$$

Класс формул $\mathfrak{N}(U)$ определяется равенством
$$
\mathfrak{N}(U)=\mathfrak{N}_\vee(U)\cup\mathfrak{N}_\wedge(U).
$$



{\it Представлением формулы} $F\in\mathfrak{N}$ называется любое
такое $\Pi$-разбиение $U\in\Pi^n$, что выполнено включение
$F\in\mathfrak{N}(U)$.

Заметим, что это определение в силу теоремы 17 статьи \cite{7}
эквивалентно определению представления формулы, приведенному в
\cite{7}.

{\it Совершенным представлением формулы} $F\in\mathfrak{N}$
называется любое такое представление $U$ этой формулы, что $U$
является совершенным $\Pi$-разбиением.

{\it Представлением формулы} $F\in\mathfrak{N}$ {\it на
прямоугольнике} $P\in\mathrm{REC}^n$ называется любое такое
представление $U$ этой формулы, что $U$ является $\Pi$-разбиением
$P$.



{\it Собственным прямоугольником} нетривиальной
($f\neq\mathrm{const}$) булевой функции $f$ называется прямоугольник
$f^{-1}(0)\times f^{-1}(1)$.


Основным результатом настоящей статьи является следующая теорема.



%%---Теорема 1.
\begin{theorem}
Для любого целого $n\geq1$ и любых $\emptyset\subset Z\subseteq
\{1,\dots,n\}$ и $\delta\in\{0,1\}$ формула $F\in\mathfrak{N}$ тогда
и только тогда принадлежит классу $\mathbb{P}^\delta_Z$, когда она
имеет совершенное представление на собственном прямоугольнике
функции $f^\delta_Z(x_1,\dots,x_n)$.
\end{theorem}





%%------ 3.
\section{О некоторых сужениях совершенных $\Pi$-разбиений}


Через $\Phi_Z^\delta$ обозначим собственный прямоугольник линейной
булевой функции $f_Z^\delta(x_1,\dots,x_n)$, и пусть
$\mathrm{N}_Z^\delta=\{\alpha\in\mathrm{B}^n\mid \
\bigoplus\nolimits_{i\in Z}\alpha_i=\delta\}$.

Очевидно справедливо равенство
$\Phi_Z^\delta=\mathrm{N}_Z^{\delta\oplus1}\times\mathrm{N}_Z^\delta$



Сформулируем определения линейного множества и его линейного
$\Pi$-разбиения \cite{8}.

Прямоугольник $L\in\mathrm{REC}^n$ называется {\it линейным
множеством} или просто {\it линейным прямоугольником}, если
существует такое $k$, $1\leq k\leq n$, и такие две
последовательности $J=J_1,\dots,J_k$ и
$\Delta=\delta_1,\dots,\delta_k$, что $\{1,\dots,n\}\supseteq
J_1\supset J_2,\dots,\supset J_k\supset\emptyset$,
$\delta_1,\dots,\delta_k\in\{0,1\}$ и выполнено равенство
$L=\Phi_{J_1}^{\delta_1}\cap\dots\cap\Phi_{J_k}^{\delta_k}$.
Последовательности $J$ и $\Delta$ называются соответственно {\it
нижней} и {\it верхней} {\it характеристическими
последовательностями} линейного множества $L$. Последний элемент
$J_k$ последовательности $J$ называется {\it множеством образующих},
последний элемент $\delta_k$ последовательности $\Delta$ -- {\it
показателем}, число $k$ -- {\it мощностным рангом} линейного
множества $L$.

Нетрудно показать (используя простейшие соображения из области
решения систем линейных уравнений), что для любых вышеуказанных $k$,
$J$ и $\Delta$ справедливо неравенство
$\Phi_{J_1}^{\delta_1}\cap\dots\cap\Phi_{J_k}^{\delta_k}\neq\emptyset$
(а, значит, и включение
$\Phi_{J_1}^{\delta_1}\cap\dots\cap\Phi_{J_k}^{\delta_k}\in\mathrm{REC}^n$);
и что для любого линейного множества $L\in\mathrm{REC}^n$ его нижняя
и верхняя характеристические последовательности определены
однозначно.

Линейное множество называется {\it элементарным}, если мощность
множества его образующих равна 1.

Для произвольных целых $p$ и $k$, $1\leq p\leq k$, и любого набора
множеств $J_1,\dots,J_k\subseteq\{1,\dots,n\}$ последовательность
$J_1,\dots,J_p$ будем называть {\it началом} последовательности
$J_1,\dots,J_k$; точно также для любого набора чисел
$\delta_1,\dots,\delta_k\in\{0,1\}$ последовательность
$\delta_1,\dots,\delta_p$ будем называть {\it началом}
последовательности $\delta_1,\dots,\delta_k$.

Линейное множество $M\in\mathrm{REC}^n$ называется {\it собственным
линейным подмножеством линейного множества} $L\in\mathrm{REC}^n$,
если нижняя характеристическая последовательность $L$ является
началом нижней характеристической последовательности $M$, и верхняя
характеристическая последовательность $L$ является началом верхней
характеристической последовательности $M$.

Собственное линейное подмножество линейного множества
$L\in\mathrm{REC}^n$ называется {\it элементарным}, если оно
является элементарным линейным множеством.

$\Pi$-разбиение линейного множества $L\in\mathrm{REC}^n$ называется
{\it линейным}, если каждый его блок является элементарным
собственным линейным подмножеством  $L$.





Сформулируем определение изоморфизма $\Pi$-разбиений \cite{7}.

Два прямоугольных фрагмента $\Pi$-разбиения $U\in\Pi^n$ называются
{\it горизонтально} ({\it вертикально}) {\it соседними}, если
горизонтально (вертикально) соседними являются соответствующие этим
фрагментам гиперблоки этого $\Pi$-разбиения.

Прямоугольный фрагмент $S\in\mathcal{F}(U)$ называется {\it
горизонтальным} ({\it вертикальным}) {\it соединением прямоугольных
фрагментов} $S_1,S_2\in\mathcal{F}(U)$, если соответствующий
фрагменту $S$ гиперблок $\Pi$-разбиения $U$ является горизонтальным
(вертикальным) соединением гиперблоков этого $\Pi$-разбиения,
соответствующих фрагментам $S_1,S_2$.

Пусть $U,T\in\Pi^n$, $|U|=|T|$ и $\mu$ -- взаимно однозначное
отображение $\Pi$-разбиения $U$ на $\Pi$-разбиение $T$.

Мы говорим, что отображение $\mu$ {\it сохраняет свойство
подсемейств быть прямоугольными фрагментами}, если для любого
подсемейства $S\subseteq U$ и его образа $\mu(S)$ из включения
$S\in\mathcal{F}(U)$ следует включение $\mu(S)\in\mathcal{F}(T)$.

По определению отображение $\mu$ {\it сохраняет соединяемость
прямоугольных фрагментов}, если оно, во-первых, сохраняет свойство
подсемейств быть прямоугольными фрагментами; во-вторых, для любых
$S,S_1,S_2\in\mathcal{F}(U)$ справедливо утверждение: если фрагмент
$S$ является горизонтальным соединением фрагментов $S_1$ и $S_2$, то
фрагмент $\mu(S)$ является горизонтальным соединением фрагментов
$\mu(S_1)$ и $\mu(S_2)$, и, если фрагмент $S$ является вертикальным
соединением фрагментов $S_1$ и $S_2$, то фрагмент $\mu(S)$ является
вертикальным соединением фрагментов $\mu(S_1)$ и $\mu(S_2)$.

По определению отображение $\mu$ {\it сохраняет однородность
блоков}, если для каждого блока $Q\in U$ при любых
$i\in\{1,\dots,n\}$, $\delta\in\{0,1\}$ из включения $Q\subseteq
\mathrm{X}_i^\delta$ следует включение $\mu(Q)\subseteq
\mathrm{X}_i^\delta$.

{\it Полуизоморфизмом} $\Pi$-разбиения $U\in\Pi^n$ на
$\Pi$-разбиение $T\in\Pi^n$ называется такое взаимно однозначное
отображение $\mu:U\longrightarrow T$, что $\mu$ сохраняет
соединяемость прямоугольных фрагментов и сохраняет однородность
блоков.

{\it Изоморфизмом} $\Pi$-разбиения $U\in\Pi^n$ на $\Pi$-разбиение
$T\in\Pi^n$ называется такой полуизоморфизм $\mu:U\longrightarrow
T$, что обратное отображение  $\mu^{-1}$ является полуизоморфизмом
$T$ на $U$.

$\Pi$-разбиения $U,T\in\Pi^n$ называются {\it изоморфными}, если
существует изоморфизм $\Pi$-разбиения $U$ на $\Pi$-разбиение $T$.

Через $\Phi_{J_1,J_2}^{\delta_1,\delta_2}$ обозначим линейный
прямоугольник с нижней характеристической последовательностью
$J_1,J_2$ и верхней характеристической последовательностью
$\delta_1,\delta_2$.

Очевидно для
$\Phi_{J_1,J_2}^{\delta_1,\delta_2}=\Phi_{J_1}^{\delta_1}\cap\Phi_{J_2}^{\delta_2}$
справедливо включение
$\Phi_{J_1,J_2}^{\delta_1,\delta_2}\subseteq\Phi_{J_2}^{\delta_2}$.





%%---Теорема 2.
\begin{theorem}
Для любого целого $n\geq2$ и любых таких $Z,I\subseteq
\{1,\dots,n\}$, что $Z\supset I\supset\emptyset$, при любых
$\delta,\sigma\in\{0,1\}$ справедливы следующие два утверждения:

1) сужение $U|\Phi_{Z,I}^{\delta,\sigma}$ любого совершенного
$\Pi$-разбиения $U$ прямоугольника $\Phi_I^\sigma$ на прямоугольник
$\Phi_{Z,I}^{\delta,\sigma}$ является изоморфным $U$ совершенным
$\Pi$-разбиением $\Phi_{Z,I}^{\delta,\sigma}$;

2) для любого совершенного $\Pi$-разбиения $V$ прямоугольника
$\Phi_{Z,I}^{\delta,\sigma}$ существует единственное совершенное
$\Pi$-разбиение $U$ прямоугольника $\Phi_I^\sigma$ такое, что
$U|\Phi_{Z,I}^{\delta,\sigma}=V$.
\end{theorem}

\begin{proof}
Докажем первое утверждение теоремы 2.

Пусть $U$ -- произвольное совершенное $\Pi$-разбиение прямоугольника
$\Phi_I^\sigma$. Через $V$ обозначим сужение $U$ на прямоугольник
$\Phi_{Z,I}^{\delta,\sigma}$. В \cite{8} установлена справедливость
следующего утверждения.


%%---Лемма 2.
\begin{lemma}
$\Pi$-разбиение линейного прямоугольника $L\in\mathrm{REC}^n$ тогда
и только тогда является совершенным, когда оно является линейным.
\end{lemma}



По лемме 2 из совершенности $U$ следует его линейность. Поэтому
любой блок $U$ является элементарным собственным линейным
подмножеством прямоугольника $\Phi_I^\sigma$.



%%---Лемма 3.
\begin{lemma}
Для любого блока $Q \in U$ пересечение
$Q\cap\Phi_{Z,I}^{\delta,\sigma}$ является элементарным собственным
линейным подмножеством прямоугольника $\Phi_{Z,I}^{\delta,\sigma}$.
Нижняя и верхняя характеристические последовательности этого
линейного подмножества получаются из соответствующих
характеристических последовательностей $Q$ посредством добавления к
ним в качестве первых элементов соответственно $Z$ и $\delta$.
\end{lemma}

\begin{proof}
Пусть $Q$ -- произвольный блок $U$. Из линейности $U$ следует, что
$Q$ это элементарный линейный прямоугольник, а $I$ и $\sigma$ --
первые элементы его соответственно нижней и верхней
характеристических последовательностей. Поэтому из включения
$Z\supset I$ следует, что множество $\Phi_Z^\delta\cap Q$ также
является элементарным линейным прямоугольником, а последовательности
$Z,I$ и $\delta,\sigma$ являются началами его соответственно нижней
и верхней характеристических последовательностей. Это по определению
означает, что $\Phi_Z^\delta\cap Q$ является элементарным
собственным линейным подмножеством линейного прямоугольника
$\Phi_{Z,I}^{\delta,\sigma}$. Кроме того очевидно нижняя и верхняя
характеристические последовательности $\Phi_Z^\delta\cap Q$
получаются из соответствующих характеристических последовательностей
$Q$ посредством добавления к ним в качестве первых элементов
соответственно $Z$ и $\delta$. Осталось заметить, что в силу
включения $Q\subseteq\Phi_I^\sigma$ справедливо равенство
$Q\cap\Phi_{Z,I}^{\delta,\sigma}=\Phi_Z^\delta\cap Q$.  Лемма 3
доказана.
\end{proof}



%%---Лемма 4.
\begin{lemma}
Сужение $V=U|\Phi_{Z,I}^{\delta,\sigma}$ является совершенным
$\Pi$-разбиением прямоугольника $\Phi_{Z,I}^{\delta,\sigma}$.
\end{lemma}

\begin{proof}
Из лемм 1, 3 следует, что $V$ является линейным $\Pi$-разбиением
прямоугольника $\Phi_{Z,I}^{\delta,\sigma}$. Поэтому в силу леммы 2
оно является его совершенным $\Pi$-разбиением. Лемма 4 доказана.
\end{proof}



Покажем, что  $\Pi$-разбиения $U$ и $V$ изоморфны.


%%---Лемма 5.
\begin{lemma}
Сужение  $V=U|\Phi_{Z,I}^{\delta,\sigma}$ является строгим.
\end{lemma}

\begin{proof}
По лемме 3 все пересечения
$Q\cap\Phi_{Z,I}^{\delta,\sigma}$, $Q\in U$, являются линейными
прямоугольниками. Поэтому для любого $Q\in U$ справедливо
неравенство $Q\cap\Phi_{Z,I}^{\delta,\sigma}\neq\emptyset$. Лемма 5
доказана.
\end{proof}



Определим отображение $\mu:U\rightarrow V$ следующим правилом:
$$
\mu(Q)=Q\cap\Phi_{Z,I}^{\delta,\sigma}, \ \ \ Q\in U.
$$



%%---Лемма 6.
\begin{lemma}
Отображение $\mu:U\longrightarrow V$ является полуизоморфизмом
$\Pi$-разбиения $U$ на $\Pi$-разбиение $V$.
\end{lemma}

\begin{proof}
В \cite{7} установлена справедливость
следующего утверждения.

%%---Лемма 7.
\begin{lemma}
Для любого $\Pi$-разбиения $U$ любого прямоугольника
$\Phi\in\mathrm{REC}^n$ справедливо утверждение: если сужение $U$ на
прямоугольник $P\subseteq\Phi$ является строгим, то заданное
равенством $\mu(Q)=Q\cap P$, $Q\in U$, отображение
$\mu:U\longrightarrow U|P$ является полуизоморфизмом $U$ на
$\Pi$-разбиение $U|P$.
\end{lemma}

Лемма 6 является следствием лемм 5 и 7. Лемма 6 доказана.
\end{proof}



Рассмотрим обратное к $\mu$ отображение $\mu^{-1}:V\longrightarrow
U$.

Для произвольного линейного прямоугольника $M\in\mathrm{REC}^n$
мощностного ранга $k\geq 2$ через $M^{(1)}$ обозначим линейный
прямоугольник, нижняя и верхняя характеристические
последовательности которого получены из соответствующих
характеристических последовательностей $M$ посредством вычёркивания
первых элементов.



%%--- Лемма 8.
\begin{lemma}
Значение отображения $\mu^{-1}:V\longrightarrow U$
определяется по формуле
$$
\mu^{-1}(M)=M^{(1)}, \ \ \ M\in V.
$$
\end{lemma}

\begin{proof}
Лемма 8 является следствием леммы 3.
\end{proof}



%%--- Следствие 1.
\begin{corollary}
Справедливо равенство $U=\{M^{(1)}\mid M\in V\}$.
\end{corollary}



Через $\mathfrak{P}(\Phi_{Z,I}^{\delta,\sigma})$ и
$\mathfrak{P}(\Phi_I^\sigma)$ обозначим множество всех подмножеств
прямоугольников $\Phi_{Z,I}^{\delta,\sigma}$ и $\Phi_I^\sigma$
соответственно.

Чтобы доказать, что отображение $\mu^{-1}$ также полуизоморфизм,
построим несколько более широкое отображение
$\Lambda:\mathfrak{P}(\Phi_{Z,I}^{\delta,\sigma})\rightarrow\mathfrak{P}(\Phi_I^\sigma)$,
и покажем, что $\mu^{-1}$ является его сужением на $V$.

Выберем произвольное $i\in Z\setminus I$, и для каждого
$(\alpha,\beta)\in\Phi_{Z,I}^{\delta,\sigma}$ определим
прямоугольник $\mathrm{T}((\alpha,\beta))\in\mathrm{REC}^n$
следующим равенством:
$$
\mathrm{T}((\alpha,\beta))=\{\alpha,\alpha+\mathbf{e}^i\}\times\{\beta,\beta+\mathbf{e}^i\}.
$$




%%---Предложение 1.
\begin{proposition}
Для любого
$(\alpha,\beta)\in\Phi_{Z,I}^{\delta,\sigma}$ справедливо включение
$$
\mathrm{T}((\alpha,\beta))\subseteq\Phi_I^\sigma.
$$
\end{proposition}

\begin{proof}
Из равенства
$\Phi_{Z,I}^{\delta,\sigma}=\Phi_Z^\delta\cap\Phi_I^\sigma$ следует
$(\alpha,\beta)\in\Phi_I^\sigma$. Поэтому
$\alpha\in\mathrm{N}_I^{\sigma\oplus1}$,
$\beta\in\mathrm{N}_I^\sigma$. Значит, из $i\in Z\setminus I$
следует $\alpha+\mathbf{e}^i\in\mathrm{N}_I^{\sigma\oplus1}$ и
$\beta+\mathbf{e}^i\in\mathrm{N}_I^\sigma$. Отсюда следует
$$
\mathrm{T}((\alpha,\beta))=\{\alpha,\alpha+\mathbf{e}^i\}\times\{\beta,\beta+\mathbf{e}^i\}\subseteq
\mathrm{N}_I^{\sigma\oplus1}\times\mathrm{N}_I^\sigma=\Phi_I^\sigma.
$$
Предложение 1 доказано.
\end{proof}



%%---Предложение 2.
\begin{proposition}
Для любых
$(\alpha,\beta),(\rho,\gamma)\in\Phi_{Z,I}^{\delta,\sigma}$ из
$(\alpha,\beta)\neq(\rho,\gamma)$ следует
$$
\mathrm{T}((\alpha,\beta))\cap\mathrm{T}((\rho,\gamma))=\emptyset.
$$
\end{proposition}

\begin{proof}
Достаточно показать, что либо вертикальные
либо горизонтальные стороны прямоугольников
$\mathrm{T}((\alpha,\beta))$ и $\mathrm{T}((\rho,\gamma))$ не
пересекаются.

Пусть $\alpha\neq\rho$. Тогда очевидно
$\alpha+\mathbf{e}^i\neq\rho+\mathbf{e}^i$. Кроме того из включений
$\alpha,\rho\in\mathrm{N}_Z^{\delta\oplus1}\cap\mathrm{N}_I^{\sigma\oplus1}$
и $i\in Z\setminus I$ следует
$\alpha+\mathbf{e}^i,\rho+\mathbf{e}^i\in\mathrm{N}_Z^\delta\cap\mathrm{N}_I^{\sigma\oplus1}$.
Поэтому $\alpha+\mathbf{e}^i\neq\rho$ и
$\rho+\mathbf{e}^i\neq\alpha$. Значит, справедливо равенство
$$
\{\alpha,\alpha+\mathbf{e}^i\}\cap\{\rho,\rho+\mathbf{e}^i\}=\emptyset.
$$
Т. е. вертикальные стороны вышеуказанных прямоугольников не
пересекаются.

В случае $\beta\neq\gamma$ по аналогичной причине их горизонтальные
стороны не пересекаются. Предложение 2 доказано.
\end{proof}



Отображение
$\Lambda:\mathfrak{P}(\Phi_{Z,I}^{\delta,\sigma})\rightarrow\mathfrak{P}(\Phi_I^\sigma)$
определим следующими равенствами:
$$
\Lambda(M)=\bigcup\limits_{(\alpha,\beta)\in
M}\mathrm{T}((\alpha,\beta)), \
M\subseteq\Phi_{Z,I}^{\delta,\sigma}, \ M\neq\emptyset; \ \ \ \ \
\Lambda(\emptyset)=\emptyset.
$$



%%---Лемма 9.
\begin{lemma}
Для любого собственного линейного подмножества $M$
линейного прямоугольника $\Phi_{Z,I}^{\delta,\sigma}$ справедливо
равенство $\Lambda(M)=M^{(1)}$.
\end{lemma}

\begin{proof}
Пусть $M$ -- произвольное собственное линейное
подмножество прямоугольника $\Phi_{Z,I}^{\delta,\sigma}$, и пусть
$J_1,\dots,J_k$ и $\tau_1,\dots,\tau_k$ -- соответственно его нижняя
и верхняя характеристические последовательности. Тогда по
определению имеем
$$
J_1=Z, \ \ J_2=I, \ \ \tau_1=\delta, \ \ \tau_2=\sigma,
$$
$$
M=\Phi_Z^\delta\cap\Phi_I^\sigma\cap\Phi_{J_3}^{\tau_3}\cap\ldots\cap\Phi_{J_k}^{\tau_k},
\ \ \
M^{(1)}=\Phi_I^\sigma\cap\Phi_{J_3}^{\tau_3}\cap\ldots\cap\Phi_{J_k}^{\tau_k}.
$$
Значит, для любого $(\alpha,\beta)\in M$ из включений $I\supset
J_3\supset\ldots\supset J_k$, $i\in Z\setminus I$ и очевидного
включения $M\subseteq M^{(1)}$ следует
$$
\{\alpha,\alpha+\mathbf{e}^i\}\subseteq
\mathrm{N}_I^{\sigma\oplus1}\cap\mathrm{N}_{J_3}^{\tau_3\oplus1}\cap\ldots\cap\mathrm{N}_{J_k}^{\tau_k\oplus1}
\ \ \ \ {\mbox и} \ \ \ \ \{\beta,\beta+\mathbf{e}^i\}\subseteq
\mathrm{N}_I^\sigma\cap\mathrm{N}_{J_3}^{\tau_3}\cap\ldots\cap\mathrm{N}_{J_k}^{\tau_k}.
$$
Поэтому
\begin{multline*}
$$
\mathrm{T}((\alpha,\beta))=\{\alpha,\alpha+\mathbf{e}^i\}\times\{\beta,\beta+\mathbf{e}^i\}
$$ \\
$$
\subseteq
(\mathrm{N}_I^{\sigma\oplus1}\cap\mathrm{N}_{J_3}^{\tau_3\oplus1}\cap\ldots\cap\mathrm{N}_{J_k}^{\tau_k\oplus1})
\times(\mathrm{N}_I^\sigma\cap\mathrm{N}_{J_3}^{\tau_3}\cap\ldots\cap\mathrm{N}_{J_k}^{\tau_k})
$$ \\
$$
=\Phi_I^\sigma\cap\Phi_{J_3}^{\tau_3}\cap\ldots\cap\Phi_{J_k}^{\tau_k}=M^{(1)}.
$$
\end{multline*}
Это означает справедливость включения $\Lambda(M)\subseteq M^{(1)}$.

Докажем обратное включение $\Lambda(M)\supseteq M^{(1)}$. Для этого
рассмотрим четыре подмножества
$A^{c_1,c_2}=M^{(1)}\cap(\mathrm{N}_Z^{c_1}\times\mathrm{N}_Z^{c_2})$,
$c_1,c_2\in\{0,1\}$, прямоугольника $M^{(1)}$. В силу очевидного
равенства $M^{(1)}=A^{0,0}\cup A^{0,1}\cup A^{1,0}\cup A^{1,1}$
достаточно доказать четыре включения $\Lambda(M)\supseteq
A^{c_1,c_2}$, $c_1,c_2\in\{0,1\}$.

Заметим, что $M=M^{(1)}\cap\Phi_Z^\delta=A^{\delta\ominus1,\delta}$.
Без ограничения общности считаем $\delta=0$, т. е. $M=A^{1,0}$. Для
любого $(\alpha,\beta)\in M$ по определению прямоугольника
$\mathrm{T}((\alpha,\beta))$ справедливо включение
$\mathrm{T}((\alpha,\beta))\ni(\alpha,\beta)$. Это означает
справедливость включения $\Lambda(M)\supseteq A^{1,0}$.

Рассмотрим произвольное $(\alpha,\beta)\in A^{0,0}$ и пусть
$\gamma=\alpha+\mathbf{e}^i$. Тогда очевидно выполнено включение
$(\gamma,\beta)\in A^{1,0}=M$. По определению прямоугольника
$\mathrm{T}((\gamma,\beta))$ справедливо включение
$\mathrm{T}((\gamma,\beta))\ni(\gamma+\mathbf{e}^i,\beta)$. В силу
равенства $(\gamma+\mathbf{e}^i,\beta)=(\alpha,\beta)$ это означает
справедливость включения $\Lambda(M)\supseteq A^{0,0}$.

Оставшиеся два включения $\Lambda(M)\supseteq A^{0,1}$ и
$\Lambda(M)\supseteq A^{1,1}$ выполнены по аналогичным причинам.
Лемма 9 доказана.
\end{proof}



%%---Лемма 10.
\begin{lemma}
Отображение $\mu^{-1}:V\longrightarrow U$ является
сужением отображения $\Lambda$ на $\Pi$-разбиение $V$.
\end{lemma}

\begin{proof}
Лемма 10 является следствием лемм 8 и 9.
\end{proof}




%%---Лемма 11.
\begin{lemma}
Отображение $\Lambda$ обладает следующими свойствами:

1) для любых двух множеств
$M_1,M_2\subseteq\Phi_{Z,I}^{\delta,\sigma}$ из $M_1\cap
M_2=\emptyset$ следует $ \Lambda(M_1)\cap\Lambda(M_2)=\emptyset; $

2) для любых двух множеств
$M_1,M_2\subseteq\Phi_{Z,I}^{\delta,\sigma}$ справедливо равенство
$\Lambda(M_1\cup M_2)=\Lambda(M_1)\cup\Lambda(M_2)$;

3) для любого прямоугольника $M\subseteq\Phi_{Z,I}^{\delta,\sigma}$
его образ $\Lambda(M)$ также является прямоугольником;

4) для любых двух горизонтально соседних прямоугольников
$M_1,M_2\subseteq\Phi_{Z,I}^{\delta,\sigma}$ прямоугольники
$\Lambda(M_1)$ и $\Lambda(M_2)$ также являются горизонтально
соседними, и для любых двух вертикально соседних прямоугольников
$M_1,M_2\subseteq\Phi_{Z,I}^{\delta,\sigma}$ прямоугольники
$\Lambda(M_1)$ и $\Lambda(M_2)$ также являются вертикально
соседними.

5) для любого $M\subseteq\Phi_{Z,I}^{\delta,\sigma}$ справедливо
равенство $\Lambda(M)\cap\Phi_{Z,I}^{\delta,\sigma}=M$.
\end{lemma}

\begin{proof}
Справедливость леммы 11 очевидным образом следует из определения
отображения $\Lambda$ и предложений 1, 2.
\end{proof}




%%---Лемма 12.
\begin{lemma}
Отображение $\mu^{-1}:V\longrightarrow U$ является
полуизоморфизмом $\Pi$-разбиения $V$ на $\Pi$-разбиение $U$.
\end{lemma}

\begin{proof}
В силу леммы 10 отображение $\mu^{-1}$ является сужением отображения
$\Lambda$ на $\Pi$-разбиение $V$. Поэтому в силу сформулированных в
лемме 11 свойств 1, 2 отображения $\Lambda$ отображение $\mu^{-1}$
сохраняет свойство подсемейств быть прямоугольными фрагментами. И
следовательно в силу свойств 3, 4 из той же леммы оно сохраняет
соединяемость прямоугольных фрагментов.

Покажем, что $\mu^{-1}$ сохраняет однородность блоков. Для этого
рассмотрим произвольный элементарный линейный прямоугольник
$M=\Phi_{J_1}^{\tau_1}\cap\ldots\cap\Phi_{J_k}^{\tau_k}$. По
определению для него выполнено равенство $|J_k|=1$. Пусть
$J_k=\{j\}$. Очевидно справедливо включение
$M\subseteq\Phi_{J_k}^{\tau_k}=\mathrm{X}_j^{\tau_k}$. Поэтому
прямоугольник $M$ является $(j,\tau_k)$-однородным. Кроме того
очевидно $M$ является $(j,\tau_k)$-центрированным, т. е. для
некоторой его диагонали $D$ справедливо включение
$D\subseteq\mathrm{R}_j^{\tau_k}$. Очевидно также для любого ребра
$(\alpha,\beta)\in\mathrm{R}_j^{\tau_k}$ существуют единственные
$i\in\{1,\dots,n\}$ и $\delta\in\{0,1\}$ для которых выполнено
включение $(\alpha,\beta)\in\mathrm{X}_i^\delta$, этими $i$ и
$\delta$ являются соответственно $j$ и $\tau_k$. Поэтому для $M$
существуют единственные $i\in\{1,\dots,n\}$ и $\delta\in\{0,1\}$ для
которых выполнено включение $M\subseteq\mathrm{X}_i^\delta$ (т. е.
для которых $M$ является $(i,\delta)$-однородным). При $k\geq 2$ то
же самое справедливо и для $M^{(1)}$. В силу леммы 8 это и означает,
что отображение $\mu^{-1}$ сохраняет однородность блоков. Лемма 12
доказана.
\end{proof}


%%---Лемма 13.
\begin{lemma}
Отображение $\mu$ является изоморфизмом $\Pi$-разбиения $U$ на
$\Pi$-разбиение $V$.
\end{lemma}

\begin{proof}
Лемма 12 является следствием лемм 6 и 12.
\end{proof}


Первое утверждение теоремы 2 является следствием лемм 4 и 13.



Докажем второе утверждение теоремы 2.

Пусть $V$ -- произвольное совершенное $\Pi$-разбиение прямоугольника
$\Phi_{Z,I}^{\delta,\sigma}$. По лемме 2 оно является линейным, т.
е. любой его блок является элементарным собственным линейным
подмножеством $\Phi_{Z,I}^{\delta,\sigma}$. Через $S$ обозначим
семейство прямоугольников $\{M^{(1)}\mid M\in V\}$. Очевидно все
прямоугольники из $S$ являются элементарными собственными линейными
подмножествами прямоугольника $\Phi_I^\sigma$.



%%---Лемма 14.
\begin{lemma}
Если существует совершенное $\Pi$-разбиение $U$ прямоугольника
$\Phi_I^\sigma$ такое, что $U|\Phi_{Z,I}^{\delta,\sigma}=V$, то оно
единственно.
\end{lemma}

\begin{proof}
В силу следствия 1 для такого $\Pi$-разбиения $U$ должно быть
выполнено равенство $U=S$. Лемма 14 доказана.
\end{proof}



%%---Лемма 15.
\begin{lemma}
Семейство прямоугольников $S$ является совершенным $\Pi$-разбиением
прямоугольника  $\Phi_I^\sigma$.
\end{lemma}

\begin{proof}
Покажем, что $S$ является прямоугольным разбиением прямоугольника
$\Phi_I^\sigma$. Очевидно $|\Phi_I^o|=4|\Phi_{Z,I}^{\delta,\sigma}|$
и для любого $M\in V$ справедливо равенство $|M^{(1)}|=4|M|$.
Следовательно справедливо равенство
$$
\sum\limits_{Q\in S}|Q|=\sum\limits_{M\in
V}|M^{(1)}|=\sum\limits_{M\in
V}4|M|=4|\Phi_{I,Z}^{\sigma,\delta}|=|\Phi_Z^\delta|.
$$
Поэтому достаточно показать, что прямоугольники семейства $S$
попарно не пересекаются.

Предположим противное: для двух различных $M,K\in V$ справедливо
неравенство $M^{(1)}\cap K^{(1)}\neq\emptyset$. Выберем произвольное
$(\alpha,\beta)\in M^{(1)}\cap K^{(1)}$ и любое $i\in Z\setminus I$.
Через $T$ обозначим прямоугольник
$\{\alpha,\alpha+\mathbf{e}^i\}\times\{\beta,\beta+\mathbf{e}^i\}$.
Тогда из включения $i\in Z\setminus I$ следует $T\subseteq
M^{(1)}\cap K^{(1)}$.  Отсюда в силу равенств $M=\Phi_Z^\delta\cap
M^{(1)}$ и $K=\Phi_Z^\delta\cap K^{(1)}$ следует $T\cap(M\cap
K)\neq\emptyset$. Это противоречит равенству $M\cap K=\emptyset$.
Значит, наше предположение неверно и прямоугольники семейства $S$
попарно не пересекаются.

Через $\lambda:V\rightarrow S$ обозначим заданное правилом
$\lambda(M)=M^{(1)}$ взаимно однозначное отображение $V$ на $S$. В
силу леммы 9 отображение $\lambda$ является сужением отображения
$\Lambda$ на $V$. Поэтому в силу свойства 5 отображения $\Lambda$
для любого $Q\in S$ справедливо равенство
$\lambda^{-1}(Q)=Q\cap\Phi_{Z,I}^{\delta,\sigma}$.



Покажем, что прямоугольное разбиение $S$ является разделимым. Пусть
$P$ -- произвольный составной гиперблок $S$. Через $F$ обозначим
соответствующий ему прямоугольный фрагмент $S$, через $C$ --
пересечение $P\cap\Phi_{I,Z}^{\sigma,\delta}$, через $E$ --
семейство блоков $\{\lambda^{-1}(Q)\mid Q\in F\}$ разбиения $V$.
Тогда из равенства
$$
C=P\cap\Phi_{Z,I}^{\delta,\sigma}=\bigcup\limits_{Q\in
F}(Q\cap\Phi_{Z,I}^{\delta,\sigma})=\bigcup\limits_{Q\in
F}\lambda^{-1}(Q)
$$
следует $C\neq\emptyset$, т. е. $C$ является прямоугольником и более
того -- гиперблоком $\Pi$-разбиения $V$. Поэтому в силу свойств 1, 2
отображения $\Lambda$ справедливы равенства
$$
\Lambda(C)=\Lambda\left(\bigcup\limits_{Q\in
F}\lambda^{-1}(Q)\right)=\bigcup\limits_{Q\in F}Q=P.
$$
Отсюда в силу свойств 1, 2, 3, 4 отображения $\Lambda$ из
разделимости гиперблока $C$ $\Pi$-разбиения $V$ следует разделимость
гиперблока $P$ прямоугольного разбиения $S$.

Покажем, что прямоугольное разбиение $S$ является однородным. Как
уже было отмечено, любой блок $S$ является элементарным собственным
линейным подмножеством прямоугольника $\Phi_I^\sigma$. Это значит,
что он является некоторым элементарным линейным  прямоугольником
$M=\Phi_I^\sigma\cap\Phi_{J_1}^{\tau_1}\cap\ldots\cap\Phi_{J_k}^{\tau_k}$.
Поэтому в силу включения $M\subseteq\Phi_{J_k}^{\tau_k}$ и равенства
$\Phi_{J_k}^{\tau_k}=\mathrm{X}_j^{\tau_k}$, $j\in J_k$, он является
однородным.

В силу разделимости и однородности прямоугольное разбиение $S$
прямоугольника $\Phi_Z^\delta$ является его $\Pi$-разбиением. А
поскольку каждый блок $S$ является элементарным собственным линейным
подмножеством прямоугольника $\Phi_I^\sigma$, это $\Pi$-разбиение
является линейным. Значит, по лемме 2 оно является совершенным.
Лемма 15 доказана.
\end{proof}

Второе утверждение теоремы 2 является следствием лемм 14 и 15.
Теорема 2 доказана.
\end{proof}





%%------ 4.
\section{Доказательство необходимого условия теоремы 1}



Покажем, что любая формула $F\in\mathbb{P}^\delta_Z$ имеет
совершенное представление на собственном прямоугольнике функции
$f^\delta_Z(x_1,\dots,x_n)$. Доказательство проведём индукцией по
$|Z|$.

При $|Z|=1$ по определению класса $\mathbb{P}_Z^\delta$ формула
$F\in\mathbb{P}_Z^\delta$ является однобуквенной формулой
$x_i^\delta$, $i\in Z$. В этом случае для собственного
прямоугольника $\Phi_Z^\delta$ функции $f_Z^\delta$ справедливо
равенство $\Phi_Z^\delta=\mathrm{X}_i^\delta$. Через $U$ обозначим
состоящее из единственного блока $\mathrm{X}_i^\delta$
$\Pi$-разбиение прямоугольника $\Phi_Z^\delta$. Тогда по определению
порождаемого $\Pi$-разбиением $U$ класса формул $\mathfrak{N}(U)$
справедливо включение $x_i^\delta\in\mathfrak{N}(U)$. Это означает,
что $U$ является представлением $F$. А поскольку единственный блок
$\mathrm{X}_i^\delta$ $\Pi$-разбиения $U$ является
$(i,\delta)$-центрированным прямоугольником, $U$ является
совершенным представлением $F$ на прямоугольнике $\Phi_Z^\delta$.


Пусть $m>1$. Предположим, что при $1\leq|Z|\leq m-1$ любая формула
из класса $\mathbb{P}_Z^\delta$ имеет совершенное представление на
прямоугольнике $\Phi_Z^\delta$. Покажем, что тогда то же самое
справедливо и при $|Z|=m$.

Пусть $|Z|=m$ и $F$ -- произвольная формула из
$\mathbb{P}_Z^\delta$. По определению класса формул
$\mathbb{P}_Z^\delta$ для $F$ существует такое отличное от $Z$
непустое подмножество $I$ множества $Z$, что справедливо включение
$F\in\mathbb{P}_\vee^\delta(I,Z\setminus
I)\cup\mathbb{P}_\wedge^\delta(I,Z\setminus I)$. Множество
$Z\setminus I$ обозначим через $J$. Тогда очевидно выполнены
неравенства $|I|\leq m-1$ и $|J|\leq m-1$.

Рассмотрим случай $F\in\mathbb{P}^1_\vee(I,J)$. Случай
$F\in\mathbb{P}^1_\wedge(I,J)$ а также случаи
$F\in\mathbb{P}^0_\vee(I,J)$ и $F\in\mathbb{P}^0_\wedge(I,J)$
рассматриваются аналогично.

По определению класса формул $\mathbb{P}^1_\vee(I,J)$ для формулы
$F\in\mathbb{P}^1_\vee(I,J)$ существуют такие четыре формулы
$F_I^0\in \mathbb{P}_I^0$, $F_J^1\in \mathbb{P}_J^1$, $F_I^1\in
\mathbb{P}_I^1$, $F_J^0\in \mathbb{P}_J^0$, что $F$
$\Pi$-эквивалентна формуле $F'=((F^0_I\wedge F^1_J)\vee(F^1_I\wedge
F^0_J))$.


В \cite{7} установлена справедливость следующего утверждения.



%%---Лемма 16.
\begin{lemma}
Для любого $\Pi$-разбиения $U\in\Pi^n$ класс формул
$\mathfrak{N}(U)$ замкнут относительно $\Pi$-эквивалентности.
\end{lemma}



В силу леммы 16 любое представление формулы $F'$ является
представлением формулы $F$. Поэтому достаточно показать, что $F'$
имеет совершенное представление на прямоугольнике $\Phi^1_Z$.

По предположению индукции указанные формулы $F_I^0$, $F_J^1$,
$F_I^1$, $F_J^0$ имеют совершенные представления на прямоугольниках
$\Phi_I^0$, $\Phi_J^1$, $\Phi_I^1$, $\Phi_J^0$ соответственно.
Обозначим их через $U_I^0$, $U_J^1$, $U_I^1$, $U_J^0$
соответственно. Тогда по определению представления формул
справедливы включения
\begin{equation}\label{1}
F_I^0\in\mathfrak{N}(U_I^0), \ \ \ \ \ F_J^1\in\mathfrak{N}(U_J^1),
\ \ \ \ \ F_I^1\in\mathfrak{N}(U_I^1), \ \ \ \ \
F_J^0\in\mathfrak{N}(U_J^0)
\end{equation}
и по теореме 2 сужения
$$
U_{Z,I}^{1,0}=U_I^0|\Phi_{Z,I}^{1,0}, \ \ \ \
U_{Z,J}^{1,1}=U_J^1|\Phi_{Z,J}^{1,1}, \ \ \ \
U_{Z,I}^{1,1}=U_I^1|\Phi_{Z,I}^{1,1}, \ \ \ \
U_{Z,J}^{1,0}=U_J^0|\Phi_{Z,J}^{1,0}
$$
этих представлений на прямоугольники соответственно
$$
\Phi_{Z,I}^{1,0}=\Phi_Z^1\cap\Phi_I^0, \ \ \
\Phi_{Z,J}^{1,1}=\Phi_Z^1\cap\Phi_J^1, \ \ \
\Phi_{Z,I}^{1,1}=\Phi_Z^1\cap\Phi_I^1, \ \ \
\Phi_{Z,J}^{1,0}=\Phi_Z^1\cap\Phi_J^0
$$
являются изоморфными им совершенными $\Pi$-разбиениями этих
прямоугольников.

Покажем, что объединение $U=U_{Z,I}^{1,0}\cup U_{Z,J}^{1,1}\cup
U_{Z,I}^{1,1}\cup U_{Z,J}^{1,0}$ этих $\Pi$-разбиений и есть
совершенное представление формулы $F'$ на прямоугольнике $\Phi_Z^1$.

Сначала покажем, что $U$ является совершенным $\Pi$-разбиением
$\Phi_Z^1$.



%%---Лемма 17.
\begin{lemma}
Прямоугольники $\Phi_{Z,I}^{1,0}$ и $\Phi_{Z,J}^{1,1}$ также как и
прямоугольники $\Phi_{Z,I}^{1,1}$ и $\Phi_{Z,J}^{1,0}$ являются
горизонтально соседними. При этом их объединения
$\Phi_{Z,I}^{1,0}\cup\Phi_{Z,J}^{1,1}$ и
$\Phi_{Z,I}^{1,1}\cup\Phi_{Z,J}^{1,0}$ являются вертикально
соседними прямоугольниками. Объединение
$(\Phi_{Z,I}^{1,0}\cup\Phi_{Z,J}^{1,1})\cup(\Phi_{Z,I}^{1,1}\cup\Phi_{Z,J}^{1,0})$
последних двух прямоугольников есть прямоугольник $\Phi_Z^1$.
\end{lemma}

\begin{proof}
Из определения прямоугольников $\Phi_{Z,I}^{1,0}$ и
$\Phi_{Z,J}^{1,1}$ следует
$$
\Phi_{Z,I}^{1,0}=
(\mathrm{N}_Z^0\cap\mathrm{N}_I^1)\times(\mathrm{N}_Z^1\cap\mathrm{N}_I^0)
\ \ \ {\mbox и} \ \ \ \Phi_{Z,J}^{1,1}=
(\mathrm{N}_Z^0\cap\mathrm{N}_J^0)\times(\mathrm{N}_Z^1\cap\mathrm{N}_J^1).
$$
Из включения $Z\supset I$ и равенства $J=Z\setminus I$ следует
$$
\mathrm{N}_Z^0\cap\mathrm{N}_I^1=\mathrm{N}_Z^0\cap\mathrm{N}_J^0, \
\ \ \
(\mathrm{N}_Z^1\cap\mathrm{N}_I^0)\cap(\mathrm{N}_Z^1\cap\mathrm{N}_J^1)=\emptyset.
$$
Поэтому прямоугольники $\Phi_{Z,I}^{1,0}$, $\Phi_{Z,J}^{1,1}$
являются горизонтально соседними. Кроме того в силу равенства
$(\mathrm{N}_Z^1\cap\mathrm{N}_I^0)\cup(\mathrm{N}_Z^1\cap\mathrm{N}_J^1)=\mathrm{N}_Z^1$
для их объединения справедливо равенство
$$
\Phi_{Z,I}^{1,0}\cup\Phi_{Z,J}^{1,1}=(\mathrm{N}_Z^0\cap\mathrm{N}_I^1)\times\mathrm{N}_Z^1.
$$
По аналогичной причине прямоугольники $\Phi_{Z,I}^{1,1}$ и
$\Phi_{Z,J}^{1,0}$ также являются горизонтально соседними и для их
объединения справедливо равенство
$$
\Phi_{Z,I}^{1,0}\cup\Phi_{Z,J}^{1,1}=(\mathrm{N}_Z^0\cap\mathrm{N}_I^0)\times\mathrm{N}_Z^1.
$$
Из этих равенств и очевидных равенств
$$
(\mathrm{N}_Z^0\cap\mathrm{N}_I^1)\cap(\mathrm{N}_Z^0\cap\mathrm{N}_I^0)=\emptyset,
\ \ \ \ \
(\mathrm{N}_Z^0\cap\mathrm{N}_I^1)\cup(\mathrm{N}_Z^0\cap\mathrm{N}_I^0)=\mathrm{N}_Z^0
$$
следует, что прямоугольники $\Phi_{Z,I}^{1,0}\cup\Phi_{Z,J}^{1,1}$ и
$\Phi_{Z,I}^{1,1}\cup\Phi_{Z,J}^{1,0}$ являются вертикально
соседними и справедливо равенство
$$
(\Phi_{Z,I}^{1,0}\cup\Phi_{Z,J}^{1,1})\cup(\Phi_{Z,I}^{1,1}\cup\Phi_{Z,J}^{1,0})=
\mathrm{N}_Z^0\times\mathrm{N}_Z^1=\Phi_Z^1.
$$
Лемма 17 доказана.
\end{proof}



В \cite{7} установлена справедливость следующего очевидного
утверждения.



%%---Лемма 18.
\begin{lemma}
Если прямоугольники $P_1,P_2\in\mathrm{REC}^n$ являются соседними,
то для любого $\Pi$-разбиения $U_1$ первого и любого $\Pi$-разбиения
$U_2$ второго прямоугольника их объединение $U_1\cup U_2$ является
$\Pi$-разбиением прямоугольника $P_1\cup P_2$. Если эти
прямоугольники являются горизонтально соседними, то справедливо
включение
$\mathfrak{N}(U)\vee\mathfrak{N}(V)\subseteq\mathfrak{N}(U\cup V)$;
если они являются вертикально соседними, то справедливо включение
$\mathfrak{N}(U)\wedge\mathfrak{N}(V)\subseteq\mathfrak{N}(U\cup
V)$.
\end{lemma}



Из лемм 17, 18 следует, что объединения $U_{Z,I}^{1,0}\cup
U_{Z,J}^{1,1}$ и $U_{Z,I}^{1,1}\cup U_{Z,J}^{1,0}$ являются
$\Pi$-разбиениями прямоугольников
$\Phi_{Z,I}^{1,0}\cup\Phi_{Z,J}^{1,1}$ и
$\Phi_{Z,I}^{1,1}\cup\Phi_{Z,J}^{1,0}$ соответственно, а объединение
$U=U_{Z,I}^{1,0}\cup U_{Z,J}^{1,1}\cup U_{Z,I}^{1,1}\cup
U_{Z,J}^{1,0}$ -- $\Pi$-разбиением прямоугольника $\Phi_Z^1$. Кроме
того из совершенности $\Pi$-разбиений $U_{Z,I}^{1,0}$,
$U_{Z,J}^{1,1}$, $U_{Z,I}^{1,1}$, $U_{Z,J}^{1,0}$ следует, что все
их блоки являются центрированными прямоугольниками. Поэтому все
блоки $\Pi$-разбиения $U$ являются центрированными прямоугольниками.
Следовательно $U$ является совершенным $\Pi$-разбиением
прямоугольника $\Phi_Z^1$.

Теперь покажем, что $\Pi$-разбиение $U$ является представлением
формулы $F'$. В \cite{7} установлена справедливость следующего
утверждения.


%%---Лемма 19.
\begin{lemma}
Для любых двух изоморфных $\Pi$-разбиений $V,U\in\Pi^n$ справедливо
равенство $\mathfrak{N}(V)=\mathfrak{N}(U)$.
\end{lemma}



В силу леммы 19 справедливы равенства
$$
\mathfrak{N}(U_{Z,I}^{1,0})=\mathfrak{N}(U_I^0), \
\mathfrak{N}(U_{Z,J}^{1,1})=\mathfrak{N}(U_J^1), \
\mathfrak{N}(U_{Z,I}^{1,1})=\mathfrak{N}(U_I^1), \
\mathfrak{N}(U_{Z,J}^{1,0})=\mathfrak{N}(U_J^0).
$$

Из включений \eqref{1}, этих равенств и лемм 16, 17, 18 следует
\begin{multline*}
$$
F'=(F^0_I\wedge F^1_J)\vee(F^1_I\wedge F^0_J)\in
\left(\mathfrak{N}(U_I^0)\wedge\mathfrak{N}(U_J^1)\right)\vee
\left(\mathfrak{N}(U_I^1)\wedge\mathfrak{N}(U_J^0)\right)
$$ \\
$$
=\left(\mathfrak{N}(U_{Z,I}^{1,0})\wedge\mathfrak{N}(U_{Z,J}^{1,1})\right)\vee
\left(\mathfrak{N}(U_{Z,I}^{1,1})\wedge\mathfrak{N}(U_{Z,J}^{1,0})\right)
$$ \\
$$
\subseteq \mathfrak{N}(U_{Z,I}^{1,0}\cup U_{Z,J}^{1,1})\vee
\mathfrak{N}(U_{Z,I}^{1,1}\cup U_{Z,J}^{1,0})
$$ \\
$$
\subseteq\mathfrak{N}(U_{Z,I}^{1,0}\cup U_{Z,J}^{1,1}\cup
U_{Z,I}^{1,1}\cup U_{Z,J}^{1,0})\subseteq \mathfrak{N}(U).
$$
\end{multline*}
Включение $F'\in\mathfrak{N}(U)$ по определению и означает, что $U$
является представлением формулы $F'$. Случай
$F\in\mathbb{P}^1_\vee(I,J)$ рассмотрен.


Необходимое условие теоремы 1 доказано.






%%------ 5.
\section{Доказательство достаточного условия теоремы 1}


Для доказательства потребуются понятия простого двойного разреза
$\Pi$-разбиения и его матрицы. Поэтому сначала сформулируем
приведённые в \cite{8} определения этих понятий и некоторые
связанные с ними утверждения.

{\it Двойным разрезом} прямоугольника $P\in\mathrm{REC}^n$
называется такая четвёрка  прямоугольников
$C=\{C_1,C_2,C_3,C_4\}\subseteq\mathrm{REC}(P)$, что для некоторого
вертикального разреза $A=\{A_1,A_2\}$ и некоторого горизонтального
разреза $B=\{B_1,B_2\}$ этого прямоугольника справедливо равенство
$C=\{A_1\cap B_1,A_1\cap B_2,A_2\cap B_1,A_2\cap B_2\}$. При этом
разрезы $A$ и $B$ называются {\it разрезами, порождающими двойной
разрез} $C$; а двойной разрез $C$ -- {\it порождённым разрезами} $A$
и $B$. Входящие в $C$ прямоугольники называются {\it компонентами}
двойного разреза $C$. Составленная из его компонент матрица
$$
\mathrm{M}(C)=\left(
\begin{array}{cc}
A_1\cap B_1 & A_1\cap B_2 \\
A_2\cap B_1 & A_2\cap B_2 \\
\end{array}
\right)
$$
называется {\it матрицей двойного разреза} $C$.

Очевидно для любого двойного разреза $C$ прямоугольника
$P\in\mathrm{REC}^n$ существует единственный порождающий $C$
вертикальный разрез $A$ и единственный порождающий $C$
горизонтальный разрез $B$ этого прямоугольника.

Заметим, что любые две различные компоненты двойного разреза $C$
тогда и только тогда являются горизонтально соседними
прямоугольниками, когда они находятся в одной строке, и тогда и
только тогда являются вертикально соседними прямоугольниками, когда
они находятся в одном столбце матрицы $\mathrm{M}(C)$. При этом
объединение находящихся в одной строке компонент $C$ есть компонента
порождающего $C$ вертикального разреза $A$, и объединение
находящихся в одном столбце компонент $C$ есть компонента
порождающего $C$ горизонтального разреза $B$.

Заметим также, что матрица двойного разреза определена не
однозначно. Очевидно любая перестановка её строк и столбцов приводит
к матрице, которая также является матрицей того же двойного разреза.
И любые две матрицы одного и того же двойного разреза отличаются
только перестановкой строк и столбцов. В этом смысле равенство
$\mathrm{M}(C)=M$ означает, что $M$ это одна из четырёх возможных
матриц двойного разреза $C$. Каждую из этих четырёх матриц будем
называть также {\it конкретной} матрицей двойного разреза $C$.


{\it Двойным разрезом гиперблока} $P\in\mathcal{H}(U)$
$\Pi$-разбиения $U\in\Pi^n$ называется такой двойной разрез
прямоугольника $P$, что все его компоненты являются гиперблоками
$\Pi$-разбиения $U$.

{\it Двойным разрезом} $\Pi$-{\it разбиения} $U\in\Pi^n$ называется
любой двойной разрез главного гиперблока $\widehat{U}$ этого
$\Pi$-разбиения.

Очевидно вертикальный и горизонтальный разрезы, порождающие двойной
разрез гиперблока являются соответственно вертикальным и
горизонтальным разрезами этого гиперблока. А вертикальный и
горизонтальный разрезы, порождающие двойной разрез $\Pi$-разбиения
являются соответственно вертикальным и горизонтальным разрезами
этого $\Pi$-разбиения.


Прямоугольники $P_1,P_2\in\mathrm{REC}^n$ называются {\it
горизонтально} ({\it вертикально}) {\it смежными}, если вертикальные
(горизонтальные) их стороны имеют непустое пересечение.

Гиперблоки $P,K\in\mathcal{H}(U)$ $\Pi$-разбиения $U\in\Pi^n$
называются {\it взаимно простыми}, если либо они являются
горизонтально соседними и любые два блока $Q\subseteq P$ и
$T\subseteq K$ этого $\Pi$-разбиения являются горизонтально смежными
прямоугольниками; либо они являются вертикально соседними и любые
два блока $Q\subseteq P$ и $T\subseteq K$ этого $\Pi$-разбиения
являются вертикально смежными прямоугольниками.

Двойной разрез гиперблока $\Pi$-разбиения $U\in\Pi^n$ называется
{\it простым}, если любые две соседние компоненты этого разреза
являются взаимно простыми гиперблоками  $\Pi$-разбиения $U$.

Двойной разрез $\Pi$-разбиения $U\in\Pi^n$ называется {\it простым},
если он является простым двойным разрезом главного гиперблока
$\widehat{U}$ этого $\Pi$-разбиения.

Для произвольных $\Pi$-разбиения $U\in\Pi^n$ и его двойного разреза
$C$ определим порождаемые ими классы формул $\mathbb{L}_\vee(U,C)$ и
$\mathbb{L}_\wedge(U,C)$. Для этого сначала для произвольной
конкретной матрицы
$$
M=\left(
\begin{array}{cc}
M_{1,1} & M_{1,2} \\
M_{2,1} & M_{2,2} \\
\end{array}
\right),
$$
двойного разреза $C$ определим классы формул
$\mathbb{L}_\vee(U,C,M)$ и $\mathbb{L}_\wedge(U,C,M)$ следующими
равенствами:
$$
\mathbb{L}_\vee(U,C,M)=\bigl(\mathfrak{N}(U|M_{1,1})\wedge\mathfrak{N}(U|M_{2,1})\bigl)\vee
\bigl(\mathfrak{N}(U|M_{1,2})\wedge\mathfrak{N}(U|M_{2,2})\bigl),
$$
$$
\mathbb{L}_\wedge(U,C,M)=\bigl(\mathfrak{N}(U|M_{1,1})\vee\mathfrak{N}(U|M_{1,2})\bigl)\wedge
\bigl(\mathfrak{N}(U|M_{2,1})\vee\mathfrak{N}(U|M_{2,2})\bigl).
$$

Как уже было отмечено, любая другая конкретная матрица $M'$ двойного
разреза $C$ отличаются от $M$ только перестановкой строк и столбцов.
Поэтому любая формула из класса $\mathbb{L}_\vee(U,C,M)$
$\Pi$-эквивалентна некоторой формуле из класса
$\mathbb{L}_\vee(U,C,M')$. И наоборот любая формула из класса
$\mathbb{L}_\vee(U,C,M')$ $\Pi$-эквивалентна некоторой формуле из
класса $\mathbb{L}_\vee(U,C,M)$. Следовательно справедливо равенство
$$
\overline{\mathbb{L}_\vee(U,C,M)}=\overline{\mathbb{L}_\vee(U,C,M')}.
$$
И точно также по той же причине справедливо равенство
$$
\overline{\mathbb{L}_\wedge(U,C,M)}=\overline{\mathbb{L}_\wedge(U,C,M')}.
$$
Эти равенства обосновывают корректность определения классов
$\mathbb{L}_\vee(U,C)$ и $\mathbb{L}_\wedge(U,C)$ следующими
равенствами:
$$
\mathbb{L}_\vee(U,C)=\overline{\mathbb{L}_\vee(U,C,M)} \ \ \ \ \
{\mbox и} \ \ \ \ \
\mathbb{L}_\wedge(U,C)=\overline{\mathbb{L}_\wedge(U,C,M)}.
$$



%%---Теорема 3.
\begin{theorem}
Если $\Pi$-разбиение $U\in\Pi^n$ имеет простой
двойной разрез $C$, то для класса порождаемых $U$ формул справедливо
равенство
\begin{equation}\label{2}
\mathfrak{N}(U)=\mathbb{L}_\vee(U,C)\cup\mathbb{L}_\wedge(U,C).
\end{equation}
\end{theorem}

\begin{proof}
Теорема 3 опирается на следующие очевидные
свойства замыканий классов формул.


%%---Предложение 3.
\begin{proposition}
Для любых трёх классов формул $N, N_1, N_2\subseteq\mathfrak{N}$ из
равенства $N=N_1\cup N_2$ следует равенство
$\overline{N}=\overline{N_1}\cup \overline{N_2}$.
\end{proposition}


%%---Предложение 4.
\begin{proposition}
Для любых двух классов формул $N_1, N_2\subseteq\mathfrak{N}$
справедливы равенства $\overline{N_1\vee N_2}=\overline{N_2\vee
N_1}$ и $\overline{N_1\wedge N_2}=\overline{N_2\wedge N_1}$.
\end{proposition}


%%---Предложение 5.
\begin{proposition}
Для любых трёх классов формул $N, N_1, N_2\subseteq\mathfrak{N}$ из
равенства $N=N_1\vee N_2$ следует равенство
$\overline{N}=\overline{\overline{N_1}\vee \overline{N_2}}$.
\end{proposition}


Кроме того для доказательства теоремы 3 потребуются две леммы.
Следующая лемма доказана в \cite{7}.


%%---Лемма 20.
\begin{lemma}
Для любого $\Pi$-разбиения $V\in\Pi^n$ класс формул
$\mathfrak{N}(V)$ является замкнутым относительно
$\Pi$-эквивалентности.
\end{lemma}



%%---Лемма 21.
\begin{lemma}
Для любого $\Pi$-разбиения $Y\in\Pi^n$ справедливо утверждение: если
$Y$ имеет вертикальный разрез $A=\{A_1,A_2\}$, компоненты которого
являются взаимно простыми гиперблоками $Y$, то для класса
порождаемых $Y$ формул справедливо равенство
$$
\mathfrak{N}(Y)=\overline{\mathfrak{N}(Y|A_1)\wedge\mathfrak{N}(Y|A_2)}.
$$
\end{lemma}

\begin{proof}
Заметим, что из взаимной простоты гиперблоков $A_1$ и $A_2$
очевидным образом следует отсутствие горизонтальных разрезов у
$\Pi$-разбиения $Y$. Следовательно по определению класса формул
$\mathfrak{N}_\vee(Y)$ справедливо равенство
$\mathfrak{N}_\vee(Y)=\emptyset$. Значит, по определению класса
формул $\mathfrak{N}(Y)$ справедливо равенство
$$
\mathfrak{N}(Y)=\mathfrak{N}_\vee(Y)\cup\mathfrak{N}_\wedge(Y)=\mathfrak{N}_\wedge(Y).
$$
Поэтому по определению классов формул $\mathfrak{N}_\wedge(Y)$ и
$\mathfrak{M}_\wedge(U,A_1,A_2)$ имеем
$$
\mathfrak{N}(Y)=\mathfrak{N}_\wedge(Y)
\supseteq\mathfrak{M}_\wedge(U,A_1,A_2)=\mathfrak{N}(Y|A_1)\wedge\mathfrak{N}(Y|A_2).
$$
Отсюда в силу леммы 20 следует включение
$\mathfrak{N}(Y)\supseteq\overline{\mathfrak{N}(Y|A_1)\wedge\mathfrak{N}(Y|A_2)}$.


Обратное включение
$\mathfrak{N}(Y)\subseteq\overline{\mathfrak{N}(Y|A_1)\wedge\mathfrak{N}(Y|A_2)}$
докажем индукцией по $|\mathrm{C}_v(Y)|$, т. е. по числу
вертикальных разрезов $\Pi$-разбиения $Y$.

Пусть $|\mathrm{C}_v(Y)|=1$. Тогда по лемме 20, по определению
класса формул $\mathfrak{N}_\wedge(Y)$, по предложению 3, по
определению классов формул $\mathfrak{M}_\wedge(Y,A_1,A_2)$,
$\mathfrak{M}_\wedge(Y,A_2,A_1)$ и по предложению 4 имеем
\begin{multline*}
$$
\mathfrak{N}(Y)=\overline{\mathfrak{N}(Y)}=\overline{\mathfrak{N}_\wedge(Y)}
$$ \\
$$
=\overline{\mathfrak{M}_\wedge(Y,A_1,A_2)\cup\mathfrak{M}_\wedge(Y,A_2,A_1)}
=\overline{\mathfrak{M}_\wedge(Y,A_1,A_2)}\cup\overline{\mathfrak{M}_\wedge(Y,A_2,A_1)}
$$ \\
$$
=\overline{\mathfrak{N}(Y|A_1)\wedge\mathfrak{N}(Y|A_2)}\cup\overline{\mathfrak{N}(Y|A_2)\wedge\mathfrak{N}(Y|A_1)}
=\overline{\mathfrak{N}(Y|A_1)\wedge\mathfrak{N}(Y|A_2)}.
$$
\end{multline*}


Пусть $m>1$ и для любого $\Pi$-разбиения $Y\in\Pi^n$ при
$|\mathrm{C}_v(Y)|\leq m$ утверждение леммы 21 уже доказано. Докажем
его для произвольного $\Pi$-разбиения $Y\in\Pi^n$ при
$|\mathrm{C}_v(Y)|=m+1$.

Рассмотрим произвольную формулу $F$ из класса
$\mathfrak{N}(Y)=\mathfrak{N}_\wedge(Y)$. По определению
$\mathfrak{N}_\wedge(Y)$ существует такой вертикальный разрез
$P=\{P_1,P_2\}$ $\Pi$-разбиения $Y$, что
$F\in\mathfrak{M}_\wedge(Y,P_1,P_2)$. Возможны три случая:

1) $P=A$,

2) одна из компонент разреза $P$ содержит одну из компонент разреза
$A$ и $P\neq A$,

3) каждая компонента разреза $P$ имеет непустое пересечение с каждой
компонентой разреза $A$.

Если $P=A$, то по определению классов
$\mathfrak{M}_\wedge(Y,A_1,A_2)$, $\mathfrak{M}_\wedge(Y,A_2,A_1)$ и
по предложению 4 имеем
$$
F\in\mathfrak{M}_\wedge(Y,P_1,P_2)\subseteq\mathfrak{M}_\wedge(Y,A_1,A_2)\cup\mathfrak{M}_\wedge(Y,A_2,A_1)
$$
$$
\subseteq
\overline{\mathfrak{N}(Y|A_1)\wedge\mathfrak{N}(Y|A_2)}\cup\overline{\mathfrak{N}(Y|A_2)\wedge\mathfrak{N}(Y|A_1)}
=\overline{\mathfrak{N}(Y|A_1)\wedge\mathfrak{N}(Y|A_2)}.
$$
Что и требовалось доказать.


Рассмотрим второй случай. По определению класса
$\mathfrak{M}_\wedge(Y,P_1,P_2)$ для формулы $F$ существуют такие
формулы $F_1\in\mathfrak{N}(Y|P_1)$ и $F_2\in\mathfrak{N}(Y|P_2)$,
что $F=(F_1\wedge F_2)$. Без ограничения общности полагаем
$P_1\supset A_1$. Через $T_2$ обозначим прямоугольник $P_1\cap A_2$.
Тогда очевидно пара прямоугольников $\{A_1,T_2\}$ является
вертикальным разрезом $\Pi$-разбиения $Y_1=Y|P_1$, а компоненты
$A_1$ и $T_2$ этого разреза являются взаимно простыми гиперблоками
$Y_1$. Кроме того очевидно справедливо неравенство
$|\mathrm{C}_v(Y_1)|\leq|\mathrm{C}_v(Y)|-1=m$. Следовательно по
предположению индукции справедливо включение
$\mathfrak{N}(Y_1)\subseteq\overline{\mathfrak{N}(Y_1|A_1)\wedge\mathfrak{N}(Y_1|T_2)}$.
Значит, в силу очевидных равенств $Y_1|A_1=Y|A_1$ и $Y_1|T_2=Y|T_2$
для формулы $F_1$ существуют такие формулы
$F'_1\in\mathfrak{N}(Y|A_1)$ и $F'_2\in\mathfrak{N}(Y|T_2)$, что
$F_1$ $\Pi$-эквивалентна формуле $(F'_1\wedge F'_2)$. Поэтому
формула $F=(F_1\wedge F_2)$ $\Pi$-эквивалентна формуле
$F'=((F'_1\wedge F'_2)\wedge F_2)$. Отсюда в силу
$\Pi$-эквивалентности формул $F'$ и $F''=(F'_1\wedge(F'_2\wedge
F_2))$ следует $\Pi$-эквивалентность формул $F$ и $F''$.

Очевидно пара прямоугольников $\{T_2,P_2\}$ является вертикальным
разрезом гиперблока $A_2$ $\Pi$-разбиения $Y$. А, значит, эта пара
прямоугольников является и вертикальным разрезом $\Pi$-разбиения
$Y_2=Y|A_2$. Поэтому из включений $F'_2\in\mathfrak{N}(Y|T_2)$,
$F_2\in\mathfrak{N}(Y|P_2)$ и очевидных равенств $Y|T_2=Y_2|T_2$,
$Y|P_2=Y_2|P_2$, $Y_2|A_2=Y|A_2$ следует
\begin{multline*}
$$
(F'_2\wedge F_2)\in\mathfrak{N}(Y|T_2)\wedge\mathfrak{N}(Y|P_2)=
\mathfrak{N}(Y_2|T_2)\wedge\mathfrak{N}(Y_2|P_2)
$$ \\
$$
=\mathfrak{M}_\wedge(Y_2,T_2,P_2)\subseteq\mathfrak{N}(Y_2|A_2)=\mathfrak{N}(Y|A_2).
$$
\end{multline*}
Значит, из $F'_1\in\mathfrak{N}(Y|A_1)$ следует включение
$F''\in\mathfrak{N}(Y|A_1)\wedge\mathfrak{N}(Y|A_2)$. Из этого
включения и $\Pi$-эквивалентности формул $F$ и $F''$ следует
$F\in\overline{\mathfrak{N}(Y|A_1)\wedge\mathfrak{N}(Y|A_2)}$. Что и
требовалось доказать.

Третий случай рассматривается аналогично второму. Лемма 21 доказана.
\end{proof}



Теперь опираясь на предложения 3, 4, 5 и леммы 20 и 21 докажем
теорему 3.

В силу леммы 20 и предложения 3 из выполненного по определению
класса формул $\mathfrak{N}(U)$ равенства
$\mathfrak{N}(U)=\mathfrak{N}_\vee(U)\cup\mathfrak{N}_\wedge(U)$
следует
$$
\mathfrak{N}(U)=
\overline{\mathfrak{N}(U)}=\overline{\mathfrak{N}_\vee(U)}\cup\overline{\mathfrak{N}_\wedge(U)}.
$$
Поэтому чтобы доказать равенство \eqref{2}, достаточно доказать
следующие два равенства:
\begin{equation}\label{3}
\overline{\mathfrak{N}_\vee(U)}=\mathbb{L}_\vee(U,C) \ \ \ {\mbox и}
\ \ \ \overline{\mathfrak{N}_\wedge(U)}=\mathbb{L}_\wedge(U,C).
\end{equation}

Докажем первое из равенств \eqref{3}.

Через $A=\{A_1,A_2\}$ и $B=\{B_1,B_2\}$ обозначим порождающие
простой двойной разрез $C$ соответственно вертикальный и
горизонтальный разрезы $\Pi$-разбиения $U$. Тогда по определению
матрицей двойного разреза $C$ является матрица
$$
M=\left(
\begin{array}{cc}
M_{1,1} & M_{1,2} \\
M_{2,1} & M_{2,2} \\
\end{array}
\right)= \left(
\begin{array}{cc}
A_1\cap B_1 & A_1\cap B_2 \\
A_2\cap B_1 & A_2\cap B_2 \\
\end{array}
\right)
$$
Из взаимной простоты соседних компонент $C$ очевидным образом
следует, что  $A$ и $B$ являются единственными соответственно
вертикальным и горизонтальным разрезами $\Pi$-разбиения $U$.
Следовательно по определению класса формул $\mathfrak{N}_\vee(U)$
справедливо равенство
$$
\mathfrak{N}_\vee(U)=\mathfrak{M}_\vee(U,B_1,B_2)\cup
\mathfrak{M}_\vee(U,B_2,B_1).
$$
В силу предложения 4 из выполненных по определению классов формул
$\mathfrak{M}_\vee(U,B_1,B_2)$ и $\mathfrak{M}_\vee(U,B_2,B_1)$
равенств
\begin{equation}\label{4}
\mathfrak{M}_\vee(U,B_1,B_2)=\mathfrak{N}(U|B_1)\vee\mathfrak{N}(U|B_2),
\end{equation}
$$
\mathfrak{M}_\vee(U,B_2,B_1)=\mathfrak{N}(U|B_2)\vee\mathfrak{N}(U|B_1).
$$
следует равенство
$\overline{\mathfrak{M}_\vee(U,B_1,B_2)}=\overline{\mathfrak{M}_\vee(U,B_2,B_1)}$.
Отсюда в силу предложения 3 следует
\begin{equation}\label{5}
\overline{\mathfrak{N}_\vee(U)}=\overline{\mathfrak{M}_\vee(U,B_1,B_2)\cup
\mathfrak{M}_\vee(U,B_2,B_1)}=\overline{\mathfrak{M}_\vee(U,B_1,B_2)}.
\end{equation}

Очевидно стоящие в первом и втором столбцах матрицы $M$ пары
прямоугольников $\{A_1\cap B_1, A_2\cap B_1\}$ и $\{A_1\cap B_2,
A_2\cap B_2\}$ являются вертикальными разрезами $\Pi$-разбиений
соответственно $U|B_1$ и $U|B_2$, и компоненты этих разрезов
являются взаимно простыми гиперблоками этих $\Pi$-разбиений. Поэтому
в силу леммы 21 справедливы равенства
\begin{equation}\label{6}
\mathfrak{N}(U|B_1)=\overline{\bigl(\mathfrak{N}(U|M_{1,1})\wedge\mathfrak{N}(U|M_{2,1})\bigl)},
\end{equation}
\begin{equation}\label{7}
\mathfrak{N}(U|B_2)=\overline{\bigl(\mathfrak{N}(U|M_{1,2})\wedge\mathfrak{N}(U|M_{2,2})\bigl)}.
\end{equation}
По определению классов формул $\mathbb{L}_\vee(U,C,M)$ и
$\mathbb{L}_\vee(U,C)$ справедливы равенства
\begin{equation}\label{8}
\bigl(\mathfrak{N}(U|M_{1,1})\wedge\mathfrak{N}(U|M_{2,1})\bigl)\vee
\bigl(\mathfrak{N}(U|M_{1,2})\wedge\mathfrak{N}(U|M_{2,2})\bigl)=\mathbb{L}_\vee(U,C,M),
\end{equation}
\begin{equation}\label{9}
\overline{\mathbb{L}_\vee(U,C,M)}=\mathbb{L}_\vee(U,C).
\end{equation}

Из равенств \eqref{5}, \eqref{4}, \eqref{6}, \eqref{7}, \eqref{8},
\eqref{9} и предложения 5 следует
\begin{multline*}
$$
\overline{\mathfrak{N}_\vee(U)}=\overline{\mathfrak{M}_\vee(U,B_1,B_2)}=
\overline{\mathfrak{N}(U|B_1)\vee\mathfrak{N}(U|B_2)}
$$ \\
$$
=\overline{\overline{\bigl(\mathfrak{N}(U|M_{1,1})\wedge\mathfrak{N}(U|M_{2,1})\bigl)}\vee
\overline{\bigl(\mathfrak{N}(U|M_{1,2})\wedge\mathfrak{N}(U|M_{2,2})\bigl)}}
$$ \\
$$
=\overline{\mathbb{L}_\vee(U,C,M)}=\mathbb{L}_\vee(U,C)
$$
\end{multline*}
Первое из равенств \eqref{3} доказано. Второе доказывается
аналогично. Теорема 3 доказана.
\end{proof}


В \cite{8} установлена справедливость следующего утверждения.


%%---Лемма 22.
\begin{lemma}
Любое совершенное $\Pi$-разбиение любого не являющегося элементарным
линейного прямоугольника $L\in\mathrm{REC}^n$ имеет единственный
двойной разрез. Он является простым. Существует такое разбиение
$\{I,J\}$ множества образующих прямоугольника $L$, что матрица
$$
\left(
\begin{array}{cc}
L\cap\Phi_I^0 & L\cap\Phi_J^{\delta\oplus1} \\
L\cap\Phi_J^\delta &  L\cap\Phi_I^1 \\
\end{array}
\right)
$$
является матрицей этого двойного разреза.
\end{lemma}



Теперь, используя теорему 3 и лемму 22, докажем достаточное условие
теоремы 1. А именно покажем, что для любой имеющей совершенное
представление на собственном прямоугольнике функции
$f^\delta_Z(x_1,\dots,x_n)$ формулы $F\in\mathfrak{N}$ справедливо
включение $F\in\mathbb{P}^\delta_Z$. Доказательство проведём
индукцией по $|Z|$.

При $|Z|=1$ для собственного прямоугольника $\Phi_Z^\delta$ функции
$f_Z^\delta$ справедливо равенство
$\Phi_Z^\delta=\mathrm{X}_i^\delta$, $i\in Z$. Очевидно
$\mathrm{X}_i^\delta$ содержит только те рёбра куба $\mathrm{B}^n$,
которые принадлежат множеству $\mathrm{R}_i^\delta$. И при этом
$\mathrm{R}_i^\delta$ является диагональю этого прямоугольника.
Поэтому существует единственное совершенное $\Pi$-разбиение $W$
этого прямоугольника. Оно состоит из единственного блока
$\mathrm{X}_i^\delta$. Следовательно множество $\mathfrak{N}(W)$
состоит из единственной формулы $F=x_i^\delta$. Включение
$F\in\mathbb{P}_Z^\delta$ для этой формулы справедливо по
определению класса формул $\mathbb{P}_Z^\delta$, $Z=\{i\}$.

Пусть $m>1$. Предположим, что при $1\leq|Z|\leq m-1$ для любой
имеющей совершенное представление на прямоугольнике $\Phi_Z^\delta$
формулы $F\in\mathfrak{N}$ справедливо включение
$F\in\mathbb{P}^\delta_Z$. Покажем, что тогда то же самое
справедливо и при $|Z|=m$.

Пусть $|Z|=m$ и $F\in\mathfrak{N}$ -- произвольная имеющая
совершенное представление на прямоугольнике $\Phi_Z^\delta$ формула.
Это представление обозначим через $W$. По определению $W$ является
совершенным $\Pi$-разбиением $\Phi_Z^\delta$ и справедливо включение
$F\in\mathfrak{N}(W)$. Из леммы 22 следует, что $\Pi$-разбиение $W$
имеет единственный двойной разрез. Обозначим его $C$. По той же
лемме 22 он является простым. Значит, по теореме 3 из включения
$F\in\mathfrak{N}(W)$ следует $
F\in\mathbb{L}_\vee(W,C)\cup\mathbb{L}_\wedge(W,C). $

Рассмотрим случай $F\in\mathbb{L}_\vee(W,C)$. Случай
$F\in\mathbb{L}_\wedge(W,C)$ рассматривается аналогично.

Пусть $\{I,J\}$ такое существующее по лемме 22 разбиение множества
$Z$ образующих прямоугольника $\Phi_Z^\delta$, что матрица
$$
M=\left(
\begin{array}{cc}
M_{1,1} & M_{1,2} \\
M_{2,1} & M_{2,2} \\
\end{array}
\right) =\left(
\begin{array}{cc}
\Phi_Z^\delta\cap\Phi_I^0 & \Phi_Z^\delta\cap\Phi_J^{\delta\oplus1} \\
\Phi_Z^\delta\cap\Phi_J^\delta &  \Phi_Z^\delta\cap\Phi_I^1 \\
\end{array}
\right)= \left(
\begin{array}{cc}
\Phi_{Z,I}^{\delta,0} & \Phi_{Z,J}^{\delta,\delta\oplus1} \\
\Phi_{Z,J}^{\delta,\delta} &  \Phi_{Z,I}^{\delta,1} \\
\end{array}
\right)
$$
является матрицей двойного разреза $C$. Тогда по определению класса
формул $\mathbb{L}_\vee(W,C)$ формула $F$ $\Pi$-эквивалентна
некоторой формуле $F'$ из класса $\mathbb{L}_\vee(W,C,M)$. Поэтому и
в силу того, что класс формул $\mathbb{P}^\delta_Z$ замкнут
относительно $\Pi$-эквивалентности, для доказательства включения
$F\in\mathbb{P}^\delta_Z$ достаточно доказать включение
$F'\in\mathbb{P}^\delta_Z$. Докажем его.

Через $V_{Z,I}^{\delta,0}$, $V_{Z,I}^{\delta,1}$,
$V_{Z,J}^{\delta,0}$, $V_{Z,J}^{\delta,1}$ обозначим сужения
соответственно
$$
W|\Phi_{Z,I}^{\delta,0}, \ \ \ \ W|\Phi_{Z,I}^{\delta,1}, \ \ \ \
W|\Phi_{Z,J}^{\delta,0}, \ \ \ \ W|\Phi_{Z,J}^{\delta,1}
$$
совершенного $\Pi$-разбиения $W$ на являющиеся элементами матрицы
$M$ прямоугольники соответственно $\Phi_{Z,I}^{\delta,0}$,
$\Phi_{Z,I}^{\delta,1}$, $\Phi_{Z,J}^{\delta,0}$,
$\Phi_{Z,J}^{\delta,1}$. Поскольку элементы матрицы $M$ являются
гиперблоками $W$, все эти сужения являются совершенными
$\Pi$-разбиениями соответствующих прямоугольников. Следовательно по
теореме 2 существуют изоморфные им совершенные $\Pi$-разбиения
соответственно $U_I^0$, $U_I^1$, $U_J^0$, $U_J^1$ прямоугольников
соответственно $\Phi_I^0$, $\Phi_I^1$, $\Phi_J^0$, $\Phi_J^1$.
Значит, по лемме 19 справедливы равенства
$$
\mathfrak{N}(V_{Z,I}^{\delta,0})=\mathfrak{N}(U_I^0), \ \
\mathfrak{N}(V_{Z,I}^{\delta,1})=\mathfrak{N}(U_I^1), \ \
\mathfrak{N}(V_{Z,J}^{\delta,0})=\mathfrak{N}(U_J^0), \ \
\mathfrak{N}(V_{Z,J}^{\delta,1})=\mathfrak{N}(U_J^1).
$$
Кроме того, в силу неравенств $1\leq|I|\leq m$ и $1\leq|J|\leq m-1$
по предположению индукции справедливы включения
$$
\mathfrak{N}(U_I^0)\subseteq\mathbb{P}_I^0, \ \ \
\mathfrak{N}(U_I^1)\subseteq\mathbb{P}_I^1, \ \ \
\mathfrak{N}(U_J^0)\subseteq\mathbb{P}_J^0, \ \ \
\mathfrak{N}(U_J^1)\subseteq\mathbb{P}_J^1.
$$
Отсюда по определению класса формул $\mathbb{L}_\vee(W,C,M)$ и
классов формул $\mathbb{PL}_\vee^\delta(I,J)$, $\mathbb{P}_Z^\delta$
следует
\begin{multline*}
$$
F'\in\mathbb{L}_\vee(W,C,M)=
\bigl(\mathfrak{N}(U|M_{1,1})\wedge\mathfrak{N}(U|M_{2,1})\bigl)\vee
\bigl(\mathfrak{N}(U|M_{1,2})\wedge\mathfrak{N}(U|M_{2,2})\bigl)
$$ \\
$$
=\bigl(\mathfrak{N}(V_{Z,I}^{\delta,0})\wedge\mathfrak{N}(V_{Z,J}^{\delta,\delta})\bigl)\vee
\bigl(\mathfrak{N}(V_{Z,J}^{\delta,\delta\oplus1}\wedge\mathfrak{N}(V_{Z,I}^{\delta,1})\bigl)
$$ \\
$$
= \bigl(\mathfrak{N}(U_I^0)\wedge\mathfrak{N}(U_J^\delta)\bigl)\vee
\bigl(\mathfrak{N}(U_J^{\delta\oplus1})\wedge\mathfrak{N}(U_I^1)\bigl)
$$ \\
$$
\subseteq(\mathbb{P}_I^0\wedge\mathbb{P}_J^\delta)\vee
(\mathbb{P}_J^{\delta\oplus1}\wedge\mathbb{P}_I^1)
=\mathbb{PL}_\vee^\delta(I,J)\subseteq\mathbb{P}_Z^\delta.
$$
\end{multline*}
Включение $F'\in\mathbb{P}^\delta_Z$ доказано. Достаточное условие
теоремы 1 доказано.





\bigskip
\begin{thebibliography}{9} % Ссылки на литературу приводятся только на английском языке (даже если у источника нет англоязычной версии).


\bibitem{1} S. V. Yablonskii,
{\it Realization of a linear function in the class of
$\pi$-circuits}, Dokl. Akad. Nauk SSSR, Nov. Ser., \textbf{94}:5,
(1954), 805--806.

\bibitem{2} V. M. Khrapchenko,
{\it Complexity of the realization of a linear function in the class
of $\Pi$-circuits}, Mat. Zametki, \textbf{9}:1 (1971), 35--40.

\bibitem{3} V. M. Khrapchenko,
{\it A method of determining lower bounds for the complexity of
$\Pi$-schemes}, Mat. Zametki, \textbf{10}:1, (1971), 83--92.


\bibitem{4} V. M. Khrapchenko,
\href{https://doi.org/10.4213/dm1236}{\it A simplified proof of a
lower complexity estimate}, Discrete Mathematics, \textbf{25}:2,
(2013), 82--84.

\bibitem{5} D. Yu. Cherukhin,
{\it To the question of a logical representation for the parity
counter}, Neform. Nauka \textbf{2}, (2009), 14--23.

\bibitem{6} K. L. Rychkov,
\href{ https://doi.org/10.33048/daio.2019.26.662}{\it Complexity of
the realization of a linear boolean function in the class of
$\pi$-schemes}, Diskretn. Anal. Issled. Oper., \textbf{25}:3,
(2018), 36--94.

\bibitem{7} K. L. Rychkov,
\href{https://doi.org/10.33048/daio.2022.29.751}{\it Representations
of normalized formulas}, Diskretn. Anal. Issled. Oper.,
\textbf{29}:4, (2022), 77--103.

\bibitem{8} K. L. Rychkov,
\href{https://doi.org/10.33048/semi.2023.20.093}{\it On the
structure of one class of perfect $\Pi$-partitions}, Siberian
Electronic Mathematical Reports, \textbf{20}:2, (2023), 1499--1518.

\bibitem{9} Yu. A. Kombarov, {\it On minimal realizations of linear boolean functions}, Diskretn. Anal. Issled. Oper.,
\textbf{19}:3, (2012), 39--57.

\end{thebibliography}
\end{document}
