Проверка логического следования методом резолюции
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
рмирует две последовательности нового списка: прямую и обратную. Если преобразуемый список - пустой список, то результатом будет пустой список (базовый случай). Иначе формируется список, который состоит из двух списков: первый сформирован добавлением первого аргумента к списку, а второй, реверсированием первого списка.
Функция scep. Эта функция перемножает первый аргумент на список, в результате которого возвращается список списков. Для корректного выхода, необходимо два базовых случая:
а) условие перемножения пустого списка на некоторую переменную,
б) условие перемножения пустого списка списков на некоторую переменную (это необходимо, так как функция задана рекурсивно относительно второго аргумента, значит, по любому настанет ситуация, когда кончатся элементы, как в подсписках, так и в главном списке).
В частном случае производим сцепление первого аргумента с головой второго аргумента (сформировали первый результирующий элемент) с рекурсивно вызванной функцией scep для того же первого аргумента и хвоста второго аргумента.
В конце формируются все комбинаций вызовом функции perestanovka, которая рекурсивно сцепляет свою голову с рекурсивно вызванной perestanovka, которая имеет в качестве аргумента хвост. Комбинация пустого списка, есть пустой список списков (базовый случай).
.Функция contrar. Она также как и в Prolog определяет наличия в списке контрарного атома заданному.
srav x y = if (( "~" ++ x == y) || ( "~" ++ y == x)) then True else False:: String -> [String] -> Boolx [] = False
contrar x y = if (srav x (head y) == True) then True else contrar x (tail y)
Первая функция нужна для проверки, являются ли атомы контрарными. Принцип работы основан на отделении первого символа.
Функция contrar состоит из двух случаев. Первый является базовым, и определяет поведение, если второй аргумент равен пустому списку. Основной случай аналогичен Prolog, смотрим, являются ли голова контрарным литером по отношению к рассматриваемому, если нет, то рекурсивно вызываем функцию для хвоста.
4. Функция soed. Ее структура будет отличаться от структуры в Prolog только синтаксической реализацией, вызванной тем, что любая функция возвращает значение, которое можно дальше использовать в программе.
soed :: [String] -> [String] -> [String][] x = xx y
|(x == []) = x
|(not (elem (head x) y)) && (not (contrar (head x) y))
= (head x) : soed (tail x) y
|contrar (head x) y = soed (tail x) (delete (cont (head x)) y)
|otherwise = soed (tail x) y
Условия те же что и в Prolog, только в Haskell рассматривается один случай, так как при работе со строками, определена функцию, возвращающая контрарный атом, независимо от знака литера.
Итак, теперь перейдем к проверке. Процедура prov не остановится при обнаружении пустой резольвенты, так как в функциях языка Haskell возвращается конечное значение, а не производится поиск условий, успешного завершения работы функции. Поэтому необходимо переработать функцию так, чтобы после каждого вызова soed она проверяла, равен ли результат []. Если это так, то необходимо прервать выполнение алгоритма. Для простоты проверки и удобства записи, пусть функция nachprov арности 1 вызовет pr с двумя аргументами, головой проверяемого списка и с его хвостом:
nachprov [] = True
nachprov (x:xs) pr x xs
pr x (y:ys)
|x == [] = True
|ys == [] = if (soed x y) == [] then True else False
|otherwise = pr (soed x y) ys
Рассмотрим структуру вспомогательной функции pr. Если в неё передаётся пустой параметр в качестве первого аргумента, значит (при корректном вводе данных) это результат функции soed. Следовательно, при рассматриваемой комбинации, пустая резольвента найдена и мы завершаем работу с положительным результатом. В другом случае объединяем голову с результатом выполнения, вполне возможно, что хвост станет пустым. Рассмотрим этот случай отдельно: если до того как хвост стал равным [] в результате функции оказался тоже пустой список, значит пустая резольвента найдена. В противном случае мы рекурсивно вызываем goprov, как и во всех остальных случаях.
Для удобства запуска реализуем операцию pusk, которая принимает входной список, формирует комбинации и проверяет каждый из вариантов.
pusk x = prov (perestanovka x)
Эта функция выдаст ответ True или False.
Примеры работы программ
1.Пример работы программы на языке Prolog:
? - pusk ([[a, s, $b, $c], [$a, b], [$s, c]]).
? - pusk ([[a, s, $b, $c], [$a, $b], [$s, c]]).
3.Пример работы программы на языке Haskell:
Main > pusk ([[a, s, ~b, ~c], [~a, b], [~s, c]]).> pusk ([[a, s, ~b, ~c], [~a, ~b], [~s, c]]).
Заключение
Итак, цель курсовой работы достигнута: проверка логического следования методом резолюции на Prolog и на Haskell реализована. Задачи исправно работают. Материал пройденный на лекциях закреплен.
Список литературы
1. Братко И., Программирование на языке Пролог для искусственного интеллекта [Текст - Москва, "МИР", 1990.
2. Роганова Н.А., Функциональное программирование [Текст] - ГИНФО, 2002.
Приложение А
Листинг программы на языке Prolog
$($X):- X.(X, [X|_]).(X,[_|Xs]):- vhodit(X, Xs).(X,[X|Xs],Xs).(X,[Y|Ys],[Y|Z]):- udalit(X,Ys,Z).(X,[$X|_]).(X,[_|Xs]):- contrar(X,Xs).($X,[X|_]).($X,[_|Xs]):- contrar($X,Xs).([], []).(Z,[X|K]):- udalit(X,Z,Z1), perestanovka(Z1,K).([],X,X).([X|Xs],Y,[X|Z]):- not(vhodit(X,Y)), not(contrar(X,Y)), soed(Xs,Y,Z).([X|Xs],Y,Z):- vhodit(X,Y), soed(Xs,Y,Z).([X|Xs],Y,Z):- contrar(X,Y), udalit($X,Y,D), soed(Xs,D,Z).([$X|Xs],Y,[$X|Z]):- not(vhodit($X,Y)), not(contrar($X,Y)), soed(Xs,Y,Z).([$X|Xs],Y,Z):- vhodit($X,Y), soed(Xs,Y,Z).([$X|Xs],Y,Z):- contrar($X,Y), udalit(X,Y,D), soed(Xs,D,Z).([X|Xs]):- prov(X,Xs).([], _).(X,[Y|Ys]):- soed(X,Y,Z), prov(Z,Ys).(X) :- perestanovka(X, Z), nachprov(Z).
Приложение Б
Листинг п?/p>