Уравнения по логике с ответами

Уравнения по логике с ответами

Сколько различных решений имеет уравнение J ∧ ¬K ∧ L ∧ ¬M ∧ (N ∨ ¬N) = 0, где J, K, L, M, N — логические переменные?

В ответе не нужно перечислять все различные наборы значений J, K, L, M и N, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

Выражение (N ∨ ¬N) истинно при любом N, поэтому

Применим отрицание к обеим частям логического уравнения и используем закон де Моргана ¬ (А ∧ В) = ¬ А ∨ ¬ В . Получим

Логическая сумма равна 1, если хотя бы одно из составляющих ее высказываний равно 1. Поэтому полученному уравнению удовлетворяют любые комбинации логических переменных кроме случая, когда все входящие в уравнение величины равны 0. Каждая из 4 переменных может быть равна либо 1, либо 0, поэтому всевозможных комбинаций 2·2·2·2 = 16. Следовательно, уравнение имеет 16 −1 = 15 решений.

Осталось заметить, что найденные 15 решений соответствуют любому из двух возможных значений логической переменной N, поэтому исходное уравнение имеет 30 решений.

Решение логических задач

Решение логических задач

Разнообразие логических задач очень велико. Способов их решения тоже немало. Но наибольшее распространение получили следующие три способа решения логических задач:

• средствами алгебры логики;
• табличный;
• с помощью рассуждений.

Познакомимся с ними поочередно.

Решение логических задач средствами алгебры логики

Обычно используется следующая схема решения:

1. изучается условие задачи;

2. вводится система обозначений для логических высказываний;

3. конструируется логическая формула, описывающая логические связи между всеми высказываниями условия задачи;

4. определяются значения истинности этой логической формулы;

5. из полученных значений истинности формулы определяются значения истинности введённых логических высказываний, на основании которых делается заключение о решении.

Пример 1. Трое друзей, болельщиков автогонок «Формула-1», спорили о результатах предстоящего этапа гонок.

— Вот увидишь, Шумахер не придет первым, — сказал Джон. Первым будет Хилл.

— Да нет же, победителем будет, как всегда, Шумахер, — воскликнул Ник. — А об Алези и говорить нечего, ему не быть первым.

Питер, к которому обратился Ник, возмутился:

— Хиллу не видать первого места, а вот Алези пилотирует самую мощную машину.

По завершении этапа гонок оказалось, что каждое из двух предположений двоих друзей подтвердилось, а оба предположения третьего из друзей оказались неверны. Кто выиграл этап гонки?

Решение. Введем обозначения для логических высказываний:

Ш — победит Шумахер; Х — победит Хилл; А — победит Алези.

Реплика Ника «Алези пилотирует самую мощную машину» не содержит никакого утверждения о месте, которое займёт этот гонщик, поэтому в дальнейших рассуждениях не учитывается.

Зафиксируем высказывания каждого из друзей:

Джон: ¬Ш/\Х

Ник: Ш/\¬А

Питер: ¬Х

Высказывание Ш /\ ¬ А/\ ¬Х истинно только при Ш=1, А=0, Х=0.

Ответ. Победителем этапа гонок стал Шумахер.

Решение логических задач табличным способом

При использовании этого способа условия, которые содержит задача, и результаты рассуждений фиксируются с помощью специально составленных таблиц.

Пример 2. В симфонический оркестр приняли на работу трёх музыкантов: Брауна, Смита и Вессона, умеющих играть на скрипке, флейте, альте, кларнете, гобое и трубе.

1. Смит самый высокий;
2. играющий на скрипке меньше ростом играющего на флейте;
3. играющие на скрипке и флейте и Браун любят пиццу;
4. когда между альтистом и трубачом возникает ссора, Смит мирит их;
5. Браун не умеет играть ни на трубе, ни на гобое.

На каких инструментах играет каждый из музыкантов, если каждый владеет двумя инструментами?

Решение. Составим таблицу и отразим в ней условия задачи, заполнив соответствующие клетки цифрами 0 и 1 в зависимости от того, ложно или истинно соответствующее высказывание.

Так как музыкантов трoе, инструментов шесть и каждый владеет только двумя инструментами, получается, что каждый музыкант играет на инструментах, которыми остальные не владеют.

