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

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

Ясно, что отношение SM\T симметрично; следовательно, мы можем применить (30:G) из п. 30.3.5 х).

51.2.2. Для того чтобы обсудить (49:W*) на этой основе, следует ввести в рассмотрение (49:W*:c). Это может быть сделано двумя путями. Первый путь полезен для последующего сравнения.

(51 :В) Семейство W удовлетворяет (49:W*) тогда и только тогда, когда оно -насыщено и не содержит ни 0, ни одноэлементных множеств.

Доказательство. (49:W*) объединяет (49:W*:a), (49:W*:b) и (49:W*:c). Первые два условия по (51:А) означают .-насыщенность. Если считать (49:W*:a) выполненным, то (49:W*:c) может быть установлено следующим образом. Если S есть / или п - 1-элементное множество, то -S не принадлежит W. Поэтому ни 0, ни одноэлементные множества не принадлежат W.

Польза от второго пути более непосредственная. Пусть У0 - семейство всех множеств, отписываемых в (49:W*:c), т. е. оно состоит из / и всех п - 1-элементных подмножеств /. Тогда мы имеем

(51 :С) V есть подмножество W, удовлетворяющего (49:W*), тогда

и только тогда, когда Fljlo .-удовлетворяемо.

Доказательство. То, что V и для W выполняется

(49:W*), означает следующее. W з V, W удовлетворяет (49:W*:a), (49:W*:b), т. е. является -насыщенным в силу (51:A). W удовлетворяет (49:W*:c), т. е. W 3 V0. Другими словами, мы ищем -насыщенное №э V \JV0, т. е. хотим узнать, может ли V[) V0 быть расширено до -насыщенного множества.

Далее, мы знаем, что применимо (30:G) из п. 30.3.5, и, следовательно, результаты последней части п. 30.3.5 также применимы 2). Возможность этого расширения эквивалентна -удовлетворяемости VJ V0.

51.2.3. Переформулируем (51 :С) более подробно.

(51 :D) Семейство V будет подмножеством W, удовлетворяющего

(49:W*), тогда и только тогда, когда оно обладает следующими свойствами:

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

(51:D:b) V не содержит ни 0, ни одноэлементных множеств.

Доказательство. Согласно (51 :С) мы должны доказать, J-удовлетворяемость V\j V0, т. е. что любые два S и Т из V или V0 пересекаются.

Если оба множества S и Т принадлежат У, то это совпадает с (51:D:a). Если оба множества S и Т принадлежат V0, то оба они имеют - 1 элементов. Следовательно, они не могут быть непересекающимися 3).

г) Следует вспомнить, что в п. 30.3.5 мы предполагали справедливость х?Ах, т. е. в нашем случае SMtS- Это означает, что S Ф 0, так как SMiS нарушается при S = 0.

Однако (49:W*:a) и (49:W*:b) исключают 0 из W; следовательно, мы можем использовать в качестве области D из п. 30.3.2, вместо / (семейства всех подмножеств /) 1 - 0 (семейство всех непустых подмножеств /). Это избавляет нас от S = 0.

2) Заметим, что область D = I - 0 (см. предыдущую сноску) конечна.

3) Мы используем то, что 2 (п - 1) > п, т. е. п > 2, т. е. п 3. Следовало бы сказать об этом подробно с самого начала, но это вполне естественное допущение, так как простые игры (т. е. множества с (49:W*)) существуют только для п 3 (см. пп. 49.4 и 49.5).



Из множеств S и Т одно принадлежит У, а другое У0. По симметрии можно предположить, что S £ У, а Т £ У0. Итак, 5 из F не может быть дизъюнктным с 7 или с любым п - 1-элементным множеством, а это совпадает с (51:D:b).

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

Читатель может попытаться проделать это для п = 3 или п = 4. Окажется, что даже для небольших п эта процедура чрезвычайно громоздка, хотя она является строгой и исчерпывающей для всех п.

51.3. Основания для перехода от ТУ к Wm. Трудности использования Wm

51.3.1. Рассмотрим семейства ТУШ из п. 49.6.

Мы хотим охарактеризовать эти ТУт непосредственно и найти некоторый простой процесс построения их всех. Далее мы выведем два различных способа характеризации, оба - типа насыщения. Первый 1>УДет введен асимметричным отношением, а второй- симметричным. Таким образом, именно второй способ, который подходит для искомого построения, аналогичен построению ТУ в п. 51.2.

Мы тем не менее приведем обе характеризации, потому что их эквивалентность весьма поучительна. Первая в некоторых (технических) отношениях напоминает определение решения (см. пп. 30.3.3 и 30.3.7), и, следовательно, переход к эквивалентной второй форме интересен тем, что указывает пути разрешения проблем этого типа. Ранее мы упоминали (в п. 30.3.7), сколь желателен мог бы быть соответствующий переход для нашего понятия решения.

