Статья: Исследование и сравнение способов решения логических задач

Теперь, в столбце «блондин» уже два минуса и одна свободная клеточка. Значит, в ней мы можем поставить «+», что будет означать, что фамилия блондина - Чернов. Следовательно, в оставшейся свободной клеточке в строке «Чернов» можно поставить «-», так как у Чернова может быть только один цвет волос, то есть только один «+».

Теперь в таблице остается только одна свободная клеточка, соответствующая утверждению «Белокуров - рыжий». И поскольку Чернов и Рыжов не рыжие, а Белокуров не брюнет и не блондин, то это утверждение верно. Ставим знак «+»:

Ответ: Белокуров - рыжий, Чернов - блондин, а Рыжов - брюнет.

1.3 Метод графов

Граф - это схема, в которой обозначается только наличие объектов и наличие и вид связи между объектами. Объекты в графе представляются вершинами (кружочками, прямоугольниками и т.п.), а связи - как дуги, или рёбра. Сборник научных статей. Решение занимательных логических задач: http://e-lib.gasu.ru/konf/sssk/arhive/2006/01/R_5_12.html - данные соответствуют 27.12.12 Если связь однонаправленная, то связь представляется дугой и обозначается на схеме линией со стрелкой, а если двусторонняя, то ребром и обозначается линией без стрелок. Как и метод таблиц, метод графов в основном используется для решения задач типа «кто есть кто?». Рассмотрим этот метод на примере решения задачи.

Задача 5. Жила-была одна дружная семья: мама, папа и сын. Они все любили делать вместе, но вот мультфильмы любили разные: «Ну погоди!», «Покемоны», «Том и Джерри». Определите, какой мультфильм любит каждый из них, если мама, папа и любитель мультфильма «Покемоны» никогда не унывают, а папа и любитель мультфильма «Том и Джерри» делают зарядку по утрам?

Решение. Рассмотрим два множества: множество людей (мама, папа, сын) и множество мультфильмов («Ну погоди!», «Покемоны», «Том и Джерри»). Обозначим элементы множеств точками:

Будем соединять точки, соответствующие друг другу сплошной линией, а не соответствующие - прерывистой. По условию задачи у каждого человека только один любимый мультфильм. Из фрагмента условия «мама, папа и любитель мультфильма «Покемоны» никогда не унывают» следует, что мама и папа не являются любителями мультфильма «Покемоны». Из фрагмента «папа и любитель мультфильма «Том и Джерри» делают зарядку по утрам» следует, что папа - не любитель мультфильма «Том и Джерри»

Из условия задачи следует, что нужно найти единственно возможное соответствие между элементами двух множеств. Так как в каждом множестве по три элемента, то если точка соединена с двумя точками прерывистой линией, то с третьей точкой она обязательно должна быть соединена сплошной. От элементов «папа» и «Покемоны» графа отходят по две прерывистые линии, а значит, третьи линии должны быть сплошные.

Итак, получается, что папа любит мультфильм «Ну погоди!», а сын - «Покемоны». В обоих множествах остается по одному элементу, значит мама любит мультфильм «Том и Джерри».

1.4 Метод блок-схем

Метод блок-схем используется при решении задач «на переливание». Это задачи, в которых с помощью сосудов известных емкостей требуется отмерить некоторое количество жидкости, а также задачи, связанные с операцией взвешивания на чашечных весах и с перевозкой на другой берег реки нескольких объектов. Суть метода состоит в том, что выделяются операции, называемые командами, и устанавливается их последовательность. Эта последовательность оформляется в виде схемы. Эти схемы называются блок-схемами. Составленная блок - схема представляет собой программу, выполнение которой может привести нас к решению поставленной задачи. В блок - схемах могут присутствовать команды условного перехода, которые обозначаются в виде ромбиков с двумя выходами.

Задача 6. Имеются два сосуда: трехлитровый и пятилитровый. Нужно, пользуясь этими сосудами, получить 1, 2, 3, 4, 5, 6, 7 и 8 литров воды. Также в распоряжении имеется водопроводный кран и раковина, куда можно сливать воду.

Решение. Перечислим все возможные операции, которые могут быть использованы, и введем для них следующие сокращенные обозначения: НБ -- наполнить большой сосуд водой из-под крана; НМ -- наполнить маленький сосуд водой из-под крана; ОБ -- опорожнить большой сосуд, вылив воду в раковину; ОМ -- опорожнить маленький сосуд, вылив воду в раковину; Б>М -- перелить из большого сосуда в маленький, пока большой сосуд не опустеет или маленький сосуд не наполнится; М>Б -- перелить из маленького в большой, пока маленький сосуд не опустеет или большой сосуд не наполнится. Выделим среди перечисленных команд только три: НБ, Б>М, ОМ. Кроме этих трех команд рассмотрим еще две вспомогательные команды: Б = 0? -- посмотреть, пуст ли большой сосуд; М = З? -- посмотреть, наполнен ли маленький сосуд.

В зависимости от результатов этого осмотра мы переходим к выполнению следующей команды по одному из двух ключей - "да" или "нет" (командой условного перехода)

Договоримся теперь о последовательности выполнения выделенных команд. После Б>М будем выполнять ОМ всякий раз, как меньший сосуд оказывается наполненным, и НБ всякий раз, как больший сосуд будет опорожнен. Последовательность команд изобразим в виде блок-схемы.

