Лекции по математической логике миэм, фэ, 2 курс, 3 семестр Осенний семестр 2009/2010 учебного года Группы к-31, 32



Скачать 54.15 Kb.
Дата07.11.2012
Размер54.15 Kb.
ТипЛекции



22.10.12, М.

Лекции

по математической логике
МИЭМ, ФЭ, 2 курс, 3 семестр

Осенний семестр 2009/2010 учебного года

Группы К-31, 32

Лектор – доцент, к. ф.-м. н. К. К. Андреев

Вопросы к теоретическому зачёту

Глава 1. Булевы функции
§ 1.1. Основные понятия
1.1.1. Декартово произведение

  1. Дать определения декартова произведения двух множеств, декартова квадрата произ­вольного множества. Привести примеры. Записать формулы, выражающие число элементов де­картова произведения и декартова квадрата.

1.1.2. Декартова степень

  1. Дать определение декартовой степени произвольного множества. Привести пример. За­писать формулу, выражающую число элементов декартовой степени.

1.1.4. Определение булевой функции

  1. Дать определение булевой функции от n переменных; привести примеры.

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

§ 1.2. Свойства булевых функций


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

§ 1.3. Дизъюнктивные нормальные формы (ДНФ)
1.3.1. Экспоненциальные обозначения в конъюнкциях

  1. Дать определение элементарной конъюнкции от данных переменных. Рассказать об экс­по­ненциальных обозначениях в конъюнкциях.

1.3.2. Лемма о равенстве двух булевых функций

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

1.3.3. Теорема о совершенной ДНФ

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

1.3.4. Определение ДНФ

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

Глава 2. Логические исчисления
§ 2.1. Определение исчисления высказываний (ИВ)
2.1.1. Язык ИВ

  1. Изложить определение языка исчисления высказываний (ИВ): определения алфа­вита, слова, формативной последовательности, формулы.

2.1.2. Аксиомы ИВ

  1. Привести список 11 аксиом исчисления высказываний. Показать (на примере одной из них), что все они являются формулами ИВ.

2.1.3. Правила вывода

  1. Дать определение подстановки в слово. Привести пример. Сформулировать предложе­ние о подста­новке в формулу. Дать определения правил вывода ИВ (правил подста­новки и правила modus ponens).


§ 2.2. Формальные выводы
2.2.1. Определение формального вывода в ИВ

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

2.2.2. Пример формального вывода в ИВ

  1. Привести (с обоснованием) пример формального вывода в ИВ (доказать выводи­мость формулы (A A)).

2.2.3. Формальный вывод из гипотез

  1. Дать определение формального вывода из гипотез (в ИВ). Дать определение фор­мулы, выводимой из данного списка гипотез.

2.2.4. Пример формального вывода из гипотез

  1. Привести пример формального вывода из гипотез.

§ 2.3. Теорема дедукции
2.3.1. Лемма к теореме дедукции

  1. Сформулировать и доказать лемму к теореме де­дукции.

2.3.2. Формулировка теоремы дедукции

  1. Сформулировать теорему дедукции. Доказать теорему, обратную к теореме дедук­ции.

2.3.3. Доказательство теоремы дедукции в частных случаях

  1. Доказать теорему дедукции в трёх частных случаях.

2.3.4. Доказательство теоремы в общем случае

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


§ 2.4. Критерий выводимости
2.4.1. Понятие интерпретации формулы

  1. Дать определение интерпретации формулы ИВ (во множестве булевых функций).

2.4.2. Формулировка критерия выводимости

  1. Сформулировать критерий выводимости в ИВ.

2.4.3. Доказательство теоремы в одну сторону

  1. Сформулировать и частично доказать критерий выводимости в ИВ.

§ 2.5. Непротиворечивость ИВ
2.5.1. Определение противоречивости

  1. Объяснить, как может быть определено понятие противоречивости ИВ (три вари­анта определения).

2.5.2. Доказательство непротиворечивости ИВ

  1. Доказать, что ИВ является непротиворечивым по любому из трёх вариантов определе­ния противоречивости.

§ 2.6. Исчисление предикатов
2.6.1. Определение предиката

  1. Дать определение n-местного предиката. Привести примеры.

2.6.2. Кванторы

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

2.6.2. Свободные и связанные переменные в математике

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

2.6.4. Язык исчисления предикатов (первого порядка)

  1. Рассказать о языке (исчисления предикатов) первого порядка.

2.6.5. Примеры сигнатур в математике

  1. Привести примеры сиг­натур.

  2. Сформулировать аксиомы арифметики G. Peano.

2.6.6. Понятия терма и формулы

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

2.6.7. Пронесение отрицания через кванторы

  1. Записать формулы пронесения отрицания через кванторы.

2.6.8. Пример из математического анализа

  1. Объяснить (на примере из математического анализа) невозможность перестановки кванторов в общем случае.


Глава 3. Теория алгорифмов (07.11.09)
§ 3.1. Понятие вычислимой функции

