Промышленный лизинг Промышленный лизинг  Методички 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 [ 145 ] 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227

только заменой

неверно, что S П Т=0п

SMzT: ни S П Т - 0, ни S zdT.

Так как, однако, мы заменяем симметричное отношение М\ на несимметричное Мчч утверждение (51 :Е) не может быть использовано тем же способом, каким мы использовали (51 :В) или, вернее, основное (51 :А).

51.4. Измененный подход. Перечисление посредством Wm

51.4.1. Перейдем теперь ко второй процедуре. Она состоит в анализе следующего вопроса. Если дана система У, то что означает выполнение включения У ТУт для ТУ, удовлетворяющего (49:W*)?

У <== Wm означает следующее. Каждое S £ У есть минимальный элемент ТУ. Это значит, что такое S должно принадлежать ТУ, но его собственные подмножества не должны принадлежать ТУ. Так как ТУ удовлетворяет (49:W*:b), т. е. содержит надмножества всех своих элементов, Это достаточно установить только для максимального собственного подмножества S, т. е. для S - (&), где i £ S. Так как ТУ удовлетворяет (49:W*:а), вместо того, чтобы говорить, что S - (i) не принадлежит ТУ, мы можем сказать, что - (S - (i)) = (-S)[](i) принадлежит ТУ. Итак, мы видим следующее.

(51 :F) У ТУШ (ТУ удовлетворяют (49:W*)) означает в точности

следующее. Каждое S £ У принадлежит ТУ, и для каждого i из этого S объединение (-S) [) (i) принадлежит ТУ.

Мы теперь докажем утверждение:

(51 :G) У есть подмножество ТУ для ТУ, удовлетворяющего (49:W*), тогда и только тогда, когда оно обладает следующими свойствами:

(51:G:a) Любые два S, Т из У пересекаются.

(51:G:b) Ни для каких двух S и Т из У не будет S zd Т.

(51:G:c) Для S и Г, принадлежащих У из S [} Т = I следует, что S П Т есть одноэлементное множество

(51:G:d) Ни 0, ни одноэлементное множество, ни 7 не должны принадлежать У.

Доказательство. Пусть Vx - семейство всех множеств (-S) U (i), где S ё У и i £ S. Тогда У g= Wm означает по (51:F), что У U Vi ТУ. Согласно (51 :D) это возможно для некоторого ТУ, удовлетворяющего (49:W*), если Уи1 удовлетворяют (51:D:a) и (51:D:b).

Сформулируем поэтому (51:D:a) и (51:D:b) для FUi-

(51:D:a). Если оба множества S и Т принадлежат У, то это совпадает с (51:G:a). Пусть оба множества S и Т принадлежат У4. Это значит, что S = (-5 ) U (0 и Т = {-Tf) U (i), где S , Г £ У, i£S\]£T.

То, что £ и Г не пересекаются, означает, что -S и -7 также не пересекаются, т. е. S (J Г = 7; (г) и (;) не пересекаются, т. е. i Ф /, (-5 ) и (/) не пересекаются, т. е. j £ *S , и, наконец, (-Т7), (j) не пересекаются, т. е. i £ Г.

Суммируя все сказанное, мы получаем S [} Т* = 7: a i и / - два различных элемента, оба из S и 71, т. е. из 5 П У-



Теперь мы должны сформулировать невозможность этого. Именно, если S [} Т = 7, то S fl Т не может обладать двумя различными элементами. Так как S П Т не может быть пустым множеством, по (51:G:a), это означает, что оно должно быть одноэлементным множеством.

Таким образом, получилось в точности (51:G:c) (с S и Т вместо S и Т).

Пусть из множеств S и Т одно принадлежит У, а другое У4. Мы можем предположить, в силу симметрии, что S принадлежит У, а Т принадлежит У4. Итак, Т = (-Г)и(У), где Г £ У, a j £ Г. То, что S и (-Г)иО) не пересекаются, означает, что множества S и -7 не пересекаются, т. е. S s Г; 5 и (/) не пересекаются, т. е. / не принадлежит S.

Суммируя сказанное, мы получим S Г, а / принадлежит Т и не принадлежит S.

Теперь мы должны сформулировать невозможность этого, т. е. отрицание S с Г. Но это есть просто (51:G:b).

