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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример N2

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

А сказал: Я - Мердок.
В сказал: А говорит правду.
С сказал: Я не Мердок.

Кто же из них шпион - А, В или С ?

Решение:

Введем следующие переменные:

Пусть А_ш =А-шпион, тогда ¯A_ш =А - не шпион.
Пусть В_ш =В-шпион, тогда ¯B_ш = В- не шпион.
Пусть C_ш =С-шпион, тогда ¯C_ш = C- не шпион.

В наших обозначениях высказывания А, В, С записываются так:

А= А_ш ;В= А_ш ;С=¯C_ш .

По условиям задачи ясно, что из трёх высказываний истинным может быть либо одно (если шпион лжет), либо два ( если шпион говорит правду). Следовательно, возможны следующие варианты распределения истинных (И) и ложных (Л) высказываний:

ИИЛ V ИЛИ V ЛИИ V ЛЛИ V ЛИЛ V ИЛЛ=1.(*)

Посмотрим, что означает ИИЛ для введенных нами обозначений.

Высказывание пленника А истинно, следовательно, А_ш =1; высказывание пленника В истинно, следовательно, А_ш =1; высказывание пленника С ложно, следовательно, С_ш=1. То есть А_ш &А_ш &С_ш =1. Но А и С не могут одновременно быть шпионами, следовательно, это неверно и данная конъюнкция ложна.

Аналогично вариант ИЛИ "переводится" в наши обозначения так:

А_ш &¯А_ш &¯С_ш =1. Эта конъюнкция тоже ложна, поскольку А не может одновременно быть шпионом и не быть им.

Интерпретируем полностью формулу (*), опуская для кратности знак конъюнкции:

А_ш А_ш С_ш U А_ш ¯А_ш ¯C_ш U ¯А_ш А_ш ¯C_ш U ¯А_ш ¯А_ш ¯C_ш U ¯А_ш А_ш C_ш U А_ш ¯А_ш C_ш = 0 U 0 U 0 U ¯А_ш ¯C_ш U 0 U 0= ¯А_ш ¯C_ш =1.

То есть ни А ни С не шпионы, следовательно, шпион v В. далее уже просто сделать вывод, что А - лжец, С - рыцарь.

Таблицы

Пример №1 Три одноклассника — Влад, Тимур и Юра, встретились спустя 10 лет после окончания школы. Выяснилось, что один из них стал врачом, другой физиком, а третий юристом. Один полюбил туризм, другой бег, страсть третьего — регби.

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

Забавно, но у двоих из друзей в названиях их профессий и увлечений не встречается ни одна буква их имен.

Определите, кто чем любит заниматься в свободное время и у кого какая профессия.

Решение.

Здесь исходные данные разбиваются на тройки (имя — профессия — увлечение).

Из слов Юры ясно, что он не увлекается туризмом и он не врач. Из слов врача следует, что он турист.

Имя	Юра
Профессия		врач
Увлечение		туризм

Буква "а", присутствующая в слове "врач", указывает на то, что Влад тоже не врач, следовательно врач — Тимур. В его имени есть буквы "т" и "р", встречающиеся в слове "туризм", следовательно второй из друзей, в названиях профессии и увлечения которого не встречается ни одна буква его имени — Юра. Юра не юрист и не регбист, так как в его имени содержатся буквы "ю" и "р". Следовательно, окончательно имеем:

Имя	Юра	Тимур	Влад
Профессия	физик	врач	юрист
Увлечение	бег	туризм	регби

Ответ. Влад — юрист и регбист, Тимур — врач и турист, Юра — физик и бегун.

Пример №2

Три подруги вышли в белом, зеленом и синем платьях. Их туфли тоже были белого, зеленого и синего цветов. Известно, что только у Ани цвет платья и туфель совпадали. Ни платье, ни туфли Вали не были белыми, Наташа была в зеленых туфлях.

Определить цвет платья и туфель каждой из подруг.

