WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     | 1 |   ...   | 24 | 25 || 27 | 28 |   ...   | 65 |

i=Несложные вычисления показывают, что F (X) - F (Y ) = -2xi(x1 + x2 + x3 + x4 + x5) > 0, т.е. F (Y ) < F (X). Это означает, что после каждой операции целое неотрицательное число F (X) строго уменьшается. Такой процесс не может продолжаться бесконечно долго.

18.7. Возьмём произвольные попарно различные числа x1,..., xn и рас - xj xi смотрим число = ±1. Покажем, что если это число равно 1, i>j x(i) - x(j) то числа m1 и m2 чётные, а если оно равно -1, то числа m1 и m2 нечётные.

Предположим сначала, что транспозиция, т.е. (i) = j, (j) = i и (k) = k при k = i, j. Пусть для определённости i < j. Тогда в рассматривае xi - xj мое произведение входит дробь = -1. Легко также проверить, что для xj - xi каждого k = i, j произведение соответствующих дробей для пар чисел (k, i) и (k, j) равно 1. Действительно, если k < i < j, то получаем произведение xi - xk xj - xk xk - xi xj - xk · ; если i < k < j, получаем · ; если i < j < k, xj - xk xi - xk xk - xj xi - xk xk - xi xk - xj получаем ·. Ясно также, что все остальные дроби равны 1.

xk - xj xk - xi Таким образом, для одной транспозиции получаем число -1.

Глава 18. Инварианты и полуинварианты Если после транспозиции мы сделаем ещё транспозицию, то для полученной в результате перестановки рассматриваемое число равно 1, поскольку xi - xj xi - xj ±(x(i) - x(j)) = ·, x ((i)) - x ((j)) x(i) - x(j) ±(x ((i)) - x ((j))) т.е. рассматриваемые числа для и для перемножаются. Аналогично доказывается, что после каждой транспозиции рассматриваемое число меняет знак.

18.8. О т в е т: нет, нельзя. Сопоставим свободной клетке номер 16. Тогда после каждого хода получается некоторая перестановка чисел 1,..., 16.

При этом каждый ход представляет собой транспозицию. Мы хотим в итоге получить транспозицию 14 15.

Покажем, что свободная клетка может вернуться на исходное место только после чётного числа ходов, т.е. чётного числа транспозиций. Согласно задаче 18.7 из этого следует, что так нельзя получить транспозицию.

Чтобы вернуться на исходное место, свободная клетка должна сделать вверх столько же ходов, сколько вниз, и влево столько же, сколько вправо.

Поэтому общее число ходов должно быть чётно.

18.9. Достаточно доказать, что из любой перестановки (1),..., (n) можно получить набор 1,..., n, сделав несколько транспозиций (эти транспозиции можно будет сделать в обратном порядке). Если (1) = 1, то поменяем местами 1 и (1). Затем в новом наборе чисел поменяем местами 2 и (2), если (2) = 2, и т.д.

18.10. Достаточно доказать, что после каждой транспозиции изменяется чётность числа всех инверсий. Пусть при транспозиции меняются местами числа (i) и (j). Тогда инверсия может появиться или исчезнуть только для пар (i, k) и (j, k). Легко видеть, что появление или исчезновение инверсии может произойти только в том случае, когда k заключено между i и j, а (k) заключено между (i) и (j). Но в этом случае обе инверсии одновременно либо появляются, либо исчезают.

18.11. а) Пусть при транспозиции переставляются числа a и b. Рассмотрим два случая.

1. Числа a и b входят в один цикл (a, a1,..., ap, b, b1,..., bq). Тогда после транспозиции из этого цикла получаются два цикла (a, a1,..., ap) и (b, b1,..., bq), поскольку a a1, a2 a3,..., ap b a и b b1,..., bq a b. Остальные циклы не меняются.

2. Числа a и b входят в разные циклы (a, a1,..., ap) и (b, b1,..., bq).

Тогда после транспозиции из этих двух циклов получится один цикл (a, a1,..., ap, b, b1,..., bq), поскольку a a1,..., ap a b, b b1,..., bq b a.

