5.13. Як вирішувати логічні завдання?
Різноманітність логічних задач дуже велике. Способів їх вирішення теж чимало. Але найбільшого поширення набули наступні три способи вирішення логічних завдань:- засобами алгебри логіки;
- табличний;
- за допомогою міркувань.
Познайомимося з ними по черзі.
I. Рішення логічних задач засобами алгебри логіки
Зазвичай використовується наступна схема рішення:- вивчається умову задачі;
- вводиться система позначень для логічних висловлювань;
- конструюється логічна формула, що описує логічні зв'язки між усіма висловлюваннями умови задачі;
- визначаються значення істинності цієї логічної формули;
- з отриманих значень істинності формули визначаються значення істинності введених # 9; логічних висловлювань, на підставі яких робиться висновок про рішення.
Приклад 1. Троє друзів, уболівальників автогонок "Формула-1", сперечалися про результати майбутнього етапу гонок.
# 151; Ось побачиш, Шумахер не прийде першим, # 151; сказав Джон. Першим буде Хілл.
# 151; Та ні ж, переможцем буде, як завжди, Шумахер, # 151; вигукнув Нік. # 151; А про Алезі і говорити нема чого, йому не бути першим.
Пітер, до якого звернувся Нік, обурився:
# 151; Хіллу не бачити першого місця, а ось Алезі пілотує найпотужнішу машину.
По завершенні етапу гонок виявилося, що кожне з двох припущень двох друзів підтвердилося, а обидва припущення третього з друзів були невірними. Хто виграв етап гонки?
Рішення. Введемо позначення для логічних висловлювань:
Ш # 151; переможе Шумахер; Х # 151; переможе Хілл; А # 151; переможе Алезі.
Репліка Ніка "Алезі пілотує найпотужнішу машину" не містить ніякого твердження про місці, яке займе цей гонщик, тому в подальших міркуваннях не враховується.
Зафіксуємо висловлювання кожного з друзів:
З огляду на те, що припущення двох друзів підтвердилися, а припущення третього невірні, запишемо і спростимо справжнє висловлювання
Висловлення істинно тільки при Ш = 1, А = 0, Х = 0.
Відповідь. Переможцем етапу гонок став Шумахер.
Приклад 2. Якийсь любитель пригод відправився в кругосвітню подорож на яхті, оснащеної бортовим комп'ютером. Його попередили, що найчастіше виходять з ладу три вузла комп'ютера # 151; a. b. c. і дали необхідні деталі для заміни. З'ясувати, який саме вузол треба замінити, він може по сигнальним лампочкам на контрольній панелі. Лампочок теж рівно три: x. y і z.
Інструкція щодо виявлення несправних вузлів така:- якщо несправний хоча б один з вузлів комп'ютера, то горить принаймні одна з лампочок x. y. z;
- якщо несправний вузол a. але справний вузол с. то загоряється лампочка y;
- якщо несправний вузол с. але справний вузол b. загоряється лампочка y. але не загоряється лампочка x;
- якщо несправний вузол b. але справний вузол c. то спалахують лампочки x і y або не світиться лампочка x;
- якщо горить лампочка х і при цьому або несправний вузол а. або всі три вузла a. b. c справні, то горить і лампочка y.
У шляху комп'ютер зламався. На контрольній панелі загорілася лампочка x. Ретельно вивчивши інструкцію, мандрівник полагодив комп'ютер. Але з цього моменту і до кінця плавання його не залишала тривога. Він зрозумів, що інструкція недосконала, і є випадки, коли вона йому не допоможе.
Які вузли замінив мандрівник? Які вади він виявив в інструкції?
Рішення. Введемо позначення для логічних висловлювань:
Правила 1-5 виражаються наступними формулами:
Формули 1-5 істинні за умовою, отже, їх кон'юнкція теж істинна:
Висловлюючи імплікації через диз'юнкцію і заперечення (нагадаємо, що), отримуємо:
Підставляючи в це тотожність конкретні значення істинності x = 1, y = 0, z = 0, отримуємо:
Звідси випливає, що a = 0, b = 1, c = 1.
Відповідь на перше питання завдання: потрібно замінити блоки b і c; блок а не вимагає заміни. Відповідь на друге запитання задачі отримаєте самостійно.
II. Рішення логічних задач табличним способом
При використанні цього способу умови, які містить завдання, і результати міркувань фіксуються за допомогою спеціально складених таблиць.
Приклад 3. У симфонічний оркестр взяли на роботу трьох музикантів: Брауна, Сміта і Вессона, які вміють грати на скрипці, флейті, альті, кларнеті, гобої і трубі.
Відомо що:- Сміт найвищий;
- грає на скрипці менше зростанням грає на флейті;
- грають на скрипці і флейті і Браун люблять піцу;
- коли між альтистом і трубачем виникає сварка, Сміт мирить їх;
- Браун не вміє грати ні на трубі, ні на гобої.
На яких інструментах грає кожен з музикантів, якщо кожен володіє двома інструментами?
Рішення. Складемо таблицю і відобразимо в ній умови задачі, заповнивши відповідні клітини цифрами 0 і 1 в залежності від того, помилково або істинно відповідне висловлювання.
Так як музикантів трoе, інструментів шість і кожен володіє тільки двома інструментами, виходить, що кожен музикант грає на інструментах, якими інші не володіють.
З умови 4 випливає, що Сміт не грає ні на альті, ні на трубі, а з умов 3 і 5, що Браун не вміє грати на скрипці, флейті, трубі і гобої. Отже, інструменти Брауна # 151; альт і кларнет. Занесемо це у таблицю, а що залишилися клітини стовпців "альт" і "кларнет" заповнимо нулями:
Відповідь: Браун грає на альті і кларнеті, Сміт # 151; на флейті і гобої, Вессон # 151; на скрипці і трубі.
Приклад 4. Три однокласника # 151; Влад, Тимур і Юра, зустрілися через 10 років після закінчення школи. З'ясувалося, що один з них став лікарем, інший фізиком, а третій юристом. Один полюбив туризм, інший біг, пристрасть третього # 151; регбі.
Юра сказав, що на туризм йому не вистачає часу, хоча його сестра # 151; єдиний лікар в сім'ї, завзятий турист. Лікар сказав, що він розділяє захоплення колеги.
Забавно, але у двох із друзів в назвах їх професій і захоплень не зустрічається ні одна буква їх імен.
Визначте, хто чим любить займатися у вільний час і у кого яка професія.
Рішення. Тут вихідні дані розбиваються на трійки (ім'я # 151; професія # 151; захоплення).
З слів Юри ясно, що він не захоплюється туризмом і він не лікар. З слів лікаря слід, що він турист.
Буква "а", присутня в слові "лікар", вказує на те, що Влад теж не лікар, отже лікар # 151; Тимур. В його імені є літери "т" і "р", що зустрічаються в слові "туризм", отже другий з друзів, в назвах професії і захоплення якого не зустрічається ні одна буква його імені # 151; Юра. Юра не юрист і не регбіст, так як в його імені містяться літери "ю" і "р". Отже, остаточно маємо:
Відповідь. Влад # 151; юрист і регбіст, Тимур # 151; лікар і турист, Юра # 151; фізик і бігун.
Приклад 5. Три дочки письменниці Доріс Кей # 151; Джуді, Айріс і Лінда, теж дуже талановиті. Вони стали відомими в різних видах мистецтв # 151; співі, балеті і кіно. Всі вони живуть в різних містах, тому Доріс часто дзвонить їм в Париж, Рим і Чикаго.
Відомо що:- Джуді живе не в Парижі, а Лінда # 151; не в Римі;
- парижанка не знімається в кіно;
- та, хто живе в Римі, співачка;
- Лінда байдужа до балету.
Де живе Айріс, і яка її професія?
Рішення. Складемо таблицю і відобразимо в ній умови 1 і 4, заповнивши клітини цифрами 0 і 1 в залежності від того, помилково або істинно відповідне висловлювання:
Далі розмірковуємо наступним чином. Так як Лінда живе не в Римі, то, згідно з умовою 3, вона не співачка. У клітку, відповідну рядку "Лінда" і одну "Спів", ставимо 0.
З таблиці відразу видно, що Лінда кіноактриса, а Джуді і Айріс не знімає в кіно.
Згідно з умовою 2, парижанка не знімається в кіно, отже, Лінда живе не в Парижі. Але вона живе і не в Римі. Отже, Лінда живе в Чикаго. Так як Лінда і Джуді живуть не в Парижі, там живе Айріс. Джуді живе в Римі і, згідно з умовою 3, є співачкою. А так як Лінда кіноактриса, то Айріс балерина.
В результаті поступового заповнення отримуємо наступну таблицю:
Відповідь. Айріс балерина. Вона живе в Парижі.
III. Рішення логічних задач за допомогою міркувань
Цим способом зазвичай вирішують нескладні логічні завдання.
Приклад 6. Вадим, Сергій і Михайло вивчають різні іноземні мови: китайський, японський і арабська. На питання, яку мову вивчає кожен з них, один відповів: "Вадим вивчає китайську, Сергій не вивчає китайську, а Михайло не вивчає арабську". Згодом з'ясувалося, що в цій відповіді тільки одне твердження вірне, а два інших помилкові. Яку мову вивчає кожен з молодих людей?
Рішення. Є три твердження:- Вадим вивчає китайську;
- Сергій не вивчає китайську;
- Михайло не вивчає арабську.
Якщо вірно перше твердження, то вірно і друге, так як юнаки вивчають різні мови. Це суперечить умові завдання, тому перше твердження помилкове.
Якщо вірно друге твердження, то перше і третє повинні бути помилкові. При цьому виходить, що ніхто не вивчає китайську. Це суперечить умові, тому друге твердження теж помилково.
Залишається вважати це остання причина твердження, а перше і друге # 151; помилковими. Отже, Вадим не вивчає китайський, китайський вивчає Сергій.
Відповідь: Сергій вивчає китайську мову, Михайло # 151; японський, Вадим # 151; арабська.
Приклад 7. У поїздці п'ятеро друзів # 151; Антон, Борис, Вадим, Діма і Гриша, знайомилися з попутницею. Вони запропонували їй відгадати їх прізвища, причому кожен з них висловив одне справжнє і одне хибне твердження:
Діма сказав: "Моє прізвище # 151; Мішин, а прізвище Бориса # 151; Хохлов ". Антон сказав:" Мішин # 151; це моє прізвище, а прізвище Вадима # 151; Бєлкін ". Борис сказав:" Прізвище Вадима # 151; Тихонов, а моє прізвище # 151; Мішин ". Вадим сказав:" Моє прізвище # 151; Бєлкін, а прізвище Грицька # 151; Чехов ". Гриша сказав:" Так, моє прізвище Чехов, а прізвище Антона # 151; Тихонов ".
Яке прізвище носить кожен із друзів?
Рішення. Позначимо висказивательную форму "юнак на ім'я А носить прізвище Б" як АБ. де літери А і Б відповідають початковими літерами імені та прізвища.
Припустимо спочатку, що істинно ДМ. Але, якщо істинно ДМ. то у Антона і у Бориса повинні бути інші прізвища, значить АМ і БМ помилково. Але якщо АМ і БМ помилкові, то повинні бути щирі СБ і ОТ. але ВБ і ВТ одночасно істинними бути не можуть.
Значить залишається інший випадок: Поправді БХ. Цей випадок призводить до ланцюжка умовиводів:
БХ істинно БМ помилково ВТ істинно АТ помилково ГЧ істинно СБ помилково АМ істинно.
Відповідь: Борис # 151; Хохлов, Вадим # 151; Тихонов, Гриша # 151; Чехов, Антон # 151; Мішин, Діма # 151; Бєлкін.
Приклад 8. Міністри закордонних справ Росії, США і Китаю обговорили за зачиненими дверима проекти угоди про повне роззброєння, представлені кожної з країн. Відповідаючи потім на запитання журналістів: "Чий саме проект був прийнятий?", Міністри дали такі відповіді: Росія # 151; "Проект не наш, проект не США";
США # 151; "Проект не Росії, проект Китаю";
Китай # 151; "Проект не наш, проект Росії".
Один з них (самий відвертий) обидва рази говорив правду; другий (самий потайний) обидва рази говорив неправду, третій (обережний) один раз сказав правду, а інший раз # 151; неправду.
Визначте, представниками яких країн є відвертий, потайний і обережний міністри.
Рішення. Для зручності запису пронумеруємо висловлювання дипломатів: Росія # 151; "Проект не наш" (1), "Проект не США" (2);
США # 151; "Проект не Росії" (3), "Проект Китаю" (4);
Китай # 151; "Проект не наш" (5), "Проект Росії" (6).
Дізнаємося, хто з міністрів самий відвертий.
Якщо це російський міністр, то з справедливості (1) і (2) випливає, що переміг китайський проект. Але тоді обидва твердження міністра США теж справедливі, чого не може бути за умовою.
Якщо самий відвертий # 151; міністр США, то тоді знову отримуємо, що переміг китайський проект, значить обидва твердження російського міністра теж вірні, чого не може бути за умовою.
Виходить, що найбільш відвертим був китайський міністр. Дійсно, з того, що (5) і (6) справедливі, cледует, що переміг російський проект. А тоді виходить, що з двох тверджень російського міністрів перший помилково, а друге вірно. Обидва ж твердження міністра США невірні.
Відповідь: Відвертіше був китайський міністр, обережніше # 151; російський, потайний # 151; міністр США.