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

Язык, логика иисчисление предикатов
Введение
Приступая к изучению языка логики предикатов (сокращенно — ЯЛП),полезно вспомнить основные особенности языков этого типа В ЯЛП явно должны бытьпредставляемы субъектно-предикатные структуры высказываний, от которых происхо­дилоотвлечение при введении пропозициональных символов. Выражаемыми должны быть,например, высказывания видов. «aобладает свойством Р», «а иb находятся в отноше­нии Р», «Для всякого предмета из некоторого множества Sверно, что он обладает свойством Р», «Для всякогопредмета из множества Sсуществует предмет этогомножества такой, что эти предметы находятся в отношении R»,«Если неверно, что всякие два предмета некоторого множества находятся вотношении R,то существуют по крайней мере два предмета этого множества, не находящиеся вэтом отношении», «Если во множестве S существует предмет х, который находится в от­ношении R с любым предметом уэтого множества, то для всякого предмета утого же множества существует предмет х такой,что последний находится в отношении Rк первому» и т. п.
Ясно,во-первых, что для выражения таких утверждений у нас нет средств в языке логикивысказываний. Ясно и то, что для выражения подобных высказываний в ЯЛП мы дол­жны иметь в числе егоисходных символов общие имена предметов; аналогами последних в ЯЛП будутпредметные переменные х, у, z,атакже они же с числовыми индексами x₁,x₂,...и т.д. Потребность в общихименах при употребле­ний ЯЛП сохранится лишь для описания областей возмож­ныхзначений этих переменных, что относится уже не к са­мому языку, а к метаязыку.Нужны также знаки свойств и отношений. Для выражения высказываний вида «Объемтела а больше объема тела b» или «Синус х меньше косинуса y» и т. п. необходимы,конечно, и предметные функторы. Впро­чем, перечислим систематически основныетипы выражений описываемого языка, каковыми являются: исходные симво­лы, термыи формулы. Описание этих выражений составит синтаксис ЯЛП.
СИНТАКСИС ЯЗЫКА ЛОГИКИПРЕДИКАТОВ (ИСХОДНЫЕ СИМВОЛЫ, ТЕРМЫ, ФОРМУЛЫ)
I. Исходные символы языка.
1. Предметные переменные х, у, z,а также х с числовыми индексами:

(бесконечное счетноемножество).

 2. Предметные константы (аналоги собственных имен ес­тественногоязыка): (также бесконечное счетноемножество).
3. Знаки свойств и отношений различных местностей — предикатныесимволы, или предикаторы:
P¹, Q ¹, R¹, S¹, ...;
Р2, Q2, R2, S² , ...;
…………………..
Pⁿ,Qⁿ,Rⁿ,Sⁿ
и возможно эти символы с нижними индексами:
P¹₁, P¹₂, P¹₃, …
P²₁, P²₂, P²₃, … и т.д.
(верхниеиндексы указывают на местность предикатора, ни­жние индексы используются длярасширения множества предикаторов той или иной местности; количество предикат­ныхсимволов той или иной местности вводится в зависимо­сти от предназначенияязыка. Однако, поскольку речь идет о языке логики предикатов, должен бытьвведен, по крайней мере один предикатный символ).
4. Знаки предметных функций различных местностей (предметные функторы):
f¹₁, f¹₂, …
f²₁ ,f²₂, …
………….
fⁿ₁, fⁿ₂, …
(числофункциональных символов той или иной местности зависит также от предназначенияязыка, возможно отсут­ствие символов этого рода вообще).
5.Логические константы: ⊃,&,",∃,∨,¬соответствен­но —импликация, конъюнкция, квантор общности, квантор существования, дизъюнкция иотрицание. (Зачастую вво­дят лишь некоторые из этих символов. Из кванторовдоста­точны только ∀или ∃, из остальных, называемыхлогически­ми связками, достаточно: ⊃ и ¬, или  ∨ и ¬, или & и ¬. Другие константы, как,впрочем, и другие знаки, могут вво­диться по определению.)
6. Техническиезнаки: (- левая скобка,)-правая скобка, ,- запятая.
Предметныеконстанты, предикаторы, предметные функ­торы и предметные переменные называютдескриптивными терминами языка, при этом три первых категории (в отличие отпредметных переменных) суть — дескриптивные постоян­ные данного языка.
II. Термы.Выраженияэтого типа являются аналогами имен естественного языка.
Определение:а) любая предметная переменная и предметная константа есть терм; б) если   f¸ⁿ есть n-местный предметный функтор, то f¸ⁿ ( есть терм;  в) ничто, кроме указанного в пунктах а) и б),не есть терм.
III. формулы.В числе этих выраженийимеются аналоги повествовательных предложений естественного языка, а так­жевысказывательные формы — предикаты, представляющие собой особую семантическуюкатегорию, которая не выделяется, — по крайней мере, явным образом — вестественном языке.
Определение:а) если  термы и P¸ⁿ  n-мест­ный предикатор, тоP¸ⁿ ()  есть формула(атомарная);
б)если А и В — формулы, то (А⊃В), (А&В), (AvB), ¬A— формулы;в) если х есть предметная переменнаяи А — фор­мула, то ∀ x A и ∃ xA— формулы; г) ничто, кроме указанно­го в пунктах а) — в), не естьформула.
Договоримся в дальнейшем опускать, когда это удобно, внешние скобки вотдельно взятых формулах; например, вместо (А & В) писать просто
А &В.
Использованныев определениях терма и формулы сим­волы    f¸ⁿ, P¸ⁿ, A, B, x(и в дальнейшем возможно x₁, x ₂и т. д.) — знаки метаязыканазываемые также син­таксическими переменными, возможными зна­чениями которыхявляются выражения соответствующей ка­тегории описываемого (объектного) языка.
Формулы А и В,встречающиеся в пунктах б) и в), назы­ваются подформулами указанных здесьформул.
Введенные понятия исходного символа, терма и формулыязыка являются эффективными (иначе: рекурсивными). По­следнее означает, чтоимеется точный способ, с помощью которого всегда можно определить, относится линекоторый символ к числу исходных символов языка, а для каждойпоследовательности исходных символов можем определить, представляет ли  онатерм или формулу. Для термов и формул такой способ заключен в их индуктивныхопределениях. Так, в каждой формуле, содержащей логические константы (знакилогических операций), имеется главная, или, что то же, последняя, в построенииформулы операции. Выделив  ее, мывыделяем тем самым собственные подформулы этой формулы. В последних сновавыделяем главную операцию и так далее, пока не дойдем до какой-либо атомарнойформу­лы. Если в процессе такого анализа исходного выражения в какой-либо частиего, не являющейся атомарной формулой, нельзя выделить знак главной операции,то эта часть не яв­ляется формулой, а следовательно, таковой не является всевыражение. Возможность распознавания атомарных формул среди последовательностейсимволов является очевидной. (При констатации эффективности введенных понятийподразумевается так называемая абстракция отождествления согласно которой всеразличные случаи употребления некото­рого символа, например а, рассматриваютсякак различные экземпляры, одного и того же символа, и предполагается, что мыумеем узнавать символ, несмотря на некоторые, всегда имеющиеся различия в егонаписаниях.)
СВОБОДНЫЕ ИСВЯЗАННЫЕ ВХОЖДЕНИЯ ПЕРЕМЕНЫХ В ФОРМУЛЫ
Каждыйслучай, когда в последовательности знаков, пред­ставляющей собой формулу А, встречается предметная пере­менная x,называется вхождением этой переменной; каждое вхождение в формулу А предметнойпеременной xв часть вида ∀x В или ∃х В, называется связанным. Под­формула В формул указанного вида называется областью действиясоответственно квантора общности ∀  и квантора существования ∃ с переменной x.Связанным является вхождение переменной, стоящей непосредственно за квантором,и каждое вхождение ее в область действия квантора. Всякое вхождение х в отличие от указанного, на­зываетсясвободным. Переменная х, имеющаясвязанные вхождения и формулу А, называется связанной в этой формуле;переменная, имеющая свободные вхождения в формулу А, называется свободной в этойформуле.
Обратимвнимание на то, что согласно определению свободной и связанной переменной однаи та же переменная в одной и той же формуле может быть свободной и связанной.Такова, например, переменная  x₁в формуле ∀ x₁ P¹(x₁) ∨ Q²(x₁, x₂);  переменная x₂
 является здесь свобод­ной, но не связанной. Мырассматриваем здесь только такие термы, в которых все переменные могут иметьлишь свобод­ные вхождения, и, значит, являются свободными переменны­ми. Формулаи терм, не содержащие свободных переменных, называются соответственно замкнутойформулой и замкнутым т е р м о м (очевидно, что для рассмат­риваемых здесьтермов, если терм замкнут, то он вообще не содержит переменных).

СЕМАНТИКАЯЗЫКА ЛОГИКИ ПРЕДИКАТОВ
Семантику языка, как мы видели при анализе естественногоязыка, составляет совокупность предметных значений и смысловых содержаний еговыражений. Но в данном случае, поскольку речь идет не об анализе уже имеющегосяязыка, а  о построении — в данном случаелогического формализованного языка —то семантикой называют совокупностьправил  приписывания значений выражениямэтого языка. Точнее говоря, здесь даже не ставится задача построения какого-тоопределенного языка. Создается лишь некоторая схема язы­ка определенного типа,в данном случае так называемой классической логики предикатов первого порядка.Этот тип языка отличается от языков других типов, даже языков с тем жесинтаксисом (например, языка интуиционистской логики предикатов, определеннойсистемы релевантной логики) своей семантикой. Приписывание значений отдельнымвыражениям языка, составляющим дескриптивным терминам, употребляемым припостроении формул, осуществляет­ся лишь в составе тех или иных формул и при этом различно от случая к случаю в зависимостиот характера решаемых логических задач, (например, при переводе каких товысказываний с естественного языка на данный формализован­ный, при анализелогических отношений между формулами данного языка, при аксиоматизациинекоторых теорий, а именно при формулировке их аксиом в языке данного типа). Совокупностьвсех правил приписывания значений выраже­ниям языка разбивается на следующиетри группы (I,II,III).
I.Правилаопределения (задания) возможных значений предметных переменных и правилаприписывания предмет­ных значений дескриптивным постоянным в составе рас­сматриваемыхв том или ином случае формул—интерпрета­ция выражений языка. II. Правилаприписывания значений свободным переменным в составе тех или иных рассматри­ваемыхформулу. III. Правила приписывания истинностных значений интерпретированнымформулам, не содержащим свободных переменных.  I. Интерпретация состоит,во-первых, в выборе некоторо­го непустого множества Dиндивидов, предметов того или иного типа, к которым могутотноситься образуемые из тех или иных формул языка высказывания. Индивиды — любые предметы в широком смысле этогослова, структура которых не учитывается, и которые можно отличать друг отдруга. В качестве такой области Dможно взятьмножество людей, растений, городов, чисел и т. д.; возможно, также объедине­ниев одной области множеств различных предметов, напри­мер, людей, городов, домов(положим, для выражения выска­зываний о местах жительства людей). Но при этом все различные предметы,рассматриваются именно как индивиды. Область D — это область возможных значений предметных переменных символыпредметных переменных х, у, z, стано­вятсяименно переменными лишь при указании области их возможных значений.Предполагается, что на области Dопределенонекоторое множество свойств, отношений и характеристик предметно-функциональноготипа (то есть возможных значений предикаторов и предметных функторов).
Второймомент интерпретации языка состоит в задании некоторой функции j
 (интерпретационная функция) приписываниязначений дескриптивным постоянным (предметным константам, предикаторам,предметным функторам опять-таки в составе рассматриваемых формул). Задание j
 в каж­дом конкретном случае представляет собойпросто указание на то, какие значения должны быть приписаны упомянутым исходнымсимволам языка в составе рассматриваемых формул. При этом предметным константам(простые постоянные термы) приписываются в качестве предметных значенийопределенные предметы из заданной области D.Предикатно­му (n-местному) символу P¸ⁿ  при n =1 в качестве значения приписываютсянекоторые свойства а при n > 1 — n-местное отношение (между предметами В).Например, если область Dесть множество целых положительных чисел, то предикат­ному символу P¹₁ можно приписать в качестве значения свойство«четно», а предикатору P²₁  отношение «больше» или «меньше». Предметномуфунктору fⁿ₁   в качестве пред­метного значения функция j
приписываеткакую-нибудь n-местную предметную функцию,определенную на обла­сти D. Например,для области чисел таковыми могут быть си­нус, косинус (одноместные функции),сумма, произведение (двухместные функции), для области людей — одноместные(возраст, рост), для области материальных тел — объем, удельный вес.
Значениясложных термов, каковыми являются также предметы из области D, и приписывание которых составляет ихинтерпретацию, вычисляются в зависимости от припи­санных уже значений ихпростым составляющим — пред­метным константам, предметным функторам, а также ивоз­можным предметным переменным, значения которых при­писываются по правиламII. Вычисление происходит в соот­ветствии с правилами построения сложноготерма. Сложные термы образуются, как мы видели, с применением предмет­ныхфункторов и строятся индуктивно. Значение такого тер­ма вычисляетсяпоследовательно в соответствии с порядком его построения.
Пример.Имеем терм f²₁(f²₁(a₁,a₂), f²₂(a₁, a₃)).
 Пусть область D — целые положительные числа, a₁  есть число 3, a₂  =4, a₃  = 5, f²₁ —сумма, f²₂   —произведение.
