исчисление предикатов что это

Исчисление предикатов

Содержание

Исчисление предикатов [ править ]

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

Чтобы построить новое исчисление, нам требуется указать 3 компонента: язык, аксиомы и правила вывода.

Язык [ править ]

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

Добавились 3 новых сущности:

(b) предикаты (они обобщили пропозициональные переменные)

(c) кванторы: всеобщности ( [math] \forall [/math] ) и существования ( [math] \exists [/math] ).

Аксиомы [ править ]

Определение:

Будем говорить, что переменная [math]y[/math] свободна для [math]x[/math] при подстановке в формулу [math]\psi[/math] (или просто свободна для подстановки вместо [math]x[/math] ), если после подстановки [math]y[/math] вместо свободных вхождений [math]x[/math] ни одно ее вхождение не станет связанным.

(11) [math]\forall(\psi) \rightarrow (\psi[x := \alpha]) [/math]

(12) [math](\psi[x := \alpha]) \rightarrow \exists(\psi) [/math]

Пример, когда нарушение свободы для подстановки приводит к противоречию:

[math] \forall(\psi) \to (\psi[x := \alpha]) \\ \psi := \exists a \lnot P(a) = P(b), x := b, \alpha := a \\ \forall b \exists a (\lnot P(a) = P(b)) \to \exists a (\lnot P(a) = P(a)) \\ [/math]

[math] \exists a (\lnot P(a) = P(a)) [/math]

Все аксиомы, порожденные данными схемами в новом языке, мы назовем аксиомами исчисления предикатов.

Правила вывода [ править ]

Добавив эти схемы к схеме для правила Modus ponens исчисления высказываний, мы сможем породить множество правил вывода.

Итог [ править ]

Определение:

Формальная система, составленная из указанного языка, множества аксиом и множества правил вывода, называется исчислением предикатов.

Обратите внимание на требование отсутствия свободных переменных в допущениях.

Доказательство:[math]\triangleright[/math]Упражнение.[math]\triangleleft[/math]

Доказательство разбором случаев. 3 старых случая те же, добавилось 2 новых правила вывода.

Источник

Основы математической логики

Основы исчисления предикатов

Особенностью исчисления предикатов является наличие предметных переменных, пробегающих конечную или бесконечную область значений, называемую предметной областью. Отдельные значения этой области называются предметами или объектами.

Какова цель построения исчисления предикатов?

Действительно, ведь необходимо придать формальному языку логического вывода «человеческий», объектовый и событийный смысл. Чтобы видеть и подразумевать предметы и объекты, свойства и обстоятельства, о которых что-то говорится. Чтобы не были истинными такого рода высказывания, как «из-за того, что у льва когти, снег белый». Чтобы лев и снег действенно участвовали в поиске истины.

Введение понятия предметной области сразу же влечёт применение теоретико-множественного аппарата, подобно тому, что привлекался в силлогистике.

Наличие предметных переменных позволяет ввести квантор общности \forall x и квантор существования .

В теории доказательств эти кванторы связаны между собой:

( 3.46)

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

Обычно используют узкое исчисление предикатов, которое разрешает связывать с помощью кванторов лишь предметные переменные. Входящие в формулу предикаты предполагаются при этом неизменными. В так называемом расширенном исчислении предикатов употребляются переменные предикаты и предикатные кванторы.

Как и в случае исчисления высказываний, при построении исчисления предикатов недостаточно указать лишь способ записи формул. Необходимо задать правила преобразования формул, выражаемые аксиомами.

Кроме них, вводятся четыре специфических постулата, которым присвоим номера от 12 до 15:

Источник

4. Исчисление предикатов. Исчисления высказываний заведомо недостаточно для того, чтобы в его рамки уложить «всю» математику. Чего нам не хватает? Мы часто используем такие обороты как «через любые две различные точки можно провести единственную прямую». Здесь задействованы такие языковые средства, как обороты «для любого» («для любых», «для всех») и «существует» (в неявной форме). Эти фундаментальные средства присутствуют при рассмотрении логики предикатов. То есть сейчас помимо логических связок мы будем использовать логические кванторы, а именно квантор всеобщности, обозначаемый далее через A (за неимением опять-таки подходящих шрифтов) и квантор существования, обозначаемый далее через E. Эти обозначения происходят от английских слов «All» и «Exists»; обычно их записывают в перевёрнутом виде (букву «A» располагают «вверх ногами», букву «E» разворачивают «зубчиками» влево).

