223.68K

Category:

informatics

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

1.

Вариативные способы
решения логических задач
Мочалова Марина Владимировна
учитель информатики
ГБОУ лицей 144 Калининского района Санкт-Петербурга

Содержание
1. Теория
2. Решение логических задач
2.1. методом рассуждений
2.2. табличным методом
2.3. с использованием графов
2.4. с использованием кругов Эйлера
2.5. с использованием алгебры логики
2.6. с помощью электронных таблиц
3. Источники

3.

Теория
Операции сравнения:
>
строго больше
<= меньше или равно
<
строго меньше
=
>= больше или равно
равно
<> не равно
Логические операции:
- НЕ – логическое отрицание (инверсия)
- И – логическое умножение (конъюнкция, одновременное выполнение условий)
- ИЛИ – логическое сложение (дизъюнкция, выполнение хотя бы одного условия из
нескольких)
- ЕСЛИ, ТО – логическое следование (импликация, соединение двух высказываний с
помощью оборота «если…, то…»)
- ТОГДА И ТОЛЬКО ТОГДА, КОГДА - логическое равенство (эквивалентность)
Содержание

4.

Теория
Порядок выполнения действий:
- выражения в скобках
- НЕ
- И
- ИЛИ
- импликация и эквивалентность
- <, <=, >, >=, =, <>
Пример:
5
1
4
3
2
7
6
10
9
8
НЕ ((Х = 7) И НЕ (Y <>9)) ИЛИ (Z > 0) (НЕ(Х = 6))
Содержание

5.

Теория
Основные логические операции
Логическое сложение
ИЛИ (дизъюнкция)
Логическое умножение
И (конъюнкция)
А
В
АИВ
0
0
0
0
1
0
1
0
0
1
1
1
А
0
0
1
1
Логическое следование
(импликация)
В
0
1
0
1
А ИЛИ В
0
1
1
1
Логическое
отрицание НЕ
(инверсия)
А
НЕ А
0
1
1
0
Логическое равенство
(эквивалентность)
А
В
А В
А
В
А В
0
0
1
0
0
1
0
1
1
0
1
0
1
0
0
1
0
0
1
1
1
1
1
1
Содержание

6.

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

7.

Решение логических задач
методом рассуждений
Виктор, Сергей и Максим изучают различные языки программирования: Паскаль, Питон и
С++. На вопрос, какой язык изучает каждый из них, один ответил: "Виктор изучает Паскаль,
Сергей не изучает Паскаль, а Максим не изучает С++". Впоследствии выяснилось, что в этом
ответе только одно утверждение верно, а два других ложны. Какой язык изучает каждый из
молодых людей?
Решение. Имеется три утверждения:
1.
Виктор изучает Паскаль;
2. Сергей не изучает Паскаль;
3.
Максим не изучает С++.
Если верно первое утверждение, то верно и второе, так как юноши изучают разные языки. Это
противоречит условию задачи, поэтому первое утверждение ложно.
Если верно второе утверждение, то первое и третье должны быть ложны. При этом получается,
что никто не изучает Паскаль. Это противоречит условию, поэтому второе утверждение тоже
ложно.
Остается считать верным третье утверждение, а первое и второе — ложными. Следовательно,
Виктор не изучает Паскаль, Паскаль изучает Сергей.
Ответ: Сергей изучает Паскаль, Максим — Питон, Виктор — С++.
Содержание

8.

Решение логических задач
табличным методом
Табличный метод является одним из основных при решении логических задач.
С помощью таблиц легко наглядно представить условие задачи и
последовательные шаги ее решения. Именно этот метод облегчает принятие
правильного решения.
Построение таблицы требует анализа находящейся в ней информации, а также
умения сравнивать, сопоставлять и делать выводы.
Первый шаг решения задачи данным методом - это составление таблицы и
заполнение ее исходными данными. Ячейки таблицы заполняются цифрами 0 и
1 в зависимости от того, ложно («0») или истинно («1») соответствующее
высказывание, заносимое в ячейку.
Затем в ячейки таблицы проставляются 0 или 1 в зависимости от анализа
условий и содержимого строк или столбцов таблицы. В каждом столбце и в
каждой строке должна быть только одна ИСТИНА.
Содержание

9.

Решение логических задач
табличным методом
Задача 1.
В шахматном турнире принимали участие шесть партнеров разных
профессий: токарь, слесарь, инженер, учитель, врач, шофер.
Известно, что:
1. В первом туре Андреев играл с врачом, учитель – с Борисовым, а
Григорьев – с Евдокимовы: в первом туре 3 партии;
2. Во втором туре Дмитриев играл с токарем, а врач – с Борисовым; во
втором туре 2 партии;
3. В третьем туре Евдокимов играл с инженером; в третьем туре 1 партия.
4. По окончании турнира места распределились так: Борисову
присудили 1-е место, Григорьев и инженер поделили 2 и 3 места,
Дмитриев занял
4 место, а Золотарев и слесарь поделили 5 и 6 места.
У кого какая профессия?
Содержание

10.

Решение логических задач
табличным методом
Анализируем условие задачи. Составляем таблицу, в которой в
столбцах расположим профессии, а в строках – фамилии
шахматистов.
Будем заполнять ячейки таблицы (нулями и единицами) согласно
условию задачи и результатов умозаключений по анализу строк или
столбцов.
токарь
слесарь
инженер
учитель
врач
шофер
Андреев
Борисов
Дмитриев
Григорьев
Евдокимов
Золотарев
Содержание

11.

1. Т.к. в первом туре 3 партии, то врач не Андреев, не Борисов, не
Григорьев, не Евдокимов. Ставим им 0 в столбце «врач».
токарь
слесарь
инженер
учитель
врач
Андреев
0
Борисов
0
шофер
Дмитриев
Григорьев
0
Евдокимов
0
Золотарев
Содержание

12.

1. Т.к. в первом туре 3 партии, то врач не Андреев, не Борисов, не
Григорьев, не Евдокимов. Ставим им 0 в столбце «врач».
2. Т.к. в втором туре 2 партии, то врач не Дмитриев. Значит, врач – Золотарев.
токарь
слесарь
инженер
учитель
врач
Андреев
0
Борисов
0
Дмитриев
0
Григорьев
0
Евдокимов
0
Золотарев
1
шофер
Содержание

13.

14.

15.

1. Т.к. в первом туре 3 партии, то врач не Андреев, не Борисов, не
Григорьев, не Евдокимов.
2. Т.к. в втором туре 2 партии, то врач не Дмитриев. Значит, врач – Золотарев.
3. Т.к. учитель не Андреев, не Борисов, не Григорьев, не Евдокимов (по усл.1)
и не Золотарев, значит, учитель – Дмитриев.
4. Т.к. инженер не Евдокимов, не Борисов, не Григорьев (по усл.4) и не
Золотарев или Дмитриев, значит, инженер – Андреев.
токарь
Учитель
врач
Андреев
0
0
Борисов
0
0
1
0
Григорьев
0
0
Евдокимов
0
0
0
1
Дмитриев
Золотарев
0
0
слесарь
0
0
Инженер
0
0
шофер
0
0
Содержание

16.

1. Т.к. в первом туре 3 партии, то врач не Андреев, не Борисов, не
Григорьев, не Евдокимов.
2. Т.к. в втором туре 2 партии, то врач не Дмитриев. Значит, врач – Золотарев.
3. Т.к. учитель не Андреев, не Борисов, не Григорьев, не Евдокимов (по усл.1)
и не Золотарев, значит, учитель – Дмитриев.
4. Т.к. инженер не Евдокимов, не Борисов, не Григорьев (по усл.4) и не
Золотарев или Дмитриев, значит, инженер – Андреев.
токарь
слесарь
инженер
учитель
врач
шофер
0
0
1
0
0
0
0
0
0
0
1
0
Григорьев
0
0
0
Евдокимов
0
0
0
0
0
1
Андреев
Борисов
Дмитриев
Золотарев
0
0
0
0
0
0
Содержание

17.

1. Т.к. в первом туре 3 партии, то врач не Андреев, не Борисов, не
Григорьев, не Евдокимов.
2. Т.к. в втором туре 2 партии, то врач не Дмитриев. Значит, врач – Золотарев.
3. Т.к. учитель не Андреев, не Борисов, не Григорьев, не Евдокимов (по усл.1)
и не Золотарев, значит, учитель – Дмитриев.
4. Т.к. инженер не Евдокимов, не Борисов, не Григорьев (по усл.4) и не
Золотарев или Дмитриев, значит, инженер – Андреев.
5. Т.к. Борисов не слесарь (по усл.4) и не токарь (по усл.2), значит, он – шофер.
токарь
слесарь
инженер
учитель
врач
шофер
0
0
1
0
0
0
0
0
0
0
1
0
Григорьев
0
0
0
Евдокимов
0
0
0
0
0
1
Андреев
Борисов
Дмитриев
Золотарев
0
0
0
0
0
0
Содержание

18.

1. Т.к. в первом туре 3 партии, то врач не Андреев, не Борисов, не
Григорьев, не Евдокимов.
2. Т.к. в втором туре 2 партии, то врач не Дмитриев. Значит, врач – Золотарев.
3. Т.к. учитель не Андреев, не Борисов, не Григорьев, не Евдокимов (по усл.1)
и не Золотарев, значит, учитель – Дмитриев.
4. Т.к. инженер не Евдокимов, не Борисов, не Григорьев (по усл.4) и не
Золотарев или Дмитриев, значит, инженер – Андреев.
5. Т.к. Борисов не слесарь (по усл.4) и не токарь (по усл.2), значит, он – шофер.
токарь
слесарь
инженер
учитель
врач
шофер
Андреев
0
0
1
0
0
0
Борисов
0
0
0
0
0
1
Дмитриев
0
0
0
1
0
0
Григорьев
0
0
0
0
Евдокимов
0
0
0
0
0
0
1
0
Золотарев
0
0
Содержание

19.

1. Т.к. в первом туре 3 партии, то врач не Андреев, не Борисов, не
Григорьев, не Евдокимов.
2. Т.к. в втором туре 2 партии, то врач не Дмитриев. Значит, врач – Золотарев.
3. Т.к. учитель не Андреев, не Борисов, не Григорьев, не Евдокимов (по усл.1)
и не Золотарев, значит, учитель – Дмитриев.
4. Т.к. инженер не Евдокимов, не Борисов, не Григорьев (по усл.4) и не
Золотарев или Дмитриев, значит, инженер – Андреев.
5. Т.к. Борисов не слесарь (по усл.4), значит, он – шофер (по усл.4).
6. Т.к Григорьев не слесарь (по усл.4), значит, он токарь. Тогда остается, что
слесарь – Евдокимов.
токарь
слесарь
инженер
учитель
врач
шофер
Андреев
0
0
1
0
0
0
Борисов
0
0
0
0
0
1
Дмитриев
0
0
0
1
0
0
Григорьев
0
0
0
0
Евдокимов
0
0
0
0
0
0
1
0
Золотарев
0
0
Содержание

20.

1. Т.к. в первом туре 3 партии, то врач не Андреев, не Борисов, не
Григорьев, не Евдокимов.
2. Т.к. в втором туре 2 партии, то врач не Дмитриев. Значит, врач – Золотарев.
3. Т.к. учитель не Андреев, не Борисов, не Григорьев, не Евдокимов (по усл.1)
и не Золотарев, значит, учитель – Дмитриев.
4. Т.к. инженер не Евдокимов, не Борисов, не Григорьев (по усл.4) и не
Золотарев или Дмитриев, значит, инженер – Андреев.
5. Т.к. Борисов не слесарь (по усл.4), значит, он – шофер (по усл.4).
6. Т.к Григорьев не слесарь (по усл.4), значит, он токарь. Тогда остается, что
слесарь – Евдокимов.
токарь
слесарь
инженер
учитель
врач
шофер
Андреев
0
0
1
0
0
0
Борисов
0
0
0
0
0
1
Дмитриев
0
0
0
1
0
0
Григорьев
1
0
0
0
0
0
Евдокимов
0
1
0
0
0
0
Золотарев
0
0
0
0
1
0
Содержание

