Математическая логика

      Решать логические задачи очень увлекательно. В них вроде бы нет никакой математики - нет ни чисел, ни функций, ни треугольников, ни векторов, а есть только лжецы и мудрецы, истина и ложь. В то же время дух математики в них чувствуется ярче всего - половина решения любой математической задачи (а иногда и гораздо больше половины) состоит в том, чтобы как следует разобраться в условии, распутать все связи между участвующими объектами. Есть люди, для которых решение логической задачи - увлекательная , но несложная задача. Их мозг как луч прожектора сразу освещает все хитроумные построения, и к правильному ответу он приходит необычайно быстро. Замечательно, что при этом он и не могут объяснить, как они пришли к решению. "Ну это же очевидно, ясно", - говорят они. "Ведь если ... " - и они начинают легко распутывать клубок противоречивых высказываний. "Действительно, все ясно", - говорит слушатель, огорченный тем, что он сам не увидел очевидного рассуждения. Согласитесь, что такое же ощущение часто возникает при чтении детективов. Итак, мы узнаем, как разными способами можно решать логические задачи. Оказывается таких приемов несколько, они разнообразны и каждый из них имеет свою область применения. На этой странице вы узнаете кое-что об этих приемах. Познакомившись подробно, поймете в каких случаях удобнее использовать тот или другой метод. Кроме этого, работая над заданиями по пректу вам придется познакомиться с основными понятиями направления "математики без формул" - математической логики, узнать о создателях этой науки и об истории ее становления.

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

      Разнообразие логических задач очень велико. Текстовые логические задачи можно условно разделить на следующие виды:

1) все высказывания истинны;

2) не все высказывания истинны;

3) задачи о правдолюбцах и лжецах.

     Желательно отрабатывать решение каждого вида задач постепенно, поэтапно.

Основные приемы и методы решения логических задач

Теория, мой друг, суха, но зеленеет жизни древо.

И.В.Гете

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

      Метод рассуждений;

      Метод таблиц;

      Метод графов;

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

      Метод бильярда;

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

      средствами алгебры логики.

Метод рассуждений.

     При помощи рассуждений обычно решают несложные

логические задачи.

     В методе рассуждений при решении помогают: схемы, чертежи,

краткие записи, умение выбирать информацию, умение пользоваться правилом перебора.

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

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

Решение. Имеется три утверждения. Если верно первое утверждение, то верно и второе, так как юноши изучают разные языки. Это противоречит условию задачи, поэтому первое утверждение ложно. Если верно второе утверждение, то первое и третье должны быть ложны. При этом получается, что никто не изучает китайский. Это противоречит условию, поэтому второе утверждение тоже ложно. Остается считать верным третье утверждение, а первое и второе — ложными. Следовательно, Вадим не изучает китайский, китайский изучает Сергей.

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

Метод таблиц.

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

     Таблицы хорошо применять, когда устанавливается соответствие между двумя    множествами (можно и между тремя множествами), когда количество элементов во множествах одинаково и неодинаково. Перед составлением таблиц следует отработать правила их заполнения.

Задача 2.

Барсук позвал к себе гостей:

Медведя, рысь и белку.

И подарили барсуку

Подсвечник и тарелку.

     Когда же он позвал к себе

Рысь, белку, мышку, волка,

То он в подарок получил

Подсвечник и иголку.

     Им были вновь приглашены

Волк, мышка и овечка.

И получил в подарок он

Иголку и колечко.

     Он снова пригласил овцу,

Медведя, волка, белку.

И подарили барсуку

Колечко и тарелку.

     Нам срочно нужен ваш совет.

(На миг дела отбросьте.)

Хотим понять, какой предмет

Каким дарился гостем.

     И кто из шестерых гостей

Явился без подарка?

Не можем мы сообразить,

Сидим... Мудрим... Запарка...

     Решение. Составим таблицу 6 x 4 и из первого четверостишия делаем выводы:

1)      медведь, рысь, белка не дарили иголку и колечко;

2)      мышка, волк, овца не дарили подсвечник и тарелку.