Часто при изложении этого материала привлекают так называемые функциональные символы, то есть специальные буквы для выражения математических операций. Скажем, через f(x,y) можно обозначить сумму чисел x+y. Функциональные символы отличаются от предикатных тем, что значением выражения f(x,y) является предмет (число, множество и т.д.), а двуместный предикат P(x,y) на данных объектах x, y будет принимать (при фиксированной интерпретации) значение «истина» или «ложь». Мы намеренно отказываемся от функциональных символов, так как вместо рассмотрения двуместного символа f достаточно привлечь трёхместный предикатный символ S, для которого S(x,y,z) означает, что f(x,y)=z. Такой подход сильно упрощает дело, так как становится ненужным давать длинное определение математических выражений (термов). Помимо этого, мы отказываемся также и от часто используемых предметных констант, служащих для обозначения фиксированных объектов. Предметные константы можно считать нульместными функциональными символами, поэтому вместо них рассматриваются одноместные предикатные символы. Скажем, можно ввести предметную константу 0 для обозначения нуля, но можно ввести предикатный символ Z и писать Z(x), если мы хотим выразить ту мысль, что объект x представляет собой не что иное как ноль.

Отметим также, что мы рассматриваем здесь так называемое чистое исчисление предикатов, то есть не используем знака равенства в качестве символа языка. Это удобно, например, при помещении в данный контекст формальной теории множеств, где за основу берётся всего один двуместный предикатный символ P для отношения принадлежности, и при этом запись P(x,y) содержательно означает, что объект x принадлежит множеству y. Равенство множеств стандартным образом определяется через принадлежность.

Нелишне также при этом добавить, что все известные содержательные математические теории (алгебра, топология, арифметика, анализ, теория вероятностей и др.) можно излагать на теоретико-множественном материале. То есть в этом смысле в теорию множеств как бы «укладывается» вся современная математика.

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

Правила образования более сложных формул из более простых можно применять последовательно и в любом порядке конечное число раз. Всякая формула строится в соответствии с этими правилами. Сейчас мы приведём пример формулы, содержательно выражающей справедливость сочетательного закона сложения, то есть равенства (x+y)+z=x+(y+z), справедливого для любых чисел x, y, z. Нам здесь потребуется только трёхместный предикатный символ S(x,y,z), выражающий отношение x+y=z, а символ для отношения равенства даже не потребуется.

Нам будут нужны дополнительные обозначения: u для x+y, v для y+z и w для общего результата (т.е. для x+y+z в обоих вариантах). Содержательно мы имеем равенства x+y=u, y+z=v, u+z=w, x+v=w. Таким образом, сочетательный закон утверждает, что для любых x,y,z найдутся такие u,v,w, что будут выполняться одновременно четыре равенства, выписанные выше. Это приводит к такой формуле: (Ax)(Ay)(Az)(Eu)(Ev)(Ew)(S(x,y,u)&S(y,z,v)&S(u,z,w)&S(x,v,w)).

Если формула Ф не имеет свободных переменных вообще, то она просто выражает некоторую законченную мысль. Такая формула называется замкнутой. При фиксации смысла входящих в неё символов, она превращается в высказывание, то есть становится истинной или ложной.

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

Первые два утверждения говорят о том, что однотипные кванторы (вместе со следующими за ними переменными) можно менять местами. Третье утверждение говорит о том, что если некий объект x «подходит» для всех y, то для каждого y найдётся хотя бы один «подходящий» x, что довольно легко осознать. Однако нижеследующее утверждение

Например, мы можем в качестве предметной области взять множество натуральных (целых неотрицательных) чисел, а двуместный предикатный символ P интерпретировать как отношение «меньше», то есть считать высказывание P^M(m_1,m_2) истинным тогда и только тогда, когда число m_1 меньше числа m_2. Высказывания P^M(3,2) и P^(4,4) будут при этом ложны, а P^M(2,7) будет истинным высказыванием. Нужно чётко понимать, что сам по себе символ P никакого смысла не имеет вообще. Проинтерпретировать же его мы имеем право на любой предметной области как душа пожелает.

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

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

Таким образом, мы сейчас откажемся от использования кванторов существования, поскольку формула (Ex)Ф содержательно выражает ту же мысль, что и ¬(Ax)¬Ф.

Вот какие правила доказательства мы добавляем.

4) Правило обобщения
Пусть утверждение Ф(x) доказано для произвольного x. Тогда можно считать доказанным утверждение (Ax)Ф(x).

5) Правило перехода к частному случаю
Пусть доказано утверждение (Ax)Ф(x). Тогда можно считать доказанным утверждение Ф(y) для любой переменной y.

В рамках исчисления высказываний такой проблемы у нас не было, так как не было предметных переменных. Заметим, что если A есть замкнутая формула, то она не имеет свободных переменных, и никаких ограничений не накладывается. Итак, сформулируем модифицированное правило условного рассуждения, которое будет обозначаться CondP.

Список из пяти правил MP, CondP, Contr, Gen, Part является полным в том смысле, что эти правила позволяют провести любое логическое рассуждение. Точнее говоря, они позволяют доказать логически любую тавтологию исчисления предикатов. Об этом пойдёт речь ниже.

Источник

ИСЧИСЛЕНИЕ ПРЕДИКАТОВ

Полезное