21.

Решение логических задач с
использованием графов
Граф – это схема, в которой отображаются объекты, а также наличие и вид
связи между ними. Объекты в графе изображаются кружками или
прямоугольниками, связи – дугами, если связь однонаправленная, и
ребрами, если связь двунаправленная.
Метод решения логических задач с использованием графов делает более
наглядным представление условия задачи, что позволяет точно
определить правильное решение задачи.
Задача: на соревнованиях по легкой атлетике Аня, Варя, Света и Галя заняли первые четыре
места. Но когда мальчики стали вспоминать, как распределились эти места среди победителей, то
мнения разошлись:
Дима: Аня была первой, а Галя – второй; Толя: Аня была первой, а Валя – третьей; Леша: Валя
была четвертой, а Света – второй.
Коля, который был судьей на эти соревнованиях и хорошо помнил, как распределились места,
сказал, что каждый их мальчиков сделал одно верное и одно невероное заявление.
Как распределились места?
Содержание

22.

Решение логических задач с
использованием графов
Решение.
Введем обозначения: кружочком с буквой внутри будем обозначать девочек,
прямоугольниками с цифрами – места в соревновании.
Нарисуем граф, в котором будут отражены все три высказывания мальчиков
(мнение Димы – жирной линией, Толи – тонкой линией, Леши – пунктиром.
А
В
1
2
С
3
Г
4
Содержание

23.

Решение логических задач с
использованием графов
Мы знаем, что в каждом высказывании мальчиков есть одно правильное и одно
неверное заявление. Значит, в графе должны остаться по одному ребру каждого
типа.
Предположим, что истинно высказывание, обозначенное ребром Г-2 (Галя заняла
второе место). Тогда нам нужно удалить ребро А-1 (Дима прав только в одном
заявлении), А-2 и С-2 (второе место могла занять только одна девочка).
А
В
1
2
С
3
Г
4
Но Валя не могла занять одновременно 3 и 4 места, значит, предположение, что
Галя заняла второе место – неверно.
Содержание

24.

Решение логических задач с
использованием графов
Берем за истинность заявление Димы, что первой была Аня (оставляем ребро А-1,
удаляем ребро Г-2).
Если Аня заняла 1 место, значит, она не могла занять второе (пунктир А-2
удаляем, т. е. это высказывание Толи неверно, верно его высказывание, что
третьей была Валя).
Если Валя действительно была третьей, то она не могла быть четвертой, согласно
высказыванию Леши. Поэтому удаляем ребро В-4 (тонкая линия).а
А
В
1
2
С
3
Г
4
Ответ: Аня -1 , Валя – 2, света – 3, Галя – 4.
Содержание

25.

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

26.

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

27.

Решение логических задач с
использованием кругов Эйлера
бегуны и
прыгуны
х/3
прыгуны и
метатели
х/3 - 4
Х – вся команда
х/3 – бегуны
(х/3 – 2) – метатели
2*(х/3 – 2) – прыгуны
2*(х/3 – 2) - х/3 = х/3 – 4 – прыгуны и метатели
2*(х/3 – 4) – волейболисты
команда = бегуны + волейболисты + метатели
(часть прыгунов – бегуны, остальные – метатели)
х = х/3 + 2*(х/3 – 4) + (х/3 – 2) х = 30
волейболисты
метатели
2*(х/3 – 4)
х/3 - 2
X
Содержание

28.

Решение логических задач с
использованием алгебры логики
Алгоритм решения:
1) внимательно изучить условие;
2) выделить простые высказывания и обозначить их латинскими буквами;
3) записать условие задачи на языке алгебры логики;
4) составить конечную формулу, для этого объединить логическим умножением
или сложением формулы каждого утверждения, приравнять конечную формулу
единице;
5) упростить полученную формулу, используя законы логических преобразований,
проанализировать полученный результат или составить таблицу истинности, найти
по таблице значения переменных, для которых F = 1, проанализировать результаты.
Содержание

