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

ПЕНЗЕНСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ

имени В. Г. БЕЛИНСКОГО

ПРИНЯТО УТВЕРЖДАЮ

на заседании Ученого совета Проректор по учебной работе

физико-математического факультета

Протокол заседания № 10

от « 18 » мая 2011 г.

Ю. А. Мазей Декан факультета _ О. П. Сурина «_» _ 2011 г.

РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ

Математическая логика и теория алгоритмов Направление подготовки 050100 Педагогическое образование Профиль подготовки Математика Квалификация (степень) выпускника – Бакалавр Форма обучения очная Пенза – 1. Цели освоения дисциплины «Математическая логика и теория алгоритмов»

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

Задачи изучаемой дисциплины:

Исходя из общих целей подготовки бакалавра педагогического образования по профилю «Математика»:

содействовать средствами дисциплины «Математическая логика и теория алгоритмов» развитию у студентов мотивации к педагогической деятельности, профессионального мышления, коммуникативной готовности, общей культуры;

научить студентов ясно, точно, грамотно излагать свои мысли в устной и письменной речи.

Исходя из конкретного содержания дисциплины:

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

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

2. Место дисциплины «Математическая логика и теория алгоритмов» в структуре ООП бакалавриата Дисциплина «Математическая логика и теория алгоритмов» относится к вариативной части профессионального цикла.

Для освоения дисциплины обучающиеся используют знания, умения, сформированные в ходе изучения дисциплин вариативной части профессионального цикла: «Алгебра», «Теория чисел», «Геометрия», «Математический анализ».

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

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

3. Компетенции обучающегося, формируемые в результате освоения дисциплины «Математическая логика и теория алгоритмов»

Процесс изучения дисциплины направлен на формирование элементов следующих компетенций в соответствии с ФГОС ВПО по данному направлению:

Структурные элементы компетенции Коды Наименование компетенции (в результате освоения дисциплины обучакомпетенции ющийся должен знать, уметь, владеть) 1 2 ОК-4 способен использовать зна- Знать: методы формализации для исследования о современной есте- ния условия поставленной задачи.

ственнонаучной картине Уметь: использовать логические методы исмира в образовательной и следования для построения и реализации профессиональной деятель- плана решения задачи.

ности, применять методы Владеть: навыками применения методов ломатематической обработки гической обработки информации при форинформации, теоретическо- мализации условия.

го и экспериментального исследования СК-1 владеет основными поло- Знать: принципы аксиоматического построжениями классических ения формализованного исчисления выскаразделов математической зываний, понятие вывода, свойства выводинауки, базовыми идеями и мости из гипотез, теорему о дедукции, её методами математики, си- применение, производные правила вывода, стемой основных матема- свойства формализованного исчисления вытических структур и аксио- сказываний.

матическим методом Уметь: использовать основные положения математической логики при решении задач.

Владеть: основными методами математической логики и теории алгоритмов.

СК-2 владеет культурой матема- Знать: законы логической равносильности;

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

основные методы математических рассуждений на Уметь: распознавать тождественно истинные основе общих методов (простейшие общезначимые) формулы языка научного исследования и логики высказываний (предикатов); применять опыта решения учебных и средства языка логики предикатов для записи научных проблем, пользо- и анализа математических предложений; строваться языком математики, ить простейшие выводы (в виде дерева) в искорректно выражать и ар- числениях высказываний и использовать эти гументировано обосновы- модели для объяснения сути и строения матевать имеющиеся знания матических доказательств.

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

рассуждений, их применимость в различных областях Уметь: использовать законы логики для прочеловеческой деятельности, верки правильности суждений, решении лороль и место математики в гических задач, построении доказательств системе наук, значение ма- математических утверждений.

тематической науки для Владеть: навыками использования логичерешения задач, возникаю- ских законов.

щих в теории и практике, общекультурное значение СК-4 владеет математикой как Знать: основные принципы построения моуниверсальным языком делей теорий и свойства моделей.

науки, средством модели- Уметь: строить примеры математических сов, способен пользоваться Владеть: навыками использования моделей построением математиче- при решении практических задач.

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

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

4. Структура и содержание дисциплины «Математическая логика и теория алгоритмов»

