И. В. Раскина Логика для всех: от пиратов до мудрецов Издание третье, стереотипное

8.7. Истинны высказывания в пунктах 1, 3, 4, 5, 7.
Ложны высказывания 2, 6, 8.
8.8. Все три высказывания означают, что некузявых
ляпусиков не бывает.
Ответ. Равносильны.
8.9. Пусть Д спит. Тогда А и Г спят (из 5). Тогда Б спит
(из 1), поэтому В не спит (из 3). Но это противоречит 4.
Значит, Д не спит. Тогда спят Г (из 2) и В (из 4), а Б не
спит (из 3). Поэтому А не спит (из 1).
Ответ. В и Г.
8.10. Пусть мальчиков больше, чем девочек. Докажем
от противного, что при любой рассадке по кругу найдутся
два мальчика рядом. Предположим, что это не так, и рас-
смотрим произвольную рассадку. По предположению спра-
ва от каждого мальчика сидит девочка. То есть детей мож-
но разбить на пары «мальчик и девочка справа от него»,
при этом могут остаться без пары только девочки. Поэтому
их не меньше, чем мальчиков. Пришли к противоречию.
Пусть при любой рассадке по кругу найдутся два маль-
чика рядом. Рассмотрим произвольную рассадку и зануме-
руем детей по кругу по часовой стрелке. А затем посадим
детей в таком порядке: 1, 3, 5, 7, 9, 11, 13, 15, 17, 2, 4,
6, 8, 10, 12, 14, 16. По условию после этого найдутся два
мальчика рядом. Но раньше они сидели через одного, т. е.
в исходном положении был гость, сидевший между ними.
Пусть при любой рассадке по кругу найдется гость, си-
дящий между двумя мальчиками. Докажем от противно-
го, что мальчиков больше, чем девочек. Действительно,
если бы девочек было больше, детей можно было бы рас-
садить так: ДДГГДДГГДДГГДДГГД, где буква Д означает
девочку, а буква Г — гостя любого пола, и никто бы не си-
дел между двумя мальчиками.
8.11. 1) Всего существует 6 теорем указанного вида. Ес-
ли дать их все, то последняя будет следовать из предыду-
щих. А 5 можно дать в таком порядке: 1
⇒ 2, 1 ⇒ 3, 2 ⇒ 3,
3
⇒ 2, 3 ⇒ 1.
143

2) Всего существует 12 таких теорем. Как отмечено
в предыдущем пункте, с участием утверждений 1, 2 и 3
нельзя давать все 6 возможных теорем. Без ограничения
общности можно исключить теорему 2
⇒ 1. Но с участи-
ем утверждений 2, 3 и 4, а также 1, 3 и 4 тоже нельзя
давать все 6 возможных теорем. Если пытаться решить
обе проблемы исключением лишь одной теоремы, исклю-
чать надо 3
⇒ 4 или 4 ⇒ 3. В любом из случаев остается
цепочка из восьми теорем 1
⇒ 3 ⇒ 2 ⇒ 4 ⇒ 1, из которой
придется исключить как минимум одну теорему, и оста-
нется не более 9 теорем. Пример на 9 теорем: 1
⇒ 2, 1 ⇒ 3,
1
⇒ 4, 2 ⇒ 3, 2 ⇒ 4, 3 ⇒ 4, 4 ⇒ 3, 4 ⇒ 2, 4 ⇒ 1.
3) Пример на
(n − 1)(n + 2)
2
теорем:
1
⇒ 2, 1 ⇒ 3, ff, 1 ⇒ n,
2
⇒ 3, 2 ⇒ 4, ff, 2 ⇒ n,
ff
n − 1 ⇒ n,
n ⇒ n − 1, n ⇒ n − 2, ff, n ⇒ 1.
Доказательство максимальности удобно изложить на
языке графов. Будем считать утверждения вершинами, а
теоремы — ориентированными ребрами. Оставим только
ребра, ориентированные в обе стороны. Если бы они обра-
зовали цикл, то последняя доказанная в этом цикле тео-
рема следовала бы из предыдущих теорем цикла. Значит,
циклов нет. Тогда «двойных» ребер — не более n − 1, по-
этому всего доказано не более
n(n − 1)
2
+ n − 1 =
(n + 2)(n − 1)
2
теорем.

жүктеу/скачать 1.3 Mb.

Достарыңызбен бөлісу: