Язык логики предикатов

Язык логики предикатов

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

Построение формализованного языка начинается с задания его алфавита – совокупности исходных символов, которые подразделяются на нелогические, логические и технические.

Нелогическими (дескриптивными) символами данного формализованного языка являются параметры нелогических терминов естественного языка, относящиеся к различным категориям, – именам, предметным функторам и предикаторам.

Первую группу символов составляют индивидные константы. В качестве символов указанного типа будем использовать буквы а, b, с и d без индексов или с индексами (в качестве которых используем целые положительные числа):

а, b, с, d, a1, b1, c1, d1, а2,...

При переводе выражений естественного языка на язык логики предикатов простые имена заменяются предметными константами, причем одинаковые имена – одинаковыми символами из данного списка, а различные – различными.

Вторую группу нелогических символов составляют п-местные предметно-функциональные константы (п ≥ 1) – параметры n-местных функторов естественного языка:

fn, gn, hn, f1n, g1n, h1n, f2n,...

Верхний индекс указывает на местность константы. Одноместный предметный функтор «столица» может быть замещен, например, константой f1, а двухместный предметный функтор «расстояние от... до...» – параметром g2.

Третью группу составляют п-местные предикаторные константы (п ≥ 1)  – параметры предикаторов естественного языка:

Рn, Qn, Rn, Sn, Р1n, Q1n, R1n, S1n Р2n,...

Верхний индекс опять-таки указывает на местность константы. Одноместный предикатор «человек» может быть замещен, например, предикаторной константой Р1, а двухместный предикатор «севернее» – параметром Q2.

Иногда верхние индексы предметно-функциональных и предикаторных констант опускают. В этом случае запрещается использовать один и тот же символ для функторов и предикаторов различной местности.

В языке логики предикатов имеется еще одна группа нелогических (дескриптивных) символов. Это так называемые предметные (индивидные) переменные:

x, y, z, x1, y1, z1, x2,...

Логические символы языка классической логики предикатов бывают двух типов. К первому относятся пропозициональные связки – знаки функций истинности. Выберем в качестве исходных связок ¬, &, ∨, ⊃, которые составляют функционально полную систему. Ко второму типу относятся кванторы: ∀ – квантор общности и ∃ – квантор существования.

Техническими символами являются левая и правая скобки, а также запятая.

Построение алфавита языка логики предикатов завершено.

Термы и формулы логики предикатов первого порядка

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

Определение терма:

1.  Произвольная предметная константа является термом.

2.  Произвольная предметная переменная является термом.

3. Если Ф – n-местная предметно-функциональная константа, а
t1, t2,..., tn – термы, то выражение Ф(t1, t2,..., tn) является термом.

4.  Ничто иное не является термом.

Выражения, указанные в пунктах 1 и 2 данного определения, называются простыми термами,  а те, которые указаны в пункте 3, – сложными.

Символы a, b1, с3, например, относятся к числу термов согласно п.1 определения, а символы х2, у, z10 являются термами согласно п.2. Символы f1, P2 и ∀ не являются термами, поскольку не относятся ни к числу предметных констант или предметных переменных, ни к числу выражений вида Ф(t1, t2,..., tn).

Определим, является ли термом выражение f1(g2(х, а)). Данная последовательность знаков имеет вид Ф(t), где Ф есть f1 – одноместная предметно-функциональная константа. Согласно п.3, данное выражение есть терм, если t,
т. е. g2(х, а) является термом. Выражение g2(х, а) имеет вид Ф(t1, t2), где Ф есть g2 – двухместная предметно-функциональная константа, t1 есть х – терм (согласно п.2), t2 есть а – терм (согласно п.1). Поэтому, согласно п.3, g2(x, а) является термом. Значит, и выражение f1(g2(х, а)) – терм.

Выражение Р1(g2(x, а)) не является термом, поскольку оно начинается не с предметно-функциональной, а с предикаторной константы. Выражение вида h2(g2(x, а)) не является термом, так как оно начинается с двухместной предметно-функциональной константы h2, а в скобках после нее находится один терм g2(x, а), а не два терма, как того требует п.3 определения.

Поясним на примерах, каким образом осуществляется перевод имен естественного языка на язык логики предикатов.

Пусть простому имени «4» соответствует предметная константа а, а простому имени «5» – константа b, одноместному предметному функтору «√» сопоставим одноместную предметно-функциональную константу f1 (или просто f), а двухместному функтору «+» – двухместную предметно-функциональную константу g2 (или просто g). Тогда, при переводе на язык логики предикатов сложным именам будут соответствовать следующие термы:

имени «» – терм f(a),

имени «4 + 5» – терм g(a, b),

имени «5 + 4» – терм g(b, a),

имени « + 5» – терм g(f(a), b),

имени «» – терм f(g(a, b)),

имени «(4 + 4) + (5 + 5)» – терм g(g(a, a), g(b, b)).

Пусть теперь константа а сопоставлена простому имени «Москва», b – имени «Киев», с – «Россия», d – «Украина»; одноместному предметному функтору «столица» сопоставим символ f, а двухместному функтору «расстояние от... до...» – символ g. Тогда при переводе на язык логики предикатов сложным именам будут соответствовать следующие термы:

«столица России» – f(c),

«расстояние от Москвы до Киева» – g(a, b),

«расстояние от Москвы до столицы Украины» – g(a, f(d)),

«расстояние от столицы России до Киева» – g(f(c), b).

Другой тип правильно построенных выражений языка логики предикатов – формулы.

Определение формулы:

1. Если П – n-местная предикаторная константа, t1, t2,..., tn – это термы, то выражение П(t1, t2,..., tn) является формулой.

2. Если А – формула, то ¬A – формула.

3. Если А и В – формулы, то (А & В), (A ∨ В), (А ⊃ В) – формулы.

4. Если А – формула, а α – предметная переменная, то ∀αA и ∃αА являются формулами.

5. Ничто иное не является формулой.

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

Элементарной является, например, формула Р2(х, f1(a)), поскольку Р2 – двухместная предикаторная константа, а в скобках после нее находятся два терма – х и f1(а). Выражение Ql(x, f1(a)) не является формулой, так как константа Q1 – одноместная и после нее в скобках должен стоять один, а не два терма. Выражение Р2(х, Q1(a)) также не относится к числу формул, ибо Q1(a) не есть терм.

Выражение ∀хР2(х, f1(а)) является формулой согласно п.4 определения, поскольку после кванторного символа ∀ находится предметная переменная x, а далее – формула Р2(х, f1(а)). Выражение ∀аР2(х, f1(а)) не есть формула, поскольку после ∀ стоит не предметная переменная, а предметная константа а. Выражение ∀xg2(х, f1(а)) также не является формулой, так как после кванторного комплекса ∀x находится терм g2(х, f1(а)), а не формула.

Простые высказывания, в которых утверждается наличие свойства у отдельного предмета, записываются в языке логики предикатов посредством формул вида П1(t), где t есть терм, соответствующий имени предмета, а П1 – одноместная предикаторная константа, соответствующая знаку свойства. Например, переводом высказывания «Ромео – юноша» может быть формула Р(а), где предметная константа а соответствует имени «Ромео», а одноместная предикаторная константа Р – знаку свойства «юноша». Высказывание «Отец Ромео храбр» может быть записано в виде Q(f(a)), если одноместному предметному функтору «отец» сопоставить одноместную предметно-функциональную константу f, а знаку свойства «храбрый» – одноместную предикаторную константу Q.

Высказывания, в которых отрицается наличие свойства у отдельного предмета, переводятся на язык логики предикатов посредством формул вида ¬П1(t). Например, переводом высказывания «Отец Ромео не является юношей» будет формула ¬Р(f(а)).

