Особенности преподавания курса дискретной математики во втузе

МЕТОДИКА ПРЕПОДАВАНИЯ ОМСКИЙ НАУЧНЫЙ ВЕСТНИК №1 (95) 2011

УДК 378.147 : 51

Н. Н. ЗЕПНОВА О. В. КУЗЬМИН

Научно-исследовательский Иркутский государственный технический университет Иркутский государственный университет

ОСОБЕННОСТИ ПРЕПОДАВАНИЯ КУРСА ДИСКРЕТНОЙ МАТЕМАТИКИ ВО ВТУЗЕ

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

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

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

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

071900 — Геоинформационные системы (ГИС): множества, логические исчисления, графы, теория алгоритмов, языки и грамматики, автоматы, комбинаторика.

220200—Автоматизированные системы обработки информации и управления (АСУ): перечислительная комбинаторика, множества, отношения на множествах, булевы функции, графы, математическая логика и формальные системы.

210300 — Роботы и робототехнические системы (РТС): множества, булева алгебра, логика предикатов, графы, языки и грамматики, автоматы.

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

стандарта, но и открыть им целостность структуры этой науки [1].

Исходя из вышесказанного, и на основе собственного опыта преподавания дискретной математики в ИрГТУ, мы пришли к выводу о необходимости создания учебно-методического пособия по изучению основ дискретной математики, предназначенного для преподавателей и студентов втуза. Мы начали разрабатывать такое пособие в 2008 г., и на данный момент принята к публикации его первая часть: «Основы теории множеств» [2], и готовится к публикации вторая — «Элементы булевой алгебры».

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

Первая часть «Основы теории множеств» содержит три основные раздела: «Множества. Действия с множествами», «Отношения на множествах», «Бесконечные множества». После каждого раздела приводится перечень контрольных вопросов, с помощью которых студент может самостоятельно проверить уровень и качество усвоения материала.

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

В первой главе «Множества. Действия с множествами» решаются задачи формирования у студентов понятийного аппарата теории множеств и навыков

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

Прежде всего, мы предлагаем применить различные подходы к определению понятия «множество», способам задания множества, что позволит избежать формирования стереотипа у студентов. При этом мы приводим большое количество примеров различных множеств, описывая их разными способами. Рассматриваются понятия подмножества, виды подмножеств, понятие синглетона, булеана, пустого множества, универсального множества, кардинального числа (мощности) множества и т.д. [3]. Все указанные понятия расширяют терминологический запас студентов, что позволит им без труда самостоятельно заниматься изучением теории множеств.

Различные действия с множествами (объединение, пересечение, дополнение, разность, симметрическая разность), а так же их свойства иллюстрируются с помощью диаграмм Эйлера—Венна [4], что улучшает восприятие учебного материала. Аналогично доказываются основные теоремы о действиях с множествами: теоремы поглощения, склеивания, теоремы де Моргана. Доказательство некоторых свойств и теорем студентам предлагается провести самостоятельно — это хорошая тренировка применения средств дискретной математики к решению теоре-тических и практических задач.

После изучения основных действий с множествами и теорем мы рассматриваем теоретико-множественные преобразования. Под теоретико-множественными преобразованиями мы понимаем выполнение таких действий с множествами, в результате которых получается новое аналитическое выражение, тождественноравное исходному, но отличающееся от него набором символов, их числом, порядком записи. Целью преобразований является упрощение формул, приводящее к уменьшению количества входящих в них знаков. Упрощенные выражения могут подвергаться дальнейшим преобразованиям с учетом каких-либо дополнительных условий: взаимосвязи между множествами, заменой одного множества другим, нахождение дополнения и т.д. Все подобные преобразования осуществляются с помощью операций объединения, пересечения, дополнения, склеивания, поглощения и законов де Моргана. При рассмотрении подобных задач следует обратить внимание студентов на возможность различных путей решения: с помощью диаграмм Эйлера — Венна и методом теоретико-множественных преобразований, и особо отметить преимущества последнего.