29.

Решение логических задач с
использованием алгебры логики
Задача о кабинетах.
В канун 1 апреля старшеклассники поменяли таблички на дверях кабинетов физики и
информатики. На первой повесили табличку «По крайней мере, в одном из этих кабинетов
находится кабинет информатики», а на втором – табличку с надписью «Кабинет физики
находится в другой аудитории». Школьники знают, что либо обе таблички истинны, либо
обе ложны. Нужно определить, где какие кабинеты располагаются.
Решение.
Выделим простые высказывания, введем обозначения.
А – в первой аудитории находится кабинет информатики
В - во второй аудитории находится кабинет информатики
not А – в первой аудитории находится кабинет физики
not В - во второй аудитории находится кабинет физики
Высказывание на двери первого кабинета Х = А или В, второго кабинета Y = not А
Содержание

30.

Решение логических задач с
использованием алгебры логики
Задача о кабинетах.
В канун 1 апреля старшеклассники поменяли таблички на дверях кабинетов физики и
информатики. На первой повесили табличку «По крайней мере, в одном из этих кабинетов
находится кабинет информатики», а на втором – табличку с надписью «Кабинет физики
находится в другой аудитории». Школьники знают, что либо обе таблички истинны, либо
обе ложны. Нужно определить, где какие кабинеты располагаются.
Решение.
По условию задачи обе таблички либо истинны либо ложны, т. е. искомая функция F равна 1:
F = (X Y) V (not X & not Y) = 1
Подставляем вместо Y и Y соответствующие формулы и производим упрощения, используя
логические законы.
F = ( ( A V B ) & not A ) V (not (A V B ) & not not A) = ( ( A V B ) & not A ) V (not (A V B ) & A)
F = (A & notA V B & notA ) V (( notA & notB) & A)
F = B & notA = 1
B=1 notA = 1 , т. е. А = 0 и при этом В =1
Ответ: в первой аудитории находится кабинет физики, во втором – информатики.
Содержание

31.

Решение логических задач с
использованием электронных таблиц
Задача о кабинетах.
В канун 1 апреля старшеклассники поменяли таблички на дверях кабинетов физики и
информатики. На первой повесили табличку «По крайней мере, в одном из этих кабинетов
находится кабинет информатики», а на втором – табличку с надписью «Кабинет физики
находится в другой аудитории». Школьники знают, что либо обе таблички истинны., либо
обе ложны. Нужно определить, где какие кабинеты располагаются.
Выделяем простые высказывания, вводим обозначения.
А – в первой аудитории находится кабинет информатики
В - во второй аудитории находится кабинет информатики
not А – в первой аудитории находится кабинет физики
not В - во второй аудитории находится кабинет физики
Высказывание на двери первого кабинета Х = А V В, на двери второго кабинета Y = not А
Итоговая формула: F = (X Y) V (not X & not Y) = 1
В ЭТ составляем таблицу истинности для функции F. Количество строк в таблице – 4 (2n, n=2 –
количество логических переменных), количество столбцов равно количеству логических переменных
плюс количество логических операций в функции F (равно 9).
Заполняем ТИ, в результирующем столбце F находим строку, в которой функция является истинной.
Содержание

32.

Решение логических задач с
использованием электронных таблиц
Как видим из ЭТ, только в одной строке F=Истина, это строка 7. В ней исходные значения А=0, В=1.
Это означает, что в первой аудитории находится кабинет физики, во втором – кабинет информатики.
Содержание

33.

Источники
- открытый банк заданий ОГЭ ФИПИ
www.fipi.ru/content/otkrytyy-bank-zadaniy-oge
- сайт К. Полякова
http://kpolyakov.spb.ru
- РЕШУ ОГЭ
https://oge.sdamgia.ru/
- Логика в информатике. В. Лыскова, М., Лаборатория Базовых Знаний, 2008
- Логические задачи. О. Богомолова, М., Бином, 2005
- Информатика и информационные технологии. Н Угринович, Бином, 2005
- демоверсии ОГЭ по информатике прошлых лет
Содержание

English Русский Rules