Предикаты. Предикаты и кванторы Двухместный предикат

Цель семинара:

Рассмотреть практическое применение логики предикатов.

План занятия:

Рассматривается тема логика предикатов на которую отводится 2 часа семинарских занятий.

Задача 1. Каким отношениям и функциям соответствуют следующие предикаты, определённые на множестве натуральных чисел:

1. Предикат тождества Е:N 2 →B:

E(a 1 ,a 2)=1 тогда и только тогда, когда a 1 =a 2 .

2. Предикат порядка Q:N 2 →B:

Q(a 1 ,a 2)=1 тогда и только тогда, когда a 1 ≤ a 2.

3. Предикат делимости D:N 2 →B:

D(a 1 ,a 2)=1 тогда и только тогда, когда a 1 делится на а 2 .

4. Предикат суммы S:N 3 →B:

S(a 1 ,a 2 ,a 3)=1 тогда и только тогда, когда a 1 +a 2 =a 3.

5. Предикат произведения П:N 3 →B:

П(a 1 ,a 2 ,a 3)=1 тогда и только тогда, когда a 1 *a 2 =a 3 .

Решение .

1. Двухместному предикату тождества Е-“x 1 ”=”x 2 ” взаимно однозначно соответствуют:

а) двухместное отношение R 1 – «быть равным», R 1 N 2:(a 1 ,a 2) R 1 тогда и только тогда, когда E(a 1 ,a 2)=1;

б) одноместная функция (операция) тождества f 1 (x 1)=x 2 , а именно: f 1 (x)=x, f:N→N.

2. Двухместному предикату порядка Q-“x 1 ≤ x 2 ” взаимно однозначно соответствует двухместное отношение R 2 - «быть не больше», R 2 N 2:(a 1 ,a 2) R 2 тогда и только тогда, когда Q(a 1 ,a 2)=1.

Однако функции f(x 1)=x 2 для предиката порядка Q(x 1 ,x 2) не существует, так как не выполнено условие Р"(а 1 ,а 2 ,…а n ,а n +1)=0 при одинаковых значениях переменной x 1 существует не единственно значение переменной x 2 , при котором предикат Q истинен. Например, Q(2,4)=1 и Q(2,6)=1, однако 4≠6.

3. Двухместному предикату делимости D-“x 1 делится на х 2 ” взаимно однозначно соответствует двухместное отношение R 3 - “делится”, R 3 N 2:(a 1 ,a 2) R 3 тогда и только тогда, когда D(a 1 ,a 2)=1.

Однако функции f(x 1)=x 2 для предиката делимости D(x 1 ,x 2) не существует, так как не выполнено условие Р"(а 1 ,а 2 ,…а n ,а n +1)=0, например D(6,2)=1 и D(6,3)=1, однако 2≠3.

4. Трехместному предикату суммы S- “х 1 +х 2 =х 3 ” взаимно однозначно соответствуют:

а) трёхместное отношение R 4 N 3: (a 1 ,a 2, a 3) R 4 тогда и только тогда, когда S(a 1 ,a 2 ,a 3)=1;

б) двухместная функция (операция арифметики)- сложение f 2 (x 1 ,x 2), а именно х 1 +х 2 =х 3 .

5. Трёхместному предикату произведения П- “x 1 *x 2 =x 3 ” взаимно однозначно соответствуют:

а) трёхместное отношение R 3 N 3: (a 1 ,a 2, a 3) R 5 тогда и только тогда, когда П (х 1 ,х 2 ,х 3)=1;

б) двухместная функция (операция арифметики)- умножение f 3 (x 1 ,x 2)=x 3 , а именно х 1 *х 2 =х 3.

Взаимная однозначность соответствия между S и f 2 (П и f 3), обусловлена выполнением для предиката S(П) условия Р"(а 1 ,а 2 ,…а n ,а n +1)=0 для каждой системы элементов a 1 ,a 2 N существует единственный элемент а 3 N такой, что S(a 1 ,a 2 ,a 3)=1 (соответственно для П(a 1 ,a 2 ,a 3)=1).

Задача 2. Проиллюстрировать на примере предиката делимости, определённого в задаче 1, понятия переменного высказывания, истинного высказывания, ложного высказывания.

Решение .

Предикат делимости D(x 1 ,x 2)- это переменное (двухместное) высказывание, предметной областью которого могут служить любые множества действительных чисел, например множество N.

D(6,2)- высказывание, значение которого есть истина, т.е. истинное высказывание.

D(5,2)- ложное высказывание.

D(3,х), D(х,2)- переменные (одноместные) высказывания, истинность которых зависит от того, каким числом будет замещён символ x, но D(а,1)- истинное высказывание, так как для любого элемента а N имеет место: D(а,1)=1 (любое натуральное число делится на единицу).

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

Решение .

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

«если а делится на b и b делится на с, то а делится на с», состоит из трёх простых высказываний D(a,b), D(b,c) и D(a,c). Следовательно, транзитивное свойство делимости можно записать в виде составного высказывания (логической формулы):

«если D(a,b) и D(b,c), то D(a,с) или (D(a,b) & D(b,c)) → D(a,c).

Задача 4. Дать словесные формулировки следующих составных высказываний (предложений):

1. S(a,b,c) & D(a,d) & D(b,d)→D(c,d), где S и D- предикаты суммы и делимости соответственно (см.пример 1);

2. D(a,b) & S(a,b,c);

3. S(a,b,c) ~ S(b,a,c);

4. P 1 ~ P 2 , где P 1 – предикат «число 3n является чётным»; Р 2 - предикат «число n является чётным».

Решение .

1. «Если каждое слагаемое a,b суммы целых чисел делится на некоторое число d, то и сумма с делится на это число»:

S(a,b,c) & D(a,d) & D(b,d)→D(c,d).

2. «Число а не делится на число b, и неверно, что их сумма равна с»: D(a,b) & S(a,b,c).

3. «От перестановки мест слагаемых a и b сумма с не меняется»- свойство коммутативности арифметической операции сложения: S(a,b,c) ~ S(b,a,c).

4. «Число 3n является чётным тогда и только тогда, когда n является чётным»: P 1 ~ P 2.

Эквивалентность может быть выражена и другими словесными формулировками, в том числе:

· «из того, что Р 1 , следует то, что Р 2 , и обратно»;

· «из того, что Р 2 , следует то, что Р 1 , и обратно»;