51.3.2. Пусть ТУ - семейство, содержащее все надмножества своих элементов, например удовлетворяющее (49:W*:b). Тогда семейство ТУт его минимальных элементов определяет ТУ. Действительно, ясно, что ТУ является семейством надмножеств всех элементов ТУт.

Следовательно, если дано семейство У и мы ищем такое ТУ, удовлетворяющее (49:W*), что У = ТУШ, то это ТУ обязательно должно быть семейством У надмножеств всех элементов У.

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

ТУ = У2). Перейдем теперь к преобразованию этой характеризации у jym в харакхерИзацИЮ насыщения.

Обозначим утверждение, что ни S [} Т = 0, ни S zd Т, через SM2T. Тогда мы имеем:

(51 :Е) У = ТУт для ТУ, удовлетворяющего (49:W*), тогда и только

тогда, когда У 5?2-насыщено и не содержит ни 0, ни одноэлементных множеств.

х) В принципе мы можем начать с пустого множества. Читатель заметит, что исключение 0 из V (см. выше) не влияет на возможность V = 0.

2) То есть W = V есть единственное семейство, которое может удовлетворять этим требованиям, но даже для него они могут не выполняться.



Доказательство. Согласно сказанному выше мы должны проверить только, обладает ли W = У желательными свойствами.

V = Wm. Пусть S - минимальный элемент в этом ТУ. Тогда S э Т для некоторого Г из F. Т принадлежит W и поэтому минимальность S исключает S zd Т. Следовательно, S = Т, т. е. S принадлежит У.

Таким образом, остается рассмотреть только обратное свойство, т. е. будет ли каждое S £ У действительно минимальным в W. Любое ££У, очевидно, принадлежит W. Поэтому минимальность означает невозможность S zd Т, где Т £ ТУ, т. е. невозможность S zd Т 3 Г, где Г£У. Это влечет невозможность S =э Г, где Г£У, и, наоборот, следует из нее (при Т = Г). Итак, мы имеем следующее условие.

(51:2) Неверно, что S zd Т для 5, Г £ У.

ТУ удовлетворяет (49:W*). Мы должны рассмотреть (49:W*:a), (49:W*:b), (49:W*:c) порознь. Сделаем это в другом порядке.

(49:W*:b). Очевидно, что W = V содержит все надмножества своих элементов, поэтому данное условие выполняется автоматически.

(49:W*:c). Пусть (49:W*:a) доказано. (См. ниже.) Тогда (49:W*:c) может быть установлено так. Если S есть / или п - 1-элементное множество, то -S не принадлежит W. Следовательно, ни 0, ни одноэлементные множества не принадлежат W, т. е. никакое подмножество их не находится в У. Итак, мы имеем следующее условие:

(51:3) Ни 0, ни какое-либо одноэлементное множество не принад-

лежат У.

(49:W*:a). Рассмотрим доказательство в два этапа.

S и -S не могут одновременно принадлежать W. Поэтому если S и Т принадлежат У, то мы не можем иметь S S, Т -S. Существование такого S влечет S (] Т Ф 0 и, наоборот, следует отсюда (при S = S). Итак, мы имеем условие: (51:4) Неверно, что S (] Т = 0 для S, Т 6 У.

Одно из множеств S и -S должно принадлежать W. Предположим, что ни S, ни - S не принадлежит ТУ. Это означает, что ни для какого Т £ У не может быть Т S или Т -S. Последнее означает, что S (] Т = 0. Тем самым ни для какого Г £ У не может быть Т - S, или S zd Т, или S П Т = 0. Иначе говоря, S не принадлежит У, и ни для какого Т £ У не выполняется отрицание SM2T 1)-

Таким образом, S не принадлежит У, но S3i2T для всех Т £ У

Мы должны теперь выразить то, что это невозможно, т. е.

(51:5) Если SM2T для всех Т £ У, то £ принадлежит У.

Значит, (51:2)-(51:5) являются нужными критериями. Сформулируем (51:2) и (51:4) вместе следующим образом. SM2T для всех S, Т £ У, т. е.

(51:6) SM2T для всех Г £ У, если £ принадлежит У.

(51:5) и (51:6) вместе выражают 2-насыщенность У. Таким образом, это условие и (51:3) образуют критерий, и это в точности то, что мы хотели доказать.

(51 :Е) представляет некоторый интерес, потому что это - полный аналог (51 :В). Таким образом, эти характеризации W и Wm отличаются



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