Определение исчисления предикатов первого порядка - раздел Образование, Основные понятия и определения Пусть Задано Некоторое Множество M = {M1, M2, …, M...
Пусть задано некоторое множество M = {m1, m2, …, mk, …}, в котором m1, m2, …, mk – какие-то определенные предметы из этого множества. Обозначим любой предмет из этого множества через х и назовем х предметной переменной. Тогда высказывания об этих предметах будем обозначать в виде P(m1), Q(m1, m2) и т. д., причем такие высказывания могут быть как истинными, так и ложными.
Предикат на множестве M есть логическая функция, определенная на M, при фиксировании аргументов которой она превращается в высказывание со значениями {T, F}.
В общем случае через P(x1, x2, …, xn) обозначим n-местный предикат, обладающий тем свойством, что, приписав значения переменным x1, x2, …, xn из соответствующих областей определения, получим высказывание со значениями {T, F}.
Важную роль в исчислении предикатов играют кванторы существования ($) и всеобщности ("). Для предиката Р(х) выражение "х Р(х) означает, что для всякого х из области определения предиката выражение Р(х) истинно. Выражение $х Р(х) означает, что существует х из области определения предиката, для которого выражение Р(х) истинно.
Таким образом, в исчислении предикатов используются:
1. Предметные переменные x1, x2, …, xn.
2. Предметные константы a, b, c, d, … .
3. Предикатные буквы A, B, C, D, … .
4. Функциональные буквы f, g, h, … .
5. Логические операторы Ø, É, Ù, Ú, Û.
6. Кванторы ", $.
Формулируются следующие правила построения термов:
1. Всякая предметная переменная или предметная константа есть терм.
2. Если f – функциональная буква и t1, t2, …, tn – термы, то f(t1, t2, …, tn) есть терм.
Формулируются следующие правила построения атомов (атомарных формул):
1. Всякое переменное высказывание есть атом.
2. Если А – предикатная буква, а t1, t2, …, tn – термы, то А(t1, t2, …, tn) есть атом.
Формулы исчисления высказываний конструируются по следующим правилам:
1. Всякий атом есть формула.
2. Если А и В – формулы и х – предметная переменная, то каждое из выражений ØА, А ÉВ, АÙВ, АÚВ, АÛВ, "хА, $хА есть формула.
Введем понятия свободного и связанного вхождения переменной в формулу. Вхождение переменной х в данную формулу называется связанным, если х является переменной входящего в эту формулу квантора ("х или $х) или находится в области действия входящего в эту формулу квантора; в противном случае вхождение переменной х в данную формулу называется свободным. Соответствующая переменная называется свободной или связанной.
В общем случае выражение "хi1"хi2 … "хir A(x1, x2, …, xn), где хi1, хi2,… хir являются подмножеством множества переменных x1, x2, …, xn, означает, что для любых значений, придаваемых переменным хi1, хi2,… хir из области определения A(x1, x2, …, xn), истинность A(x1, x2, …, xn) зависит только от свободных переменных, входящих в эту формулу. Аналогичное утверждение справедливо для квантора существования.
Если к формуле A(x1, x2, …, xn) применить n раз какие-либо кванторы, то получится выражение z1х1z2х2 … znхn A(x1, x2, …, xn), где zI Î{", $}, представляющее собой некоторое постоянное высказывание, которое называется замкнутой формулой, т. е. формулой без свободных переменных.
Формулы исчисления предикатов имеют смысл только тогда, когда имеется какая-нибудь интерпретация входящих в нее символов. Под интерпретацией I в исчислении предикатов понимается всякая система, состоящая из непустого множества M, называемого областью интерпретации, и какого-либо соответствия, относящего каждой предикатной букве Аi некоторое n-местное отношение в M (т. е. Mn®{T,F}), каждой функциональной букве fi – некоторую n-местную функцию в M (т. е. Mn®M) и каждой предметной константе аi – некоторый элемент из M.
Интерпретация формулы исчисления предикатов – отношение, которое каждой предикатной букве ставит в соотвествие значение истины, либо ложь.
Областью истинности J предикатаназывается подмножество M, на котором предикат принимает значение «истина» (Т).
При заданной интерпретации предметные переменные пробегают значения из M, а логическим связкам и кванторам придается их обычный смысл (см. п. 6.1.1).
Для данной интерпретации любая формула без свободных переменных представляет собой высказывание, которое может быть истинным или ложным, а всякая формула со свободными переменными выражает некоторое отношение на области интерпретации, причем это отношение может быть истинным для одних значений переменных из области интерпретации и ложным для других.
Для выяснения факта, истинна или ложна формула в данной интерпретации I, необходимо, задав область интерпретации, интерпретировать прежде всего все термы, входящие в формулу, затем атомы и, наконец, саму формулу. Если область интерпретации конечна, то можно выяснить истинность или ложность любой формулы, перебрав все различные элементы множества Mn, где n – число различных переменных, входящих в формулу. Однако на практике М часто настолько велико или бесконечно, что необходим логический вывод.
В настоящее время искусственный интеллект одна из быстро развивающихся областей науки которая разрабатывает методы и средства поиска решений... Идея создания искусственного подобия человеческого разума для решения сложных... В 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
Новости и инфо для студентов