б) Разобьём все перестановки на два класса: те, для которых число n - m чётно, и те, для которых число n - m нечётно. Первый класс содержит тождественную перестановку 1, 2,..., n (для неё n - m = 0). Второй класс содержит все транспозиции (для них n - m = 1). Согласно задаче а) применение 212 Глава 18. Инварианты и полуинварианты транспозиции изменяет класс. Поэтому перестановки, которые получаются из тождественной чётным числом транспозиций, лежат в первом классе, а перестановки, которые получаются из тождественной нечётным числом транспозиций, лежат во втором классе.

Глава 19.

Логика 19.1. Логические задачи 19.1. В трёх ящиках лежат шары чёрный, белый и зелёный (в каждом ящике по одному шару). На первом ящике написано: белый, на втором чёрный, на третьем белый или зелёный. Известно, что ни одна надпись не соответствует действительности. Выясните, где какие шары лежат.

19.2. Путешественник попал на остров, часть обитателей которого всегда говорит правду, а остальные всегда лгут. Какой вопрос должен задать путешественник обитателю острова, чтобы выяснить, всегда ли он говорит правду или всегда лжёт 19.3. Один человек всегда говорит правду, а другой человек всегда лжёт. Какой вопрос нужно им задать, чтобы они ответили на него одинаково 19.4. Некто всегда говорит правду. Какой вопрос нужно ему задать дважды, чтобы он дал на него разные ответы 19.5. Дано 8 предметов, один из которых выделен. Требуется задать 3 вопроса, на которые даются только ответы да и нет, и узнать, какой предмет выделен.

19.6. В институте работают правдолюбы, которые всегда говорят правду, и лжецы, которые всегда лгут. Однажды каждый из сотрудников сделал два заявления.

1) В институте нет и десяти человек, которые работают больше меня.

214 Глава 19. Логика 2) В институте по крайней мере у ста человек зарплата больше, чем у меня.

Известно, что нагрузка у всех сотрудников разная, и зарплата тоже.

Сколько человек работает в институте 19.7. Три мудреца сидят на стульях в затылок друг другу так, что сидящий впереди не видит тех, кто сидит сзади. Они знают, что есть белых и 2 чёрных шляпы. Мудрецы зажмуривают глаза и им на головы надевают шляпы, после чего оставшиеся шляпы убирают. Мудрецы открывают глаза, и сидящий сзади всех говорит, что он не знает, какого цвета на нём шляпа. После этого сидящий посредине говорит, что он тоже не знает, какого цвета на нём шляпа. Знает ли теперь сидящий впереди, какого цвета на нём шляпа 19.8. В вагоне поезда едут несколько мудрецов. Когда поезд проехал туннель, в окна попала пыль. Вошёл проводник и сказал: У некоторых из вас испачкались лица. К сожалению, в поезде нет воды. Но сейчас будут большие остановки, поэтому можно будет выйти из поезда и умыться. На n-й остановке испачкавшиеся мудрецы вышли из поезда, чтобы умыться. Сколько мудрецов испачкалось (Мудрец идёт умываться тогда и только тогда, когда он точно знает, что испачкался.) 19.2. Логические парадоксы Парадокс лжеца Некто произносит фразу: Высказывание, которое я сейчас произношу, ложно. Ложно само это высказывание или нет Если допустить, что это высказывание истинно, то оно должно быть ложным, а если допустить, что это высказывание ложно, то оно должно быть истинным.

Парадокс парикмахера Деревенский парикмахер бреет тех и только тех жителей своей деревни, которые не бреют себя сами. Бреет ли он себя Если допустить, что он не бреет себя, то он должен себя брить, а если допустить, что он бреет себя, то он не должен себя брить.

Парадокс Ришара Рассмотрим множество всех натуральных чисел, каждое из которых может быть однозначно определено посредством осмысленного Глава 19. Логика текста, содержащего не более тысячи слогов. Это множество конечно, поскольку таких текстов конечное число. Рассмотрим наименьшее натуральное число, не входящее в указанное множество.

Выделенный курсивом абзац содержит менее тысячи слогов, поэтому он определяет число из рассматриваемого множества. С другой стороны, он определяет число, не входящее в это множество.