· «условия Р 1 необходимо и достаточно для того, чтобы Р 2 »;

· «Р 2 необходимо и достаточно, чтобы Р 1 »;

· «Р 1 , если и только если Р 2 »;

· «Р 2 , если и только если Р 1 »;

· «условия Р 1 и Р 2 эквивалентны»;

· «Р 2 тогда и только тогда, когда Р 1 » и др.

Задача 5. Пусть х определён на множестве людей М, а Р(х)- предикат «х-смертен». Дать словесную формулировку предикатной формулы

Решение .

Выражение означает «все люди смертны». Оно не зависит от переменной х, а характеризует всех людей в целом, т.е. выражает суждение относительно всех х множества М.

Задача 6. Пусть Р(х)- предикат «х-чётное число», определённый на множестве М. Дать словесную формулировку высказывания определить его истинность.

Решение .

Исходный предикат Р(х)- «х- чётное число» является переменным высказыванием: при подстановке конкретного числа вместо переменной х он превращается в простое высказывание, являющееся истинным или ложным, например при подстановке числа 5 превращается в высказывание «5-чётное число», являющееся ложным. Высказывание означает «в М существует четное число». Поскольку множество М, на котором задан предикат Р(х), не определено в условии (в таком случае говорят, что задача сформулирована не вполне корректно), доопределим М.

Пусть предикат Р(х) определён на множестве натуральных чисел N, т.е. , тогда высказывание - истинно. В общем случае высказывание истинно на любом множестве М, содержащем хотя бы одно чётное число, и ложно на любом множестве нечетных чисел.

Задача 7. Пусть N(х)- предикат «х-натуральное число». Рассмотреть варианты навешивания кванторов. Проинтерпретировать полученные высказывания и определить их истинность.

Решение .

Высказывание «все числа- натуральные» истинно на любом множестве натуральных чисел и ложно, если М содержит хотя бы одно ненатуральное число, например целое отрицательное;

Высказывание «существует натурально х» истинно на любом множестве М, содержащем хотя бы одно натуральное число, и ложно- в противном случае.

Задача 8. Записать предикатной формулой предложение «Любой человек имеет отца».

Решение .

Для построения предикатной формулы используем два предиката «х- человек» и «у- отец х» и для удобства восприятия обозначим их соответственно: ЧЕЛОВЕК (х) и ОТЕЦ (у). Тогда предложение «Любой человек имеет отца» в предикатной форме имеет вид:

Заметим, что если предикат ОТЕЦ(у,х) определён на множестве людей, то выражение «любой человек имеет отца» можно записать проще:

Задача 9. Пусть предикат Р(х,у) описывает отношение «х любит у» на множестве людей. Рассмотреть все варианты навешивания кванторов на обе переменные. Дать словесную интерпретацию полученных высказываний.

Решение .

Обозначим предикат «х любит у» через ЛЮБИТ (х,у). Предложения, соответствующие различным вариантам навешивания

ЛЮБИТ(х,у)- «для любого человека х существует человек у, которого он любит» или «всякий человек кого-нибудь любит» (рис. а);

ЛЮБИТ (х,у)- «существует такой человек у, что его любят все х» (рис. б)ж

ЛЮБИТ (х,у)- «все люди любят всех людей» (рис. в);

ЛЮБИТ (х,у)- «существует человек, который кого- то любит» (рис. г);

ЛЮБИТ (х,у)- «существует человек, который любит всех людей» (рис. д);

ЛЮБИТ (х,у)- «для всякого человека существует человек, который его любит» (рис. е).

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

Задача 10. Пусть Q(x,y)- предикат порядка «х≤у». Рассмотреть различные варианты квантификации его переменных. Определить истинность получаемых выражений для разных случаев интерпретации области определения М предиката, х, у М.

Решение .

Одноместный предикат от у: « для любого х имеет место х≤у». Если М- бесконечное множество неотрицательных целых чисел, то этот предикат ложен; на любом конечном множестве натуральных чисел предикат истинен в единственной точке, представляющей наибольшее число в М. При подстановке любого другого у из М этот предикат обращается в ложное высказывание;

Одноместный предикат от х: «для любого у имеет место х≤у». Если М-множество неотрицательных целых чисел, то этот предикат истинен в единственной точке х=0 и ложен при подстановке вместо х любого числа из М;

Одноместный предикат от у: «существует число в М, которое не больше у». Если М- любое непустое множество чисел, то данный предикат превращается в истинное высказывание при подстановке какого- либо у из М.

Одноместный предикат от х: « существует число в М, которое не меньше х». На любом непустом множестве М чисел данный предикат превращается в истинное высказывание при подстановке какого- либо х из М.

Высказывание « для любых х и у выполняется х≤у» ложно на любом множестве, состоящем более, чем из одного элемента, и истинно на множестве с одним элементом;

Высказывание «существуют такие х и у, что х≤у» истинно на любом непустом множестве;

Высказывание «для любого числа х существует число у, не меньше чем х» истинно на любом непустом множестве;

Высказывание «существует у такой, что для любого х х≤у»утверждает, что в М имеется единственный максимальный элемент;

Высказывание «существует х такой, что он не больше любого у» утверждает, что в М имеется единственный минимальный элемент.

Высказывание «для любого числа у существует число х, не больше, чем у» истинно на любом непустом множестве

Задача 11. Рассмотреть все возможные варианты навешивания кванторов на предикат D(х,у)- «х делится на у», определенный на множестве натуральных чисел N. Дать словесные формулировки полученных высказываний и определить их исьтинность.

Решение .

Операции навешивания кванторов приводят к следующим формулам:

Одноместный предикат «всякое натуральное число из N делится на натуральное число у из N»; истинный только для одного значения свободной переменной у=1;

Переменное высказывание «существует натуральное число, которое делится на у», истинное для любого значения свободной переменной у, взятой из множества N;

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

Переменное высказывание «существует натуральное число, которое делит натуральное число х», истинное для любого значения свободной переменной х;

Высказывания «для любых двух натуральных чисел имеет место делимость одного на другое» ложные;

Высказывания «существуют такие два натуральных числа, что первое делится на второе», истинны;

Высказывание «существует натуральное число, которое делится на любое натуральное», ложное;

Высказывание « для всякого натурального числа найдется такое натуральное, которое делится на первое», истинное;

Окончательно получим префиксную нормальную форму для исходной предикатной формулы.

Понятие предиката.

Предикат- представляет собой функцию субъекта и выражения свойств о субъекте.

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

Например, в рассуждении «Всякий ромб – параллелограмм; ABCD – ромб; следовательно, ABCD – параллелограмм» посылки и заключение являются элементарными высказываниями логики высказываний и с точки зрения этой логики рассматриваются как целые, неделимые, без учёта их внутренней структуры. Следовательно, алгебра логики, будучи важной частью логики, оказывается недостаточной в анализе многих рассуждений.

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

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

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

Например, в высказывании «7 – простое число», «7» – субъект, «простое число» – предикат. Это высказывание утверждает, что «7» обладает свойством «быть простым числом».

Если в рассмотренном примере заменить конкретное число 7 переменной х из множества натуральных чисел, то получим высказывательную форму «х – простое число». При одних значениях х (например, х = 13, х = 17) эта форма дает истинные высказывания, а при других значениях х (например, х = 10, х = 18) эта форма дает ложные высказывания.

Определение 1. Одноместным предикатом Р (х ) называется всякая функция одного переменного, в которой аргумент x пробегает значения из некоторого множества M , а функция при этом принимает одно из двух значений: истина или ложь.

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

Множество , на котором предикат принимает только истинные значения, называется областью истинности предиката Р (х ).

Так, предикат P (x ) – «х – простое число» определён на множестве N , а множество для него есть множество всех простых чисел.

Определение 2. Предикат Р (х ), определённый на множестве M , называется тождественно истинным (тождественно ложным ), если .

Определение 3. Двухместным предикатом P ( x ,у ) называется функция двух переменных х и у , определённая на множестве М =М 1 ×М 2 и принимающая значения из множества {1,0}.

В качестве примеров двухместных предикатов можно назвать предикаты: Q (x ,у ) – «х = у » предикат равенства, определённый на множестве R 2 =R ×R ; F (x ,у ) – «х || у » прямая х параллельна прямой у , определённой на множестве прямых, лежащих на данной плоскости.

Аналогично определяется n -местный предикат.

Говорят, что предикат Р (х ) является следствием предиката Q (х ) , если ; и предикаты Р (х ) и Q (х )равносильны , если .

Приведём примеры к изложенному материалу.

Пример 1. Среди следующих предложений выделить предикаты и для каждого из них указать область истинности, еслиM = R для одноместных предикатов и M = R×R для двухместных предикатов:

1) х + 5 = 1;

2) при х = 2 выполняется равенство х 2 – 1 = 0;
3) х 2 – 2х + 1 = 0;
4) существует такое число х , что х 3 – 2х + 1 = 0;
5) х + 2 х – 4;
6) однозначное неотрицательное число х кратно 3;
7) (х + 2) – (3х – 4);
8) х 2 + у 2 > 0.

Решение . 1) Предложение является одноместным предикатом Р (х ), I P = {– 4};
2) предложение не является предикатом. Это ложное высказывание;
3) предложение является одноместным предикатом Р (х ), I P = {1};
4) предложение не является предикатом. Это истинное высказывание;
5) предложение является одноместным предикатом Р (х ), I P = (3; +∞);
6) предложение является одноместным предикатом Р (х ), I P = {0; 3; 6; 9};
7) предложение не является предикатом;
8) предложение является двухместным предикатом Q (х,y ), I Q = R×R \ {(0,0)}.

Пример 2. Изобразить на декартовой плоскости область истинности предиката .

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

24.Логические операции над предикатами: конъюнкция, дизъюнкция, отрицание, импликация. Кванторные операции. Кванторы всеобщности и существования.

Логические операции над предикатами

Предикаты, так же, как высказывания, принимают два значения и и л (1, 0), поэтому к ним применимы все операции логики высказываний.

Рассмотрим применение операций логики высказываний к предикатам на примерах одноместных предикатов.

Пусть на некотором множестве М определены два предиката Р (х ) и Q (х ).

Определение 4. Конъюнкцией двух предикатов Р (х ) и Q (х ) называется новый предикат Р (х )&Q (х ), который принимает значение «истина» при тех и только тех значениях , при которых каждый из предикатов Р (х ) и Q (х ) принимает значение «истина» и принимает значение «ложь» во всех остальных случаях. Очевидно, что областью истинности предиката Р (х )&Q (х ) является общая часть областей истинности предикатов Р (х ) и Q (х ), т.е. пересечение .

Так, например, для предикатов Р (х ): «х – четное число» и Q (х ): « х кратно 3» конъюнкцией Р (х )&Q (х ) является предикат «х – четное число и х кратно 3», то есть предикат «х делится на 6».

Определение 5. Дизъюнкцией двух предикатов Р (х ) и Q (х ) называется новый предикат , который принимает значение «ложь» при тех и только тех значениях , при которых каждый из предикатов принимает значение «ложь» и принимает значение «истина» во всех остальных случаях. Ясно, что областью истинности предиката является объединение областей истинности предикатов Р (х ) и Q (х ), то есть объединение .

Определение 6. Отрицанием предиката Р (х ) называется новый предикат , который принимает значение «истина» при всех значениях , при которых предикат Р (х ) принимает значение «ложь», и принимает значение «ложь» при тех значениях , при которых предикат Р (х ) принимает значение «истина». Очевидно, что, .

Определение 7. Импликацией предикатов Р (х ) и Q (х ) называется новый предикат , который является ложным при тех и только тех значениях , при которых одновременно Р (х ) принимает значение «истина», а Q (х ) – значение «ложь» и принимает значение «истина» во всех остальных случаях.

Так как при каждом фиксированном справедлива равносильность , то .

Ясно, что при выполнении логических операций над предикатами к ним применимы и равносильности алгебры логики.

Пример 3. Пусть даны предикаты А (х,у ) и В (х,у ), определенные на множестве . Найти множество истинности предиката и изобразить ее с помощью кругов Эйлера-Венна.

Решение . Так как , то .

Изображена серой частью рисунка:

Можно рассматривать и обратную задачу: «Зная область истинности предиката, полученного в результате применения логических операций к некоторым предикатам, записать этот предикат».

Пример 4. Записать предикат, полученный в результате логических операций над предикатами Р (х ), Q (х ) и R (х ), область истинности которого изображена серой частью рисунка:

Решение . Так как здесь , то искомый предикат имеет вид: .
Кванторные операции над предикатами

