426
ЛОГИКА ПРЕДИКАТОВ Другое расширение стандартной логики предикатов связано с рассмотрением т. н. обобщенных кванторов (кванторов Генки на). Если в стандартной кванторной приставке любой формулы, находящейся в предваренной нормальной форме, каждый квантор содержится в области действия всех предшествующих ему кванторов, то обобщенные кванторы представляют собой кванторные комплексы, составляющие которых не обязаны более быть упорядочены отношением строгого линейного порядка. Введение обобщенных кванторов позволяет строить адекватные модели достаточно сложных фрагментов естественного языка. В первопорядковой логике предикатов, как уже говорилось, разрешается квалификация только предметных переменных, т. е. кванторы могут быть соотнесены лишь с предметами, индивидами («всякий предмет», «некоторый предмет»). Для логического анализа контекстов, в которых кванторы соотносятся также со свойствами, отношениями, функциями, необходим переход к логике второго порядка. В алфавите ее языка наряду с предикаторными константами Р", Qn, Rn, Р^,... имеются предикаторные переменные различной местности Р1, Q", /Р1, Р,п,— (в алфавит могут быть введены также и предметно-функциональные переменные/, g", /*",/[",.-•)• В атомарных формулах n(t,,t2,...,tn) на месте П могут использоваться как предикаторные константы, так и предикаторные переменные(аналогично,всложныхтермахФ(1],12,...Дп)вроли Ф может выступать теперь предметно-функциональная переменная). «Кванторные» пункты в определении формулы видоизменяются за счет разрешения использовать в формулах видов VolA и ЗаА на месте а не только предметные, но также предикаторные и предметно-функциональные (если они есть в алфавите) переменные. Средствами языка второпорядковой логики предикатов могут быть воспроизведены логические формы многих высказываний, которые нельзя выразить в первопорядковом языке (напр., «У Марса и Земли есть общие свойства» — ЗР(Р(а) л Р(Ь)), «Марс обладает всеми свойствами, присущими каждой планете» — V/\\/x(S(x) z> Рх)) z> P(a)), где константам a, b и S соответствуют термины «Марс», «Земля», «планета»). Семантически логика предикатов второго порядка строится по аналогии с первопорядковой. При распределении значений переменных предикаторным и предметно-функциональным переменным приписываются сущности тех же типов, которые сопоставляются в модели соответствующим константам. Правила установления значений термов и формул незначительно адаптируются с учетом синтаксических особенностей второпоряд- кового языка. Понятие общезначимой формулы — обычное. Синтаксическое построение логики предикатов второго порядка сталкивается с фундаментальной проблемой метатео- ретического характера — класс общезначимых формул второпорядковой логики принципиально не аксиоматизируем, не формализуем, т. е. не существует исчисления, класс теорем которого совпадал бы с классом общезначимых формул. Тем не менее в качестве второпорядкового исчисления предикатов обычно рассматривают некоторую неполную формальную систему, которая получается естественным обобщением первопорядкового исчисления. Логика предикатов второго порядка является очень богатой логической теорией. В ней, напр., может быть определен пре- дикатор равенства: а = ? = DftP(P(a) = Рф)) (это определение по своей сути повторяет лейбницевский принцип «тождественности неразличимых»: равными, тождественными объявляются объекты, обладающие одинаковыми свойствами). Один из возможных путей расширения выразительных средств логики второго порядка состоит во введении в ее язык предикаторов более высоких ступеней, «предикаторов от предикаторов». Они выражают свойства свойств или отношений, отношения между свойствами или отношениями. Так, в контексте «Отношение родства симметрично» термин «симметрично» репрезентирует свойство отношения (родства), а в контексте «Щедрость и скупость — противоположные качества» термин «противоположно» представляет отношение между свойствами (щедростью и скупостью). При указанном подходе натуральные числа 0,1,2,... могут рассматриваться как свойства свойств и определяться средствами второпорядковой логики предикатов следующим образом: 0(Р) ее u-BxPlx), ЦР) = n-BxPfx), 2(F) ^ ^xByi-TX = = УЛ Р(х) А Р(у) A \/z(P(z) ^>(Z = XVZ = y)))uT. Д. Среди неклассических систем логики предикатов следует особо выделить т. н. свободную логику — нестандартную теорию квалификации, при построении которой отказываются от обязательного существования индивидов в области интерпретации, а также допускают пустоту термов. Часто неклассические исчисления предикатов строятся так, что их отличие от классического проявляется — в самой системе аксиом и правил вывода — лишь на пропозициональном уровне: вместо схем аксиом классического исчисления высказываний выбираются схемы аксиом соответствующего неклассического пропозиционального исчисления (подобным образом обычно строятся кванторные системы интуиционистской логики и минимальной, многие системы модальной логики и релевантной логики). В этом отношении специфичным является конструктивное исчисление предикатов, в котором (наряду с модификацией пропозициональной части) принимаются особые, характерные именно для кванторной теории постулаты, формализующие т. н. принцип Маркова (простейшая формулировка данного принципа такова: Vjc(P(jc) v -,P(jc)) 3 (-r^JcP(jc) => BjcP(jc)). Весьма нетривиальной и интересной с философской точки зрения оказалась проблема построения кванторных расширений модальных логик, известная также как проблема кванти- фикации в модальных контекстах. При попытке построения модальной логики предикатов возникает ряд существенных трудностей содержательного характера, на которые обратил внимание У. Куайн. Помимо известных проблем, связанных с нарушением принципа взаимозаменимости в неэкстенсиональных контекстах (а модальные контексты — один из их типов), обнаружилось, что к неожиданным результатам в модальной логике приводит применение правила введения квантора существования (знаменитый куайновский парадокс Вечерней и Утренней звезды); во многих кванторных модальных системах ряд теорем не согласуются с интуицией (к ним относятся, напр., формула Баркан 03хР(х)зЕЬс0Р(х), позволяющая заключать от возможности существования к актуальному существованию некоторого объекта, теорема VjcVj<x = у Z) их = у), означающая необходимость любого утверждения о равенстве). Но главной причиной философской ущербности модальной логики предикатов, по мнению У. Ку- айна, является реанимация в ее рамках схоластического понятия модальностей de ге (модальностей, квалифицирующих характер связи признака с предметом) и причастность этой теории эссенциализму (метафизической концепции, согласно которой предметы сами по себе — независимо от того, как они представлены в языке, — обладают некоторыми свойствами необходимо, а некоторыми случайно).
427
ЛОГИКА ПРЕДИКАТОВ В современной модальной логике, особенно в результате разработки ее точных формальных семантик, удалось снять многие возражения У Куайна. Так, А. Смульяном была установлена необходимость учета областей действий дескрипций при замене равного равным в модальных контекстах. С. Крипке предложил способ построения богатых систем модальной логики предикатов без формулы Баркан и других парадоксальных законов. Т. Парсонс точными методами продемонстрировал непричастность данных теорий эссен- циализму показал, что можно развивать модальную логику в антиэссенииалистском ключе—с отрицанием эссенциалист- ского принципа в качестве аксиомы. Тем не менее проблема адекватной экспликации кванторных модальных контекстов языка, особенно эпистемических контекстов (утверждений о знании, мнении, вере), и по сей день остается актуальной. Особую важность для логики предикатов, как и для любой логической теории, представляет иссследование ее метатеоре- тических свойств (см. Метшмогшкш). В связи с наличием двух способов построения логических теорий — семантического и синтаксического (в виде исчислений) — возникает вопрос о соотношении класса общезначимых в семантике формул и множества теорем исчисления. Классическое исчисление предикатов первого порядка семантически непротиворечиво (корректно), т. е. каждая его теорема универсально общезначима. Наличие данного свойства обосновывается стандартным методом: демонстрируется общезначимость всех аксиом исчисления и инвариантность его правил вывода относительно свойства «быть общезначимой формулой». Более трудным оказалось доказательство семантической полноты первопорядкового исчисления предикатов, т. е. того, что всякая универсально общезначимая формула является теоремой исчисления. Впервые этот результат был получен К. Геделем (1930). Позднее Л. Генкин предложил изящный (хотя и неконструктивный) метод доказательства полноты, существенно опирающийся на лемму Линденбаума (о возможности расширения любого непротиворечивого множества формул логики предикатов до непротиворечивого насыщенного множества). Еще более простой метод, использующий технику т. н. модельных множеств, был разработан Я. Хинтиккой. Наличие свойств семантической непротиворечивости и полноты у первопорядкового исчисления предикатов свидетельствует о том, что оно представляет собой адекватную формализацию семантически построенной логики предикатов, т. е. что у важнейших понятий — общезначимой формулы (закона логики) и логического следования (имеющего место между посылками и заключением в корректном рассуждении) — имеются точные синтаксические аналоги. Данное свойство, как уже было сказано ранее, отсутствует у логики предикатов второго порядка. Исчисление предикатов (как первопорядковое, так и вто- ропорядковое) обладает также свойством синтаксической непротиворечивости, т. е. не существует формулы А, такой, что |—-А и 1-г-А. Однако, в отличие от классического исчисления высказываний, исчисление предикатов не является синтаксически полным (максимальным, непополнимым), т. е. к нему можно присоединить в качестве новой аксиомы некоторую недоказуемую формулу так, что полученная система окажется синтаксически непротиворечивой. Синтаксическая неполнота исчисления предикатов имеет серьезное в методологическом отношении следствие: обеспечивается возможность построения на базе данной логической системы нетривиальных прикладных теорий за счет присоединения их собственных постулатов, не обладающих статусом логических законов. Особую важность применительно к логике предикатов имеет исследование проблемы разрешения. А. Чёрчем был получен фундаментальный результат, свидетельствующий о том, что в общем случае эта проблема не имеет решения: не существует алгоритма, позволяющего для произвольной формулы языка логики предикатов решить вопрос о том, является ли она законом данной теории, т. е. любое адекватное понятие закона логики предикатов существенным образом неэффективно, не содержит алгоритмической процедуры распознавания элементов своего объема. Тем не менее в некоторых частных случаях проблема разрешения находит свое решение. Установлено, напр., что логика предикатов разрешима относительно свойства «быть общезначимой формулой на множестве с конечным числом элементов». Алгоритм проверки формул логики предикатов на общезначимость в области, содержащей п объектов, состоит в элиминации кванторов и преобразовании данной формулы в формулу языка логики высказываний (для последнего проблема разрешения решена). При устранении кванторов общности и существования используется их связь с пропозициональными связками конъюнкции и дизъюнкции, соответственно: если а,, а^..., ап — имена всех объектов данной конечной области, то утверждение УхА(х) эквивалентно утверждению А(а,) л A(Oj) л ... л А(ап),а 3 vA(x) эквивалентно А(а,) V A(Oj) V... V А(ав). Разрешимой является т. н. логика одноместных предикатов — фрагмент логики предикатов, формулы которого не содержат предикаггорных констант местности большей 1. Можно показать, что любая подобная формула с к предикаторными константами универсально общезначима тогда и только тогда, когда она общезначима во всех конечных областях не более чем с 2* элементами (а этот вопрос, как уже было сказано, может быть решен эффективным образом). Разрешающая процедура имеется также для некоторых типов формул, приведенных к предваренной нормальной форме. Напр., вопрос об универсальной общезначимости формул с кванторной приставкой 3 а, 3 о^... 3 ап может быть сведен к вопросу о ее общезначимости на одноэлементном множестве, подобный вопрос о формулах с приставками Vo^Vo^... VanH VOjVOj... Van3?,3f^,... 3?n сводится к вопросу об общезначимости на множестве из п элементов. Создание логики предикатов связано с именами Г, Фреге, Б. Ршсселт и А УЫмхедш, Современные формулировки клас- сическогопервопорядковогоисчисленияпредикатовиегоде- тальный анализ был осуществлен Д Гтмбертом и его учениками В. Аккерманом и П. Бернайсом. Большую роль в оформлении точной теоретико-множественной семантики лотки предикатовсыграли работы А Терского. Значительный вклад в установление метатеоретическихсвойствлогики предикатов внесли Л. Лёвингейм, Т. Сколем, К. Гсдель, А Чёр% Ж. Эрб- ран, Л. Генкин. Серьезные научные результаты в данной области были получены также П Геяцешом, Л. Кальмаром, С Кмиаац В. Крейгом, У. Дротом, А А Мшрковъш, А. И. Мальцевым, Я. С Новшковылц К А Смяршшыщ К. Шютге и многими другими исследователями. Лп: Гильберт Д., Аккерман В. Основы теоретической логики. М., 1947; Предикатов исчисление (Ееенин-Вояышн А. С.).— В кн.: Философская энциклопедия, т. 4. М., 1967; Киши С. К. Введение в метаматематику М, 1957; Мендельсон Э. Введение в математическую логику М, 1976; Новиков П. С. Элементы математической логики. М.