Получаем таблицу:

Ответ: виден из таблицы.

Задача 3.

     Три клоуна Бим, Бам и Бом вышли на арену в красной, зеленой и синей рубашках. Их туфли были тех же цветов. У Бима цвета рубашки и туфель совпадали. У Бома ни туфли, ни рубашка не были красными. Бам был в зеленых туфлях, а в рубашке другого цвета. Как были одеты клоуны?

Решение. Составим таблицу, в столбцах которой отметим возможные цвета рубашек и туфель клоунов (буквами К, З и С обозначены красный, зеленый и синий цвета). Будем заполнять таблицу, используя условия задачи. Туфли Бама зеленые, а рубашка не является зеленой. Ставим знак + в клетку 2-й строки и 5-го столбца, и знак - в клетку 2-й строки и 2-го столбца. Следовательно, у Бима и Бома туфли уже не могут быть зелеными, так же как не могут быть туфли Бама синими или красными. Отметим все это в таблице (см. табл. 1).

( табл.1)

     Далее, туфли и рубашка Бома не являются красными, отметим соответствующие ячейки таблицы знаком – . Из таблицы, заполненной на этом этапе, видим, что красные туфли могут быть только у Бима, а, следовательно, туфли Бома - синие. Правая часть таблицы заполнена, мы установили цвета обуви клоунов (табл.1). Цвет рубашки Бима совпадает с цветом его туфель и является красным. Теперь легко устанавливается владелец зеленой рубашки - Бом. Бам, в таком случае, одет в рубашку синего цвета.

     Мы полностью заполнили таблицу, в которой однозначно устанавли-ваются цвета туфель и рубашек клоунов (см. табл. 2): Бим одет в красную рубашку и красные туфли, Бам в синей рубашке и зеленых туфлях, Бом в зеленой рубашке и туфлях синего цвета.

( табл.2)

Ответ: Бим одет в красную рубашку и красные туфли, Бам в синей рубашке и зеленых туфлях, Бом в зеленой рубашке и туфлях синего цвета.

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

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

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

     При решении логических задач очень часто полезно вычертить “дерево логических условий”. Это “дерево” выражает в виде простого чертежа логическую взаимосвязь между данными высказываниями.

Научимся “выращивать” логические деревья на простых примерах. Выращивание любого дерева начинается с рассмотрения исходной формулы.

     Логической сумме на логическом дереве будет соответствовать “разветвление” ветвей.

     Логическому произведению на выращиваемом дереве будет соответствовать “следование” ветвей друг за  другом.

Задача 4. В соревнованиях по гимнастике на первенство школы участвуют Алла, Валя, Таня и Даша. Болельщики высказали предположения о возможных победителях:

1: “Первой будет Таня, Валя будет второй”.

2: “Второй будет Таня, Даша - третьей”.

3: “Алла будет второй, Даша - четвертой”.

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

Решение.

Введем буквенные обозначения всех высказываний, задающих условие задачи:

T1 - “Таня будет первой”;

W2 - “Валя будет второй”;

T2 - “Таня будет второй”;

D3 - “ Даша будет третьей”;

A2 - “ Алла будет второй”;

D4 - “Даша будет четвертой”

Построим  дерево для высказываний.

Каждому простому высказыванию в формуле на выращиваемом дереве будет соответствовать одна ветвь.

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

Ветвь 1:

т.к. T1Ч T2є 0, A2Ч T2є 0

Ветвь 2:

т.к. T1Ч T2є 0

Ветвь 3:

Ветвь 4:

,

т.к. D3Ч D4 є 0

Ветвь 5:

,

т.к. W2Ч T2є 0, T2Ч A2є 0

Ветвь 6:

,

т.к. W2ЧT 2є 0

Ветвь 7:

,

т.к. W2Ч A 2є 0

Ветвь 8:

,

т.к. D3Ч D4 є 0

Итак, только выражение ветви 3 эквивалентно 1:

Из этого выражения следует:

Таня - первая;

Алла - вторая;

Даша - третья;

Валя - четвертая.

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

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