Процедура вывода Эрбрана - раздел Образование, Основные понятия и определения В Исчислении Предикатов Не Существует Универсального Алгоритма, Который Позво...
В исчислении предикатов не существует универсального алгоритма, который позволяет проверить общезначимость, нейтральность, невыполнимость формулы, т.к. для формулы исчисления предикатов существует бесконечное число интерпретаций. Однако было установлено, что множество дизъюнктов (СНФ) невыполнимо тогда и только тогда, когда принимает значение ложь на всех интерпретациях, на любых областях. Но так как рассмотрение всех интерпретаций на любых областях невозможно, хорошо было бы найти такую специальную область интерпретации, установив на которой факт невыполнимости множества дизъюнктов, можно было бы сделать вывод о невыполнимости этого множества на любых других областях интерпретаций. Такая область существует, называется универсумом Эрбрана и определяется следующим образом.
Пусть Hо – множество констант, появляющихся в множестве дизъюнктов S. Если в S нет констант, то в Hо включается некоторая константа, например Hо = {a}. Для i = 0,1,2, … Hi+1 = Hi È {fn(t1, t2, …, tn)}, где fn – все n-местные функциональные символы, встречающиеся в S, а t1, t2, …, tn – элементы множества Hi.
Тогда множество H = H¥ называется универсумом Эрбрана для S, а Hi – его уровнем i. Элементы эрбрановой области не имеют конкретных значений, это синтаксические объекты.
Пример. Пусть S = { P(x, a, g(y)) Ú ¬Q(х)), ¬P(f(x), a, y) Ú Q(a)}. Тогда
На универсуме Эрбрана вводится понятие эрбрановой интерпретации, или H-интерпретации. Говорят, что интерпретация IH является H-интерпретацией для множества дизъюнктов S, если выполнены следующие условия:
1) каждому предикатному символу Pjn соответствует некоторое n-местное отношение в H;
2) каждому функциональному символу fjn соответствует некоторая n-местная операция в H ( т. е. функция, отображающая Hn в H);
3) каждой предметной константе ai из S соответствует некоторая константа из H (т. е. все константы отображаются на самих в себя).
Пример. Пусть S = {¬P(f(x)) Ú Q(x), R(x)}. Тогда примеры H-интерпретаций следующие:
При I1H оба дизъюнкта выполнимы, при I2H первый дизъюнкт выполним, второй – нет, при I3H оба дизъюнкта невыполнимы, т. е. принимают значение «ложь».
В случае, если интерпретация задана не на универсуме Эрбрана, а на произвольной области D, то можно установить следующее соответствие между этими интерпретациями. Пусть дана интерпретация I на некоторой области D. Говорят, что H-интерпретация IH соответствует интерпретации I, если имеет место следующее: пусть h1, h2, …, hn, … – элементы H и пусть каждый hi отображается на некоторый элемент di области D, тогда если любой P(d1, d2, …, dn) принимает значение «истина» («ложь») при интерпретации I, то P(h1, h2, …, hn) также принимает значение «истина» («ложь») при IH.
Справедлива следующая теорема: множество дизъюнктов S невыполнимо тогда и только тогда, когда S ложно при всех H-интерпретациях. Таким образом, для установления невыполнимости множества дизъюнктов достаточно рассмотреть не все его интерпретации, а только H-интерпретации.
Процедура вывода Эрбрана основывается на его теореме, которая гласит: множество дизъюнктов S невыполнимо тогда и только тогда, когда существует конечное невыполнимое множество фундаментальных примеров дизъюнктов в S.
Фундаментальным примером дизъюнкта называется дизъюнкт, полученный заменой всех переменных в этом дизъюнкте элементами универсума Эрбрана таким образом, что все вхождения одной и той же переменной в дизъюнкт заменяются на один и тот же элемент универсума.
Таким образом, для установления невыполнимости множества дизъюнктов необходимо образовать множества S1, S2, …, Sn, … фундаментальных примеров дизъюнктов и последовательно проверить их на ложность. Теорема Эрбрана гарантирует, что если множество S невыполнимо, то данная процедура обнаружит такое n , что Sn является ложным.
Недостаток процедуры Эрбрана состоит в экспоненциальном росте множеств Si при увеличении i. Иной подход предложил Дж. Робинсон, который ввел принцип резолюций, являющийся теоретической основой для построения большинства методов автоматического доказательства теорем.
В настоящее время искусственный интеллект одна из быстро развивающихся областей науки которая разрабатывает методы и средства поиска решений... Идея создания искусственного подобия человеческого разума для решения сложных... В XVIII в Г Лейбниц и Р Декарт независимо друг от друга развили эту идею предложив...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Процедура вывода Эрбрана
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Понятие искусственного интеллекта
Центральным понятием является понятие «искусственный интеллект». Термин искусственный интеллект (artificial intelligence) был предложен в 1956 г. на научном семинаре в Стэндфордско
Цели и задачи искусственного интеллекта
К основным целям искусственного интеллекта можно отнести:
1. Обработка зрительных сцен:
- обработка изображения;
- распознавание и понимание образов;
- машинная
Истоки формальных рассуждений
2.1. Левополушарное и правополушарное мышления
Как известно, мозг человека состоит из двух полушарий, каждое из которых по-своему преобразует информацию.
Весь окружающий мир делит
Типы мышления
Левое полушарие – «Я»
Тип мышления
Сходство – различие
Выделение признаков конкретных объектов
Декомпозиция целого на части
Понятие формальной системы
Появление формальных систем было обусловлено осознанием того факта, что совершенно различные системы, будь то технические, социальные, экономические или биологические, облад
Разрешимость формальной системы
Первым вопросом, который возникает при задании формальной системы, является вопрос об инверсии, т. е. о том, возможно ли, рассматривая какую-либо формулу формальной системы, определить, является ли
Интерпретация формальной системы
Формальные системы являются не просто игрой ума, а всегда представляют собой модель какой-то реальности (либо конкретной, либо математической).
Интерпретация представл
Доказательство и истинность
Из приведённых выше определений существует уже по построению глубокое различие между концепциями доказательства и истинности. Эти понятия относятся к двум различным областям. Априорно ничто не гара
Основные принципы силлогистики
Аристотель (384-322 гг. до н. э.) – древнегреческий учёный-энциклопедист, основоположник формальной логики. Основные сочинения в области логики: «Категории», «Об истолковании», «Аналитики первая и
Решение силлогизмов
Силлогизм – вывод ранга 2, т.е. вывод, который можно сделать на основании истинности двух посылок. В этих посылках фигурируют три класса сущностей: S ,P и M. Для формирования силлогизма используютс
Расширенная силлогистика
Расширение классической силлогистики Аристотеля возможно произвести двумя способами – переходом к негативным утверждениям и увеличением числа посылок.
Моделирование силлогистики
Основной элемент при выводах в силлогистике – переход от двух посылок к заключению. Этот процесс может быть автоматизирован, схема автоматизированной системы для получения силлогистических выводов
Синтаксис исчисления высказываний
Основное понятие исчисления высказываний – высказывание. Это предложения на естественном языке, которые могут быть истинными или ложными. При этом различают логическую истину языка
Понятие семантического дерева
Если Р={Р1…Рn} – множество высказываний, то семантическое дерево – это бинарное дерево, удовлетворяющее следующим условиям:
1) каждая дуга помечена негативной или поз
Алгоритм Куайна
Алгоритм Куайна, или алгоритм частичного перебора, позволяет доказать общезначимость формулы без просмотра полного семантического дерева. Основная идея алгоритма з
Алгоритм редукции
Алгоритм редукции позволяет доказать общезначимость формул с помощью приведения их к противоречию. Рассмотрим работу алгоритма на примере.
Пример.Проверит
Нормальные формы и алгоритм нормализации
Каждая логическая формула может изучаться алгебраически путем приведения ее к нормальной форме. Возможно приведение к двум нормальным формам – конъюнктивной нормальной форме (КНФ)
Алгоритм Куайна для ДНФ
Алгоритм Куайна для ДНФпозволяет проверить выполнимость и общезначимость приведенной дизъюнктивной нормальной формы.
Пусть р – элементарное высказывание, а S – приведенная
Принцип резолюций
В исчислении высказываний не существует общего, по-настоящему эффективного критерия для проверки выполнимости КНФ, однако есть удобный метод для выявления невыполнимости множества дизъюнктов.
Хорновские дизъюнкты
Часто в исчислении высказываний возникает следующая задача: нужно проверить какую-то формулу (цель), логически выведенную из множества фактов и правил. Резолюция является методом доказательства от
Исчисление предикатов
Уже упоминавшийся выше силлогизм «Люди смертны …» не может быть представлен с помощью исчисления высказываний. Для его формализации необходимо ввести квантифицированную переменную
Общезначимость и выполнимость формул исчисления предикатов
Понятия общезначимости и противоречивости формул, введенные в исчислении высказываний, сохраняют свою силу и для исчисления предикатов.
Формула исчисления предикатов называется
Исчисление предикатов как формальная система
Рассмотрим формальную аксиоматическую систему для исчисления предикатов.
1. Алфавит:
а) счетное множество предметных переменных x1, x2, …, xn …;
Пренексные нормальные формы исчисления предикатов
В исчислении высказываний были рассмотрены две нормальные формы высказываний – КНФ и ДНФ. В исчислении предикатов также имеется нормальная форма, так называемая пренексная нормальная форма
Сколемовские стандартные формы исчисления предикатов
Очевидно, что если формулы F и Ф равносильны, то F логически невыполнима тогда и только тогда, когда логически невыполнима Ф. Благодаря этому утверждению и в силу того, что алгоритмы приведения в П
Принцип резолюции для логики предикатов
В главе 5 был изложен принцип резолюций для исчисления высказываний, где нахождение контрарных пар не вызывало трудностей. Для логики предикатов это не так. Действительно, пусть имеются дизъюнкты т
Индуктивные рассуждения
Термин «индукция» (от лат. inductio – наведение) в науку впервые был введен Аристотелем, который, в свою очередь, приписывал первое применение этого термина Сократу. Аристот
Принцип единственного различия
«Если после введения некоторого фактора появляется или после удаления этого фактора исчезает известное явление, причем не вводились и не удалялись никакие другие факторы и не производилось никакого
Особенности индуктивных схем рассуждений
Индуктивные рассуждения справедливы при условии, что в описании ситуации имеется полное множество наблюдаемых факторов и явлений. Причем в левой части причинно-следственного отношения может стоять
Алгоритм древ
Данный алгоритм является методом качественного обобщения по признакам и предложен как развитие алгоритма обобщения Э. Ханта – CLS.
В основе метода используется дерево решений – один из спо
Индукция решающих деревьев (ID3)
Алгоритм ID3 (induction of decision tree) формирует решающие деревья на основе примеров. Каждый пример имеет одинаковый набор атрибутов (признаков), которые можно рассматрив
Метод фокусирования
Важный шаг при решении задачи обобщения понятий – получение решающих правил (продукций, деревьев), которые содержат не только логические функции на конкретных значениях признаков, но включают более
Рассуждения по аналогии
Согласно Большому энциклопедическому словарю «... аналогия (от греч. analogon – соответствие, равенство отношений) – сходство предметов (явлений, объектов) в каких-либо свой
Простая аналогия
Дадим формальные механизмы использования аналогии для решения задач. Пусть существуют два рассуждения: в первое входят два объекта S1 и S2, преобразование F и некоторый вывод
Модальные логики
Вводятся операторы над логическими формулами, которые могут модифицировать их интерпретацию. В зависимости от того, какие операторы вводятся, различают классы модальных логик:
1.
Применение нечеткой математики
Вводится понятие нечеткого множества – множества, относительно любого из элементов которого можно сделать следующие заключения:
1. Элемент принадлежит данному множе
Нечеткая силлогистика
Рассмотрим силлогизм, который содержит следующие посылки:
1. Среди тех, кто носит цилиндр, почти все ходят с тросточкой.
2. Среди тех, кто ходит с тросточкой, почти все пьют марти
Методы поиска в пространстве состояний
Методы поиска в пространстве состояний фактически являются методами поиска на графе, у которого начальная вершина – начальное состояние, и задан оператор, который строит все вершины, следующие непо
Искусственный нейрон
Стремясь воспроизвести функции человеческого мозга, исследователи создали простые аппаратные (а позже программные) модели биологического нейрона и системы его соединений. Когда нейрофизиологи дости
Персептроны
Рис. 13. Персептронный нейрон
Первое систематическое изучение искусственных нейронных сетей было предпринято Маккалокком
Обучение персептрона
Способность искусственных нейронных сетей обучаться является их наиболее интригующим свойством. Подобно биологическим системам, которые они моделируют, эти нейронные сети сами моделируют себя в рез
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов