КУРСОВАЯ РАБОТА
по дисциплине «Математическая логика и теория алгоритмов»
на тему: «Логика высказываний. Логика предикатов. Реляционная логика»
Cодержание
Введение
. Логика высказываний
. Логика предикатов
. Реляционная алгебра
Заключение
Список литературы
Введение
В середине XX века развитие вычислительной техники привело к появлению логических электронных элементов, логических блоков и устройств вычислительной техники, что было связано с дополнительной разработкой таких областей логики, как проблемы логического синтеза, логическое проектирование и логического моделирования логических устройств и средств вычислительной техники. Эти проблемы изучает теория алгоритмов, основанная на математике, и математической логике в частности. Математическая логика нашла широкое применение в языках программирования. А в 80-х годах XX века начались исследования в области искусственного интеллекта на базе языков и систем логического программирования. Это направление является самым развивающимся и перспективным.
Поэтому целью данной курсовой работы является знакомство с методами решений задач логики высказываний, логики предикатов и реляционной логики.
Задачами, которые будут решаться в работе, являются:
ознакомиться с алгеброй логики высказываний и исчислением высказываний,
рассмотреть алгебру логики предикатов и исчисление предикатов,
изучить реляционную алгебру.
Для решения поставленных задач использовался теоретический материал научных работ Лаврова И.А., Максимовой Л.Л. и Пономарева В.Ф.
1. Логика высказываний
Выполнить задания по алгебре высказываний и исчислению высказываний:
{(AÚB); (A→C); (B→D)}├ CÚD
Обозначим F=AÚB , G=A→C, H=B→D, J=CÚD
а. Построить таблицу истинности.
Рисунок 1 - Таблица истинности
ABCDAÚBA→CB→DCÚDFGHJ00000110000101110010011100110111010011000101111101101101011111111000101010011011101011111011111111001000110110111110110111111111
В таблице истинности жирным шрифтом выделены столбцы с посылками, а жирным и курсивом выделено заключение. Смотря на те строчки, в которых истины все посылки одновременно видно, что заключение также истинно. Поэтому можно сделать вывод, что данное заключение выводимо из данного множества посылок.
б. Упростить посылки и заключения, т.е. привести их к базису {Ø, &, Ú} с минимальным числом операций:
= A® C = ØAÚC
G = B®D = ØBÚD
Формулы H и J остаются без изменения.
в. Привести посылки и заключение к базисам {Ø, &} и {Ø, Ú}:
=AvB=Ø(ØA&ØB) (в базисе {Ø, &})
H=AvB (в базисе {Ø, Ú})
F = = A®C= ØAÚC = Ø (ØØA&ØC) = Ø(A&ØC) (в базисе {Ø, &})= A®C = ØAÚC (в базисе {Ø, Ú})= B®D = ØBÚD = Ø (ØØB&ØD) = Ø(B&ØD) (в базисе {Ø, &}) = B®D = ØBÚD (в базисе {Ø, Ú})
J=CvD=Ø(ØC&ØD) (в базисе {Ø, &})
J=CvD (в базисе {Ø, Ú})
г. Для посылок и заключения построить КНФ, ДНФ, СКНФ, СДНФ:
= AvB (КНФ, ДНФ, СКНФ) = (A&B) Ú (ØA&B) Ú (A&ØB) (СДНФ, построенная с помощью таблицы истинности);
F = A®C = ØAÚC (КНФ, ДНФ, СКНФ) = (A&C) Ú (ØA&C) Ú (ØA&ØC) (СДНФ, построенная с помощью таблицы истинности);
G = B®D = ØBÚD (КНФ, ДНФ, СКНФ)
G = (B&D) Ú (ØB&D) Ú (ØB&ØD) (СДНФ, построенная с помощью таблицы истинности);
J = CvD (КНФ, ДНФ, СКНФ)
J = (C&D) Ú (ØC&D) Ú (C&ØD) (СДНФ, построенная с помощью таблицы истинности);
д. Доказать истинность заключения путём построения дерева доказательства
вп {AvC}├ AvC
{AvC; DvC}├ AvC вп {DvC}├ DvC
mp{AvC; DvC}├ AÚB→DÚC
{A→C}├ AÚB→DÚC {AÚB}├ AÚB
вп {AÚB; A→C}├ AÚB→DÚC вп {AÚB; A→C}├ AÚB{B→D}├ BÚC→CÚD
вп {AÚB; B→D}├ BÚC→CÚD
{AÚB; A→C}├ BÚC вп {AÚB; A→C; B→D}├ BÚC→CÚD {AÚB; A→C; B→D}├ CÚD
Рисунок 2 - Граф построения дерева доказательства
е. Доказать истинность заключения методом дедуктивного вывода (с построением графа дедуктивного вывода):
AÚB A→C B→D
m.p. AÚB→BÚC BÚC→CÚD
BÚC
m.p.
CÚD