Сводка теории

Формулы логики предикатов и их преобразование

Функция n переменных ( n = 1,2,...) с непустой областью определения, множество значений которой содержится во множестве { 1, 0 }, называется n-местным предикатом.

Если область определения n -местного предиката имеет вид , т.е. все независимые переменные пробегают одно и то же множество, то говорят, что предикат определен на множестве М.

n -местный предикат может, в частности, принимать для всех наборов значений независимых переменных одно и то же значение, т.е. быть тождественно-истинным или тождественно-ложным.

Если в многоместном предикате фиксировать значения некоторых, но не всех независимых переменных, получается новый предикат с меньшим числом мест.

Если F – свойство элементов множества M и F(x) – соответствующий этому свойству предикат (определенный на M), то предложение: «все элементы множества M обладают свойством F» или «каждый (или любой, или всякий) элемент множества M обладает свойством F»- записывается в виде: ; а предложение: «во множестве M существует (или есть, или имеется, или найдется) элемент, обладающий свойством F» – в виде .

Читаются эти выражения так: «Для всякого (или для всех) »; «Существует x такое, что F(x)».

Выражения и называются квантором общности (или всеобщности) и квантором существования соответственно. При этом обычно говорят: «квантор по переменной x».

Можно рассматривать постановку квантора общности и квантора существования перед знаками предикатов («навешивание» кванторов или «квантификация») как особые операции.

Навешивание квантора общности есть операция, сопоставляющая одноместному предикату F(x) высказывание – истинное, если F(x) тождественно-истинен, и ложное в противном случае. Навешивание квантора существования есть операция, сопоставляющая одноместному предикату F(x) высказывание – ложное, если F(x) тождественно ложен, и истинное в противном случае.

Операции навешивания кванторов общности и существования сопоставляют каждому n -местному предикату (n-1) -местные предикаты исоответственно. В последних двух предикатах переменная называется связанной, остальные переменные – свободными (или параметрами).

Логико-математический язык первого порядка (первой ступени) L задается набором из четырех множеств:

a) (индивидные) переменные x, y, z,...;

b) n -местные (индивидные) функциональные символы F, G, H,... для каждого n;

c) n -местные (индивидные) предикатные символы P, B, S,... для каждого n;

d) логические связки и кванторы.

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

Если задан язык L, то можно определить некоторые правильно построенные тексты, составленные из символов L и вспомогательных символов – скобок и запятых. Эти тексты называются выражениями языка L и подразделяются на термы и формулы.

Дата добавления: 2014-01-06