Задание 23. Советы учителям и ученикам

1. Какие знания/умения/навыки нужны ученику, чтобы решить эту задачу

Эта задача – одна из самых сложных в экзамене, если не самая сложная. Для ее решения ученик должен уметь

- преобразовывать логические выражения (включая выполнение замены переменных);

- переводить формальное описание, в виде системы логических условий, на нормальный, "человеческий" язык;

- подсчитать число двоичных наборов, удовлетворяющих заданным условиям.

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

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

2 Рекомендации для учителей: как разбирать задачу с учениками

Эти рекомендации – не догма, а попытка сделать выводы из собственного опыта и опыта коллег. Ждем комментариев и Ваших рекомендаций. Придумывайте свои подходы, применяйте их и сообщайте нам!

2.1. Преобразования логических выражений

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

¬a \/ b равносильно a→ b

(a→ b) /\ (b→ a) равносильно a ≡ b

(¬a \/ b) /\ (a\/¬b) равносильно a ≡ b

(a \/ b) /\ (¬a \/ ¬b) равносильно ¬(a ≡ b).

Подробнее о преобразованиях логических выражений написано здесь [см. раздел "ТЕМЫ"]

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

2.2. Анализ множества решений.

Самое трудное – сообразить, что из себя представляет множество решений. В разделах 5 и 6 разобрано несколько примеров. Другие полезные примеры и рекомендации можно найти, например,  на сайте К.Ю.Полякова и в пособии под ред. В.Р.Лещинера.

2.3. Подсчет количества решений

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

2.4. Выводы

Таким образом, план подготовки может быть примерно таким.

1) Повторить логические преобразования и элементы комбинаторики.

2) Порешать задачи и попрактиковаться в переводе формального описания, в виде системы логических условий, на нормальный, "человеческий" язык.

3. Рекомендации для учеников: как решать подобные задачи

Точного алгоритма действий, гарантированно приводящего к успеху здесь нет. Первая цель – понять, что собой представляет множество решений системы. Для этого систему бывает полезно преобразовать (упростить) систему, используя тождественные преобразования и замены переменных. Затем – подсчитать количество элементов во множестве решений.

Во многих случаях система состоит из однотипных уравнений, каждое из которых связывает небольшое число переменных (две-три-четыре), при том, что в системе может быть 10 и более переменных. Обычно, количество переменных не является источником сложности, оно является параметром решения. Если не получается решить задачу в общем виде, можно попробовать перебрать все решения для системы с небольшим количеством переменных. Это может подсказать, как выглядит решение в общем виде.