Федеральное агентство по образованию
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
Бийский технологический институт (филиал)
государственного образовательного учреждения
высшего профессионального образования
«Алтайский государственный технический университет
им. И.И. Ползунова»
Т.М. Тушкина, В.С. Фролов, О.Д. Ростова, Л.П. Кувшинова
МАТЕМАТИЧЕСКАЯ ЛОГИКА
И ТЕОРИЯ АЛГОРИТМОВ
Методические рекомендации по изучению дисциплины для студентов специальностей 080801 «Прикладная информатика в экономике», 230201 «Информационные системы и технологии»
Бийск
Издательство Алтайского государственного технического университета
им. И.И. Ползунова
2010
УДК 519.1
Рецензент: к.т.н., доцент кафедры МСИиА БТИ АлтГТУ
Гареева Р.Г.
Тушкина, Т.М.
Математическая логика и теория алгоритмов: методические рекомендации по изучению дисциплины для студентов специальностей 080801 «Прикладная информатика в экономике», 230201 «Информационные системы и технологии» / Т.М. Тушкина, В.С. Фролов, О.Д. Ростова, Л.П. Кувшинова; Алт. гос. техн. ун-т, БТИ. – Бийск: Изд-во Алт. гос. техн. ун-та, 2010. – 16 с.
Данная методическая разработка является составной частью учебно-методического комплекса по дисциплине «Математическая логика и теория алгоритмов» для студентов специальностей 080801 «Прикладная информатика в экономике», 230201 «Информационные системы и технологии» и представляет собой совокупность рекомендаций и разъяснений, позволяющих студенту оптимальным образом организовать процесс изучения курса «Математическая логика и теория алгоритмов». В методических рекомендациях сформулированы цели и задачи курса, приведена структура курса и конкретизированы отдельные модули, составляющие курс. Даны рекомендации по работе с литературой, по подготовке к лекциям и практическим занятиям, по выполнению индивидуальных домашних заданий и подготовке к зачету.
УДК 519.1
Рассмотрено и одобрено на заседании
кафедры высшей математики
и
математической физики.
Протокол № 3 от 03.07.2009 г.
© Т.М. Тушкина, В.С. Фролов,
О.Д. Ростова, Л.П. Кувшинова, 2010
© БТИ АлтГТУ, 2010
СОДЕРЖАНИЕ
1 ОСОБЕННОСТИ КУРСА………………………………………………..4
2 МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО ИЗУЧЕНИЮ
ДИСЦИПЛИНЫ……………………………………………………………9
2.1 Лекции и практические занятия…………………………………..9
2.2 Чтение учебника и конспекта лекций…………………………...10
2.3 Решение задач…………………………………………………….10
2.4 Самопроверка……………………………………………………..13
2.5 Выполнение индивидуальных заданий……………………….....13
2.6 Зачет……………………………………………………………….13
РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА…………………………………...14
1 ОСОБЕННОСТИ КУРСА
Развитие экономики любого государства основано на применении новейших, в том числе информационно-компьютерных технологий. Разработка таких средств требует развитого логического и абстрактного мышления, формированием которых и занимается математическая логика. Эта наука развивалась в связи с изучением законов человеческого мышления, что впоследствии обусловило ее применение в областях, которые связаны с моделированием мышления – кибернетикой и программированием. Изучение математической логики способствует лучшему пониманию строения математических теорий, сущности и структуры математических доказательств, логики ЭВМ.
Математическая логика представляет собой обширный и разветвленный раздел математики и изучает способы формального представления высказываний, построения новых высказываний из имеющихся, а также способы установления истинности или ложности высказываний.
Курс «Математическая логика и теория алгоритмов» входит в число дисциплин, включенных в учебный план специальностей 080801 «Прикладная информатика в экономике» и 230201 «Информационные системы и технологии» в соответствии с ГОС ВПО.
Целью дисциплины является овладение студентами аппаратом математической логики и теории алгоритмов для решения различных задач, связанных с их профессиональной деятельностью. Более подробно цели курса «Математическая логика и теория алгоритмов» представлены в таблице 1.
Таблица 1 – Цели курса «Математическая логика и теория
алгоритмов»
| Содержание цели |
|
| Студент будет иметь представление:
|
|
| 1 О предмете математической логики |
|
| 2 О предмете теории алгоритмов |
|
| 3 О месте и роли математической логики в системе математических наук |
|
| Студент будет знать:
|
Студент будет уметь:
|
| 4 Основные понятия логики высказываний: высказывание, операции над высказываниями, формула логики высказываний, равносильные формулы логики |
8 Представлять логическими формулами сложные высказывания |
| 9 Производить корректные преобразования логических формул |
|
Продолжение таблицы 1
| высказываний, законы логики, нормальные формы формул, совершенные нормальные формы (СДНФ, СКНФ), булева функция, полная система булевых функций, базис, аксиома исчисления высказываний, вывод в исчислении высказываний, резолютивный вывод |
10 Задавать булевы функции различными способами |
| 11 Доказывать равносильность формул логики высказываний различными способами |
|
| 12 Исследовать логическую формулу на общезначимость средствами алгебры логики высказываний и исчисления высказываний |
|
| 13 Устанавливать правильность схемы рассуждения |
|
| 14 Упрощать контактные схемы |
|
| 5 Основные понятия логики предикатов: предикат, область истинности предиката, выполнимый предикат, тождественно истинный и тождественно ложный предикаты, кванторы общности и существования, формула логики предикатов, равносильные формулы логики предикатов, префиксная нормальная форма, метод резолюций в исчислении предикатов |
15 Записывать математические утверждения с помощью логической символики |
| 16 Задавать предикаты различными способами |
|
| 17 Доказывать равносильность формул логики предикатов |
|
| 18 Исследовать формулу логики предикатов на общезначимость средствами исчисления предикатов |
|
| 19 Доказывать истинность предикатов, заданных на множестве натуральных чисел, с помощью метода математической индукции |
|
| 6 Основные понятия теории алгоритмов: интуитивное понятие алгоритма, эффективная вычислимость, оператор суперпозиции, оператор примитивной рекурсии, оператор минимизации, машина Тьюринга, программа машины Тьюринга, неразрешимая алгоритмическая проблема |
20 Доказывать принадлежность функции классу рекурсивных функций |
| 21 Применять машину Тьюринга к заданной начальной конфигурации |
|
| 7 Соответствие между интуитивным понятием алгоритма, рекурсивной функцией и машиной Тьюринга |
22 Строить машину Тьюринга, вычисляющую заданную функцию |
Для изучения дисциплины «Математическая логика и теория алгоритмов» требуется, чтобы студент владел базовыми понятиями теории множеств (множество, подмножество, отношение, функция и др.).
Курс «Математическая логика и теория алгоритмов» является базовым для многих дисциплин, изучаемых в дальнейшем студентами специальностей «Прикладная информатика в экономике» и «Информационные системы и технологии». В частности, сказанное относится к другой математической дисциплине, дискретной математике.
Кроме того, успешное овладение методами математической логики и теории алгоритмов снимает трудности вхождения студентов специальности «Информационные системы и технологии» в такие общепрофессиональные и специальные дисциплины, как «Теория информационных процессов и систем», «Управление данными», «Моделирование систем», «Основы теории управления», «Алгоритмы и методы переработки информации», а студентов специальности «Прикладная инофрматика в экономике» – «Методы оптимального управления», «Информационный менеджмент», «Моделирование информационных процессов», «Проектирование информационных систем» и др. В этой связи будущие специалисты должны владеть дискретными методами формализованного представления информации. Речь идет о методах, основанных на логических представлениях.
Изучение математической логики студентами данных специальностей осуществляется во втором семестре. Основными разделами математической логики являются: логика высказываний, логика предикатов, теория алгоритмов. Структура курса «Математическая логика и теория алгоритмов» представлена на рисунке 1.
Выделяются три модуля, тесно связанные друг с другом. В двух первых модулях изучаются логические представления –
описание исследуемой системы, процесса, явления в виде совокупности сложных высказываний, составленных из простых (элементарных) высказываний и логических связок между ними. Логические представления и их составляющие характеризуются определенными свойствами и набором допустимых преобразований над ними (операций, правил вывода и т.п.), реализующих разработанные в формальной логике правильные методы рассуждений – законы логики.
Модуль 1 – Логика высказываний.
Логика высказываний является фундаментом математической логики. Основным объектом рассмотрения в ней является высказывание. Все научные знания (законы и явления физики, химии, биологии и др., математические теоремы), события повседневной жизни, ситуации, возникающие в экономике и процессах управления, формулируются в виде высказываний, относительно которых мы должны знать, истинны они или ложны, т.е. знать их истинностные значения.
Модуль 2 – Логика предикатов.
Логика предикатов представляет собой разитие логики высказываний. С помощью формул логики высказываний можно описать и исследовать структуру сложных высказываний, установить их истинность или ложность в зависимости от истинности или ложности входящих в них простых высказываний. Понятие предиката используется для описания внутренней логической структуры простых высказываний, не содержащих связок. С помощью логических связок предикаты могут объединяться в разнообразные логические формулы. Исследование предикатных формул и способов установления их истинности является основным предметом логики предикатов. Логика предикатов вместе с входящей в нее логикой высказываний является основой логического языка математики. С ее помощью удается формализовать и точно исследовать основные методы построения математических теорий. В этой связи логика предикатов является важным средством построения развитых логических языков и формальных систем.
Для построения логики высказываний и логики предикатов существует два подхода (языка), образующих два варианта формальной логики: алгебру логики
и логические исчисления
(рисунок 2). Между основными понятиями этих языков существует взнаимно однозначное соответствие. Оно обеспечивается в конечном итоге единством законов логики, лежащих в основе допустимых преобразований.
Модуль 3
– Теория алгоритмов.
Основным объектом рассмотрения является алгоритм. Теория алгоритмов не учит «составлять» алгоритмы. Основная задача классической теории алгоритмов – это ответ на вопрос: «Можно ли вообще для задач данного типа построить алгоритм?». Это связано с тем, что, во-первых, не для всех задач возможно создать алгоритмы их решения. Во-вторых, чтобы сделать математически строгий вывод о невозможности построить алгоритм, нужно иметь строгое (формальное) определение самого алгоритма. Но понятие алгоритма относится к основным неопределяемым понятиям (понимать понимаем, а сказать не можем). Поэтому его заменили строго формализованными математическими моделями. Среди них самыми известными являются рекурсивные функции и машины Тьюринга (рисунок 3). Эти математические модели, выступающие в роли «конкретизаций» понятия алгоритма, изучаются в третьем модуле курса.
Курс «Математическая логика и теория алгоритмов» имеет практическую часть (практические занятия – 17 часов), на самостоятельную работу студентов специальности «Прикладная информатика в экономике» отводится 51 час, специальности «Информационные системы и технологии» – 34 часа.
Итоговая аттестация знаний студентов по дисциплине «Математическая логика и теория алгоритмов» осуществляется во время зачета по завершению семестра.
2 МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО ИЗУЧЕНИЮ ДИСЦИПЛИНЫ
Учебным планом по дисциплине «Математическая логика и теория алгоритмов» для студентов предусмотрено участие в лекциях, практических занятиях. В течение семестра студентам предлагае
2.1
Лекции и практические занятия
Основной составной частью учебного процесса в преподавании дисциплины «Математическая логика и теория алгоритмов» студентам дневной формы обучения являются лекции и практические занятия. Очевидно, что студенты, активно участвующие в этих занятиях, способны успешнее освоить предмет.
Все лекции студентам необходимо конспектировать. В конспект рекомендуется выписывать определения, формулировки и доказательства теорем, формулы и т.п. На полях конспекта следует помечать вопросы, выделенные студентом для консультации с преподавателем. Выводы, полученные в виде формул, а также алгоритмы решения тех или иных классов задач дискретной математики рекомендуется в конспекте подчеркивать или обводить рамкой, чтобы при перечитывании конспекта они выделялись и лучше запоминались. Полезно составить краткий справочник, содержащий определения важнейших понятий и наиболее часто употребляемые формулы дисциплины. К каждой лекции следует разобрать материал предыдущей лекции. Ряд вопросов дисциплины вынесен на самостоятельное изучение. Такое задание требует оперативного выполнения. В конспекте лекций необходимо оставить место для освещения упомянутых вопросов.
На практических занятиях подробно рассматриваются основные вопросы дисциплины, разбираются основные типы задач. К каждому практическому занятию следует заранее самостоятельно выполнить домашнее задание и выучить лекционный материал к следующей теме. Систематическое выполнение домашних заданий обязательно и является важным фактором, способствующим успешному усвоению дисциплины.
2.2 Чтение учебника и конспекта лекций
В настоящее время имеется достаточно большое количество литературы по математической логике и теории алгоритмов. Поскольку в данном случае курс предназначен специалистам в области информационных технологий, в первую очередь, можно порекомендовать учебные пособия [1-4], а также [7, 8].
Изучая материал по учебнику или конспекту лекций, следует переходить к следующему вопросу только в том случае, когда хорошо усвоен предыдущий вопрос. При этом необходимо воспроизводить на бумаге все рассуждения, как имеющиеся, так и пропущенные в силу их простоты.
Особое внимание следует обращать на определение основных понятий дисциплины. Студент должен подробно разбирать примеры, которые поясняют понятия, и уметь строить аналогичные примеры самостоятельно. Это является одним из важных условий усвоения дисциплины.
2.3 Решение задач
Умение студентов решать задачи по математической логике и теории алгоритмов является залогом успешного усвоения дисциплин информационного блока. Однако в процессе изучения математической логики студенты сталкиваются с рядом трудностей.
Первая из них состоит в том, что студенту, начинающему изучать алгебру логики, не до конца понятен смысл применения логической связки «импликация», с помощью которой из двух исходных высказываний (посылки и следствия) получается высказывание, ложное только в том случае, когда посылка истинна, а следствие ложно. При обсуждении импликации рассмотрим следующий пример. Даны простые высказывания: «данный четырехугольник
– квадрат»
(А
) и «около данного четырехугольника можно описать окружность»
(В
) и составное высказывание, понимаемое как «если данный четырехугольник квадрат, то около него можно описать окружность».
Существуют три набора значений высказываний А
и В
, при которых высказывание истинно:
а) А
истинно и В
истинно, то есть данный четырехугольник квадрат, и около него можно описать окружность;
б) А
ложно и В
истинно, то есть данный четырехугольник не является квадратом, но около него можно описать окружность (разумеется, это справедливо не для всякого четырехугольника);
в) A
ложно и B
ложно, то есть данный четырехугольник не является квадратом, и около него нельзя описать окружность.
Ложен только один вариант, когда А
истинно, а В
ложно, то есть данный четырехугольник является квадратом, но около него нельзя описать окружность.
В обычной речи связка «если ..., то»
описывает причинно-следственную связь между высказываниями. Но в логических операциях смысл высказываний не учитывается. Рассматривается только их истинность или ложность. Поэтому не следует смущаться «бессмысленностью» импликаций, образованных высказываниями, совершенно не связанными по содержанию. Например, таким истинным высказыванием, как «если 2∙2=5, то Москва является столицей России». С точки зрения обыденной логики такая ситуация целиком абсурдна, но это мнение возникает в силу того, что человеческий разум пытается, в первую очередь, придать импликации смысл причинной логической связи, т.е. подразумевается, что заключение может быть выведено из посылки на основании каких-то логических рассуждений.
Абсолютная чужеродность посылки и заключения оставляет лишь одну возможность – руководствоваться формальным определением импликации. Можно также сказать, что формальное определение импликации гораздо ближе искусственному интеллекту, чем традиционному мышлению человека, поскольку импликация может быть реализована в операторах условного перехода в программировании, а также в некоторых компьютерных микросхемах. Тем удивительнее тот факт, что еще в глубокой древности Аристотель уже знал, что импликация истинна в трех из четырех случаев.
Алгебра высказываний позволяет научиться моделировать простейшие мыслительные процессы. Одним из самых интересных ее приложений является применение к решению логических задач. Логические задачи весьма разнообразны, способов их решения также немало. Но наибольшее распространение получили следующие три способа решения логических задач:
а) средствами алгебры логики;
б) табличный;
в) с помощью рассуждений.
Решение логических задач средствами алгебры логики происходит следующим образом:
а) изучается условие задачи;
б) вводится система обозначений для логических высказываний;
в) конструируется логическая формула, описывающая логические связи между всеми высказываниями условия задачи;
г) определяются значения истинности этой логической формулы;
д) из полученных значений истинности формулы определяются значения истинности введенных логических высказываний, на основании которых делается заключение о решении.
При использовании табличного способа решения логических задач условия, которые они содержат, и результаты рассуждений фиксируются с помощью специально составленных таблиц.
Всегда, когда в процессе решения задачи требуется проводить равносильные преобразования логической формулы, студенты, как правило, сталкиваются с другой трудностью. Суть ее такова. Некоторые преобразования логических формул похожи на преобразования формул в обычной алгебре (вынесение общего множителя за скобки, использование переместительного и сочетательного законов и т.п.), тогда как другие преобразования основаны на свойствах, которыми не обладают операции обычной алгебры (использование распределительного закона для конъюнкции, законов поглощения, склеивания, де Мор-гана и др.). Т.е. полного сходства логических операций (конъюнкция и дизъюнкция) с числовыми (умножение и сложение) нет. Кроме того, законы двойственности говорят от том, что логические сложение и умножение являются «перевертышами»: отрицание результата логического умножения А и В совпадает с результатом логического сложения отрицаний А и В, и наоборот. Таким образом, при упрощении логических формул не всегда очевидно, какой из законов алгебры логики следует применить на том или ином шаге. Навыки приходят с опытом.
Чтобы справиться с этими трудностями, нужно решить достаточно много задач [5, 6, 10], что даст возможность глубже понять основные положения разделов изучаемой дисциплины, научиться применять их при анализе конкретной ситуации. В этой связи типовые задачи, рассмотренные в рекомендуемых учебных пособиях, следует разобрать внимательно, обращаясь при необходимости к соответствующим указаниям, подробным решениям или ответам. Задачи должны быть использованы в процессе работы над курсом и затем при подготовке к экзамену. При этом непременным условием является глубокое усвоение соответствующего материала по конспекту лекций или учебнику.
2.4 Самопроверка
После изучения определенной темы и решения достаточного количества соответствующих задач студенту рекомендуется воспроизвести по памяти определения, выводы формул, формулировки и доказательства теорем, проверяя себя каждый раз по учебнику или конспекту лекций. Контрольные вопросы, приводимые в конспекте лекций по дисциплине, имеют цель помочь студенту в таком повторении, закреплении и проверке прочности усвоения изученного материала.
Часто недостаточность усвоения того или иного вопроса выясняется только при изучении дальнейшего материала. В этом случае надо повторить плохо изученный раздел, внимательно разобрав материал учебника, а также прорешать задачи.
2.5 Выполнение
индивидуальных заданий
В процессе изучения дисциплины «Математическая логика и теория алгоритмов» студенту предлагается выполнить индивидуальные домашние задания [9] по пяти темам дисциплины: составление таблиц истинности логических формул, нахождение СДН и СКН логической функции, минимизация в классе ДНФ и КНФ, полные системы булевых функций, предикаты. Не следует приступать к решению задания до решения достаточного количества задач по материалу, соответствующему этому заданию. Опыт показывает, что чаще всего неумение решить ту или иную задачу вызывается тем, что у студента отсутствует необходимая практика в решении задач.
Указанные задания должны выполняться самостоятельно. В противном случае студент не приобретает необходимых знаний и может оказаться неподготовленным к их защите, а в конечном итоге к тестированию и к зачету.
Кроме того, по желанию студенты могут повысить свой итоговый рейтинг с помощью успешного выполнения индивидуальных заданий повышенной степени сложности. Список заданий предоставляется преподавателем, ведущим дисциплину.
2.6
Зачет
На зачете, прежде всего, выясняется отчетливое усвоение теоретических и прикладных вопросов программы и умение применять полученные знания к решению практических задач. Зачет проводится по билетам. Каждый билет имеет теоретическую (один вопрос) и практическую (три задачи) составляющие. Определения и алгоритмы решения задач должны формулироваться точно и подкрепляться примерами. Студент должен уметь объяснить как выбор схемы решения задачи, так и все его этапы.
РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА
Основная литература
1. Хаггарти, Р. Дискретная математика для программистов / Р. Хаг-гарти. – М.: Техносфера, 2005.
2. Новиков, Ф.А. Дискретная математика для программистов / Ф.А. Новиков. – СПб.: Питер, 2001.
3. Нефедов, В.Н. Курс дискретной математики: учеб. пособие / В.Н. Нефедов, В.А. Осипова. – М.: Изд-во МАИ, 1992.
4. Яблонский, С.В. Введение в дискретную математику: учебное пособие для вузов / под ред. В.А. Садовничего. – 3-е изд., стер. / С.В. Яблонский. – М.: Высшая школа, 2002.
5. Лавров, И.А. Задачи по теории множеств, математической логике и теории алгоритмов / И.А. Лавров, Л.Л. Максимова. – Изд. 4-е. – М.: ФИЗМАТЛИТ, 2001.
6. Москинова, Г.И. Дискретная математика. Математика для менеджера в примерах и упражнениях: учеб. пособие / Г.И. Москинова. – М.: Логос, 2000.
Дополнительная литература
7. Судоплатов, С.В. Дискретная математика: учебное пособие / С.В. Судоплатов, Е.В. Овчинникова. – М.: Инфра-М, 2007.
8. Романовский, И.В. Дискретный анализ / И.В. Романовский. – 2-е. изд. – СПб.: Невский диалект, 2000.
Перечень пособий, методических указаний и материалов, используемых в учебном процессе
9. Ростова, О.Д.
Дискретная математика: методические рекомендации к типовому расчету по математике с вариантами заданий для студентов специальностей 071900, 351400, 170600, 171200 / О.Д. Ростова, Т.М. Тушкина, В.С. Фролов; Алт. гос. техн. ун-т, БТИ. – Бийск: Изд-во Алт. гос. техн. ун-та, 2005.
10. Тушкина, Т.М. Математическая логика и теория алгоритмов: методические рекомендации по проведению практических занятий для студентов специальностей 080801 «Прикладная информатика в экономике», 230201 «Информационные системы и технологии» / Т.М. Тушкина, В.С. Фролов, О.Д. Ростова, Л.П. Кувшинова; Алт. гос. техн. ун-т, БТИ. – Бийск: Изд-во Алт. гос. техн. ун-та, 2010.
11. Тушкина, Т.М. Математическая логика и теория алгоритмов: методические рекомендации по самостоятельной работе студентов специальностей 080801 «Прикладная информатика в экономике», 230201 «Информационные системы и технологии» / Т.М. Тушкина, В.С. Фролов, О.Д. Ростова, Л.П. Кувшинова; Алт. гос. техн. ун-т, БТИ. – Бийск: Изд-во Алт. гос. техн. ун-та, 2010.
Учебное издание
ТУШКИНА
Татьяна Михайловна
ФРОЛОВ
Виктор Савельевич
РОСТОВА
Ольга Дмитриевна
КУВШИНОВА
Лидия Павловна
МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ
Методические рекомендации по изучению дисциплины для студентов специальностей 080801 «Прикладная информатика в экономике»,
230201 «Информационные системы и технологии»
Редактор Идт Л.И.
Технический редактор Сазонова В.П.
Подписано в печать 26.02.2010. Формат 60´84 1/16
Усл. п. л. - 0,93. Уч.-изд. л. - 1,00
Печать - ризография, множительно-копировальный
аппарат «RISO EZ300»
Тираж 50 экз. Заказ 2010-34
Издательство Алтайского государственного
технического университета
656038, г. Барнаул, пр-т Ленина, 46
Оригинал-макет подготовлен ИИО БТИ АлтГТУ
Отпечатано в ИИО БТИ АлтГТУ
659305, г. Бийск, ул. Трофимова, 27