ЯЗЫКИ ЛОГИКО-МАТЕМАТИЧЕСКИЕ

— символические языки для формализованного изложения логических и математических теорий. Я. л.-м. задают перечнем формальных символов (он играет роль, сходную с ролыо алфавита естественного языка) и определением правильно построенных выражений различных типов (аналогов осмысленных слов и предложений естественного языка), а также снабжают семантикой — истолкованием смысла формальных символов и выражений. Правильно построенные выражения, значениями которых являются объекты, наз. термами, а выражения, значениями которых являются суждения, наз. формулами. Перечень формальных символов является бесконечным: он может содержать логические символы, символы предикатов и функций (в число последних могут входить индивидуальные стволы — символы -местных ф-ций), вспомогательные знаки (скобки, запятые и т. д.) и обычно содержит бесконечно много переменных. Все эти символы задают как слова в некотором конечном алфавите. Семантика указывает допустимые значения переменных, истолкование символов предикатов, ф-ций и логических символов. Рассмотрим, напр., язык арифметики формальной. Переменные: и т. д. Логические символы: (читается : влечет), всех), Э (существует). Символы предикатов: = (равняется). Символы ф-ций: за), О

(нуль). Термы: 0 есть терм; каждая переменная есть терм; если термы, то и термы. Формулы: если термы, то формула; если А и В — формулы, переменная, то — формулы.

Я. л.-м. делятся на логические и собственно логико-математические (прикладные). Делятся они еще и на языки первого и более высоких порядков; языки первого порядка — на кванторные и бескванторные.

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

Предикатные Я. л.-м. получаются из соответствующих пропозициональных языков путем добавления предметных переменных, предикатных символов с различным числом свободных мест (пропозициональные переменные рассматриваются как -местные предикатные символы) и кванторов V, 3 (или одного из них; в этом случае второй обычно вводится в качестве сокращения; напр., означает . Иногда добавляют также функциональные символы. Атомарные ф-лы такого языка имеют вид где -местный предикатный символ, термы. Остальные ф-лы строятся из атомарных с помощью логических связок. Для предикатных языков с несколькими сортами переменных для каждого из функциональных и предикатных символов указывается, к какому сорту принадлежит каждый аргумент и (для функциональных символов) к какому сорту принадлежит результат (т. е. терм, начинающийся с рассматриваемого символа). Часто выделяют язык исчисления предикатов с равенством — результат добавления двухместного предикатного символа атомарная ф-ла, в отличие от общего случая, имеет вид к соответствующему предикатному языку. В логич. языках 1-го порядка допускаются кванторы лишь по предметным переменным; в языках более высоких порядков имеются кванторы по предикатам (кванторы 2-го порядка), предикатам от предикатов (3 порядок) и т. д. Язык теории типов содержит кванторы всех конечных порядков.

Иногда предикатные языки включают в себя правила построения термов с помощью -символа читается: какой-нибудь х, для которого верно или, для языков с равенством, с помощью читается: тот единственный х, для которого Собственно логико-математические (прикладные) языки характеризуются тем, что пропозициональные и предикатные переменные в них отсутствуют вовсе или играют второстепенную роль. Среди этих языков простейшими по логической структуре являются бескванторные языки. Из бескванторных языков наиболее употребительны языки для описания различных классов вычислимых ф-ций. Напр., язык ПРФ (примитивно-рекурсивных ф-ций); предметные переменные функциональные переменные: натуральные числа: и т. д.; функциональные символы (функторы): (тождественный 0); функциональные переменные (все это — одноместные функторы): , где — натуральные числа, (-местная ф-ция, значение которой равно аргументу); если ф. - -местный функтор, функторы, то функтор (результат подстановки если функтор, функтор, то и функтор [примитивная рекурсия: ]

Термы: предметные переменные и выражения вида где термы, ф. - -местный функтор. Формулы: где — термы. Допустимые значения предметных переменных языка ПРФ — натуральные числа, допустимые значения функциональных переменных — примитивно-рекурсивные ф-ции (иногда — более широкие классы вычислимых ф-ций). Аналогично задают языки для описания других классов всюду определенных вычислимых ф-ций.

При описании частичных ф-ций, кроме предиката, равенства, появляются предикат t или (читается: определено); интерпретируется в этом случае так: и из следует, что значение равно значению s. Добавляются также средства для изображения ф-ции, универсальной для рассматриваемого класса: либо символ для этой ф-ции, либо правило: если t — терм, то функтор (номер его в некоторой заранее фиксированной нумерации рассматриваемого класса равен значению ).

Употребляются также языки для описания вычислимых функционалов различных типов: есть тип (объекты типа натуральные числа); если — типы, то есть тип (операций, перерабатывающих объекты тина и объекты типа ). Это — конечные типы; рассматриваются также трансфинитные типы.

Для каждого типа указывается правило построения последовательности переменных этого типа, а также константы этого типа, в число которых входит обычно символ операции, все значения которой равны 0, а также объект типа ; в число констант типа часто включают оператор примитивной рекурсии. Термы типа - это переменные и константы типа выражения вида где — терм типа терм типа (выражение ) интерпретируется как результат применения операции к аргументу s), а также (если в рассматриваемом языке имеется оператор абстракции К) выражение которое интерпретируется как обозначение ф-ции, перерабатывающей каждое где — типа типа

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

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

Лит.: Новиков П. С. Элементы математической логики. М., 1973; К лини С. К. Математическая логика. Пер. с англ. М., 1973 [библиогр. с. 451—465]; Чёрч А. Введение в математическую логику. Пер. с англ., т. 1. М., 1960; Карри X. Б. Основания математической логики. Пер. с англ. М., 1969 [библиогр. с. 518—5473. Г. Е. Минц.