4.1. Структура дисциплины «Математическая логика и теория алгоритмов»

Общая трудоемкость дисциплины составляет 5 зачетных единиц, 180 часов.

Раздел 1. Алгебра высказываний Высказывания. Формулы алгебры высказываний.

Логическая равносильность формул. Нормальные формы.

Логическое следование формул. Приложение алгебры высказываний.

Применение алгебры высказываний к описанию релейно-контактных схем.

Раздел 2. Исчисление высказываний Построение исчисления высказываний.

Теорема дедукции и ее применение.

Свойства исчисления высказываний.

Раздел 3. Алгебра предикатов и исчисление предикатов Логические и кванторные операции над предикатами.

Формулы логики предикатов.

Приведенная форма и предваренная нормальная форма.

Проблема разрешения формул логики предикатов.

Применение логики предикатов.

Исчисление предикатов и его свойства.

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

Частично рекурсивные функции.

Рекурсивность нумерующих функций Кусочное задание функции.

Машины Тьюринга. Нормальные алгоритмы Маркова.

4.2. Содержание дисциплины «Математическая логика и теория алгоритмов»

Раздел 1. Алгебра высказываний Тема 1.1. Высказывания. Формулы алгебры высказываний.

Высказывания и операции над ними: отрицание, дизъюнкция, конъюнкция, импликация, эквивалентность высказываний. Формулы алгебры высказываний и их классификация:

выполнимые, опровержимые, тождественно-истинные, тождественно-ложные формулы.

Тема 1.2. Логическая равносильность формул. Нормальные формы.

Логическая равносильность формул алгебры высказываний: основные равносильности алгебры высказываний. Нормальные формы. Совершенные нормальные формы: СДНФ, СКНФ. Теорема существования и единственности совершенных нормальных форм.

Тема 1.3. Логическое следование формул. Приложение алгебры высказываний.

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

Тема 1.4. Применение алгебры высказываний к описанию релейно-контактных схем.

Методы математических доказательств: метод от противного. Применение алгебры высказываний к описанию релейно-контактных схем: анализ и синтез схем.

Раздел 2. Исчисление высказываний Тема 2.1. Построение исчисления высказываний.

Исчисление высказываний. Формулы исчисления высказываний. Аксиомы исчисления высказывания и правила вывода.

Тема 2.2. Теорема дедукции и ее применение.

Теорема дедукции и ее применение: правила введения и снятия двойного отрицания, правила контрапозиции, правило силлогизма.

Тема 2.3. Свойства исчисления высказываний.

Исследования системы аксиом исчисления высказываний; их независимость, непротиворечивость и полнота.

Раздел 3. Алгебра предикатов и исчисление предикатов Тема 3.1. Логические и кванторные операции над предикатами.

Логика предикатов. Логические и кванторные операции над предикатами. Формулы логики предикатов и их классификация: общезначимые, опровержимые формулы.

Тема 3.2. Формулы логики предикатов.

Равносильные преобразования и логическое следование формул логики предикатов.

Тема 3.3. Приведенная форма и предваренная нормальная форма.

Приведенная форма для формул логики предикатов. Предваренная нормальная форма. Теорема существования ПНФ.

Тема 3.4. Проблема разрешения формул логики предикатов.

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

Тема 3.5. Применение логики предикатов.

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

Тема 3.6. Исчисление предикатов и его свойства.

Исчисление предикатов. Непротиворечивость исчисления предикатов. Теорема Геделя о полноте исчисления предикатов.

Раздел 4. Теория алгоритмов Тема 4.1. Необходимость уточнения понятия алгоритма. Понятие вычислимой функции.

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

Тема 4.2. Частично рекурсивные функции.

Формальная теория вычислимости. Оператор примитивной рекурсии. Понятие примитивно-рекурсивной функции. Частично-рекурсивные функции. Оператор минимизации.

Примитивно-рекурсивные и частично-рекурсивные подмножества множества N. Теорема о суммируемости рекурсивных функций.

Тема 4.3. Рекурсивность нумерующих функций.

Функции Кантора(понятие, формулы). Примитивная рекурсивность функции Кантора. Обобщённые функции Кантора.

Тема 4.4. Кусочное задание функции.

