59. Квантор всеобщности и квантор существования.

С помощью логических операций из данных предикатов можно строить более сложные предикаты. Наряду с теми логическими операциями, которые действуют и над высказываниями, для образования новых предикатов из уже имеющихся применяются кванторы.

Применение квантора всеобщности к предикату , где дает (n – 1)-местный предикат , который набору сопоставляет высказывание, истинное тогда и только тогда, когда для любого значения a переменной x_i истинно высказывание .

Квантор существования в применении к предикату при дает (n – 1)-местный предикат , который набору сопоставляет высказывание, истинное тогда и только тогда, когда хотя бы для одного значения a переменной x_i истинно высказывание .

60. Формула в исчислении предикатов. Предикатная переменная. Область действия квантора. Связанное и свободное вхождение переменной в формулу. Выполнимая формула. Тождественно истинная формула и тождественно ложная формула. Общезначимая формула, противоречивая формула.

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

Предикатная переменная — переменная, возможными значениями которой являются предикаты.

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

Поскольку в математической логике интересуются лишь структурой суждений, отвлекаясь от их конкретного смысла, а также во избежание двусмысленностей, свойственных естественным языкам, для построения логики предикатов используется формализованный язык, алфавит которого обычно содержит четыре группы символов:

1) предикатные переменные — выражения вида , где m и n — неотрицательные целые числа;

2) предметные переменные ;

3) логические символы  (или  — конъюнкция),  (дизъюнкция),  (импликация),  (эквивалентность), ¬ (отрицание),  (квантор существования),  (квантор всеобщности);

4) вспомогательные символы (,) (скобки) и , (запятая).

Выражение называется m-местной предикатной переменной; 0-местные предикатные переменные называются пропозициональными переменными.

Элементарной формулой называется всякая пропозициональная переменная, а также любое выражение вида , где P — какая-либо m-местная предикатная переменная (m > 0), а — произвольные предметные переменные. Из элементарных формул следующим образом строятся предикатные формулы:

1) все элементарные формулы суть формулы;

2) если  и  — формулы, то выражения (  ), (  ), (  ), (  ),¬ считаются формулами;

3) если  — формула, x — предметная переменная, то x  и x  суть формулы.

Например, предикатными формулами являются .

Часть формулы  , которая сама является формулой, называется подформулой формулы .

Областью действия квантора y  или y в формуле  называется такая ее подформула , что y  или y является подформулой формулы .

Вхождение переменной y в формулу  называется связанным, если оно есть вхождение в квантор y  или y, или в область действия одного из этих кванторов.

Всякое вхождение переменной y, не являющееся связанным, называется свободным. Например, в формуле первые два вхождения переменной x₁ — связанные, а третье — свободное.

Переменная y называется свободной переменной формулы , если она имеет свободные вхождения в .

Говорят, что задана интерпретация формулы  на непустом множестве M, если каждой свободной переменной формулы  сопоставлен некоторый элемент из M, а каждой m-местной предикатной переменной из  — некоторый m-местный предикат на M. Истинностное значение  формулы  в данной интерпретации определяется индукцией по построению формулы . Если  имеет вид , то ее значением является значение предиката, сопоставленного предикатной переменной P, на наборе значений переменных . Если  имеет вид ¬, то = И тогда и только тогда, когда = Л. Аналогично, в соответствии с истинностными таблицами для логических операций  определяются значения формул вида (  ), (  ), (  ), (  ) через значения формул  и . Например,   = И, тогда и только тогда, когда = И и = И. Значение формулы y есть Л в том и только том случае, когда  = Л в некоторой интерпретации, полученной из данной приписыванием значения переменной y. Значение формулы y есть И, если = И в некоторой интерпретации, полученной из данной приписыванием значения переменной y. Если = И, то говорят, что формула  истинна в данной интерпретации.

Предикатная формула называется общезначимой на множестве M, если она истинна в любой интерпретации на M. Например, формула

общезначима на любом множестве, содержащем ровно один элемент, и не будет общезначимой на M, если в M есть хотя бы два элемента. Формула называется общезначимой или тавтологией, или тождественно истинной, если она общезначима на любом непустом множестве. Тот факт, что формула  общезначима, обычно обозначают так:  

Целью логики предикатов является описание класса всех общезначимых формул. Одним из способов такого описания является построение исчисления предикатов, то есть исчисления, аксиомами и выводимыми формулами которого являются предикатные формулы. При этом в качестве аксиом выбираются некоторые общезначимые формулы, а правила вывода позволяют из общезначимых формул получать новые общезначимые формулы.