Смотреть что такое «ИСЧИСЛЕНИЕ ПРЕДИКАТОВ» в других словарях:

ИСЧИСЛЕНИЕ ПРЕДИКАТОВ — раздел математической логики, логическое исчисление, в алфавит знаков которого, помимо символов исчисления высказываний, входят также символы вещей (индивидов), их свойств и отношений, а также выражений все и некоторые (кванторы), позволяющие… … Большой Энциклопедический словарь

исчисление предикатов — — [http://www.iks media.ru/glossary/index.html?glossid=2400324] Тематики электросвязь, основные понятия EN predicate calculus … Справочник технического переводчика

исчисление предикатов — раздел математической логики, логическое исчисление, в алфавит знаков которого, помимо символов исчисления высказываний, входят также символы вещей (индивидов), их свойств и отношений, а также выражений «все» и «некоторые» (кванторы), позволяющие … Энциклопедический словарь

Исчисление предикатов — Логика первого порядка (исчисление предикатов) формальное исчисление, допускающее высказывания относительно переменных, фиксированных функций, и предикатов. Расширяет логику высказываний. В свою очередь является частным случаем логики высшего… … Википедия

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

ИСЧИСЛЕНИЕ ПРЕДИКАТОВ — раздел матем. логики, логич. исчисление, в алфавит знаков к рого, помимо символов исчисления высказываний, входят также символы вещей (индивидов), их свойств и отношений, а также выражений все и некоторые (кванторы), позволяющие количественно… … Естествознание. Энциклопедический словарь

УЗКОЕ ИСЧИСЛЕНИЕ ПРЕДИКАТОВ — см. Предикатов исчисление … Математическая энциклопедия

ИНТУИЦИОНИСТСКОЕ ИСЧИСЛЕНИЕ ПРЕДИКАТОВ — см. Интуиционистская логика … Математическая энциклопедия

ПРЕДИКАТОВ ИСЧИСЛЕНИЕ — формальная аксиоматич. теория; исчисление, предназначенное для описания логических законов, справедливых для любой непустой области объектов с произвольными заданными на этих объектах предикатами (т. в. свойствами и отношениями). Для формулировки … Математическая энциклопедия

Исчисление (значения) — В математике термином «исчисление» обозначаются разные области знаний, а также формальные теории (множества формул, полученных из аксиом с помощью правил вывода). Дифференциальное исчисление Интегральное исчисление Вариационное исчисление… … Википедия

Источник

исчисление предикатов

Смотреть что такое «исчисление предикатов» в других словарях:

ИСЧИСЛЕНИЕ ПРЕДИКАТОВ — раздел математич. логики, совокупность логико математич. исчислений, формализующих те разделы совр. логики, в которых отображаются и изучаются (в связи с рассмотрением субъектно предикатной структуры предложений) правила оперирования с… … Философская энциклопедия

ИСЧИСЛЕНИЕ ПРЕДИКАТОВ — раздел математической логики, логическое исчисление, в алфавит знаков которого, помимо символов исчисления высказываний, входят также символы вещей (индивидов), их свойств и отношений, а также выражений все и некоторые (кванторы), позволяющие… … Большой Энциклопедический словарь

исчисление предикатов — — [http://www.iks media.ru/glossary/index.html?glossid=2400324] Тематики электросвязь, основные понятия EN predicate calculus … Справочник технического переводчика

Исчисление предикатов — Логика первого порядка (исчисление предикатов) формальное исчисление, допускающее высказывания относительно переменных, фиксированных функций, и предикатов. Расширяет логику высказываний. В свою очередь является частным случаем логики высшего… … Википедия

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

ИСЧИСЛЕНИЕ ПРЕДИКАТОВ — раздел матем. логики, логич. исчисление, в алфавит знаков к рого, помимо символов исчисления высказываний, входят также символы вещей (индивидов), их свойств и отношений, а также выражений все и некоторые (кванторы), позволяющие количественно… … Естествознание. Энциклопедический словарь

УЗКОЕ ИСЧИСЛЕНИЕ ПРЕДИКАТОВ — см. Предикатов исчисление … Математическая энциклопедия

ИНТУИЦИОНИСТСКОЕ ИСЧИСЛЕНИЕ ПРЕДИКАТОВ — см. Интуиционистская логика … Математическая энциклопедия

ПРЕДИКАТОВ ИСЧИСЛЕНИЕ — формальная аксиоматич. теория; исчисление, предназначенное для описания логических законов, справедливых для любой непустой области объектов с произвольными заданными на этих объектах предикатами (т. в. свойствами и отношениями). Для формулировки … Математическая энциклопедия

Исчисление (значения) — В математике термином «исчисление» обозначаются разные области знаний, а также формальные теории (множества формул, полученных из аксиом с помощью правил вывода). Дифференциальное исчисление Интегральное исчисление Вариационное исчисление… … Википедия

Источник