A.A. Lokshin - Аннотация

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

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

Задача 1.Имеется 5 одуванчиков и 19 репейников. Сколькими способами можно составить из них букет, состоящий из трёх одуванчиков и семи репейников?

Решение.Букет, очевидно, представляет собой неупорядоченное множество, элементы которого выбираются из двух других непересекающихсянеупорядоченных множеств – множества одуванчиков:

ОД = {ОД1, ОД2,..., ОД5} (1)

и множества репейников:

P = {Р1, Р2,..., Р19}. (2)

Существенно, однако, то, что каждому букету Б можно вз а имно-однозначным образом сопоставить упорядоченную пару

Б ↔ ({три одуванчика); {семь репейников}). (3)

Это оказывается возможным только потому, что множества (1) и (2) не пересекаются!

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

({три одуванчика); {семь репейников}) (4)

являются два неупорядоченных множества.

Теперь в силу взаимной однозначности соответствия (3) заключаем, что численность множества Б (т.е. искомое число различных букетов заданного состава) равна численности множества упорядоченных пар вида (4).Тем самым, применяя правило произведения для нахождения этой численности, получаем

Ответ:искомое число способов равно ∙ ; здесь – число сочетаний из n элементов по k элементов.

Соображения вида (3) обычно считаются само собой разумеющимися и, как правило, опускаются в разделах, посвященных комбинаторике. Однако, на наш взгляд, проведенное рассуждение заслуживает большего внимания и, быть может, даже специального названия – например, « обобщенного правила произвед е ния ».

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

Задача 2.Имеется 5 одуванчиков и 19 репейников. Сколькими способами можно составить из них букет, состоящий из десяти цветков и содержащий не менее трех одуванчиков?

Ответ:

Каждый педагог, ведущий начальный курс логики, сталкивается с необходимостью иллюстрировать логические законы на примерах, взятых из естественного языка. Здесь, однако, преподавателя логики подстерегают трудности, связанные с тем, что язык логики и естественный язык – неизоморфны.

Пример 1.Попробуем проиллюстрировать закон де Моргана

(1)

(Здесь символы , и обозначают соответственно отрицание , кон ъ юнкцию и дизъюнкцию высказываний.)

Рассмотрим высказывание

«Я не буду поступать в МГУ и в МПГУ» . (2)

По вышеприведенному закону де Моргана высказывание (2), казалось бы, следует понимать так:

«Я не буду поступать в МГУ или я не буду поступать в МПГУ», т.е.

«Я не буду поступать хотя бы в одно из этих учебных завед е ний». (3)

Однако, в естественном языке фраза (2) имеет вполне определенный смысл, не совпадающий с (3). А именно, смысл (2) таков:

«Я не буду поступать в МГУ и я не буду поступать в МПГУ». (2)

Таким образом, использовать примеры вида (2) для иллюстрации упомянутого выше закона де Моргана – нельзя.

Еще более интересная ситуация возникает, когда мы имеем дело с высказываниями, содержащими кванторы общности и существования .

Пример 2.Рассмотрим, например, следующий закон отрицания высказываний с квантором общности

(4)

заметим при этом, что «утверждение»

«» (4а)

является грубой ошибкой .

Попробуем теперь проиллюстрировать закон (4), отрицая высказывание:

«Каждый сумеет решить эту задачу». (5)