Рабочая программа по дисциплине «логика» для специальности 351400 Прикладная информатика (по областям) Форма обучения: очная

Вид материала

Содержание

1.1.2. Требования к обязательному минимуму содержания
Принципы построения
Цели курса
Учебно-тематический план
Количество часов
Содержание лекционных занятий
Программа практических занятий
Программа самостоятельной работы студента

Подобный материал:

Федеральное агентство по образованию

ГОУ ВПО «Удмуртский государственный университет»

факультет Информационных технологий и

вычислительной техники

кафедра Теоретических основ информатики

РАБОЧАЯ ПРОГРАММА

по дисциплине

«ЛОГИКА»

для специальности

351400 Прикладная информатика (по областям)

Форма обучения: очная

Курс	1
Семестр	1, 2
Всего часов	140
Всего аудиторных часов	105
Лекции, час.	70
Практические занятия, час.	35
Самостоятельная работа, час.	35
Экзамен, номера семестров	2
Зачет, номера семестров	1
Другие виды контроля: одна контрольная работ, семестр одно дом. задание, семестр	1, 2 1, 2

Ижевск

2009

Рабочая программа составлена на основании ГОС ВПО специальности 351400 «Прикладная информатика (по областям)» (квалификация – информатик (квалификация в области ), утвержденного 14 марта 2000 г.

Составитель рабочей программы

д.ф-м.н., профессор ________________ А.П.Бельтюков

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

«___» _______________ 2009 г.

Заведующий кафедрой ___________________ А.П.Бельтюков

д.ф-м.н., профессор

Одобрено методической комиссией

«___» _______________ 2009 г.

Председатель методической комиссии ______________________В.И.Родионов

Декан факультета _____________________В.И.Родионов

Требования

государственного образовательного стандарта (ГОС)

по специальности 351400 – Прикладная информатика (по областям)

1.1. Требования к профессиональной подготовленности специалиста

1.1.1. По циклу математических и естественнонаучных дисциплин

Информатик должен знать и уметь использовать:

- основные понятия дискретной математики;

иметь опыт:

употребления математической символики для выражения количественных и

качественных отношений объектов;

иметь представление:

- о математике как особом способе познания мира, общности ее понятий и

представлений;

- дискретности и непрерывности в природе и обществе;

- о соотношении порядка и беспорядка в природе и обществе,

упорядоченности строения объектов, переходах в неупорядоченное

состояние и наоборот.

1.1.2. По циклу общепрофессиональных дисциплин

информатик должен знать:

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

- информационные закономерности, специфику информационных объектов и

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

- информационные модели знаний и методы представления знаний в базах

информационных систем;

уметь использовать:

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

иметь опыт:

- применения математических моделей и методов для анализа, расчетов,

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

предметной области;

- решения формализуемых и трудно формализуемых задач, а также

проектирования информационных процессов;

иметь представление:

- о качественных и количественных методах описания

профессионально-ориентированных информационных систем;

1.1.3. По циклу специальных дисциплин

информатик должен иметь опыт:

работы с основными объектами, явлениями и процессами, связанными с

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

исследования.

1.1.2. ТРЕБОВАНИЯ К ОБЯЗАТЕЛЬНОМУ МИНИМУМУ СОДЕРЖАНИЯ

ОСНОВНОЙ ОБРАЗОВАТЕЛЬНОЙ ПРОГРАММЫ

Наименование дисциплины - Математика

Основные разделы: Дискретная математика: логические исчисления,

графы, комбинаторика.

Индекс	Наименование дисциплины	Всего часов
ЕН.Р.01	Логика Из требований федерального компонента включены следующие дидактические единицы (по дисциплине ЕН.Ф.01 «МАТЕМАТИКА»): Дискретная математика: логические исчисления, графы, комбинаторика. Элементы теории нечётких множеств. Нечёткие алгоритмы. Теория неопределённости.	140 час.

Курс входит в раздел: национально-региональный (вузовский) компонент

Принципы построения

курса «Логика»

Курс входит в число математических дисциплин. Курс адресован студентам

1 курса специальностей "Прикладная математика и информатика" и

"Прикладная информатика (по областям)". Курс готовит студентов к

использованию языка математики на основе логико-предметных языков,

основных понятий дискретной математики, математической логики и теории

алгоритмов. Основная цель курса для студента - освоение

математического фундамента большей части компьютерных наук.

Дисциплина "Дискретная математика" ставит свой целью ознакомление

студентов с важнейшими разделами дискретной математики и ее

применением в компьютерных науках. В процессе обучения прививаются

навыки свободного обращения с такими дискретными объектами как функции

алгебры логики, автоматные функции, машины Тьюринга, рекурсивные

функции, графы и коды. Во всех разделах дисциплины большое внимание

следует уделять построению алгоритмов для решения задач дискретной

математики. Это способствует более глубокому пониманию проблематики

теории алгоритмов, ее возможностей и трудностей, помогает строить

алгоритмы для решения дискретных задач.

Понятия и факты, проводимые в дисциплине "Дискретная математика",

используются в дисциплинах "ЭВМ (Информатика) и программирование",

"Исследование операций", "Теория вероятностей", "Теория систем и

системный анализ", "Базы данных" и некоторых других.

Ядро курса - логико-предметные языки, с помощью которых ведется

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

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

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

изучаются начала математического анализа в традиционном классическом

изложении. Этот предмет используется для некоторых примеров.

В курсе выделено 3 блока: основания математики (элементы математической

логики и теория множеств и их приложения в математике), основы теории

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

Курс имеет практическую часть в виде практических занятий с

преподавателем в аудитории и выполнения некоторых домашних заданий.

Оценка знаний и умений студентов проводится с помощью тестирования,

проверки зачетных заданий и экзамена.

Цели курса

После изучения теоретических разделов курса и выполнения практических

занятий в объеме рабочей программы студент должен

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

математики: логические исчисления, функциональные системы с

операциями, дискретные структуры (графы, сети, коды), дизъюнктивные

нормальные формы и схемы из функциональных элементов, комбинаторику,

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

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

количественных и качественных отношений объектов; применения теории

алгоритмов;

- иметь представление о соотношении дискретности и непрерывности в

математике;

Структура курса:

[0] Основы формальных языков

[0]->[1] Основы математической логики

[1]->[2] Логико-предметные языки

[2]->[3] Теория множеств

[3]->[4] Построение основных математических структур в теории множеств

[0]->[5] Основы теории алгоритмов

[3]->[6] Основы теории графов

[3]->[7] Комбинаторика

[6,7]->[8] Построение логических функций

[4,5,6,7]->[9] Элементы теории кодирования

Учебно-тематический план

№	Тема	Количество часов
№	Тема	Лекц	Практ	Сам
1	основы формальных языков	2	2	2
2	язык исчисления высказываний	4	4	2
3	язык исчисления предикатов	4	4	2
4	логико-предметные языки	2	4	2
5	логический вывод	4	4	2
6	аксиоматика формальных предметных теорий	2	2	1
7	язык теории множеств	2	2	1
8	наивная теория множеств и ее парадоксы	2	2	1
9	аксиомы теории множеств	4	2	1
10	отношения и функции в теории множеств	2	2	1
11	Упорядочения	2	2	1
12	эквивалентности и разбиения	2	2	1
13	алгебры и алгебраические системы	2	3	1
14	натуральные и целые числа в теории множеств	2	0	1
15	рациональные и вещественные числа и их функции в теории множеств	2	0	1
16	бесконечные порядковые и количественные числа	2	0	1
17	рекурсивные функции натуральных чисел	2	0	1
18	математическое понятие алгоритма	4	0	1
19	вычислимые и невычислимые функции	2	0	1
20	разрешимые и неразрешимые, перечислимые и неперечислимые множества	2	0	1
21	подклассы множества вычислимых функций	2	0	1
22	основы теории графов	2	0	1
23	основы комбинаторики	2	0	1
24	перечисление дискретных объектов	2	0	1
25	построение логических функций	2	0	1
26	дизъюнктивные нормальные формы	2	0	1
27	схемы из функциональных элементов	2	0	1
28	коды для сжатия информации	2	0	1
29	коды повышенной надежности передачи и хранения информации	2	0	1
30	коды для защиты информации	2	0	1

Содержание лекционных занятий

Лекция 1. Введение, основы формальных языков

Место дискретной математики в системе математического образования.

Дискретная математика и компьютерные науки. Соотношение между

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

Основы формальных языков. Алфавит, слова, выражения, предложения.

Особенности логических языков.

Лекция 2. Язык исчисления высказываний

Алгебра логики. Функции алгебры логики. Таблицы истинности. Формулы.

Исчисление высказываний. Определение языка формул. Интерпретация.

Истинность. Тавтологии. Выполнимые формулы. Модели.

Лекция 3. Язык исчисления предикатов

Исчисление предикатов 1-го порядка (узкого исчисления предикатов -

УИП). Предметная область. Предметные константы, переменные,

функциональные константы, предикатные константы, вместимость (число

аргументов, размерность). Неформальные понятия функции и отношения.

Понятие интерпретации. Понятие истинности формулы на

заданной интерпретации. Выполнимость и общезначимость формулы 1-го

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

Лекция 4. Логико-предметные языки

Использование языков, построенных на основе языка узкого исчисления

предикатов. Примеры: язык арифметики натуральных чисел, язык теории

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

Лекция 5. Логический вывод

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

Структура логического вывода в естественной форме записи. Другие виды

логического вывода. Системы аксиом и правила вывода. Правила вывода

исчисления высказываний для естественной формы записи. Правила введения

и правила удаления. Теорема о полноте исчисления высказываний. Правила

вывода для исчисления предикатов. Введение и удаление кванторов.

Полнота исчисления предикатов.

Лекции 6. Аксиоматика формальных предметных теорий

Узкое исчисление предикатов с равенством. Логико-предметные теории с

равенством. Аксиомы и схемы аксиом равенства. Примеры и использование

аксиом арифметики и других математических теорий. Схема аксиом

математической индукции и ее использование.

Лекция 7. Язык теории множеств

Понятие класса абстрактных множеств как предметной области теории

множеств. Константы, предикаты и функции теории множеств:

пустое множество, возможность введения других постоянных множеств,

предикат принадлежности, выразимость равенства через принадлежность

(принцип экстенсиональности) функции пары, объединения, канторовой

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

выделения подмножеств элементов, обладающих заданными свойствами.

Лекция 8. Наивная теория множеств и ее парадоксы

Обозначение множества элементов, обладающих заданными свойствами.

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

парадоксов. Ограничения на операцию выделения. Операция

параметрического объединения.

Лекция 9. Аксиомы теории множеств

Аксиома экстенсиональности. Аксиома пустого множества. Аксиома пары.

Аксиома объединения (и ее виды). Виды аксиомы бесконечности. Аксиома

выделения и ее виды.

Лекция 10. Отношения и функции в теории множеств

Упорядоченная пара. Декартовы произведения. Декартова степень.

Бинарное отношение. Однозначность отношения. Функция. Обратное

отношение. Взаимно-однозначное соответствие. Суперпозиция и итерация

отношений. Понятие инъекции, сюръекции, и биекции. Область

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

Лекция 11. Упорядочения

Строгие и нестрогие порядки. Свойства порядков. Линейные порядки.

Максимальный и минимальный, наименьший и наибольший элементы. Полные

порядки. Предпорядки. Конечные полные порядки.

Лекция 12. Эквивалентности и разбиения

Свойства отношений эквивалентности. Классы смежности отношений, классы

эквивалентности, факторизация, фактор-множество, разбиение на классы

эквивалентности. Примеры отношений эквивалентности и разбиений на

классы эквивалентности. Восстановление отношения эквивалентности по

разбиению на классы эквивалентности.

Лекция 13. Алгебры и алгебраические системы

Понятие алгебры и алгебраической системы. Примеры алгебраических

систем. Гомоморфизм, эндоморфизм, эпиморфизм, изоморфизм алгебраических

систем. Примеры алгебраических систем. Модель натуральных чисел с

операцией следования в теории множеств как алгебраическая система,

изоморфные ей системы.

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

Натуральные числа в теории множеств, ординальное моделирование

натуральных чисел. Рекурсивные определения функций в теории множеств.

Натуральные числа со сложением и умножением как алгебраическая система.

Моделирование целых чисел в теории множеств. Кольцо целых чисел со

сложением, вычитанием и умножением как алгебраическая система.

Лекция 15. Рациональные и вещественные числа и их функции в теории

множеств

Моделирование рациональных чисел в теории множеств. Несократимые

дроби, классы эквивалентных дробей. Поле рациональных чисел как

алгебраическая система. Моделирование вещественных чисел в теории

множеств. Сечения, классы эквивалентных фундаментальных

последовательностей. Поле вещественных чисел как алгебраическая

система.

Лекция 16. Бесконечные порядковые и количественные числа

Ординалы. Равномощность. Мощность. Кардиналы. Примеры ординалов и

кардиналов.

Лекция 17. Рекурсивные функции натуральных чисел

Понятие примитивной рекурсии. Операция нахождения наименьшего корня

(минимизации). Операция многоместной суперпозиции. Исходные

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

рекурсивные, частично-рекурсивные и общерекурсивные функции.

Лекция 18. Математическое понятие алгоритма

Машины Тьюринга. Операции над машинами Тьюринга. Тезис Тьюринга. Связь

класса рекурсивных функций с классом вычислимых функций. Тезис Черча.

Лекция 19. Вычислимые и невычислимые функции

Модели вычислимых функций. Нормальные алгоритмы. Универсальные

алгоритмы (универсальные машины). Универсальные функции. Неразрешимые

проблемы.

Лекция 20. Разрешимые и неразрешимые, перечислимые и неперечислимые

множества

Определения, свойства и примеры рекурсивно разрешимых и перечислимых

множеств.

Лекция 21. Подклассы множества вычислимых функций

Примитивно рекурсивные, автоматные и элементарные функции, множества и

отношения

Лекция 22. Основы теории графов

Основные понятия и задачи теории графов. Типы графов, способы

задания графов. Изоморфизм графов. Связность. Планарность. Критерии

планарности. Виды и свойства деревьев. Алгоритмы обхода вершин графа.

Алгоритм разбиения графа на подграфы заданного типа. Примеры

применения.

Лекция 23. Основы комбинаторики

Перестановки, размещения, сочетания, сочетания с повторениями,

разбиения, покрытия. Рекуррентные соотношения. Понятие о производящих

функциях. Бином Ньютона.

Лекция 24. Перечисление дискретных объектов

Алгоритмы генерирования комбинаторных объектов: перестановок,

размещений, сочетаний, сочетаний с повторениями, покрытий.

Лекция 25. Построение логических функций.

Реализация функций формулами, эквивалентность формул. Свойства

элементарных функций. Принцип двойственности. Разложение функций

алгебры логики по переменным.

Лекция 26. Дизъюнктивные нормальные

формы.

Совершенная дизъюнктивная нормальная

форма. Полнота и замкнутость, примеры полных систем. Важнейшие

замкнутые классы, теорема о полноте.

Лекция 27. Схемы из функциональных элементов

Построение логических формул по схемам из функциональных элементов.

Построение схем из функциональных элементов по формулам.

Лекция 28. Коды для сжатия информации.

Проблематика теории кодирования. Алфавитное кодирование. Критерии

однозначности декодирования. Методы сжатия информации с помощью

кодирования. Коды с минимальной избыточностью.

Лекция 29. Коды повышенной надежности

передачи и хранения информации.

Помехоустойчивое кодирование. Коды Хемминга.

Лекция 30. Коды для защиты информации

Применение кодирования для защиты информации. Криптография.

Коды с секретным и открытым ключом.

Программа практических занятий

Краткое описание технологии занятий. Занятия проводятся с группой под

руководством преподавателя и состоят в решении задач по каждой теме и

разбором их.

Тема 1. Основы формальных языков

Задачи на формализацию высказываний естественного языка.

Тема 2. Язык исчисления высказываний

Задачи на построение таблиц истинности, сокращенных таблиц истинности и

семантических таблиц Бета.

Тема 3. Язык исчисления предикатов

Задачи на формализацию математических утверждений с помощью языка

узкого исчисления предикатов.

Тема 4. Логико-предметные языки

Формулирование математических утверждений на специализированных

логико-предметных языках.

Тема 5. Логический вывод

Построение доказательств формул исчисления высказываний, исчисления

предикатов.

Тема 6. Аксиоматика формальных предметных теорий

Построение формул, однозначно определяющих математические операции.

Тема 7. Язык теории множеств

Формулирование математических утверждений на языке теории множеств.

Тема 8. Наивная теория множеств

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

множеств.

Тема 9. Аксиомы теории множеств

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

Тема 10. Отношения и функции в теории множеств

Определение математических отношений и функций на языке теории

множеств.

Тема 11. Упорядочения

Построение упорядочений с заданными свойствами.

Тема 12. Эквивалентности и разбиения

Построение эквивалентностей и разбиений с заданными свойствами.

Тема 13. Алгебры и алгебраические системы

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

Программа самостоятельной работы студента

Первый семестр.

Неделя Форма контроля

1

2 Выдача индивидуального контрольного домашнего задания 1

3

4 Прием индивидуального контрольного домашнего задания 1

5

6 Выдача индивидуального контрольного домашнего задания 2

7

8 Прием индивидуального контрольного домашнего задания 2

9

10 Выдача индивидуального контрольного домашнего задания 3

11

12 Прием индивидуального контрольного домашнего задания 3

13

14 Выдача индивидуального контрольного домашнего задания 4

15

16 Прием индивидуального контрольного домашнего задания 4

17

18 Зачетная контрольная работа.

Второй семестр

Неделя Форма контроля

1 Выдача индивидуального контрольного домашнего задания 5

2

3 Прием индивидуального контрольного домашнего задания 5

4

5 Выдача индивидуального контрольного домашнего задания 6

6

7 Прием индивидуального контрольного домашнего задания 6

8

9 Выдача индивидуального контрольного домашнего задания 7

10

11 Прием индивидуального контрольного домашнего задания 7

12

13 Выдача индивидуального контрольного домашнего задания 8

14

15 Прием индивидуального контрольного домашнего задания 8

16

17 Итоговая контрольная работа.

Контролирующие материалы

8.1. Вопросы текущего тестирования

8.1.1. Записать в виде формул логико-предметного языка,

используя указанные в скобках предикаты и функции:

8.1.1.1. Все люди смертны (Ч(), С()).

8.1.1.2. Если все люди смертны и Сократ человек, то Сократ смертен.

8.1.1.3. Гена - самый лучший в мире крокодил (K(), Л(,)).

8.1.1.4. Для любого вещественного числа найдется большее его натуральное

число (R(x), N(x)).

8.1.1.5. Функция возведения в квадрат непрерывна (x**2, |x|, x-y, меньше).

8.1.1.6. Существуют рациональные числа, сколь угодно близкие к нулю.

8.1.2. Контрольные вопросы

8.1.2.1. Подходит ли формула P(1) => Ax P(x) под схему A=>B?

8.1.2.2. Подходит ли формула P() => P() под схему B=>A?

8.1.2.3. Подходит ли формула P() = Q() под схему A=>A?

8.1.2.4. Применимо ли правило Ax (A(x)=>B) |- Ex A(x) => B

к формуле Ap (P(x) => P(x))?

8.1.3. Контрольные вопросы

8.1.3.1. Какие множества совпадают:

0, {0}, {0,0}, 1, {0,1}, {1,0}, 2, {1,2}, 3, {0,1,2}, 1 U 2?

8.1.3.2. Сколько элементов в множествах:

{{0,0},{0,0}}, {{0}}, {{0,0}}, {{0},{0}}, {0,{0}}.

8.1.4. Всегда ли выполнено

8.1.4.1. (a,b) = (b,a) => a = b?

8.1.4.2. {(a,b),(b,a)} = {(b,a),(a,b)}?

8.1.4.3. {(a,b)} = {(b,a)}?

8.1.4.4. {(x,x),(y,y)} = {(x,y),(x,y)}?

8.1.4.5. {0,3}x{1,4}?

8.1.4.6. 2x3?

8.1.5. Вопросы

8.1.5.1. Построить наименьший частичный порядок, содержащий

{(1,2),(2,3),(4,3)}.

8.1.5.2. Построить наименьшее отношение эквивалентности,

содержащее

{(1,2),(3,4)}.

8.1.5.3. Построить для отношения эквивалентности из п. 2

соответствующие классы эквивалентности.

8.1.6. Являются ли функциями следующие отношения?

8.1.6.1. {(0,1),(0,2)}.

8.1.6.2. {(1,0),(2,0)}

8.1.7. Являются ли взаимно-однозначными соответствиями следующие

отношения?

8.1.7.1. {(0,1),(0,2)}.

8.1.7.2. {(1,0),(2,0)}

8.1.7.3. {(0,1),(1,0)}.

8.1.7.4. {(0,2),(1,2)}.

8.1.7.5. {(0,0),(1,1)}.

8.1.8. Построить взаимно-однозначное соответствие между множествами

3 и {1,3,5}.

8.1.9. Равномощны ли множества 0 и {0}?

8.1.10. Чему равно:

8.1.10.1. (0,1) +цел (0,1)

8.1.10.2. (1,2) -цел (1,3)

8.1.10.3. (1,2) *цел (0,2)

8.1.10.4. ((0,1),2) + ((1,1),3)

8.1.10.5. ((0,2),3) * ((1,2),3)

8.1.11. Пусть p=R(O,I32), q=I22 o R(O, I32), m=R(I11, p o I33).

Чему равно:

8.1.11.1. p(3,0)

8.1.11.2. p(2,1)

8.1.11.3. q(0)

8.1.11.4. q(2)

8.1.11.5. m(2,0)

8.1.11.6. m(2,1)

8.1.11.7. m(1,2)

8.1.12. Написать программу машины Тьюринга для сложения нескольких

чисел в монадической ("палочковой") системе счисления, разделенных

знаком "+".

8.1.13. Что делает машина Тьюринга

aq> qqr

bq> qqqr

q>1s

aqq>aqqr

bqq>bqqr

aqqq>aqqqr

bqqq>bqqqr

qq> qqqql

qqq> qqqqql

aqqqq> qqqqqql

bqqqqq> qqqqqql

aqqqqq> qqqqqqql

bqqqq> qqqqqqql

qqqq>1s

qqqqq>1s

aqqqqqq>aqqqqqql

bqqqqqq>bqqqqqql

aqqqqqqq> qqqqqqql

bqqqqqqq> qqqqqqql

qqqqqq> qr

qqqqqqq>0s

со словами: "", "a", "ba", "aba", "abba", "baba"?"

8.1.14. Что делает алгоритм

f(ex','ee)=ex':'f(ee);

f(ee)=ee;

f('a,b')=?, f('a')=?, f('a,b,c')=?

8.1.15. Сколько слов длины 5 в алфавите из 10 символов?

8.1.16. Сколько слов длины 16 в алфавите из 2 символов?

8.1.17. Сколькими способами можно разбить 6-элементное множество

на 3 непустых подмножества.

8.1.18. Сколько существует логических функций от

4 логических переменных?

8.1.19. Сколько существует логических функций от

логических функций от 2-х переменных?

8.1.20. Сколько существует логических функций от пар

логических функций от 2-х переменных?

8.1.21. Перечислите все монотонные логические функции 2-х аргументов.

8.1.22. Замкнуты ли классы

8.1.22.1. Логических функций, ограниченных сверху дизъюнкцией всех своих

аргументов?

8.1.22.2. - - - снизу конъюнкцией всех своих аргументов?

8.1.22.3. - - - сверху одним из своих аргументов?

8.1.22.4. - - - снизу - - - - ?

8.1.22.5. - - - сверху первым аргументом?

8.1.22.6. - - - снизу - - ?

8.1.22.7. - - - сверху последним - ?

8.1.22.8. - - - снизу - - ?

8.1.22.9. - - равных конъюнкции аргументов, от которых они зависят?

8.1.22.10. - - - дизъюнкции - - - - - ?

8.1.23. Сколько существует классов изоморфных мультиграфов с двумя

вершинами?

Экзаменационные вопросы

1. Алфавит, слова, выражения, предложения, логические языки.

2. Алгебра логики, функции, таблицы истинности.

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

4. Интерпретация, истинность, тавтологии, выполнимые формулы, модели.

5. Язык исчисления предикатов 1-го порядка.

6. Интерпретация, истинность формул на заданной интерпретации.

7. Выполнимость и общезначимость формулы 1-го порядка, модели.

8. Язык арифметики натуральных чисел.

9. Язык теории слов в конечном алфавите.

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

11. Структура логического вывода в естественной форме записи.

12. Системы аксиом и правила вывода.

13. Правила вывода исчисления высказываний для естественной формы записи.

14. Правила введения и правила удаления.

15. Теорема о полноте исчисления высказываний.

16. Правила вывода для исчисления предикатов.

17. Введение и удаление кванторов.

18. Полнота исчисления предикатов.

19. Узкое исчисление предикатов с равенством.

10. Аксиомы и схемы аксиом равенства.

21. Аксиомы арифметики.

22. Схема аксиом математической индукции.

23. Язык теории множеств.

24. Константы, предикаты и функции теории множеств.

25. Пустое множество.

26. Предикат принадлежности.

27. Принцип экстенсиональности.

28. Функция пары.

29. Функция объединения.

30. Функция канторовой степени.

31. Множество элементов, обладающих заданными свойствами.

32. Парадокс Рассела.

33. Операция выделения, операция параметрического объединения.

34. Аксиома экстенсиональности.

35. Аксиома пустого множества.

36. Аксиома пары.

37. Аксиома объединения (и ее виды).

38. Аксиома выделения и ее виды.

39. Упорядоченная пара, декартово произведение, декартова степень.

40. Бинарное отношение, однозначность отношения, функция.

41. Обратное отношение, взаимно-однозначное соответствие.

42. Суперпозиция и итерация отношений.

43. Инъекция, сюръекция, биекция.

44. Область определения и множество значений.

45. Строгие и нестрогие порядки.

46. Максимальный и минимальный, наименьший и наибольший элементы.

47. Полные порядки.

48. Отношения эквивалентности, факторизация.

49. Алгебраические систем.

50. Натуральные числа в теории множеств.

51. Рекурсивные определения функций в теории множеств.

52. Целые числа в теории множеств.

53. Рациональные числа в теории множеств.

54. Вещественные числа в теории множеств.

55. Ординалы.

56. Равномощность, кардиналы.

57. Примитивная рекурсия.

58. Операция нахождения наименьшего корня (операция минимизации).

59. Операция многоместной суперпозиции.

60. Исходные функциональные константы для порождения рекурсивных функций.

61. Примитивно рекурсивные, частично-рекурсивные и общерекурсивные функции.

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

63. Тезис Черча.

64. Нормальные алгоритмы.

65. Универсальные алгоритмы (универсальные машины), универсальные функции.

66. Неразрешимые проблемы.

67. Рекурсивно разрешимые и перечислимые множества.

68. Примитивно рекурсивные функции множества и отношения.

69. Автоматные функции, множества и отношения.

70. Элементарные функции, множества и отношения

71. Графы.

72. Изоморфизм графов.

73. Связность графов.

74. Планарность графов.

75. Деревья.

76. Алгоритмы обхода вершин графа.

77. Перестановки, размещения, сочетания, сочетания с повторениями.

78. Рекуррентные соотношения в комбинаторике.

79. Производящая функция, бином Ньютона.

80. Алгоритмы генерирования комбинаторных объектов.

81. Дизъюнктивная нормальная форма, совершенная ДНФ

82. Принцип двойственности для логических функций.

83. Полнота и замкнутость систем логических функций.

84. Алфавитное кодирование.

85. Помехоустойчивое кодирование.

86. Методы сжатия информации с помощью кодирования.

87. Применение кодирования для защиты информации.

Примеры (образцы) экзаменационных задач

01. Сформулировать на ЯУИП (U - люди) "Некоторые студенты

[С(x)] получили зачет [З(студент,предмет)] по всем предметам

[П(x)], которые они изучали [И(студент,предмет)].

02. Сформулировать на ЯУИП (U - люди) "Все студенты

[С(x)] получили зачет [З(студент,предмет)] по некоторым предметам

[П(x)], которые они изучали [И(студент,предмет)].

03. Сформулировать на ЯУИП (U - люди) "Все студенты

[С(x)] получили зачет [З(студент,предмет)] по всем предметам

[П(x)] которые они изучали [И(студент,предмет)].

04. Сформулировать на ЯУИП (U - люди) "Некоторые студенты

[С(x)] получили зачет [З(студент,предмет)] по некоторым предметам

[П(x)], которые они изучали [И(студент,предмет)].

05. Сформулировать на ЯУИП (U - люди) "По всем предметам

[П(x)] получили зачет [З(студент,предмет)] некоторые студенты

[П(x)], которые их изучали [И(студент,предмет)].

06. Сформулировать на ЯУИП (U - люди) "По некоторым предметам

[П(x)] получили зачет [З(студент,предмет)] все студенты

[П(x)], которые их изучали [И(студент,предмет)].

07. При каких интерпретациях истинна формула

Ax(C(x)=>EyB(x,y))&EzC(z)=>EtEuB(t,u)?

08. При каких интерпретациях истинна формула

Ax(D(x)=>B(x)\/C(x))&EyD(y)=>EzB(z)\/EuC(u)?

09. При каких интерпретациях истинна формула

Ax(D(x)=>B(x)&C(x))&EyD(y)=>EzB(z)&EuC(u)?

10. При каких интерпретациях истинна формула

Ax(C(x)=>AyB(x,y))&EzC(z)=>EuAvB(u,v)?

11. При каких интерпретациях истинна формула

Ax(C(x)=>EyB(x,y))&EzAu~B(z,u)=>Ev~C(v)?

12. При каких интерпретациях истинна формула

Ax(D(x)=>B(x)\/C(x))&Ez(B(z)\/~C(z))=>Eu~D(u)?

13. При каких интерпретациях истинна формула

Ax(D(x)=>B(x)&C(x))&EyD(y)&Ey~B(y)&Ez~C(z)=>Eu~D(u)?

14. При каких интерпретациях истинна формула

Ax(C(x)=>AyB(x,y))&EzEu~B(z,u)=>Ev~C(v)?

15. Найти {1,2,3}x{4,1}.

16. Найти P({1,3}).

10.4.17. Найти {1,3}{2,1}.

10.5.18. Найти минимальное отношение строгого частичного порядка,

содержащее {(2,1),(1,3),(1,4)}.

10.5.19. Найти минимальное отношение нестрогого частичного порядка,

содержащее {(2,1),(1,3),(1,4)}.

10.5.20. Найти минимальное отношение строгого линейного порядка,

содержащее {(2,1),(1,3),(1,4)}.

10.5.21. Найти минимальное отношение нестрогого линейного порядка,

содержащее {(2,1),(1,3),(1,4)}.

10.5.22. Использовав функциональные символы f, g и предикаты

Меньше и =,

записать в виде формулы ЛПЯ утверждение: Все локальные максимумы

функции f больше всех локальных максимумов g.

10.5.23. Использовав функциональные символы f, g и предикаты Меньше и =,

записать в виде формулы ЛПЯ утверждение: на всех тех отрезках, на

которых функция f убывает, функция g возрастает.

10.5.24. Использовав функциональные символы f, g и предикаты Меньше и =,

записать в виде формулы ЛПЯ утверждение: множества значений f и g

совпадают.

10.5.25. Использовав функциональные символы f, g и предикаты Меньше и =,

записать в виде формулы ЛПЯ утверждение: Каждое значение f больше

некоторого значения g.

10.5.26. Использовав функциональные символы f, g и предикаты Меньше и =,

записать в виде формулы ЛПЯ утверждение: между любыми двумя

значениями f есть хотя бы одно значение g.

10.5.27. Использовав функциональные символы f, g и предикаты Меньше и =,

записать в виде формулы ЛПЯ утверждение: между любыми локальными

максимумами функции f есть локальный максимум функции g.

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

9.1. Основная литература

1. Гаврилов Г.П., Сапоженко А.А. "Сборник задач по дискретной

математике": Учеб.пособие. М.: Наука, 1977-1992. 408 с.

2. Ершов Ю.Л. и др. "Математическая логика", 1973-1987 и далее.

3. Иложарский В.К. "Математическая логика и алгоритмы", 1970.

4. Карпов В.Г., Нощенский В.А. "Математическая логика и дискретная

математика", 1977.

5. Колмогоров А.Н., Драгалин "Введение в математическую логику",

1982.

6. "Математическая логика" / Ред. Столяр А.А., 1991.

7. Мендельсон Э. "Введение в математическую логику", 1971-1984 и

далее.

8. Непейвода Н.Н. "Прикладная логика": Учебное пособие, Ижевск, Изд-во

УдГУ, 1997, 384с.

9. Нефедов В.Н., Осипова В.А. "Курс дискретной математики", 1992

10. Шенфилд Д. "Математическая логика", 1975.

11. Эдельман С.Л. "Математическая логика", 1975.

9.2. Дополнительная литература

Дополнительная литература

1. Александров П.С. "Введение в теорию множеств и общую

топологию", 1977.

2. Верещагин Н.К., Шень А. "Начала теории множеств", 1999.

3. Верещагин Н.К., Шень А. "Языки и исчисления", 2000

4. Клини С.К. "Математическая логика", 1973.

5. Колмогоров А.Н., Драгалин "Математическая логика,

дополнительные главы", 1984.

6. Косовский Н.К. "Основы теории элементарных алгоритмов", 1987.

7. Косовский Н.К., Тишков А.В. "Логики конечнозначных

предикатов на основе неравенств", СПб, 2000.

8. Чень Ч., Ли Р. "Математическая логика и автоматическое

доказательство теорем", 1983.

9. Яблонский С.В. Введение в дискретную математику: Учеб.пособие.

М.: Наука, 1986. 384 с.

10. Кристофидес Н. Теория графов:алгоритмический подход. - М.: Мир,

1978.

9.3. Другие учебно-методические материалы

Материалы по лекциям (А.П.Бельтюков):

URL:dm.ru/~belt/apbmatlo.txt

URL:dm.ru/~belt/apblogic.txt

URL:dm.ru/~belt/apblogir.txt

URL:dm.ru/~belt/discmatq.txt

URL:dm.ru/~belt/work-pgm/clac.htm

Приложение 1

Основное оборудование по дисциплине

Перечень основного оборудования в соответствии с ГОС

по дисциплине «Логика»

специальности «Прикладная информатика (по областям)»

Формы обучения «дневная»

2009/2010 год

№ п/п	Наименование оборудования	Кол-во	Примечание (сведения о наличии, необходимости обновления, приобретения)
1	Компьютерный проектор	1	Наличествует 1

Blog

Рабочая программа по дисциплине «логика» для специальности 351400 Прикладная информатика (по областям) Форма обучения: очная

Содержание

Тема