Кусочно-определённые функции. Теорема о мажорируемых неявных функциях. примитивная рекурсивность некоторых арифметических функций: [X/Y], REST, DIV, P(X), ( x), Тема 4.5. Машины Тьюринга. Нормальные алгоритмы Маркова.

Регистровые машины, машины Тьюринга. Команды. Конфигурации. Вычислимые по Тьюрингу функции. Тезис Чёрча. Конечные и бесконечные машины. Операции с машинами.

Понятие программы. Эффективная нумерация программ. Нормальные алгоритмы Маркова.

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

Технология традиционного обучения предусматривает такие методы и формы изучения материала как лекция, практические занятия:

информационная лекция:

1.1. Высказывания. Формулы алгебры высказываний.

1.2. Логическая равносильность формул. Нормальные формы.

2.1 Построение исчисления высказываний.

2.2 Теорема дедукции и ее применение.

2.3 Свойства исчисления высказываний.

3.1. Логические и кванторные операции над предикатами.

3.2. Формулы логики предикатов.

3.3. Приведенная форма и предваренная нормальная форма.

3.6. Исчисление предикатов и его свойства.

4.2. Частично рекурсивные функции.

4.3. Рекурсивность нумерующих функций 4.4. Кусочное задание функции.

проблемная лекция 1.3. Логическое следование формул. Приложение алгебры высказываний.

3.4. Проблема разрешения формул логики предикатов.

3.5. Применение логики предикатов.

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

лекция-визуализация 1.4. Применение алгебры высказываний к описанию релейно-контактных схем.

4.5. Машины Тьюринга. Нормальные алгоритмы Маркова.

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

3.5. Применение логики предикатов.

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

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

3.4. Проблема разрешения формул логики предикатов.

коллективная мыслительная деятельность:

2.2 Теорема дедукции и ее применение;

2.3 Свойства исчисления высказываний;

медиатехнология подготовка и демонстрация преподавателем презентации 4.5. Машины Тьюринга. Нормальные алгоритмы Маркова кейс-технология проблемный метод 3.5. Применение логики предикатов.

моделирование 1.4. Применение алгебры высказываний к описанию релейно-контактных схем.

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

Самостоятельная работа студентов включает работу под руководством преподавателя (собеседования, коллоквиумы) и индивидуальную работу студента.

При реализации образовательных технологий используются следующие виды самостоятельной работы:

работа с теоретическим материалом;

решение стандартных задач и упражнений по образцу;

решение вариативных задач и упражнений;

поиск информации в сети «Интернет» в дополнительной и справочной литературе;

подготовка к коллоквиуму;

подготовка к сдаче экзамена.

6. Учебно-методическое обеспечение самостоятельной работы студентов.

Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины «Математическая логика и теория алгоритмов»

изучение свойств операций над высказываниями, составление примеров формул в соответствии с их стандарт.: установление истинности выска- № 1.7, 1.9, 1. вариативные: классификация формул без составления таблицы, решение логических уравнений доказательство основных равносильностей, теоремы о существовании СКНФ доказательство свойств логического следования, изучение приложений алгебры высказываний стандарт.: установление логического следования обоснование метода доказательства от противного вариативные: анализ и синтез релейноконтактной схемы решение задачи по составлению модели реальной жизненной ситуации средствами математической логики (составить проект технического работа с теоретическим материалом;

изучение структуры формализованного исчисления стандарт.: распознавание объектов исчисления работа с теоретическим материалом;

доказательство теоремы дедукции и ее следствий применение теоремы дедукции для построения работа с теоретическим материалом;

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

Алгебра предикатов и исчисление предикатов работа с теоретическим материалом;

изучение свойств логических и кванторных операций над предикатами, составление примеров формул в соответствии с их классификацией вариативные: установление вида формулы алгебры предикатов работа с теоретическим материалом;

доказательство основных равносильностей и свойств логического следования вариативные: решение логических задач работа с теоретическим материалом;

доказательство теорем о существовании приведенной и предваренной форм приведение формул к предваренной нормальной работа с теоретическим материалом;

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

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

работа с теоретическим материалом;

операции суперпозиции и подстановки для функций натурального аргумента работа с теоретическим материалом;

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

2. Составить таблицу истинности и выяснить равносильны ли следующие формулы алгебры высказываний:

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

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

4. Найти все формулы алгебры высказываний, являющиеся логическими следствиями следующих формул (посылок):

5. Решить логически задачи.

а) Вова, Рома, Юра и Саша заняли на олимпиаде четыре первые места. Когда их спросили о распределении мест, они дали три таких ответа:

