книги из ГПНТБ / Василевский, А. Б. Методы решения задач учебное пособие

учатся в одной школе, юннат и первоклассник живут в одном городе, Б и фотограф приехали в лагерь позже других; 2) В и чет­ вероклассник ходили утром в поход, а вечером Б и третьеклассник

АТУ|/тш

/уУ/уу

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

Составляем матрицу с тремя входами (рис. 52). Несовместные элементы отмечаем различной штриховкой в зависимости от условия.

120

Элементы 2Л, 1 JO, БФ несовместны (по первому условию за­ дачи). По второму условию несовместны элементы 3Б, 3В, 4В, /<3,

матист старше А и шахматист может быть только четвероклассни­

Применение алгебры высказываний

В алгебре высказываний элементами являются высказывания, например, «Николай — отличник», «Иван лжет». Для обозначения высказываний будем использовать большие латинские буквы А, В, С, ... Запись зн. {А} = 1 означает, что значение высказывания А является истиной; запись зн. (Л) = 0 означает, что значение вы­ сказывания А является ложью. Таким образом, всякое высказыва­ ние может принимать только значения 0 или 1.

Логическое произведение высказываний (конъюнкция). Логическое произведение высказываний Л и В обозначают так: А/\В. Эта операция соответствует составному высказыванию «Л и В». Такое составное высказывание считают истинным тогда и только тогда, когда оба высказывания истинны. Поэтому в качестве определения операции логического произведения целесообразно взять такую таблицу истинности:

Логическая сумма высказываний (дизъюнкция). Обозначение логической суммы A\jB. Эта операция соответствует составному высказыванию «Л или В». Это высказывание считается истинным

121

тогда и только тогда, когда истинно хотя бы одно из данных вы­ сказываний. Таблица истинности для операции «или»:

Отрицание высказывания. Отрицание высказывания А обозна­

чается так: А. Отрицание высказывания А соответствует высказы­ ванию «неверно, что Л». Поэтому оно определяется следующей таблицей истинности:

Ал

1 0

0 1

Как и в алгебре чисел, считаем, что операция умножения старше операции сложения. Это позволяет не писать некоторые скобки. Например, выражение

(А/\В)\/((А\/В) АС)

122

Сначала по значениям в первых двух столбцах заполняем третий

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

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

прашивать трех свидетелей: Клода, Жака и Дика. Их показания

1)либо Клод сказал правду, и тогда Жак солгал, либо Клод солгал, и тогда Жак сказал правду;

2)либо Жак сказал правду, тогда Дик солгал, либо Жак сол­ гал, и тогда Дик сказал правду;

Условие задачи выполняется в том случае, если одновременно истинны эти три алгебраические выражения, а следовательно, истинна их конъюнкция:

зн. ((К Л Ж У К Л Ж )Л (Ж Л Д У Ж /\Д )Л [Д /\К Л Ж У Д 7 \(К \/Ж )]| =

(К Л Ж У К Л Ж )Л (Ж А Д У Ж Л Д )Л [Д Л К /\Ж У Д Л (К У Ж )] =

= (КлЖлДУКЛЖлД)Л(ДЛКЛЖУД/\КУДЛЖ )=/ГлЖлЖ

После выполнения равносильных преобразований уравнение (1) заменяется таким:

зн. [КАЖАД] = 1.

Отсюда получаем зн. (/С) = 1; зн. (Ж) = 1; зн. (Д) = 1.

Таким образом, только Жак сказал правду, показания же Клода и Дика были ложными.

Применение графов

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

124

всех случаев. Объекты изображаются точками, а отношения между ними — отрезками.

Пример 4. Три товарища — Иван, Дмитрий и Степан — преподают различные предметы (химию, биологию, физику) в школах Москвы, Ленинграда и Киева. Известно, что:

1) Иван работает не в Москве, а Дмитрий не в Ленинграде;

2)москвич преподает не физику;

3)тот, кто работает в Ленинграде, преподает химию;

4)Дмитрий преподает не биологию.

Какой предмет и в каком городе преподает каждый из това­ рищей?

Рис. 53

Выделим три множества: множество имен, множество учебных предметов, множество городов. Элементы множеств обозначим точ­ ками (на рис. 53 точкам поставлены в соответствие первые буквы имен, предметов, городов). Две точки разных множеств соединим штриховой линией, если они характеризуют признаки разных людей. Две точки разных множеств соединим сплошными линиями, если они соответствуют признакам одного человека. Граф на рис. 53 содержит все указанные в задаче элементы множеств и отношения

между ними. Задача на языке графов свелась к построению трех треугольников со «сплошными» сторонами и вершинами в точках разных множеств.

125

быть штриховой.

Очевидно, что если какая-то точка соединена штриховыми от­ резками с двумя точками во втором множестве, то ее нужно соеди­

т

Строим «сплошные» отрезки МС, ИЛ, ХИ, БМ, БС.

владеют разными иностранными языками (английским, французским, немецким, испанским), но каждая только одним. Девушка, которая играет на гитаре,

127

Часть II. ГЕОМЕТРИЯ

Г л а в а 5. ОБЩИЕ ВОПРОСЫ РЕШЕНИЯ ГЕОМЕТРИЧЕСКИХ ЗАДАЧ

§ 1. С х е мы р е ш е н и я к о н с т р у к т и в н ы х з а д а ч *

Общие сведения

Решить задачу построением — это значит построить геометри­ ческую фигуру по данным фигурам и данным зависимостям между элементами этих фигур. Решением конструктивной задачи считается каждая фигура, которая удовлетворяет всем ее условиям.

Конструктивная задача считается решенной при помощи циркуля или линейки (или при помощи других данных нам инструментов), если указана конечная последовательность основных построений, после выполнения которых искомая фигура считается найденной в силу аксиом конструктивной геометрии. Непосредственное расчле­ нение конструктивного решения на основные построения в боль­ шинстве случаев приводит к большому числу логических операций. Поэтому если решение данной задачи удалось свести к ранее най­ денному решению какой-либо другой задачи, то она считается ре­ шенной.

При решении почти каждой конструктивной задачи возникает вопрос: как нужно рассуждать, чтобы найти ее решение, чтобы по­ лучить все решения и сформулировать те условия, при которых задача имеет решение? Чтобы последовательно рассмотреть все эти вопросы при решении конструктивной задачи, следует придержи­ ваться некоторого плана, т. е. схемы решения. Схемы решения конструктивных задач могут быть различны. Их выбор зависит и от содержания задачи, и от того метода, которым мы намерены ре­ шать эту задачу.

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

При решении задач на построение чаще всего используется че­ тырехэтапная схема, состоящая из анализа, построения, доказатель­

* Этот параграф заимствован из работы автора «Методы решения геометрш веских задач» (Минск, «Вышэйшая школа», 1969).