Высказывания, в которых утверждается наличие отношения между двумя предметами, записываются в виде формул П2(t1, t2), где П2 – двухместная предикаторная константа, соответствующая знаку двухместного отношения, a t1 и t2 – термы, соответствующие именам предметов. Например, высказывание «Ромео любит Джульетту» может быть записано в виде R(a, b), где R соответствует двухместному предикатору «любит», а а и b – именам «Ромео» и «Джульетта», соответственно. Переводом высказывания «Джульетта любит саму себя» будет формула R(b, b), a переводом высказывания «Джульетта любит своего отца» – R(b, f(b)).

Высказывания, в которых отрицается наличие отношения между двумя предметами, выражаются с помощью формул вида ¬П2(t1, t2). Например, переводом высказывания «Отец Ромео не любит отца Джульетты» является формула ¬R(f(a), f(b)).

Вообще, высказывания о наличии отношения между п предметами записываются в виде Пn(t1, t2,..., tn), где Пn – n-местная предикаторная константа, соответствующая знаку n-местного отношения. Например, высказывание «Джульетта любит Ромео больше, чем своего отца» может быть записано в виде формулы R1(b, a, f(b)), где R1 – трехместная предикаторная константа, соответствующая трехместному отношению «любит больше, чем».

Высказывания об отсутствии отношения между п предметами переводятся посредством формул вида ¬Пn(t1, t2,..., tn).

Высказывания, в которых говорится о существовании объекта, удовлетворяющего некоторому условию, записываются в языке логики предикатов посредством формул вида ∃αА(α), где α – индивидная переменная, пробегающая по области объектов, о которых идет речь в высказывании, а А(α) – формула, выражающая утверждение о том, что α удовлетворяет условию А. Например, высказывание «Кто-то является храбрым» может быть переведено формулой ∃xQ(x), где х здесь и далее пробегает по классу людей, а Q – одноместная предикаторная константа, соответствующая предикатору «храбрый». Высказывание «Кто-то не является храбрым» может быть записано как ∃x¬Q(x). Высказывание «Кто-то любит Джульетту» переводится с помощью формулы вида ∃xR(x, b), где R соответствует двухместному предикатору «любит», a b – имени «Джульетта». Высказывание «Джульетта любит кого-нибудь» может быть записано в виде ∃xR(b, x), а высказывание «Кто-то не любит самого себя» – в виде ∃x¬R(x, x).

Высказывания, в которых утверждается, что условию А удовлетворяет любой объект предметной области, переводятся на язык логики предикатов формулами вида ∀αA(α). Например, высказыванию «Все являются храбрецами» соответствует ∀xQ(x), высказыванию «Всякий любит Джульетту» – ∀xR(x, b), высказыванию «Никто не любит отца Ромео» – ∀x¬R(x, f(a)), высказыванию «Отец Ромео не любит никого» – ∀x¬R(f(a), x).

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

Высказыванию «Каждый любит кого-нибудь» соответствует формула ∀x∃yR(x, у); высказыванию «Кто-то кого-то не любит» – формула ∃x∃y¬R(x, у); высказыванию «Кто-то любит Ромео больше, чем кого-либо» – формула ∃х∀уR1(х, а, у).

В состав каждого из рассмотренных ранее высказываний входил только один предикатор – «юноша», «храбрый», «любит» или «любит больше, чем». Однако простые высказывания могут содержать два, три и более предикаторов. Каким же образом осуществляется их формальная запись? Если подобное высказывание содержит квантор, то его переводом будет формула вида ∃αА(α) или ∀αA(α) с той лишь разницей, что условие А(α) будет иметь более сложную структуру.