19.3. Логика высказываний Пусть p и q некоторые высказывания, каждое из которых может быть либо истинным (И), либо ложным (Л). Из них можно составить следующие составные высказывания:

¬p отрицание: p неверно ;

p&q конъюнкция: верны p и q ;

p q дизъюнкция: верно p или q ;

p q импликация: p влечёт q, т.е. q верно, если p верно;

p q эквивалентность: p эквивалентно q.

Эти составные высказывания имеют следующие таблицы истинности:

p q ¬p p&q p q p q p q И И Л И И И И И Л Л Л И Л Л Л И И Л И И Л Л Л И Л Л И И Для конъюнкции часто используется также обозначение, а для эквивалентности обозначение.

19.9. Выпишите таблицу истинности для каждого из следующих высказываний: а) p&(¬p); б) p (¬p); в) ¬(p&q); г) (p q) (¬p).

Составное высказывание называют тавтологией, если оно истинно при любых значениях входящих в него переменных.

19.10. Являются ли следующие высказывания тавтологиями:

а) p (¬p); б) (¬(¬p)) p; в) ¬(p&(¬p)); г) ((p q) p) p 19.11. Докажите, что следующие высказывания эквивалентны, т.е. имеют одинаковые таблицы истинности: p&q и ¬((¬p) (¬q);

p q и ¬((¬p)&(¬q); p q и (¬q) (¬p); p q и (p q)&(q p).

19.12. Докажите, что для любой данной таблицы истинности с помощью связок &, ¬ и можно составить высказывание, имеющее данную 216 Глава 19. Логика таблицу истинности, в случае: а) одной переменной; б) двух переменных; в) n переменных.

19.13. Часть жителей острова всегда говорит правду, а остальные всегда лгут. Путешественник хочет выяснить, какая из двух дорог ведёт в деревню A, задав один вопрос встретившемуся ему местному жителю.

Сможет ли он это сделать Решения 19.1. В третьем ящике может лежать только чёрный шар. Белый шар может лежать только во втором ящике. Зелёный шар лежит в первом ящике.

19.2. Нужно задать такой вопрос: Если бы ты всегда говорил правду, то как бы ты ответил на вопрос: "Ты лжец" Тот, кто всегда говорит правду, на этот вопрос ответит: нет, а тот, кто всегда лжёт, ответит: да.

19.3. Ты всегда говоришь правду 19.4. Я тебя сегодня о чём-нибудь спрашивал 19.5. Занумеруем предметы номерами от 0 до 7. Зададим вопросы, входит ли выделенный предмет в группы {0, 2, 4, 6}, {0, 1, 4, 5} и {0, 1, 2, 3}. Пусть i = = 0, если на i-й вопрос получен ответ да, и i = 1 в противном случае. Тогда выделенный предмет имеет номер 1 + 22 + 43.

Действительно, запишем номера предметов в двоичной системе счисления: a0 + a1 · 2 + a2 · 4, где ai = 0 или 1. Тогда k-й вопрос можно переформулировать так: Равно ли ak-1 нулю 19.6. О т в е т: 110. Из первого заявления для правдолюба с наименьшей нагрузкой следует, что в институте не более 10 правдолюбов, а для лжеца с наибольшей нагрузкой что в институте не менее 10 правдолюбов. Из второго заявления для правдолюба с самой большой зарплатой следует, что в институте не менее 100 лжецов, а для лжеца с самой маленькой зарплатой что в институте не более 100 лжецов. Таким образом, в институте работает 10 правдолюбов и 100 лжецов.

19.7. О т в е т: сидящий впереди знает, что на нём белая шляпа. Если бы на двух передних мудрецах были чёрные шляпы, то сидящий сзади мудрец знал бы, что на нём белая шляпа. Значит, хотя бы на одном из них шляпа белая.

Поэтому если бы на сидящем впереди мудреце была бы чёрная шляпа, то сидящий посредине понял бы, что на нём самом белая. Значит, на мудреце, сидящем впереди, шляпа белая.

