МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ
УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«Пермский государственный педагогический университет»
Математический факультет
Кафедра высшей математики
Пастухова Г.В.
Учебно-методический комплекс дисциплины
МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ
050100 – Педагогическое образование
Профиль подготовки – Информатика и ИКТ
Квалификаций (степень) выпускника
Бакалавр педагогического образования
Форма обучения очная
Пермь, 2012
1. Цель дисциплины.
В дисциплину «Математическая логика и теория алгоритмов» вошли и одна из древнейших математических наук – логика (первое дошедшее до нас сочинение «Аналитики» Аристотеля (382-322 гг. до н.э.) принадлежит позднегреческой эпохе) и совсем юная по меркам истории – теория алгоритмов, которая не насчитывает и ста лет. Обе эти науки, не смотря на столь значительную разницу в возрасте, имеют много общего – они обосновывают саму математику, ее строение и особенности формализаций различных математических систем.
Программа дисциплины отражает цель курса – знакомство с формализацией математического языка, которая рассматривается в данном курсе значительно глубже, чем в курсах алгебры, геометрии и математического анализа, и охватывает также логические средства. В рамках этого курса изучается, прежде всего, язык логики, освещаются современные подходы к формализации и аксиоматизации различных математических дисциплин, в частности затрагиваются такие фундаментальные понятия, как понятие непротиворечивости и полноты математической теории, независимости системы аксиом.
Дисциплина включает в себя два основных раздела: «Математическая логика» и «Теория алгоритмов». В вводном разделе программы рассматриваются основные этапы становления математической логики как особой математической дисциплины, освещается ее роль в решении проблем обоснования математики, в развитии современной вычислительной техники.
Раздел «Математическая логика» в свою очередь состоит из подразделов «Алгебра высказываний», которая изучает высказывания, формулы, их истинностные значения, тождественно ложные, истинны и выполнимые формулы, равносильность формул, приведение формул с помощью равносильных преобразований к нормальным формам. Овладение техникой алгебры высказываний позволить студентам решать алгебраическим методом логические задачи, в частности проверять правильность некоторых рассуждений, а также составлять и упрощать релейно-контактные схемы с заданными условиями работы.
Пример формальной аксиоматической системы рассматривается в разделе «Исчисление высказываний». Особое внимание в этом разделе следует уделить доказательству выводимости в построенном исчислении формул (теорем).
Далее вводится понятие предиката, определяются операции навешивания кванторов общности и существования, обобщаются понятия формулы и ее интерпретации. Возможности языка алгебры предикатов иллюстрируются разнообразными примерами при рассмотрении арифметической и геометрической моделей.
Формализованное исчисление предикатов рассматривается как расширение исчисления высказываний.
Все вышеуказанные подразделы (алгебры и исчисления высказываний и предикатов) являются примерами построения той или иной формализованной системы. Принципы построения и характеристики (полнота, разрешимость, противоречивость) составляющие метатеорию формальных систем подытоживают данный раздел. Также даются примеры и понятия неклассических видов логики как нечеткая и алгоритмическая и принципы логического программирования.
Второй раздел «Теория алгоритмов» является теоретической основой программирования и посвящен формализации понятия «алгоритма» в виде машин Тьюринга и рекурсивных функций. Начинается раздел с изучения возникшей потребности в строгом определении «алгоритма». Далее рассматривается интуитивное понятия «алгоритма», приводятся примеры.
Подраздел «Рекурсивные функции» посвящен базовым функциям и операциям, формируется понятие и примеры частично-рекурсивных, рекурсивных и общерекурсивных функций, доказывается рекурсивность основных арифметических функций, формулируется тезис Черча. Также даются понятия алгоритмически неразрешимых, легкоразрешимых и трудноразрешимых задач и оценки (меры) сложности алгоритмов.
Аналогично строится формализация понятия алгоритма в виде машин Тьюринга, рассматривается ее устройство, действия над машинами, связь с рекурсивными функциями, финалом является тезис Тьюринга, проводиться аналогия с тезисом Черча.
2. Место дисциплины в структуре ООП:
Дисциплина «Математическая логика и теория алгоритмов» относится к вариативной части профессионального цикла.
Для освоения дисциплины «Математическая логика и теория алгоритмов» используются знания, умения и виды деятельности, сформированные в ходе изучения дисциплин: «Алгебра», «Геометрия», «Математический анализ», «Теория функций действительного переменного», «Теория чисел», «Информатика».
Дисциплина «Математическая логика и теория алгоритмов» является логической основой понимания сущности доказательств и их логического строения, изучения аксиоматических математических теорий из разных областей математики, а также теоретическим обоснованием логической составляющей обучения математике. Алгоритмический подход позволяет изучать математические теории в целом.
3. Требования к результатам освоения этой дисциплины
Процесс изучения дисциплины направлен на формирование следующих специальных компетенций СК-1, СК-2, СК-3.
| № | Общая формулировка | Детализация |
| СК-1 | Овладение содержанием фундаментальных математических дисциплин (овладение основными понятиями, идеями и принципами, освоение методов фундаментальных математических теорий) | - владеет основными понятиями алгебры высказываний (АВ) и предикатов, исчисления высказываний (ИВ) и предикатов (ИП) (высказывания, действия над высказываниями (конъюнкция, дизъюнкция, импликация, эквивалентность), таблицы истинности, формулы АВ, равносильных формул, ДНФ, СДНФ, КНФ, СКНФ; аксиомы и их свойств (полнота, независимость) исчисления, правила вывода из аксиом, теорема дедукции, выводимой формулы, связь АВ и ИВ, свойства ИВ (непротиворечивость, полнота); предиката, квантора, нормальных форм и формул; формул ИП, аксиомы и их свойства ИП, выводимые формулы, теорема дедукции, свойства ИП (непротиворечивость, полнота; алгоритма, вычислимой функции, машины Тьюринга, действии над машинами, тезис Черча, тезис Тьюринга, рекурсивной функции (частично рекурсивной и примитивно рекурсивной)); - имеет навык равносильных преобразований формул АВ, применения АВ для решения текстовых задач и анализа РКС, доказательства выводимости в построенном исчислении формул (теорем); -способен уточнить понятие «алгоритма» с помощью рекурсивных функций и машин Тьюринга; -имеет навык построения машин Тьюринга для решения задач и действиями над ними; - умет доказывать рекурсивность основных функций. |
| СК-2 | Овладение методом математического моделирования (способность к построению математических моделей, выбору и применению соответствующему модели математического метода решения задачи и интерпретации результатов) | - владеет аксиоматическим методом построения математических дисциплин на примерах ИВ и ИП; - готов исследовать различные системы на такие характеристики как полнота, непротиворечивость, разрешимость; - способен показать алгоритмическую неразрешимость проблемы останова, самоприменимости и др. |
| СК-3 | Понимание методологической и историко-культурной функций математики | - способен применить аксиоматический метод к анализу произвольной математической теории; - имеет навык применения языка логики предикатов к анализу математических текстов (запись определения, предложения, теоремы) и построения противоположных. обратных утверждений данному и применять доказательство от противного; - знает методику формулирования необходимых и достаточных условий; - владеет навыком преобразований высказываний для анализа релейно-контактных схем и решения текстовых задач. |
В результате изучения дисциплины студент должен
знать:
- этапы становления математической логики как особой математической дисциплины, начиная с логики Аристотеля; ее роль в развитии современной вычислительной техники;
- способы формализации систем и понятия «алгоритма»
- законы логической равносильности;
- компоненты (аксиомы и правила вывода) и характеристики (свойства) исчисления высказываний и исчисления предикатов;
- методы математической логики для изучения математических доказательств и теорий;
- различные определения понятия алгоритма;
- формулировку алгоритмически неразрешимых проблем;
- знать аксиоматический метод построения класса вычислимых функций;
уметь:
- распознавать тождественно истинные формулы алгебры высказываний и логики предикатов;
- применять средства языка логики предикатов для записи и анализа математических предложений;
- строить простейшие выводы в исчислении высказываний и исчислении предикатов, использовать эти модели для объяснений строения математических доказательств;
- строить машины Тьюринга для решения простых алгоритмических задач;
- доказывать вычислимость простейших функций в теории алгоритмов;
владеть:
- техникой равносильных преобразований логических формул;
- методами распознавания тождественно истинных и равносильных формул;
- дедуктивным аппаратом изучаемых логических исчислений;
- алгоритмом нумерации кортежей;
- алгоритмом разложения вычислимых функций в простейшие;
- способами получения из основных рекурсивных функций доказательств рекурсивности (примитивной, общерекурсивной и частичной) функций.
приобрести навыки:
- находить совершенные формы; проверять правильность рассуждений;
- выполнять упрощения формул алгебры высказываний с помощью основных равносильностей и построения таблиц истинности;
- составлять и упрощать комбинационные схемы с заданными условиями работы;
- доказывать выводимость формул исчисления высказываний;
- записывать в виде формул логики предикатов содержательные математические предложения;
- проверять формулы на общезначимость и выполнимость;
- доказывать рекурсивность той или иной функции, уметь строит из функций с помощью операций минимизации, постановки и рекурсии иные функции.