Начнем выполнение программы. Будем фиксировать, как меняется количество воды в сосудах, если действовать по приведенной схеме. Результаты оформим в виде таблицы:

Дальше эта последовательность будет полностью повторяться. Из таблицы видим, что количество воды в обоих сосудах вместе образует следующую последовательность: 0, 5, 2, 7, 4, 1, 6, 3, 0 и т.д. Таким образом, действуя по приведенной схеме, можно отмерить любое количество литров от 1 до 7. Чтобы отмерить 8 литров, надо наполнить оба сосуда.

1.5 Метод кругов Эйлера

Суть данного метода - определение количества элементов, обладающих общими свойствами. Способ назван по фамилии его изобретателя Леонарда Эйлера. Задачи, которые решаются с помощью кругов Эйлера, чаще всего нельзя решить никак иначе. Рассмотрим этот метод на примере решения некоторых задач.

Задача 7. В магазин «Мир музыки» пришло 35 покупателей. Из них 20 человек купили диски «Metallica», 11 - диски «Skillet», 10 человек не купили ни одного диска. Сколько человек купили диски и «Metallica», и «Skillet»?

Решение. Изобразим эти множества на кругах Эйлера.

Теперь считаем: всего внутри большого круга 35 покупателей, значит внутри двух меньших 35-10=25 покупателей. По условию 20 покупателей купили диск «Metallica», следовательно, только диск «Skillet» купили 25-20=5 покупателей. Также есть условие, что диск «Skillet» купили 11 человек, а значит, 11-5=6 покупателей купили диски и «Metallica», и «Skillet».

Ответ: 6 покупателей купили диски и «Metallica», и «Skillet».

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

Решение. Изобразим все множества в виде кругов. На пересечении всех трех множеств, находящихся внутри большого множества 2 человека. Так как 8 человек посещают математический и физический кружки, значит, тех, кто посещает их без химического 8-2=6. Так же посчитаем количество человек, которые посещают только математический и химический, и только физический и химический. Получается 5-2=3 и 3-2=1.

Далее, найдем число учащихся, посещающих только один кружок. Так как всего кружок математики посещает 18 человек, а число учеников, посещающих также другие кружки равно 6+2+3=11, то число учеников, посещающих только кружок математики равно 18-11=7. Аналогичным образом вычислим число учеников, посещающих только кружок физики и только кружок химии. Получим 14-(6+2+1)=14-9=5 и 10-(2+1+3)=10-6=4. Впишем эти числа в соответствующие области.

Внутри большого круга мы получили 7 непересекающихся областей, численные значения которых нам известны, и оставшуюся область, численное значение которой нам надо найти. Так как всего в классе 36 человек, то надо из 36 вычесть суммы всех известных областей, обозначающих количество учеников, посещающих кружки. 36-(7+3+2+6+1+5+4)=36-28=8. Ответ: в классе 8 учеников, не посещающих кружки.

1.6 Метод математического бильярда

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

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

Рассмотрим задачу 6, которая служила примером использования метода блок-схем.

Задача 6. Имеются два сосуда: трехлитровый и пятилитровый. Нужно, пользуясь этими сосудами, получить 1, 2, 3, 4, 5, 6, 7 и 8 литров воды. Также в распоряжении имеется водопроводный кран и раковина, куда можно сливать воду.

Решение. В рассматриваемой задаче стороны параллелограмма должны иметь длины 3 и 5 единиц. По горизонтали будем откладывать количество воды в литрах в 5-литровом сосуде, а по вертикали - в 3-литровом сосуде. На всем параллелограмме нанесена сетка из одинаковых равносторонних треугольников.

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

Пусть шар находится в левом нижнем углу и после удара начнет перемещаться вверх вдоль левой боковой стороны параллелограмма до тех пор, пока не достигнет верхней стороны в точке А. Это означает, что мы полностью наполнили водой малый сосуд. Отразившись упруго, шар покатится вправо вниз и ударится о нижний борт в точке В, координаты которой 3 по горизонтали и 0 по вертикали. Это означает, что в большом сосуде 3 литра воды, а в малом сосуде воды нет, то есть мы перелили воду из малого сосуда в большой сосуд.

Пусть шар находится в левом нижнем углу и после удара начнет перемещаться вверх вдоль левой боковой стороны параллелограмма до тех пор, пока не достигнет верхней стороны в точке А. Это означает, что мы полностью наполнили водой малый сосуд. Отразившись упруго, шар покатится вправо вниз и ударится о нижний борт в точке В, координаты которой 3 по горизонтали и 0 по вертикали. Это означает, что в большом сосуде 3 литра воды, а в малом сосуде воды нет, то есть мы перелили воду из малого сосуда в большой сосуд.

Однако это решение не является самым коротким. Существует второй путь, когда воду сначала наливают в пятилитровый сосуд. Если на диаграмме шар из точки О покатится вправо по нижней стороне параллелограмма и затем, отразившись от правой боковой стороны, в точку 2 на верхней стороне параллелограмма и т.д., то получим более короткое решение задачи. Можно показать, что полученное решение с 6 переливаниями уже является самым коротким.

1.7 Сравнение методов решения логических задач

Как видно из предыдущих параграфов, задачи бывают нескольких типов. Например, задачи типа «кто есть кто?» или задачи «на переливание». Также есть отдельный тип задач «на множества», решаемых с помощью кругов Эйлера.