Пусть имеется предикат Р (х ), определенный на множестве М . Если , то при подстановке а вместо х в предикат Р (х ) получится высказывание Р (а ). Такое высказывание называется единичным . Наряду с образованием из предикатов единичных высказываний в логике предикатов рассматривается еще две операции, которые превращают одноместный предикат в высказывание.

Определение 8. Пусть Р (х М . Под выражением понимают высказывание, истинное, когда Р (х ) тождественно истинный на множестве М предикат, и ложное в противном случае. Это высказывание уже не зависит от х . Соответствующее ему словесное выражение будет: «Для всякого х Р (х ) истинно». Символ называют квантором всеобщности .

Переменную х в предикате Р (х ) называют свободной (ей можно придавать различные значения из М ), в высказывании переменную х называют связанной квантором .

Определение 9. Пусть Р (х ) – предикат, определенный на множестве М . Под выражением понимают высказывание, которое является истинным, если существует хотя бы один элемент , для которого Р (х ) истинно, и ложным в противном случае. Это высказывание уже не зависит от х . Соответствующее ему словесное выражение будет: «Существует х , при котором Р (х ) истинно». Символ называют квантором существования. В высказывании переменная х связана квантором .

Приведем пример употребления кванторов.

Пример 5. Пусть на множестве N натуральных чисел задан предикат Р (х ): «Число х кратно 5». Используя кванторы, из данного предиката можно получить высказывания: – «Все натуральные числа кратны 5»; – «Существует натуральное число, кратное 5». Очевидно, первое из этих высказываний ложно, а второе истинно.

Ясно, что высказывание истинно только в том единственном случае, когда Р (х ) – тождественно истинный предикат, а высказывание ложно только в том единственном случае, когда Р (х ) – тождественно ложный предикат.

Кванторные операции применяются и к многоместным предикатам. Так, применение к двухместному предикату Q (х,у ) квантора всеобщности по переменной х дает одноместный предикат , зависящий от у . К этому предикату можно применить кванторную операцию по переменной у . В результате получим или высказывание или высказывание .

Таким образом, может быть получено одно из восьми высказываний: , , , , , , , .

Легко показать, что перестановка любых кванторов местами, вообще говоря, изменяет логическое значение высказывания.

Пример 6 . Пусть предикат Q (х,у ): «ху» определен множестве N × N. Показать, что высказывания и имеют различные логические значения.

Решение . Так как высказывание означает, что для всякого натурального числа у существует натуральное число х такое, что у является делителем х , то это высказывание истинно. Высказывание означает, что есть натуральное число х , которое делится на любое натуральное число у. Это высказывание, очевидно, ложно.

Если предикат Р (x ) является тождественно истинным, то истинными будут высказывания Р (а 1), Р (а 2),..., Р (а n ). При этом истинными будут высказывание и конъюнкция Р (а 1)&Р (а 2)&...&Р (а n ).

Если же хотя бы для одного элемента Р (а k ) окажется ложным, то ложными будут высказывание и конъюнкция Р (а 1)&Р (а 2)&...&Р (а n ). Следовательно, справедлива равносильность

Нетрудно показать, что справедлива и равносильность

Это означает, что кванторные операции обобщают операции конъюнкции и дизъюнкции на случай бесконечных областей.

25. Понятие формулы логики предикатов. Значение формулы логики предикатов. Равносильные формулы логики предикатов. Основные равносильности логики предикатов.

Понятие формулы логики предикатов.

В логике предикатов используется следующая символика:

1. Символы р , q , r , ... – переменные высказывания, принимающие два значения: 1 – истина, 0 – ложь.

2. Предметные переменные – х , у , z , ..., которые пробегают значения из некоторого множества М : х 0 , у 0 , z 0 , ... – предметные константы, то есть значения предметных переменных.

3. Р (·), F (·) – одноместные предикатные переменные; Q (·,·,...,·), R (·,·,...,·) – n -местные предикатные переменные. Р 0 (·), Q 0 (·,·,…,·) – символы постоянных предикатов.

4. Символы логических операций: .

5. Символы кванторных операций: .

6. Вспомогательные символы: скобки, запятые.

Определение формулы логики предикатов.

1. Каждое высказывание как переменное, так и постоянное, является формулой.

2. Если F (·,·,...,·) – n -местная предикатная переменная или постоянный предикат, а x 1 , х 2 , ..., х n – предметные переменные или предметные постоянные, не обязательно все различные, то F (x 1 , х 2 ,..., х n ) есть формула. В этой формуле предметные переменные являются свободными. Формулы вида 1 и 2 называются элементарными.

3. Если A и B – формулы, причем такие, что одна и та же предметная переменная не является в одной из них связанной, а в другой свободной, то слова есть формулы. В этих формулах те переменные, которые в исходных формулах были свободными, являются свободными, а те, которые были связанными, являются связанными.

4. Если А – формула, то – формула, и характер предметных переменных при переходе от формулы А к формуле не меняется.

5. Если А (х ) – формула, в которую предметная переменная х входит свободно, то слова и являются формулами, причем предметная переменная в них входит связанно.

6. Никакая другая строка символов формулой не является.

Например, если Р (x ) и Q (х,у ) – одноместный и двухместный предикаты, а q , r – переменные высказывания, то формулами будут слова:

Не является формулой слово: . Здесь нарушено условие п.3, так как в формулу переменная х входит связано, а в формулу Р (х ) переменная х входит свободно.

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

Пример 1. Какие из следующих выражений являются формулами логики предикатов? В каждой формуле выделите свободные и связанные переменные.

2) ;

3) ;

Решение. Выражения 1), 2), 4), 6) являются формулами, так как записаны в соответствии с определением формулы логики предикатов. Выражения 3) и 5) не являются формулами. В выражении 3) операция конъюнкции применена к формулам P (x ) и ; в первой из них переменная х свободна, а во второй связана квантором общности, что противоречит определению формулы. В выражении 5) квантор существования по переменной у навешен на формулу , в которой переменная у связана квантором общности, что также противоречит определению формулы.

В формуле 1) переменная у свободна, а переменные х и z связаны. В формуле 2) нет предметных переменных. В формуле 4) переменная х связана, а переменная у свободна.

Значение формулы логики предикатов

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

а) переменных высказываний;
б) свободных предметных переменных из множества М ;
в) предикатных переменных.

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

Пример 2. Дана формула , где предикаты Р (x ), Q (x ) и R (x ) определены на множестве N. Найти ее значение, если

1) Р (x ): «число х делится на 3», Q (x ): «число х делится на 4», R (x ): «число х делится на 2»;