Начнем с формальной записи высказываний, содержащих два одноместных предикатора. Высказывание «Некоторый юноша храбр» может быть переведено на формальный язык посредством формулы ∃х(P(х) & Q(х)), которая имеет следующий буквальный смысл (с учетом того, что константам Р и Q соответствуют предикаторы «юноша» и «храбрый») – «Существует объект х (человек), который является юношей и является храбрым». Этот смысл в точности соответствует смыслу исходного высказывания. Высказывание «Всякий юноша храбр» может быть записано как ∀x(P(x) ⊃ Q(x)). Буквальный смысл этой формулы – «Для всякого объекта х (из класса людей) верно, что если он юноша, то он храбр» – также соответствует смыслу исходного высказывания. Отрицательные высказывания «Некоторый юноша не храбр» и «Ни один юноша не храбр» могут быть переведены соответственно формулами ∃х(P(х) & ¬Q(х)) и ∀x(P(x) ⊃ ¬Q(x)).

Рассмотрим теперь простые высказывания с одним одноместным и одним двухместным предикатором.

Например, переводом высказывания «Некоторый юноша любит Джульетту» будет формула ∃х(P(х) & R(x, b)) – «Существует человек х такой, что он является юношей и любит Джульетту». Переводом высказывания «Джульетта любит какого-то юношу» является формула ∃х(P(х) & R(b, x)) – «Существует человек х такой, что он является юношей и Джульетта любит его». Переводом высказывания «Каждый юноша любит Джульетту» является формула ∀x(P(x) ⊃ R(x, b)) – «Для всякого человека х верно, что если он юноша, то он любит Джульетту».

Более трудными являются случаи, когда в состав высказываний об отношениях входят несколько одноместных предикаторов. Рассмотрим, например, высказывание «Всякий юноша любит какую-нибудь девушку». Как и раньше, предикаторам «юноша» и «любит» сопоставим константы Р и R, а одноместному предикатору «девушка» сопоставим одноместную предикаторную константу S. Тогда формальная запись нашего высказывания может иметь следующий вид: ∀x(P(x) ⊃ ∃у(S(у) & R(x, у))). Буквальный смысл этой записи с учетом принятых обозначений – «Для всякого x из класса людей, верно, что если он юноша, то существует у из этого же класса такой, что он девушка и х любит у» – в точности соответствует смыслу исходного высказывания. Высказывание «Некоторые юноши любят всякую девушку» может быть выражено формулой ∃х(Р(х) & ∀х(S(y) ⊃ R(x, у))) – «Существует человек х из класса людей такой, что он юноша и для всякого человека у верно, что если у – девушка, то х любит у». Соответствующим переводом высказывания «Некоторые юноши не любят ни одной девушки» является формула ∃х(Р(х) & ∀y(S(у) ⊃ ¬R(х, y))).

Приведем еще несколько достаточно трудных примеров формальной записи простых высказываний естественного языка:

«Всякий храбрец является юношей или девушкой» –

∀х(Q(х) ⊃ (Р(х) ∨ S(х)));

«Всякая храбрая девушка не любит ни одного нехраброго юношу» –

∀х((S(х) & Q(х)) ⊃ ∀у((Р(у) & ¬Q(у)) ⊃ ¬R(х, у)));

«Всякий юноша любит некоторую девушку больше, чем отца этой девушки» –

∀х(Р(х) ⊃ ∃у(S(у) & R1(х, у, f(у))));

«Некоторая девушка, отец которой храбр, любит его больше, чем некоторого не храброго юношу» –

∃х(S(х) & Q(f(х)) & ∃у((Р(у) & ¬Q(у)) & R1(х, f(х), у))).

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

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

Область действия квантора.

В формулах вида ∀αA и ∃αA формула А называется областью действия квантора (∀ или ∃) по переменной α.

Например, в формуле ∀х(∃у¬P(х, у) ⊃ Q(у, z)) областью действия квантора ∀ по переменной х является формула ∃у¬P(х, у) ⊃ Q(у, z), а областью действия квантора ∃ по переменной у – формула ¬P(х, у):

∀х(∃у¬P(х, у) ⊃ Q(у, z))

область действия квантора ∃ по у

область действия квантора ∀ по х.

