Методичка по матлогике
.pdfопераций проекции и выборки. Последней задачей является
написание формул реляционного исчисления для заданных операций на языке реляционного исчисления с переменными-кортежами.
Пример выполнения курсовой работы приведен в Приложении А.
2.3 Защита курсовой работы
Защита проекта является особой формой проверки выполнения проекта. Защита должна приучать студента к всестороннему
обоснованию предложенных им решений задачи и к глубокому пониманию выполненной работы.
Защиту работы принимает комиссия, назначенная кафедрой.
Защита состоит в пояснении хода решения предложенных в курсовой работе заданий, курсовая работа оценивается дифференцированной отметкой по пятибалльной системе.
Студент, не представивший в установленный срок курсовую работу или не защитивший ее по неуважительной причине, считается имеющим академическую задолженность.
Условием получения оценки по курсовой работе является не только подготовка текста, но и устная защита. К защите допускаются готовые работы - окончательный вариант, исправленный на основании замечаний руководителя. Во время защиты необходимо ответить на заданные вопросы.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Список литературы
1.Игошин, В.И. Математическая логика и теория алгоритмов : учеб. пособие для вузов / Владимир Иванович Игошин . - М. : Академия , 2004. - 446, [1] с. (Высшее профессиональное образование).
2.Клини С.К. Математическая логика : пер. с англ. / Стивен Коул Клини . - М. : КомКнига , 2007. - 480 с.
3.Лавров И.А. Математическая логика : учеб. пособие для вузов / Игорь Андреевич Лавров . - М. : Академия , 2007. - 239 с. (Университетский учебник. Сер. Прикладная математика и информатика).
4.Марченков С.С. Элементарные рекурсивные функции / Сергей Серафимович Марченков . - М. : МЦНМО , 2003. - 111 с.
5.Хаггарти Р. Дискретная математика для программистов : учеб. пособие для вузов : пер. с англ. / Род Хаггарти . - М. : Техносфера , 2003. - 315 с., ил. (Мир программирования).
6.Новиков, Ф.А. Дискретная математика для программистов : учеб. пособие для вузов / Федор Александрович Новиков . - СПб. : Питер , 2005. - 363 с. (Учебник для вузов).
7.Олькина, Е.В. Методические указания по оформлению пояснительных записок к дипломным, курсовым проектам (работам)
иотчетов по практикам в соответствии с требованиями государственных стандартов [Текст] / Елена Викторовна Олькина. –
Орел: ОрелГТУ, 2007. – 54с. – (Для спец. 080801, 230105, 230201).
PDF created with pdfFactory Pro trial version www.pdffactory.com
Приложение А (обязательное)
Пример выполнения курсовой работы
1. Выполнить задания по алгебре высказываний и исчислению высказываний:
{Aà(BàC);AàB;A} |- C
Обозначим F= A→ (B→C), G=A→B, H=A и J=C.
а. Построить таблицу истинности.
Таблица А.1 – Таблица истинности логического выражения
A |
B |
C |
AàB |
BàC |
Aà(BàC) |
H |
|
J |
G |
|
F |
|
|
|
|
|
|
0 |
0 |
0 |
1 |
1 |
1 |
|
|
|
|
|
|
0 |
0 |
1 |
1 |
1 |
1 |
|
|
|
|
|
|
0 |
1 |
0 |
1 |
0 |
1 |
|
|
|
|
|
|
0 |
1 |
1 |
1 |
1 |
1 |
|
|
|
|
|
|
1 |
0 |
0 |
0 |
1 |
1 |
|
|
|
|
|
|
1 |
0 |
1 |
0 |
1 |
1 |
|
|
|
|
|
|
1 |
1 |
0 |
1 |
0 |
0 |
|
|
|
|
|
|
1 |
1 |
1 |
1 |
1 |
1 |
|
|
|
|
|
|
В таблице истинности жирным шрифтом выделены столбцы с посылками, а жирным и курсивом выделено заключение. Смотря на те строчки, в которых истины все посылки одновременно (в данном случае это последняя строчка, которая выделена жирной рамкой), видно, что заключение также истинно. Поэтому можно сделать
PDF created with pdfFactory Pro trial version www.pdffactory.com
вывод, что данное заключение выводимо из данного множества посылок.
б. Упростить посылки и заключения, т.е. привести их к базису
{¬, &, } с минимальным числом операций:
F= A→ (B→C) = ¬A (BàC) = ¬A¬B C
G= AàB = ¬A B
Формулы H и J остаются без изменения.
в. Привести посылки и заключение к базисам {¬, &} и {¬, }: F = Aà(BàC) = ¬A¬B C = ¬(¬¬A&¬(¬B C)) =
¬(A&¬¬B&¬C) = ¬(A&B&¬C) (в базисе {¬, &})
F= Aà(BàC) = ¬A¬B C (в базисе {¬, })
G= AàB = ¬A B = ¬ (¬¬A&¬B) = ¬(A&¬B) (в базисе {¬, &})
G = AàB = ¬A B (в базисе {¬, })
Формулы H и J остаются без изменения.
г. Для посылок и заключения построить КНФ, ДНФ, СКНФ, СДНФ:
F = Aà(BàC) = ¬A¬B C (КНФ, ДНФ, СКНФ)
F=(A&B&C) (¬A&B&C) (¬A&B&¬C) (¬A&¬B&¬C) (A&¬B&C) (A&¬B&¬C) (¬A&¬B&C) (СДНФ, построенная с помощью таблицы истинности)
G = AàB = ¬A B (КНФ, ДНФ, СКНФ)
G = (A&B) (¬A&B) (¬A&¬B) (СДНФ, построенная с помощью таблицы истинности);
Формулы H и J остаются без изменения.
PDF created with pdfFactory Pro trial version www.pdffactory.com
д. Доказать истинность заключения путём построения дерева доказательства, представленного на рисунке А.1.
Рисунок A.1 – Дерево доказательства
е. Доказать истинность заключения методом дедуктивного вывода (с построением графа дедуктивного вывода):
Построим граф дедуктивного вывода, представленный на рисунке А.2.
Рисунок A.2 – Граф дедуктивного вывода
PDF created with pdfFactory Pro trial version www.pdffactory.com
ж. Доказать истинность заключения методом резолюции (с построением графа вывода пустой резольвенты):
Приведем посылки и отрицание заключения к виду КНФ: F= A→ (B→C) = ¬A¬B C
G=A→B = ¬A B H=A
¬J=¬C
K = {¬A B,¬A¬B C,A,¬C}
Построим граф вывода пустой резольвенты, представленный на рисунке А.3.
Рисунок А.3 –Граф вывода пустой резольвенты
2 Выполнить задание по алгебре предикатов и исчислению предикатов:
F = x (A(x)→B(y))& z(C(z)→A(x))→y(C(z)→B(y))
а. Привести выражение к виду ПНФ
F = x (A(x)→B(y))& z(C(z)→A(x))→y(C(z)→B(y))= =¬( x (A(x) →B(y))& z(C(z) →A(x)))V y(C(z) →B(y))= =¬ x (¬A(x)VB(y))V ¬ z(¬C(z)VA(x))V y(¬C(z)VB(y)))=
PDF created with pdfFactory Pro trial version www.pdffactory.com
= x(A(x)&¬B(y))V z (C(z)&¬A(x))V y(¬C(z)VB(y))= = v(A(v)&¬B(y))V w (C(w)&¬A(x))V t(¬C(z)VB(t))= = v w t ((A(v)&¬B(y))V(C(w)&¬A(x))V(¬C(z)VB(t)))= = v w t((A(v)VC(w)V¬C(z)VB(t))&(¬B(y)VC(w)V¬C(z)VB(t)) &(A(v)V¬A(x)V¬C(z)VB(t))&(¬B(y)V¬A(x)V¬C(z)VB(t))) F= v w t((A(v)VC(w)V¬C(z)VB(t))&(¬B(y)VC(w)V¬C(z)VB(t)) &(A(v)V¬A(x)V¬C(z)VB(t))&(¬B(y)V¬A(x)V¬C(z)VB(t)))
б. Привести выражение к виду ССФ
Для приведения к виду ССФ воспользуемся алгоритмом Сколема, поэтому будут проведены следующие замены:
v = a, где a – предметная постоянная w = b, где b – предметная постоянная t = c, где c – предметная постоянная
В результате получится следующее выражение: F=(A(a)VC(b)V¬C(z)VB(c))&(¬B(y)VC(b)V¬C(z)VB(c))&(A(a)V
¬A(x)V¬C(z)VB(c))&(¬B(y)V¬A(x)V¬C(z)VB(c))
в. Доказать истинность заключения методом дедуктивного вывода (с построением графа дедуктивного вывода):
Представим нашу формулу в следующем виде: { x (A(x)→B(y)); z(C(z)→A(x)) }|- y(C(z)→B(y))
Построим граф дедуктивного вывода для доказательства выводимости заключения из данного множества посылок:
PDF created with pdfFactory Pro trial version www.pdffactory.com
Рисунок А.4 – Граф дедуктивного вывода г. Доказать истинность заключения методом резолюции (с
построением графа вывода пустой резольвенты)
¬F = ¬( x (A(x)→B(y))& z(C(z)→A(x))→y(C(z)→B(y))) =
=¬(¬( x (¬A(x)VB(y))& z(¬C(z)VA(x)))V y(¬C(z)VB(y))) =
=x (¬A(x)VB(y))& z(¬C(z)VA(x))& y(C(z)& ¬B(y)) =
= v (¬A(v)VB(y))& w(¬C(w)VA(x))V t(C(z)&B(t))= = v w t ((¬A(v)VB(y))&(¬C(w)VA(x))&C(z)& ¬B(t)
¬F = v w t ((¬A(v)VB(y))&(¬C(w)VA(x))&C(z)& ¬B(t)) Д = { ¬A(v)VB(y); ¬C(w)VA(x); C(z); ¬B(t) }
Построим граф вывода пустой резольвенты:
Рисунок А.4 – Граф дедуктивного вывода
PDF created with pdfFactory Pro trial version www.pdffactory.com
3 Реляционная алгебра
Выполнить следующие бинарные операции и составить результирующие таблицы.
1)(r1Èr2)
2)(r1Çr2)
3)(r1 \ r2)
4)Выполнить заданную композицию операций
p( r1.A3, r1.A4, r2×A7,r2.A8)(r1>q<r2, d(r1.A7)< d(r2.A7))
Отношения r1 и r2 получаются из заданного по условию
отношения путем удаления соответствующих заданию пар элементов (столбец, строка). В результате данных операций получаются отношения, представленные в таблицах А.1 и А.2.
Таблица А.1 – Отношение r1
А3 |
А4 |
А7 |
А8 |
с1 |
d2 |
1 |
2 |
с2 |
d3 |
2 |
3 |
|
|
|
|
с1 |
d1 |
2 |
1 |
с2 |
d2 |
1 |
4 |
Таблица А.1 – Отношение r2
А3 |
А4 |
А7 |
А8 |
|
|
|
|
c3 |
d4 |
3 |
4 |
c4 |
d1 |
4 |
1 |
|
|
|
|
c1 |
d2 |
1 |
2 |
c2 |
d3 |
2 |
3 |
PDF created with pdfFactory Pro trial version www.pdffactory.com
Далее необходимо выполнить 3 базовые операции с отношениями, результаты выполнения которых представлены в таблицах А.3, А.4, А.5
Таблица А.3 – Результат выполнения операции r1Èr2
А3 |
А4 |
А7 |
А8 |
|
|
|
|
c1 |
d2 |
1 |
2 |
|
|
|
|
c2 |
d3 |
2 |
3 |
|
|
|
|
c1 |
d1 |
2 |
1 |
|
|
|
|
c2 |
d2 |
1 |
4 |
|
|
|
|
c3 |
d4 |
3 |
4 |
|
|
|
|
C4 |
d1 |
4 |
1 |
Таблица А.4 – Результат выполнения операции r1Çr2
A3 |
A4 |
A7 |
A8 |
c1 |
d2 |
1 |
2 |
c2 |
d3 |
2 |
3 |
Таблица А.5 – Результат выполнения операции r1\r2
А3 |
А4 |
А7 |
А8 |
c1 |
d1 |
2 |
1 |
c2 |
d2 |
1 |
4 |
Последнее задание представляет собой композицию двух операций, поэтому для ее выполнения требуется получить сначала промежуточное отношение, представляющее собой результат выполнения операции условного соединения над отношениями r1 и r2. Результирующее отношение представлено в таблице А.6. После
этого необходимо выполнить операцию проекции над полученным отношением, выбрав заданные по условию операции атрибуты
PDF created with pdfFactory Pro trial version www.pdffactory.com