Математическая энциклопедия - логические исчисления

формализации содержательных логич. теорий; выводимые объекты Л. п. интерпретируются как суждения, составленные из простейших (имеющих, вообще говоря, субъектно-предикатную структуру) при помощи пропозициональных связок и кванторов. Чаще всего используются связки "не", "и", "или", "если..., то..." и кванторы существованиях и всеобщности. От произвольных исчислений

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

Одно из важнейших Л. и. классическое исчисление предикатов с функциональными знаками. Язык этого исчисления, помимо круглых скобок и логич. символов

содержит три потенциально бесконечных списка: список предметных переменных, предикатных переменных и функциональных переменных (каждая из предикатных и функциональных переменных снабжена информацией о своей размерности, причем для предикатных переменных наименьшая размерность 1, а для функциональных 0). Понятие терма: 1) всякая предметная переменная и всякая функциональная переменная размерности 0 есть терм; 2) если Т 1, ..., Tl термы, а f функциональная переменная размерности l, то f( Т 1, ..., Tl).тоже терм. Если Т 1, ..., Т k термы, а Р - предикатная переменная размерности k, то Р( Т 1, ..., Tk).наз. атомарной ф о р м у л о й. Понятие формулы: 1) всякая атомарная формула есть формула; 2) если Fи G формулы, а х - предметная переменная, то выражения

суть тоже формулы. Говорят, что в последних двух формулах все вхождения переменной хсвязанные; вхождения переменных, к-рые в процессе построения формулы не связываются кванторами, наз. свободными вхождениями. Терм Тназ. свободным для хв F, если для любого свободного вхождения хв Fневерно, что оно является вхождением в подформулу вида или где у - какая-либо из переменных, участвующих в построении означает результат подстановки Т в F вместо всех свободных вхождений x.

Пусть х - произвольная предметная переменная, А, В, С и D - произвольные формулы, причем Dне содержит хсвободно, Т - произвольный терм, свободный для хв А. Аксиомами рассматриваемого исчисления являются любые формулы следующих 10 видов (каждый из к-рых наз. схемой аксиом):

Кроме того, это исчисление имеет три правила вывода: "из Аи можно получить В","из можно получить можно получить ". Доказуемыми формулами (или теоремам и) рассматриваемого исчисления наз. любые формулы, к-рые могут быть получены из аксиом

исчисления в результате применения (возможно, многократного) указанных правил (см. Вывод логический). Основная интерпретация исчисления предикатов. Область значения предметных переменных непустое множество предметов М, функциональных переменных функции из Мв M, предикатных переменных функции из Мв {0, 1 } (одно из значений интерпретируется как "истина", второе как "ложь"); имеются в виду функции, определенные на любом наборе предметов, количество членов к-рого соответствует размерности неременной. Теперь для любой атомарной формулы, зафиксировав значение ее предикатной переменной и значения входящих в нее предметных и функциональных переменных, можно говорить об истинности или ложности этой формулы. Аналогично, используя таблицы истинности для пропозициональных связок и обычную интерпретацию кванторов (как бесконечных конъюнкций и дизъюнкций), можно судить об истинности произвольной формулы рассматриваемого языка при выбранном Ми выбранных значениях входящих в нее предикатных, функциональных и свободных предметных переменных. Формула наз. общезначимой, если при любом таком выборе она оказывается истинной. Так, каковы бы ни были значения двуместной предикатной переменной Ри одноместной функциональной переменной f, из того, что для нек-рого хформула P(f(x), f(y)) истинна при любом y, следует, что найдется z, для к-poro P(z,f(z)).истинна. Следовательно, формула

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

Многочисленные Л. и. получаются видоизменением построенного выше Л. и. Так, добавление в язык символа вместе со схемами аксиом