19.8. Докажем, что если испачкалось n мудрецов, то все они пойдут умываться на n-й остановке. При n = 1 это очевидно: испачкавшийся мудрец видит, что все остальные не испачкались, причём он знает, что кто-то испачкался. Предположим, что требуемое утверждение доказано, если испачкалось не более n мудрецов. Рассмотрим случай, когда испачкалось n + 1 мудрецов.

Глава 19. Логика Каждый из испачкавшихся мудрецов рассуждает так. Возможны два варианта: (1) я не испачкался, (2) я испачкался. При первом варианте испачкалось n мудрецов; они выйдут на n-й остановке. Поэтому до n-й остановки мне не следует выходить, потому что первый вариант остаётся возможным. Но если на n-й остановке никто не выйдет, то, значит, я испачкался.

19.9. О т в е т: а) ЛЛ; б) ИИ; в) ЛИИИ; г) ИИИИ.

19.10. О т в е т: да, являются. В случае г) достаточно заметить, что для высказывания (p q) p таблица истинности имеет вид ИИЛЛ.

19.11. Все требуемые таблицы истинности легко составляются.

19.12. а) Легко видеть, что высказывания p, ¬p, p&¬p и p ¬p соответствуют всем возможным таблицам истинности.

б) Высказывания p&q, p&(¬q), ¬p&q и ¬p&(¬q) принимают значение И ровно для одного из четырёх возможных наборов значений переменных p и q.

Чтобы получить высказывание, принимающее значение И на двух, трёх или четырёх наборах, можно применить дизъюнкцию. Например, высказывание (p&q) (p&¬q) принимает значение И, если (p, q) = (И,И) или (p, q) = (И,Л).

Высказывание p&¬p принимает значение Л для всех наборов переменных.

Теперь мы построили требуемые высказывания для всех таблиц истинности.

Отметим, что высказывание, принимающее значение И на всех четырёх наборах переменных, можно построить проще, а именно, взять высказывание p ¬p.

б) Решение для n переменных точно такое же, как для двух переменных.

Высказывание p1&¬p1 принимает значение Л для всех наборов переменных.

Высказывания p1&p2&... &pn, ¬p1&p2&... &pn и т.д. принимают значение И ровно для одного набора значений переменных (всего можно составить 2n таких высказываний столько же, сколько есть разных наборов значений переменных). Высказывания, принимающее значение И в точности для данных наборов значений, составляется из этих высказываний с помощью дизъюнкции.

19.13. Пусть p это утверждение, что дорога ведёт в A, q это утверждение, что встретившийся местный житель правдив. Получаем следующую таблицу желаемых ответов и, соответственно, таблицу истинности требуемого высказывания (она, естественно, составляется на основе того, что правдивый говорит правду, а лжец лжёт):

p q желаемый таблица ответ истинности И И да И И Л да Л Л И нет Л Л Л нет И Требуемое высказывание строится теперь так, как описано в решении задачи 19.12. Это будет высказывание (p&q) (¬p&¬q). Таким образом, нужно 218 Глава 19. Логика задать вопрос: Верно ли, что ты правдив и эта дорога ведёт в A, или что ты лжец и эта дорога не ведёт в A Житель ответит Да тогда и только тогда, когда дорога ведёт в A.

Замечание. Легко проверить, что таблица истинности построенного высказывания (p&q) (¬p&¬q) совпадает с таблицей истинности высказывания p q. Поэтому можно задать вопрос: Верно ли, что ты правдив тогда и только тогда, когда эта дорога ведёт в A Глава 20.

Стратегии. Турниры.

Таблицы 20.1. Выбор стратегии 20.1. Перевозчику нужно переправить через реку волка, козу и капусту. В лодку он может взять только один из этих объектов. Кроме того, капусту нельзя оставить вместе с козой, а козу с волком. Как осуществить переправу 20.2. Три солдата и три разбойника должны переправиться через реку. Они нашли лодку, в которую помещаются только два человека.

На каждом берегу нельзя оставлять больше разбойников, чем солдат.

Pages:     | 1 |   ...   | 24 | 25 || 27 | 28 |   ...   | 65 |



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.