Материалы к промежуточному и итоговому контролю.
Контрольная работа 1
Пусть значение высказывания  истинное. Что можно сказать о значениях высказывания 
С помощью истинностных таблиц проверьте, являются ли эквивалентными формулы A и B. A=
С помощью таблицы истинности и эквивалентных преобразований привести формулу к ДНФ, КНФ,СКНФ и СДНФ.
Постройте релейно-контактную схему с заданной функцией проводимости 
Контрольная работа 2
Является ли тождественно-истинными формулы:
 ;  .
Докажите, что функция  примитивно рекурсивная.
Пусть для слов в алфавите  заданы подстановки
Примените к слову abcddacba.
Определите, в какое слово переработает МТ слово 111*11, исходя из начального стандартного состояния. МТ задана функциональной схемой.
Самостоятельная работа по теме «Предикаты»
1.Найти формулы ПНФ:
x(A(x) B(y))y(B(y) A(x))
x( A(x)x( C(x)))x((C(x)A(x))
x(A(x)x(B(x)))y( A(x) C(y)C(y)B(x))
x(A(x)x(B(y)))x( A(x) B(y))
x(A(x)B(y))y(A(x)(B(y)C(z))z(A(x)C(z))
x(A(x)y(B(y)C(z)))z(A(x)B(y)C(z))
x(A(x)B(z))y(C(y)A(x))z(C(y)B(z))
x(A(x)B(y))y((C(y)A(x))(C(y)y(B(y)))
x(A(x)B(y))y(A(x)(B(y)C(z)))(A(x)z(C(z)))
x(A(x)B(y)A(x)y(B(y)C(z)))(A(x)z(C(z)))
x(A(x)z(B(y)C(z)))y(B(y)(A(x)C(z)))
x(A(x)z(B(y)C(z)))y(B(y)(A(x)C(z)))
(x(A(x))x(B(x)))z((B(x)C(z))(A(x)C(z)))
(x( A(x))x( B(x)))( B(x)A(x))
(x(A(x)))(x(B(x)))y(C(y)A(x)C(y)B(x))
x( A(x)y(B(y)))( B(y)A(x))
(x(B(x))x(A(x)))y((A(x)C(y))( C(y)B(x)))
x( A(x)y(B(y)))(B(y)A(x))
x( A(x)y( B(y)))(B(y)A(x))
x(A(x)B(x))y(B(x)C(y)z(C(y)D(z)))
2.Какие из нижеприведенных формул являются тождестивенно истинными:
x(P1(x))x(P2.(x))x(P1(x)P2.(x));
y(P1.(x))y (P2.(x))y(P1.(x)(P2.(x));
x(P1(x)P2.(x))x(P1(x))x(P2.(x));
y(P1.(x)(P2.(x))y(P1.(x))y (P2.(x))
3.Докажите выводимость заключения методом дедукции:
a) x(P1.(x) P2.(x)); x(P3.(x)P1.(x))
 x(P3.(x) P2.(x));
б ) x(y(P21.(x; y)P2.(y) y(P3.(y)P24.(x; y)))
x(P3.(x)xy(P21.(x; y) P2.(y)));
в ) x(P1.(x)P2.(x) P3.(x)); x(P1.(x) P4.(x))
x(P4.(x)P3.(x)).
4.Докажите выводимость заключения по принципу резолюции:
x(P1.(x)y(P2.(y) P23.(x; y)));
x(P1.(x)y(P4.(y) P23.(x; y)))
 y(P2.(y)P4.(y)).
Вопросы к экзамену
Логика и интуиция. Логика традиционная и математическая логика.
Высказывания и операции над ними.
Формулы алгебры высказываний
Тавтологии алгебры высказываний. Основные правила получения тавтологий.
Логическая равносильность формул. Примеры равносильных формул. Равносильные преобразования формул.
Нормальные формы для формул алгебры высказываний. Представление формул алгебры высказываний совершенными дизъюнктивными нормальными (СДН) формами и совершенными конъюнктивными нормальными (СКН) формами. Два способа приведения формулы алгебры высказываний к совершенной нормальной форме
Логическое следование формул. Следование и равносильность формул. Правила логических умозаключений.
Приложение алгебры высказываний к логико – математической практике.
Методы доказательства математических теорем. Дедуктивные и индуктивные умозаключения. Правильные и неправильные дедуктивные умозаключения.
Булевы функции. Происхождение булевых функций. Булевы функции от одного аргумента. Булевы функции от двух аргументов. Свойства дизъюнкции, конъюнкции и отрицания. Свойства эквивалентности, импликации и отрицания. Выражение одних булевых функций через другие.
Булевы функции от n аргументов. Понятие булевой функции. Число булевых функций. Выражение булевых функций через конъюнкцию, дизъюнкцию и отрицание.
Булевы функции и формулы алгебры высказываний. Нормальные формы булевых функций.
Полные системы булевых функций. Специальные классы булевых функций. Теорема Поста о полноте системы булевых функций.
Применение булевых функций к релейно-контактным схемам. Идея применения. Две основные задачи теории релейно-контактных схем. Релейно-контактные схемы в ЭВМ.
Двоичный полусумматор. Одноразрядный двоичный сумматор. Шифратор и дешифратор
Система аксиом и теория формального вывода. Теорема о дедукции и следствия из неё. Применение теоремы о дедукции.
Производные правила вывода.
Полнота формализованного исчисления высказываний. Теорема адекватности.
Непротиворечивость формализованного исчисления высказываний. Разрешимость формализованного исчисления высказываний.
Независимость системы аксиом формализованного исчисления высказываний.
Понятие предиката. Классификация предикатов. Множество истинности предиката. Равносильность и следование предикатов
Логические операции над предикатами. Отрицание предиката. Конъюнкция двух предикатов. Дизъюнкция двух предикатов. Свойства отрицания, конъюнкции и дизъюнкции. Импликация и эквивалентность двух предикатов.
Кванторные операции над предикатами. Квантор общности. Квантор существовании. Численные кванторы. Ограниченные кванторы.
Понятие формулы логики предикатов. Классификация формул логики предикатов. Тавтологии логики предикатов
Равносильные преобразования формул и логическое следование формул логики предикатов.
Проблемы разрешения для общезначимости и выполнимости формул.
Применение логики предикатов к логико-математической практике.
Формализованное исчисление предикатов. Первоначальные понятия. Система аксиом исчисления предикатов. Правила вывода. Теория формального вывода.
Неформальные аксиоматические теории. Примеры аксиоматических теорий. Интерпретации и модели аксиоматической теории. Свойства аксиоматической теории.
Формальные аксиоматические теории. Понятие формальной аксиоматической теории.
Формализованное исчисление высказываний как формальная аксиоматическая теория. Формализация теории аристотелевых силлогизмов.
Свойства формализованного исчисления предикатов. Непротиворечивость формализованного исчисления предикатов. Теорема Гёделя о существовании модели. Полнота и адекватность формализованного исчисления предикатов. Неполнота формализованного исчисления предикатов в абсолютном и узком смыслах. Теорема компактности.
Интуитивное представление об алгоритмах.
Машины Тьюринга. Определение машины Тьюринга. Применение машин Тьюринга к словам.
Конструирование машин Тьюринга. Вычислимые по Тьюрингу функции. Правильная вычислимость функций на машине Тьюринга. Композиция машин Тьюринга. Тезис Тьюринга (основная гипотеза теории алгоритмов) Машины Тьюринга и современные электронно-вычислительные машины.
Рекурсивные функции. Основные понятия теории рекурсивных функций и тезис Чёрча. Примитивно рекурсивные функции. Примитивная рекурсивность предикатов. Вычислимость по Тьюрингу примитивно рекурсивных функций. Функции Аккермана. Оператор минимизации.
Общерекурсивные и частично рекурсивные функции. Вычислимость по Тьюрингу частично рекурсивных функций. Частичная рекурсивность функций, вычислимых по Тьюрингу.
Характеристики сложности алгоритмов.
Пропозициональные логики: интуиционистские логики, многозначные логики, нечеткие логики и нечеткие множества, модальные логики, временные (темпоральные логики).
Предикатные логики.
Предикатные временные логики и их приложение к программированию.
Алгоритмическая логика Хоара.
Методические рекомендации по освоению учебного материала.
Методические рекомендации преподавателю:
При проведении практических занятий по математической логике и теории алгоритмов рекомендуется:
уделять внимание разбору теоретических задач, предлагаемых на лекциях и на семинарских занятиях;
уделять внимание краткому повторению теоретического материала, который используется при решении упражнений и задач;
осуществлять регулярную проверку домашних заданий;
ставить проблемные вопросы, по возможности использовать примеры и задачи с практическим содержанием;
использовать при проведении практических занятий активные методы обучения;
развивать математическую логику у студентов.
Методические указания студентам:
Учиться преодолевать самый высокий уровень непонимания материала («непонятно, что непонятно»).
При разборе примеров в аудитории или при выполнении домашних заданий целесообразно каждый шаг обосновывать теми или иными теоретическими положениями.
При изучении теоретического материала не задерживать внимание на трудных и непонятных местах, смело их пропускать и двигаться дальше, а затем возвращаться к тому, что было пропущено (часто последующее проясняет предыдущее).
При чтении учебников и лекционных материалов активно отмечать карандашом непонятные места. Карандаш легко стирается, когда вопрос можно снять.
С первых студенческих дней конструировать собственный стиль понимания сути изучаемого материала. Математические дисциплины в этой ситуации являются наиболее успешным полигоном.
Самостоятельная работа студентов. Аудиторная самостоятельная работа студентов по дисциплине выполняется на учебных занятиях под непосредственным руководством преподавателя и по его заданию. Она включает: текущие консультации; коллоквиум как форма контроля освоения теоретического содержания дисциплины (в часы консультаций); прием и разбор домашних заданий (в часы практических занятий).
Внеаудиторная самостоятельная работа выполняется студентом по заданию преподавателя, но без его непосредственного участия. Она включает: формирование и усвоение содержания конспекта лекций, а также самостоятельное изучение отдельных вопросов на базе рекомендованной преподавателем учебной литературы, включая информационные образовательные ресурсы (электронные учебники, электронные библиотеки); написание рефератов; подготовка к выступлению на конференции; подготовка к семинарам, их оформление; выполнение микроисследований; выполнение домашних заданий в виде решения отдельных задач, проведения типовых расчетов, расчетно-компьютерных и индивидуальных работ по отдельным разделам содержания дисциплины; компьютерный текущий самоконтроль и контроль успеваемости.
Для того, чтобы заработать то количество баллов, которое вы видите в тематическом плане дисциплины «Математическая логика и теория алгоритмов» по каждой теме, вам необходимо сделать задание по данной теме на оценку «отлично». В противном случае преподаватель имеет право снять несколько баллов. Снять баллы преподаватель может и за пропущенные семинарские или лекционные занятия.
Баллы, характеризующие успеваемость студента по дисциплине, набираются им в течение всего периода обучения за изучение дидактических единиц.
При выборе критериев оценки освоения студентом программы дисциплины в обязательном порядке учитывается: выполнение программы в части лекционных, практических занятий; выполнение предусмотренных программой аудиторных и внеаудиторных контрольных и иных письменных работ. Преподаватель осуществляет текущий контроль и выставляет рейтинговый балл по каждой контрольной точке модуля.
Максимальная сумма баллов, набираемая студентом по дисциплине (за один семестр), равна 100. Студент, набравший менее 60 баллов получает итоговую оценку – неудовлетворительно, от 61 до 75 – удовлетворительно, от 76 до 90 - хорошо, 91 и выше баллов - отлично.
|