2) Р (x ): «число х делится на 3», Q (x ): «число х делится на 4», R (x ): «число х делится на 5».

Решение. В обоих случаях конъюнкция Р (x )&Q (x ) есть утверждение, что число х делится на 12. Но тогда при всех х , если число х делится на 12, то оно делится и на 2, и, значит, в случае 1) формула истинна.

В алгебре логики высказывания рассматриваются как нераздельные целые и только с точки зрения их истинности или ложности.

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

Например, в рассуждении “Всякий ромб – параллелограмм; АВСD – ромб; следовательно, АВСD - параллелограмм ” посылки и заключение являются элементарными высказываниями логики высказываний и с точки зрения этой логики рассматриваются как целые, неделимые, без учета их внутренней структуры. Следовательно, алгебра логики, будучи важной частью логики, оказывается недостаточной в анализе многих рассуждений.

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

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

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

предикат – это то, что утверждается о субъекте. Например, в высказывании “7 - простое число”, “7” – субъект, “простое число” – предикат. Это высказывание утверждает, что “7” обладает свойством “быть простым числом”.

Если в рассмотренном примере заменить конкретное число 7 переменной х из множества натуральных чисел, то получим высказывательную форму “х – простое число”. При одних значения х (например, х=13, х=17) эта форма дает истинные высказывания, а при других значениях х (например, х=10, х=18) эта форма дает ложные высказывания.

Ясно, что эта высказывательная форма определяет функцию одной переменной х, определенной на множестве N, и принимающую значения из множества {1;0} (или {и; л}). Здесь предикат становится функцией субъекта и выражает свойство субъекта.

Определение 1.

Одноместным предикатом Р(x) называется произвольная функция переменного x, определенная на множестве M и принимающая значение из множества {1; 0}.

Множество М, на котором определен предикат Р(x), называется областью определения предиката Р(x).

Множество всех элементов , при которых предикат принимает значения “истина” (1), называется множеством (областью) истинности предиката Р(x), т.е. множество истинности предиката Р(х)- это множество .Так, например, предикат Р(x) – “x – простое число” определен на множестве N, а множество истинности I P для него есть множество всех простых чисел.

Предикат Q(x) – “sinx=0” определен на множестве R, а его множеством истинности является

Предикат F(x) – “диагонали параллелограмма x взаимно перпендикулярны” определен на множестве всех параллелограммов, а его множеством истинности является множество всех ромбов.

Из приведенных примеров видим, что одноместные предикаты выражают свойства предметов (субъектов).

Определение 2.

Предикат Р(х), определенный на множестве М, называется тождественно истинным, если его множество истинности совпадает с областью определения, т. е. I p =M.

Определение 3.

Предикат Р(х), определенный на множестве М, называется тождественно ложным, если его множество истинности является пустым множеством, т. е. I p =0.

Естественным обобщением понятия одноместного предиката является понятие многоместного предиката, с помощью которого выражаются отношения между предметами.

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

Определение 4.

Двухместным предикатом Р(x,y) называется функция двух переменных x и y, определенная на множестве М=М 1 хМ 2 и принимающая значения из множества {1;0}.

В числе примеров двухместных предикатов можно назвать такие предикаты: Q(x, y) – “x=y” - предикат равенства, определенный на множестве RхR=R 2 ; F(x,y) – “х параллелен y”, “прямая х параллельна прямой y”, определенный на множестве прямых, лежащих на данной плоскости.

Совершенно аналогично вводится понятие трехместного предиката. Приведем пример трехместного предиката (функции трех переменных): S(x,y,z) – “x+y=z”. Подстановка в него х=3 превращает его в двухместный предикат: S(y,z) – “3+y=z”, а подстановка х=3, z=2 – в одноместный предикат S(y) – “3+y=2”.Подстановка же S(2,3,5) превращает его в истинное высказывание, а S(1,7,4)– в ложное.

Аналогично определяется и n-местный предикат (функция n переменных). Пример n- местного предиката:

R(x 1 , x 2 ,…,x n): a 1 x 1 +…+a n x n =0, который, как видим, представляет собой алгебраическое уравнение с n неизвестными.

При n=0 будем иметь нульместный предикат – это логическая (пропозициональная) переменная, принимающая значения из множества {1;0}.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

на тему: "Предикаты: определения и примеры"

Введение

Заключение

Введение

В чемсостоит необходимость введения предикатов в математику?

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

Возьмем, например, следующее умозаключение. "Всякое целое число является рациональным. Число 5 - целое. Следовательно, 5 - рациональное число". Все эти три утверждения с точки зрения логики высказываний являются атомарными. Т.е. только средствами логики высказываний нельзя вскрыть внутреннюю структуру и поэтому нельзя доказать логичность этого рассуждения в рамках логики высказываний. Средства, предоставляемые логикой высказываний, оказываются недостаточными для анализа многих математических рассуждений. В алгебре логики не рассматриваются ни структура высказываний, ни тем более, их содержание. В то же время и в науке, и в практике используются заключения, существенным образом зависящие как от структуры, так и от содержания используемых в них высказываний.

Например, в рассуждении " Всякий ромб - параллелограмм; ABCD - ромб; следовательно, ABCD - параллелограмм" посылки и заключение являются элементарными высказываниями логики высказываний, и с точки зрения этой логики рассматриваются как целые, неделимые, без учёта их внутренней структуры. Следовательно, алгебра логики, будучи важной частью логики, оказывается недостаточной в анализе многих рассуждений.

В силу изложенного материала, можно заключить, что актуальность данной работы несомненна.

Цель данного реферата заключается в том, чтобы совершить обзор

литературных источников по проблеме предикатов в дискретной математике.

Для достижения поставленной цели необходимо решить следующие задачи:

·найти нужную информацию о предикатах по данной теме;

·тщательно проанализировать и выбрать нужные данные;

·оформить реферат согласно требованиям.

Объектом исследования является архив материалов по математическим предикатам.

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

Реферат состоит из введения, основной части, заключения и списка использованной литературы.

Предикаты: определения и примеры

Введем основное понятие темы.

Определение 1. Пусть М - непустое множество. Тогда n-местным предикатом, заданным на М, называется выражение, содержащее n переменных и обращающееся в высказывание при замене этих переменных элементами множества М .

