Рассмотрим предложение
Это предложение не является высказыванием, так как о нем нельзя сказать, истинно оно или ложно. Оно называется предикатом или условием (на х и у). Приведем другие примеры предложений с переменными:
Есть простое число;
Есть четное число;
Меньше у,
Есть общий делитель у, z.
Будем считать, что допустимыми значениями переменных у и z являются натуральные числа. Если в предложениях заменить переменные их допустимыми значениями, то получатся высказывания, которые могут быть как истинными, так и ложными. Например,
2 есть простое число;
3 есть четное число;
5 меньше 7;
3 есть общий делитель 6 и 12.
ОПРЕДЕЛЕНИЕ. Предложения с переменными, дающие высказывания в результате замены свободных переменных их допустимыми значениями, называются предикатами.
Предложения могут служить примерами предикатов.
По числу входящих свободных переменных различают предикаты одноместные, двухместные, трехместные и т. д. Предикаты (2) и (3) - одноместные, предикаты (1) и (4) - двухместные, предикат (5) - трехместный. Высказывания будем считать нульместными предикатами.
Заменяя в одноместном предикате (2) переменную натуральными числами, будем получать высказывания:
0 есть простое число;
1 есть простое число;
2 есть простое число;
3 есть простое число и т. д.
Некоторые из них являются истинными. Таким образом, данный одноместный предикат выделяет среди натуральных чисел те, при подстановке которых вместо переменной получается истинное высказывание, и его можно рассматривать как условие на значения свободной переменной, входящей в предикат. В данном случае числа, удовлетворяющие этому условию, - простые.
Одноместный предикат можно рассматривать как условие на объекты данного вида; двухместный - как условие на пары объектов данного вида и т. д.
Предикаты можно задавать различными способами. В алгебре часто рассматривают предикаты, заданные с помощью уравнений, неравенств, а также систем уравнений или неравенств. Например, неравенство задает одноместный предикат, уравнение - двухместный, а система уравнений - трехместный у, z - рациональные переменные).
Обозначать предикаты будем большими буквами латинского алфавита (возможно, с нижними индексами) с указанием в скобках всех свободных переменных, входящих в этот предикат. Например, - обозначение двухместного предиката, - трехместного и - обозначение -местного предиката.
В дальнейшем мы будем говорить об истинностном значении произвольного предиката на том или ином наборе входящих в него свободных переменных, понимая под этим истинностное значение высказывания, которое получается в результате замены свободных переменных соответствующими им значениями из рассматриваемого набора.
Высказывание, которое получается при подстановке в предикат набора допустимых значений вместо его переменных, будем обозначать Если это высказывание истинное (ложное), говорят, что набор значений удовлетворяет (не удовлетворяет) предикату
Цель семинара:
Рассмотреть практическое применение логики предикатов.
План занятия:
Рассматривается тема логика предикатов на которую отводится 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}. Здесь предикат становится функцией субъекта и выражает свойство субъекта.
Областью значений предиката является двухэлементное множество B={true, false}. При этом сами переменные x 1 ,...,x n называются предметными переменными, т.е. их значения не являются логическими (не принадлежат множеству B).
Понятие ``предикат"" обобщает понятие ``высказывание"". Неформально говоря, предикат – это высказывание, в которое можно подставлять аргументы. Если аргумент один – то предикат выражает свойство аргумента, если больше – то отношение между аргументами.
Так как значениями предикатов являются true или false, то сами предикаты можно рассматривать как логические переменные. Из них можно составлять сложные логические выражения, образованные из простых предикатов с помощью знаков логических операций. После подстановки в такое составное выражение конкретных значений предметных переменных получается сложное высказывание, значение которого определяется истинностью или ложностью входящих в него простых высказываний и логическими операциями.
Определение 1.Логика предикатов, раздел математической логики, изучающий логические законы, общие для любой области объектов исследования (содержащей хоть один объект) с заданными на этих объектах предикатами (т. е. свойствами и отношениями).
В результате формализации логика предикатов принимает вид различных исчислений. Простейшими логическими исчислениями являются исчисления высказываний. В более сложных исчислениях предикатов описываются логические законы, связывающие объекты исследования с отношениями между этими объектами.
В классическом исчислении предикатов употребляются следующие знаки: 1) т. н. предметные переменные - буквы х, у, z ,..., которые содержательно рассматриваются как неопределённые имена объектов исследования теории; 2) предикатные переменные - знаковые комплексы вида P m , Q n , R l ,... (m, n, l - натуральные числа), причём, например, Q n означает произвольное n-местное отношение между объектами; 3) знаки для логических связок: конъюнкции &, дизъюнкции , импликации É, отрицания ù, означающие соответственно «... и...», «... или...», «если..., то...», «неверно, что...»; 4) знаки для кванторов " (квантор всеобщности), $ (квантор существования), означающие соответственно «для всех...» и «существует... такое, что...»; 5) запятая, скобки (для уточнения строения формул).
Определение 2Квантор (от лат. quantum - сколько), логическая операция, дающая количественную характеристику области предметов, к которой относится выражение, получаемое в результате её применения.
В обычном языке носителями таких характеристик служат слова типа «все», «каждый», «некоторый», «существует», «имеется», «любой», «всякий», «единственный», «несколько», «бесконечно много», «конечное число», а также все количественные числительные. В формализованных языках, составной частью которых является исчисление предикатов, для выражения всех подобных характеристик оказывается достаточным кванторов двух видов: Квантор всеобщности (оборот «для всех х», обозначается через " x, и Квантор существования («для некоторых х», обозначения: $ x.
С помощью кванторов можно записать четыре основных формы суждений традиционной логики: «все А суть В » записывается в виде " x [A (x )É ÉB (x )], «ни одно A не есть B » - в виде " x [A (x )É B (x )], «некоторые А суть B » - в виде $ x [A (x )&B (x )], «некоторые А не суть В » - в виде $ x [A (x )& B (x )] (здесь А (х ) означает, что х обладает свойством A) .
Часть формулы, на которую распространяется действие каких-либо Квантора, называется областью действия этого Квантора (её можно указать с помощью скобок). Применение Квантора уменьшает число свободных переменных в логическом выражении и превращает (если Квантор не «фиктивный», т. е. относится к переменной, действительно входящей в формулу) трёхместный предикат в двухместный, двухместный - в одноместный, одноместный - в высказывание.
Определение 3. Одноместным предикатом Р(x) называется произвольная функция переменной x, определенная на множестве M и принимающая значение из множества {1; 0}.
Определение 4. Множество М, на котором определен предикат Р(x), называется областью определения предиката Р(x).
Множество всех элементов , при которых предикат принимает значения “истина” (1), называется множеством (областью) истинности предиката Р(x), т.е. множество истинности предиката Р(х)- это множество или иначе: или так: Так, например, предикат Р(x) – “x – простое число” определен на множестве N, а множество истинности I P для него есть множество всех простых чисел.
Предикат Q(x) – “sin(x)=0” определен на множестве R, а его множеством истинности является
Предикат F(x) – “диагонали параллелограма x взаимно перпендикулярны” определен на множестве всех параллелограмов, а его множеством истинности является множество всех ромбов.
Из приведенных примеров видим, что одноместные предикаты выражают свойства предметов (субъектов).
Определение 5. Предикат Р(х), определенный на множестве М, называется тождественно истинным , если его множество истинности совпадает с областью определения, т. е. I p =M.
Определение 6. Предикат Р(х), определенный на множестве М, называется тождественно ложным , если его множество истинности является пустым множеством, т. е. I p =0.
Естественным обобщением понятия одноместного предиката является понятие многоместного предиката, с помощью которого выражаются отношениямежду предметами.
Примером бинарного отношения, т. е. отношения между двумя предметами, является отношение “меньше ”. Пусть это отношение введено на множестве Z целых чисел. Оно может быть охарактеризовано высказывательной формой “х Определение 7. Двухместным предикатом Р(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 переменных). Пример п- местного предиката: R(x 1 , x 2 ,…,x n): a 1 x 1 +…+a n x n =0, который, как видим, представляет собой алгебраическое уравнение с n неизвестными. При n=0 будем иметь нульместный предикат
– это логическая (пропозициональная) переменная, принимающая значения из множества {1;0}. Исторически понятие о предикате явилось следствием логического анализа высказываний естественного языка, т. е. выяснения их логической структуры, выяснения того, какой логикой может быть выражен (формализован) смысл этих высказываний. Идея выделения логической структуры речи, в отличие от грамматической, для нужд логической дедукции принадлежит Аристотелю. В аристотелевской и в последующей «традиционной» логике П. понимался в узком смысле как один из двух терминов суждения, а именно тот, в котором нечто говорится о предмете речи - субъекте. Форма сказывания - предикативная связь - сводилась при этом к атрибутивной связи, т. е. выражала «присущность» предмету некоторого признака. Аристотель выделял 4 типа признаков, способных играть роль предиката.: родовые, видовые, собственные и случайные. Это т. н. предикабилии - типы сказуемых. Основой для «функциональной» точки зрения на предикат служат в естественных и в искусственных (точных) языках выражения вида повествовательных предложений, содержащие неопределённые термины - неопределённые имена предметов: переменные (параметры) в записи утверждений в математическом языке, например х
+ 2 = 4; слова «нечто», «некто», «кто-либо» и пр., играющие в естественном языке роль переменных в выражениях типа: «Некто человек», «Кто-то любит кого-то», «Если кто-либо человек, то он смертен» и т.п. Записав эти выражения некоторым единым способом, например заменяя неопределённые термины пробелами, аналогично тому, как это делается в опросных бланках, «-+ 2 = 4», «-человек», «- любит -», «Если - человек, то - смертен», или же принимая запись с помощью переменных в качестве основной, «x + 2 = 4», «x человек», «х
любит у
», «Если х
человек, то х
смертен», легко заметить нечто общее между ними. Во-первых, наличие неопределённых терминов делает эти и подобные им выражения, вообще говоря, неопределёнными как в смысле того, что в них утверждается, так и в смысле их истинностного значения; во-вторых, всякое подходящее указание на область значений неопределённых терминов и одновременная квантификация или замена неопределённых терминов их значениями преобразует соответствующие выражения в осмысленные высказывания. В современной логике выражения, имеющие вид повествовательных предложений и содержащие неопределённые термины, получили общее название пропозициональных функций, или, сохраняя традиционный термин, предикатов. Как и числовые функции, предикаты. являются соответствиями. Неопределённые термины играют в них обычную роль аргументов функции, но, в отличие от числовых функций, значениями предикатов. служат высказывания. В общем случае, отвлекаясь от какого-либо определённого языка и сохраняя только функциональную форму записи, предикат от n
переменных (от n
неопределенных терминов) выражают формулой P
(x 1 ,..., x n
),
где n
³ 0.
При n
= 0 предикат совпадает с высказыванием, при n
= 1 предикат будет свойством в узком смысле (1-местным предикатом), при n
= 2 - свойством «пары» (2-местным предикатом, или бинарным отношением), при n
= 3 -
свойством «тройки» (3-местным предикатом, или тернарным отношением) и т.д. Примеры предикатов:
1.
Возьмём высказывания: `` Сократ - человек "", `` Платон - человек "". Оба эти высказывания выражают свойство ``быть человеком"". Таким образом, мы можем рассматривать предикат `` быть человеком "" и говорить, что он выполняется для С0ократа и Платона. 2. Возьмём высказывание: `` расстояние от Иркутска до Москвы 5 тысяч километров "". Вместо него мы можем записать предикат `` расстояние "" (означающий, что первый и второй аргумент этого предиката находятся на расстоянии, равном третьему аргументу) для аргументов `` Иркутск "", `` Москва "" и `` 5 тысяч километров "". 3. Высказывание "у каждого человека есть отец" можно записать:
"x $
y (человек(x) Éотец(y,x)) 3. Выражение "Джон владеет красной машиной" записывается, например, так: 4. Выражение «все простые числа больше чем x» можно записать " y
(P
(y
) É Q
(x, y
)). , где · P
(x
) выражает условие ``x является простым числом"", · Q
(x, y
) выражает условие ``x меньше чем y"". 5. Выражение "у всех людей общий отец". Понятие предиката Определение 1
Предикат
- утверждение, которое содержит переменные, принимающие значение $1$ или $0$ (истинно или ложно) в зависимости от значений переменных. Пример 1
Например, выражение $x=x^5$ является предикатом, т.к. оно является истинным при $x=0$ или $x=1$ и ложным при всех остальных значениях $x$. Определение 2
Множество, на котором предикат принимает только истинные значения, называется множеством истинности предиката
$I_p$. Предикат называется тождественно-истинным
, если на любом наборе аргументов он принимает истинное значение: $P (x_1, \dots, x_n)=1$ Предикат называется тождественно-ложным
, если на любом наборе аргументов он принимает ложное значение: $P (x_1, \dots, x_0)=0$ Предикат называется выполнимым
, если хотя бы на одном наборе аргументов он принимает истинное значение. Т.к. предикаты могут принимать только два значения (истинно/ложно или $0/1$), то к ним можно применять все операции алгебры логики: отрицание, конъюнкция, дизъюнкция и т.д. Пусть предикат $R(x, y)$: $«x = y»$ обозначает отношение равенства, где $x$ и $y$ принадлежат множеству целых чисел. В этом случае предикат R будет принимать истинное значение для всех равных $x$ и $y$. Другой пример предиката -- РАБОТАЕТ($x, y, z$) для отношения «$x$ работает в городе y в компании $z$». Еще один пример предиката -- НРАВИТСЯ($x, y$) для «x нравится y» для $x$ и $y$, которые принадлежат $M$ -- множеству всех людей. Таким образом, предикатом является все то, что утверждается или отрицается о субъекте суждения. Рассмотрим применение операций алгебры логики к предикатам. Логические операции:
Определение 3
Конъюнкция двух предикатов
$A(x)$ и $B(x)$ -- предикат, который принимает истинное значение при тех и только тех значениях $x$ из $T$, при которых каждый из предикатов принимает истинное значение, а ложное значение -- во всех остальных случаях. Множество истинности $T$ предиката -- пересечение множеств истинности предикатов $A(x)$ и $B(x)$. Например:
предикат $A(x)$: «$x$ -- чётное число», предикат $B(x)$: «$x$ делится на $5$». Таким образом, предикатом будет выражение «$x$ -- чётное число и делится на $5$» или «$x$ делится на $10$». Определение 4
Дизъюнкция двух предикатов
$A(x)$ и $B(x)$ -- предикат, который принимает ложное значение при тех и только тех значениях $x$ из $T$, при которых каждый из предикатов принимает ложное значение и принимает истинное значение во всех остальных случаях. Множество истинности предиката -- объединение областей истинности предикатов $A(x)$ и $B(x)$. Определение 5
Отрицание предиката
$A(x)$ -- предикат, который принимает истинное значение при всех значениях $x$ из $T$, при которых предикат $A(x)$ принимает ложное значение и наоборот. Множество истинности предиката $A(x)$ -- дополнение $T"$ к множеству $T$ в множестве $x$. Определение 6
Импликация предикатов
$A(x)$ и $B(x)$ -- предикат, который является ложным при тех и только тех значениях $x$ из $T$, при которых $A(x)$ -- истинно, а $B(x)$ -- ложно, и принимает истинное значение во всех остальных случаях. Читается: «Если $A(x)$, то $B(x)$». Пример 2
Пусть $A(x)$: «Натуральное число $x$ делится на $3$»; $B(x)$: «Натуральное число $x$ делится на $4$». Составим предикат: «Если натуральное число $x$ делится на $3$, то оно делится и на $4$». Множество истинности предиката -- объединение множества истинности предиката $B(x)$ и дополнения к множеству истинности предиката $A(x)$. Над предикатами помимо логических операций можно выполнять квантовые операции: применение квантора всеобщности, квантора существования и т.д. Определение 7
Кванторы
-- логические операторы, применение которых к предикатам превращает их в ложные или истинные высказывания. Определение 8
Квантор
-- логические операции, которые ограничивают область истинности предиката и создают высказывание. Чаще всего используют кванторы: квантор всеобщности (обозначается символом $\forall x$) -- выражение «для всех $x$» («для любого $x$»); квантор существования (обозначается символом $\exists x$) -- выражение «существует $x$ такое, что... »; квантор единственности и существования (обозначается $\exists !x$) -- выражение «существует точно одно такое $x$, что... ». В математической логике существует понятие связывание
или квантификация
, которые обозначают приписывание квантора к формуле. Пусть -- предикат «$x$ кратно $7$». С помощью квантора всеобщности можно записать следующие ложные высказывания: любое натуральное число делится на $7$; каждое натуральное число делится на $7$; все натуральные числа делятся на $7$; который будет иметь вид: Рисунок 1.
Для записи истинных высказываний используем квантор существования
: существуют натуральные числа, которые делятся на $7$; найдётся натуральное число, которое делится на $7$; хотя бы одно натуральное число делится на $7$. Запись будет иметь вид: Рисунок 2.
Пусть на множестве $x$ простых чисел задан предикат: «Простое число является нечетным». Поставив перед предикатом слово «любое», получим ложное высказывание: «Любое простое число является нечетным» (например, $2$ является простым четным числом). Поставим перед предикатом слово «существует» и получим истинное высказывание: «Существует простое число, которое является нечетным» (например, $x=3$). Таким образом, предикат можно превратить в высказывание, если поставить перед предикатом квантор. Для построения отрицания высказываний, которые содержат кванторы, применяется правило отрицания кванторов
: Рисунок 3.
Рассмотрим предложения и выделим среди них предикаты, указав область истинности каждого из них. Примеры предикатов
Операции над предикатами
Кванторы
Примеры применения кванторов
Операции над кванторами