Предикаты. Основные понятия. Предикаты: определения и примеры Составить предикат отношения принадлежности произвольной точки

Если попытаться с помощью логики высказываний доказать корректное умозаключение «Каждый человек любит самого себя (Л). Я- человек (В). Следовательно, я люблю самого себя (С)», то общезначимого вывода (А & В) н С не получится. С посылками (А & В) совместимо не только заключение С, но и его отрицание. Значит, высказывание С не является необходимым следствием (А & В). Причина этого не в ущербности логики высказываний, а в ее ограниченности. Согласно одному из ее допущений внутренняя структура простых высказываний не учитывается. Поэтому неудивительно, что расширение возможностей формализации было связано прежде всего с отказом от указанного допущения. Это привело к созданию важного обобщения ЛВ, названного логикой предикатов.

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

Для анализа внутренней структуры высказываний в логике предикатов дополнительно к основным понятиям ЛВ были введены следующие:

• универсум;
• имя собственное;
• предметная константа;
• предметная переменная;
• предикат, терм;
• предметная функция;
• квантор.

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

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

Универсум U логики предикатов - класс объектов с заданными свойствами и отношениями.

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

Чтобы обсуждать вещи универсума, необходимо для каждой из них заручиться именем собственным (обозначает эту и только эту вещь).

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

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

Допущение непустоты универсума - каждому имени собственному должна соответствовать некоторая вещь универсума.

В логике предикатов не важно, каким именем обозначается та или иная вещь, существенно, какая вещь обозначается. Поэтому если два и более различных имени обозначают одну и ту же вещь, то независимо от различия своих интенсионалов (смыслов) они считаются экстенсионально взаимозаменяемыми. Например, «автор “Евгения Онегина”» и «А. С. Пушкин» - экстенсионально взаимозаменяемые имена, так как обозначают одного и того же человека. В противном случае значение истинности высказывания будет зависеть от малейшего изменения смысла контекста, в котором оно употребляется.

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

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

Допущение бивалентности - каждое простое высказывание ЛП

либо истинно, либо ложно.

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

Допустим, задан некоторый универсум U. Относительно любой его вещи ее имя собственное может быть известно или неизвестно. Если оно известно, то данная вещь обозначается одной из строчных начальных букв латинского алфавита а , Ь, с... и называется предметной константой. Значение каждой предметной константы, т. е. обозначаемая ею вещь, фиксировано и не может быть произвольно изменено.

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

Различие между предметными константами и переменными поясняет следующий пример. Допустим, необходимо формализовать утверждение, что некоторая вещь из универсума U обладает свойством Р. Это возможно осуществить двумя способами: либо как Ра, если а - известное имя собственное вещи, либо как Рх, если имя собственное вещи неизвестно. Выражение Ра читается: «Данная вещь а из универсума U обладает свойством Р». Выражение Рх читается так: «Произвольная вещь*из универсума U обладает свойством Р». Фундаментальное различие между обоими случаями состоит в том, что выражения типа Ра, РЬ... можно оценивать как истинные или ложные, а выражения Рх, Ру... так оценивать нельзя.

Пусть U= «пищевые продукты», Р= «сладкий», а =* «сахар», b = «соль». Тогда выражение Ра = «Сахар сладкий» истинно, а выражение РЬ =* «Соль сладкая» ложно. Сказать же, что Рх - «Произвольный пищевой продукт сладкий» истинно или ложно, бессмысленно, потому что неизвестно, о каком же именно пищевом продукте идет речь. Знак * обозначает любую съедобную вещь или, как говорят, «пробегает» по всем вещам рассматриваемого универсума. Значит, чтобы выражение ЛП, содержащее вхождения предметных переменных, можно было интерпретировать как истинное или ложное высказывание, их необходимо заменить соответствующими им предметными константами.

Допустим, необходимо формализовать утверждение, что некоторая вещь находится в определенном отношении к другой вещи. Здесь также различаются указанные выше два случая. Выражение вида Rxy означает «Произвольные вещи лги у из универсума х принято называть одноместными (одноаргументными) предикатами. Их отличительная особенность состоит в том, что они обозначают свойства вещей. Выражения вида Р 2 ху называют двухместными (двухаргументными ) предикатами. Их особенность заключается в том, что они обозначают бинарные отношения. В общем, выражения вида Р п принято называть п-местными предикатами , обозначающими л-местные отношения, п > 0. В случае Р° предикатная буква - знак простого высказывания Л В, которое по допущению бивалентности либо истинно, либо ложно. Так как атомарные формулы ЛВ сводимы к виду Р°, то они все представляют собой атомарные формулы ЛП.