Поясним конкретными примерами. Пусть М есть множество натуральных чисел N . Тогда, например, такие выражения: "x - простое число", "x - четное число", "x больше 10" являются одноместными предикатами. При подстановке вместо x произвольных натуральных чисел получаются высказывания: "2 - простое число", "6 - простое число", "3 - четное число", "5 больше 10" и т.д.

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

Множество , на котором предикат принимает только истинные значения, называется областью истинности предиката Р (х ) .

Так, предикат P (x ) - "х - простое число" определён на множестве N , а множество для него есть множество всех простых чисел.

Вот такие выражения: " x больше y", " x делит y нацело", " x плюс y равно 10, или x+y=10 " являются двухместными предикатами. Примеры трехместных предикатов, заданных на множестве натуральных чисел: " число z лежит между x и y", " x плюс y равно z", " |x-y| = z " .

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

Причем местность предикатов не всегда равна числу всех переменных, содержащихся в выражении.

Например, выражение " существует число x такое, что y = 2 x " на множестве натуральных чисел определяет одноместный предикат.,

По смыслу этого выражения, в нем можно заменять только переменную y. Например: если применить замену y на 6, то получим истинное высказывание: " существует число x такое, что 6 = 2x", а если заменим y на 7, то получим ложное (на множестве N) высказывание: " существует число x такое, что 7 =2x".

Предикат с заменяемыми переменными x1,…,xn обычно обозначается заглавной латинской буквой, после которой в скобках указываются эти переменные. Например, P (x1,x2), Q (x2,x3), R (x1). Среди переменных в скобках могут быть и фиктивные .

Определение 2. Предикат (n -местный, или n -арный <#"20" src="doc_zip3.jpg" /> (или " Истина " и " Ложь "), определённая на n -й декартовой степени <#"21" src="doc_zip4.jpg" />,

если на любом наборе аргументов он принимает значение 1.

Предикат называют тождественно - ложным и пишут:

если на любом наборе аргументов он принимает значение 0.

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

Например, обозначим предикатом EQ (x, y) отношение равенства (" x = y "), где x и y принадлежат множеству вещественных чисел <#"justify">Определение 3. Предикат W (x1,…,xn) называется конъюнкцией предикатов U (x1,…,xn) и V (x1,…,xn), заданных на множестве М , если для любых а1,…, аn из М высказывание W (а1,…, аn) есть конъюнкция высказываний U (а1,…, аn) и V (а1,…, аn) .

Аналогично приводятся определения и других упомянутых выше операций.

В логике предикатов первого порядка вводятся и две новые операции. Называются они квантором общности и квантором существования . Эти операции рассмотрим сначала на примерах.

Пусть дано выражение: " существует число х, такое, что x + y=10". На множестве натуральных чисел это предложение определяет одноместный предикат P (y), так, например, Р (2) и Р (9) - истинные высказывания, а Р (11) - ложное. Если обозначить предикат " x + y = 10 " через S (x,y) (а это предикат двухместный), то P (y) можно записать так: " существует х такой, что S (x,y)". В этом случае говорят, что предикат P (y) получен из предиката S (x,y) навешиванием квантора существования на x и пишут P (y) = (?x) S (x,y)

Рассмотрим другой пример. Выражение " для всех х справедливо, что y = - х2 " определяет на множестве целых чисел одноместный предикат Q (y). Если предикат " y = - х2 " обозначить через T (x,y), то Q (y) можно записать так: "для всех x справедливо T (x,y)". В таком случае говорят, что предикат Q (y) получен из предиката T (x,y) навешиванием квантора общности на х и пишут Q (y) = (?x) T (x,y).

Пользуясь этими примерами, дадим определение в общем виде.

Определение 4. Пусть P (x1,…,xn) - предикат, заданный на множестве M , y - переменная. Тогда выражение: " для всякого y выполняется P (x1,…,xn)" - предикат, полученный из P навешиванием квантора общности на переменную y, а выражение " существует y такой, что выполняется P (x1,…,xn)" - предикат, полученный из P навешиванием квантора существования на переменную y .

Заметим, что в определении не требуется, чтобы y была одна из переменных x1,…,xn, хотя в содержательных примерах, квантор навешивается на одну из переменных x1,…,xn. Указанное требование не накладывается, чтобы избежать усложнения определения формулы логики предикатов. Если y - одна из переменных x1,…,xn, то после навешивания квантора на y новый предикат является (n-1) - местным, если y{ x1,…,xn}, то местность нового предиката равна n .

Если предикат W (x1,…,xn) получен из предикатов U (x1,…,xn) и V (x1,…,xn) с помощью связок, то истинность высказывания W (a1,…,an) определяется таблицами истинности этих связок . Пусть W (x1,…,xn) = (?y) U (x1,…,xn,y). Тогда высказывание W (a1,…,an) истинно тогда и только тогда, когда для любого b M истинно высказывание U (a1,…,an,b). Если же W (x1,…,xn) = (?y) U (x1,…,xn,y), то высказывание W (a1,…,an) истинно в том и только в том случае, когда найдется b M, для которого высказывание U (a1,…,an) истинно .

Вообще понятие предиката - весьма широкое понятие . Это видно уже из приведенных выше римеров. Тем не менее, еще раз подчеркнем, показав, что n - местная функция может рассматриваться как (n+1) - местный предикат. Действительно, функции y = f (x1,…,xn), заданной на множестве М, можно поставить в соответствие выражение " y равно f (x1,…,xn)". Это выражение есть некоторый предикат P (x1,…,xn,y). При этом, если элемент b есть значение функции в точке (a1,…,an), то высказывание P (a1,…,an,b) истинно, и обратно. (Подобное "превращение" функции в предикат мы уже привели в качестве примера выше для сложения натуральных чисел.)

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

Во-первых, предикат можно представить отношением следующим образом.

Пусть предикат P (x1,…,xn) задан на множестве M. Рассмотрим прямую степень этого множества Mn = Mx Mx…xM и подмножество Dp множества Mn, определяемое равенством:

Dp = { (a1,…,an) Mn высказывание P (a1,…,an) истинно}.

Отношение Dp можно назвать областью истинности предиката P. Во многих случаях предикат P можно отождествить с отношением Dp.

При этом, правда, возникают некоторые трудности при определении операций над отношениями, аналогичными операциям над предикатами .

Во-вторых, предикат P (x1,…,xn), заданный на M, можно отождествить с функцией fp: Mn {0,1}, определяемой равенством:

Говорят, что предикат Р (х ) является следствием предиката Q (х ) : , если; и предикаты Р (х ) и Q (х ) равносильны:

Приведём примеры к изложенному материалу.

Пример 1. Среди следующих предложений выделить предикаты и для каждого из них указать область истинности, если M = R для одноместных предикатов и M = R×R для двухместных предикатов :

. х + 5 = 1

При х = 2 выполняется равенство х 2 - 1 = 0

. х 2 - 2х + 1 = 0

Существует такое число х , что х 3 - 2

. х + 2 < Зх - 4

Однозначное неотрицательное число х кратно 3

. (х + 2) - (3х - 4)

. х 2 + у 2 > 0

Решение .

1) Р (х ), I P = { - 4};