Вторая глава «Отношения на множествах» посвящена важнейшим отношениям между двумя или несколькими множествами. Подробно рассматриваются свойства отношений (транзитивность, рефлексивность, симметричность (а также противоположные им), полнота, универсальность и др.). При этом интересно рассмотреть отношения не только между математическими объектами, такие как: «прямая а перпендикулярна прямой Ь» (в пространстве), «отрезок а короче отрезка Ь на 5 сантиметров»; «число а = числу Ь», но и между людьми или объектами окружающего мира: «Толя брат Пети», «Петя увидел Колю»; «быть одноклассниками», «проиграть в шахматы», «Иркутск расположен южнее Омска». Подобные задачи позволяют увлечь студентов интересными межличностными ситуациями и облегчить понимание изучаемого материала.

Исходя из свойств отношений, рассматриваются различные виды отношений: эквивалентность, квази-

порядок, порядок, строгий порядок, полный порядок. Установление вида конкретного отношения позволяет студентам лучше усвоить свойства отношений. Особое внимание уделяется изучению различных видов отображений множеств. Необходимость этого вызвана тем, что при изучении математического анализа у студентов формируется представление об отображениях множеств только как об «одно-однозна-чных», тогда как существуют и другие виды отображений. Наконец, рассматривается вопрос разбиения множеств на классы с помощью отношения эквивалентности, что позволяет устанавливать мощность бесконечных множеств в дальнейшем [5].

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

В заключение третьего раздела приводятся определение и основные свойства несчетных множеств. Эта тема, как правило, составляет особую трудность для изучения, поскольку требует отказаться от интуитивных представлений о реальном мире и опираться только на логические рассуждения и факты, доказанные в теории множеств. Поэтому подробно рассматривается вопрос о несчетности множества действительных чисел, принадлежащих отрезку [0, 1] и приводится логическое доказательство данного утверждения с помощью диагонального метода Кантора [6]. После доказательства данного факта целесообразно привести примеры доказательства несчетности некоторых множеств путем установления взаимнооднозначного соответствия с множеством действительных чисел, принадлежащих отрезку [0, 1].

Материал третьей главы, в зависимости от требований учебной программы специальности, можно рассматривать в сокращенном варианте.

Вторая часть пособия «Элементы Булевой алгебры» включает две главы: «Операции Булевой алгебры» и «Минимизация булевых функций»

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

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

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

ОМСКИЙ НАУЧНЫЙ ВЕСТНИК №1 (95) 2011 МЕТОДИКА ПРЕПОДАВАНИЯ

МЕТОДИКА ПРЕПОДАВАНИЯ ОМСКИЙ НАУЧНЫЙ ВЕСТНИК №1 (95) 2011

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

Далее мы предлагаем рассмотреть основные операции над переменными в Булевой алгебре (дизъюнкция, конъюнкция и инверсия). Очень важно иллюстрировать аксиомы, которыми определяются операции, необычными примерами, может быть даже не имеющими отношения к математике. Например: пусть высказывание А означает: «до Ангарска из Иркутска можно доехать электричкой», а В — «до Ангарска из Иркутска можно доехать автобусом». Как А, так и В являются истинными. Тогда сложные высказывания А+В: «до Ангарска из Иркутска можно доехать электричкой или автобусом» и А-В: «до Ангарска из Иркутска можно доехать как электричкой, так и на на автобусе» являются истинными. Высказывание С: «до Ангарска из Иркутска можно доехать на метро» является ложным (поскольку метро в Иркутске нет), но сложное высказывание А + С: «до Ангарска из Иркутска можно доехать электричкой или на метро» — истинно. Высказывание же А-В: «до Ангарска из Иркутска можно доехать как электричкой, так и на метро» является ложным. Подобные примеры позволяют учащимся лучше усвоить особенности операций и повышают интерес к предмету.

При доказательстве коммутативности, ассоциативности, инвариантности дизъюнкции и конъюнкции можно обойтись аксиомами этих действий. А вот свойства дистрибутивности конъюнкции относительно дизъюнкции: А(В+С)=АВ+АС; и особенно, дистрибутивности дизъюнкции относительно конъюнкции: А+ВС=(А+В)(А+С) уже не столь очевидны. Для их доказательства целесообразно ввести понятие таблицы истинности.

