Введение

В середине XX века развитие вычислительной техники привело к появлению логических электронных элементов, логических блоков и устройств вычислительной техники, что было связано с дополнительной разработкой таких областей логики, как проблемы логического синтеза, логическое проектирование и логического моделирования логических устройств и средств вычислительной техники. Эти проблемы изучает теория алгоритмов, основанная на математике, и математической логике в частности. Математическая логика нашла широкое применение в языках программирования. А в 80-х годах XX века начались исследования в области искусственного интеллекта на базе языков и систем логического программирования. Это направление является самым развивающимся и перспективным.

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

Задачами, которые будут решаться в работе, являются:

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

рассмотреть алгебру логики предикатов и исчисление предикатов,

изучить реляционную алгебру.

Для решения поставленных задач использовался теоретический материал научных работ Лаврова И.А., Максимовой Л.Л. и Пономарева В.Ф.

1 Логика высказываний

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

{(A®(B®C));( ØDÚA);B}|-(D®C)

F= A®(B®C) G=ØDÚA H=B J= D®C

Таблица 1 - Таблица истинности

ABCDB®CA®(1)ØDÚAD®CH(1)FGJ00001111000111000010111100111101010001110101010001101111011111011000111110011110101011111011111111000011110100101110111111111111

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

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

F = A® (B®C) = ØAÚ(BàC) = ØAÚØBÚC= D®C = ØDÚC

Формулы G и H остаются без изменения.

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

F = Aà(BàC) = ØAÚØBÚC = Ø(ØØA&Ø(ØBÚC)) = Ø(A&ØØB&ØC) =

= Ø(A&B&ØC) (в базисе {Ø, &})

F = Aà(BàC) = ØAÚØBÚC (в базисе {Ø, Ú})=ØDÚA = ØDÚA=Ø (ØØD&ØA) = Ø(D&ØA) (в базисе {Ø, &})=ØDÚA (в базисе {Ø, Ú})

J = DàC = ØDÚC = Ø (ØØD&ØC) = Ø(D&ØC) (в базисе {Ø, &})

J = DàC = ØDÚC (в базисе {Ø, Ú})

Формула H остается без изменения.

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

F = Aà(BàC) = ØAÚØBÚC (КНФ, ДНФ, СКНФ)=(ØA&ØB&ØC) Ú (ØA&ØB&C) Ú (ØA&B&ØC) Ú (ØA&B&C) Ú (A&ØB&ØC) Ú (A&ØB&C) Ú (A&B&C) (СДНФ, построенная с помощью таблицы истинности)

J= D®C = ØDÚC (КНФ, ДНФ, СКНФ)

J = (D&C) Ú (ØD&C) Ú (ØD&ØC) (СДНФ, построенная с помощью таблицы истинности);

G=ØDÚA (КНФ, ДНФ, СКНФ)

G = (D&ØA) Ú (D&A) Ú(ØD&A) (СДНФ, построенная с помощью таблицы истинности)

Формула H остается без изменения

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

Рисунок 1 -дерево доказательства

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

Рисунок 2 - Граф дедуктивного вывода

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

Приведем посылки и отрицание заключения к виду КНФ:

F= A® (B®C) = ØAÚØBÚC=ØDÚA=B