Из условия 4 следует, что Смит не играет ни на альте, ни на трубе, а из условий 3 и 5, что Браун не умеет играть на скрипке, флейте, трубе и гобое. Следовательно, инструменты Брауна — альт и кларнет. Занесем это в таблицу, а оставшиеся клетки столбцов «альт» и «кларнет» заполним нулями:

Из таблицы видно, что на трубе может играть только Вессон.

Из условий 1 и 2 следует, что Смит не скрипач. Так как на скрипке не играет ни Браун, ни Смит, то скрипачом является Вессон. Оба инструмента, на которых играет Вессон, теперь определены, поэтому остальные клетки строки «Вессон» можно заполнить нулями:

Из таблицы видно, что играть на флейте и на гобое может только Смит.

Ответ: Браун играет на альте и кларнете, Смит — на флейте и гобое, Вессон — на скрипке и трубе.

Решение логических задач с помощью рассуждений

Этим способом обычно решают несложные логические задачи.

Пример 3. Вадим, Сергей и Михаил изучают различные иностранные языки: китайский, японский и арабский. На вопрос, какой язык изучает каждый из них, один ответил: «Вадим изучает китайский, Сергей не изучает китайский, а Михаил не изучает арабский». Впоследствии выяснилось, что в этом ответе только одно утверждение верно, а два других ложны. Какой язык изучает каждый из молодых людей?

Решение. Имеется три утверждения:

1. Вадим изучает китайский;
2. Сергей не изучает китайский;
3. Михаил не изучает арабский.

Если верно первое утверждение, то верно и второе, так как юноши изучают разные языки. Это противоречит условию задачи, поэтому первое утверждение ложно.

Если верно второе утверждение, то первое и третье должны быть ложны. При этом получается, что никто не изучает китайский. Это противоречит условию, поэтому второе утверждение тоже ложно.

Остается считать верным третье утверждение, а первое и второе — ложными. Следовательно, Вадим не изучает китайский, китайский изучает Сергей.

Ответ: Сергей изучает китайский язык, Михаил — японский, Вадим — арабский.

Пример 4. Министры иностранных дел России, США и Китая обсудили за закрытыми дверями проекты соглашения о полном разоружении, представленные каждой из стран. Отвечая затем на вопрос журналистов: «Чей именно проект был принят?», министры дали такие ответы:

Россия — «Проект не наш, проект не США»;
США — «Проект не России, проект Китая»;
Китай — «Проект не наш, проект России».

Один из них (самый откровенный) оба раза говорил правду; второй (самый скрытный) оба раза говорил неправду, третий (осторожный) один раз сказал правду, а другой раз — неправду.

Определите, представителями каких стран являются откровенный, скрытный и осторожный министры.

Решение. Для удобства записи пронумеруем высказывания дипломатов:

Россия — «Проект не наш» (1), «Проект не США» (2);
США — «Проект не России» (3), «Проект Китая» (4);
Китай — «Проект не наш» (5), «Проект России» (6).

Узнаем, кто из министров самый откровенный.

Если это российский министр, то из справедливости (1) и (2) следует, что победил китайский проект. Но тогда оба утверждения министра США тоже справедливы, чего не может быть по условию.

Если самый откровенный — министр США, то тогда вновь получаем, что победил китайский проект, значит оба утверждения российского министра тоже верны, чего не может быть по условию.

Получается, что наиболее откровенным был китайский министр. Действительно, из того, что (5) и (6) справедливы, cледует, что победил российский проект. А тогда получается, что из двух утверждений российского министра первое ложно, а второе верно. Оба же утверждения министра США неверны.

Ответ: Откровеннее был китайский министр, осторожнее — российский, скрытнее — министр США.

Решение логических задач в 10-м профильном классе

Урок №1

Цель урока: познакомить с основными способами решения логических задач.

Задачи урока:

• повторить материал по темам «Логические функции» и «Логические законы и правила преобразования логических выражений»;
• познакомить с основными способами решения логических задач;
• научить решать логические задачи, используя законы логики;
• продолжить работу по развитию логического мышления, памяти, внимательности, аккуратности при работе в тетради;
• побудить познавательный интерес к решению логических задач.

Дополнительные материалы: задачник (приложение 1), презентации (приложение 2, приложение 3).

Ход урока

I. Организационный момент (1мин).

II. Проверка домашнего задания. Повторение (5мин).

Примечание: для повторения используется презентация (приложение 2).