Верхними индексами для обозначения местности предиката можно и не пользоваться, так как число мест предиката легко определяется по числу предметных переменных, которыми он управляет. Например, Р 8 означает, что после предикатной буквы Р должно стоять три предметных переменных - Pxyz. В дальнейшем используется именно данный вариант символизации.

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

Двухместная функция сложения /(а, Ь), определенная на множестве натуральных чисел, устанавливает соответствие между парой определенных натуральных чисел а и Ь и новым числом с из этого же множества как результатом их суммы: а + Ь - с. Например,/(1,2) = 3,/(/(1,2), /(1, 2)) = 3 + 3 = 6. Другие примеры и-иредметных функций: g(b) = = мать b, g(g(b)) = мать матери b = бабушка b, g(g(g(b))) = мать бабушки b = прабабушка Ь. Функция f n при п = 0 обозначает предметную константу.

Предметные константы и предметные переменные принято объединять общим именем - простой терм (от англ. term). Понятие терма обобщает понятие субъекта в традиционной логике. К числу сложных термов относятся «-местные функциональные знаки, п > 0, сопровождаемые «-предметными константами или переменными в качестве простых термов.

Объединение термов с предикатной буквой порождает атомарную формулу ЛП. Основное правило в этом процессе следующее: п-мест- ной предикатной букве должно соответствовать п термов. Таким образом, выражение Л 3 не будет атомарной формулой ЛП, так как предикатный символ не сопровождается тремя термами, а выражение вида РаДгтаковой признать можно. Если?,... t n - произвольные термы, Р" - произвольный «-местный предикат, то атомарная формула ЛП имеет следующий канонический вид: Р а - 1п п>0. Только атомарным формулам ЛП и построенным из них сложным формулам можно приписывать то или иное значение истинности.

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

Пусть универсум состоит из трех вещей, каждая из которых имеет свое собственное имя, U = {а , Ь, с). Если необходимо сказать, что все элементы данного универсума обладают свойством Р, это можно сделать двумя способами. Во-первых, построив конъюнкцию - (Ра & РЬ & Рс), которая истинна, если и только если истинны все ее конъюнкты. Во-вторых, использовав специальное сокращение, называемое квантором общности и ставящееся перед той формулой (Рх - в данном случае), количественную характеристику которой оно определяет: (х)Рх. Формула Рх, перед которой поставлен квантор общности (х)Рх, читается так: «Каждый х обладает свойством Р», «Для всех х имеет место свойство Р». Формула -i(х)Рх читается следующим образом: «Неверно, что каждый х обладает свойством Р». Формула (х)-лРх означает: «Ни один х не обладает свойством Р».

Если необходимо сказать, что некоторые вещи рассматриваемого универсума обладают свойством Р, то это можно сделать также двумя способами. Во-первых, построив дизъюнкцию (Ра v Pbv Рс), которая истинна, если и только если истинен по крайней мере один ее дизъюнкт. Во-вторых, использовав специальное сокращение, называемое квантором существования и ставящееся перед тем выражением, количественную характеристику которого оно определяет: (Ех)Рх. Формула Рх, перед которой поставлен квантор существования (Ех)Рх , читается «Существует такой х , который обладает свойством Р», «По крайней мере для одногох имеет место Р». Формула -i(Ех)Рх читается «Неверно, что существует такой.г, который обладает свойством Р». Формула (Ex)-iPx означает «Некоторые х не обладают свойством Р».

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

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

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

Рассматривается тема логика предикатов на которую отводится 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;

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

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

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

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

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

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

При задании частичного порядка, если пара элементов (a ,b ) принадлежит U , то говорят, что a предшествует b . Если никакой из этих двух элементов другому не предшествует, но говорят, что они не сравнимы.

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

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

Итальянский экономист Вильфредо Парето (1848-1923) предложил использовать в таких задачах конструкцию, которая в его честь называется границей Парето (Pareto frontier). Мы ее сейчас опишем.

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

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

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

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

Например, в рассуждении “Всякий ромб – параллелограмм; АВС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}.

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

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

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

Например, в рассуждении «Всякий ромб – параллелограмм; 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) формула истинна.