- Саша занял первое место, а Рома – второе;

- Юра занял второе место, а Вова – четвертое место.

Как распределились места, если в каждом ответе только одно утверждение истинно.

б) По обвинению в ограблении перед судом предстали Иванов, Петров, Сидоров. Следствием установлено следующее:

1) Если Иванов не виновен или Петров виновен, то Сидоров виновен.

2) Если Иванов не виновен, то Сидоров не виновен.

1. Пусть f(0,n)=1, f(m,0)=m+1, f(m+1,n+1)=f(m,mn)f(m+1,n). Найдите f(2,5); f(4,4).

2. Докажите, что если функция (x) – примитивно рекурсивна, то функция f(x), определяется условием (1) f(0)=0, (2) f(x+1)=(x+1) примитивно рекурсивна.

рекурсивна.

4. Пусть f(x)=2x+1, Imf – множество ее значений. Докажите, что Imf – примитивно рекурсивная.

5. Решите уравнений: а) q(x)=5; б) x[ ]=2.

6. Найдите пару (x,y) натуральных чисел, канторовский номер которой равен 121.

7. Найдите упорядоченную тройку (x,y,z) натуральных чисел, с канторовским номером 20.

1. Под высказыванием понимают… а) любое повествовательное предложение;

б) предложение с переменной, превращающееся в правильное утверждение при подстановке вместо переменных конкретных значений;

в) предложение, представляющее собой утверждение, о котором можно судить, истинно оно или ложно;

г) безличные, вопросительные и восклицательные предложения.

2. Отрицанием высказывания Р называется такое высказывание Р, которое а) истинно, если Р истинно, и ложно, если Р ложно;

б) всегда ложно;

в) всегда истинно;

г) истинно, если Р ложно, и ложно, если Р истинно.

3. Конъюнкцией высказываний Р и Q называется высказывание Р Q, которое а) истинно тогда и только тогда, когда Р и Q одновременно истинны;

б) ложно тогда и только тогда, когда Р и Q одновременно ложны;

в) ложно тогда и только тогда, когда Р – истинно, а Q ложно;

г) истинно тогда и только тогда, когда Р и Q имеют одинаковое значение истинности.

4. Дизъюнкцией высказываний Р и Q называется высказывание РQ, которое а) истинно тогда и только тогда, когда Р и Q одновременно истинны;

б) ложно тогда и только тогда, когда Р и Q ложны одновременно;

в) ложно тогда и только тогда, когда Р - истинно, а Q ложно;

г) истинно тогда и только тогда, когда Р и Q имеют одинаковое значение истинности.

5. Импликацией высказываний Р и Q называется высказывание РQ, которое а) истинно, тогда и только тогда, когда Р- истинно, а Q-ложно;

б) ложно, тогда и только тогда, когда Р- истинно, а Q-ложно;

в) истинно, тогда и только тогда, когда Р- ложно, а Q-истинно;

г) ложно, тогда и только тогда, когда Р- ложно и Q-истинно;

6. Эквиваленцией высказываний Р и Q называется высказывание РQ, которое а) истинно, тогда и только тогда, когда Р и Q принимают разное значение истинности;

б) ложно, тогда и только тогда, когда Р и Q принимают одинаковое значение истинности;

в) истинно, тогда и только тогда, когда Р и Q принимают одинаковое значение истинности;

г) ложно, тогда и только тогда, когда, Р и Q принимают разное значение истинности.

7. Пропозиционными переменными называются такие переменные а) вместо которых можно подставлять конкретные высказывания;

б) значение которых зависит от позиции переменной в формуле;

в) которые принимают значение истины в любом высказывании;

8. Определите, какая последовательность символов не является формулой (внешние скобки опущены) а) ((РQ)(P(RS)));

б) (PQ)(PS);

в) (Q(PP ))((QP)Q);

г) ((PQ)R)Q.

9. Формула алгебры высказываний называется тавтологией, а) при любом выборе значений входящих в нее переменных данная формула принимает значение ложно;

б) при любом выборе значений входящих в нее переменных данная формула принимает значение истинно;

в) хотя бы при одном выборе значений входящих в нее переменных данная формула принимает значение ложно;

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

10. Формула алгебры высказываний называется противоречием, если а) при любом выборе значений входящих в нее переменных данная формула принимает значение ложно;

б) при любом выборе значений входящих в нее переменных данная формула принимает значение истинно;

в) хотя бы при одном выборе значений входящих в нее переменных данная формула принимает значение ложно;

г) хотя бы при одном выборе входящих в нее переменных данная формула принимает значение истинно.

11. Формула алгебры высказываний называется выполнимой,если а) при любом выборе значений входящих в нее переменных данная формула принимает значение ложно;

б) при любом выборе значений входящих в нее переменных данная формула принимает значение истинно;

в) хотя бы при одном выборе значений входящих в нее переменных данная формула принимает значение ложно;

г) хотя бы при одном выборе входящих в нее переменных данная формула принимает значение истинно.

12 Формула алгебры высказываний называется опровержимой, если а) при любом выборе значений входящих в нее переменных данная формула принимает значение ложно;

б) при любом выборе значений входящих в нее переменных данная формула принимает значение истинно;

в) хотя бы при одном выборе значений входящих в нее переменных данная формула принимает значение ложно;

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

13. Определить вид формулы (P(QP))((QP)Q) а) тавтология;

б) противоречие;

в) выполнимая и опровержимая.

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

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

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

г) при любых значениях, входящих в них пропозиционных переменных данные формулы принимают значение ложно.

15. Формула (PQ)(QP)(RP) равносильна следующей формуле:

16. Конъюнктивной нормальной формой для формулы алгебры высказываний называется а) произвольная конъюнкция конъюнктивных одночленов;

б) произвольная конъюнкция дизъюнктивных одночленов;

в) произвольная конъюнкция дизъюнктивных совершенных одночленов;

г) произвольная дизъюнкция конъюнктивных одночленов.

17. Одночлен от нескольких переменных называется совершенным, если а) каждая его переменная совершенна;

б) каждая его переменная входит в него только один раз;

в) каждая из этих переменных входит в него хотя бы один раз со знаком отрицания или без него;

г) каждая из этих переменных входит в него хотя бы один раз со знаком отрицания или без него.

18. СКН – форма некоторой формулы от трех переменных содержит пять сомножителей (совершенных дизъюнктивных одночленов). Что проще: СКН – форма или СДН – форма этой формулы?

а) СКН – форма;

б) СДН – форма;

в) СКН – форма и СДН – формы одинаковы по простоте.

19. Формула B называется логическим следствием формулы А тогда и только тогда, когда а) формула (А В) – тавтология;

б) формула А равносильна формуле В; (x1,x2,...,xn) в) формула (А В) – тавтология;

г) формула (А В) – выполнима.

20. Формула В(x1,x2,...,xn) называется логическим следствием формулы А1(x1,x2,...,xn), А2(x1,x2,...,xn),…,Аs(x1,x2,...,xn) тогда и только тогда, когда а) ((А1 А2 … Аs) В) – тавтология;

б) ((А1 А2 … Аs) В) – тавтология;

в) из того, что |B| = 1 следует, что |А1| = |А2| =…=|Аs| = 1.

21. Если логическая структура данной теоремы выражается следующей формулой:

(АВ), то противоположное утверждение имеет следующую структуру:

22. Булевой функцией от n аргументов называется а) любая функция, принимающая значение в множестве [ 0; 1];

б) любая функция, заданная на множестве { 0; 1};

в) любая функция от n аргументов, заданная на двухэлементном множестве { 0; 1} и принимающая значение в том же множестве.

23. Булевых функций от трех переменных существует ровно:

24. Суперпозиция функций h1(x1,x2) = x1x2, h2(x1) = x1, h3(x1,x3) = x1x3 в функцию g(u,v,t) = u v t есть функция:

а) G(x1, x2, x3) = x1(x2 x3);

б) G(x1, x2, x3) = x1 x2 x3;

