Методичка по матлогике

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ – УЧЕБНО- НАУЧНО-ПРОИЗВОДСТВЕННЫЙ КОМПЛЕКС» УЧЕБНО-НАУЧНО-ИССЛЕДОВАТЕЛЬСКИЙ

ИНСТИТУТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

Кафедра «Информационные системы»

И.С. Константинов, В.А. Ноздрачева, А.В. Артемов

МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ВЫПОЛНЕНИЮ КУРСОВОЙ РАБОТЫ

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

Дисциплина – «Математическая логика и теория алгоритмов» Направления подготовки – 230400 «Информационные системы и технологии», 230700 «Прикладная информатика», 231000 «Программная инженерия»

Печатается по решению редакционно-издательского совета Госуниверситета-УНПК

Орел, 2012

PDF created with pdfFactory Pro trial version www.pdffactory.com

Авторы: доктор технических наук, профессор кафедры «Информационные системы» И.С. Константинов,

доцент кафедры «Информационные системы», кандидат экономических наук В.А. Ноздрачева,

доцент кафедры «Информационные системы», кандидат технических наук А.В. Артемов

Рецензент: кандидат технических наук, доцент кафедры «Информационные системы» В.Н. Волков

Методические указания предназначены для студентов направлений подготовки: 230400, 230700, 231000 очной (дневной)

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

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

Редактор Фролов А.И. Технический редактор Демидов А.В.

ФГБОУ ВПО «Госуниверситет-УНПК» Лицензия ИД 00670 от 5.01.2000

Подписано к печати ___________г. Формат 60×84 1\16 Печать офсетная Уч.-изд. л. ___. Усл. печ. л. ___. Тираж __ экз. Заказ №____

Отпечатано с готового оригинал-макета на полиграфической базе Госуниверситета-УНПК

302030, г. Орел, ул. Московская, 65

© ФГБОУ ВПО «Госуниверситет-УНПК», 2012

PDF created with pdfFactory Pro trial version www.pdffactory.com

PDF created with pdfFactory Pro trial version www.pdffactory.com

1 Общие положения

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

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

−закрепление, углубление, обобщение знаний, полученных в теоретических курсах, и применение этих знаний к комплексному решению конкретной задачи;

−привитие навыков самостоятельной работы с литературой, в том числе со справочной литературой, ГОСТами, нормами и типовыми решениями;

−умение самостоятельно систематизировать и изложить знания, полученные в процессе самостоятельного изучения литературы;

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

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

−закрепление навыков по выполнению преобразований и

оформлению отчетной документации.

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

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

Знания и практические навыки по данной тематике, полученные студентами в ходе курсового проектирования, необходимы для успешного изучения дисциплин «Логические основы искусственного интеллекта», «Функциональное и логическое программирование», «Теория реляционных баз данных», «Базы данных», «Проектирование информационных систем».

1.2 Организация курсового проектирования

В соответствии с учебным планом и рабочей программой по дисциплине «Математическая логика и теория алгоритмов» каждый

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

PDF created with pdfFactory Pro trial version www.pdffactory.com

При выполнении записки к курсовой работе необходимо соблюдать следующие правила:

1)работа должна быть выполнена в соответствии с требованиями

коформлению курсовой работы;

2)не допускается замена варианта заданий курсовой работы

другим.

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

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

В ходе курсового проектирования руководитель регулярно проводит консультации, на которых проверяет все решения и расчеты, помогает студенту найти правильный путь к решению поставленной задачи. Курсовая работа перед сдачей руководителю должна быть подписана студентом. Если он удовлетворяет предъявляемым требованиям, то работа допускается к защите, что

удостоверяет руководитель своей подписью в соответствующей графе титульного листа пояснительной записки.

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

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

Курсовая работа не принимается к защите, если ее вариант не соответствует выданному студенту.

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

Студент, не защитивший курсовую работу, к экзамену не допускается. Зачтенные работы возврату не подлежат.

Студент должен выполнить четыре задания:

PDF created with pdfFactory Pro trial version www.pdffactory.com

1)Выполнить задания по алгебре высказываний и исчислению высказываний:

a.Построить таблицу истинности для посылок и заключения и по таблице истинности доказать истинность заключения из данных посылок;

b.Упростить посылки и заключения, т.е. привести их к базису {¬, &, } с минимальным числом операций;

c.Привести посылки и заключение к базисам {¬, &} и {¬, };

d.Для посылок и заключения построить КНФ, ДНФ, СКНФ, СДНФ;

e.Доказать истинность заключения путём построения дерева доказательства;

f.Доказать истинность заключения методом дедуктивного вывода (с построением графа дедуктивного вывода);

g.Доказать истинность заключения методом резолюции (с построением графа вывода пустой резольвенты).

2)Выполнить задание по алгебре предикатов и исчислению предикатов:

a.Привести выражение к виду ПНФ;

b.Привести выражение к виду ССФ;

c.Доказать истинность заключения методом дедуктивного вывода (с построением графа дедуктивного вывода);