2)Предложение не является предикатом. Это ложное высказывание;

3)Предложение является одноместным предикатом Р (х ), I P ={1};

4)Предложение не является предикатом. Это истинное высказывание;

5) Предложение является одноместным предикатом Р (х ), I P = (3; +?);

) Предложение является одноместным предикатом Р (х ), I P = {0; 3; 6; 9};

) Предложение не является предикатом;

) Предложение является двухместным предикатом Q (х,y ), I Q = R×R \ { (0,0) }.

Пример 2. Изобразить на декартовой плоскости область истинности предиката .

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

Рисунок 1. График параболы х = у 2

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

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

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

предикат декартова плоскость математика

Заключение

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

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

Итак, актуальность темы реферата несомненна. Цель достигнута и задачи выполнены. Литература просмотрена, выбрана, проанализирована, результаты представлены в данном реферате.

Список используемых источников

1.Эвнин А.Ю. Дискретная математика. Конспект лекций. 1998.

2.Ерусалимский А.Я. Дискретная математика. Теория. Задачи. Приложения. 2000.

3.Электронный источник. URL: http://forum. vopr.net

Электронный источник. http://lib. mexmat.ru/books/109887

Электронный источник. http://lib. mexmat.ru/books/81214

Репетиторство

Нужна помощь по изучению какой-либы темы?

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

Логика высказываний – очень узкая логическая система. Есть такие типы логических рассуждений, которые не могут быть осуществлены в рамках логики высказываний, например:

Всякий друг лица А есть друг лица В. С не есть друг В, следовательно, С не есть друг А.
Простое число два – четное. Следовательно, существуют простые четные числа.

Корректность этих умозаключений основана на внутренней структуре самих предложений и на смысле слов «всякий» и «существует».

Рассмотрим предложения, зависящие от параметров, например: «х – четное число», «х меньше y », «x +y =z », «u и v – братья». Если в первых трех предложениях заменить x ,y и z некоторыми числами, а в последнем подставить имена членов некоторой семьи, то полученные высказывания могут быть истинными или ложными. Например, для х =5, y =2, z =7, u – Петр, v – Иван получим: «5 – четное число», «5 меньше 2», «5+2=7», «Петр и Иван – братья».

Предложения такого типа называются предикатами. Точнее, предикатом P(x 1 ,…,x n) называется функция, переменные которой принимают значения из некоторого множества М, а сама она принимает два значения: истинное (И) и ложное (Л), т.е. P(x 1 ,…,x n):М {И,Л}.

Предикат от n аргументов называют n-местным предикатом и обозначают полностью P (n) (x 1 ,…,x n) , если нужно подчеркнуть число аргументов. Высказывания считают нуль-местными предикатами.

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

Например:

1. Пусть P (1) (x) означает предикат «х делится на 2», а Q (1) (х) – предикат «х делится на 3». Тогда выражение P (1) (x) &Q (1) (х) означает предикат «х делится на 2 и х делится на 3», т.е. определяет предикат делимости на 6.

2. Пусть S (2) (х,у) означает предикат «х=у ». Он принимает значение И тогда и только тогда, когда х=у . В этом случае выражение ┐S (2) (х,х) ÞS (2) (х,у) определяет предикат, принимающий значение И при любых х и у.

Кроме операций логики высказываний будем применять еще операции связывания квантором.

Квантор всеобщности. Пусть Р(х) – предикат, принимающий значение И или Л для каждого х ÎМ. Тогда под выражением "хР(х) будем подразумевать высказывание истинное, когда Р(х) истинно для каждого элемента х из М, и ложное – в противном случае. Символ "х называется квантором всеобщности и запись "хР(х) читается так: «для всех х Р(х) ». Это высказывание уже не зависит от х.

Квантор существования. Пусть Р(х) – предикат. Под выражением $х Р(х) будем понимать высказывание истинное, если существует элемент множества М, для которого Р(х) истинно, и ложное – в противном случае. Символ $ х называется квантором существования и запись $ хР(х) читается так: «существует х , такое, что (или для которого) Р(х) » .

Для предикатов, рассмотренных чуть ранее, можем записать:

$ х (P (1) (x) &Q (1) (х)) – истинное высказывание;
" х (P (1) (x) &Q (1) (х)) – ложное высказывание;
" х,у (┐S (2) (х,х) ÞS (2) (х,у)) – истинное высказывание.

Введем теперь строгие определения для исчисления предикатов.

(Чистое) исчисление предикатов (первого порядка) - это формальная теория К, в которой определены следующие компоненты.

1. Алфавит:

связки основные ┐,

дополнительные &,

служебные символы (,) Î (, ’ , ’ ,)

кванторы всеобщности

существования

предметные константы

переменные

предметные предикаты P, Q, . . .

функторы f, q,. . .

С каждым предикатом и функтором связано некоторое натуральное число, которое называется арностью, или иногда местностью.

2. Формулы имеют следующий синтаксис:

