Методические рекомендации по изучению дисциплины для студентов специальностей 080801 «Прикладная информатика в экономике», 230201 «Информационные системы и технологии» Бийск (стр. 1 из 3)
Федеральное агентство по образованию
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
Бийский технологический институт (филиал)
государственного образовательного учреждения
высшего профессионального образования
«Алтайский государственный технический университет
им. И.И. Ползунова»
Т.М. Тушкина, В.С. Фролов, О.Д. Ростова, Л.П. Кувшинова
МАТЕМАТИЧЕСКАЯ ЛОГИКА
И ТЕОРИЯ АЛГОРИТМОВ
Методические рекомендации по изучению дисциплины для студентов специальностей 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.Выделяются три модуля, тесно связанные друг с другом. В двух первых модулях изучаются логические представления – описание исследуемой системы, процесса, явления в виде совокупности сложных высказываний, составленных из простых (элементарных) высказываний и логических связок между ними. Логические представления и их составляющие характеризуются определенными свойствами и набором допустимых преобразований над ними (операций, правил вывода и т.п.), реализующих разработанные в формальной логике правильные методы рассуждений – законы логики.