Программа дисциплины [Введите название дисциплины] для направления/ специальности [код направления подготовки и «Название направлени - umotnas.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Программа дисциплины [Введите название дисциплины] для направления/... 1 197.19kb.
Программа дисциплины [Введите название дисциплины] для направления/... 1 113.15kb.
Программа дисциплины Финансирование проектов частно-государственного... 1 318.69kb.
Программа дисциплины Экономика перекрывающихся поколений для направления/... 1 62.53kb.
Программа дисциплины для направления/ специальности подготовки бакалавра/... 1 57.14kb.
Программа дисциплины для направления/ специальности подготовки бакалавра/... 1 159.67kb.
Программа дисциплины для направления/ специальности подготовки бакалавра/... 1 73.78kb.
Программа дисциплины «Государственно-конфессиональные отношения:... 1 335.27kb.
Программа дисциплины для направления/ специальности 230401. 1 237.41kb.
Программа дисциплины Вероятность и статистика для направления/ специальности 1 98.29kb.
Программа дисциплины «Уголовная политология» 4 746.97kb.
Обеспечение образовательного процесса Оборудованными учебными кабинетами... 1 300.96kb.
Викторина для любознательных: «Занимательная биология» 1 9.92kb.

Программа дисциплины [Введите название дисциплины] для направления/ специальности - страница №1/1




Национальный исследовательский университет «Высшая школа экономики»
Программа дисциплины [Введите название дисциплины] для направления/ специальности [код направления подготовки и «Название направления подготовки» ] подготовки бакалавра/ магистра/ специалиста






Правительство Российской Федерации
Федеральное государственное автономное образовательное учреждение высшего профессионального образования
"Национальный исследовательский университет
"Высшая школа экономики"

Факультет Прикладной математики и кибернетики МИЭМ-НИУ ВШЭ

Программа дисциплины
«Математическая логика»

для направления 010400.62 «Прикладная математика и информатика» подготовки бакалавра


Автор программы:

Сухоцкий Г. В.,gvsukhotskiy@hse.ru


Одобрена на заседании кафедры «Высшая математика» «___»____________ 20 г

Зав. кафедрой Л.И.Кузьмина


Рекомендована учебно-методической комиссией ФПМ и К «___»____________ 20 г

Председатель


Утверждена ученым советом ФПМ и К «___»_____________20 г.

Ученый секретарь

Москва, 2012_

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

1Область применения и нормативные ссылки


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

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

Программа разработана в соответствии с;
ФГОС ВПО для направления 100400.62 «Прикладная математика и информатика» подготовки бакалавра


    Рабочим учебным планом на 2012-2013 учебный год университета для направления 010400.62 «Прикладная математика и информатика» подготовки бакалавра



2Цели освоения дисциплины


Целями освоения дисциплины «Математическая логика» являются

получение представления об основных понятиях, методах и результатах теории вычислимости;

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

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



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


В результате освоения дисциплины студент должен:

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

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

Владеть навыками проведения соответствующих рассуждений

кооперации с коллегами, способностью в качестве

В результате освоения дисциплины студент осваивает следующие компетенции:

способность владеть культурой мышления, уметь аргументировано и ясно строить устную и письменную речь (ОК-1);

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

способность логически верно, аргументировано и ясно строить устную и письменную речь на русском языке, готовить и редактировать тексты профессионального назначения, публично представлять собственные и известные научные результаты, вести дискуссии (ОК7);

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

способность самостоятельно применять методы и средства познания, обучения и самоконтроля для приобретения новых знаний и умений, в том числе в новых областях, непосредственно не связанных со сферой деятельности, развития социальных и профессиональных компетенций, изменения вида своей профессиональной деятельности (ОК-10);


    способность работать в коллективе и использовать нормативные правовые документы в своей деятельности (ОК-13);

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

    способность демонстрации общенаучных базовых знаний естественных наук, матема- тики и информатики, понимание основных фактов, концепций, принципов теорий, свя- занных с прикладной математикой и информатикой (ПК-1);

    способность приобретать новые научные и профессиональные знания, используя со- временные образовательные и информационные технологии (ПК-2);

    способность понимать и применять в исследовательской и прикладной деятельно- сти современный математический аппарат (ПК-3);

    способность приобретать и использовать организационно-управленческие навыки в профессио- нальной и социальной деятельности (ПК-11);



способность готовить научно-технические отчеты, обзоры, публикации по результам выполненных работ (ПК-17).

4Место дисциплины в структуре образовательной программы

Настоящая дисциплина относится к вариативной части математического и естественнонаучного цикла и блоку дисциплин, обеспечивающих математическую подготовку.


Изучение данной дисциплины базируется на следующих дисциплинах:

  • алгебра,

  • математический анализ

Для освоения учебной дисциплины, студенты должны владеть следующими знаниями и компетенциями:

  • основные определения и простейшие базисные факты математического анализа

и линейной алгебры.

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



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


5Тематический план учебной дисциплины







Название раздела

Всего часов

Аудиторные часы

Самостоя­тельная работа

Лекции

Семинары

Практические занятия

1

Элементы теории множеств: счетные множества, сравнения мощностей множеств, теоремы Кантора—Бернштейна и Кантора

16

4




4

8


2

Машина с неограниченными регистрами (МНР), МНР-программы, МНР-вычислимость, тезис Черча

16

4




4

8


3

Универсальные функции, тотальные МНР-вычислимые функции. Разрешимые и перечислимые множества.

24

6




6

12


4

Алгебраические и диофантовы множества. Теорема Матиясевича и 10-я проблема Гильберта.


8


2




2


4

5

Булевы функции, их носитель. ДНФ и СДНФ.

Алгоритм Блейка. Полиномы Жегалкина. Тупиковая ДНФ.


16



4






4


8


6

Функциональное замыкание совокупности булевых функций. Полные совокупности. Классы S, L, M, T0, T1, их функциональная замкнутость и полнота. Теорема Поста о полноте.


8


2





2


4

7

Контактные схемы и булевы функции, ими реализуемые. Проблема минимизации контактных схем. Функция Шеннона. Теоремы Шеннона и Лупанова.




8


2




2


4

8


Формальные исчисления. Исчисление высказываний (ИВ). Теорема об отсутствии в ИВ лишних правил вывода. Критерий выводимости формулы в ИВ. Алгоритм эффективного нахождения вывода по данной выводимой формуле в ИВ.



24

6



6

12


99

Основные понятия логики предикатов. Кванторы всеобщности исуществования. Предваренная нормальная форма.

Итого


24


6




6


12


6Формы контроля знаний студентов


Тип контроля

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

1 год

Параметры

1

2

3

4

Текущий

(8 неделя)



Контрольная работа








*




аудиторная

Текущий


(8 неделя)

Контрольная работа










*

домашняя


Итоговый

Зачет


















6.1Критерии оценки знаний, навыков

6.2



Порядок формирования оценок по дисциплине

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

домашняя контрольная работа во второй половине семестра.

Итоговый контроль – устный экзамен в окончанию семестра.


Результирующая оценка за текущий контроль рассчитывается следующим образом:

Отекущий = 0,5·Окр№1 + 0,5·Окр№2

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

в рабочей ведомости и составляет оценку Оаудиторная. Также учитывается оценка Осам. работа самостоятельной работы студентов: в практических домашних задачах на программирование оценивается функциональность и объем созданных программ; в самостоятельных докладах на семинарах – полнота и глубина освещения темы.

Итоговая оценка по курсу выставляется по следующей формуле:

Оитоговая = 0,5·Оэкзамен +0,3·Отекущий + 0,2·Оаудиторная

где О зачет – оценка за работу непосредственно на зачете.



6.2.1 Таблица соответствия оценок по десятибалльной и системе зачет/незачет


Оценка по 10-балльной шкале

Оценка по 5-балльной шкале

1

1-3 неудовлетворительно

2

3

4

4-5 удовлетворительно

6-7 хорошо


8-10 отлично


5 - ______ __

6

7 _____

8

9

10



7Содержание дисциплины




Тема 1. Элементы теории множеств

1.1. Взаимно однозначное соответствие между множествами. Равномощность множеств. Счетные множества, простейшие теоремы о счетных множествах.

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

1.3. Теорема о равномощности бесконечного множества и его объединения с конечным или счетным множеством.

1.4. Определение неравенства между мощностями множеств. Теорема Кантора—Бернштейна.

1.5. Теорема Кантора. Несчетность множества всех бесконечных последовательностей из 0 и 1.

1.6. Парадоксы теории множеств.

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

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

Ю. П. Шевелев, Дискретная математика, Лань, М., 2008

Г. П. Гаврилов, А. А. Сапоженко, Сборник задач по дискретной математике, Наука, М., 1977



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

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


Тема 2. Вычислимость

2.1. Машина с неограниченными регистрами (МНР). Система команд. Программа. Схема работы МНР по заданной программе.

2.2. МНР-вычислимые функции. Разрешимые предикаты.

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

2.4. Неформальные алгоритмы. Тезис Черча.

2.5. Доказательство существования МНР-невычислимых функций.

2.6. Система нумерации МНР-команд и МНР-программ. Примеры явного описания программ по заданному номеру.

2.7. Построение МНР-невычислимой функции, использующее явную нумерацию программ.

2.8. Универсальная функция для заданного множества МНР-вычислимых функций. Теорема о существовании вычислимой универсальной функции для множества всех МНР-вычислимых функций одного переменного.

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

2.10. Понятие алгоритмически неразрешимой проблемы. Теорема о несуществовании алгоритма, определяющего тотальность/нетотальность элементов множества всех МНР-вычислимых функций. Алгоритмическая неразрешимость проблемы самоприменимости и проблемы остановки. Теорема Райса.

2.11. Разрешимые и перечислимые множества. Теорема о разрешимости любого перечислимого множества. Примеры перечислимого, но неразрешиммого множества, а также неперечислимого множества. Критерий разрешимости множества ( теорема Поста).

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

2.13. Алгебраические подмножества. Диофантовы подмножества. Теорема Матиясеви-ча (без доказательства). 10-я проблема Гильберта и ее отрицательное решение с помощью теоремы Матиясевича.

2.14. Теорема о том, что всякое перечислимое множество есть множество значений некоторой тотальной МНР-вычислимой функции.

2.15. Теорема о том, что множество перечислимо тогда и только тогда, когда оно является множеством неотрицательных значений некоторого многочлена от нескольких переменных с целыми коэффициентами. Приложение: существование «формулы простых чисел».



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

Н. Катленд, Вычислимость. Введение в теорию рекурсивных функций, Мир, М., 1983



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

Н. К. Верещагин, А. Шень, Лекции по математической логике и теории алгоритмов. Вычислимые функции, МЦНМО, М., 1999


Тема 3. Булевы функции

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

3.2. n-мерный единичный куб, его грани в вершины. Нумерация вершин с помощь двоичного разложения целых чисел.

3.3. Определение формулы. Задание булевых функций с помощью формул, вопрос о его единственности. Равносильность формул. Список важнейших равносильностей алгебры логики.

3.4. Носитель (множество истинности) булевой функции. Теорема о носителе конъюнкции (дизъюнкции) булевых функций.

3.5. Элементарная конъюнкция. Правильная элементарная конъюнкция и описание её носителя.

3.6. Дизъюнктивная нормальная форма (ДНФ) булевой функции и совершенная ДНФ (СДНФ). Теорема о существовании единственной СДНФ у любой ненулевой булевой функции. Практический способ нахождения СДНФ.

3.7. Полином Жегалкина булевой функции. Теорема о его существовании и единственности. Линейные булевы функции.

3.8. Сокращенная ДНФ. Правила обобщенного склеивания и поглощения.

3.9. Алгоритм Блейка нахождения СДНФ.

3.10. Тупиковая, минимальная и кратчайшая ДНФ и способ их нахождения.

3.11. Двойственная и самодвойственная булевы функции. Теорема о суперпозиции двойственных булевых функций.

3.12. Монотонные булевы функции Теорема о суперпозиции монотонных булевых функций.

3.13. Функциональное замыкание совокупности булевых функций. Функционально замкнутые совокупности. Полные совокупности. Классы S, L, M, T0, T1, их функциональная замкнутость и полнота.

3.14. Теорема Поста о полноте.

3.15. Контактные схемы и булевы функции, ими реализуемые. Проблема минимизации контактных схем. Функция Шеннона. Теоремы Шеннона и Лупанова.



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

С. Г. Гиндикин, Алгебра логики в задачах, Наука, М., 1972



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

Ю. П. Шевелев, Дискретная математика, Лань, М., 2008

Г. П. Гаврилов, А. А. Сапоженко, Сборник задач по дискретной математике, Наука, М., 1977
Тема 4. Формальные исчисления

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

4.2. Язык, аксиомы и правило вывода исчисления высказываний.

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

4.4. Теорема об отсутствии в исчислении высказываний лишних правил вывода.

4.5. Формулы в исчислении высказываний, являющиеся тавтологией. Критерий выводимости формулы в исчислении высказываний (с доказательством того, что из выводимости следует тавтологичность).

4.6. Алгоритм эффективного нахождения вывода по данной выводимой формуле в исчислении высказываний.

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

В. А. Душский, Исчисление высказываний и его свойства, МИЭМ, М., 2007



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

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

И. А. Лавров, Л. Л. Максимова, Задачи по теории множеств, математической логике и теории алгоритмов, Наука, М., 1984
Тема 5. Логика и исчисление предикатов

5.1. Определение n-местного предиката, его множества истинности.

5.2. Кванторы всеобщности и существования. Геометрическая интерпретация навешива- ния кванторов на предикаты.

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

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

5.4. Общезначимые и выполнимые формулы. Формальный вывод в исчислении предикатов (ИП). Корректность, полнота, неразрешимость ИП в общем случае.



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

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

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

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

Н. К. Верещагин, А. Шень, Лекции по математической логике и теории алгоритмов. Вычислимые функции, МЦНМО, М., 1999



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

7.1Методические рекомендации преподавателю


Нет.

7.2Методические указания студентам


Нет.

8Оценочные средства для текущего контроля и аттестации студента

8.1Тематика заданий текущего контроля


Аудиторная контрольная работа № 1.

Тема: элементы теории множеств и теория вычислимости

Примерные вопросы:

1. Привести пример взаимно однозначного соответствия между интервалом (0,1) и отрезком [0,1].

2. Выписать явно МНР-программу с номером 8. Чему равно значение функции от двух переменных, вычислямой по этой программе, в точке (1,2)? А в точке (1, 1)?

3. Написать программу, вычисляющую функцию f(x,y)= xy+x+1.


Домашняя контрольная работа № 2.

Тема: алгебра логики и исчисление высказываний.

Примерные вопросы:

1. Написать СДНФ для функции f(x1, x2, x3)=(1,1,0,0,10,1,0).Найти её минимальную ДНФ. Вычислить для данной функции её полином Жегалкина.

2. Полна ли система функций {(01101001), (10001101), (00011100)}?

3. Доказать, что в исчислении высказываний ├ (A≡A).



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


  1. Какое отображение называется взаимно однозначным соответствием между множествами? Привести примеры отображений, которые являются и которые не являются взаимно однозначными соответствиями. Установить взаимно однозначное соответствие между множеством всех целых четных чисел и множеством всех целых нечетных чисел.




  1. Какие множествами называются равномощными? Доказать, что множество всех бесконечных последовательностей чисел из 0 и 1 равномощно множеству всех подмножеств множества {1, 2, 3,…}.




  1. Какие множества называются счетными? Привести пример счетного множества. Доказать, что всякое бесконечное подмножество счетного множества само счетно. Доказать, что всякое бесконечное множество содержит счетное подмножество.




  1. Доказать, что объединение конечного или счетного числа конечных или счетных множеств конечно или счетно. Вывести отсюда, что множество всех наборов (a1,…,ad), где d фиксировано, а a1,…ad –целые неотрицательные числа, счетно.




  1. Доказать, что множество всех рациональных чисел счетно. Доказать, что множество всех конечных последовательностей натуральных числе счетно.




  1. Что такое алгебраическое число? Доказать, что множество всех алгебраических чисел счетно.




  1. Доказать, что если A – бесконечное множество, а B – конечное или счетное множество, то A равномощно объединению A с B. Вывести отсюда, отрезок [a, b] равномощен интервалу (a, b) для любых чисел a < b.




  1. Доказать, что отрезок [0,1] равномощен множеству всех бесконечных последовательностей из 0 и 1. Вывести отсюда, что квадрат равномощен отрезку.




  1. Что означает утверждение «мощность множества A не меньше мощности множества B»? Верно ли, что |A|≥|A|? Верно ли, что если |A|≥|B| и |B|≥|C|, то |A|≥|C|? Ответ обосновать.




  1. Доказать теорему Кантора--Бернштейна. Доказать с ее помощью, что шар и куб равномощны.




  1. Доказать теорему Кантора. Вывести из нее, что множество всех бесконечных последовательностей из 0 и 1 несчетно.




  1. Рассказать об известных вам парадоксах теории множеств.




  1. Описать как работает МНР (машина с неограниченными регистрами). Какие в ней используются команды? Что такое программа для МНР? Привести пример.




  1. Что такое МНР-вычислимая функция? Доказать, пользуясь только определением, что f(x,y)=x+y является такой функцией.




  1. Что такое разрешимый предикат? Привести пример.




  1. Доказать, если f(x1,…xn), g1(y1,…,ym),…, gn(y1,…,ym) –- МНР-вычислимые функции, то и f(g1(y1,…,ym),…,gn(y1,…,ym)) - тоже МНР-вычислимая функция.




  1. Что такое неформальный алгоритм? Привести пример. Сформулировать тезис Черча. Привести пример его применения.




  1. Доказать, что существуют МНР-невычислимые функции.




  1. Рассказать как нумеруются МНР-команды и МНР-программы. Выписать МНР-программы, имеющие номера 8,914.15. Какие функции от одного переменного они вычисляют?



  1. Используя нумерацию программ, указать явно МНР-невычислимую функцию.




  1. Что такое универсальная функция для заданного множества МНР-вычислимых функций? Доказать, что для множества всех МНР-вычислимых функций одного переменного существует универсальная вычислимая функция .




  1. Что такое тотальная МНР-вычислимая функция одного переменного? Приведите пример. Доказать, что для множества всех таких функций универсальной вычислимой функции не существует.

  2. Дать определение алгоритмически неразрешимой проблемы. Доказать, что проблема самоприменимости алгоритмически не разрешима.




  1. Какое подмножество в Ns называется разрешимым? А какое называется перечислимым? Привести примеры. Доказать, что не существует общего алгоритма, позволяющего по паре чисел (n, m) узнать останавливается ли вычисление по программе с номером n при начальной конфигурации регистров R1=m, R2=0, R3=0,…




  1. Доказать, что не существует общего алгоритма, который для любой МНР-вычислимой функции одного переменного позволял бы установить тотальна она или нет.




  1. Доказать, что всякое разрешимое подмножество в Ns перечислимо. Обосновать существование неразрешимых и неперечислимых множеств.




  1. Доказать, что в Ns существуют перечислимые подмножества, не являющиеся разрешимыми, например, таковым является при s=1 множество всех таких n, что вычисление по МНР-программе с номером n сходится при начальной конфигурации R1=n, R2=0, R3=0,…




  1. Доказать, что перечислимые подмножества в N --- это в точности проекции на первую координату разрешимых подмножеств в N2.




  1. Что такое алгебраическое подмножество в Ns? Привести пример. Доказать, что всякое алгебраическое подмножество разрешимо.




  1. Какие подмножества в N называются диофантовыми? Сформулировать теорему Матиясевича.




  1. Сформулировать 10-ю проблему Гильберта. Используя теорему Матиясевича, доказать, что 10-я проблема Гильберта имеет отрицательное решение.




  1. Доказать, что всякое перечислимое подмножество в N является множеством значений некоторой тотальной МНР-вычислимой функции одного переменного.




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




  1. Дать определение булевой функции (функции алгебры логики) от n переменных. Дать определения конъюнкции, дизъюнкции, импликации, отрицания и эквивалентности.




  1. Сколько всего имеется булевых функций от n переменных? Ответ обосновать. Что такое таблица истинности булевой функции? Привести пример.




  1. Что такое n-мерный единичный куб, его вершины и грани? Как нумеруются его вершины с помощью двоичного разложения чисел? Проиллюстрировать эти понятия на примере n=1, 2, 3.




  1. Что такое формула? Как булевы функции задаются с помощью формул? Единственно ли такое задание? Привести примеры.




  1. Указать важнейшие равносильности формул алгебры логики. Проиллюстрировать на примере одной из них принцип их доказательства.




  1. Что такое носитель булевой функции? Доказать, что носитель конъюнкции (дизъюнкции) булевых функции f и g от n переменных равен пересечению (объединению) носителей функций f и g.




  1. Что такое элементарная конъюнкция? Когда она называется правильной? Доказать, что носителем элементарной конъюнкции от n переменных является грань n-мерного куба. Привести примеры.




  1. Что такое дизъюнктивная нормальная форма булевой функции? Что такое ее совершенная дизъюнктивная нормальная форма (СДНФ)? Привести примеры. Доказать, что всякая ненулевая булева функция обладает единственной СДНФ.




  1. Описать практический способ нахождения СДНФ. Привести пример.




  1. Что такое полином Жегалкина? Сколько всего имеется различных полиномов Жегалкина от n переменных? Ответ обосновать. Доказать, что всякая булева функция может быть реализована полиномом Жегалкина и притом единственным. Привести пример.




  1. Что такое сокращенная дизъюнктивная нормальная форма булевой функции? Привести пример. Сформулировать и обосновать правила обобщенного склеивания и поглощения.




  1. Сформулировать алгоритм Блейка нахождения сокращенной дизъюнктивной нормальной формы. Привести пример его применения.




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




  1. Что такое двойственная и что такое самодвойственная булевы функции? Привести примеры. Доказать, что если F(x1,…xn)=f(g1(x1,…,xn),…fd(x1,…,xn)), то F*(x1,…xn)=f*(g*1(x1,…,xn),…f*d(x1,…,xn)).




  1. Что такое монотонная булева функция? Привести примеры. Доказать, что если f(y1,…,yd), g1(x1,…,xn),…, g1(x1,…,xn) монотонны, то и f(g1(x1,…,xn),…fd(x1,…,xn)) монотонна.




  1. Что такое функциональное замыкание совокупности булевых функций? Какая совокупность называется функционально замкнутой? Какая совокупность называется полной? Привести примеры. Описать классы S, L, M, T0, T1 и доказать, что они функционально замкнуты и неполны.




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



  1. Что такое контактная схема и булева функция, реализуемая контактной схемой? Привести пример. Как по данной схеме записать формулой реализуемую этой схемой булеву функцию? Привести пример.




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




  1. В чем состоит проблема минимизации контактных схем? Доказать, что для функции Шеннона L(n) имеет место неравенство L(n) ≤ n2n. Сформулировать теоремы Шеннона и Лупанова.




  1. Описать компоненты, из которых состоит любое формальное исчисление, -- язык, аксиомы, правила выводаю Что такое вывод? Привести пример формального исчисления.




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




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




  1. Объяснить почему ни одно из правил вывода в исчислении высказываний не является лишним.




  1. Какая формула в исчислении высказываний называется тавтологией? Привести примеры.

Сформулировать критерий выводимости формулы в исчислении высказываний. Доказать одну его часть: если формула выводима, то она является тавтологией. Сформулировать алгоритм, с помощью которого по заданной выводимой в исчислении высказываний формуле можно эффективно найти ее вывод.
59.Дать определение n-местного предиката. Привести примеры.
60. Описать процедуру навешивания кванторов всеобщности и существования в логике предикатов. Привести примеры.
61.Дать определение связанных и свободных переменных в формулах логики предикатов. Привести примеры.

62. Определить множество истинности предиката. Сформулировать и обосновать, как преоб- разуются множества истинности предикатов при действии на них основных логических связок.


63. Изложить геометрическую интерпретацию навешивания кванторов на предикаты. Привести примеры. Выписать формулы пронесения отрицания через кванторы. Доказать одну из этих формул.

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

65. Дать определение предваренной нормальной формы для формулы логики предикатов. Привести примеры. Доказать, что любая формула логики предикатов может быть приведена к предваренной нормальной форме.

66. Изложить алгоритм приведения формулы логики предикатов к предваренной нормальной форме. Привести примеры его применения.

67. Рассказать об основных понятиях исчисления предикатов. Дать определение алфавита исчисления предикатов (ИП), сигнатуры языка. Привести примеры.

68.Дать определение терма, атомарной формулы, формулы в ИП. Привести примеры. Дать определение связанного и свободного вхождений переменной в формулу ИП, замкнутой формулы. Привести примеры.

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

70. Дать определение общезначимой и выполнимой формул. Привести примеры.

71. Дать описание аксиом и правил вывода в ИП. Привести пример формального вывода в ИП.

72. Сформулировать теорему о корректности ИП и теорему К.Гёделя о полноте ИП. Сформулировать теорему А.Чёрча о неразрешимости в общем случае ИП.


Примеры заданий промежуточного /итогового контроля

Нет.

9Учебно-методическое и информационное обеспечение дисциплины

9.1Базовый учебник


Нет

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


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

Н. Катленд, Вычислимость. Введение в теорию рекурсивных функций, Мир, М., 1983

Н. К. Верещагин, А. Шень, Лекции по математической логике и теории алгоритмов. Вычислимые функции, МЦНМО, М., 1999

В. А. Душский, Исчисление высказываний и его свойства, МИЭМ, М., 2007

Ю. П. Шевелев, Дискретная математика, Лань, М., 2008

С. Г. Гиндикин, Алгебра логики в задачах, Наука, М., 1972

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

Г. П. Гаврилов, А. А. Сапоженко, Сборник задач по дискретной математике, Наука, М., 1977


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


В. А. Успенский, Н. К. Верещагин, В. Е. Плиско, Вводный курс математической логики, Физматлит, М., 2002

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



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

9.4Справочники, словари, энциклопедии


Не используются

9.5Программные средства


Не используются


9.6Дистанционная поддержка дисциплины


Не предусмотрена

10Материально-техническое обеспечение дисциплины


Не используется

Приложение











  1. Итоговая оценка за экзамен/ зачет

    Результирующая оценка
    за дисциплину
    (Выставляется в диплом)







    Самостоятельная внеаудиторная работа студентов













    Выставление оценки Осам.работа по 10-балльной

    шкале за аудиторную работу студента.



    (Оценка выставляется только при решении преподавателя оценивать данный вид деятельности студента)

    Выставление оценки за итоговый контроль (зачет/экзамен) в 10 балльной системе

    1

    Определение весов q1 и q2 (ВНИМАНИЕ, Сумма удельных весов должна быть равна единице: ∑qi = 1, при этом, 0,2 ≤ qi 0,8)







    2

    Орезульт =

    q1·Оитог.контроль + q2·Онакопленная








    Определение весов k1 k2 k3 (ВНИМАНИЕ, сумма ki =1, в случае, если преподаватель не учитывает аудиторную и самостоятельную внеаудиторную работу студентов, то k2 и k3 равны 0 (нулю), а k1=1).










    Расчет накопленной оценки

    Онакопленная= k1* Отекущий + k2* Оауд + k3* Осам.работа

    Что получается в результате

    Онакопленная*

    Оитог.контроль

    Орезультирующая*
    Формирование оценки по дисциплине, если она читается несколько этапов (модулей) поясним на примере дисциплины читаемой 3 этапа (таблица 2).

Таблица 2.Формирование оценки по дисциплине: если дисциплина читается несколько этапов (модулей)





Промежуточная оценка
за 1 этап

Промежуточная оценка
за 2 этап

Накопленная оценка 3 (за 3 тап)

Итоговая оценка
за экзамен/ зачет

Результирующая оценка
за дисциплину

(Выставляется


в диплом)

Элемент оценки

Накопленная
оценка 1

Оценка за экзамен/ зачет

(по окончанию этапа 1) (ВАЖНО!


Не является блокирующей)

Накопленная
оценка2

Оценка за экзамен/ зачет

(по окончанию этапа 2)



(ВАЖНО!
Не является блокирующей)

Текущий контроль

Аудиторная работа

Самостоятельная внеаудиторная работа студентов

Текущий контроль

Аудиторная работа

Самостоятельная внеаудиторная работа студентов

Текущий контроль

Аудиторная
работа

Самостоятельная внеаудиторная работа студентов

Действия
преподавателя

действия преподавателя в рамках каждого этапа соответствуют действию преподавателя
по формированию оценки,
если дисциплина читается один этап (модуль) (таблица 1)

действия преподавателя в рамках каждого этапа соответствуют действию преподавателя
по формированию оценки,
если дисциплина читается один этап (модуль) (таблица 1)

действия
преподавателя
(таблица 1)

Выставление оценки за итоговый контроль (зачет/экзамен) в 10 балльной системе

Определение весов q1 и q2 (ВНИМАНИЕ, Сумма удельных весов должна быть равна единице: ∑qi = 1, при этом, 0,2 ≤ qi 0,8)

Орезульт итог =

q1·Оитог.контроль +

q2·Онакопленная

Результат

этап

Опромежуточная 1*

Опромежуточная 2*

Онакопленная 3*

Оитог.контроль

Орезультирующая Итог*

ИТОГ

Онакопленная Итоговая=промежут 1+ Опромежут 2+ Онакопленная 3):кол-во модулей

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