В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 18
Текст из файла (страница 18)
В следующем рассуждении найдите недостающую посылку, связывающую высказывания «Прямые а и Ь лежат в одной плоскости» и «Прямые а и Ь скрещиваются» так, чтобы рассуждение было правильным: 1) «Прямые а и Ь либо параллельны, либо пересекаются, либо скрещиваются»; 2) «Прямые а и Ь лежат в одной плоскости и не пересекаются»; 3) ??? Следовательно, прямые лежат в одной плоскости и параллельны.
Р е ш е н и е. Введем обозначения для простейших высказываний, входящих в это рассуждение: Х: «Прямые а и Ь параллельны»; г' «Прямые а и Ь пересекаются; Х: «Прямые а и Ь скрещиваются»; К «Прямые а и Ь лежат в одной плоскости». Тогда задача сводится к отысканию такой формулы Г(с, р), зависящей от переменных уи р; что справедлива следующая выводимость: В задаче 2.40, л найдены все такие формулы (их пять). Одна из них: У-» -т К Придавим этой формуле смысл; «Если прямые а и Ь скрещиваются, то они не лежат в одной плоскости».
Сформулируйте остальные четыре угверждения, которые могут быть взяты в качестве посылки в данном рассуждении. 3.53. В следующем рассуждении найдите недостающую посылку так, чтобы рассуждение было правильным и посылка выражала связь между высказываниями: «Целое число оканчивается нулем»; «Целое число делится на 5»; «Целое число оканчивается цифрой 5». 1) Целое число делится на 5 и не оканчивается нулем; 2) ??? Следовательно, целое число оканчивается цифрой 5.
87 Логические задачи. Решить задачи 3.54 — 3.62. 3.54. Один из трех братьев Витя, Толя, Коля разбил окно. В разговоре участвуют еще двое братьев — Андрей и Дима. — Это мог сделать только или Витя, или Толя, — сказал Андрей. — Я окно не разбивал, — возразил Витя, — и Коля тоже. — Вы оба говорите неправду, — заявил Толя. — Нет, Толя, один из них сказал правду, а другой сказал неправду, — возразил Дима. — Ты, Дима, не прав, — вмешался Коля. Их отец, которому, конечно, можно доверять, уверен, что трое братьев сказали правду.
Кто разбил окно? Р е ш е н и е. Введем обозначения для высказываний: В: «Витя разбил окно»; Т: «Толя разбил окно»; К: «Коля разбил окно». Тогда высказывания братьев можно записать в символической форме следующим образом: А — = ВчТ; Р = — -1Вл -~К; Е: — -1А л -т 'г'— = -1(В ч Т) л -1(-1В л -тК) — = ~В л ~ Т л (В ч К) —= =— -1 Тл ((~В л В) ч (-1В л К)) = -1 Т л ~В л К; Р— = (А л.зР) ч (-1Ал Р) — = ((Вч Т) л-т(-чВл-~Х)) ч (-1(Вч Т) л л (~В л -1К)) — = ((В ч Т) л (В ч К)) ч (-1В л ~ Тл -1К) =— В ч (Т л К) ч ч (тВ л т Т л з К) — = (3 ч ч В) л (3 ч ч Т) л (В ч ~ К) — = В ч (т Т л ч К); ̻— з -«Рь— т -1(Вч (-1Тл -иК)) = — 1Вл (Тч Х). Образуем из высказываний А, г, Е, Р, М всевозможные конъюнкции по три высказывания: А л Ул Е А л г'л Р, А л Т, л Р, А л А л М, АлРлМ, г'л«,лР, РлЕлМ, 'глРлМ,ЕлРлМ,Ал ('лМ.
Поскольку из высказываний А, г', Т., Р, Мтолько три истинны, то из десяти конъюнкций истинна лишь одна. Проверьте самостоятельно, что конъюнкции А л Е, »'л.(«Ь л Р ложны, а потому восемь из перечисленных конъюнкций ложны. Остаются две конъюнкции: А л г л Р, А л Рл М. Проведем их преобразования: А л гл Р— = (В ч Т) л ~В л -тМл (В ч (т Тл ~М)) — = (В ч (Тл «Тл л -~М)) л -тВ л -1М вЂ” = 3 л -тВ л -1М вЂ” = О; А л Р'л Мьт (В ч Т) л чВ л -~Мл (Тч М) = — Тл ~Вл 'чМл Т— = Тл л -зВ л -1М. Итак, заключаем, что истинным может быть только высказывание А л гл Мили (эквивалентное ему) Тл -т В л «М, т е.
истинны высказывания Т, тВ и ~М, а значит, окно разбил Толя. 3.55. Один из трех братьев поставил на скатерть кляксу. — Витя не ставил кляксу, — сказал Алеша. — Это сделал Боря. — Ну, а ты что скажешь? — спросила бабушка Борю. — Это Витя поставил кляксу, — сказал Боря. — А Алеша не пачкал скатерть. — Я знаю, что Боря не мог это сделать. А я сегодня не готовил уроки, — сказал Витя. Оказалось, что двое мальчиков в каждом из двух случаев сказа- ли правду, а один оба раза сказал неправду. Кто поставил на ска- терть кляксу? У к а з а н и е. Образуйте прежде всего всевозможные попарные дизъюнкции из высказываний братьев.
Все они будут истинны. Затем рассмотрите конъюнкцию всех истинных дизъюнкций. Она тоже будет истинна. Преобразовав ее к конъюнкции элементарных выс- казываний, установите виновного. 3.56. Один из четырех мальчиков испортил выключатель. На вопрос «Кто это сделал?» были получены следующие ответы: 1) «Это сделал или Миша, или Коля»; 2) «Это сделал или Витя, или Коля»; 3) «Это не могли сделать ни Толя, ни Миша»; 4) «Это сделал или Витя, или Миша».
Можно ли по этим данным устано- вить, кто виновен в поломке выключателя, если из четырех вы- сказываний три — истинны? 3.57. Четыре друга — Антонов (А), Вехов (В), Сомов (С), Деев (Р) — решили провести свой отпуск в четырех различных горо- дах — Москве, Пятигорске, Киеве и Ташкенте. В какой город дол- жен поехать каждый из них, если имеются следующие ограничения: Р) если А не едет в Москву, то С не едет в Пятигорск; Ц)если В не едет ни в Москву, ни в Ташкент, то А едет в Москву; В) если Сне едет в Ташкент, то Ведет в Киев; В) если В не едет в Москву, то Ведет в Москву; Т) если Ю не едет в Пятигорск, то В не едет в Москву? Р е ш е н и е.
Символом Ам обозначим высказывание: «Антонов едет в Москву», символом -~Ам — высказывание «Антонов не едет в Москву». Аналогичны буквенные обозначения и для остальных друзей. Тогда ограничения запишутся так: Р = -1Ам-+ 'Се†= Амч-чС», Д— : (-тВм л -зВт) -+ Ам — = Вм ч Вт ч Ам' В = тСт-+ В» = Стч В»,' В = -ьЮм -+ Вм = 0м ч Вм„ Т вЂ” = .0» -+ -|Вм — = Рь ч -1Вм. Составляем последовательно конъюнкции этих высказываний, каждая из которых истинна: Р л Д: — (Ам ч -1 С») л (Вм ч Вт ч Ам) — = (Ам л Вм) ч (-з Ск л Вм) ч ч(Амл Вт) ч (-~С»л Вт) чАмч(-зС»лАм) =— (Амл Вт) чАмч (-зС»л л Вм) ч (чС» л Вт) = Ам ч (з С» л Вм) ч (тС» л Вт); Р л О л  — = (Ам ч (~ С» л Вм) ч (з Ск л Вт)) л ( Стч Вт)— : (Ам л л (Ст ч Вк)) ч ((~ С» л Вм) л (Ст ч Вк)) ч ( 1С» л Вт л (Ст ч Вт))) = — = (Ам л Ст) ч (Ам л В»)ч (-~ С» л Вм л Ст) ч (-з Сь л Вм л В») ч (т С» л л Вт л Ст) ч (ч С» л Вт л В») = — (Ам л Ст) ч (Ам л В»)ч (-юС» л Вм л Ст); Рл Ол Вл В— = ((Амл Ст) ч (Амл В») л (зС» л Вмл Ст)) л(Рмч 89 ч Вм) — = (Ам л Ст (т Рм ч Вм)) ч (Ам л Ст л Рм) ч (Ам л Сто Вт) ч (Ам ч л Вхл Рм) ч (Ам л Вх т Вм) ч (~ Се л Вм л Ст л Рм) ч (~ Се л Вм л Ст л т Рм) ч (Ам л Вх л Вм) ч (ч Сг л Вм л Ст л Рм) ч (ч Се л Вм л Ст л л Вм) = ч Сь л Вм л С~..
При проведении преобразований мы использовали факт, что ложны конъюнкции, в которых говорится, что одно лицо поедет в два разных города или что два разных человека поедуг в один город. Таким образом, мы установили, что конъюнкция -1См т Вм л См истинна, т.е. истинны высказывания Вм и Ст. Из условия Ти истинности Вм заключаем, что -зРы — истинно, т.е.
Рь ложно. Тогда истинно Ам Следовательно, истинно Р„. Итак, Антонов едет в Пятигорск, Вехов — в Москву, Сомов — в Ташкент, Деев — в Киев. 3.58. Шесть спортсменов — Адамов, Белов, Ветров, Глебов, Дронов, Ершов — в проходившем соревновании заняли шесть первых мест, причем ни одно место не было разделено между ними. О том, кто какое место занял, были получены такие высказывания: 1) «Кажется, первым был Адамов, а вторым — Дронов»; 2) «Нет, на первом месте был Ершов, а на втором — Глебов»; 3) «Вот так болельщики! Ведь Глебов был на третьем месте, а Белов — на четвертом»; 4) «И вовсе не так: Белов был пятым, а Адамов — вторым»; 5) «Все вы перепутали: пятым был Дронов, перед ним — Ветров», Известно, что в высказывании каждого болельщика одно утверждение истинное, а другое ложное. Определите, какое место занял каждый из спортсменов.
Указание. Рассмотрите высказывания: А,; «Адамов занял 1-е место» (1= 1, 2, 3, 4, 5, 6). Аналогичные значения имеют символы В» 1» 6» Рь Е» Высказывания болельщиков представьте в виде дизьюнкций. Все они будут истинны. Рассмотрите конъюнкцию этих истинных дизъюнкций. Преобразуйте эту конъюнкцию и, учитывая ее истинность, выведите распределение мест между спортсменами. 3.59. Для четырех дружинников, фамилии которых начинаются буквами А, Е, Р, С, необходимо составить график дежурств на четыре вечера подряд, учитывая, что: 1) С и Р не могут дежурить в первый вечер в связи с командировкой: 2) если С выйдет во второй вечер или Р— в третий, то Е сможет подежурить в четвертый; 3) если А не будет дежурить в третий вечер, то Е согласен дежурить во второй вечер; 4) если А или Р будут дежурить во второй вечер, то С сможет пойти в четвертый вечер; 5) если Р в четвертый вечер уедет на конференцию, то А придется дежурить в первый, а Св третий вечер.
З.бб. При составлении расписания уроков на один день учителя математики, истории и литературы высказали следующие пожелания: математик просил поставить ему или первый, или второй урок; историк — или первый, или третий; учитель литературы— или второй, или третий. Как составить расписание, чтобы учесть все пожелания? 90 3.61. Для полярной экспедиции из восьми претендентов А, В, С, Р, Е, Г, 6 и Н надо отобрать шесть специалистов: биолога, гидролога, синоптика, радиста, механика и врача.
Обязанности биолога могут выполнять Е и 6, гидролога — В и Г, синоптика— Ги 6, радиста — С и Р, механика — С и Н, врача — А и Р. Хотя некоторые претенденты владеют двумя специальностями, в экспедиции каждый сможет работать только по одной специальности. Кого и кем следует взять в экспедицию, если Г не может ехать без В, Р— без Н и без С, С не может ехать одновременно с 6, а А не может ехать вместе с В? 3.62. Некий остров населен жителями, каждый из которых либо всегда говорит правду, либо всегда лжет. Все жители отвечают на вопросы только «да» или «нет». К развилке дорог, из которых только одна ведет в столицу острова, подходит путешественник.
Никаких знаков, указывающих куда ведет каждая дорога, у развилки нет. Но здесь стоит местный житель, некто )ч. Какой вопрос, предусматривающий ответ «да» или «нет», должен задать ему путешественник, чтобы определить, какая дорога ведет в столицу острова? Р е ш е н и е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