в) G(x1, x2, x3) = (x1x2) x3.

25. Данная релейно-контактная схема равносильна следующей схеме:

1. Высказывания. Операции над ними.

2. Тавтологии. Основные свойства.

3. Отношения логического следования. Свойства 4. Равносильность формул. Основные равносильности 5. Полные и неполные системы логических связок.

6. Двойственные формулы. Приведенные формулы. Свойства.

7. Теорема двойственности 8. Логическое следование формул алгебры высказываний: основные логические следствия.

Свойства логического следования.

9. Приложение алгебры высказываний к логико-математической практике.

10. Прямая и обратная теоремы, противоположная и обратная теоремы; закон контрапозиции.

11. Элементарная конъюнкция и элементарная дизъюнкция. Свойства 12. Конъюнктивная и дизъюнктивная нормальные формы 13. Полные элементарные конъюнкции и дизъюнкции.

14. Совершенные дизъюнктивные нормальные формы. Алгоритмы построения СДНФ 15. Совершенные конъюнктивные нормальные формы.

1. Что называется высказыванием? Операции над высказываниями.

2. Как определяются формулы алгебры высказываний? Таблица истинности.

3. Назовите виды формулы.

4. Перечислите тавтологии и их свойства.

5. Равносильность формул алгебры высказываний и их свойства.

6. Основные равносильности.

7. Логическое следствие, его свойства.

8. Совершенные нормальные формы.

9. Приведение формул к совершенной нормальной форме.

10. Сформулируйте алгоритм построения СДНФ и СКНФ.

11. Нахождение следствий из данных посылок.

12. Нахождение посылок для данного следствия.

13. Обоснование метода доказательства от противного.

14. Применение алгебры высказываний к анализу и синтезу релейно-контактных схем.

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

2. Перечислить аксиомы формализованного исчисления.

3. Сформулировать теорему дедукции и основные идеи ее доказательства.

4. Сформулировать и доказать следствия теоремы дедукции.

5. Применения теорему дедукции, доказать правило силлогизма, правила снятия и введения двойного отрицания, правила контрапозиции.

6. В чем состоит свойство полноты исчисления высказываний?

7. Сформулировать и доказать лемму о выводимости формулы из специального множества гипотез.

8. Какое исчисление называется непротиворечивым? Доказать непротиворечивость исчисления.

9. Свойство независимости системы аксиом.

10. Доказать независимость аксиомы А1.

11. Доказать независимость аксиомы А2.

12. Доказать независимость аксиомы А3.

1. Высказывания. Операции над высказываниями.

2. Формулы алгебры высказываний. Таблица истинности.

3. Виды формулы. Основные тавтологии.

4. Тавтологии и их свойства.

5. Равносильность формул алгебры высказываний и их свойства.

6. Основные равносильности.

7. Логическое следствие, его свойства.

8. Совершенные нормальные формы.

9. Приведение формул к совершенной нормальной форме.

10. Алгоритм построения СДНФ.

11. Алгоритм построения СКНФ.

12. Нахождение следствий из данных посылок.

13. Нахождение посылок для данного следствия.

14. Обоснование метода доказательства от противного.

15. Применение алгебры высказываний к анализу и синтезу релейно-контактных схем.

16. Исчисление высказываний.

17. Теорема дедукции.

18. Следствия теоремы дедукции.

19. Применение теоремы дедукции.

20. Полнота исчисления высказываний.

21. Лемма о выводимости формулы из специального множества гипотез.

22. Непротиворечивость исчисления высказываний.

23. Независимость системы аксиом.

24. Независимость аксиомы А1.

25. Независимость аксиомы А2.

26. Независимость аксиомы А3.

27. Понятие предиката. Область истинности предиката.

28. Логические операции над предикатами.

29. Кванторные операции над предикатами.

30. Понятие формулы логики предикатов, их классификация.

31. Тавтологии логики предикатов.

32. Равносильность формул логики предикатов. Основные равносильности.

33. Логическое следование формул логики предикатов.

34. Приведенные формы формул логики предикатов.

35. Предваренная нормальная форма.

36. Проблема общезначимости для формул логики предикатов.

37. Выполнимость формул на бесконечном множестве.

