Логические задачи и способы их решения
Привет! Ты — мой внутренний голос, мой творческий наставник. Сегодня мы не просто будем решать задачи — мы научимся мыслить структурно, как программисты и аналитики. Готов взломать код логики? Поехали!
22.1. Метод рассуждений
Суть метода: Это чистый «stream of consciousness», но упорядоченный. Мы берем факты и последовательно выжимаем из них следствия, пока не найдем ответ. Это базовый алгоритм работы мозга.
🏠 Пример 1. Улица четырех домов
Представь классическую стратегию или квест. У нас есть 4 слота (дома) и 4 персонажа с разными классами (профессиями).
Условия:
- Столяр живет правее охотника.
- Врач левее охотника.
- Скрипач с краю.
- Скрипач рядом с врачом.
- Семён не скрипач и не сосед скрипача.
- Иван сосед охотника.
- Василий правее врача.
- Василий через дом от Ивана.
🔎 Давай рассуждать:
Рисуем четыре прямоугольника. Начнем с позиций. Скрипач с краю (дом 1 или 4). Но врач рядом с ним (усл. 4), а врач левее охотника (усл. 2). Значит, скрипач не может быть в доме 4.
Вывод 1: Скрипач в доме 1, врач в доме 2.
Охотник правее врача → Охотник в доме 3.
Столяр правее охотника → Столяр в доме 4.
Расстановка профессий:
1 — Скрипач
2 — Врач
3 — Охотник
4 — Столяр
Теперь имена. Василий правее врача (дом 3 или 4) и через дом от Ивана. Иван рядом с охотником (дом 3).
Итог:
1. Геннадий (Скрипач)
2. Иван (Врач)
3. Семён (Охотник)
4. Василий (Столяр)
22.2. Задачи о рыцарях и лжецах
Это прообраз компьютерного булева типа данных. Персонажи могут быть только двух состояний. Суть решения — перебор вариантов, где мы ищем противоречие.
✅ True (Истина)
Всегда говорит правду. Его слова соответствуют действительности.
❌ False (Ложь)
Всегда лжет. Каждое его утверждение неправда.
🗣️ Пример 2. Парадокс незнакомца
Ситуация: A и B беседуют. Незнакомец спрашивает A: «Ты рыцарь?». A отвечает неразборчиво. B говорит: «A сказал, что он лжец». Может ли A так сказать?
ЕСЛИ A — рыцарь:
Он скажет правду: "Я рыцарь".
(Сказать "Я лжец" было бы ложью).
ЕСЛИ A — лжец:
Он должен солгать. Истина — он лжец.
Значит, он скажет "Я рыцарь".
ИТОГ: Ни рыцарь, ни лжец никогда не скажут "Я лжец".
Значит, B — лжец, так как он приписал A невозможную фразу.
🏰 Пример 3. Город Лжецов и Правдивых
Ты пришел в один из двух городов. Нужно узнать, где ты, задав один вопрос «Да/Нет».
Вопрос: «Вы находитесь в своем городе?»
Сценарий 1: Ты в городе Правдивых.
- Местный П: "Да" (он дома).
- Местный Л: "Да" (он в гостях, но лжет).
Результат: Ответ "Да" → Город Правдивых.
Сценарий 2: Ты в городе Лжецов.
- Местный Л: "Нет" (он дома, но лжет).
- Местный П: "Нет" (он в гостях, говорит правду).
Результат: Ответ "Нет" → Город Лжецов.
22.3. Табличный метод
Когда объектов много, мозг перегружается. Мы строим матрицу, как в Excel. Это позволяет визуализировать связи. Заполняем ячейки: 1 (да), 0 (нет).
Таблица превращает хаос фактов в структурированную базу данных
🏕️ Пример 5. Летний лагерь
Четыре друга: Алеша, Боря, Витя, Гриша. Кружки: Математика, Авиамодели, Шахматы, Фото.
Из условий делаем выводы: Гриша ≠ Фото, Алеша ≠ Шахматы, Алеша ≠ Фото и ≠ Авиамодели.
Шаг 1: Алеша не подходит под 3 кружка.
Вывод: Алеша — Математика.
Шаг 2: Гриша не Фото и не Авиамодели.
Вывод: Гриша — Шахматы.
Шаг 3: Остались Витя и Боря.
Вывод: Витя — Авиамодели, Боря — Фото.
22.4. Таблицы истинности
Мы переводим слова на язык формул (A, B, C, ∧, ∨, →). Это позволяет решить задачу формально, как уравнение.
📈 Пример 6. Прибыль фирмы
Три подразделения (A, B, C). Три прогноза. Один ложный, два истинных.
Формулы прогнозов:
1. F1 = A → (B ∧ C)
2. F2 = A ↔ C
3. F3 = C → B
Составляем таблицу истинности.
Ищем строку, где две 1 и одна 0.
A B C | F1 | F2 | F3
0 1 1 | 1 | 0 | 1 ← Две истины (F1, F3), одна ложь (F2).
Ответ: Прибыль получили B и C.
22.5. Упрощение логических выражений
Аналог упрощения алгебраических выражений. Зачем перебирать таблицу, если выражение можно сократить? Это основа оптимизации кода.
🎓 Пример 7. Кто изучал логику?
Условие: «Если изучал первый, то изучал и второй, но неверно, что если изучал третий, то изучал и второй».
Формализация:
A — первый, B — второй, C — третий.
F = (A → B) ∧ ¬(C → B)
Упрощение:
1. Раскрываем импликацию: (¬A ∨ B) ∧ ¬(¬C ∨ B)
2. Закон де Моргана: (¬A ∨ B) ∧ (C ∧ ¬B)
3. Раскрываем скобки:
(¬A ∧ C ∧ ¬B) ∨ (B ∧ C ∧ ¬B)
Вторая скобка = 0 (ложь), так как B ∧ ¬B = 0.
Итог: ¬A ∧ C ∧ ¬B
Результат: Первый не изучал, Третий изучал, Второй не изучал.
📌 Самое главное
Давайте подведём итоги нашего путешествия в мир логики:
🚀 Проверь себя
Попробуй решить эти задачки, используя изученные методы.
1. Тест на «читерство» (Рыцари и лжецы)
Вы встретили 10 островитян по кругу. Каждый говорит: «Следующие 4 человека после меня — лжецы». Сколько среди них лжецов?
Подсказка: Если текущий — рыцарь, то следующие 4 — точно лжецы. Что скажет человек, стоящий сразу после этих 4-х лжецов?
2. Криптографическая задача (Метод рассуждений)
Три богини: Правда (всегда 1), Ложь (всегда 0) и Мудрость (рандом).
- Слева: «Рядом со мной Правда».
- В центре: «Я — Мудрость».
- Справа: «Рядом со мной Ложь».
Определи, кто где сидит.
3. Задача аналитика (Упрощение)
Подозреваются четверо: A, B, C, D.
- A: «Если я виновен, то B тоже виновен».
- B: «Если C виновен, то я не виновен».
- C: «A виновен или D виновен».
Известно: виновен ровно один человек, а все трое свидетелей сказали правду. Кто он?