Докажем, например, последнее свойство, сведя данные в таблицу. Для этого будем придавать переменным все возможные наборы, которые они могут принимать, и вычислять значение выражений, стоящих в левой и в правой частях доказываемого равенства при всех наборах переменных. При этом необходимо объяснить студентам, что перечисление наборов значений переменных не должно быть произвольным: если набор значений переменных принять за двоичное число, то номер строки будет означать это число в десятичной системе. Например, набор 100 в пятой строке означает число 4. Поэтому первая строка имеет номер 0, и этому числу в десятичной системе соответствует набор 000 в двоичной. Каждый набор последующей строчки получается из предыдущего набора прибавлением 1 к двоичному числу согласно правилам сложения в двоичной системе.

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

Сравнивая колонки, соответствующие значениям комбинаций А+ВС и (А+В)(А+С), видим, что при одних и тех же наборах переменных они принимают одинаковые значения. Таким образом, истинность утверждения доказана. Таблицы истинности применяются и далее при исследовании булевых функций.

Далее целесообразно рассмотреть теоремы одной переменной, поскольку их доказательство вытекает непосредственно из свойств конъюнкции, дизъюнкции и инверсии. Здесь можно провести аналогию

с теорией множеств (операции объединения и пересечения множества с пустым и универсальным множествами). Например, в теории множеств теореме А-1 = А соответствует свойство: АпИ=А. Аналогию с теорией множеств уместно проводить и при доказательстве теорем поглощения, склеивания и де Моргана: объединение множеств есть дизъюнкции в булевой алгебре, пересечение — конъюнкции, а дополнение — инверсии. Рассмотрим, например, теорему поглощения, которая может быть записана в дизъюнктивной (А + АВ =А) и конъюнктивной А(А + В)=А форме. Если заменить знак « + » на «и», а знак «» на «п», получим теорему поглощения для множеств дизъюнктивной и конъюнктивной форме соответственно.

Доказательство теорем склеивания и поглощения можно провести как с помощью свойств конъюнкции и дизъюнкции, так и с помощью таблиц истинности. А вот доказательство теоремы де Моргана возможно провести только с помощью таблицы истинности или воспользоваться аналогией с теорией множеств. Можно предложить студентам доказать эти теоремы самостоятельно — это будет хорошим упражнением.

Теоремы поглощения, склеивания и де Моргана применяются для упрощения различных комбинаций булевых переменных, связанных операциями дизъюнкции, конъюнкции или инверсии, называемых булевыми формулами [7]. Поэтому далее мы предлагаем рассмотреть несколько задач по упрощению булевых формул, что позволит студентам закрепить полученные знания.

Во второй главе «Минимизация булевых функций» мы рассматриваем различные формы представления булевых формул. Они могут быть записаны в виде комбинаций дизъюнкций и конъюнкций нескольких переменных. Если булева формула записана в виде дизъюнкции выражений, каждое из которых представляет собой либо отдельный элемент (с инверсией или без) либо конъюнкцию некоторых элементов, то говорят, что эта формула представлена в дизъюнктивной нормальной форме (ДНФ). Аналогично определяется понятие конъюнктивной нормальной формы (КНФ) булевой формулы.

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

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

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

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

аргументов, называемую элементарной конъюнкцией (минтермом). При составлении элементарных конъюнкций используют следующее правило: если некоторый аргумент принимает на наборе значение равное нулю, то в элементарную конъюнкцию он входит с отрицанием, а если его значение равно единице, то без отрицания. Сложив минтермы, дающие единичное значение функции, получим ДНФ, после упрощения (минимизации) которой мы можем получить исходное выражение функции. Для минимизации функций, содержащих большое количество переменных, мы предлагаем ознакомить студентов с методом Квайна [8], достаточно несложным и интересным в применении.

В качестве контрольных заданий по данной главе мы предлагаем студентам провести полное исследование какой-либо из предложенных преподавателем функций: минимизировать аналитически заданную функцию и проверить правильность результата минимизации с помощью таблицы истинности. Записать по таблице ДНФ и минимизировать ее методом Квайна.

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

Библиографический список

1. Мельников, О. И. Обучение дискретной математике / О. И. Мельников. - М. : Изд-во ЛКИ, 2008. - 224 с. - КВК 987-