3.1.1. Машина с неограниченными регистрами (МНР)

  1. Дать определение машины с неограниченными регистрами (МНР), определение про­граммы для такой машины.

3.1.2. Вычисление функций на МНР

  1. Рассказать о реализации функций натурального аргумента на МНР.

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

3.1.3. Пример невычислимой функции

  1. Привести (с обоснованием) пример невычислимой функции.

§ 3.2. Счётные и несчётные множества (14.11.09)

3.2.1. Определение счётного множества

  1. Дать определение счётного множества. Привести примеры счётных множеств. Дока­зать, что подмножество счётного множества не более чем счётно.


3.2.2. Пример несчётного множества


  1. Доказать, что множество всевозможных бесконечных последовательностей нату-раль­ных чисел несчётно (теорема G. Cantor’а).


3.2.3. Несчётность множества всех действительных чисел


  1. Доказать, что множество всех действительных чисел несчётно (теорема G. Cantor’а).


3.2.4. Счётность множества всех вычислимых функций (21.11.09)


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

3.2.5. Существование невычислимой функции

  1. Доказать существова­ние невычислимой функции.

§ 3.3. Нумерация программ

3.3.1. Нумерация N2 и N3

  1. Рассказать о нумерации N2 и N3.

3.3.2. Нумерация команд

  1. Рассказать о нумерации команд для МНР.

3.3.3. Нумерация программ

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

§ 3.4. Универсальные функции (28.11.09)

  1. Дать определение функции, универсальной для данного класса (множества) функций (натурального аргумента). Доказать, что универсальная функция существует тогда и только то­гда, когда данный класс счётен. Доказать существование универсальной вычислимой функции.



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

  2. Доказать, что универсальная вычислимая функция не может быть продолжена до всюду определённой вычислимой функции. (05.12.09.)

§ 3.5. Определение алгорифма

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

  1. Сформулировать понятие алгорифма.

  2. Сформулировать тезис Church’а.

3.5.2. Невозможность некоторых алгорифмов

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

  2. Доказать, что не существует алгорифма проверки корректности программы.

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

Похожие:

Лекции по математической логике миэм, фэ, 2 курс, 3 семестр Осенний семестр 2009/2010 учебного года Группы к-31, 32 iconЛекции по математической логике миэм, фпм, 2 курс, 4 семестр Весенний семестр 2010/2011 учебного года Группы м-41−46
Дать определения декартова произведения двух множеств, декартова квадрата произ­вольного множества. Привести примеры. Записать формулы,...
Лекции по математической логике миэм, фэ, 2 курс, 3 семестр Осенний семестр 2009/2010 учебного года Группы к-31, 32 iconЛекции по линейной алгебре и аналитической геометрии фпм, 2 курс Осенний семестр 2010/2011 учебного года
Дать определение скалярного произведения, привести примеры. (Стр. 6, 7 и 9 методички.)
Лекции по математической логике миэм, фэ, 2 курс, 3 семестр Осенний семестр 2009/2010 учебного года Группы к-31, 32 iconРасписание экзаменов 1 курс осенний семестр (1) 2011-2012 учебного года

Лекции по математической логике миэм, фэ, 2 курс, 3 семестр Осенний семестр 2009/2010 учебного года Группы к-31, 32 iconКалендарно-тематический план практических занятий по математике на весенний семестр 2009-2010 учебного года 1 курс

Лекции по математической логике миэм, фэ, 2 курс, 3 семестр Осенний семестр 2009/2010 учебного года Группы к-31, 32 iconЛекции по линейной алгебре и аналитической геометрии фпм, 1 курс Весенний семестр 2009/2010 учебного года
...
Лекции по математической логике миэм, фэ, 2 курс, 3 семестр Осенний семестр 2009/2010 учебного года Группы к-31, 32 iconРасписание экзаменов осенний семестр 2011-2012 учебного года

Лекции по математической логике миэм, фэ, 2 курс, 3 семестр Осенний семестр 2009/2010 учебного года Группы к-31, 32 iconВопросы к экзамену По дисциплине "Системы искусственного интеллекта". Осенний семестр 2008/2009 учебного года
Искусственный интеллект как научная область. Основные направления исследований. Классификация интеллектуальных систем
Лекции по математической логике миэм, фэ, 2 курс, 3 семестр Осенний семестр 2009/2010 учебного года Группы к-31, 32 iconРасписание занятий 6 курса лечебного факультета на весенний семестр 2009 2010 учебного года

Лекции по математической логике миэм, фэ, 2 курс, 3 семестр Осенний семестр 2009/2010 учебного года Группы к-31, 32 iconРасписание занятий студентов 1 курса педиатрического факультета на 1 семестр 2009/2010 учебного года

Лекции по математической логике миэм, фэ, 2 курс, 3 семестр Осенний семестр 2009/2010 учебного года Группы к-31, 32 iconПлан лекций по частной гистологии для студентов 2-го курса лечебного, педиатрического и медико-профилактического факультетов на осенний семестр 2012 2013 учебного года
Краткое содержание лекции (подчёркнутые вопросы освещаются студентам педиатрического факультета)
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org