Решение логических задач при помощи построения трехмерной таблицы Автор: Алия Батырова ученица 10 класса МОУ-СОШ с. Кировское
Логические задачи на приведение во взаимно - однозначное соответствие элементов трех множеств удобно решать с помощью трехмерной таблицы.
Рассмотрим этот алгоритм на примере решения следующей логической задачи.
Задача Маша, Лида, Женя и Катя играют на разных инструментах – баяне, рояле, гитаре, скрипке, но каждая на одном. Они же владеют иностранными языками – английским, французским, немецким, испанским, но каждая одним.
Задача Девушка, играющая на гитаре, говорит по-испански. Ни Лида, ни Маша не играют на скрипке и баяне, не знают английского языка. Девушка, которая говорит по-немецки, не играет на баяне. Женя знает французский язык, но не играет на скрипке.
Кто играет на каком инструменте и каким иностранным языком владеет?
РЕШЕНИЕ ЗАДАЧИ
ИМЕНА ИНСТРУМЕНТЫ ЯЗЫКИ А Ф Н И Строится пространственная система координат XYZ*, на осях проставляются названия множеств* и элементы этих множеств*. Б Р Г С ЛЖКМ ИМЕНА М – Маша Л – Лида Ж – Женя К – Катя ЯЗЫКИ А – Английский Ф – Французский Н – Немецкий И – Испанский ИНСТРУМЕНТЫ Б – Баян Р – Рояль Г – Гитара С – Скрипка
ИМЕНА ИНСТРУМЕНТЫ ЯЗЫКИ ЛЖКМ Б Р Г С А Ф Н И Читается условие задачи*. ИМЕНА М – Маша Л – Лида Ж – Женя К – Катя ЯЗЫКИ А – Английский Ф – Французский Н – Немецкий И – Испанский ИНСТРУМЕНТЫ Б – Баян Р – Рояль Г – Гитара С – Скрипка
ИМЕНА ИНСТРУМЕНТЫ ЯЗЫКИ ЛЖКМ Б Р Г С А Ф Н И Если пара элементов в двух множествах находится в соответствии, то точка, лежащая на пересечении соответствующих прямых, становится центром темного кружка, в противном случае - белого кружка*. ИМЕНА М – Маша Л – Лида Ж – Женя К – Катя ЯЗЫКИ А – Английский Ф – Французский Н – Немецкий И – Испанский ИНСТРУМЕНТЫ Б – Баян Р – Рояль Г – Гитара С – Скрипка
ИМЕНА ИНСТРУМЕНТЫ ЯЗЫКИ ЛЖКМ Б Р Г С А Ф Н И Девушка, играющая на гитаре*, говорит по-испански*. ИМЕНА М – Маша Л – Лида Ж – Женя К – Катя ЯЗЫКИ А – Английский Ф – Французский Н – Немецкий И – Испанский ИНСТРУМЕНТЫ Б – Баян Р – Рояль Г – Гитара С – Скрипка
ИМЕНА ИНСТРУМЕНТЫ ЯЗЫКИ ЛЖКМ Б Р Г С Ф Н И Ни Лида, ни Маша* не играют на скрипке* и баяне*, не знают английского языка*. А ИМЕНА М – Маша Л – Лида Ж – Женя К – Катя ЯЗЫКИ А – Английский Ф – Французский Н – Немецкий И – Испанский ИНСТРУМЕНТЫ Б – Баян Р – Рояль Г – Гитара С – Скрипка
ИМЕНА ИНСТРУМЕНТЫ ЯЗЫКИ ЛЖКМ Р Г С А Ф Н И Девушка, которая говорит по-немецки*, не играет на баяне*. Б ИМЕНА М – Маша Л – Лида Ж – Женя К – Катя ЯЗЫКИ А – Английский Ф – Французский Н – Немецкий И – Испанский ИНСТРУМЕНТЫ Б – Баян Р – Рояль Г – Гитара С – Скрипка
ИМЕНА ИНСТРУМЕНТЫ ЯЗЫКИ ЛКМ Б Р Г С А Н И Женя* знает французский язык*, но не играет на скрипке*. Ф Ж ИМЕНА М – Маша Л – Лида Ж – Женя К – Катя ЯЗЫКИ А – Английский Ф – Французский Н – Немецкий И – Испанский ИНСТРУМЕНТЫ Б – Баян Р – Рояль Г – Гитара С – Скрипка
ИМЕНА ИНСТРУМЕНТЫ ЯЗЫКИ ЛКМ Б Р Г С А Н И Применяется правило экстраполяции*. Ф Ж ИМЕНА М – Маша Л – Лида Ж – Женя К – Катя ЯЗЫКИ А – Английский Ф – Французский Н – Немецкий И – Испанский ИНСТРУМЕНТЫ Б – Баян Р – Рояль Г – Гитара С – Скрипка
ИМЕНА ИНСТРУМЕНТЫ ЯЗЫКИ ЛКМ Б Р Г С А Н И «Тёмная» экстраполяция. Если на горизонтали (вертикали) все фигуры, кроме одной, светлые*, то свободная занимается тёмной фигурой*. Ф Ж ИМЕНА М – Маша Л – Лида Ж – Женя К – Катя ЯЗЫКИ А – Английский Ф – Французский Н – Немецкий И – Испанский ИНСТРУМЕНТЫ Б – Баян Р – Рояль Г – Гитара С – Скрипка
ИМЕНА ИНСТРУМЕНТЫ ЯЗЫКИ ЛКМ Б Р Г С А Н И «Светлая» экстраполяция. Если на горизонтали (вертикали) имеется «тёмная» фигура*, то все остальные фигуры на ней - светлые*. Ф Ж ИМЕНА М – Маша Л – Лида Ж – Женя К – Катя ЯЗЫКИ А – Английский Ф – Французский Н – Немецкий И – Испанский ИНСТРУМЕНТЫ Б – Баян Р – Рояль Г – Гитара С – Скрипка
ИМЕНА ИНСТРУМЕНТЫ ЯЗЫКИ ЛКМ Б Р Г С А Н И Повторяются правила «светлой» и «темной» экстраполяций, пока это возможно*. Ф Ж ИМЕНА М – Маша Л – Лида Ж – Женя К – Катя ЯЗЫКИ А – Английский Ф – Французский Н – Немецкий И – Испанский ИНСТРУМЕНТЫ Б – Баян Р – Рояль Г – Гитара С – Скрипка
ИМЕНА ИНСТРУМЕНТЫ ЯЗЫКИ ЛКМ Б Р Г С А Н И К темной фигуре, находящейся на пересечении элементов Ж и Ф*, применим «светлую» экстраполяцию*. Ф Ж ИМЕНА М – Маша Л – Лида Ж – Женя К – Катя ЯЗЫКИ А – Английский Ф – Французский Н – Немецкий И – Испанский ИНСТРУМЕНТЫ Б – Баян Р – Рояль Г – Гитара С – Скрипка
ИМЕНА ИНСТРУМЕНТЫ ЯЗЫКИ ЛКМ Б Р Г С А Н И К темной фигуре, находящейся на пересечении элементов Г и И*, также применим «светлую» экстраполяцию*. Ф Ж ИМЕНА М – Маша Л – Лида Ж – Женя К – Катя ЯЗЫКИ А – Английский Ф – Французский Н – Немецкий И – Испанский ИНСТРУМЕНТЫ Б – Баян Р – Рояль Г – Гитара С – Скрипка
ИМЕНА ИНСТРУМЕНТЫ ЯЗЫКИ ЛКМ Б Р Г С А Н И В результате «темной» экстраполяции в плоскости XY*, на пересечении элементов А и К, появится темная фигура*. Ф Ж ИМЕНА М – Маша Л – Лида Ж – Женя К – Катя ЯЗЫКИ А – Английский Ф – Французский Н – Немецкий И – Испанский ИНСТРУМЕНТЫ Б – Баян Р – Рояль Г – Гитара С – Скрипка
ИМЕНА ИНСТРУМЕНТЫ ЯЗЫКИ ЛКМ Б Р Г С А Н И В плоскости XZ в результате «темной» экстраполяции*, на пересечении элементов Б и Ж появится темная фигура *. Ф Ж ИМЕНА М – Маша Л – Лида Ж – Женя К – Катя ЯЗЫКИ А – Английский Ф – Французский Н – Немецкий И – Испанский ИНСТРУМЕНТЫ Б – Баян Р – Рояль Г – Гитара С – Скрипка
ИМЕНА ИНСТРУМЕНТЫ ЯЗЫКИ ЛКМ Б Р Г С А Н И В плоскости XY к темной фигуре, находящейся на пересечении элементов А и К*, применим «светлую» экстраполяцию*. Ф Ж ИМЕНА М – Маша Л – Лида Ж – Женя К – Катя ЯЗЫКИ А – Английский Ф – Французский Н – Немецкий И – Испанский ИНСТРУМЕНТЫ Б – Баян Р – Рояль Г – Гитара С – Скрипка
ИМЕНА ИНСТРУМЕНТЫ ЯЗЫКИ ЛКМ Б Р Г С А Н И В плоскости XZ к темной фигуре, находящейся на пересечении элементов Б и Ж*, также применим «светлую» экстраполяцию*. Ф Ж ИМЕНА М – Маша Л – Лида Ж – Женя К – Катя ЯЗЫКИ А – Английский Ф – Французский Н – Немецкий И – Испанский ИНСТРУМЕНТЫ Б – Баян Р – Рояль Г – Гитара С – Скрипка
ИМЕНА ИНСТРУМЕНТЫ ЯЗЫКИ ЛКМ Б Р Г С А Н И Правило множественного проектирования.* Ф Ж ИМЕНА М – Маша Л – Лида Ж – Женя К – Катя ЯЗЫКИ А – Английский Ф – Французский Н – Немецкий И – Испанский ИНСТРУМЕНТЫ Б – Баян Р – Рояль Г – Гитара С – Скрипка
ИМЕНА ИНСТРУМЕНТЫ ЯЗЫКИ ЛКМ Р Г С А Н И «Темная» фигура* в своей плоскости проектируется на координатные оси*. Прямые, проведенные через проекции в двух других плоскостях*, раскрашиваются одинаково*. Ф ИМЕНА М – Маша Л – Лида Ж – Женя К – Катя ЯЗЫКИ А – Английский Ф – Французский Н – Немецкий И – Испанский ИНСТРУМЕНТЫ Б – Баян Р – Рояль Г – Гитара С – Скрипка Б Ж
ИМЕНА ИНСТРУМЕНТЫ ЯЗЫКИ ЛКМ Б Р Г С А Н И В плоскости YZ к «темной» фигуре, находящейся на пересечении элементов Ф и Б*, применим «светлую» экстраполяцию*. Ф Ж ИМЕНА М – Маша Л – Лида Ж – Женя К – Катя ЯЗЫКИ А – Английский Ф – Французский Н – Немецкий И – Испанский ИНСТРУМЕНТЫ Б – Баян Р – Рояль Г – Гитара С – Скрипка
ИМЕНА ИНСТРУМЕНТЫ ЯЗЫКИ ЛКМ Б Р Г С А Н И Проектирование в плоскости YZ «темной» фигуры, находящейся на пересечении элементов И и Г*, не дает информации, так как прямые, проведенные через проекции в двух других плоскостях*, уже раскрашены одинаково*. Ф Ж ИМЕНА М – Маша Л – Лида Ж – Женя К – Катя ЯЗЫКИ А – Английский Ф – Французский Н – Немецкий И – Испанский ИНСТРУМЕНТЫ Б – Баян Р – Рояль Г – Гитара С – Скрипка
ИМЕНА ИНСТРУМЕНТЫ ЯЗЫКИ ЛМ Б Р Г А Н И Применим проектирование к «темной» фигуре, находящейся на пересечении элементов К и С в плоскости XZ*. Ф Ж С К ИМЕНА М – Маша Л – Лида Ж – Женя К – Катя ЯЗЫКИ А – Английский Ф – Французский Н – Немецкий И – Испанский ИНСТРУМЕНТЫ Б – Баян Р – Рояль Г – Гитара С – Скрипка
ИМЕНА ИНСТРУМЕНТЫ ЯЗЫКИ ЛМ Б Р Г А Н И Ф Ж С К В плоскости YZ повторим «темную»* и «светлую» экстраполяции*. ИМЕНА М – Маша Л – Лида Ж – Женя К – Катя ЯЗЫКИ А – Английский Ф – Французский Н – Немецкий И – Испанский ИНСТРУМЕНТЫ Б – Баян Р – Рояль Г – Гитара С – Скрипка
ИМЕНА ИНСТРУМЕНТЫ ЯЗЫКИ ЛМ Б Р Г А Н И Ф Ж С К В сложившейся ситуации возможности экстраполяции и проектирования исчерпаны, а задача не решена… В таких случаях делается допущение о цвете фигуры в какой-либо свободной вершине сетки*. ИМЕНА М – Маша Л – Лида Ж – Женя К – Катя ЯЗЫКИ А – Английский Ф – Французский Н – Немецкий И – Испанский ИНСТРУМЕНТЫ Б – Баян Р – Рояль Г – Гитара С – Скрипка
ИМЕНА ИНСТРУМЕНТЫ ЯЗЫКИ ЛМ Б Р Г А И Ф Ж С К Пусть точка, лежащая на пересечении элементов М и Н*, станет центром «темного» кружка*. Применим к ней «светлую» экстраполяцию*. ИМЕНА М – Маша Л – Лида Ж – Женя К – Катя ЯЗЫКИ А – Английский Ф – Французский Н – Немецкий И – Испанский ИНСТРУМЕНТЫ Б – Баян Р – Рояль Г – Гитара С – Скрипка Н
ИМЕНА ИНСТРУМЕНТЫ ЯЗЫКИ ЛМ Б Р Г А Н И Ф Ж С К В результате «темной» экстраполяции, на пересечении элементов Л и И*, появится «темная» фигура*. ИМЕНА М – Маша Л – Лида Ж – Женя К – Катя ЯЗЫКИ А – Английский Ф – Французский Н – Немецкий И – Испанский ИНСТРУМЕНТЫ Б – Баян Р – Рояль Г – Гитара С – Скрипка
ИМЕНА ИНСТРУМЕНТЫ ЯЗЫКИ Л Б Р Г А И Ф Ж С К В плоскости XY к «темной» фигуре, находящейся на пересечении элементов М и Н*, применим проектирование*. Н М ИМЕНА М – Маша Л – Лида Ж – Женя К – Катя ЯЗЫКИ А – Английский Ф – Французский Н – Немецкий И – Испанский ИНСТРУМЕНТЫ Б – Баян Р – Рояль Г – Гитара С – Скрипка
ИМЕНА ИНСТРУМЕНТЫ ЯЗЫКИ Л Б Р Г А И Ф Ж С К К точке, находящейся на пересечении элементов Л и И*, также применим правило проектирования*. Н М НН ММ НН ИМЕНА М – Маша Л – Лида Ж – Женя К – Катя ЯЗЫКИ А – Английский Ф – Французский Н – Немецкий И – Испанский ИНСТРУМЕНТЫ Б – Баян Р – Рояль Г – Гитара С – Скрипка
ИМЕНА ИНСТРУМЕНТЫ ЯЗЫКИ Л Б Р Г Ж С К Н М НН ММ Н И Ф Н А ИМЕНА М – Маша Л – Лида Ж – Женя К – Катя ЯЗЫКИ А – Английский Ф – Французский Н – Немецкий И – Испанский ИНСТРУМЕНТЫ Б – Баян Р – Рояль Г – Гитара С – Скрипка При допущении о цвете фигуры в свободной вершине сетки мы не получили противоречий, поэтому можно считать, что задача решена верно*.
ИМЕНА ИНСТРУМЕНТЫ ЯЗЫКИ Б Р Г С Итак, мы узнали, что Маша играет на рояле и владеет немецким языком *, Лида играет на гитаре и знает испанский язык*, Женя играет на баяне и владеет французским языком*, Катя играет на скрипке и знает английский язык*. НННН И Ф Н А ИМЕНА М – Маша Л – Лида Ж – Женя К – Катя ЯЗЫКИ А – Английский Ф – Французский Н – Немецкий И – Испанский ИНСТРУМЕНТЫ Б – Баян Р – Рояль Г – Гитара С – Скрипка М ЛЖ К
ИМЕНА ИНСТРУМЕНТЫ ЯЗЫКИ ЛМ Б Р Г А Н И Ф Ж С К А теперь, чтобы проверить, не имеет ли данная задача двух верных решений, вернемся назад и предположим противное: пусть точка, лежащая на пересечении элементов М и Н*, станет центром не «темного», а светлого кружка*. ИМЕНА М – Маша Л – Лида Ж – Женя К – Катя ЯЗЫКИ А – Английский Ф – Французский Н – Немецкий И – Испанский ИНСТРУМЕНТЫ Б – Баян Р – Рояль Г – Гитара С – Скрипка
ИМЕНА ИНСТРУМЕНТЫ ЯЗЫКИ ЛМ Б Р Г А Н И Ф Ж С К После применения правил экстраполяции и множественного проектирования, таблица заполнится следующим образом*. В заполненной таблице мы не видим противоречий, это означает, что полученное решение, тоже удовлетворяет заданным условиям*. ИМЕНА М – Маша Л – Лида Ж – Женя К – Катя ЯЗЫКИ А – Английский Ф – Французский Н – Немецкий И – Испанский ИНСТРУМЕНТЫ Б – Баян Р – Рояль Г – Гитара С – Скрипка
ИМЕНА ИНСТРУМЕНТЫ ЯЗЫКИ Б Р Г С Согласно второму решению, Маша играет на гитаре и владеет испанским языком *, Лида играет на рояле и знает немецкий язык*, Женя играет на баяне и владеет французским языком*, Катя играет на скрипке и знает английский язык*. НННН И Ф Н А ИМЕНА М – Маша Л – Лида Ж – Женя К – Катя ЯЗЫКИ А – Английский Ф – Французский Н – Немецкий И – Испанский ИНСТРУМЕНТЫ Б – Баян Р – Рояль Г – Гитара С – Скрипка М ЛЖ К
ИМЕНА ИНСТРУМЕНТЫ ЯЗЫКИ ЛЖКМ Б Р Г С Ф Н И При решении данной задачи нам не пришлось использовать правило множественной экстраполяции, которое заключается в следующем: если две (n) параллели в плоскости* одинаково светло раскрашены,* везде, за исключением двух (n) неокрашенных вершин*, то на двух (n) параллелях другого направления, проходящих через эти неокрашенные вершины*, вне данных прямых вставляются светлые фигуры*. А ИМЕНА М – Маша Л – Лида Ж – Женя К – Катя ЯЗЫКИ А – Английский Ф – Французский Н – Немецкий И – Испанский ИНСТРУМЕНТЫ Б – Баян Р – Рояль Г – Гитара С – Скрипка
ИМЕНА ИНСТРУМЕНТЫ ЯЗЫКИ ЛЖКМ Б Р Г С Ф Н И А ИМЕНА М – Маша Л – Лида Ж – Женя К – Катя ЯЗЫКИ А – Английский Ф – Французский Н – Немецкий И – Испанский ИНСТРУМЕНТЫ Б – Баян Р – Рояль Г – Гитара С – Скрипка В некоторых задачах применение этого правила упрощает решение.
Задача После традиционного вечера встречи с выпускниками школы в стенгазете появилась заметка о трех наших бывших учениках. В ней было сказано, что Иван, Андрей и Борис стали учителями. Теперь они преподают разные дисциплины: один из них – математику, второй – физику, а третий – химию. Живут они тоже в разных городах: Минске, Витебске, Харькове. В заметке было также написано, что их первоначальные планы осуществились не полностью: 1) Иван живет не в Минске. 2) Андрей - не в Витебске. 3) Житель Минска преподает не математику. 4) Андрей преподает не физику. 5) Повезло только жителю Витебска: он преподает любимую им химию. Определите, кто где живет и что преподает? Эту задачу можно решить с помощью вышеизложенного метода.
Литература 1.Лыскова В.Ю., Ракитина Е.А. Логика в информатике. – М.: Лаборатория Базовых Знаний, Шапиро С.И. Решение логических и игровых задач (логико- психологические этюды). – М.: Радио и связь, 1984