ins-kurs4.tex

   1 \subsubsection{íÏÄÅÌØ ÐÒÏÇÒÁÍÍ}
   2
   3 \paragraph{ðÁÒÁÍÅÔÒÙ ÍÏÄÅÌÉ ÐÒÏÇÒÁÍÍ}
   4 \newcommand*{\Ac}{\Sigma}
   5 \newcommand*{\Bc}{T}
   6 \newcommand*{\Cc}{\Atoms_T}
   7 æÉËÓÉÒÕÅÍ Ä×Á ËÏÎÅÞÎÙÈ ÁÌÆÁ×ÉÔÁ:
   8 $\Ac$~"---  \emph{ÂÁÚÏ×ÙÈ ÏÐÅÒÁÔÏÒÏ×}
   9 ($\size{\Ac} = \sym r$),
  10 ${\Bc}$~"--- \emph{ÂÁÚÏ×ÙÈ ÔÅÓÔÏ×}
  11 ($\size{\Bc} = \sym k$).
  12 %% éÈ ÜÌÅÍÅÎÔÙ ÂÕÄÅÍ ÏÂÏÚÎÁÞÁÔØ, ÓÏÏÔ×ÅÔÓÔ×ÅÎÎÏ,
  13 %% $\sym{a_1},\dotsc,\sym{a_r}$ É $\sym{p_1},\dotsc,\sym{p_k}$.
  14
  15 éÓÈÏÄÑ ÉÚ ×ÙÂÒÁÎÎÏÇÏ ÍÎÏÖÅÓÔ×Á ÐÒÅÄÉËÁÔÏ×, ÏÐÒÅÄÅÌÉÍ ÍÎÏÖÅÓÔ×Ï~$\Cc$
  16 \emph{ÂÕÌÅ×ÙÈ ÁÔÏÍÏ×}:
  17 \begin{equation}
  18   \label{eq:conditions}
  19   \Cc \eqdef
  20   \left\{ c \mid c\colon \Bc \to \{ \False, \True \}\right\}.
  21 \end{equation}
  22 âÕÌÅ× ÁÔÏÍ ÓÏÐÏÓÔÁ×ÌÑÅÔ ËÁÖÄÏÍÕ ÔÅÓÔÕ ÚÎÁÞÅÎÉÅ
  23 ÉÓÔÉÎÎÏÓÔÉ.
  24
  25 \newcommand*{\atomLe}{\olessthan}
  26 íÙ ÂÕÄÅÍ ÉÓÐÏÌØÚÏ×ÁÔØ ÞÁÓÔÉÞÎÙÊ ÐÏÒÑÄÏË $\atomLe$ ÎÁ ÕÓÌÏ×ÉÑÈ, ËÏÔÏÒÙÊ
  27 ÏÐÒÅÄÅÌÑÅÔÓÑ ÅÓÔÅÓÔ×ÅÎÎÙÍ ÏÂÒÁÚÏÍ: ÄÌÑ $c_1, c_2$,
  28 $c_1, c_2 \in \Cc$,
  29 \begin{equation}
  30   \label{eq:cond-order}
  31   c_1 \atomLe c_2 \equivdef
  32   \forall p \in \Bc\colon c_1(p) \atomLe c_2(p).
  33 \end{equation}
  34
  35 \subsubsection{óÉÎÔÁËÓÉÓ}
  36 ðÒÉ ÏÐÒÅÄÅÌÅÎÉÉ ÓÉÎÔÁËÓÉÓÁ ÐÒÏÇÒÁÍÍ ÂÕÄÅÍ
  37 ÐÏÌØÚÏ×ÁÔØÓÑ ÓÐÅÃÉÁÌØÎÙÍ ÚÎÁËÏÍ $\Exit$, ÏÂÝÉÍ ÄÌÑ ×ÓÅÈ ÐÒÏÇÒÁÍÍ.
  38
  39
  40 (\emph{äÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÏÊ ÏÐÅÒÁÔÏÒÎÏÊ ÐÒÏÐÏÚÉÃÉÏÎÁÌØÎÏÊ})
  41 \emph{ÐÒÏÇÒÁÍÍÏÊ} ÎÁÄ ÁÌÆÁ×ÉÔÁÍÉ
  42 $\Ac$, $\Bc$ ÎÁÚÏ×£Í ËÏÎÅÞÎÕÀ ÐÏÍÅÞÅÎÎÕÀ ÓÉÓÔÅÍÕ ÐÅÒÅÈÏÄÏ×
  43 $\pi$, ÇÄÅ $\piForm{}$ É
  44 \begin{itemize}
  45 \item
  46 $\Vc$~"--- ÍÎÏÖÅÓÔ×Ï \emph{ÐÒÅÏÂÒÁÚÏ×ÁÔÅÌÅÊ} ÐÒÏÇÒÁÍÍÙ,
  47 %
  48 \item
  49 $\Entry$, $\Entry\in \Vc$,~"--- \emph{×ÈÏÄÎÁÑ} ÔÏÞËÁ ÐÒÏÇÒÁÍÍÙ,
  50 %
  51 \item
  52 $T\colon \Vc\times\Cc \to \Vc \cup \{\Exit\}$~"---
  53 \emph{ÆÕÎËÃÉÑ ÐÅÒÅÈÏÄÏ×},
  54 %
  55 \item
  56 $B\colon \Vc \to \Ac$~"--- \emph{ÆÕÎËÃÉÑ ÐÒÉ×ÑÚËÉ}
  57 (ÏÐÅÒÁÔÏÒÏ× Ë ÐÒÅÏÂÒÁÚÏ×ÁÔÅÌÑÍ).
  58 %
  59 \end{itemize}
  60 %
  61 $\Exit$ ÂÕÄÅÍ ÎÁÚÙ×ÁÔØ \emph{×ÙÈÏÄÎÏÊ} ÔÏÞËÏÊ (ÌÀÂÏÊ ÐÒÏÇÒÁÍÍÙ).
  62 ÷ÏÏÂÝÅ, ÄÁÌÅÅ (ÄÌÑ ËÒÁÔËÏÓÔÉ) \emph{ÔÏÞËÁÍÉ} ÐÒÏÇÒÁÍÍÙ ÂÕÄÅÍ ÎÁÚÙ×ÁÔØ
  63 $\Exit$ ÉÌÉ ÌÀÂÏÊ Å£
  64 ÐÒÅÏÂÒÁÚÏ×ÁÔÅÌØ. (äÌÑ ÐÒÏÇÒÁÍÍÙ~$\pi$ ÕËÁÚÁÎÎÏÇÏ ×ÉÄÁ
  65 ÍÎÏÖÅÓÔ×Ï ÔÏÞÅË ÜÔÏ $\Vc \cup \{\Exit\}$.)
  66
  67 $\size{\pi}$~"--- \emph{ÒÁÚÍÅÒ} ÐÒÏÇÒÁÍÍÙ~$\pi$:
  68 $\size{\pi} \eqdef \size{\Vc}$.
  69 úÁÍÅÔÉÍ, ÞÔÏ ÉÚ ÏÐÒÅÄÅÌÅÎÉÑ ÓÌÅÄÕÅÔ, ÞÔÏ
  70 ËÏÌÉÞÅÓÔ×Ï ÐÅÒÅÈÏÄÏ× × $\pi$ ÒÁ×ÎÏ $\size{\pi}\cdot\size{\Cc} =
  71 \size{\pi}2^{\sym{k}}$.
  72
  73 \subsubsection{óÅÍÁÎÔÉËÁ}%ÐÒÏÇÒÁÍÍ.
  74 åÓÔØ ÏÂÝÉÊ ÐÏÄÈÏÄ Ë ÚÁÄÁÎÉÀ ÏÐÅÒÁÃÉÏÎÎÏÊ ÓÅÍÁÎÔÉËÉ
  75 ÄÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÙÈ ÏÐÅÒÁÔÏÒÎÙÈ ÐÒÏÐÏÚÉÃÉÏÎÁÌØÎÙÈ
  76 ÐÒÏÇÒÁÍÍ~"--- ÓÒÅÄÓÔ×ÁÍÉ \tND{ÄÉÎÁÍÉÞÅÓËÉÈ ÛËÁÌ} É
  77 \tND{ÄÉÎÁÍÉÞÅÓËÉÈ ÍÏÄÅÌÅÊ}. íÙ ËÏÒÏÔËÏ ÏÐÉÛÅÍ ÅÇÏ.
  78
  79 ðÏÔÏÍ ÍÙ ÓÕÚÉÍ ÏÂÌÁÓÔØ ÓÅÍÁÎÔÉËÉ ÄÌÑ ÒÁÓÓÍÁÔÒÉ×ÁÅÍÙÈ ÐÒÏÇÒÁÍÍ; ÓÕÖÅÎÉÅ
  80 ÂÕÄÅÔ ÓÏÏÔ×ÅÔÓÔ×Ï×ÁÔØ ÐÅÒÅÈÏÄÕ Ë ÔÏÌØËÏ ÐÒÏÇÒÁÍÍÁÍ ÓÏ ÓÅÍÁÎÔÉÞÅÓËÉÍÉ Ó×ÏÊÓÔ×ÁÍÉ
  81 \tND{ÐÅÒÅÓÔÁÎÏ×ÏÞÎÏÓÔÉ} É \tND{ÍÏÎÏÔÏÎÎÏÓÔÉ} ÏÐÅÒÁÔÏÒÏ×.
  82
  83 \paragraph{äÉÎÁÍÉÞÅÓËÉÅ ÛËÁÌÙ É ÍÏÄÅÌÉ.}
  84 %
  85 \emph{äÉÎÁÍÉÞÅÓËÏÊ ÛËÁÌÏÊ} ÎÁÄ ÁÌÆÁ×ÉÔÏÍ ÂÁÚÏ×ÙÈ
  86 ÏÐÅÒÁÔÏÒÏ×~$\Ac$ ÎÁÚÙ×ÁÅÔÓÑ ÌÀÂÁÑ ÔÒÏÊËÁ
  87 $\Fc = \langle S, \boldsymbol{s_0}, Q \rangle$, ÓÏÓÔÏÑÝÁÑ ÉÚ
  88 \begin{itemize}
  89 \item ÎÅÐÕÓÔÏÇÏ ÍÎÏÖÅÓÔ×Á \emph{ÓÏÓÔÏÑÎÉÊ} $S$,
  90 \item \emph{ÎÁÞÁÌØÎÏÇÏ ÓÏÓÔÏÑÎÉÑ} $\boldsymbol{s_0} \in S$,
  91 \item ÆÕÎËÃÉÉ \emph{ÐÒÅÏÂÒÁÚÏ×ÁÎÉÑ} $Q\colon S \times \Ac \to S$.
  92 \end{itemize}
  93 \begin{justification}
  94   ôÁËÏÅ ÏÐÒÅÄÅÌÅÎÉÅ~"--- ÁÂÓÔÒÁËÃÉÑ ×ÁÖÎÙÈ ÓÏÓÔÁ×ÌÑÀÝÉÈ ÒÅÁÌØÎÙÈ
  95   ×ÙÞÉÓÌÅÎÉÊ:
  96   ÍÎÏÖÅÓÔ×Ï ÓÏÓÔÏÑÎÉÊ ÓÏÏÔ×ÅÔÓÔ×ÕÅÔ ×ÏÚÍÏÖÎÙÍ
  97   ÓÏÓÔÏÑÎÉÑÍ ÐÁÍÑÔÉ ×ÙÞÉÓÌÉÔÅÌØÎÏÊ ÍÁÛÉÎÙ;
  98   ÐÒÅÏÂÒÁÚÏ×ÁÎÉÅ, Ó×ÑÚÁÎÎÏÅ Ó ÏÐÅÒÁÔÏÒÏÍ,~"---
  99   ÄÅÊÓÔ×ÉÀ ÎÁ ËÁÖÄÏÍ ÓÏÓÔÏÑÎÉÉ ÐÁÍÑÔÉ
 100   (ËÁËÉÍ ÓÔÁÎÅÔ ÓÏÓÔÏÑÎÉÅ ÐÁÍÑÔÉ ÐÏÓÌÅ ÉÓÐÏÌÎÅÎÉÑ ÏÐÅÒÁÔÏÒÁ).
 101   ðÒÉ ÜÔÏÍ ×ÎÕÔÒÅÎÎÅÅ ÕÓÔÒÏÊÓÔ×Ï ÐÁÍÑÔÉ É ÒÅÁÌØÎÙÈ ÏÐÅÒÁÔÏÒÏ× ÎÁÐÒÑÍÕÀ
 102   ÎÉËÁË ÎÅ ÏÐÉÓÙ×ÁÅÔÓÑ.
 103 \end{justification}
 104 %
 105 æÕÎËÃÉÀ ÐÒÅÏÂÒÁÚÏ×ÁÎÉÑ $Q$ ÍÏÖÎÏ ÒÁÓÐÒÏÓÔÒÁÎÉÔØ ÅÓÔÅÓÔ×ÅÎÎÙÍ ÏÂÒÁÚÏÍ
 106 ÎÁ ×ÓÅ ÃÅÐÏÞËÉ $\Ac^*$ ÂÁÚÏ×ÙÈ ÏÐÅÒÁÔÏÒÏ×, ÐÏÌÁÇÁÑ $Q^*(s,\lambda)=s$
 107 (ÐÕÓÔÁÑ ÃÅÐÏÞËÁ)
 108 É $Q^*(s,ta)=Q(Q^*(s,t),a)$ ÄÌÑ ×ÓÑËÉÈ $a \in \Ac$, $t \in \Ac^*$.
 109
 110 íÙ ÇÏ×ÏÒÉÍ. ÞÔÏ ÓÏÓÔÏÑÎÉÅ $s''$ \emph{ÄÏÓÔÉÖÉÍÏ} ÉÚ $s'$, ÅÓÌÉ
 111 $s''=Q^*(s',t)$ ÄÌÑ ÎÅËÏÔÏÒÏÇÏ $t \in \Ac^*$ ($s'$ ÐÒÅÏÂÒÁÚÕÅÔÓÑ × $s''$
 112 ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÙÍ ÐÒÉÍÅÎÅÎÉÅÍ ËÁËÉÈ-ÔÏ ÂÁÚÏ×ÙÈ ÏÐÅÒÁÔÏÒÏ×).
 113
 114 \emph{(äÅÔÅÒÍÉÎÉÒÏ×ÁÎÎÏÊ) ÄÉÎÁÍÉÞÅÓËÏÊ ÍÏÄÅÌØÀ} ÎÁÄ ÁÌÆÁ×ÉÔÁÍÉ $\Ac$ É
 115 $\Bc$ ÎÁÚÙ×ÁÅÔÓÑ ÌÀÂÁÑ ÐÁÒÁ ×ÉÄÁ $\langle \Fc,
 116 \val\rangle$, ÔÁËÁÑ, ÞÔÏ
 117 %
 118 \begin{itemize}
 119 \item $\Fc=\langle S,\boldsymbol{s_0},Q\rangle$~"--- ÛËÁÌÁ ÎÁÄ $\Ac$,
 120 %
 121 \item $\val\colon S \to \Cc$.
 122 \end{itemize}
 123 ôÁËÉÅ $\val$ ÎÁÚÙ×ÁÀÔ
 124 \emph{ÏÃÅÎËÁÍÉ}%
 125 \footnote{\emph{ïÃÅÎËÁ}~"--- ÜÔÏ ÐÒÏÓÔÏ
 126   ÔÅÒÍÉÎ. úÎÁÞÅÎÉÅ ÒÕÓÓËÏÇÏ ÓÌÏ×Á \emph{ÏÃÅÎËÁ} ÓÌÁÂÏ Ó×ÑÚÁÎÏ ÐÏ
 127   ÓÍÙÓÌÕ Ó ÏÐÒÅÄÅÌÑÅÍÙÍ ÐÏÎÑÔÉÅÍ.}
 128 (ËÁË ×ÉÄÎÏ, ÜÔÏ ÆÕÎËÃÉÉ, ÐÒÉÄÁÀÝÉÅ ÚÎÁÞÅÎÉÑ
 129 ÐÒÅÄÉËÁÔÁÍ × ËÁÖÄÏÍ ÓÏÓÔÏÑÎÉÉ $s$, $s \in S$).
 130
 131 \paragraph{÷ÙÞÉÓÌÅÎÉÑ ÐÒÏÇÒÁÍÍ.}\label{def:run}
 132 \emph{÷ÙÞÉÓÌÅÎÉÅ ÐÒÏÇÒÁÍÍÙ~$\pi$}, $\piForm{}$, ÎÁ ÍÏÄÅÌÉ~$\langle \Fc, \val \rangle$~"---
 133 ÜÔÏ ËÏÎÅÞÎÁÑ ÉÌÉ ÂÅÓËÏÎÅÞÎÁÑ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ ÔÒÏÅË, ÏÂÏÚÎÁÞÁÅÍÁÑ $\Run(\pi,\langle \Fc, \val \rangle)$,
 134 ×ÉÄÁ\marginpar{$s_0, \initR$?}
 135 \begin{equation}\label{eq:simple-run}
 136   s_0\initR v_1,
 137   s_1 \xrightarrow{c_1} v_2, \dotsc
 138   ,s_{i-1} \xrightarrow{c_{i-1}} v_i,\dotsc \: ,
 139 \end{equation}
 140 × ËÏÔÏÒÏÊ $v_i \in \Vc$, $c_i \in \Cc$, $s_i \in S$
 141 É ËÏÔÏÒÕÀ ÍÙ ÓÔÒÏÉÍ ÐÏ ÔÁËÉÍ ÐÒÁ×ÉÌÁÍ:
 142 %
 143 \begin{itemize}
 144 \item
 145   ×ÓÅÇÄÁ ÔÏÞËÁ $v_1$ ÅÓÔØ  $\Entry$,
 146   Á ÓÏÓÔÏÑÎÉÅ~$s_0$ ÅÓÔØ ÎÁÞÁÌØÎÏÅ
 147   ÓÏÓÔÏÑÎÉÅ~$\boldsymbol{s_0}$ ÛËÁÌÙ~$\Fc$;
 148 %
 149 \item
 150   É ÄÁÌØÛÅ ÄÌÑ ËÁÖÄÏÇÏ $i$, ${i \ge 1}$
 151   \begin{itemize}
 152   \item
 153     åÓÌÉ $v_{i} = \Exit$, ÔÏ $i$ ÏËÁÚÙ×ÁÅÔÓÑ
 154     ÎÏÍÅÒÏÍ ÐÏÓÌÅÄÎÅÇÏ ÜÌÅÍÅÎÔÁ É ÍÙ ÔÏÇÄÁ ÇÏ×ÏÒÉÍ,
 155     ÞÔÏ $\Run$ \emph{ÚÁ×ÅÒÛÁÅÔÓÑ Ó ÒÅÚÕÌØÔÁÔÏÍ} $s_{i-1}$.
 156   \item åÓÌÉ $v_{i} \neq \Exit$, ÔÏ ÍÙ "<ÓÏ×ÅÒÛÁÅÍ ÓÌÅÄÕÀÝÉÊ ÛÁÇ
 157   ×ÙÞÉÓÌÅÎÉÑ">:
 158   $s_{i} = Q(s_{i-1},[B(v_{i})])$.
 159   $c_i = \val(s_i)$, $v_{i+1} = T(v_i, c_i)$.
 160   \end{itemize}
 161 \end{itemize}
 162 åÓÌÉ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ ÏËÁÚÙ×ÁÅÔÓÑ ÂÅÓËÏÎÅÞÎÏÊ, ÔÏ ÍÙ ÇÏ×ÏÒÉÍ, ÞÔÏ
 163 $\Run$ \emph{ÚÁÃÉËÌÉ×ÁÅÔÓÑ} É ÒÅÚÕÌØÔÁÔ ÎÅÏÐÒÅÄÅÌ£Î.
 164
 165 \begin{justification}
 166   ÷ÙÂÏÒ ÛËÁÌÙ, ÎÁ ËÏÔÏÒÏÊ ÂÕÄÕÔ ÏÓÎÏ×ÁÎÙ ×ÙÞÉÓÌÅÎÉÑ ÒÁÓÓÍÁÔÒÉ×ÁÅÍÙÈ
 167   ÐÒÏÇÒÁÍÍ, ÓÏÏÔÎÏÓÉÔÓÑ ÓÏ Ó×ÏÊÓÔ×ÁÍÉ ÒÅÁÌØÎÙÈ ÏÐÅÒÁÔÏÒÏ×, ËÏÔÏÒÙÅ
 168   ÍÏÇÕÔ ÂÙÔØ ÉÓÐÏÌØÚÏ×ÁÎÙ ÐÒÉ ÎÁÐÉÓÁÎÉÉ ÒÅÁÌØÎÙÈ ÐÒÏÇÒÁÍÍ. ðÏÜÔÏÍÕ
 169   ÛËÁÌÁ ×ÙÂÉÒÁÅÔÓÑ ÏÄÎÁ ÎÁ ×ÓÅ ÐÒÏÇÒÁÍÍÙ. äÉÎÁÍÉÞÅÓËÁÑ ÖÅ ÍÏÄÅÌØ
 170   ÓÏÏÔ×ÅÔÓÔ×ÕÅÔ
 171   ×ÈÏÄÎÙÍ ÄÁÎÎÙÍ, ÎÁ ËÏÔÏÒÙÈ ÍÙ ÚÁÐÕÓËÁÅÍ ËÁÖÄÕÀ ÏÔÄÅÌØÎÕÀ
 172   ÐÒÏÇÒÁÍÍÕ. íÎÏÖÅÓÔ×Ï ÍÏÄÅÌÅÊ ÓÏÏÔ×ÅÔÓÔ×ÕÅÔ ×ÏÚÍÏÖÎÙÍ ÐÏ×ÅÄÅÎÉÑÍ
 173   ÍÏÄÅÌÉÒÕÅÍÙÈ ÒÅÁÌØÎÙÈ ÐÒÏÇÒÁÍÍ ÎÁ ×ÓÅ×ÏÚÍÏÖÎÙÈ ×ÈÏÄÎÙÈ ÄÁÎÎÙÈ.
 174 \end{justification}
 175 \bigskip
 176
 177 ôÁËÉÍÉ ÖÅ ÓÒÅÄÓÔ×ÁÍÉ ÏÐÉÓÙ×ÁÌÁÓØ É ÓÅÍÁÎÔÉËÁ ÐÒÏÇÒÁÍÍ ×
 178 ÐÒÅÄÛÅÓÔ×ÕÀÝÉÈ ÒÁÂÏÔÁÈ,
 179 ÎÁÐÒÉÍÅÒ~\cite{zakh-length-preserv}, ÇÄÅ ÂÙÌ ÐÒÅÄÌÏÖÅÎ ÓÐÏÓÏÂ
 180 ÐÏÓÔÒÏÅÎÉÑ ÒÁÚÒÅÛÁÀÝÅÇÏ ÜË×É×ÁÌÅÎÔÎÏÓÔØ ÐÒÏÇÒÁÍÍ ÁÌÇÏÒÉÔÍÁ,
 181 ÐÒÉÍÅÎ£ÎÎÙÊ É × ÜÔÏÊ ÒÁÂÏÔÅ.\marginpar{ÇÄÅ ÓÍ. ÐÏÄÒÏÂÎÅÅ?}
 182
 183 äÁÌØÛÅ ÜÔÉ ÓÒÅÄÓÔ×Á ÂÕÄÕÔ ÐÒÉÍÅÎÑÔØÓÑ ÄÌÑ ÏÐÉÓÁÎÉÑ ÐÒÏÇÒÁÍÍ Ó
 184 ÓÅÍÁÎÔÉËÏÊ, ÏÂÌÁÄÁÀÝÅÊ ÎÅËÏÔÏÒÙÍÉ ÓÐÅÃÉÁÌØÎÙÍÉ Ó×ÏÊÓÔ×ÁÍÉ.
 185
 186 \paragraph{ëÏÍÍÕÔÁÔÉ×ÎÏÓÔØ.}
 187 äÌÑ ÆÉËÓÉÒÏ×ÁÎÎÏÇÏ ÁÌÆÁ×ÉÔÁ~$\Ac$
 188 ×ÏÚØÍ£Í ÏÄÎÕ ËÏÎËÒÅÔÎÕÀ ÛËÁÌÕ~"--- \tING{ËÏÍÍÕÔÁÔÉ×ÎÕÀ ÛËÁÌÕ} $\CommF$,
 189 $\CommF = \langle S, \nullVect, Q \rangle$:
 190 \begin{itemize}
 191 \item
 192 ÍÎÏÖÅÓÔ×Ï
 193 \emph{ÓÏÓÔÏÑÎÉÊ}~$S$ ÅÓÔØ
 194 $\Nzr$, ÇÄÅ $\Nz \eqdef \mathbb N \cup \{ 0 \}$;
 195 \item
 196 \emph{ÎÁÞÁÌØÎÏÅ ÓÏÓÔÏÑÎÉÅ}~"--- ÎÕÌÅ×ÏÊ
 197 ×ÅËÔÏÒ~$\nullVect$;
 198 \item
 199 ÏÂÏÚÎÁÞÉÍ $[\sym a_j]$ ÅÄÉÎÉÞÎÙÊ ×ÅËÔÏÒ
 200 Ó $j$\nobreakdash-ÏÊ ÅÄÉÎÉÞÎÏÊ ËÏÍÐÏÎÅÎÔÏÊ, É ÏÐÒÅÄÅÌÉÍ \emph{ÐÒÅÏÂÒÁÚÏ×ÁÎÉÅ}
 201 ÓÏÓÔÏÑÎÉÑ $s\in S$ ÏÐÅÒÁÔÏÒÏÍ $\sym a_j$
 202 ËÁË ÓÌÏÖÅÎÉÅ:
 203 \begin{equation}
 204   \label{eq:comm-update}
 205   Q(s,\sym a_j) \eqdef (s+[\sym a_j]).
 206 \end{equation}
 207 %
 208 \end{itemize}
 209
 210 ÷ÙÞÉÓÌÅÎÉÑ ×ÓÅÈ ÒÁÓÓÍÁÔÒÉ×ÁÅÍÙÈ ÐÒÏÇÒÁÍÍ ÏÓÎÏ×Ù×ÁÀÔÓÑ
 211 ÎÁ ÜÔÏÊ ÛËÁÌÅ~$\CommF$.
 212 \begin{justification}
 213 ôÁË ÉÚ ×ÓÅÈ ×ÏÚÍÏÖÎÙÈ ÓÅÍÁÎÔÉË ÐÒÏÇÒÁÍÍ ÍÙ ×ÙÂÒÁÌÉ ÓÅÍÁÎÔÉËÕ ÐÒÏÇÒÁÍÍ Ó
 214 \tING{ÐÅÒÅÓÔÁÎÏ×ÏÞÎÙÍÉ} ÏÐÅÒÁÔÏÒÁÍÉ, Ô.Å. ÔÁËÉÈ, ÞÔÏ
 215 ÒÅÚÕÌØÔÉÒÕÀÝÅÅ ÐÒÅÏÂÒÁÚÏ×ÁÎÉÅ ÃÅÐÏÞËÏÊ
 216 ÏÐÅÒÁÔÏÒÏ× ÎÅ ÚÁ×ÉÓÉÔ ÏÔ ÐÏÒÑÄËÁ ÏÐÅÒÁÔÏÒÏ× × ÎÅÊ. åÓÌÉ ÏÂÒÁÔÉÔØÓÑ Ë ÒÅÁÌØÎÙÍ
 217 ×ÙÞÉÓÌÅÎÉÑÍ, ÔÏ ÜÔÏ Ó×ÏÊÓÔ×Ï ÍÏÖÎÏ ÐÏÎÑÔØ ËÁË ÍÏÄÅÌØ ÔÏÇÏ, ÞÔÏ
 218 ÏÐÅÒÁÔÏÒÙ ÒÁÂÏÔÁÀÔ Ó ÎÅÚÁ×ÉÓÉÍÙÍÉ ÏÂÌÁÓÔÑÍÉ ÐÁÍÑÔÉ É, ÓÔÁÌÏ ÂÙÔØ,
 219 ÉÈ ÄÅÊÓÔ×ÉÑ ÎÅ ×ÌÉÑÀÔ ÄÒÕÇ ÎÁ ÄÒÕÇÁ.
 220 \end{justification}
 221
 222 ïÔÎÏÛÅÎÉÅ \emph{ÄÏÓÔÉÖÉÍÏÓÔÉ} ×Ï ××ÅÄ£ÎÎÏÊ ÛËÁÌÅ $\CommF$ ÓÏ
 223 ÎÁ ÍÎÏÖÅÓÔ×Å ÓÏÓÔÏÑÎÉÊ
 224 $S$, ËÁË ÓÌÅÄÕÅÔ ÉÚ ÏÐÒÅÄÅÌÅÎÉÊ, ÓÏ×ÐÁÄÁÅÔ Ó
 225 ÅÓÔÅÓÔ×ÅÎÎÙÍ ÏÔÎÏÛÅÎÉÅÍ ÞÁÓÔÉÞÎÏÇÏ ÐÏÒÑÄËÁ ÎÁ $\Nzr$.
 226
 227 \paragraph{íÏÎÏÔÏÎÎÏÓÔØ.} âÕÄÅÍ ÄÏÐÕÓËÁÔØ ÄÉÎÁÍÉÞÅÓËÉÅ ÍÏÄÅÌÉ
 228 ÔÏÌØËÏ ÉÚ ÔÁËÏÇÏ ÐÏÄÍÎÏÖÅÓÔ×Á~$\CommMonM$ ÍÎÏÖÅÓÔ×Á~$\Mc_{\CommF}$:
 229 \begin{equation*}
 230   \label{eq:monot-model}
 231 \CommMonM \eqdef \left\{
 232   \val\colon S \to \Cc
 233   \mid
 234   \text{$\val$ ÍÏÎÏÔÏÎÎÁÑ}
 235 \right\},
 236   \text{ ÇÄÅ }
 237 \end{equation*}
 238 \begin{multline}
 239   \label{eq:monot-valuation}
 240   \val\colon S \to \Cc
 241   \text{ ÍÏÎÏÔÏÎÎÁÑ}
 242   \equivdef\\
 243   \forall s_1,s_2\in S\colon
 244   s_1 \atomLe s_2 \implies
 245   \val(s_1) \atomLe \val(s_2).\hfil
 246 \end{multline}
 247 %
 248 \begin{note}
 249 ÷ÏÚØÍ£Í ÌÀÂÕÀ ÐÒÏÇÒÁÍÍÕ~$\pi$
 250 É ÌÀÂÕÀ ÍÏÄÅÌØ
 251 $\langle \CommF, \val \rangle$ Ó ÍÏÎÏÔÏÎÎÏÊ
 252 ÏÃÅÎËÏÊ.
 253 ÷ ÓÏÏÔ×ÅÔÓÔ×ÉÉ Ó ÄÁÎÎÙÍ ÏÐÒÅÄÅÌÅÎÉÅÍ
 254 ÅÓÌÉ ×
 255 ×ÙÞÉÓÌÅÎÉÉ~$\Run(\pi,\langle \Fc_\text, \val \rangle)$ ÎÁ ËÁËÏÍ-ÔÏ ÛÁÇÅ ËÁËÏÍÕ-ÔÏ
 256 ÐÒÅÄÉËÁÔÕ ÂÙÌÏ ÄÁÎÏ ÚÎÁÞÅÎÉÅ~$1$, ÔÏ É ÎÁ ÐÏÓÌÅÄÕÀÝÉÈ
 257 ÛÁÇÁÈ ÅÍÕ ÂÕÄÅÔ ÄÁ×ÁÔØÓÑ ÚÎÁÞÅÎÉÅ~$1$.
 258 \end{note}
 259
 260 ðÒÏÇÒÁÍÍÙ Ó ÓÅÍÁÎÔÉËÏÊ ÏÓÎÏ×ÁÎÎÏÊ ÎÁ $\CommF$ É Ó ÍÎÏÖÅÓÔ×ÏÍ ÄÏÐÕÓÔÉÍÙÈ
 261 ÄÉÎÁÍÉÞÅÓËÉÈ ÍÏÄÅÌÅÊ $\CommMonM$ ÍÙ É ÎÁÚÙ×ÁÅÍ \tING{ÐÒÏÇÒÁÍÍÁÍÉ Ó
 262   ÐÅÒÅÓÔÁÎÏ×ÏÞÎÙÍÉ É ÍÏÎÏÔÏÎÎÙÍÉ ÏÐÅÒÁÔÏÒÁÍÉ}. ÷ÙÞÉÓÌÅÎÉÅ ÐÒÏÇÒÁÍÍÙ ÎÁ
 263 ÍÏÄÅÌÉ $\langle \CommF, \val \rangle$ ÄÁÌØÛÅ ÂÕÄÅÍ ËÏÒÏÔËÏ ÎÁÚÙ×ÁÔØ
 264 ×ÙÞÉÓÌÅÎÉÅÍ ÎÁ $\val$.
 265
 266 \subsection{ðÒÏÂÌÅÍÁ ÜË×É×ÁÌÅÎÔÎÏÓÔÉ.}
 267 ðÒÏÇÒÁÍÍÙ $\pi\pNo{1}$ É $\pi\pNo{2}$ ÎÁÚÏ×£Í
 268 %
 269 \begin{itemize}
 270 \item
 271 \emph{ÜË×É×ÁÌÅÎÔÎÙÍÉ ÎÁ ÏÃÅÎËÅ~$\val \in \Mc$},
 272 ÅÓÌÉ ÒÅÚÕÌØÔÁÔÙ ×ÙÞÉÓÌÅÎÉÊ $\Run(\pi\pNo{1},\val)$ É $\Run(\pi\pNo{2},\val)$
 273 ÏÄÉÎÁËÏ×Ù\marginpar{ÓÏ×ÐÁÄÁÀÔ~"--- ÏÔÌÉÞÁÅÔÓÑ?},
 274 Ô.Å.\ ÌÉÂÏ ÏÂÁ ×ÙÞÉÓÌÅÎÉÑ ÚÁÃÉËÌÉ×ÁÀÔÓÑ,
 275 ÌÉÂÏ ÏÂÁ ÚÁ×ÅÒÛÁÀÔÓÑ Ó ÏÄÎÉÍ É ÔÅÍ ÖÅ ÒÅÚÕÌØÔÁÔÏÍ
 276 (ÏÂÏÚÎ.: $\pi\pNo{1} \Equiv_{\val} \pi\pNo{2}$);
 277 %
 278 \item
 279 \emph{ÜË×É×ÁÌÅÎÔÎÙÍÉ ÎÁ $\CommMonM$} (ÉÌÉ
 280 ÐÒÏÓÔÏ \emph{ÜË×É×ÁÌÅÎÔÎÙÍÉ}),
 281 ÅÓÌÉ ${\forall\val\in\CommMonM\colon {\pi\pNo{1} \Equiv_{\val}
 282     \pi\pNo{2}}}$
 283 \sloppy
 284 (ÏÂÏÚÎ.: $\pi\pNo{1} \Equiv \pi\pNo{2}$).
 285 \label{def:equivalence}
 286 \end{itemize}
 287 %
 288 \emph{ðÒÏÂÌÅÍÁ ÜË×É×ÁÌÅÎÔÎÏÓÔÉ} ÄÌÑ ÄÁÎÎÙÈ $\Ac$, $\Bc$ ÓÏÓÔÏÉÔ ×
 289 ÔÏÍ, ÞÔÏÂÙ ÐÒÏ×ÅÒÉÔØ ÄÌÑ ÐÒÏÉÚ×ÏÌØÎÏÊ ÐÁÒÙ $\pi\pNo{1}$, $\pi\pNo{2}$,
 290 ×ÅÒÎÏ ÌÉ, ÞÔÏ ${\pi\pNo{1} \Equiv_{\CommMonM} \pi\pNo{2}}$.
 291
 292
 293 %%% Local Variables:
 294 %%% mode: latex
 295 %%% TeX-master: "main"
 296 %%% End: