\input style
\chapter{3 harakteristika semantiki}

nAS INTERESUYUT PREIMUSHCHESTVENNO TAKIE SISTEMY,
KOTORYE, PRISTUPIV K RABOTE V NEKOEM "NACHALXNOM
SOSTOYANII", ZAVERSHAT EE V KAKOM-TO "KONECHNOM
SOSTOYANII", KOTOROE, KAK PRAVILO, ZAVISIT OT
VYBORA NACHALXNOGO SOSTOYANIYA. eTOT PODHOD NESKOLXKO
OTLICHAETSYA OT KONCEPCII AVTOMATA S KONECHNYM CHISLOM
SOSTOYANIJ, KOTORYJ, S ODNOJ STORONY, VOSPRINIMAET
POTOK VHODNYH SIMVOLOV, A S DRUGOJ STORONY,
POROZHDAET POTOK VYHODNYH SIMVOLOV. chTOBY PEREVESTI
|TO V NASHU SHEMU, MY DOLZHNY  PREDPOLOZHITX, CHTO
ZNACHENIE VHODA (T. E. ARGUMENT) oTRAZHAETSYA V
VYBORE NACHALXNOGO SOSTOYANIYA I CHTO ZNACHENIE VYHODA
(T. E. OTVET) OTRAZHAETSYA V VYBORE KONECHNOGO
SOSTOYANIYA. nASH PODHOD IZBAVLYAET NAS OT
VSEVOZMOZHNYH NEPRINCIPIALXNYH SLOZHNOSTEJ.

pERVAYA CHASTX |TOJ GLAVY POSVYASHCHENA POCHTI ISKLYUCHITELXNO
TAK NAZYVAEMYM "DETERMINIROVANNYM MASHINAM", TOGDA
KAK VO VTOROJ CHASTI (KOTORUYU MOZHNO PROPUSTITX PRI
PERVOM CHTENII) RECHX IDET O TAK NAZYVAEMYH
"NEDETERMINIROVANNYH MASHINAH". rAZLICHIE MEZHDU
|TIMI DVUMYA PONYATIYAMI SOSTOIT  V TOM, CHTO DLYA
DETERMINIROVANNOJ MASHINY SOBYTIE, KOTOROE
PROIZOJDET POSLE ZAPUSKA KONSTRUKCII, POLNOSTXYU
OPREDELYAETSYA EE NACHALXNYM SOSTOYANIEM. eSLI ONA
ZAPUSKAETSYA DVAZHDY V ODINAKOVYH NACHALXNYH
SOSTOYANIYAH, TO PROIZOJDUT ODINAKOVYE SOBYTIYA:
POVEDENIE DETERMINIROVANNOJ MASHINY POLNOSTXYU
VOSPROIZVODIMO. dLYA NEDETERMINIROVANNOJ MASHINY,
NAPROTIV, ZAPUSK V ZADANNOM NACHALXNOM SOSTOYANII
PRIVEDET K KAKOMU-TO ODNOMU SOBYTIYU IZ KLASSA
VOZMOZHNYH SOBYTIJ; NACHALXNOE SOSTOYANIE TOLXKO
FIKSIRUET |TOT KLASS V CELOM.

tEPERX YA PREDPOLAGAYU, CHTO PROEKTIROVANIE TAKOJ SISTEMY
YAVLYAETSYA CELENAPRAVLENNOJ DEYATELXNOSTXYU, T. E. MY
ZHELAEM DOSTICHX CHEGO-TO S POMOSHCHXYU |TOJ SISTEMY.
nAPRIMER, ESLI MY HOTIM SOZDATX MASHINU, SPOSOBNUYU
VYCHISLYATX NAIBOLXSHIJ OBSHCHIJ DELITELX, TO MOZHEM
POTREBOVATX, CHTOBY KONECHNOE SOSTOYANIE
UDOVLETVORYALO USLOVIYU
$$
x=\nod(X, Y) \eqno(1)
$$
v RASSMOTRENNOJ RANEE MASHINE MY BUDEM IMETX TAKZHE
$y=\nod(X, Y)$, POTOMU CHTO IGRA ZAKANCHIVAETSYA PRI
$x=y$, NO |TO OTNYUDX NE CHASTX NASHIH TREBOVANIJ,
KOGDA MY RESHAEM PRINYATX KONECHNOE ZNACHENIE $x$ V
KACHESTVE OTVETA.

mY NAZYVAEM USLOVIE (1) (ZHELAEMYM) "POSTUSLOVIEM" --- "POST", POTOMU CHTO 
ONO NALAGAETSYA NA TO SOSTOYANIE, V KOTOROM SISTEMA DOLZHNA OKAZATXSYA
\emph{POSLE} SVOEJ RABOTY. zAMETIM, CHTO
POSTUSLOVIE MOZHET UDOVLETVORYATXSYA MNOGIMI
VOZMOZHNYMI SOSTOYANIYAMI. v TAKOM SLUCHAE MY
ESTESTVENNO SCHITAEM KAZHDOE IZ NIH ODINAKOVO
UDOVLETVORITELXNYM, TAK CHTO NET OSNOVANIJ
TREBOVATX, CHTOBY KONECHNOE SOSTOYANIE BYLO
ODNOZNACHNOJ FUNKCIEJ OT NACHALXNOGO SOSTOYANIYA.
(chITATELX UVIDIT IZ DALXNEJSHEGO, CHTO IMENNO ZDESX
PROYAVLYAETSYA POTENCIALXNAYA POLEZNOSTX
NEDETERMINIROVANNOGO USTROJSTVA.)

dLYA TOGO CHTOBY ISPOLXZOVATX |TU MASHINU, KOGDA MY
HOTIM POLUCHITX OT NEE OTVET (NAPRIMER, HOTIM
"CHTOBY ONA DOSTIGLA KONECHNOGO SOSTOYANIYA,
UDOVLETVORYAYUSHCHEGO POSTUSLOVIYU (1) DLYA ZADANNOGO
NABORA ZNACHENIJ $X$ I $Y$"), NAM ZHELATELXNO ZNATX
MNOZHESTVO SOOTVETSTVUYUSHCHIH NACHALXNYH SOSTOYANIJ, A
BOLEE TOCHNO, MNOZHESTVO TAKIH NACHALXNYH SOSTOYANIJ,
PRI KOTORYH ZAPUSK OBYAZATELXNO PRIVEDET K SOBYTIYU
PRAVILXNOGO ZAVERSHENIYA PRICHEM SISTEMA OSTANETSYA V
KONECHNOM SOSTOYANII, UDOVLETVORYAYUSHCHEM POSTUSLOVIYU.
eSLI MY MOZHEM PRIVESTI SISTEMU BEZ VYCHISLITELXNYH
USILIJ V ODNO IZ TAKIH SOSTOYANIJ, TO MY UZHE ZNAEM,
KAK ISPOLXZOVATX |TU SISTEMU DLYA POLUCHENIYA
ZHELAEMOGO OTVETA. pRIVEDEM PRIMER DLYA EVKLIDOVOJ
IGRY NA KARTONE: MY MOZHEM GARANTIROVATX KONECHNOE
SOSTOYANIE, UDOVLETVORYAYUSHCHEE POSTUSLOVIYU (1) DLYA
LYUBOGO NACHALXNOGO SOSTOYANIYA, UDOVLETVORYAYUSHCHEGO
USLOVIYU
$$
\nod(x,y)=\nod(h,Y) \and 0<x\le500 \and 0<y\le 500
\eqno(2)
$$
(vERHNIE GRANICY DOBAVLENY, CHTOBY UCHESTX
OGRANICHENNYJ RAZMER LISTA KARTONA. eSLI MY
NACHINAEM S PAROJ $(X,Y)$, TAKOJ, CHTO
$\nod(X,Y)=713$, TO NE SUSHCHESTVUET PARY $(x,y)$,
UDOVLETVORYAYUSHCHEJ USLOVIYU (2), T. E. DLYA TAKIH
ZNACHENIJ $X$ I $Y$ USLOVIE (2) SVODITSYA K
PREDIKATU $F$, A |TO OZNACHAET, CHTO RASSMATRIVAEMAYA
MASHINA NE MOZHET BYTX ISPOLXZOVANA DLYA VYCHISLENIYA
$\nod(X,Y)$ PRIMENITELXNO K |TOJ PARE ZNACHENIJ $X$
I $Y$).

pRI MNOGIH KOMBINACIYAH $(X, Y)$ MNOGIE SOSTOYANIYA
UDOVLETVORYAYUT USLOVIYU (2). v SLUCHAE $0<X\le 500$ I
$0<Y\le500$ \emph{TRIVIALXNYM} VYBOROM YAVLYAETSYA
$x=X$ I $y=Y$. eTOT VYBOR MOZHET BYTX PROIZVEDEN
BEZ KAKOGO-LIBO VYCHISLENIYA FUNKCII nod I DAZHE BEZ
UCHETA TOGO FAKTA, CHTO |TO SIMMETRICHNAYA FUNKCIYA OT
SVOIH ARGUMENTOV.

uSLOVIE, HARAKTERIZUYUSHCHEE MNOZHESTVO VSEH NACHALXNYH
SOSTOYANIJ, PRI KOTORYH ZAPUSK OBYAZATELXNO PRIVEDET
K SOBYTIYU
PRAVILXNOGO ZAVERSHENIYA, PRICHEM SISTEMA OSTANETSYA V KONECHNOM 
SOSTOYANII, UDOVLETVORYAYUSHCHEM ZADANNOMU POSTUSLOVIYU,  
NAZYVAETSYA "SLABEJSHIM PREDUSLOVIEM, SOOTVETSTVUYUSHCHIM |TOMU  
POSTUSLOVIYU". (mY NAZYVAEM EGO "SLABEJSHIM", POSKOLXKU, CHEM 
SLABEE USLOVIE, TEM BOLXSHE SOSTOYANIJ UDOVLETVORYAYUT EMy, A MY 
STREMIMSYA ZDESX OHARAKTERIZOVATX VSE VOZMOZHNYE NACHALXNYE 
SOSTOYANIYA, KOTORYE NEIZBEZHNO PRIVEDUT K ZHELAEMOMU KONECHNOMU 
SOSTOYANIYU.)

eSLI SISTEMA (MASHINA, KONSTRUKCIYA) OBOZNACHAETSYA CHEREZ S, A 
ZHELAEMOE POSTUSLOVIE --- CHEREZ R, TO SOOTVETSTVUYUSHCHEE 
SLABEJSHEE PREDUSLOVIE MY OBOZNACHIM%
\note{pO NACHALXNYM BUKVAM 
ANGLIJSKIH SLOV weakest RrE-condition.--- pRIM. PEREV.}
$$
\wp (S,R)
$$

eSLI NACHALXNOE SOSTOYANIE UDOVLETVORYAET $\wp(S, R)$, TO 
KONSTRUKCIYA OBYAZATELXNO OBESPECHIT V KONCE KONCOV ISTINNOSTX 
$R$. pOSKOLXKU $\wp(S, R)$ --- |TO SLABEJSHEE PREDUSLOVIE, MY 
ZNAEM TAKZHE, CHTO ESLI NACHALXNOE SOSTOYANIE NE UDOVLETVORYAET 
$\wp(S, R)$, TO TAKOJ GARANTII DATX NELXZYA, T. E. HOD 
SOBYTIJ MOZHET PRIVESTI K ZAVERSHENIYU RABOTY V KONECHNOM 
SOSTOYANII, Ne UDOVLETVORYAYUSHCHEM $R$, A MOZHET DAZHE I VOOBSHCHE 
POMESHATX DOSTIZHENIYU KAKOGO BY TO NI BYLO KONECHNOGO SOSTOYANIYA 
(KAK MY UVIDIM DALEE, LIBO POTOMU, CHTO SISTEMA OKAZYVAETSYA 
VOVLECHENNOJ V VYPOLNENIE NEZAVERSHIMOGO ZADANIYA, LIBO POTOMU, 
CHTO SISTEMA POPADAET V TUPIK).

mY SCHITAEM, CHTO NAM DOSTATOCHNO HOROSHO IZVESTNO, KAK RABOTAET 
KONSTRUKCIYA $S$, ESLI MOZHEM VYVESTI DLYA LYUBOGO POSTUSLOVIYA 
$R$ SOOTVETSTVUYUSHCHEE SLABEJSHEE PREDUSLOVIE $\wp (S,R)$, 
POSKOLXKU TEM SAMYM MY ULOVILI, CHT\'O |TA KONSTRUKCIYA 
SPOSOBNA SDELATX DLYA NAS; |TO NAZYVAETSYA "EE SEMANTIKOJ".

zDESX UMESTNY DVA ZAMECHANIYA. vO-PERVYH, MNOZHESTVO VOZMOZHNYH 
POSTUSLOVIJ, VOOBSHCHE GOVORYA, STOLX OGROMNO, CHTO |TA 
INFORMACIYA V TABLICHNOJ FORME (T. E. V VIDE TABLICY, GDE 
KAZHDOMU POSTUSLOVIYU $R$ SOOTVETSTVUET ZAPISX, V KOTOROJ 
SODERZHITSYA SOOTVETSTVUYUSHCHEE PREDUSLOVIE $\wp(S, R))$, 
OKAZALASX BY SOVERSHENNO NEOBOZRIMOJ, A SLEDOVATELXNO, 
BESPOLEZNOJ. pO|TOMU OPREDELENIE SEMANTIKI TOJ ILI INOJ 
KONSTRUKCII VSEGDA DAETSYA DRUGIM SPOSOBOM --- V VIDE 
PRAVILA, OPISYVAYUSHCHEGO, KAK DLYA LYUBOGO ZADANNOGO POSTUSLOVIYA 
$R$ MOZHNO VYVESTI SOOTVETSTVUYUSHCHEE SLABEJSHEE PREDUSLOVIE 
$\wp(S, R))$. dLYA FIKSIROVANNOJ KONSTRUKCII $S$ TAKOE 
PRAVILO, KOTOROE PO ZADANNOMU PREDIKATU $R$, OZNACHAYUSHCHEMU 
POSTUSLOVIE, VYRABATYVAET PREDIKAT $\wp(S, R)$, OZNACHAYUSHCHIJ 
SOOTVETSTVUYUSHCHEE SLABEJSHEE PREDUSLOVIE, NAZYVAETSYA 
"PREOBRAZOVATELEM PREDIKATOV". kOGDA MY PROSIM, CHTOBY NAM 
SOOBSHCHILI OPISANIE SEMANTIKI KONSTRUKCII S, TO V SUSHCHNOSTI 
RECHX IDET O SOOTVETSTVUYUSHCHEM |TOJ KONSTRUKCII PREOBRAZOVATELE 
PREDIKATOV.

 vO-VTORYH,--- I YA CHUVSTVUYU ISKUSHENIE DOBAVITX "BLAGODARYA 
