Решение задачи: фрегат и эсминец

Вот решения задач, оформленные так, чтобы их было удобно переписать в тетрадь школьнику. 1. В таблице приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета: Запрос | Количество страниц (тыс.) ---|--- фрегат | эсминец | 3000 фрегат | 2000 эсминец | 2500 Сколько страниц (в тысячах) будет найдено по запросу фрегат & эсминец Решение: Обозначим: \(A\) - количество страниц по запросу "фрегат" \(B\) - количество страниц по запросу "эсминец" \(A \lor B\) - количество страниц по запросу "фрегат | эсминец" \(A \land B\) - количество страниц по запросу "фрегат & эсминец" Из таблицы имеем: \(A \lor B = 3000\) \(A = 2000\) \(B = 2500\) Используем формулу для объединения множеств: \(A \lor B = A + B - (A \land B)\) Подставим известные значения: \(3000 = 2000 + 2500 - (A \land B)\) \(3000 = 4500 - (A \land B)\) \(A \land B = 4500 - 3000\) \(A \land B = 1500\) Ответ: По запросу "фрегат & эсминец" будет найдено 1500 тысяч страниц. 2. В таблице приведены запросы к поисковому серверу. Расположите номера запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу. Для обозначения логической операции "ИЛИ" в запросе используется символ |, а для логической операции "И" – &. 1) кролики | лисицы 2) (зайцы & кролики) | (лисицы & волки) 3) зайцы & кролики & лисицы & волки 4) зайцы & кролики Решение: Обозначим множества: К - кролики Л - лисицы З - зайцы В - волки В общем случае, для любых множеств \(X\) и \(Y\): \(X \land Y \subseteq X \subseteq X \lor Y\) Это означает, что количество элементов в пересечении не больше, чем в одном из множеств, а количество элементов в одном из множеств не больше, чем в объединении. Также, если \(A \subseteq B\), то количество элементов в \(A\) меньше или равно количеству элементов в \(B\). Рассмотрим запросы: 4) \(З \land К\) 1) \(К \lor Л\) 2) \((З \land К) \lor (Л \land В)\) 3) \(З \land К \land Л \land В\) Сравним запросы: Запрос 3) \(З \land К \land Л \land В\) является пересечением всех четырех множеств. Это будет наименьшее количество страниц. Запрос 4) \(З \land К\) является пересечением двух множеств. Запрос 2) \((З \land К) \lor (Л \land В)\) является объединением двух пересечений. Запрос 1) \(К \lor Л\) является объединением двух множеств. Это будет наибольшее количество страниц. Сравним 3) и 4): \(З \land К \land Л \land В \subseteq З \land К\). Значит, количество страниц для 3) меньше или равно, чем для 4). Сравним 4) и 2): \(З \land К \subseteq (З \land К) \lor (Л \land В)\). Значит, количество страниц для 4) меньше или равно, чем для 2). Сравним 2) и 1): \((З \land К) \lor (Л \land В)\) и \(К \lor Л\). В общем случае, \(X \land Y \subseteq X\) и \(X \land Y \subseteq Y\). Также \(X \subseteq X \lor Y\). Мы знаем, что \(З \land К \subseteq К\) и \(Л \land В \subseteq Л\). Тогда \((З \land К) \lor (Л \land В)\) будет подмножеством или равно \(К \lor Л\). Например, если \(З \land К\) и \(Л \land В\) не пересекаются, то \((З \land К) \lor (Л \land В)\) будет меньше, чем \(К \lor Л\). В общем случае, объединение двух пересечений будет меньше или равно объединению двух исходных множеств. То есть, количество страниц для 2) меньше или равно, чем для 1). Таким образом, порядок возрастания количества страниц: 3) \(З \land К \land Л \land В\) (наименьшее) 4) \(З \land К\) 2) \((З \land К) \lor (Л \land В)\) 1) \(К \lor Л\) (наибольшее) Ответ: 3, 4, 2, 1. 3. Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F? Таблица истинности: X | Y | Z | F --|---|---|-- 1 | 1 | 1 | 1 1 | 1 | 0 | 1 1 | 0 | 1 | 1 1 | 0 | 0 | 1 Варианты выражений: 1) \(X \lor \neg Y \lor Z\) 2) \(X \land Y \land Z\) 3) \(X \land Y \land \neg Z\) 4) \(\neg X \lor Y \lor \neg Z\) Решение: Проверим каждое выражение по таблице истинности. Заметим, что во всех строках таблицы \(X = 1\), и \(F = 1\). Это означает, что выражение должно быть истинным, когда \(X = 1\). Проверим вариант 2) \(X \land Y \land Z\): Если \(X=1, Y=1, Z=0\), то \(1 \land 1 \land 0 = 0\). Но в таблице \(F=1\). Значит, вариант 2) не подходит. Проверим вариант 3) \(X \land Y \land \neg Z\): Если \(X=1, Y=1, Z=1\), то \(1 \land 1 \land \neg 1 = 1 \land 1 \land 0 = 0\). Но в таблице \(F=1\). Значит, вариант 3) не подходит. Проверим вариант 4) \(\neg X \lor Y \lor \neg Z\): Если \(X=1, Y=0, Z=1\), то \(\neg 1 \lor 0 \lor \neg 1 = 0 \lor 0 \lor 0 = 0\). Но в таблице \(F=1\). Значит, вариант 4) не подходит. Проверим вариант 1) \(X \lor \neg Y \lor Z\): 1) \(X=1, Y=1, Z=1\): \(1 \lor \neg 1 \lor 1 = 1 \lor 0 \lor 1 = 1\). (Совпадает) 2) \(X=1, Y=1, Z=0\): \(1 \lor \neg 1 \lor 0 = 1 \lor 0 \lor 0 = 1\). (Совпадает) 3) \(X=1, Y=0, Z=1\): \(1 \lor \neg 0 \lor 1 = 1 \lor 1 \lor 1 = 1\). (Совпадает) 4) \(X=1, Y=0, Z=0\): \(1 \lor \neg 0 \lor 0 = 1 \lor 1 \lor 0 = 1\). (Совпадает) Все значения совпадают. Ответ: 1) \(X \lor \neg Y \lor Z\). 4. Для какого из приведённых чисел ложно высказывание: НЕ (число < 10) ИЛИ НЕ (число чётное)? Варианты чисел: 1) 123 2) 56 3) 9 4) 8 Решение: Перепишем высказывание, используя обозначения: \(A\) = "число < 10" \(B\) = "число чётное" Высказывание: \(\neg A \lor \neg B\) Нам нужно найти число, для которого это высказывание ложно. Высказывание \(\neg A \lor \neg B\) ложно тогда и только тогда, когда \(\neg A\) ложно И \(\neg B\) ложно. То есть, когда \(A\) истинно И \(B\) истинно. Значит, нам нужно найти число, которое одновременно: 1) < 10 (число меньше 10) 2) чётное (число чётное) Проверим варианты: 1) Число 123: < 10? Нет (123 не < 10). Чётное? Нет (123 не чётное). Для 123: \(A\) ложно, \(B\) ложно. \(\neg A\) истинно, \(\neg B\) истинно. \(\neg A \lor \neg B\) истинно. 2) Число 56: < 10? Нет (56 не < 10). Чётное? Да (56 чётное). Для 56: \(A\) ложно, \(B\) истинно. \(\neg A\) истинно, \(\neg B\) ложно. \(\neg A \lor \neg B\) истинно. 3) Число 9: < 10? Да (9 < 10). Чётное? Нет (9 не чётное). Для 9: \(A\) истинно, \(B\) ложно. \(\neg A\) ложно, \(\neg B\) истинно. \(\neg A \lor \neg B\) истинно. 4) Число 8: < 10? Да (8 < 10). Чётное? Да (8 чётное). Для 8: \(A\) истинно, \(B\) истинно. Тогда \(\neg A\) ложно, \(\neg B\) ложно. Высказывание \(\neg A \lor \neg B\) будет ложно \((ложно \lor ложно = ложно)\). Ответ: 4) 8. 5. Решите логическую задачу: Ваня, Петя, Саша, Коля носят фамилии В,П,С,К. Известно, что: 1) Ваня и С. – отличники 2) Петя и В – троечники 3) В ростом выше П 4) Коля ростом ниже П 5) У Саши и Пети одинаковый рост На какую букву начинается фамилия каждого мальчика? Решение: Обозначим мальчиков: В - Ваня, П - Петя, С - Саша, К - Коля. Обозначим фамилии: Вф - фамилия на В, Пф - фамилия на П, Сф - фамилия на С, Кф - фамилия на К. Составим таблицу соответствия: Мальчик | Фамилия ---|--- Ваня | ? Петя | ? Саша | ? Коля | ? Используем данные: 1) Ваня и С. – отличники. Это означает, что Ваня - отличник, и мальчик с фамилией на С - отличник. Из этого следует, что Ваня не носит фамилию на С. Также, если Ваня - отличник, то Петя и В (троечники) не могут быть Ваней. Значит, Ваня не носит фамилию на В. 2) Петя и В – троечники. Это означает, что Петя - троечник, и мальчик с фамилией на В - троечник. Из этого следует, что Петя не носит фамилию на В. Также, если Петя - троечник, то Ваня и С (отличники) не могут быть Петей. Значит, Петя не носит фамилию на С. Суммируем, что мы знаем о Ване и Пете: Ваня: не Сф, не Вф. Петя: не Вф, не Сф. Рассмотрим фамилии: Вф, Пф, Сф, Кф. Если Ваня не Сф и не Вф, то его фамилия может быть Пф или Кф. Если Петя не Вф и не Сф, то его фамилия может быть Пф или Кф. Теперь используем информацию о росте: 3) В ростом выше П 4) Коля ростом ниже П 5) У Саши и Пети одинаковый рост Из 3) и 4) следует, что мальчик с фамилией на В выше Пети, а Коля ниже Пети. Значит, мальчик с фамилией на В не может быть Колей. Также, Коля не может быть мальчиком с фамилией на В. Из 5) следует, что Саша и Петя имеют одинаковый рост. Из 3) и 4) мы знаем, что Петя не имеет одинаковый рост с мальчиком с фамилией на В (В выше П) и не имеет одинаковый рост с Колей (Коля ниже П). Значит, Саша не может быть мальчиком с фамилией на В и не может быть Колей. Давайте сведем все вместе: 1. Ваня и С. – отличники. Ваня \(\ne\) Сф. Мальчик с фамилией Сф \(\ne\) Петя, \(\ne\) Коля. 2. Петя и В – троечники. Петя \(\ne\) Вф. Мальчик с фамилией Вф \(\ne\) Ваня, \(\ne\) Саша. 3. В ростом выше П. Мальчик с фамилией Вф \(\ne\) Коля. 4. Коля ростом ниже П. Коля \(\ne\) мальчик с фамилией Вф. 5. У Саши и Пети одинаковый рост. Саша \(\ne\) мальчик с фамилией Вф (т.к. В выше П, а Саша и Петя одинакового роста). Саша \(\ne\) Коля (т.к. Коля ниже П, а Саша и Петя одинакового роста). Соберем ограничения для каждого мальчика: Ваня: - Отличник (из 1) - Не Сф (из 1) - Не Вф (т.к. Вф - троечник, а Ваня - отличник) Значит, Ваня может быть Пф или Кф. Петя: - Троечник (из 2) - Не Вф (из 2) - Не Сф (т.к. Сф - отличник, а Петя - троечник) Значит, Петя может быть Пф или Кф. Саша: - Отличник (из 1, т.к. Ваня и С. отличники, а Ваня не С.) - Не Вф (т.к. Вф - троечник, а Саша - отличник) - Не Коля (из 5 и 4: Саша и Петя одинакового роста, Коля ниже Пети, значит Саша не Коля) - Не Сф (т.к. Саша - это мальчик, а Сф - это фамилия. Если Саша носит фамилию Сф, то это противоречит "Ваня и С. - отличники", где С. - это мальчик с фамилией на С. То есть, Саша не может быть "С." в этом контексте, если он сам носит фамилию на С. Это немного запутанно. Давайте переформулируем: "Ваня и мальчик с фамилией на С - отличники". Если Саша носит фамилию на С, то Саша - отличник. Это согласуется. Но если Саша - это "С.", то Ваня и Саша - отличники. Это тоже согласуется. Давайте предположим, что "С." означает "мальчик, чья фамилия начинается на С". Тогда: Ваня - отличник. Мальчик с фамилией на С - отличник. Петя - троечник. Мальчик с фамилией на В - трое