Учебное пособие Москва Издательство мцнмо 2007 удк 512. 1517. 1511. 1 Ббк 22. 14122. 161 П70 Прасолов В. В
 Скачать 3.28 Mb.
|
|
19.9. Выпишите таблицу истинности для каждого из следующих высказываний а) p & (¬p); б) p ∨ (¬p); в) ¬(p & г) (p ∨ q) ∨ (¬p). Решения задач 239 Составное высказывание называют тавтологией, если оно истинно при любых значениях входящих в него переменных. Являются ли следующие высказывания тавтоло- гиями: а) p ∨ (¬p); б) (¬(¬p)) ≡ p; в) ((p → q) → p) → г) ¬(p & (¬p))? 19.11. Докажите, что следующие высказывания эквивалентны, те. имеют одинаковые таблицы истинности p & и ¬((¬p) ∨ (¬q); p ∨ q и ¬((¬p) & (¬q); p → q и (¬q) → (¬p); p ≡ q и (p → q) & (q → p). 19.12. Докажите, что для любой данной таблицы истинности с помощью связок &, ¬ и ∨ можно составить высказывание, имеющее данную таблицу истинности, в случае: а) одной переменной б) двух переменных в) n переменных. Часть жителей острова всегда говорит правду, а остальные всегда лгут. Путешественник хочет выяснить, какая из двух дорог ведёт в деревню A, задав один вопрос встретившемуся ему местному жителю. Сможет ли он это сделать? Решения 19.1. В третьем ящике может лежать только чёрный шар. Белый шар может лежать только во втором ящике. Зелёный шар лежит в первом ящике. Нужно задать такой вопрос Если бы ты всегда говорил правду, то как бы ты ответил на вопрос Ты лжец Тот, кто всегда говорит правду, на этот вопрос ответит нет, а тот, кто всегда лжёт, ответит да. Ты всегда говоришь правду. Я тебя сегодня о чём-нибудь спрашивал. Занумеруем предметы номерами от 0 до 7. Зададим вопросы, входит ли выделенный предмет в группы {0, 2, 4, 6}, {0, 1, 4, и {0, 1, 2, 3}. Пусть e i = 0, если на й вопрос получен ответ «да», и e i = 1 в противном случае. Тогда выделенный предмет имеет номер e 1 + 2 e 2 + Действительно, запишем номера предметов в двоичной системе счисления a 0 + a 1 · 2 + a 2 · 4, где a i = 0 или 1. Тогда й вопрос можно переформулировать так Равно ли нулю Глава 19. Логика. Ответ. Из первого заявления для правдолюба с наименьшей нагрузкой следует, что в институте не более 10 правдолюбов, а для лжеца с наибольшей нагрузкой — что в институте не менее 10 правдолюбов. Из второго заявления для правдолюба с самой большой зарплатой следует, что в институте не менее лжецов, а для лжеца с самой маленькой зарплатой — что в институте не более 100 лжецов. Таким образом, в институте работает 10 правдолюбов и 100 лжецов. Ответ сидящий впереди знает, что на нём белая шляпа. Если бы на двух передних мудрецах были чёрные шляпы, то сидящий сзади мудрец знал бы, что на нём белая шляпа. Значит, хотя бы на одном из них шляпа белая. Поэтому если бы на сидящем впереди мудреце была бы чёрная шляпа, то сидящий посредине понял бы, что на нём самом — белая. Значит, на мудреце, сидящем впереди, шляпа белая. Докажем, что если испачкалось n мудрецов, то все они пойдут умываться на й остановке. При n=1 это очевидно испачкавшийся мудрец видит, что все остальные не испачкались, прич м он знает, что кто-то испачкался. Предположим, что требуемое утверждение доказано, если испачкалось не более n мудрецов. Рассмотрим случай, когда испачкалось n + 1 мудрецов. Каждый из испачкавшихся мудрецов рассуждает так. Возможны два варианта) я не испачкался, (2) я испачкался. При первом варианте испачкалось n мудрецов они выйдут на й остановке. Поэтому до й остановки мне не следует выходить, потому что первый вариант остаётся возможным. Но если на й остановке никто не выйдет, то, значит, я испачкался. Ответа) ЛЛ; б) ИИ; в) ЛИИИ; г) ИИИИ. 19.10. Ответ да, являются. В случаев) достаточно заметить, что для высказывания (p → q) → p таблица истинности имеет вид ИИЛЛ. 19.11. Все требуемые таблицы истинности легко составляются. а) Легко видеть, что высказывания p, ¬p, p & ¬p и p ∨ соответствуют всем возможным таблицам истинности. б) Высказывания p & q, p & (¬q), ¬p & q и ¬p & (¬q) принимают значение И ровно для одного из четырёх возможных наборов значений переменных p и q. Чтобы получить высказывание, принимающее значение И на двух, трёх или четырёх наборах, можно применить дизъюнкцию. Например, высказывание (p & q) ∨ (p & принимает значение И, если (p, q) = (И,И) или (p, q) = (И,Л). Высказывание p&¬p принимает значение Л для всех наборов переменных. Теперь мы построили требуемые высказывания для всех Решения задач 241 таблиц истинности. Отметим, что высказывание, принимающее значение И на всех четырёх наборах переменных, можно построить проще, а именно, взять высказывание p ∨ б) Решение для n переменных точно такое же, как для двух переменных. Высказывание p 1 & принимает значение Л для всех наборов переменных. Высказывания p 1 & p 2 & . . . & p n , ¬p 1 & p 2 & . . . . . . & и т. д. принимают значение И ровно для одного набора значений переменных (всего можно составить таких высказываний столько же, сколько есть разных наборов значений переменных. Высказывание, принимающее значение Ив точности для данных наборов значений, составляется из этих высказываний с помощью дизъюнкции. Пусть p — это утверждение, что дорога ведёт в A, q — это утверждение, что встретившийся местный житель правдив. Получаем следующую таблицу желаемых ответов и, соответственно, таблицу истинности требуемого высказывания (она, естественно, составляется на основе того, что правдивый говорит правду, а лжец лжёт): p q желаемый таблица ответ истинности И И да И И Л да Л Л И нет Л Л Л нет И Требуемое высказывание строится теперь так, как описано в решении задачи 19.12. Это будет высказывание Таким образом, нужно задать вопрос Верно ли, что ты правдив и эта дорога ведёт вили что ты лжец и эта дорога не ведёт в Житель ответит Да тогда и только тогда, когда дорога ведёт в Замечание. Легко проверить, что таблица истинности построенного высказывания (p & q) ∨ (¬p & ¬q) совпадает с таблицей истинности высказывания p ↔ q. Поэтому можно задать вопрос: «Верно ли, что ты правдив тогда и только тогда, когда эта дорога ведёт в A?» ГЛАВА СТРАТЕГИИ. ТУРНИРЫ. ТАБЛИЦЫ. Выбор стратегии. Перевозчику нужно переправить через реку волка, козу и капусту. В лодку он может взять только один из этих объектов. Кроме того, капусту нельзя оставить вместе с козой, а козу — с волком. Как осуществить переправу. Три солдата и три разбойника должны переправиться через реку. Они нашли лодку, в которую помещаются только два человека. На каждом берегу солдаты не могут оставаться, если их меньше, чем разбойников. Каким всем переправиться через реку. Семья ночью подошла к мосту. Папа может перейти егоза минуту, мама за 2, сын за 5, бабушка за У них есть один фонарик. Мост выдерживает только двоих. Как им перейти мост за 17 минут (Если помосту идут двое, то они идут с меньшей из их скоростей. Идти помосту без фонарика нельзя. Светить издали нельзя, перебрасывать фонарик через реку тоже нельзя. Двое играют в следующую игру. Есть 9 карточек с числами 1, 2, . . . , 9. Играющие по очереди берут себе по одной карточке. Выигрывает тот, у кого есть три карточки с числами, дающими в сумме 15. Докажите, что эта игра эквивалентна игре в «крестики-нолики» на доске размером × 3. Условия задач. Переливания. Есть полный кувшин молока ёмкостью 8 литров и два пустых кувшина в 5 литров и 3 литра. Как разделить молоко на две равные части. Есть полный кувшин молока ёмкостью 12 литров и два пустых кувшина в 8 литров и 5 литров. Как разделить молоко на две равные части. Есть четыре бочки. В первую входит 24 ведра, во вторую 13, в третью 11, в четвёртую 5. Первая бочка наполнена водой, а остальные бочки пустые. Как разделить воду натри равные части. Турниры При решении задач о турнирах нужно знать следующие пра- вила: а) в волейболе не бывает ничьих; б) в шахматах за победу присуждается 1 очко, за ничью 1/2 очка, за поражение 0 очков. Восемь волейбольных команд сыграли каждая с каждой по одному матчу. Докажите, что можно выбрать четыре команды a 1 , a 2 , a 3 , так, что команда выиграла у при i < j. 20.9. Алик, Боря и Вася сыграли несколько партий в шахматы, причём каждый сыграл одинаковое число партий. Могло ли при этом оказаться, что у Алика меньше всех проигрышей, у Бори больше всех выигрышей, ау Васи больше всего очков. а) В шахматном турнире участвовали два ученика класса и некоторое число учеников 8 класса. Два семиклассника набрали 8 очков, а каждый из восьмиклассников набрал одно и тоже число очков. Сколько восьмиклассников участвовало в турнире Найдите всевозможные реше- ния. б) В шахматном турнире участвовали ученики 9 и классов. Десятиклассников было враз больше, чем Глава 20. Стратегии. Турниры. Таблицы девятиклассников, и они набрали вместе в 4,5 раза больше очков, чем все девятиклассники. Сколько очков набрали девятиклассники. В соревнованиях участвуют 2 n боксёров. Каждый день проходят бои пар боксёров (каждый боксёр проводит ровно один бой. Все боксёры имеют разную силу, и в каждом бою побеждает сильнейший. Докажите, что за+ 1)/2 дня можно определить место каждого боксёра. (Расписания на каждый день составляются накануне вечером ив день соревнований не меняются. Взвешивания. Есть несколько мешков, в каждом из которых достаточно много монет. Водном мешке монеты фальшивые, а во всех других настоящие. Известен вес настоящей монеты и известно, что фальшивая монета на 1 грамм легче настоящей. Как при помощи одного взвешивания навесах с разновесками обнаружить мешок с фальшивыми монетами. Среди 26 одинаковых по виду монет есть одна фальшивая, которая легче остальных. Докажите, что затри взвешивания на чашечных весах (без стрелок и гирь) можно найти фальшивую монету. Среди 2n+1 монет есть 2k фальшивых (k6n), прич м вес фальшивой монеты отличается отвеса настоящей монеты на 1 грамм. Как заодно взвешивание на чашечных весах со стрелкой про одну выбранную монету узнать, фальшивая она или нет. Есть n мешков, в каждом из которых достаточно много монет. Есть несколько разных сортов монет. Монеты разного сорта имеют разный вес, причём их веса различаются на целое число граммов. Вес монеты каждого сорта известен. В каждом мешке лежат монеты одного сорта, но количество мешков с монетами данного сорта может быть произвольным. Как при помощи одного взвешивания на ве- Условия задач 245 сах с разновесками выяснить, какого сорта монеты лежат в каждом мешке. Некоторые из 20 металлических кубиков, одинаковых по размерами внешнему виду, алюминиевые, остальные* дюралевые (более тяжёлые). Как при помощи взвешиваний навесах с двумя чашками без гирь определить число дюралевых кубиков. а) Дано 2 (3 n − 3) монет (n > 2), среди которых есть одна фальшивая монета, отличающаяся повесу от настоящей. За n взвешиваний на чашечных весах без гирь нужно найти фальшивую монету и выяснить, тяжелее она или легче, чем настоящая. б) Сделайте тоже самое в случае, когда монет меньше 2 (3 n − 3), но больше двух. Таблицы. а) В прямоугольной таблице, составленной из положительных чисел, произведение суммы чисел любого столбца на сумму чисел любой строки равно числу, стоящему на их пересечении. Докажите, что сумма всех чисел в таблице равна единице. б) В прямоугольной таблице произведение суммы чисел любого столбца на сумму чисел любой строки равно числу, стоящему на их пересечении. Докажите, что либо сумма всех чисел в таблице равна единице, либо все числа равны нулю. Квадратная таблица в клеток заполнена числами от 1 до n так, что в каждой строке и каждом столбце встречаются все эти числа. Докажите, что если n нечётно и таблица симметрична относительно диагонали, идущей из Предполагается, что все кубики могут быть алюминиевыми, но они не могут быть все дюралевыми (если все кубики окажутся одного веса, то нельзя выяснить, алюминиевые они или дюралевые Глава 20. Стратегии. Турниры. Таблицы левого верхнего угла в правый нижний, тона этой диагонали встретятся все числа 1, 2, 3, . . . , n. 20.20. В клетках таблицы 8 × 8 записаны неотрицательные числа, сумма которых равна а) Сумма чисел, стоящих на одной из диагоналей, равна. Числа, расположенные симметрично относительно этой диагонали, равны. Докажите, что сумма чисел в любом столбце меньше б) Сумма чисел, стоящих на двух диагоналях, равна Числа, расположенные симметрично относительно любой диагонали, равны. Докажите, что сумма чисел в любой строке меньше 518. 20.21. Числа 1, 2, . . ., расположены в виде квадратной таблицы. . . , k, k + 1, k + 2, . . . , 2k, . . . . . . . . . . . . (k − 1)k + 1, . . . , . . . Выпишем произвольное число из этой таблицы, а затем вычеркнем строку и столбец, содержащие это число. Тоже самое проделаем с оставшейся таблицей из (k − чисел и т. д. k раз. Найдите сумму выписанных чисел. Решения 20.1. Сначала нужно перевезти через реку козу. После этого перевозчик возвращается, и есть два варианта дальнейших действий. Нужно перевезти капусту (волка, вернуться обратно с козой, оставить козу на берегу, перевезти волка (капусту) и потом перевезти козу. Будем указывать в скобках, кто плывёт в лодке. Переправиться через реку можно следующим образом РРСС(РС), РРСС(Р)С, РСС(РР)С, РСС(Р)РС, СС(РР)РС, СС(С)РРР, С(СС)РРР, С(Р)РРСС, (РС)РРСС. Решения задач. Основная идея состоит в том, что бабушка должна пройти помосту вместе с внуком. Сначала идут папа с мамой, затем папа возвращается с фонариком, после этого идут бабушка с внуком, затем мама возвращается с фонариком, наконец, папа с мамой переходят через мост. Всего на это будет затрачено 2 + 1+ 10+ 2+ 2= минут. Легко проверить, что есть ровно 8 троек карточек, дающих в сумме 15: (1, 5, 9), (1, 6, 8), (2, 4, 9), (2, 5, 8), (2, 6, 7), (3, 4, 8), (3, 5, 7) и (4, 5, 6). Эти 8 троек чисел — в точности тройки чисел, лежащих на одной прямой в таблице 9 4 7 5 3 6 Таким образом, цель играющего состоит в том, чтобы занять в этой таблице три клетки на одной вертикали, горизонтали или диагонали. Первое решение. Если в литровый, литровый и литровый кувшин налито, соответственно, a, b, c литров молока, то будем обозначать это (a, b, c). Можно применить такую последовательность переливаний: (8, 0, 0) →(3, 5, 0)→(3, 2, 3)→ → (6, 2, 0) → (6, 0, 2) → (1, 5, 2) → (1, 4, 3) → (4, 4, Второе решение. Если есть три кувшина ёмкостью a, b, c литров, то последовательные переливания n литров жидкости удобно изображать в правильном треугольнике со стороной Каждой точке внутри правильного треугольника со стороной можно сопоставить три неотрицательных числа x, y, z, сумма которых равна n. А именно, если через точку внутри правильного треугольника со стороной n провести прямые, параллельные сторонам треугольника, то образуются три маленьких треугольника со сторонами x, y, z; легко доказать, что x + y + z = n. Каждое из чисел x, y, z соответствует одной из сторон правильного треугольника. Будем считать, что этой стороне соответствует один из кувшинов, те. будем считать, что в кувшины ёмкостью a, b, c литров налито, соответственно, x, y, z литров. Переливания происходят в области, заданной неравенствами x 6 a, y 6 b, z 6 Каждое отдельное переливание представляет собой перемещение из одной точки границы данной области в другую точку границы в направлении, параллельном одной из сторон треугольника Глава 20. Стратегии. Турниры. Таблицы Два различных варианта решения задачи изображены на рис. 20.1. (8, 0, 0) (6, 2, 0) (4, 4, 0) (3, 5, 0) (6, 0, 2) (1, 5, 2) (1, 4, 3) (3, 2, 3) (8, 0, 0) (7, 1, 0) (7, 0, 1) (5, 3, 0) (4, 4, 0) (5, 0, 3) (2, 3, 3) (4, 1, 3) (2, 5, 1) (4, 1, 3) (2, 5, 1) (4, 1, 3) (2, 5, 1) (4, 1, 3) (2, 5, 1) (4, 1, 3) (2, 5, 1) (4, 1, 3) (2, 5, 1) (4, 1, 3) (2, 5, 1) (4, 1, 3) (2, 5, 1) (4, 1, 3) (2, 5, 1) (4, 1, 3) (2, 5, 1) (4, 1, 3) (2, 5, 1) (4, 1, 3) (2, 5, 1) (4, 1, 3) (2, 5, 1) (4, 1, 3) (2, 5, 1) (4, 1, 3) (2, 5, 1) (4, 1, 3) (2, 5, 1) (4, 1, 3) (2, 5, 1) (4, 1, 3) (2, 5, 1) (4, 1, 3) (2, 5, 1) (4, 1, 3) (2, 5, 1) (4, 1, 3) (2, 5, 1) (4, 1, 3) (2, 5, 1) (4, 1, 3) (2, 5, 1) (4, 1, 3) (2, 5, 1) (4, 1, 3) (2, 5, 1) (4, 1, 3) (2, 5, Рис. 20.1. Переливания. Можно применить такую последовательность перелива- ний: (12, 0, 0) → (4, 8, 0) → (0, 8, 4) → (8, 0, 4) → → (8, 4, 0) → (3, 4, 5) → (3, 8, 1) → (11, 0, 1) → → (11, 1, 0) → (6, 1, 5) → (6, 6, 0). 20.7. Можно применить следующие переливания, 0, 0, 0) → (19, 0, 0, 5) → (8, 0, 11, 5) → → (8, 11, 0, 5) → (0, 11, 8, 5) → (0, 13, 8, 3) → (8, 13, 0, 3) → → (8, 13, 3, 0) → (8, 8, 3, 5) → (8, 8, 8, 0). |