38. Частные случаи выполнимости формул.

39. Понятие алгоритма. Примеры.

40. Характерные черты алгоритмов.

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

42. Понятие вычислимой функции.

43. Простейшие функции. Суперпозиция функций. Операция подстановки.

44. Оператор примитивной рекурсии. Понятие примитивно-рекурсивной функции.

45. Частично-рекурсивные функции. Оператор минимизации.

46. Примитивно-рекурсивные и частично-рекурсивные подмножества множества N.

47. Теорема о суммируемости рекурсивных функций.

48. Кусочно-определённые функции. Теорема о мажорируемых неявных функциях.

49. Примитивная рекурсивность функции [X/Y].

50. Примитивная рекурсивность функции REST.

51. Примитивная рекурсивность функции DIV.

52. Примитивная рекурсивность функции P(X).

53. Примитивная рекурсивность функции ( x).

54. Примитивная рекурсивность функции exp X Y.

55. Понятие о возвратной рекурсии(теоремы).

56. Примитивная рекурсивность функции X [ X ]2.

57. Функции Кантора(понятие, формулы).

58. Примитивная рекурсивность функции Кантора.

59. Обобщённые функции Кантора.

60. Рекурсивно-перечислимое множество.

61. Теорема о задании перечислимого множества.

62. Теорема о перечислимости пересечения и объединения перечислимых множеств.

63. Теорема Поста.

64. Рекурсивно-перечислимое множество N n. Универсальная функция.

65. Машины Тьюринга. Команды. Конфигурация.

66. Описание машины Тьюринга.

67. Вычислимые по Тьюрингу функции.

68. Нормальные алгоритмы Маркова.

7. Учебно-методическое и информационное обеспечение дисциплины «Математическая логика и теория алгоритмов»

1. Игошин В. И. Математическая логика и теория алгоритмов.- М.: Издательский центр «Академия»; 2004.

2. Игошин В. И. Задачник и упражнения по математической логике и теории алгоритмов.М.: Издательский центр «Академия»; 2005.

3. Лавров И. А. Математическая логика – М.: Академия, 2006.

4. Лавров И. А., Максимова Л. Л.Задачи по теории множеств, математической логике и теории алгоритмов.- М., 2005.

5. Мендельсон Э. Введение в математическую логику. – М.: Либроком, 2010.

1. Блох А. Ш. Граф-схемы и алгоритмы: учеб. Пособие для физ-мат. пед. ин-тов – Минск: Высш. школа, 1987.

2. Заитдинов Р. Г. Решение логических задач: учеб. пособие – Тверь: 3. Клини С. Математическая логика.- М.: Мир, 1973.

4. Ловков А. А., Парфенов Г. Н. Элементы математической логики: учеб.-метод. пособие – Пенза, 2001.

5. Мальцев А. И. Алгоритмы и рекурсивные функции.- М., 1965.

6. Новиков П. С. Элементы математической логики.- М.: Наука, 1973.

7. Осьминина Н. А. Элементы теории алгоритмов: метод. рекоменд. – Пенза, 2004.

8. Чёрч А. Введение в математическую логику.- М.: Наука, 1960.

Exponenta.ru Математика для Российское обрапрограммы, стандарты, ВУЗы, тесты ЕГЭ.

8. Материально-техническое обеспечение дисциплины «Математическая логика и теория алгоритмов»

Для освоения данной дисциплины необходимы:

– мультимедийные средства обучения (компьютер и проектор, ресурсы Интернета).

Рабочая программа дисциплины «Математическая логика и теория алгоритмов» составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций примерной ООП ВПО по направлению подготовки 050100 «Педагогическое образование» и профилю подготовки «Математика».

Программу составили:

1. Монахова О. А., доцент, к. ф.-м. н.

Настоящая программа не может быть воспроизведена ни в какой форме без предварительного письменного разрешения кафедры-разработчика программы.

Программа одобрена на заседании кафедры алгебры Программа одобрена учебно-методическим советом физико-математического факультета Председатель учебно-методического совета физико-математического факультета _ М. В. Сорокина Программа одобрена учебно-методическим управлением университета «_» _ 2011 года Начальник учебно-методического управления университета _ Г.Н. Шалаева