Студопедия — Логический вывод на хорновских дизъюнктах.
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Логический вывод на хорновских дизъюнктах.






Клозом Хорна (дизъюнктом Хорна, хорновским дизъюнктом) называется выражение вида (A1Ù….ÙAn)->(B1Ú…ÚBm), где n>=0, 0<=m<=1. Ai, Bj – литеры.

Клозы Хорна действительно являются дизъюнктами, так как возможны следующие случаи:

A) m=0, n=0 - имеем пустой клоз.

B) m=0, n>0 – A1Ù….ÙAn. Клоз Хорна такого вида называется теоремой (и используется для формулирования теорем). А так как в выводе участвуют теоремы, а их отрицания, то имеем ùA1Ú…ÚùAn.

C) m=1, n=0. Такой клоз Хорна называют фактом. Факт состоит из одной литеры.

D) m=1, n>0 – аксиома. A1Ù….ÙAn->B=ùA1Ú … ÚùAnÚB.

Задача. Методом резолюции получить пустой клоз.

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

//здесь расписать формально шаги резолюции (16)

Пусть имеем список целей:

C1, …, Ci-1, Ci, Ci+1, …, Ck

Его отрицание является дизъюнктом:

ù C1 Ú … Ú ù Ci-1 Ú ù C i Ú ù Ci+1 Ú … Ú ù Ck

А) Если факт B = Ci, то:

ù C1 Ú … Ú ù Ci-1 Ú ù Ci Úù Ci+1 Ú … Ú ù Ck

B

ù C1 Ú …Úù Ci-1 Ú ù Ci+1 Ú … Úù Ck

Т.е. получили список:

C1 …, C i-1 , C i+1, …, Ck

Фактически мы исключили цель, имеющую подтверждающий факт.

В) Если аксиома (A1 An) B, где:

B - Ci

Имеем:

ù С1 Ú … Ú ù Ci-1 Ú ù Ci Ú ù Ci+1 Ú … Ú ù Ck

ù A1 Ú … Ú ù Ak Ú B

ù C1 Ú … Úù Ci-1 Ú ù A1 … Ú ù An Úù Ci+1 Ú … Úù Ck

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

C1, …, C i-1, A1, …, An, Ci+1, …, Ck

Далее, процесс продолжается и так до тех пор, пока мы не получим пустой клоз или не будет возможности применить ни аксиому, ни факт. Заметим, что боковой клоз всегда выбирается из входного множества, что увеличивает скорость вывода. Но этот метод имеет крупный недостаток. Он в отличие от OL-вывода не обладает свойством полноты, и может зацикливать в довольно тривиальных случаях.

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

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

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

 







Дата добавления: 2015-10-19; просмотров: 842. Нарушение авторских прав; Мы поможем в написании вашей работы!



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

Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...

Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...

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

ОСНОВНЫЕ ТИПЫ МОЗГА ПОЗВОНОЧНЫХ Ихтиопсидный тип мозга характерен для низших позвоночных - рыб и амфибий...

Принципы, критерии и методы оценки и аттестации персонала   Аттестация персонала является одной их важнейших функций управления персоналом...

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

ОЧАГОВЫЕ ТЕНИ В ЛЕГКОМ Очаговыми легочными инфильтратами проявляют себя различные по этиологии заболевания, в основе которых лежит бронхо-нодулярный процесс, который при рентгенологическом исследовании дает очагового характера тень, размерами не более 1 см в диаметре...

Примеры решения типовых задач. Пример 1.Степень диссоциации уксусной кислоты в 0,1 М растворе равна 1,32∙10-2   Пример 1.Степень диссоциации уксусной кислоты в 0,1 М растворе равна 1,32∙10-2. Найдите константу диссоциации кислоты и значение рК. Решение. Подставим данные задачи в уравнение закона разбавления К = a2См/(1 –a) =...

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

Studopedia.info - Студопедия - 2014-2024 год . (0.01 сек.) русская версия | украинская версия