Рабочий план

 

Дисциплина: Математическая логика и теория алгоритмов

Курс, семестр: 2 курс, 3 семестр

Направление подготовки: Информационные системы и технологии

Профиль: Информационные системы и технологии в образовании

Учебный год: 2013/2014

Разработчик: Тропин М.П.

 

Тематическое планирование

 

Название темы

Лекции

ЛР

ПЗ

СР

Формы контроля

 

 

1

Логика высказываний

12

 

10

18

Контр.работа №1

Коллоквиум №1

 

 

2

Элементы логики предикатов

2

 

2

12

 

 

 

3

Элементы теории алгоритмов

4

 

 

12

Контр.работа №2

 

 

 

ИТОГО

18

12

42

 

Зачёт

 

 

План лекций и практических занятий

Темы лекций и практ. занятий

Содержание

Часы и дата лекций

Часы и дата ПЗ и ЛР

1

Высказывания. Формулы. Таблицы истинности

Определение высказывания. Логические операции. Формулы логики высказываний. Таблица истинности формулы. Теорема о количестве вариантов значений логических переменных.

2, 05.09.

2, 12.09

2

Равносильность формул

Равносильность формул. Основные равносильности. Теорема о преобразовании формул к упрощённому виду.

2,

19.09.

2, 26.09.

3

Полные системы логических операций

Теорема о выражении одних операций через другие. Штрих Шеффера, стрелка Пирса. Теорема о выражении всех логических операций через штрих Шеффера.

2, 03.10

 

4

Нормальные формы

Элементарная конъюнкция. Дизъюнктивная нормальная форма (ДНФ). Элементарная дизъюнкция. Конъюнктивная нормальная форма (КНФ). Приведение формулы к КНФ (ДНФ). Теорема о построении формулы по таблице истинности.

2, 10.10

2, 17.10.

5

Контактно-релейные схемы

Контактно-релейные схемы. Интерпретация последовательного и параллельного соединения переключателей при помощи логических операций. Алгоритм построения контактно-релейной схемы, реализующей данную логическую формулу.

2, 24.10.

2, 31.10

6

Логическое следование

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

2, 07.11.

2, 14.11.

7

Элементы логики предикатов

Понятие n-местного предиката. Логические операции над предикатами. Определение кванторов. Основные равносильности логики предикатов. Варианты равносильного преобразования формул.

2, 21.11

2, 28.11

8

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

Понятие алгоритма, характеристические свойства алгоритмов. Вычислимые функции.

 

1, 05.12.

 

9

Машины Тьюринга

Понятие машины Тьюринга: устройство, алфавит, состояния, переходы. Примеры машин Тьюринга. Тезис Тьюринга.

2,

05.12. 12.12.

 

10

Рекурсивные функции

Рекурсивный способ определения функций. Рекурсивно-вычислимые функции. Примеры.

1,

12.12

0

 

ИТОГО

 

18

12

Литература.

1. Зюзьков В.М., Шелупанов А.А. Математическая логика и теория алгоритмов, М.: Горячая линия-Телеком, 2007. - 176 с. - 50 экз.

2. Игошин В.И. Математическая логика и теория алгоритмов, М.: Академия, 2010. - 448 с. - 19 экз.

  1. Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов, М.: Академия, 2007. - 304 с. - 19 экз.
Последнее изменение: Среда, 24 Октябрь 2018, 17:04