(51:D:b). Ни 0, ни одноэлементные множества не должны принадлежать ни У, ни Vi. Последнее означает, что мы не можем иметь множества (-*9) (J (г), где S £ У и i £ S. Такое множество (-S) (J (i) может быть только одноэлементным, а это означало бы, что -S = 0, т. е. S = I.

Резюмируя, мы получаем: ни 0, ни одноэлементные множества, ни I не должны принадлежать У. Это совпадает с (51:G:d).

Таким образом, мы, как и хотели, получили условия (51:G:a) - (51:G:d).

(51 :G) решает проблему перечисления всех Wm совершенно так же, как (51 :D) решало соответствующую проблему для W. Начиная с произвольного У, которое удовлетворяет (51:G:a)-(51:G:b) х), мы будем увеличивать его последовательно до тех пор, пока это можно делать без нарушения (51:G:a)-(51:G:d). Когда этот процесс нельзя будет продолжать дальше, мы получим У, которое максимально среди всех подмножеств вида Wm для соответствующего W со свойствами (49:W*), т. е. мы имеем такое Wm. Производя этот процесс построения всеми возможными способами, мы получим все искомые Wm.

51.4.2. Наши последние замечания показывают, что практическое перечисление всех простых игр может быть основано на (51 :G), и - мы хотим фактически проделать это в п. 52. Но сначала, однако, лучше провести некоторые другие рассмотрения.

Мы намерены теперь проанализировать несколько более подробно утверждение о том, что (51 :G) есть условие типа насыщения.

Заметим сначала, что так как (51:G:b) относится к двум произвольным множествам S и Т из У, мы можем поменять их местами, т. е. мы можем заменить (51:G:b) на

(51:G:b*) Ни для каких двух S и Г из У не будет выполнено ни S => Т ни S cz Т.

Обозначим утверждение, что S и Т удовлетворяют (51:G:a), (51:G:b*), (51:G:c),- т. е. что ни S f] Т = 0, ни S =э Г, ни S cz Т, ни S U Т - I за исключением случая, когда S П Т - одноэлементное множество,- через SM3T.

Тогда (51 :G) устанавливает просто, что У является -удовлетворяемым, а также со свойством (51:G:d). Пусть теперь областью D будет семейство / тех подмножеств 7, для которых выполнено (51:G:d), т. е. не являю-



гдихся ни 0, ни одноэлементными множествами, ни самим I. Тогда последние замечания п. 51.4.1 показывают, что множества ТУ являются максимальными -удовлетворяемыми подмножествами из I.

Ясно, что отношение SM3T симметрично 1). Следовательно, мы можем применить (30:G) из п. 30.3.5. Это даст нам следующее.

(51 :Н) V = Wm для ТУ со свойствами (49:W*) тогда и только тогда, когда Уз-насыщено (в /).

Сравнение (51 :F) и (51 :Н) показывает, что нам удалось перейти от асимметричного Мг к симметричному Мз и выполнить тем самым обещание, данное в сноске 1 на стр. 290.

51.4.3. Чрезвычайно поучительно сравнить Мг (из п- 51.3.2) с нашим Мз-

SM2T : ни S [\Т = 0, ни S zd Т,

SM3T : ни 5ПГ = 0, ни S zd Т, ни S а Т, ни S{)T=I, за исключением случая, когда S П Т есть одноэлементное множество.

Простая симметризация Мг (см. п. 30.3.2) дала бы три первые части этого описания Мз, но не последнюю. Эта последняя часть - существен-ное? достижение (51 :G) и (51:Н) и не связана какими-либо очевидными путями с тремя остальными.

Из этого можно заключить, сколь запутанными должны быть операции, с помощью которых программа п. 30.3.7 могла бы быть выполнена, если бы это оказалось вообще возможным.

.51.5. Простота и разложение

51.5.1. Рассмотрим связи между понятием простой игры и понятием разложения.

Предположим, следовательно, что Г - разложимая игра с компонентами А и Н (/ и К - дополнительные множества в /). Тогда мы должны ответить на вопрос, что означает простота игры Г применительно к А и Н.

Начнем с определения множеств ТУ и L. Так как мы должны рассмотреть их для всех трех игр, необходимо отметить их зависимость от игры. Поэтому мы будем писать ТУГ, Lr; ТУд, LA; ТУН, LH.

Следует добавить, что мы не предполагаем существенности или какой-либо нормировки игр Г, А, Н. Удобно, однако, предположить, что все они являются играми с нулевой суммой 2).

(51:1) S = R{JT (R g= /, Т g= К) принадлежит WT (LT) тогда

и только тогда, когда R принадлежит Wa (La), а Т принадлежит WK (LH).

Доказательство. Заменим S на его дополнение (в /), т. е. на / - S 3); заменим, далее, R и Т их соответствующими дополнениями

х) SM3T выполняется в /, Sf\S = 0 верно только для S = 0; S D S не верно никогда; S\JS = I справедливо только при S = I; следовательно, ничего этого не может быть для S £ I.

2) Читатель, который помнит рассуждения п. 46.10, может пожелать узнать в этом месте, как улаживается вопрос об эксцессах (в Г, А, Н соответственно е0, cp,i>). Этот вопрос будет выяснен в п. 51.6.

3) Предпочтительнее писать дополнение таким способом вместо обычного -S, -Т, так как теперь дополнения берутся относительно различных множеств.



1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 [ 145 ] 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227