Формула = (атом

| ┐ (формула | ( формула

(формула ) | (переменная формула

| переменная формула

Атом = предикат ( список термов )

Список термов = терм | терм ,

Список термов терм = константа |

Переменная | функтор ( список термов )

При этом должны быть выполнены следующие контекстные условия: в терме f (t 1 ,. . .,t n) функтор f должен быть n - местным. В атоме (или атомарной формуле) P(t 1 ,. . .,t n) предикат Р должен быть n - местным.

Вхождения переменных в атомарную формулу называются свободными. Свободные вхождения переменных в формулах А и В остаются свободными в формулах А и А В. В формулах x А и x А формула А, как правило имеет, свободные вхождения переменной х. Вхождения переменной х в формулы x А и x А называются связанными. Вхождения других переменных (отличных от x ), которые были свободными в формуле А, остаются свободными и в формулах x А и x А. Одна и та же переменная может иметь в одной и той же формуле как свободные, так и связанные вхождения. Формула, не содержащая свободных вхождений переменных, называется замкнутой.

Например, рассмотрим формулу x (Р(х) y Q(x,y)) и ее подформулы. В подформулу y Q(x,y) переменная х входит свободно, а оба вхождения переменной у связаны (квантором существования). Таким образом, эта подформула не замкнута. С другой стороны, то же самое вхождение переменной х в подформулу Q(x,y) является связанным вхождением в формуле x (Р(х) y Q(x,y)) . В этой формуле все вхождения всех переменных связаны, а потому формула замкнута.

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

Формулы вида А и ┐А, где А - атом, называются литеральными формулами (или литералами). В формулах x А и x А подформула А называется областью действия квантора по х.

Обычно связки и кванторы упорядочивают по приоритету следующим образом: ┐, ,$, &, , . Лишние скобки при этом опускают. Терм t называется свободным для переменной х в формуле А, если никакое свободное вхождение переменной х в формулу А не лежит в области действия никакого квантора по переменной у, входящей в терм t. В частности, терм t свободен для любой переменной в формуле А , если никакая переменная терма не является связанной переменной формулы А.

Например:

а) терм у свободен для переменной х в формуле Р(x) , но тот же терм у не свободен для переменной х в формуле y P{x).

б) терм f(x, z) свободен для переменной х в формуле y P(x,y) Q(x), но тот же терм f(x, z) не свободен для переменной х в формуле

z y P(x,y) Q(x).

Переход от предиката Р(х) к " х Р(х) или $ х Р(х) называется связыванием переменной х , или навешиванием квантора на переменную х , или квантификацией переменной х.

Выражение " х Р(х) и $ х Р(х) не зависят от х и при фиксированных Р и предметного множества М имеет вполне определенные значения, представляя вполне конкретные высказывания относительно всех х в предметной области М.

Возвращаясь к определению предиката можно отметить, что высказывание есть просто нуль местный предикат.

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

Рассмотрим решение некоторых примеров.

Пример 4.4. Пусть N (х) – предикат «х – натуральное число». Рассмотреть варианты навешивания кванторов, интерпретировать и определить их истинность.

Решение. " х N(х) –«все числа натуральные». Это высказывание истинно на любом множестве натуральных чисел и ложно, если М содержит хоть одно ненатуральное число (например, целое отрицательное).

Пример 4.5. Пусть предикат Р(х,у) описывает отношение «х любит у » на множестве людей. Проанализировать варианты навешивания кванторов и дать интерпретацию.

Решение . Используя взаимно однозначное соответствие между отношениями предикатами, можно проиллюстрировать решение схемами (рис. 4.1.).

Рис. 4.1. Иллюстрация влияния кванторов

Интерпретация:

" х $ y Р(х,у) – «для любого х существует у , которого он любит».

$ у " х Р(х,у) – «существует такой у , которого любят все х ».

" х "уР(х,у ) - «все х любят всех у ».

$ х $ у Р(х,у) – « найдется х , который любит кого-то из у » или «найдется человек, который кого-то любит».

$ х " у Р(х,у) – «существует х , который любит всех у ».

" у $ х Р(х,у) – «для любого из у найдется х , который его любит».

Аксиомы (логические): любая система аксиом исчисления высказываний, плюс

P 1: x A(x) A(t),

P 2: A(t) x A(x),

где терм t свободен для переменной х в формуле А.

Правила вывода:

где формула А содержит свободные вхождения переменной х, а формула В их не содержит.

Исчисление предикатов, которое не содержит предметных констант, функторов, предикатов и собственных аксиом, называется чистым. Исчисление предикатов, которое содержит предметные константы и/или функторы и/или предикаты и связывающие их собственные аксиомы, называется прикладным.

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

Соответствие между предикатами, отношениями и функциями

n – местный предикат можно рассматривать как функцию Р (х 1 ,…х n) от n переменных х i Î М i , где М i - предметные области, а РÎВ={0,1}={И,Л}. Таким образом, предикат Р (х 1 ,…х n) является функцией типа Р: М 1 ´М 2 ´… ´М n ®В , или, если предметная область едина для всех переменных, то имеем Р: М n ®В .

Из рассмотренного очевидно, что для любых М и n существует однозначное соответствие между n-местными отношениями R ÍМ n и предикатами Р (х 1 ,…х n) , М n ®В :

Каждому n – местному отношению R соответствует предикат Р (х 1 ,…х n) такой, что Р (а 1 ,…а n)=1, если и только если (а 1 ,…а n)ÎR;

Всякий предикат Р (х 1 ,…х n) определяет отношение R такое, что (а 1 ,…а n)ÎR , если и только если Р (а 1 ,…а n)=1.

При этом R задает область истинности предиката P.

Рассмотрим теперь функцию f (х 1 ,…, х n), f : М n ®M . Тогда можно видеть, что всякой функции f: М n ®M соответствует предикат Р (х 1 ,…х n +1), Р: М n +1 ®В , такой что Р(а 1 ,…а n +1)=1 , если и только если f (а 1 ,…а n)=а n +1 .

Понятие предиката шире понятия функции (см. рис. 4.1.), поэтому обратное соответствие (от (n+1 )-местного предиката к n–местной функции) возможно не всегда, а только для таких предикатов, для которых выполняется условие, связанное с однозначностью функции:

Р(а 1 ,…а n +1)=0 ® ("а¢ n +1 ÎМ|а¢ n +1 ¹а n +1 Р(а 1 ,…а¢ n +1)=0. (4.3.)

Аналогичное соответствие имеется между подмножеством отношений {R¢}Ì{R} и множеством функций {f} . Для этого класса отношений выполняется условие

(а 1 ,…а n +1)ÎR¢ ® ("а¢ n +1 ÎМ|а¢ n +1 ¹а n +1 (а 1 ,…а¢ n +1)ÎR¢). (4.4.)

Пример 4.6. Каким отношениям и функциям соответствуют предикаты, определенные на множестве натуральных чисел?

1. Предикат суммы S: N 3 ®В:

S(х 1 ,х 2 ,х 3)=1 тогда и только тогда, когда х 1 +х 2 =х 3 .

2. Предикат порядка Q:N 2 ®В:

Q (х 1 ,х 2)=1 тогда и только тогда, когда х 1 £х 2 .