Решение: можно решать, составляя две таблицы, а можно таблицы объединить в одно целое.

	Аня	Валя	Наташа			Аня	Валя	Наташа
Белые туфли	+	-	-		Белое платье	+	-	-
Зеленые туфли	-	-	+		Зеленое платье	-	+	-
Синие туфли	-	+	-		Синее платье	-	-	+

 

	белое платье	зеленое платье	синее платье	белые туфли	зеленые туфли	синее платье
Аня
Валя
Наташа
белые туфли
зеленые туфли
синие туфли

Рассуждения

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

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

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

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

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

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

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

Круги Эйлера

Этот метод даёт ещё более наглядное представление о возможном способе изображения условий, зависимости, отношений в логических задачах.

Один из величайших математиков петербургский академик Леонард Эйлер за свою долгую жизнь (он родился в 1707 г., а умер в 1783 г.) написал более 850 научных работ. В одной из них и появились эти круги. Эйлер писал тогда, что «они очень подходят для того, чтобы облегчить наши размышления». Наряду с кругами в подобных задачах применяют прямоугольники и другие фигуры.

Пример№1

1. Часть жителей города умеет говорить только по-русски, часть – только по-узбекски и часть умеет говорить на обоих языках. По-узбекски говорят 85%, по-русски 75%. Сколько процентов жителей говорят на обоих языках?

Решение. Составим схему –

У ? Р

85% 75%

В кружке под буквой «У» обозначим жителей, говорящих по-узбекски, под буквой «Р» - по-русски. В общей части кружков обозначим жителей, говорящих на обоих языках. Теперь от всех жителей (100%) отнимем кружок «У» (85%), получим жителей, говорящих только по-русски (15%). А теперь от всех, говорящих по-русски (75%), отнимем эти 15%. Получим говорящих на обоих языках (60%).

Пример N2

Из сотрудников фирмы 16 побывали во Франции,10-в Италии,6-в Англии; в Англии и Италии-5; в Англии и Франции -6; во всех трех странах - 5 сотрудников. Сколько человек посетили и Италию, и Францию, если всего в фирме работают 19 человек, и каждый из них побывал хотя бы в одной из названных стран?

Решение:

Нам известно, что во всех трех странах было 5 сотрудников. В Англии и Италии тоже 5, значит эти же сотрудники были и во Франции и поэтому в пересечении кругов А и И ставим 0. В Франции и Италии нам неизвестно поэтому пишем х-5 в пересечении кругов А и Ф. Т.к. в Англии было 6 человек, то 6-5-1=0 пишем 0,во Франции 16-х+5-6 и Италии 10-х+5-5 и всего в фирме 19 сотрудников, то остается составить и решить уравнение:

1+16-х+5-6+5+х-5+10-х+5-5=19, отсюда х=7, значит в Италии и Франции побывало 7-5=2 сотрудника фирмы.

Пртимер №3

В классе всего 36 человек. Учащиеся посещают математический, физический и химический кружки, причем, математический кружок посещают 18 человек, физический - 14 человек, химический - 10 человек. Кроме того, известно, что все три кружка посещают 2 человека, математический и физический - 8, математический и химический - 5, физический и химический - 3.

Сколько учеников класса не посещают никаких кружков?

Решение

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

Общей части всех трех кругов соответствует множество ребят, посещающих все три кружка, поэтому она обозначена МФХ.

Через МФХ_ обозначено множество ребят, посещающих математический и физический кружки, но не посещающих химический кружок. Аналогичным образом обозначены и все остальные области. Здесь для удобства обозначений мы будем отрицание отмечать чертой над символом.

Теперь обратимся к числовым данным.

В область МФХ впишем число 2, т.к. все три кружка посещают 2 ученика. Далее известно, что ребят, посещающих математический и физический кружки, было 8. Значит, в область МФ надо вписать число 8. Но область МФ состоит из двух частей: МФХ и МФХ, причем в МФХ входят 2 человека. Значит, на долю МФХ остается 6 человек. Здесь мы используем очевидные соображения о том, что количество элементов в двух непересекающихся множеств равно сумме количеств элементов в каждом из них. Это утверждение будет неверным для пересекающихся множеств, отсюда и возникает некоторая непривычная с точки зрения школьной арифметики сложность данной задачи.

