ОСНОВНЫЕ МЕТОДЫ РЕШЕНИЯ ЛОГИЧЕСКИХ ЗАДАЧ ПРИ ПОДГОТОВКЕ К ЕГЭ ПО ИНФОРМАТИКЕ

Немкова А.Е.

Лесосибирский педагогический институт –

филиал Сибирского федерального университета, Россия

Логика – наука, изучающая методы установления истинности или ложности одних высказываний на основе истинности или ложности других высказываний [1].

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

Пример №1:

Перед началом Турнира «Четырех» болельщики высказали следующие предположения по поводу своих кумиров:

А) Макс победит, Билл – второй;

В) Билл – третий, Ник – первый;

С) Макс – последний, а первый – Джон.

Когда соревнования закончились, оказалось, что каждый из болельщиков был прав только в одном из своих прогнозов. Какое место на турнире заняли Джон, Ник, Билл, Макс [3]?

Решение (способ 1, метод рассуждений)

1) Есть «точная» информация, которая не подвергается сомнению - каждый из болельщиков оказался прав только в одном прогнозе.

2) Запишем высказывания болельщиков:

1. Макс победит, Билл – второй;

2. Билл – третий, Ник – первый;

3. Макс – последний, а первый – Джон.

3) Известно, что из двух высказываний каждого болельщика одно истинно, а другое – ложно.

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

5) Пусть первый болельщик угадал, что Билл занял второе место, тогда второй болельщик предсказал первое место Нику, следовательно, по предположению третьего, Макс занял последнее место, а Джон – третье.

Отсюда имеем: Ник – 1, Билл – 2, Джон – 3 и Макс – 4 место.

Решение (способ 2, табличный метод):

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

1) Запишем высказывания трех болельщиков в форме таблицы (заголовок строки обозначает место в турнирной таблице):

	Первый болельщик	Второй болельщик	Третий болельщик
1	Макс	Ник	Джон
2	Билл
3		Билл
4			Макс

2) Считая, что два человека не могут оказаться на одном месте, начнем рассматривать эту таблицу с той строчки, где больше всего информации (в данном случае – с первой).

3) Предположим, что Макс действительно занял первое место, как и сказал первый болельщик, тогда:

3.1. Второй и третий болельщики ошиблись, поставив на первое место Ника и Джона;

3.2. С учетом главного условия задачи, получается, что третий болельщик угадал во втором случае, и Макс будет на четвертом месте, но данное утверждение противоречит начальному предположению, следовательно, Макс должен быть не на первом месте, а на четвертом, как сказал третий болельщик:

	Первый болельщик	Второй болельщик	Третий болельщик
1	Макс	Ник	Джон
2	Билл
3		Билл
4			Макс

3.3. Имеем, что в первом прогнозе первый болельщик ошибся, то есть он угадал, что Билл занял второе место:

	Первый болельщик	Второй болельщик	Третий болельщик
1	Макс	Ник	Джон
2	Билл
3		Билл
4			Макс

3.4. Так как Билл – второй, он не может быть на третьем месте, поэтому из прогноза второго болельщика следует, что Ник – первый:

	Первый болельщик	Второй болельщик	Третий болельщик
1	Макс	Ник	Джон
2	Билл
3		Билл
4			Макс

3.5. Определимся с Джоном – ему досталось единственное свободное третье место:

	Первый болельщик	Второй болельщик	Третий болельщик
1	Макс	Ник	Джон
2	Билл		Джон
3		Билл
4			Макс

Получаем окончательный список победителей: Ник, Билл, Джон, Макс.

Пример №2:

Следующие два высказывания истинны:

1. Неверно, что если корабль A вышел в море, то корабль C — нет.

2. В море вышел корабль B или корабль C, но не оба вместе.

Определить, какие корабли вышли в море [2].

Решение (способ 1, применение законов логики):

Обозначим буквами высказывания:

A — «корабль A вышел в море»,

B — «корабль B вышел в море»,

C — «корабль C вышел в море».

Высказывание «если корабль A вышел в море, то корабль C — нет» можно записать в виде A → = 1. По условию (1), это высказывание неверно, таким образом, имеем A → = 0. Кроме того, из (2) получаем A B = 1. Таким образом, решение задачи сводится к решению системы логических уравнений:

Нужно найти тройку логических значений A, B и C, при которых оба уравнения превращаются в истинные равенства. Для этого преобразуем уравнения так, чтобы правые части были равны 1 (истинному значению). Применим инверсию (операцию «НЕ») к первому уравнению:

Теперь представляем импликацию и «исключающее ИЛИ» через базовые операции «И», «ИЛИ», «НЕ»:

Объединить оба уравнения с помощью операции «И» в одно, равносильное исходной системе:

Раскрываем инверсию в первой скобке по закону де Моргана и совершаем необходимые преобразования, после чего получим:

Последнее уравнение, равносильное исходной системе, имеет единственное решение: A = 1, B = 0 и C = 1. Таким образом, в море вышли корабли А и C.

Решение (способ 2, таблица истинности): Построим таблицу истинности для системы с тремя переменными:

A	B	C	A→
1	1	1	0	0
1	1	0	1	0
1	0	1	0	1
1	0	0	1	1
0	1	1	1	1
0	1	0	1	1
0	0	1	1	0
0	0	0	1	0

Полужирным выделена строка, для которой выполняются условия задачи. Таким образом, A = 1, B = 0 и C = 1 , это значит, что в море вышли корабли А и C.

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

Литература:

1. Киргизова Е.В., Немкова А.Е. Способы решения систем логических уравнений / Materiały VIII Międzynarodowej naukowi-praktycznej konferencji «Dynamika naukowych badań - 2012» Volume 10. Pedagogiczne nauki.: Przemyśl. Nauka i studia - 112 str.

2. Логические задачи / О.Б. Богомолова – 2-е изд. – М.: БИНОМ. Лаборатория знаний, 2006. – 271 с.: ил.

3. Поляков К.Ю. Системы логических уравнений / Учебно-методическая газета для учителей информатики: Информатика №14, 2011 г.

4. Чуркина Т.Е. ЕГЭ. Информатика. Практикум по выполнению типовых тестовых заданий ЕГЭ: учебно-методическое пособие – М.: Издательство Экзамен, 2011 г.