III. Изучение нового материала (20мин).

Примечание: объяснение материала проходит с помощью презентации (приложение 3).

Давным-давно в одной из восточных стран был знаменитый оракул. В отличие от остальных оракулов, его устами вещало не одно божество, а целых три: бог Правды, бог Лжи и бог Дипломатии. Эти божества изображались совершенно одинаковыми фигурами, расположенными в ряд за алтарем, перед которым преклоняли колени люди, ищущие совета. Боги всегда охотно отвечали на вопросы. Но так как они были похожи друг на друга, никто не мог определить, то ли отвечает бог Правды, которому надо верить, то ли бог Лжи, который говорит всегда неправду, то ли бог Дипломатии, который может либо солгать, либо сказать правду. Такое положение было на руку жрецам, ибо любой ответ оракула можно было толковать как угодно.

Но однажды нашелся кощунственный смельчак, который задумал совершить то, что не удавалось самым большим мудрецам. Он решил опознать каждого из богов.

Смельчак вошел в храм и спросил бога, стоящего слева:

– Кто стоит рядом с тобой?

– Бог Правды, – ответил тот.

Тогда смельчак спросил бога, стоящего в центре:

– Бог Дипломатии, – был ответ.

Последний вопрос смельчак задал богу, стоявшему справа:

– Кто стоит рядом с тобой?

– Бог Лжи, – ответил бог.

– Теперь все понятно, – довольно сказал смельчак.

Что же он понял из ответов богов? (Вопрос к классу).

Эта задача принадлежит к классу логических задач, разнообразие которых очень велико. Способов их решения тоже немало. Сегодня на уроке мы с вами научимся решать логические задачи – станем смельчаками или Шерлоками Холмсами, которые могут распознавать лжецов, преступников и распутывать сложные ситуации.

Наибольшее распространение получили следующие четыре способа решения логических задач:

• с помощью рассуждений;
• средствами алгебры логики;
• табличный способ;
• с помощью графов.

На этом уроке мы рассмотрим первые два способа решения логических задач: с помощью рассуждений и средствами алгебры логики.

Решение логических задач с помощью рассуждений

Этим способом обычно решают несложные логические задачи.

Задача №1. Три девочки – Роза, Маргарита и Анюта представили на конкурсе корзины из выращенных ими роз, маргариток и анютиных глазок. Девочка, вырастившая маргаритки, обратила внимание Розы на то, что ни у одной из девочек имя не совпадает с названием любимых цветов. Какие цветы вырастила каждая из девочек?

Решение.

1. Девочка, вырастившая маргаритки, обратила внимание на то, что ни у одной из девочек имя не совпадает с названием выращенных цветов, поэтому можно записать следующие условия:
   а) Аня вырастила не анютины глазки.
   б) Маргарита вырастила не маргаритки.
   в) Роза вырастила не розы.
2. Из диалога Розы и девочки, вырастившей маргаритки, следует, что Роза вырастила не маргаритки. Поэтому она могла вырастить либо розы, либо анютины глазки. Учитывая условие в), получаем, что Роза вырастила анютины глазки.
3. В связи с условием б) и предыдущим выводом очевидно, что Маргарита вырастила розы.
4. Следовательно, Аня вырастила маргаритки.

Ответ. Роза вырастила анютины глазки, Маргарита – розы, Аня – маргаритки.

Задача №2. Вадим, Сергей и Михаил изучают различные иностранные языки: китайский, японский и арабский. На вопрос, какой язык изучает каждый из них, один ответил: «Вадим изучает китайский, Сергей не изучает китайский, Михаил не изучает арабский». Впоследствии выяснилось, что в этом ответе только одно утверждение верно, а два других ложны. Какой язык изучает каждый из молодых людей?

Решение.

1. Имеются три утверждения:
   а) Вадим изучает китайский;
   б) Сергей не изучает китайский;
   в) Михаил не изучает арабский.
2. Если верно первое утверждение, то верно и второе, так как юноши изучают разные языки. Это противоречит условию задачи, поэтому первое утверждение ложно.
3. Если верно второе утверждение, то первое и третье должны быть ложны. При этом получается, что никто не изучает китайский. Это противоречит условию, поэтому второе утверждение тоже ложно.
4. Остается считать верным третье утверждение, а первое и второе – ложными. Следовательно, Вадим не изучает китайский, изучает китайский Сергей.
5. Так как Михаил не изучает арабский, то он может изучать лишь японский. Тогда Вадим изучает арабский.