Тогда
f²₁(a₁, a₂)=7;
f²₂(a₁, a₃)=15;
f²₁(f²₁(a₁, a₂), f²₂(a₁, a₃))=22.
II.Свободным переменным в тойили иной формуле (а тем самым и в составе термов этой формулы) в качествезначений приписывают, также как и постоянным термам, предметы из области D.Такие приписывания осуществляют­ся когда мы хотим получить изинтерпретированной форму­лы со свободными переменными высказывание нашего язы­ка.Приписывание осуществляют заменой каждого вхожде­ния некоторой свободнойпеременной какой-либо предмет­ной константой с одновременной интерпретациейтаковой, если она еще не была интерпретирована в формуле.
Будемговорить, что при осуществлении этих приписыва­ний в добавление к уже имеющейсяинтерпретации форму­лы, формула оказывается полностью интерпретированной.
Однако важнозаметить, что формулы со свободными пе­ременными нужны не только дляобразования высказываний из них. Они представляют собой особые высказывательныеформы, называемые предикатами. Это сложные знаковые формы возможных свойствпредметов заданной области и возможных отношений среди этих предметов. По типуих предметных значений они должны быть отнесены к катего­рии предакаторов.Можно назвать их сложными предикаторами (в отличие от простых, указанных средиисходных сим­волов). Надо отметить, что эти формы не выделяются и даже незамечаются в естественных языках. Они играют, однако, решающую роль в теориипонятия. Имея тот или иной предикат, можно ставить вопрос, для каких пред­метов,которые могут представлять свободные переменные, этот предикат выполняется илине выполняется. В таком слу­чае мы просто указываем предметы длясоответствующих переменных (не осуществляя указанных подстановок пред­метныхконстант вместо них). Например, можно сказать, что предикат «(Р2(x, a₁) >∃yQ2(x, y))», — выражающий свойствокакого-то числа х из областинатуральных чисел, состоящее в том, что «если это число больше 5 (знаками отношения«больше» и «5»является соответственно Р2и a₁ то оно де­лится без остатка (Q2) нанекоторое число у», выполняется длячисел 6, 8, 9 и т. д., но не выполняется для 7, 11 и др.
III.Приписывание истинностныхзначений полностью интерпретированным формулам.
Напомним,что полностью интерпретированная форму­ла — это формула, в которой осуществленаинтерпретация дескриптивных постоянных и приписано значение всем сво­боднымпеременным, если таковые имеются в ней. Каждая такая формула представляет собойопределенное высказыва­ние — с определенным смыслом и истинностным значени­ем —но лишь при условии, если нам известны значения встречающихся в ней — явным илинеявным образом — ло­гических констант, (которые и определяются рассматривае­мымиправилами III). Явным образом указываются — в сложных формулах — логическиеконстанты, перечислен­ные в списке исходных символов. Простые атомарные фор­мулы видов Pⁿ (t₁, …,tn)
по-видимому,не содержат логиче­ских констант. Однако, неявным образом здесь присутствуетлогическое отношение принадлежности свойства Р некото­рому предмету tпри n= 1 или о наличииотношения Pⁿ  меж­ду предметами  t₁, …,tnиз области D.
Определение значений всехлогических терминов, как явно обозначенных, так и неявно содержащихся в форму­лах,осуществляется как раз посредством правил приписыва­ния истинностных значенийполностью интерпретирован­ным формулам нашего языка (строго говоря, мы имеемздесь так называемое неявное определение логических констант, но они достаточныдля понимания того, какой именно смысл они придают нашим высказываниям).
Правила этитаковы. Значение простого (атомарного) вы­сказывания Pⁿ (t₁, …,tn), n>= 1, определяется в зависимости от заданныхзначений термов t₁, …,tnи предикатора Pⁿ   . Оно за­висит от характера предметов даннойпредметной области. Положим, имеем формулу: P²(f¹₁ (a₁), f¹₁(a₂)). Предположим, что согласно заданнойинтерпретации D — множество лю­дей: Р2 означает «больше»: f¹₁  «возраст»: a₁— Петров, a₂— Сидоров. Вся формулапредставляет собой высказывание «Возраст Петрова больше, чем возраст Сидорова».Высказывание истинно или ложно в зависимости от того, имеет или неимеет место данное отношение между возрастами Петрова и Сидорова.
Заметим,что в части лексики мы перевели здесь высказыва­ние, полученное из определеннойформулы рассматриваемого язы­ка (ЯКЛП), по существу на обычный естественныйрусский язык. В самом ЯКЛП знаковой формой его является упомянутая формула.Подобные переводы обычно напрашиваются сами собой в силу того, что заданиезначений отдельных терминов — составляющих формулу — осуществляется посредствомвыражений естественно­го языка. Мы говорим «значение Р2 — больше, a₁ и a₂ — соответ­ственно Сидоров и Петров» и т. п.).Это значит, что приписывание предметных значений выражениям описываемого языкаосуще­ствляется методом перевода их в тот или иной естественный язык. Можетпоказаться, что при упомянутых переводах высказываний данного языка наестественный теряется та самая точность их вы­ражений, ради достижения которойкак раз и строятся формализо­ванные языки. Однако точность здесь по сравнению сестествен­ными языками достигается не за счет более точною употребленияотдельных терминов, — достаточная точность их уже должна быть обеспеченапри осуществлении интерпретации выражений форма­лизованного языка — а за счетопределенных, стандартных спосо­бов построения высказываний и их логическихформ. И она имен­но сохраняется, или точнее сказать, должна сохраняться при ука­занныхпереводах.
Длясложных формул имеем, предполагая, что все составляю­щие их формулы полностьюинтерпретированы.
Формулавида А & В имеет значение «истина» — при данной интерпретации иприписывании значений свободным перемен­ным — е. т. е. А имеет значение И и Вимеет значение И.
ФормулаAvВ — истина е. т. е. значение А равно И или значе­ние В равноИ.
Формулевида  А ⊃В приписывается значение Ие. т. е. А имеет значение Л или Вимеет значение И.
Значениемформул вида ¬А является И е.т.е. значение А есть Л.
Формулавида ∀х А(х)имеет значение «истина» е.т. е. для вся­кого предмета а(i)из D, А(а(i)) — истина (А(а(i)) — результат заме­щениявсех свободных вхождений х в А(х) константой а(i)¹).
Формулавида ∃х А(х)имеет значение истина е. т.е. существует предмет а в области Dтакой, что истинна формула A(a(i)).
Если значение некоторой формулы не является И, то она имеетзначение Л, но никакая формула не имеет одновременно значения И и Л.
Как уже говорилось, правила приписывания истинностных зна­ченийполностью интерпретированным формулам неявным обра­зом определяют также значениялогических констант «&», «v», «⊃», «¬»   и кванторов ∀и ∃и вместе стем и смыслы высказыва­ний, образованных посредством соответствующих констант.На­пример, высказывания вида   ∀х А(х),∃  х А(х), относящиеся к неко­торой областииндивидов D, мы должны понимать,соответственно, как «для всякого предмета хиз D верно А(х}» и «существует пред­мет хв D такой, что верно А(х)». Нетрудно видеть, что &, v, ⊃,¬,представляют собой здесь логические связки — знаки функций ис­тинности, —определенные ранее в разделе «Логика высказыва­ний», но теперь применительно кформулам ЯЛП.
Примеры
Определимзначение формулы —
∀x((P²(x, a₁) & P²((x, a₂))⊃ P²(x,y))
приусловии, что область возможных значений переменных D есть множество целыхположительных чисел, константам a₁  и a₂приписаны соответственночисла 2 и 3, свободной пе­ременной у —значение 6; предикатный символ Р2 имеет в качестве значенияотношения «делится». Ясно, что при ука­занной интерпретации данная формулавыражает определен­ное высказывание: в переводе на русский язык, «Для всяко­гоцелого положительного числа х верно,что если оно делит­ся на 2 и на 3, то оно делится на 6». Ясно, что это высказы­ваниеи соответственно наша формула истинны. Рассмотрим формулу  ∀x  ∃yP²(y, x).Если D — множество людей, Р2 — отец, то она представляетсобой высказывание «Для всякого человека хсуществует человек у такой, что онявляется от­цом первого».
Как ужесказано, полностью интерпретированные фор­мулы языка при учете правил IIIпредставляют собой выска­зывания этого языка, а интерпретированные формулы сосвободными переменными — предикаты (знаковые формы сложных свойств и отношенийсоответствующей области предметов D).Неинтерпретированные формулы, не содержа­щие свободных переменных, — сутьлогические формы вы­сказываний, а со свободными переменн