Теперь рассмотрим множество МХ, на которое приходится 5 человек. Эта область также состоит из двух частей. На МФХ приходится 2 человека, значит, на МФХ приходится 3.

Рассмотрим теперь множество М, в которое входят 18 учеников. Оно состоит из 4 частей. Количественный состав трех подмножеств мы уже нашли: это 2, 6 и 3. Значит, в четвертое подмножество МФХ входит 18 - (2+3+6) = 7 человек.

Таким образом, в классе 8 ребят, не посещающих никаких кружков.

C помощью графов

1. 
   Граф - один из видов моделей, отражающих взаимодействие объектов или систем.
   

Графом называют схему, в которой обозначаются только наличие объектов (элементов системы) и наличие и вид связи между объектами.

Объекты представляются в графе вершинами (на схеме они обозначаются кружочками, прямоугольниками и т.п.). Связи между объектами представляются, если связь однонаправленная (обозначается на схеме линиями со стрелками) или ребрами, если связь между объектами двусторонняя ( обозначается на схеме линиями без стрелок).

Например, если нужно представить в графе, что из состояния А в состояние В возможен переход под воздействием V, то это можно изобразить так:

Если нужно представить, что к-тый участник соревнования занял n-е место ( или, что то же самое, n-е место занял к-тым участником), это можно изобразить так:

Пример №1

1. В первенстве класса по теннису 6 участников: Андрей, Борис, Виктор, Галина, Дмитрий и Елена. Первенство проводилось по круговой системе: каждый из участников играет с каждым из остальных один раз. Некоторые игры уже проведены: Андрей сыграл с Борисом, Галиной и Еленой, Борис с Галиной, Виктор с Галиной, Дмитрием и Еленой. Сколько пар проведено и сколько ещё осталось?

Решение. Изобразим данные задачи в виде схемы. Участников будем изображать точками, Андрея – А, Бориса – Б и т.д.. Если двое участников уже сыграли между собой, то будем соединять их точки отрезками.

Б В

А Г

Е Д

Число игр, уже проведённых, равно числу рёбер, т.е.7.

Чтобы найти число игр, которые осталось провести, построим ещё один граф с теми же вершинами, но рёбрами будем соединять тех участников, которые ещё не играли друг с другом. (Если точки из одного множества соответствуют точкам из другого, будем соединять их сплошной линией, а если не соответствуют – пунктирной).

Б В

А

Г

Е Д

Рёбер у этого графа оказалось 8, значит, осталось провести 8 игр.

Пример №2.
Марина, Лариса, Жанна и Катя умеют играть на разных инструментах( пианино, виолончели, гитаре, скрипке), но каждая только на одном. Они же знают иностранные языки (английский, французский, немецкий и испанский), но каждая только один. Известно:

1. 
   Девушка, которая играет на гитаре говорит по v испански.
   
2. 
   Лариса не играет ни на скрипке ни на виолончели и не знает английского языка.
   
3. 
   Марина не играет ни на скрипке, ни на виолончели и не знает ни немецкого, ни английского.
   
4. 
   Девушка, которая говорит по - немецки, не играет на виолончели.
   
5. 
   Жанна знает французский язык, но не играет на скрипке.
   

Кто на каком инструменте играет и какой иностранный язык знает?

Решение:

Из пятого условия, что Жанна знает французский язык, рисуем стрелку. Из третьего условия, что Марина не знает ни немецкого, ни английского, а французский знает Жанна, то Марина знает испанский и рассматривая первое условие она играет на гитаре. Из условия N2 видим, что Лариса играет на пианино, т.к. Марина играет на гитаре, а на других инструментах она играть не умеет, и значит, она говорит по-немецки.

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