В произвольной форм, 2 и т. д.). Иначе говоря, переменная имеет некоторое число вхождений в данную формулу. Например, в формуле ∀х(∃у¬P(х, у) ⊃ Q(у, z)) переменная x имеет два вхождения, у – три вхождения, z –одно вхождение, а остальные переменные – ни одного вхождения.

Свободные и связанные вхождения переменных.

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

Например, в формуле, указанной выше, первые вхождения переменных х и у связаны, поскольку они следуют непосредственно за кванторами ∀ и ∃. Второе вхождение х находится в области действия квантора ∀ по переменной x, т. е. в формуле ∃у¬P(х, у) ⊃ Q(у, z), а второе вхождение у расположено в области действия квантора ∃ по переменной у, т. е. в формуле ¬P(х, у), поэтому указанные вхождения являются связанными. Что же касается третьего вхождения переменной у и единственного вхождения z, то они являются свободными.

∀х(∃у¬P(х,  у) ⊃ Q(у,  z))

свободные вхождения переменных

связанные вхождения переменных

Свободные и связанные переменные.

Предметная переменная называется свободной в некоторой формуле, если существует по крайней мере одно ее свободное вхождение в эту формулу. Переменная называется связанной в формуле, если существует по крайней мере одно ее связанное вхождение в эту формулу.

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

Местность терма.

Местность терма есть число входящих в него различных предметных переменных.

Замкнутые термы.

Терм, не содержащий в своем составе предметных переменных, называется замкнутым.

Например, терм f(x, у, z) является трехместным, так как именно это число различных переменных встречается в его составе, термы f(x, b, z) и f(х, у, у) – двухместные, терм f(x, b, а) – одноместный, а терм f(c, b, a) – нульместный, т. е. замкнутый терм. Замкнутые (нульместные) термы являются аналогами имен естественного языка; поэтому и результатом перевода любого имени естественного языка на язык логики предикатов должен являться именно замкнутый терм.

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

Местность формулы.

Местность формулы логики предикатов первого порядка есть число входящих в нее различных свободных предметных переменных.

Замкнутые формулы (предложения).

Формула, не содержащая свободных переменных, называется замкнутой. Замкнутые формулы есть предложения.

Обратите внимание на принципиальное отличие определения местности формулы в логике высказываний и логике предикатов. Если в логике высказываний местность формулы определялась простым подсчетом числа различных пропозициональных переменных, входящих в ее состав, то в логике предикатов мы должны подсчитывать не просто различные индивидные переменные, входящие в формулу, а именно различные свободные индивидные переменные. С учетом только что сказанного, формула ∀х(∃у¬P(х, у) ⊃ Q(у, z)) является двухместной, поскольку она содержит две различные свободные переменные – у и z, а формула ∃z∀х(∃у¬P(х, у) ⊃ ∀yQ(у, z)) не имеет ни одной свободной переменной, поэтому она нульместная, т. е. замкнутая. Результатом перевода произвольного высказывания естественного языка обязательно должна быть замкнутая формула.

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

подстановкой вместо свободных индивидных переменных замкнутых термов, или квантификацией свободных индивидных переменных.

Так, применяя к выражению прикладного языка логики предикатов первого порядка х у, где х и у пробегают по натуральным числам, первый способ элиминации свободных переменных, т. е. подставляя вместо х, скажем, терм
5 + 4, а вместо у терм √81, получим выражение 5 + 4 √81, которое является ложным предложением. Применяя же к этому выражению второй способ элиминации свободных переменных – квантификацию переменных, – можно получить, например, выражение ∀х∃у(х у), которое является истинным предложением, утверждающим, что в натуральном ряду чисел относительно любого числа существует число, которое больше его, т. е. утверждающего, что натуральный ряд чисел бесконечен. При другой расстановке кванторов можно получить, например, выражение ∃у∀х(х у), которое является ложным предложением, так как утверждает, что в натуральном ряду чисел есть наибольшее число, но такого числа, как известно, нет. Отсюда видно, что замкнутые высказывательные формы действительно являются предложениями.