5-382-00426-6.

2. Зепнова, Н. Н. Основы теории множеств для студентов втуза / Н. Н. Зепнова // Педагогика и жизнь : междунар. сб. науч. тр. ; под ред. проф. О. И. Кирикова. — Вып. 8. — Воронеж : ВГПУ, 2008. - 319 с. - ІББК 987-5-88519-456-3. - С. 199-208.

3. Кузьмин, О. В. Перечислительная комбинаторика : учеб. пособие / О. В. Кузьмин. — М. : Дрофа, 2005. — 110 с. — КБК 57107-8636-5.

4. Палий, И. А. Дискретная математика : курс лекций / И. А. Палий. - М. : Эксмо, 2008. - 325 с. - КБК 978-5-699-27101-6.

5. Г орбатов, В. А. Дискретная математика : учеб. для студентов втузов / В. А. Горбатов, А. В. Горбатов, А. В. Горбатова. - М. : ООО «Изд-во АСТ»: - ООО «Изд-во Астрель», 2003. - 447 с. -КБК 5-17-019257-6 (ООО «Изд-во АСТ»). - КБК 5-271-06991-5 (ООО «Издательство Астрель»).

6. Колмогоров, А. Н. Элементы теории функций и функционального анализа : учеб. для вузов / А. Н. Колмогоров, С. В. Фомин. -

6-е изд., испр. - М. : Наука. - Гл. ред. физ.-мат. лит., 1989. - 624 с. -ІББК 5-02-013993-9.

7. Судоплатов, С. В. Элементы дискретной математики : учебник / С. В. Судоплатов, Е. В. Овчинникова. - М. : ИНФРА-М, Новосибирск : Изд-во НГТУ, 2002. - 280 с. - ІББК 5-16-000957-4 (ИНФРА-М), КБК 5-7782-0332-2 (НГТУ).

8. Шевелев, Ю. П. Высшая математика 5. Дискретная математика. Ч. 1: Теория множеств. Булева алгебра (для автоматизированной системы обучения) : учеб. пособие / Ю. П. Шевелев. -Томск : Том. гос. ун-т систем управления и радиоэлектроники, 1998. - 114 с. - ІББК 5-8688-0639-2 (Ч.1). КБК 5-8688-9040-Х.

ЗЕПНОВА Наталья Николаевна, кандидат педагогических наук, доцент кафедры математики Научноисследовательского Иркутского государственного технического университета.

КУЗЬМИН Олег Викторович, доктор физико-математических наук, профессор (Россия), заведующий кафедрой теории вероятностей и дискретной математики Иркутского государственного университета. Адрес для переписки: e-mail: zepnova_nat@mail.ru

Статья поступила в редакцию 01.12.2010 г.

© Н. Н. Зепнова, О. В. Кузьмин

Книжная полка

Исакова, Л. Д. Перевод профессионально ориентированных текстов на немецком языке : учебник / Л. Д. Исакова. - М. : Флинта, 2009. - 96 с. - ISBN 978-5-9765-0714-2.

Настоящий учебник составлен в соответствии с учебными программами по специальности «Теория и методика преподавания иностранных языков и культур», квалификация «Лингвист, преподаватель». Цель учебника — научить студентов осуществлять адекватный письменный перевод профессионально ориентированных текстов по лингвистике, методике преподавания иностранного языка и психологии. Учебник написан на немецком языке. Он включает 13 уроков, рассчитанных на 40 часов аудиторных практических занятий. Урок состоит из теоретического материала по определенной теме аспекта перевода с иностранного языка на русский и аспекта языковых особенностей научного стиля, списка специальных терминов по указанной специальности, предтекстовых упражнений, текста для перевода, послетекстовых упражнений. Учебным материалом для перевода послужили оригинальные научные тексты на немецком языке. В конце учебника приведены дополнительные тексты для перевода и терминологический словарь. Для студентов-лингвистов, изучающих немецкий язык.

ОМСКИЙ НАУЧНЫЙ ВЕСТНИК №1 (95) 2011 МЕТОДИКА ПРЕПОДАВАНИЯ