Ответ. Китайский изучает Сергей, Вадим – арабский, Михаил – японский.

Решение логических задач средствами алгебры логики

Обычно используется следующая схема решения:

1. изучается условие задачи;
2. вводится система обозначений для логических высказываний;
3. конструируется логическая формула, описывающая логические связи между всеми высказываниями условия задачи;
4. определяются значения истинности этой логической формулы;
5. из полученных значений истинности формулы определяются значения истинности введенных логических высказываний, на основании которых делается заключение о решении.

Задача №3. Виновник ночного дорожно-транспортного происшествия скрылся с места аварии. Первый из опрошенных свидетелей сказал работникам ГИБДД, что это были «Жигули», первая цифра номера машины – единица. Второй свидетель сказал, что машина была марки «Москвич», а номер начинался с семерки. Третий свидетель заявил, что машина была иностранная, номер начинался не с единицы. При дальнейшем расследовании выяснилось, что каждый из свидетелей правильно указал либо только марку машины, либо только первую цифру номера. Какой марки была машина и с какой цифры начинался номер?

Решение.

Введем обозначения для логических высказываний: Ж – это «Жигули»; М – это «Москвич»; И – это иностранная машина; Е – номер машины начинается с единицы; С – номер машины начинается с семерки.

Запишем высказывания свидетелей в наших обозначениях:

Из того факта, что каждый из свидетелей правильно указал либо только марку машины, либо только первую цифру номера, получаем три истинных составных высказывания:

Если все эти истинные высказывания логически перемножить, то получим следующее истинное логическое высказывание:

Для решения задачи нужно определить, при каких значениях логических переменных Ж, М, И, Е, С это высказывание истинно.

Упростим выражение, учитывая те обстоятельства, что машина не может быть одновременно и марки «Жигули», и марки «Москвич», и иностранного происхождения, а также то, что номер машины не может одновременно начинаться с единицы и с семерки:

При выводе мы также использовали закон противоречия и закон исключения констант.Высказывание истинно только при Ж=1, М=0, И=0, Е=0, С=1. Таким образом, мы установили, что виновником дорожно-транспортного происшествия была машина марки «Жигули», номер которой начинался с цифры семь.

Ответ. Машина марки «Жигули», номер которой начинался с цифры семь.

Задача №4. В клуб служебного собаководства на очередную тренировку пришли со своими собаками Антон, Борис, Петр, Виктор и Олег. Желая подшутить над новым инструктором, на вопрос: «Кто же хозяин каждой из собак?» каждый юноша дал один правильный и один неправильный ответ. Антон сказал: «Моя собака – Рекс, а собака Петра – Лайма». Борис сказал: «Рекс – моя собака, а собака Виктора – Джек». Петр сказал: «Собака Виктора – Зевс, а моя собака – Рекс». Виктор сказал: «Моя собака – Джек, а собака Олега – Бичо». Олег сказал: «Да, моя собака – Бичо, а собака Бориса – Зевс». Кто же на самом деле хозяин каждой собаки?

Решение.

Обозначим высказывательную форму «Юноша X – хозяин собаки Y» как и запишем получившиеся логические выражения. Из высказываний молодых людей и того факта, что одно из высказываний истинно, а другое ложно, следуют истинные составные высказывания:

Если все эти истинные высказывания логически перемножить, то получим следующее истинное высказывание:

Выполните преобразование этого высказывания с учетом того, что у каждого хозяина только одна собака и у каждой собаки только один хозяин.

В результате преобразований получим следующее равносильное высказывание:

которое истинно только при .

Ответ. Петр – хозяин Лаймы, Борис – Рекса, Виктор – Зевса, Олег – Бичо, Антон – Джека.

IV. Закрепление материала (10мин).

Примечание: у доски решает один учащийся, остальные оформляют решение задач в тетради. Вторую задачу может решить другой учащийся.

1) Вернемся к задаче об оракуле и попробуем решить ее одним из способов.

Примечание: способ решения определяет сам учащийся.

Ответ. Слева – бог Дипломатии, в центре – бог Лжи, справа – бог Правды.

2) Решите логическую задачу №16 из задачника (приложение 1).

Ответ. Победителем этапа гонки стал Шумахер.