SUDXBE" --- CHASTO NAS NE INTERESUET POLNAYA SEMANTIKA 
KONSTRUKCII. eTO OB®YASNYAETSYA TEM, CHTO MY STREMIMSYA 
ISPOLXZOVATX KONSTRUKCIYU $S$ TOLXKO DLYA KONKRETNOJ 
NADOBNOSTI, A TOCHNEE, DLYA TOGO, CHTOBY OBESPECHITX ISTINNOSTX 
VESXMA KONKRETNOGO POSTUSLOVIYA $R$, RADI KOTOROGO 
PROIZVODILASX RAZRABOTKA KONSTRUKCII. i DAZHE PRIMENITELXNO K 
|TOMU KONKRETNOMU POSTUSLOVIYU $R$ NAS CHASTO NE INTERESUET 
TOCHNYJ VID $\wp(S,R)$; ZACHASTUYU MY UDOVLETVORYAEMSYA BOLEE 
SILXNYM USLOVIEM $P$, T. E. TAKIM USLOVIEM, DLYA KOTOROGO 
MOZHNO POKAZATX, CHTO UTVERZHDENIE
$$
P \Rightarrow  \wp(S, R)\qquad\hbox{ DLYA VSEH SOSTOYANIJ}\eqno{(3)}
$$
SPRAVEDLIVO. (pREDIKAT "$P\Rightarrow Q$" (CHITAETSYA "IZ $r$ SLEDUET 
$Q$") LOZHEN TOLXKO V TEH TOCHKAH PROSTRANSTVA SOSTOYANIJ, GDE 
USLOVIE $P$ SPRAVEDLIVO, a $Q$ NE SPRAVEDLIVO; VO VSEH 
OSTALXNYH TOCHKAH ON ISTINEN. tREBUYA, CHTOBY UTVERZHDENIE 
"$P \Rightarrow \wp(S,R)$" BYLO SPRAVEDLIVO DLYA VSEH SOSTOYANIJ, MY 
TEM SAMYM TREBUEM, CHTOBY VSYAKIJ RAZ KOGDA $P$ --- ISTINA, 
USLOVIE $\wp(S, R)$ TOZHE BYLO ISTINOJ; TOGDA $r$ --- 
DOSTATOCHNOE PREDUSLOVIE. v TEORETIKO-MNOZHESTVENNOJ 
TERMINOLOGII |TO OZNACHAET, CHTO MNOZHESTVO SOSTOYANIJ, 
HARAKTERIZUEMOE USLOVIEM $P$, YAVLYAETSYA PODMNOZHESTVOM TOGO 
MNOZHESTVA SOSTOYANIJ, KOTOROE HARAKTERIZUETSYA USLOVIEM 
$\wp(S, R)$.) eSLI DLYA ZADANNYH $r$, $S$ I $R$ OTNOSHENIE (3) 
VYPOLNYAETSYA, |TO CHASTO MOZHNO DOKAZATX, NE PRIBEGAYA K TOCHNOJ 
FORMULIROVKE,--- ILI, ESLI VAM TAK BOLXSHE NRAVITSYA, 
"VYCHISLENIYU" ILI "VYVODU" --- PREDIKATA $\wp(S,R)$. i |TO 
OTRADNOE OBSTOYATELXSTVO, POSKOLXKU, ZA ISKLYUCHENIEM 
TRIVIALXNYH SLUCHAEV, SLEDUET OZHIDATX, CHTO YAVNAYA FORMULIROVKA 
USLOVIYA $\wp(S,R)$ PREVYSIT PO KRAJNEJ MERE REZERV NASHEJ 
PISCHEJ BUMAGI, NASHEGO TERPENIYA ILI NASHEJ (ANALITICHESKOJ) 
IZOBRETATELXNOSTI (ILI KAKUYU-TO KOMBINACIYU |TIH REZERVOV).

sMYSL $\wp(S, R)$, T. E. "SLABEJSHEGO PREDUSLOVIYA DLYA 
NACHALXNOGO SOSTOYANIYA, PRI KOTOROM ZAPUSK OBYAZATELXNO 
PRIVEDET K SOBYTIYU PRAVILXNOGO ZAVERSHENIYA, PRICHEM SISTEMA 
$S$ OSTANETSYA V KONECHNOM SOSTOYANII, UDOVLETVORYAYUSHCHEM 
POSTUSLOVIYU $R$" POZVOLYAET NAM USTANOVITX, CHTO 
PREOBRAZOVATELX PREDIKATOV, RASSMATRIVAEMYJ KAK FUNKCIYA OT 
POSTUSLOVIYA $R$, OBLADAET RYADOM OPREDELENNYH SVOJSTV.

{\sl sVOJSTVO 1.} dLYA LYUBOJ KONSTRUKCII $S$ MY IMEEM
$$
\wp(S,F)=F \eqno{(4)}
$$

pREDPOLOZHIM, CHTO OKAZALOSX NE TAK; PRI |TOM NASHLOSX HOTX ODNO SOSTOYANIE, 
UDOVLETVORYAYUSHCHEE USLOVIYU $\wp(S,F)$. vOZXMEM TAKOE SOSTOYANIE V KACHESTVE 
NACHALXNOGO SOSTOYANIYA DLYA KONSTRUKCII $S$. tOGDA, SOGLASNO NASHEMU 
OPREDELENIYU, ZAPUSK PRIVEL BY K SOBYTIYU PRAVILXNOGO ZAVERSHENIYA, PRICHEM 
SISTEMA OSTALASX BY V KONECHNOM SOSTOYANII, UDOVLETVORYAYUSHCHEM PREDIKATU $F$. 
nO ZDESX VOZNIKAET PROTIVORECHIE, TAK KAK PO OPREDELENIYU PREDIKATA $F$ NE 
SUSHCHESTVUET SOSTOYANIJ, UDOVLETVORYAYUSHCHIH $F$; TEM SAMYM DOKAZANO OTNOSHENIE 
(4). sVOJSTVO 1 IZVESTNO TAKZHE POD NAZVANIEM "ZAKON ISKLYUCHENNOGO CHUDA".

{\sl sVOJSTVO 2.} dLYA LYUBOJ KONSTRUKCII $S$ I LYUBYH POSTUSLOVIJ $Q$ I 
$R$, TAKIH, CHTO
$$
Q \Rightarrow R\qquad\hbox{DLYA VSEH SOSTOYANIJ}
$$
SPRAVEDLIVO TAKZHE OTNOSHENIE
$$
\wp(S,Q) \Rightarrow\wp(S, R)\qquad\hbox{DLYA VSEH SOSTOYANIJ}\eqno{(6)}
$$
v SAMOM DELE, PRI LYUBOM NACHALXNOM SOSTOYANII, UDOVLETVORYAYUSHCHEM $\wp(S,Q)$, 
SOGLASNO OPREDELENIYU, PO OKONCHANII RABOTY SISTEMY BUDET OBESPECHENA 
ISTINNOSTX $Q$. s UCHETOM OTNOSHENIYA (5) TEM SAMYM BUDET OBESPECHENA I 
ISTINNOSTX $R$. sLEDOVATELXNO, DANNOE NACHALXNOE SOSTOYANIE BUDET 
ODNOVREMENNO UDOVLETVORYATX I USLOVIYU $\wp(S,R)$, KAK ZAPISANO V (6). 
sVOJSTVO 2 --- |TO SVOJSTVO MONOTONNOSTI.

{\sl sVOJSTVO 3.} dLYA LYUBOJ KONSTRUKCII $S$ I DLYA LYUBYH POSTUSLOVIJ $Q$ 
I $R$ SPRAVEDLIVO
$$
(\wp(S, Q) \and \wp(S,R))=\wp(S,Q\and R) \eqno{(7)}
$$

v LYUBOJ TOCHKE PROSTRANSTVA SOSTOYANIJ IZ LEVOJ CHASTI OTNOSHENIYA (7)  
LOGICHESKI SLEDUET EGO PRAVAYA CHASTX POTOMU, CHTO DLYA LYUBOGO NACHALXNOGO 
SOSTOYANIYA, UDOVLETVORYAYUSHCHEGO $\wp(S,Q)$, I $\wp(S,R)$, MY ZNAEM V 
SOVOKUPNOSTI, CHTO USTANOVITSYA KONECHNOE SOSTOYANIE, UDOVLETVORYAYUSHCHEE I $Q$, 
I $R$. dALEE, POSKOLXKU, V SILU OPREDELENIYA,
$$
(Q \and R) \Rightarrow Q \qquad\hbox{DLYA VSEH SOSTOYANIJ}
$$
SVOJSTVO 2 POZVOLYAET NAM ZAKLYUCHITX, CHTO
$$
\wp(S, Q \and R)\Rightarrow\wp(S, Q)\qquad\hbox{DLYA VSEH SOSTOYANIJ}
$$
I ANALOGICHNO 
$$
\wp(S, Q \and R) \Rightarrow \wp(S, R)\qquad\hbox{DLYA VSEH SOSTOYANIJ}
$$

oDNAKO IZ $A\Rightarrow B$ I $A\Rightarrow C$, SOGLASNO ISCHISLENIYU PREDIKATOV, 
MOZHNO VYVESTI, CHTO $A\Rightarrow(B\and C)$. pO|TOMU PRAVAYA CHASTX OTNOSHENIYA (7) 
LOGICHESKI SLEDUET IZ EGO LEVOJ CHASTI V LYUBOJ TOCHKE PROSTRANSTVA 
SOSTOYANIJ. pOSKOLXKU OBE CHASTI VSYUDU SLEDUYUT DRUG IZ DRUGA, ONI DOLZHNY 
BYTX RAVNY, A TEM SAMYM DOKAZANO SVOJSTVO 3.

{\sl sVOJSTVO 4.} dLYA LYUBOJ KONSTRUKCII $S$ I LYUBYH POSTUSLOVIJ $Q$ I 
$R$ SPRAVEDLIVO
$$
(\wp(S,Q)\or \wp(S, R))\Rightarrow \wp(S,Q \or R) \qquad\hbox{DLYA VSEH SOSTOYANIJ}
\eqno{(8)}
$$

pOSKOLXKU, V SILU OPREDELENIYA, 
$$
Q \Rightarrow(Q \or R)\qquad\hbox{DLYA VSEH SOSTOYANIJ}
$$
SVOJSTVO 2 POZVOLYAET NAM PRIJTI K ZAKLYUCHENIYU, CHTO 
$$
 \wp(S,Q) \Rightarrow \wp(S, Q \or R)\qquad\hbox{ DLYA VSEH SOSTOYANIJ}
$$
I ANALOGICHNO 
$$
\wp(S,R) \Rightarrow\wp(S, Q \or R)\qquad\hbox{DLYA VSEH SOSTOYANIJ}
$$

nO, SOGLASNO ISCHISLENIYU VYSKAZYVANIJ, IZ $A \Rightarrow C$ 
I~$B\Rightarrow C$ MOZHNO 
ZAKLYUCHITX, CHTO $(A\or B)\Rightarrow C$, I |TIM DOKAZANA SPRAVEDLIVOSTX 
SOOTNOSHENIYA (8). vOOBSHCHE GOVORYA, SLEDOVANIE V OBRATNOM NAPRAVLENII NE 
IMEET MESTA. tAK PRO ZHENSHCHINU, KOTORAYA ZHDET REBENKA, NEVERNO UTVERZHDENIE, 
CHTO ONA RODIT OBYAZATELXNO SYNA I NEVERNO UTVERZHDENIE, CHTO ONA RODIT 
OBYAZATELXNO DOCHX; ODNAKO S ABSOLYUTNOJ UVERENNOSTXYU MOZHNO UTVERZHDATX, CHTO 
ONA RODIT SYNA ILI DOCHX. vPROCHEM, DLYA DETERMINIROVANNYH KONSTRUKCIJ 
SPRAVEDLIVO SLEDUYUSHCHEE, BOLEE SILXNOE SVOJSTVO.

{\sl sVOJSTVO 4'.}  dLYA LYUBOJ DETERMINIROVANNOJ KONSTRUKCII $S$ I LYUBYH 
POSTUSLOVIJ $Q$ I $R$ SPRAVEDLIVO
$$
(\wp(S, Q) \or \wp(S, R)) \Rightarrow \wp (S, Q \or R)
$$

nAM NUZHNO POKAZATX, CHTO SLEDOVANIE VYPOLNYAETSYA I V LEVUYU  STORONU. 
rASSMOTRIM KAKOE-TO NACHALXNOE SOSTOYANIE, UDOVLETVORYAYUSHCHEE 
$\wp(S, Q \or R)$, |TOMU NACHALXNOMU SOSTOYANIYU SOOTVETSTVUET 
\emph{EDINSTVENNOE} KONECHNOE SOSTOYANIE, UDOVLETVORYAYUSHCHEE LIBO $Q$, LIBO 
$R$, LIBO OBOIM USLOVIYAM; SLEDOVATELXNO, DANNOE NACHALXNOE SOSTOYANIE 
DOLZHNO UDOVLETVORYATX LIBO $\wp(S, Q)$, LIBO $\wp(S, R)$, LIBO OBOIM 
USLOVIYAM SOOTVETSTVENNO, T. E. ON DOLZHNO UDOVLETVORYATX 
$(\wp(S,Q) \or \wp(S,R))$. i |TIM DOKAZANO SVOJSTVO 4'.

v |TOJ KNIGE YA BUDU --- I |TO MOZHET OKAZATXSYA ODNOJ IZ EE OTLICHITELXNYH 
OSOBENNOSTEJ --- RASSMATRIVATX NEDETERMINIROVANNOSTX KAK PRAVILO, A 
DETERMINIROVANNOSTX KAK ISKLYUCHENIE: DETERMINIROVANNAYA MASHINA BUDET 
RASSMATRIVATXSYA KAK CHASTNYJ SLUCHAJ NEDETERMINIROVANNOJ, KAK KONSTRUKCIYA, 
DLYA KOTOROJ SPRAVEDLIVO SVOJSTVO 4' A NE TOLXKO BOLEE SLABOE SVOJSTVO 4. 
tAKOE RESHENIE OTRAZHAET KORENNOE IZMENENIE V MOEM MIROVOZZRENII. v 
1958~G. YA BYL ODNIM IZ PERVYH, KTO RAZRABATYVAL BAZOVOE PROGRAMMNOE 
OBESPECHENIE DLYA MASHINY S PRERYVANIYAMI VVODA-VYVODA, I 
NEVOSPROIZVODIMOSTX POVEDENIYA TAKOJ VO VSEH OTNOSHENIYAH 
NEDETERMINIROVANNOJ MASHINY YAVILASX GORESTNYM OBSTOYATELXSTVOM. kOGDA 
VPERVYE BYLA PREDLOZHENA IDEYA PRERYVANIJ VVODA-VYVODA, MENYA NASTOLXKO 
PUGALA SAMA MYSLX O NEOBHODIMOSTI RAZRABATYVATX NADEZHNOE PROGRAMMNOE 
OBESPECHENIE DLYA TAKOGO NEUKROTIMOGO ZVERYA, CHTO YA OTTYAGIVAL PRINYATIE 
RESHENIYA O DOPUSHCHENII TAKIH PRERYVANIJ PO KRAJNEJ MERE V TECHENIE TREH 
MESYACEV. i DAZHE POSLE TOGO, KAK YA SDALSYA (MOE SOPROTIVLENIE SLOMILI 
LESTXYU), CHUVSTVOVAL YA SEBYA VESXMA NEUYUTNO: VEDX OSHIBKA V PROGRAMME 
SPOSOBNA VYZVATX NESURAZNOE POVEDENIE SISTEMY, STOLX SHODNOE S 
NEVOSPROIZVODIMYM MASHINNYM SBOEM. kROME TOGO,--- I |TO V TO VREMYA, KOGDA 
DLYA DETERMINIROVANNYH MASHIN MY VSE ESHCHE POLAGALISX NA "OTLADKU",--- S 
SAMOGO NACHALA BYLO SOVERSHENNO OCHEVIDNO, CHTO TESTIROVANIE PROGRAMM 
OKAZYVALOSX TEPERX SOVSEM NEPRIGODNYM SREDSTVOM DLYA DOSTIZHENIYA DOLZHNOGO 
UROVNYA NADEZHNOSTI.

v TECHENIE MNOGIH LET VPOSLEDSTVII YA OTNOSILSYA K NEVOSPROIZVODIMOSTI 
POVEDENIYA NEDETERMINIROVANNOJ MASHINY KAK K DOBAVOCHNOMU OSLOZHNENIYU, 
KOTOROGO SLEDUET IZBEGATX LYUBYMI SPOSOBAMI. pRERYVANIYA BYLI DLYA MENYA NE 
CHEM INYM, KAK ZLYMI KOZNYAMI INZHENEROV PO APPARATURE PROTIV BEDNYH 
RAZRABOTCHIKOV PROGRAMMNOGO OBESPECHENIYA. iZ |TOGO MOEGO STRAHA RODILASX 
DISCIPLINA "GARMONICHESKI VZAIMODEJSTVUYUSHCHIH POSLEDOVATELXNYH PROCESSOV". 
nESMOTRYA NA EE USPEH, MOI OPASENIYA SOHRANYALISX, POSKOLXKU NASHI RESHENIYA
--- HOTX BY I S DOKAZANNOJ PRAVILXNOSTXYU --- PREDSTAVLYALISX CHASTNYMI 
RESHENIYAMI PROBLEMY "UKROSHCHENIYA" (IMENNO TAK  MY  |TO VOSPRINIMALI!) 
KONKRETNYH VIDOV NEDETERMINIROVANNOSTI. oSNOVANIEM DLYA MOEGO STRAHA BYLO 
OTSUTSTVIE OBSHCHEJ METODOLOGII.

s TEH POR DVA OBSTOYATELXSTVA IZMENILI KARTINU. pERVOE VOZNIKLO S 
PONIMANIEM TOGO, CHTO DAZHE V SLUCHAE POLNOSTXYU DETERMINIROVANNYH MASHIN 
POLEZNOSTX TESTIROVANIYA PROGRAMM OKAZYVAETSYA SOMNITELXNOJ. kAK YA UZHE 
MNOGO paZ GOVORIL I VO MNOGIH MESTAH PISAL, TESTIROVANIE PROGRAMMY MOZHET 
VPOLNE |FFEKTIVNO SLUZHITX DLYA DEMONSTRACII NALICHIYA V NEJ OSHIBOK, NO, K 
SOZHALENIYU, NEPRIGODNO DLYA DOKAZATELXSTVA IH OTSUTSTVIYA. dRUGIM 
PROYASNIVSHIMSYA TEM VREMENEM OBSTOYATELXSTVOM YAVILOSX OBNARUZHENIE 
NEOBHODIMOSTI TOGO, CHTOBY VSYAKAYA DISCIPLINA PROEKTIROVANIYA DOLZHNYM 
OBRAZOM UCHITYVALA TOT FAKT, CHTO SAMO PROEKTIROVANIE KONSTRUKCII, 
PREDNAZNACHENNOJ DLYA KAKOJ-TO CELI, TOZHE DOLZHNO BYTX CELENAPRAVLENNOJ 
DEYATELXNOSTXYU. v NASHEM KONKRETNOM SLUCHAE |TO OZNACHAET ESTESTVENNOSTX 
PREDPOLOZHENIYA, CHTO OTPRAVNOJ TOCHKOJ DLYA PROEKTNYH RASSMOTRENIJ BUDET 
SLUZHITX ZADANNOE POSTUSLOVIE. v KAKOM-TO SMYSLE MY BUDEM "RABOTATX 
VSPYATX". dEJSTVUYA TAK, MY OBNARUZHIM, CHTO VESXMA SUSHCHESTVENNYM OKAZYVAETSYA 
SLEDOVANIE IZ SVOJSTVA 4, TOGDA KAK OT RAVENSTVA IZ SVOJSTVA 4' MY 
POLUCHIM OCHENX MALO POLXZY.

kAK TOLXKO MY RAZRABOTALI MATEMATICHESKIJ APPARAT, POZVOLYAYUSHCHIJ 
PROEKTIROVATX NEDETERMINIROVANNYE KONSTRUKCII, DOSTIGAYUSHCHIE CELI, 
NEDETERMINIROVANNAYA MASHINA PERESTAET NAS PUGATX. nAPROTIV! mY NAUCHIMSYA 
DAZHE CENITX EE KAK VAZHNUYU STEPENX NA PUTI RAZRABOTKI PROEKTA V KONECHNOM 
ITOGE POLNOSTXYU DETERMINIROVANNOJ KONSTRUKCII.

(pOSLEDUYUSHCHAYA CHASTX |TOJ GLAVY MOZHET BYTX PROPUSHCHENA PRI PERVOM CHTENII.) 
rANEE MY DOGOVORILISX, CHTO PREDSTAVLYAEM FUNKCIONIROVANIE KONSTRUKCII $S$ 
DOSTATOCHNO HOROSHO, ESLI TOLXKO ZNAEM, KAK SOOTVETSTVUYUSHCHIJ EJ 
PREOBRAZOVATELX PREDIKATOV $\wp(S,R)$ DEJSTVUET NAD LYUBYM POSTUSLOVIEM 
$R$. eSLI NAM IZVESTNO TAKZHE, CHTO DANNAYA KONSTRUKCIYA DETERMINIROVANA, TO 
ZNANIE |TOGO PREOBRAZOVATELYA PREDIKATOV POLNOSTXYU OPREDELYAET VOZMOZHNOE 
POVEDENIE KONSTRUKCII. dLYA DETERMINIROVANNOJ KONSTRUKCII $S$ I 
NEKOTOROGO POSTUSLOVIYA $R$ VSYAKOE NACHALXNOE SOSTOYANIE POPADAET V ODNO IZ 
TREH NEPERESEKAYUSHCHIHSYA MNOZHESTV V SOOTVETSTVII SO SLEDUYUSHCHIMI VZAIMNO 
ISKLYUCHAYUSHCHIMI VOZMOZHNOSTYAMI:

(A) zAPUSK KONSTRUKCII $S$ PRIVEDET K KONECHNOMU SOSTOYANIYU, 
UDOVLETVORYAYUSHCHEMU $R$.

(B) zAPUSK KONSTRUKCII $S$ PRIVEDET K KONECHNOMU SOSTOYANIYU, 
UDOVLETVORYAYUSHCHEMU $\non R$.

(V) zAPUSK KONSTRUKCII $S$ NE PRIVEDET K KAKOMU BY TO NI BYLO KONECHNOMU 
SOSTOYANIYU, T. E. RABOTA NE SMOZHET ZAVERSHITXSYA PRAVILXNYM OBRAZOM.

pERVOE MNOZHESTVO HARAKTERIZUETSYA VYRAZHENIEM $\wp(S, R)$, VTOROE 
MNOZHESTVO --- VYRAZHENIEM $\wp(S, \non R)$, IH OB®EDINENIE --- 
VYRAZHENIEM $(\wp(S,R)\or\wp(S,\non R))=\wp(S,R\or\non R)=\wp(S,T)$
A SLEDOVATELXNO, TRETXE MNOZHESTVO HARAKTERIZUETSYA VYRAZHENIEM 
$\non\wp(S,T)$.

tRUDNEE DATX POLNUYU SEMANTICHESKUYU HARAKTERISTIKU NEDETERMINIROVANNOJ 
SISTEMY. pO OTNOSHENIYU K LYUBOMU ZADANNOMU POSTUSLOVNYU $R$ MY SNOVA IMEEM 
TRI VOZMOZHNYH TIPA SOBYTIJ, KAK PERECHISLENO VYSHE V PUNKTAH (A), (B) I 
(V). oDNAKO V SLUCHAe NEDETERMINIROVANNOJ SISTEMY ODNO I TO ZHE NACHALXNOE 
SOSTOYANIE NE OBYAZATELXNO PRIVODIT K EDINSTVENNOMU SOBYTIYU, KOTOROE PO 
OPREDELENIYU OTNOSILOSX BY K ODNOMU IZ TREH VZAIMNO ISKLYUCHAYUSHCHIH TIPOV; 
DLYA LYUBOGO NACHALXNOGO SOSTOYANIYA VOZMOZHNYE SOBYTIYA MOGUT TEPERX 
OTNOSITXSYA K ODNOMU, DVUM ILI DAZHE KO VSEM TREM TIPAM.

chTOBY OPISYVATX TAKIE SITUACII, MY MOZHEM ISPOLXZOVATX PONYATIE 
"SVOBODNOGO PREDUSLOVIYA". rANEE MY RASSMOTRIVALI TAKIE PREDUSLOVIYA, PRI 
KOTORYH GARANTIROVALASX DOSTIZHIMOSTX "PRAVILXNOGO REZULXTATA", T. E. 
KONECHNOGO SOSTOYANIYA, UDOVLETVORYAYUSHCHEGO $R$. sVOBODNOE PREDUSLOVIE 
YAVLYAETSYA BOLEE SLABYM: ONO GARANTIRUET TOLXKO, CHTO SISTEMA NE VYDAST 
NEPRAVILXNOGO REZULXTATA, T. E. NE DOSTIGNET TAKOGO KONECHNOGO SOSTOYANNYA, 
KOTOROE NE UDOVLETVORYALO BY $R$, ODNAKO NE ISKLYUCHAETSYA VOZMOZHNOSTX 
NEZAVERSHENIYA RABOTY SISTEMY. aNALOGICHNO I DLYA SVOBODNYH PREDUSLOVIJ MY 
MOZHEM VVESTI PONYATIE "SLABEJSHEGO SVOBODNOGO PREDUSLOVIYA"; OBOZNACHIM EGO 
CHEREZ $\wlp(S,R)$, pRI |TOM PROSTRANSTVO NACHALXNYH SOSTOYANIJ 
PODRAZDELYAETSYA V PRINCIPE NA SEMX VZAIMNO NEPERESEKAYUSHCHIHSYA OBLASTEJ, NI 
ODNA IZ KOTORYH NE OBYAZANA BYTX PUSTOJ. (iH SEMX, POTOMU CHTO IZ TREH 
OB®EKTOV MOZHNO SDELATX SEMX NEPUSTYH VYBOROK.) vSE ONI LEGKO 
HARAKTERIZUYUTSYA TREMYA PREDIKATAMI: $\wlp(S,R)$, $\wlp(S,\non R)$ I 
$\wp(S,T)$.
$$
\wp(S, R) = (\wlp (S, R) \and \wp(S, T) )\leqno{(A)}
$$
zAPUSK OBESPECHIT ISTINNOSTX R.
$$
 \wp(S, \non R) = (\wlp (S, \non R) \and \wp(S, T)) \leqno{(B)}
$$
zAPUSK OBESPECHIT ISTINNOSTX $\non R$.
$$
 \wlp (S, F) = (\wlp (S, R) \and \wlp (S, \non R)) \leqno{(V)}
$$
zAPUSK NE SMOZHET PRIVESTI K PRAVILXNO ZAVERSHAEMOJ RABOTE 
$$
 \wp(S, T) \and \non \wlp(S, R) \and \non \wlp(S, \non R)\leqno{(AB)}
$$
zAPUSK PRIVEDET K ZAVERSHAEMOJ RABOTE, NO PO NACHALXNOMU STOYANIYU NELXZYA 
OPREDELITX, BUDET LI KONECHNOE SOSTOYANIE UDOVLETVORYATX USLOVIYU $R$ ILI 
NET.
$$
 \wlp (S,R) \and \non \wp(S, t)\leqno{(AV)}
$$
eSLI ZAPUSK PRIVODIT K KAKOMU-TO KONECHNOMU SOSTOYANIYU, TAKOE KONECHNOE 
SOSTOYANIE BUDET UDOVLETVORYATX $R$, NO PO NACHALXNOMU SOSTOYANIYU NELXZYA 
OPREDELITX, ZAVERSHITSYA LI RABOTA SISTEMY.
$$
 \wlp (S, \non R) \and \non \wp (S, T)\leqno{(BV)}
$$
eSLI ZAPUSK PRIVODIT K KAKOMU-TO KONECHNOMU SOSTOYANIYU, TAKOE KONECHNOE 
SOSTOYANIE NE BUDET UDOVLETVORYATX $R$, NO PO NACHALXNOMU SOSTOYANIYU NELXZYA 
OPREDELITX, ZAVERSHITSYA LI RABOTA SISTEMY. 
$$
 \non (\wlp(S, R) \or \wlp(S, \non R) \or \wp(S, T)\leqno{(ABV)}
$$
pO NACHALXNOMU SOSTOYANIYU NELXZYA OPREDELITX, PRIVEDET LI ZAPUSK K 
ZAVERSHAEMOJ RABOTE, A V SLUCHAE ZAVERSHAEMOSTI NELXZYA OPREDELITX, BUDET LI 
UDOVLETVORYATXSYA USLOVIE $R$.

pOSLEDNIE CHETYRE VOZMOZHNOSTI SUSHCHESTVUYUT TOLXKO DLYA NEDETERMIROVANNYH 
MASHIN.

iZ OPREDELENIYA $wlp(S, R)$ SLEDUET, CHTO
$$
\wlp(S, T)=T 
$$
yaSNO TAKZHE, CHTO
$$
 (\wlp(S,F) \and \wp(S,T))=F
$$

eSLI BY BYLO NE TAK, TO SUSHCHESTVOVALO BY NACHALXNOE SOSTOYANIE, DLYA 
KOTOROGO MOZHNO BYLO BY GARANTIROVATX I ZAVERSHIMOSTX, I NEZAVERSHIMOSTX 
RABOTY. nA RIS. 3.1 DANO GRAFICHESKOE
$$
//RIS.31
$$
PREDSTAVLENIE PROSTRANSTVA  SOSTOYANIJ,PRICHEM VNUTRENNIE CHASTI  
PRYAMOUGOLXNIKOV UDOVLETVORYAYUT $\wlp (S, R)$, $\wlp(S, \non R)$ I 
$\wp(S, T)$  SOOTVETSTVENNO.  

eTOT ANALIZ PRIVEDEN DLYA POLNOTY, A TAKZHE POTOMU, CHTO NA PRAKTIKE 
PONYATIE SVOBODNOGO PREDUSLOVIYA OKAZYVAETSYA VESXMA POLEZNYM. eSLI, 
NAPRIMER, KTO-TO REALIZUET YAZYK PROGRAMMIROVANIYA, TO ON NE STANET 
DOKAZYVATX, CHTO PRI |TOJ REALIZACII LYUBAYA PRAVILXNAYA PROGRAMMA 
VYPOLNYAETSYA PRAVILXNO. oN BYL BY UDOVLETVOREN I SCHASTLIV, ESLI BY TVERDO 
ZNAL, CHTO NIKAKAYA PRAVILXNAYA PROGRAMMA NE BUDET VYPOLNENA PRAVILXNO BEZ 
SOOTVETSTVUYUSHCHEGO PREDUPREZHDENIYA,--- RAZUMEETSYA, PRI USLOVII, CHTO KLASS 
PROGRAMM, KOTORYE NA SAMOM DELE BUDUT VYPOLNYATXSYA PRAVILXNO, DOSTATOCHNO 
VELIK DLYA TOGO, CHTOBY |TA REALIZACIYA PREDSTAVLYALA KAKOJ-TO INTERES.

oDNAKO POKA MY NE BUDEM RASSMATRIVATX PONYATIE SVOBODNOGO PREDUSLOVIYA, A 
SOSREDOTOCHIM SVOE VNIMANIE NA SPOSOBE HARAKTERISTIKI TEH NACHALXNYH 
SOSTOYANIJ, KOTORYE GARANTIRUYUT POLUCHENIE PRAVILXNOGO REZULXTATA. kOGDA 
TAKOJ SPOSOB BUDET RAZRABOTAN, MY POSMOTRIM, KAK MOZHNO EGO VIDOIZMENITX 
TAKIM OBRAZOM, CHTOBY |TO POZVOLILO NAM RASSUZHDATX O SVOBODNYH 
PREDUSLOVIYAH V TOJ MERE, V KOTOROJ ONI NAS INTERESUYUT.

\bye