Интерпретация — это присвоение значения символам формального языка . Многие формальные языки, используемые в математике , логике и теоретической информатике, определяются исключительно в синтаксических терминах и, как таковые, не имеют никакого значения, пока им не будет дана некоторая интерпретация. Общее изучение интерпретаций формальных языков называется формальной семантикой .
Наиболее часто изучаемыми формальными логиками являются пропозициональная логика , предикатная логика и их модальные аналоги, и для них существуют стандартные способы представления интерпретации. В этих контекстах интерпретация — это функция , которая обеспечивает расширение символов и строк символов объектного языка. Например, функция интерпретации может взять предикат T (для «высокий») и присвоить ему расширение { a } (для «Авраам Линкольн»). Все, что делает наша интерпретация, — это присваивает расширение {a} нелогической константе T и не делает утверждения о том, должно ли T обозначать высокий, а «a» — Авраам Линкольн. Логическая интерпретация также ничего не говорит о логических связках, таких как «и», «или» и «не». Хотя мы можем считать эти символы обозначающими определенные вещи или концепции, это не определяется функцией интерпретации.
Интерпретация часто (но не всегда) предоставляет способ определения истинностных значений предложений в языке. Если данная интерпретация присваивает значение True предложению или теории , то интерпретация называется моделью этого предложения или теории.
Формальный язык состоит из возможно бесконечного набора предложений (называемых по-разному словами или формулами ), построенных из фиксированного набора букв или символов . Инвентарь, из которого берутся эти буквы, называется алфавитом , по которому определяется язык. Чтобы отличить строки символов, которые есть в формальном языке, от произвольных строк символов, первые иногда называют хорошо сформированными формулами (wff). Существенной особенностью формального языка является то, что его синтаксис может быть определен без ссылки на интерпретацию. Например, мы можем определить, что ( P или Q ) является хорошо сформированной формулой, даже не зная, является ли она истинной или ложной.
Формальный язык можно определить с помощью алфавита и слова, находящегося в , если оно начинается с и состоит исключительно из символов и .
Возможная интерпретация могла бы присвоить десятичную цифру «1» и «0» — . Тогда будет обозначать 101 при этой интерпретации .
В конкретных случаях пропозициональной логики и логики предикатов рассматриваемые формальные языки имеют алфавиты, которые делятся на два набора: логические символы ( логические константы ) и нелогические символы. Идея этой терминологии заключается в том, что логические символы имеют одно и то же значение независимо от изучаемого предмета, в то время как нелогические символы меняют свое значение в зависимости от области исследования.
Логическим константам всегда придается одно и то же значение каждой интерпретацией стандартного вида, так что изменяются только значения нелогических символов. Логические константы включают квантификаторные символы ∀ («все») и ∃ («некоторые»), символы для логических связок ∧ («и»), ∨ («или»), ¬ («не»), скобки и другие группирующие символы, а также (во многих трактовках) символ равенства =.
Многие из обычно изучаемых интерпретаций связывают каждое предложение на формальном языке с одним значением истинности, либо True, либо False. Эти интерпретации называются функциями истинности ; [ dubious – discussion ] они включают обычные интерпретации пропозициональной и первопорядковой логики. Предложения, которые становятся истинными в результате определенного назначения, считаются удовлетворенными этим назначением.
В классической логике ни одно предложение не может быть сделано как истинным, так и ложным при одной и той же интерпретации, хотя это не относится к логикам перенасыщения, таким как LP. [1] Однако даже в классической логике возможно, что истинностное значение одного и того же предложения может быть разным при разных интерпретациях. Предложение является непротиворечивым , если оно истинно хотя бы при одной интерпретации; в противном случае оно является непротиворечивым . Предложение φ называется логически допустимым , если оно удовлетворяется каждой интерпретацией (если φ удовлетворяется каждой интерпретацией, которая удовлетворяет ψ, то φ называется логическим следствием ψ).
Некоторые логические символы языка (кроме квантификаторов) являются истинностно-функциональными связками , которые представляют функции истинности — функции, которые принимают истинностные значения в качестве аргументов и возвращают истинностные значения в качестве выходных данных (другими словами, это операции над истинностными значениями предложений).
Истинностно-функциональные связки позволяют составлять сложные предложения из более простых предложений. Таким образом, истинностное значение сложного предложения определяется как некая истинностная функция истинностных значений более простых предложений. Связки обычно считаются логическими константами , что означает, что значение связок всегда одинаково, независимо от того, какие интерпретации даются другим символам в формуле.
Вот как мы определяем логические связки в пропозициональной логике:
Итак, при заданной интерпретации всех букв предложений Φ и Ψ (т. е. после присвоения значения истинности каждой букве предложения) мы можем определить значения истинности всех формул, которые имеют их в качестве составляющих, как функцию логических связок. Следующая таблица показывает, как выглядит этот тип вещей. Первые два столбца показывают значения истинности букв предложений, как определенные четырьмя возможными интерпретациями. Другие столбцы показывают значения истинности формул, построенных из этих букв предложений, причем значения истинности определяются рекурсивно.
Теперь легче увидеть, что делает формулу логически действительной. Возьмем формулу F : (Φ ∨ ¬Φ). Если наша функция интерпретации делает Φ Истиной, то ¬Φ делается Ложью из-за связки отрицания. Поскольку дизъюнкт Φ из F является Истиной при этой интерпретации, F является Истиной. Теперь единственная другая возможная интерпретация Φ делает ее Ложью, и если это так, ¬Φ делается Истиной из-за функции отрицания. Это снова сделало бы F Истиной, поскольку один из дизъюнктов F , ¬Φ, был бы истинным при этой интерпретации. Поскольку эти две интерпретации для F являются единственно возможными логическими интерпретациями, и поскольку F оказывается Истиной для обеих, мы говорим, что она логически действительна или тавтологична.
Интерпретация теории — это отношение между теорией и некоторым предметом, когда существует соответствие «многие к одному» между определенными элементарными утверждениями теории и определенными утверждениями, связанными с предметом. Если каждое элементарное утверждение в теории имеет корреспондента, это называется полной интерпретацией , в противном случае это называется частичной интерпретацией . [2]
Формальный язык пропозициональной логики состоит из формул, построенных из пропозициональных символов (также называемых пропозициональными символами, пропозициональными переменными, пропозициональными переменными ) и логических связок. Единственными нелогическими символами в формальном языке пропозициональной логики являются пропозициональные символы, которые часто обозначаются заглавными буквами. Чтобы сделать формальный язык точным, необходимо зафиксировать определенный набор пропозициональных символов.
Стандартный вид интерпретации в этой настройке — это функция, которая сопоставляет каждый пропозициональный символ с одним из значений истинности true и false. Эта функция известна как функция назначения истинности или оценочная функция. Во многих презентациях буквально назначается значение истинности, но некоторые презентации назначают носителей истины .
Для языка с n различными пропозициональными переменными существует 2 n различных возможных интерпретаций. Например, для любой конкретной переменной a существует 2 1 =2 возможных интерпретаций: 1) a присваивается T , или 2) a присваивается F . Для пары a , b существует 2 2 =4 возможных интерпретаций: 1) обоим присваивается T , 2) обоим присваивается F , 3) a присваивается T , а b присваивается F , или 4) a присваивается F , а b присваивается T .
При любом назначении истинности для набора пропозициональных символов существует уникальное расширение интерпретации для всех пропозициональных формул, построенных из этих переменных. Эта расширенная интерпретация определяется индуктивно, используя определения таблицы истинности логических связок, обсуждавшихся выше.
В отличие от пропозициональной логики, где каждый язык одинаков, за исключением выбора другого набора пропозициональных переменных, существует много различных языков первого порядка. Каждый язык первого порядка определяется сигнатурой . Сигнатура состоит из набора нелогических символов и идентификации каждого из этих символов как константного символа, функционального символа или предикатного символа . В случае функциональных и предикатных символов также назначается арность натурального числа . Алфавит для формального языка состоит из логических констант, символа отношения равенства =, всех символов из сигнатуры и дополнительного бесконечного набора символов, известных как переменные.
Например, в языке колец есть константные символы 0 и 1, два двоичных символа функций + и · и нет двоичных символов отношения. (Здесь отношение равенства принимается за логическую константу.)
Опять же, мы могли бы определить язык первого порядка L как состоящий из отдельных символов a, b и c; предикатных символов F, G, H, I и J; переменных x, y, z; никаких функциональных букв; никаких сентенциальных символов.
При наличии сигнатуры σ соответствующий формальный язык известен как набор σ-формул. Каждая σ-формула строится из атомарных формул с помощью логических связок; атомарные формулы строятся из терминов с использованием предикатных символов. Формальное определение набора σ-формул идет в другом направлении: сначала термины собираются из константных и функциональных символов вместе с переменными. Затем термины могут быть объединены в атомарную формулу с использованием предикатного символа (символа отношения) из сигнатуры или специального предикатного символа "=" для равенства (см. раздел "Интерпретация равенства" ниже). Наконец, формулы языка собираются из атомарных формул с использованием логических связок и квантификаторов.
Чтобы приписать значение всем предложениям языка первого порядка, необходима следующая информация.
Объект, несущий эту информацию, называется структурой ( сигнатуры σ), или σ-структурой, или L -структурой (языка L), или «моделью».
Информация, указанная в интерпретации, предоставляет достаточно информации, чтобы дать значение истинности любой атомарной формуле после того, как каждая из ее свободных переменных , если таковые имеются, была заменена элементом домена. Значение истинности произвольного предложения затем определяется индуктивно с использованием T-схемы , которая является определением семантики первого порядка, разработанной Альфредом Тарским. T-схема интерпретирует логические связки с использованием таблиц истинности, как обсуждалось выше. Таким образом, например, φ ∧ ψ выполняется тогда и только тогда, когда выполняются как φ, так и ψ.
Это оставляет вопрос о том, как интерпретировать формулы вида ∀ x φ( x ) и ∃ x φ( x ) . Область дискурса образует диапазон для этих квантификаторов. Идея состоит в том, что предложение ∀ x φ( x ) истинно при интерпретации именно тогда, когда каждый подстановочный случай φ( x ), где x заменяется некоторым элементом области, выполняется. Формула ∃ x φ( x ) выполняется, если существует хотя бы один элемент d области такой, что φ( d ) выполняется.
Строго говоря, пример подстановки, такой как формула φ( d ), упомянутая выше, не является формулой в исходном формальном языке φ, поскольку d является элементом домена. Есть два способа решения этой технической проблемы. Первый — перейти к более крупному языку, в котором каждый элемент домена именуется постоянным символом. Второй — добавить к интерпретации функцию, которая присваивает каждую переменную элементу домена. Тогда T-схема может количественно оценить вариации исходной интерпретации, в которой эта функция присваивания переменной изменяется, вместо количественной оценки примеров подстановки.
Некоторые авторы также допускают пропозициональные переменные в логике первого порядка, которые затем также должны быть интерпретированы. Пропозициональная переменная может стоять сама по себе как атомарная формула. Интерпретация пропозициональной переменной — это одно из двух значений истинности: истинное и ложное. [4]
Поскольку интерпретации первого порядка, описанные здесь, определены в теории множеств , они не связывают каждый предикатный символ со свойством [5] (или отношением), а скорее с расширением этого свойства (или отношения). Другими словами, эти интерпретации первого порядка являются экстенсиональными [6], а не интенсиональными .
Пример интерпретации языка L, описанного выше, выглядит следующим образом.
В интерпретации Л:
Как указано выше, интерпретация первого порядка обычно требуется для указания непустого множества в качестве области дискурса. Причина этого требования заключается в том, чтобы гарантировать, что эквивалентности, такие как где x не является свободной переменной φ, являются логически допустимыми. Эта эквивалентность сохраняется в каждой интерпретации с непустой областью, но не всегда сохраняется, когда разрешены пустые области. Например, эквивалентность не выполняется в любой структуре с пустой областью. Таким образом, теория доказательств логики первого порядка становится более сложной, когда разрешены пустые структуры. Однако выигрыш от их разрешения незначителен, поскольку как предполагаемые интерпретации, так и интересные интерпретации теорий, которые изучают люди, имеют непустые области. [7] [8]
Пустые отношения не вызывают никаких проблем для интерпретаций первого порядка, поскольку нет похожего понятия передачи символа отношения через логическую связку, расширяющую его область действия в этом процессе. Таким образом, приемлемо, чтобы символы отношения интерпретировались как тождественно ложные. Однако интерпретация символа функции всегда должна назначать символу четко определенную и полную функцию.
Отношение равенства часто рассматривается специально в логике первого порядка и других предикатных логиках. Существует два общих подхода.
Первый подход заключается в том, чтобы рассматривать равенство как не отличающееся от любого другого бинарного отношения. В этом случае, если в сигнатуру включен символ равенства, обычно необходимо добавлять различные аксиомы о равенстве в системы аксиом (например, аксиому подстановки, гласящую, что если a = b и R ( a ) выполняется, то R ( b ) также выполняется). Этот подход к равенству наиболее полезен при изучении сигнатур, которые не включают отношение равенства, таких как сигнатура для теории множеств или сигнатура для арифметики второго порядка , в которой есть только отношение равенства для чисел, но нет отношения равенства для множества чисел.
Второй подход заключается в том, чтобы рассматривать символ отношения равенства как логическую константу, которая должна интерпретироваться реальным отношением равенства в любой интерпретации. Интерпретация, которая интерпретирует равенство таким образом, известна как нормальная модель , поэтому этот второй подход аналогичен изучению только тех интерпретаций, которые случайно оказываются нормальными моделями. Преимущество этого подхода в том, что аксиомы, связанные с равенством, автоматически удовлетворяются каждой нормальной моделью, и поэтому их не нужно явно включать в теории первого порядка, когда равенство трактуется таким образом. Этот второй подход иногда называют логикой первого порядка с равенством , но многие авторы принимают его для общего изучения логики первого порядка без комментариев.
Есть еще несколько причин ограничить изучение логики первого порядка нормальными моделями. Во-первых, известно, что любая интерпретация первого порядка, в которой равенство интерпретируется отношением эквивалентности и удовлетворяет аксиомам подстановки для равенства, может быть сокращена до элементарно эквивалентной интерпретации на подмножестве исходной области. Таким образом, в изучении ненормальных моделей мало дополнительной общности. Во-вторых, если рассматриваются ненормальные модели, то каждая непротиворечивая теория имеет бесконечную модель; это влияет на формулировки результатов, таких как теорема Лёвенгейма–Сколема , которые обычно формулируются в предположении, что рассматриваются только нормальные модели.
Обобщение логики первого порядка рассматривает языки с более чем одним видом переменных. Идея заключается в том, что различные виды переменных представляют различные типы объектов. Каждый вид переменной может быть квантифицирован; таким образом, интерпретация для языка со многими сортами имеет отдельную область для каждого из видов переменных, чтобы охватывать ее (существует бесконечный набор переменных каждого из различных видов). Символы функций и отношений, в дополнение к наличию арности, указываются таким образом, что каждый из их аргументов должен происходить из определенного вида.
Одним из примеров многосортной логики является плоская евклидова геометрия [ требуется пояснение ] . Существует два вида: точки и линии. Существует символ отношения равенства для точек, символ отношения равенства для линий и бинарное отношение инцидентности E , которое принимает одну точечную переменную и одну линейную переменную. Предполагаемая интерпретация этого языка имеет точечные переменные, изменяющиеся по всем точкам на евклидовой плоскости , линейную переменную, изменяющуюся по всем линиям на плоскости, и отношение инцидентности E ( p , l ) выполняется тогда и только тогда, когда точка p находится на линии l .
Формальный язык для логики предикатов высшего порядка выглядит почти так же, как формальный язык для логики первого порядка. Разница в том, что теперь существует много различных типов переменных. Некоторые переменные соответствуют элементам домена, как в логике первого порядка. Другие переменные соответствуют объектам более высокого типа: подмножествам домена, функциям из домена, функциям, которые берут подмножество домена и возвращают функцию из домена в подмножества домена и т. д. Все эти типы переменных могут быть квантифицированы.
Существует два вида интерпретаций, обычно используемых для логики высшего порядка. Полная семантика требует, чтобы после удовлетворения области дискурса переменные высшего порядка охватывали все возможные элементы правильного типа (все подмножества области, все функции из области в себя и т. д.). Таким образом, спецификация полной интерпретации совпадает со спецификацией интерпретации первого порядка. Семантика Хенкина , которая по сути является многосортной семантикой первого порядка, требует, чтобы интерпретация указывала отдельный домен для каждого типа переменной высшего порядка, по которому будет осуществляться диапазон. Таким образом, интерпретация в семантике Хенкина включает область D , набор подмножеств D , набор функций из D в D и т. д. Связь между этими двумя семантиками является важной темой в логике высшего порядка.
Описанные выше интерпретации пропозициональной логики и логики предикатов не являются единственными возможными интерпретациями. В частности, существуют другие типы интерпретаций, которые используются при изучении неклассической логики (например, интуиционистской логики ), а также при изучении модальной логики.
Интерпретации, используемые для изучения неклассической логики, включают топологические модели, булевозначные модели и модели Крипке . Модальная логика также изучается с использованием моделей Крипке.
Многие формальные языки связаны с определенной интерпретацией, которая используется для их мотивации. Например, сигнатура первого порядка для теории множеств включает только одно бинарное отношение ∈, которое предназначено для представления членства во множестве, а областью дискурса в теории первого порядка натуральных чисел должно быть множество натуральных чисел.
Предполагаемая интерпретация называется стандартной моделью (термин, введенный Абрахамом Робинсоном в 1960 году). [9] В контексте арифметики Пеано она состоит из натуральных чисел с их обычными арифметическими операциями. Все модели, которые изоморфны только что приведенной, также называются стандартными; все эти модели удовлетворяют аксиомам Пеано . Существуют также нестандартные модели (версии первого порядка) аксиом Пеано , которые содержат элементы, не коррелирующие ни с одним натуральным числом.
Хотя предполагаемая интерпретация может не иметь явного указания в строго формальных синтаксических правилах , она, естественно, влияет на выбор правил формирования и преобразования синтаксической системы. Например, примитивные знаки должны позволять выражение моделируемых понятий; сентенциальные формулы выбираются так, чтобы их аналоги в предполагаемой интерпретации были осмысленными повествовательными предложениями ; примитивные предложения должны выходить как истинные предложения в интерпретации; правила вывода должны быть такими, чтобы, если предложение непосредственно выводится из предложения , то оно оказывается истинным предложением со смысловым подтекстом , как обычно. Эти требования гарантируют, что все доказуемые предложения также оказываются истинными. [10]
Большинство формальных систем имеют гораздо больше моделей, чем предполагалось (существование нестандартных моделей является примером). Когда мы говорим о «моделях» в эмпирических науках , мы имеем в виду, если мы хотим, чтобы реальность была моделью нашей науки, говорить о предполагаемой модели . Модель в эмпирических науках — это предполагаемая фактически-истинная описательная интерпретация (или в других контекстах: непреднамеренная произвольная интерпретация, используемая для прояснения такой предполагаемой фактически-истинной описательной интерпретации.) Все модели — это интерпретации, которые имеют ту же область дискурса, что и предполагаемая, но другие назначения для нелогических констант . [11] [ нужна страница ]
Дана простая формальная система (назовем ее ), алфавит которой α состоит всего из трех символов и правило образования формул которой следующее:
Схема единственной аксиомы такова :
Формальное доказательство можно построить следующим образом:
В этом примере теорема, полученная как « » может быть интерпретирована как «Один плюс три равно четырем». Другой интерпретацией было бы прочтение ее в обратном порядке: «Четыре минус три равно одному». [12] [ нужна страница ]
Существуют и другие общепринятые применения термина «интерпретация», которые не относятся к присвоению значений формальным языкам.
В теории моделей говорят , что структура A интерпретирует структуру B, если существует определяемое подмножество D из A и определяемые отношения и функции на D , такие, что B изоморфна структуре с доменом D и этими функциями и отношениями. В некоторых случаях используется не домен D , а D по модулю отношения эквивалентности, определяемого в A. Для получения дополнительной информации см. Интерпретация (теория моделей) .
Говорят, что теория T интерпретирует другую теорию S , если существует конечное расширение посредством определений T ′ теории T такое, что S содержится в T ′.
![{\displaystyle [\forall y(y=y)\lor \exists x(x=x)]\equiv \exists x[\forall y(y=y)\lor x=x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1103d5e6440cb56fa1c1cfeb394b2f4306fc9ae3)
