Пусть P(x) - предикат определенный на множестве М. Под выражением понимают высказывание, которое является истинным, если существует элемент , для которого P(x) истинно, и ложным – в противном случае. Это высказывание уже не зависит от x. Соответствующее ему словесное выражение звучит так: “Существует x, при котором P(x) истинно.” Символ называют квантором существования. В высказывании переменная x связана этим квантором (на нее навешен квантор).
Кванторные операции применяются и к многоместным предикатам. Пусть, например, на множестве М задан двухместный предикат P(x,y). Применение кванторной операции к предикату P(x,y) по переменной x ставит в соответствие двухместному предикату P(x,y) одноместный предикат (или одноместный предикат ), зависящий от переменной y и не зависящий от переменной x. К ним можно применить кванторные операции по переменной y, которые приведут уже к высказываниям следующих видов:
Рассмотрим предикат P(x) определенный на множестве M={a1,…,an}, содержащем конечное число элементов. Если предикат P(x) является тождественно - истинным, то истинными будут высказывания P(a1),P(a2),…,P(an). При этом истинными будут высказывания и конъюнкция .
Если же хотя бы для одного элемента P(ak)окажется ложным, то ложными будут высказывание и конъюнкция . Следовательно, справедлива равносильность .
3. Численные кванторы.
В математике часто встречаются выражения вида “по меньшей мере n” (“хотя бы n”), “не более чем n”, “n и только n” (“ровно n”), где n – натуральное число.
Эти выражения, называемые численными кванторами, имеют чисто логический смысл; они могут быть заменены равнозначными выражениями, не содержащими числительных и состоящими только из логических терминов и знака или ~, означающего тождество (совпадение) объектов.
Пусть n=1. Предложение “По меньшей мере один объект обладает свойством P” имеет тот же смысл, что и предложение “Существует объект, обладающий свойством P”, т.е. (*)
Предложение “не более чем один объект обладает свойством P” равнозначно предложению “Если есть объекты, обладающие свойством P, то они совпадают”, т.е. (**) Предложение “один и только один объект обладает свойством P” равнозначно конъюнкции вышеуказанных предложений (*) и (**).
Отрицание предложений с кванторами.
Известно, что часто для отрицания некоторого предложения достаточно предпослать сказуемому этого предложения отрицательную частицу “не”. Например, отрицанием предложения “Река х впадает в Черное море.” является предложение “ Река х не впадает в Черное море ”. Годится ли этот прием для построения отрицаний предложений с кванторами? Рассмотрим пример.
Предложения “Все птицы летают ” и “Все птицы не летают ” не являются отрицаниями друг друга, т. к. они оба ложны. Предложения “ Некоторые птицы летают ” и “ Некоторые птицы не летают ” не являются отрицанием друг друга, т. к. они оба истинны. Таким образом, предложения , полученные добавлением частицы “не” к сказуемому предложений “Все х суть Р” и “Некоторые х суть Р” не являются отрицаниями этих предложений. Универсальным способом построения отрицания данного предложения является добавление словосочетания “наверно, что” в начале предложения. Таким образом, отрицанием предложения “Все птицы летают” является предложение “Неверно, что все птицы летают”; но это предложение имеет тот же смысл, что и предложение “Некоторые птицы не летают”. Отрицанием предложения “Некоторые птицы летают” является предложение “Неверно, что некоторые птицы летают”, которое имеет тот же смысл, что и предложение “Все птицы не летают”.
Условимся отрицание предложения записывать как , а отрицание предложения – как . Очевидно, что предложение имеет тот же смысл, а следовательно, то же значение истинности, что и предложение , а предложение – тот же смысл, что . Иначе говоря, равносильно ; равносильно .
Кванторы общности и существования называют двойственными относительно друг друга. Выясним теперь, как строить отрицание предложения, начинающегося с нескольких кванторов, например, такого: .
Последовательно применяя сформулированное выше правило, получим: равносильно , что равносильно , что равносильно .
Упражнения.
№ 1. Какие из следующих выражений являются предикатами:
а) х делится на три (х пробегает множество натуральных чисел);
б) у = х2 (х пробегает множество действительных чисел);
в) х2 + х + 1 = 0 (х пробегает множество действительных чисел);
г) x2+2x+1 (х пробегает множество действительных чисел);
д) х есть мать у (х и у пробегают множество всех людей);
е) х и у (х и у пробегают множество всех людей).
№2. Пусть х, у, z пробегают множество действительных чисел. От какого числа переменных зависят следующие предикаты:
а) х2 + у2 = z2;
б) для всякого х найдется такой у, что х + у = 1;
в) существует z, такое, что для всякого х имеет место неравенство
х + у<z.
№3. Даны два предиката:
Ф1( х): х есть собака;
Ф2(х): х обладает хорошим обонянием (х пробегает множество всех живых существ).
Прочесть символическое выражение ("х)( Ф1(х) ÞФ2(х))
№4. В следующих высказываниях выделить входящие в них предикаты и записать эти высказывания с помощью символики исчисления предикатов:
а) снег белый;
б) я живу в городе Саратове;
в) 2<3;
г) 2·2 = 4;
д) некоторые змеи ядовиты.
№5. Предикаты P1 и Р2 заданы на N высказывательными формами «х — простое число» и «х — четное число». Найдите множество истинности предиката Р, заданного конъюнкцией этих высказывательных форм.
№6. Задайте множество значений переменной так, чтобы на этом множестве данные высказывательные формы были равносильны: а) «х кратно 3»; «х кратно 5»; б) «у — четное число»; «у — простое число»; в) x3—1 = 0; х2+2х-3=0; г) «z —ромб»; «диагонали в z взаимно перпендикулярны».
№7. Определите, равносильны ли на множестве М следующие высказывательные формы: а) , х≠2, М=R; б) , х£2; М=R; в) , х<2; М=R; г) , х£2; М=R; д) « »,«у— составное число»; M=N; е) « », «у — нечетное число»; M=N;
ж) « », « — нечетная функция»; М — множество всевозможных числовых функций числового аргумента; з) хÎ{ }, хÎ{1; 6; 7}; М={1; 2; 3; 4; 5; 6; 7}.
№8. Следующие высказывательные формы замените равносильными им дизъюнкциями:
а) |х + 3| > 3; б) (х — 5)/(х— 1) > 0; в) х2 — 5х + 6 = 0;
г) х2 + у2≠ 0.
№9 Как записать символически равносильность двух уравнений
f1 (х, у) = 0 и f2 (x, у) = 0?
№10. Записать с помощью логической символики, что система уравнений: f1(х, у) = 0 и f2 (x, у) = 0 несовместна (не имеет решений).
№11. Записать с помощью логической символики высказывания:
а) существует точно одно х, такое, что Ф(х);
б) существует по крайней мере два х, таких, что Ф(х);
в) существует не более двух х, таких, что Ф(х).
№12. Записать с помощью логической символики высказывания:
1. Для всех х, удовлетворяющих условию Ф1 (x), имеет место Ф2 (х).
2. Существует х, удовлетворяющий условию Ф1 (x)и такой, что имеет место Ф2(х) .
№13. Определите, следует ли одна высказывательная форма из другой, если M=R:
а) |х]<3; х2—Зх+2=0; б) х4=16; х2=-2; в) х2+х-6=0; (х— 1)(х—2)(х—3) = 0; г) х—1>0; (х—2) (х—5) =0; д) sinx=2; х2 + 5=0; е) х2+5х—6>0; х+1 = 1+х.
4. Приложение математической логики.
4.1. Виды теорем и их взаимосвязь.