Языки. Интерпретации.
В
языке над &,
где знак
интерпретируется как сложение по модулю два, устанавливаются следующие
соотношения:
Эти равенства
позволяют переводить формулы в языке над
в равные
им формулы в языке над
. и обратно. Тождественные
преобразования в последнем языке осуществляются при помощи равенств,
установленных для конъюнкции
таетcя, что
конъюнкция связывает "сильнее", чем знак +. Этих равенств достаточно для
того, чтобы из них при помощи тождественных преобразований, так же как
и при рассмотрении языка над
можно было вывести люОое верное равенство в языке над
Выражение в этом языке наз. приведённым полиномом (п.п.), если оно либо
имеет вид
где каждое
есть или
или переменное, или конъюнкция
различных переменных без отрицаний,
при
и
либо равно
. Напр.,
выражение
является п. п. Всякую формулу
А. л. можно привести к п. п.
Кроме рассмотренных
языков, существуют и др. языки, равносильные им (два языка наз. равносильными,
если при помощи нек-рых правил преобразования каждая формула одного из
этих языков переводится в нек-рую равную ей формулу в другом языке и обратно).
В основу такого языка достаточно положить любую систему операций (и констант),
обладающую тем свойством, что через операции (и константы) этой системы
можно представить всякую функцию А, л. Такие системы наз. функционально
полными-. Примерами полных систем являются
и т. п.Существует алгоритм, к-рый по произвольной конечной системе функций
А. л. устанавливает её полноту или неполноту. Рассматриваются и такие языки,
в основе к-рых лежат системы операций, не являющихся функционально полными,
и таких языков бесконечно много. Среди них имеется бесконечно много попарно
неравносильных языков (в смысле отсутствия переводимости при помощи тождественных
преобразований с одного языка на другой). Однако для всякого языка, построенного
на основе тех или иных операций А. л., существует такая конечная система
равенств этого языка, что всякое равенство этого языка выводимо при помощи
тождественных преобразований из равенств этой системы. Такая система равенств
наз. дедуктивно полной системой равенств (п. с. р.) языка.
Рассматривая
тот или иной из упомянутых выше языков вместе с нек-рой п. с. р. этого
языка, иногда отвлекаются от табличного задания операций, лежащих в основе
этого языка, и от того, что значениями его переменных являются высказывания.
Вместо этого допускаются различные интерпретации языка, состоящие из той
или иной совокупности объектов (служащих значениями переменных) л системы
операций над объектами этого множества, удовлетворяющих равенствам из п.
с. р. этого языка. Так, язык над
в результате
такого шага превращается в язык т. н. булевой алгебры, язык над
превращается в язык т. н. булевого кольца (с единицей), язык над
в язык дистрибутивной структуры и т. п.
А. л. развивается
гл. обр. под влиянием задач, встающих в области её приложений. Из них самую
важную роль играют приложения А. л. в теории электрич. схем. Для описания
последних в нек-рых случаях приходится отказываться от пользования лишь
обычной двузначной А. л. и рассматривать те или иные её многозначные обобщения
(см. Многозначная логика).
Лит.: Гильберт
Д. и Аккер-м а н Б., Основы теоретической логики, пер. с нем., М., 1947;
Тарский А., Введение в логику и методологию дедуктивных наук, пер. с ан
гл., М., 1948; К л и-н и С. К., Введение в метаматематику, пер. с англ.,
М., 1957; Новиков П. С., Элементы математической логики, М., 1959. В. Б.
Кудрявцев.
А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я