d.Доказать истинность заключения методом резолюции (с построением графа вывода пустой резольвенты).

3)Выполнить задания по реляционной логике:

∙По заданному отношению r и двум операциям построить два отношения r1 и r2;

∙Выполнить над отношениями r1 и r2 заданные операции.

4)Для заданного выражения построить машину Тьюринга.

Пример выполнения и оформления курсовой работы

представлен в приложении А.

PDF created with pdfFactory Pro trial version www.pdffactory.com

2 Требования к выполнению курсовой работы

2.1Структура и содержание курсовой работы

Пояснительная записка является основным документом, предъявляемым студентом при защите курсовой работы. Она составляется в соответствии с требованиями ГОСТ 2.105-95, ЕСКД. Общие требования к текстовым документам. В записке отражаются результаты, полученные при выполнении курсовой работы.

Курсовая работа состоит из пояснительной записки, в которой содержатся решения предложенных задач.

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

За принятые в курсовой работе решения и правильность данных отвечает студент – автор курсовой работы.

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

−титульный лист;

−задание на курсовое проектирование;

−содержание;

−введение;

−основная часть;

−заключение;

−список использованных источников;

−приложение (приложения).

Оформление курсовой работы должно соответствовать требованиям, изложенном в источниках 7,8.

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

Во введении обосновывается целесообразность выбора темы, актуальность и практическая значимость проблемы. Формулируются цели и задачи работы. Показывается, на что автор обращает особое внимание, какие моменты опускает.

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

PDF created with pdfFactory Pro trial version www.pdffactory.com

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

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

Список литературы должен содержать все источники, использованные в работе. Список литературы подбирается студентами самостоятельно. Возможно использование списка дополнительной литературы, рекомендованного в методических указаниях к семинарским занятиям. Основой для написания курсовой работы должны служить законы РФ, научные работы и монографии, статьи в периодической печати, словари и справочники, статистические материалы. При чтении литературы необходимо сначала ориентироваться на фундаментальные работы (монографии и научные труды), затем дополнять свои знания за счет периодических изданий. Материал, необходимый для курсовой работы следует законспектировать. В списке литературы использованные источники располагаются в алфавитном порядке.

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

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

Не допускается дословное переписывание материала из литературных источников. Если в работе приведен цифровой и фактический материал, цитаты из работ отдельных авторов, необходима ссылка на источник (сноска). Допускается два варианта сносок: постраничные, и ссылки на список литературы.

Курсовая работа выполняется на нелинованных листах (формат А4). Работа должна быть сброшюрована, иметь титульный лист, оформленный по правилам. Текст пишется на одной стороне листа.

Специфика заполнения полей титульного листа:

Кафедра - указывается полное название профилирующей кафедры.

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

PDF created with pdfFactory Pro trial version www.pdffactory.com

Студент, руководитель – указывается фамилия студента с краткими инициалами, расшифровка имени и отчества не допускается.

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

Факультет (институт) – указывается аббревиатура факультета, например: УНИИ ИТ.

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

2.2Порядок выполнения курсовой работы

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

В первой части выделяется два подраздела: алгебра высказываний и исчисление высказываний. В первой части необходимо построить таблицу истинности для каждой формулы, входящей в посылку и для заключения. Затем необходимо для каждой посылки и заключения в отдельности выполнить указанные действия: минимизировать формулы, построить КНФ и ДНФ, построить СКНФ, СДНФ, привести в два базиса: отрицание-конъюнкция и отрицание- дизъюнкция. Во второй части необходимо выполнить доказательство истинности заключения из посылок 4 методами:

1По первому методу необходимо построить общую таблицу истинности для всех посылок и для заключения, выделить те строчки,

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

2Во втором методе доказательства необходимо построить дерево доказательства, которое начинается с применения аксиом, от

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

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

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

PDF created with pdfFactory Pro trial version www.pdffactory.com

введения дополнительной посылки. Данный способ заключается в

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

4 Четвертым методом доказательства является метод резолюций, для которого необходимо построить граф вывода пустой резольвенты. Данный метод предполагает приведение посылок и отрицания заключения к виду КНФ, и последовательным шагам по достижению пустой резольвенты.

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

первом подразделе необходимо привести заданную формулу к видам ПНФ и ССФ, дать краткие комментарии выполняемым действиям. Во втором подразделе необходимо преобразовать исходную формулу, выделив в ней посылки и заключение, используя теоретические знания о понятии вывода, понятии посылок и заключения. Затем

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

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

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

привести формулы для реляционного исчисления с переменными кортежами. Сначала необходимо из исходных отношений удалить согласно заданию 4 пары: (столбец, строка) и все последующие

операции выполнять именно с полученными в ходе удаления отношениями. Для всех студентов ставится задача выполнить три базовые операции над отношениями: пересечение, объединение и разность, а также выполнить композицию двух операций. Из двух операций в композиции одна будет операцией условного соединения, а вторая операция может быть операцией проекции или выборки. Для

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

PDF created with pdfFactory Pro trial version www.pdffactory.com