Cтраница 1
Формулы узкого исчисления предикатов приобретают содержательное истолкование при рассмотрении их связей с моделями. Такие связи устанавливаются по хорошо известным правилам математической логики. [1]
Класс К2 называется конечно аксиоматизируемым обогащенным подклассом класса К, если существует формула узкого исчисления предикатов 91 сигнатуры К2 такая, что К % состоит из тех и только тех обогащений - моделей, на которых 31 истинна. [2]
Так как модель SR0 совершенная, то отношение 93 представимо на 3R формулой узкого исчисления предикатов. [3]
Значительная часть алгебраических локальных теорем может быть выведена из следующей основной локальной теоремы: для совместимости бесконечной системы формул узкого исчисления предикатов, допускающего отношение тождества и произвольное множество символов для индивидуальных объектов и предикатов, необходимо и достаточно, чтобы была совместна каждая подсистема данной системы. [4]
Рекурсивно нумерованная рекурсивно устойчивая модель или алгебра называется рекурсивно совершенной, если она - бесконечно и каждый рекурсивный предикат, определенный на этой модели, представим формулой узкого исчисления предикатов. Теорема Геделя [1] показывает, что арифметика S является рекурсивно совершенной алгеброй. [5]
Что же касается интересующих нас сейчас вопросов методологии и теории познания, то в применении к ним уж заведомо имеет смысл заранее ограничиться лишь рассмотрением языков типа естественных, объем класса слов и выражений в которых не превосходит мощность класса формул узкого исчисления предикатов. В буквальном смысле слова такие языки вообще состоят из конечного множества слов; если же допускать в принципе употребление слов и фраз любой длины, то их множество следовало бы охарактеризовать как потенциально счетное. [6]
Именно, о формулах, которые ( в нормальной форме) имеют приставку, состоящую из одних только знаков общности, или из одних только знаков существования, или у которых все знаки общности предшествуют знакам существования. Во всех этих случаях вопрос о всегда-истинности формулы узкого исчисления предикатов сводится к вопросу о всегда-истинности ее в области, содержащей определенное конечное число индивидуумов, а в такой области он решается полностью средствами исчисления предложений. [7]
Он доказал, что решение этой проблемы в общем случае сводится к ее решению для случая, когда логич. Вместе с тем он установил, что если формула узкого исчисления предикатов содержит лишь одноместные предикатные переменные и число их равно нек-рому натуральному и, то из общезначимости формулы в любой области, состоящей не более чем из 2 предметов, следует ее общезначимость во всякой области. Из этого утверждения следует разрешимость проблемы разрешения для узкого исчисления одноместных предикатов. [8]
Известны также описания колец, проективные или плоские модули над которыми определяются формулами узкого исчисления предикатов. [9]
В работе [5] было введено понятие аксиоматизируемого соответствия между моделями фиксированных классов. Параграф 1 настоящей статьи посвящен рассмотрению тех модельных соответствий, которые могут быть заданы формулами узкого исчисления предикатов ( формулами УИП), н содержащими дополнительных предикатных символов. Рассмотрение это основывается на одной элементарной лемме о приведении формул УИП с разделяющимися переменными. В качестве иллюстрации выводятся результаты С. [10]
В случае неконструктивного внешнего мира, когда внешние воздействия на рассматриваемый нами процесс не могут быть сведены к алгоритму, положение принципиально изменяется. В самом деле, предположим, что процесс, о котором идет речь, может накапливать информацию, поступающую извне, и осуществлять сравнение с нею задаваемых ему формул узкого исчисления предикатов. Если первая последовательность содержит все истинные, а вторая - все неистинные формулы исчисления предикатов что в случае неконструктивной среды не является невозможным), то нетрудно построить вполне конструктивную процедуру разрешения для ( узкого) исчисления предикатов, основанную на накоплении все большего и большего количества внешней информации сравнении с нею формул, подлежащих разрешению. [11]
Переходя к общему случаю, мы ради краткости далее будем предполагать, что рассматриваемые модели имеют два основных множества. Из них одно будем называть первым, а другое - вторым множеством. Формулы соответствующего двухсортного исчисления предикатов имеют тот же вид, что и формулы обычного односортного узкого исчисления предикатов. Различие состоит в том, что в двухсортном исчислении предметные переменные разделяются на два сорта: значениями переменных 1-го сорта служат элементы 1-го основного множества, а значениями переменных 2-го сорта служат элементы 2-го основного множества. Основные предикаты двухсорт-ных моделей определены на паре множеств и в соответствии с сортностью своих аргументов могут быть разных типов. Предикаты и предикатные переменные, все пустые места которых предназначены предметным переменным 1-го сорта, условимся называть - предикатами 1-го типа. Предикаты, все пустые места которых предназначены для предметных переменных 2-го сорта, будем называть предикатами второго типа. [12]
Индексы г, / предполагаются пробегающими или весь натуральный ряд, или его конечный начальный отрезок. Говорят, что класс К или что элементарная теория Т ( К) класса К рекурсивно разрешима, если совокупность номеров S всех истинных на К формул узкого исчисления предикатов является рекурсивным множеством натуральных чисел. В противном случае элементарная теория Т ( К) называется рекурсивно неразрешимой. [13]
Само собой разумеется, что неконструктивная среда вовсе не обязана полностью брать на себя задачу разрешения, как это фактически имело место в приведенном примере. Выдаваемые ею неконструктивные последовательности могут и не быть непосредственно последовательностями формул. Они должны обладать лишь одной особенностью - возможностью их конструктивного преобразования ( в рамках рассматриваемой самоорганизующейся процедуры разрешения) в соответствующим образом упорядоченные последовательности доказуемых ( истинных) и недоказуемых неистинных) формул узкого исчисления предикатов. [14]
Пусть К - некоторый класс моделей сигнатуры ст. Формулы узкого-исчисления предикатов, внелогические константы которых содержатся в а, будут называться - формулами. ST, если 9Г ложна на некоторой конечной модели из К. Если 91 истинна на всех конечных / - моделях, то говорят, что 91конечно истинна на К. Через Т ( К), F ( К) обозначим соответственно совокупность всех тождественно истинных формул и совокупность конечно опровержимых на К К-формул. С помощью результатов этой же заметки ниже доказываются более сильные предложения о том, что совокупности Т ( К) и F ( K) эффективно неотделимы, если К - один из указанных выше классов групп или колец. Отсюда, в частности, непосредственно следует теорема Б. А. Трахтенброта [2] о рекурсивной неотделимости тождественно истинных и конечно опровержимых формул узкого исчисления предикатов. [15]