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

Пусть 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={a₁,…,a_n}, содержащем конечное число элементов. Если предикат P(x) является тождественно - истинным, то истинными будут высказывания P(a₁),P(a₂),…,P(a_n). При этом истинными будут высказывания и конъюнкция .

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

3. Численные кванторы.

В математике часто встречаются выражения вида “по меньшей мере n” (“хотя бы n”), “не более чем n”, “n и только n” (“ровно n”), где n – натуральное число.

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

Пусть n=1. Предложение “По меньшей мере один объект обладает свойством P” имеет тот же смысл, что и предложение “Существует объект, обладающий свойством P”, т.е. (*)

Предложение “не более чем один объект обладает свойством P” равнозначно предложению “Если есть объекты, обладающие свойством P, то они совпадают”, т.е. (**) Предложение “один и только один объект обладает свойством P” равнозначно конъюнкции вышеуказанных предложений (*) и (**).

Отрицание предложений с кванторами.

Известно, что часто для отрицания некоторого предложения достаточно предпослать сказуемому этого предложения отрицательную частицу “не”. Например, отрицанием предложения “Река х впадает в Черное море.” является предложение “ Река х не впадает в Черное море ”. Годится ли этот прием для построения отрицаний предложений с кванторами? Рассмотрим пример.

Предложения “Все птицы летают ” и “Все птицы не летают ” не являются отрицаниями друг друга, т. к. они оба ложны. Предложения “ Некоторые птицы летают ” и “ Некоторые птицы не летают ” не являются отрицанием друг друга, т. к. они оба истинны. Таким образом, предложения , полученные добавлением частицы “не” к сказуемому предложений “Все х суть Р” и “Некоторые х суть Р” не являются отрицаниями этих предложений. Универсальным способом построения отрицания данного предложения является добавление словосочетания “наверно, что” в начале предложения. Таким образом, отрицанием предложения “Все птицы летают” является предложение “Неверно, что все птицы летают”; но это предложение имеет тот же смысл, что и предложение “Некоторые птицы не летают”. Отрицанием предложения “Некоторые птицы летают” является предложение “Неверно, что некоторые птицы летают”, которое имеет тот же смысл, что и предложение “Все птицы не летают”.

Условимся отрицание предложения записывать как , а отрицание предложения – как . Очевидно, что предложение имеет тот же смысл, а следовательно, то же значение истинности, что и предложение , а предложение – тот же смысл, что . Иначе говоря, равносильно ; равносильно .

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

Последовательно применяя сформулированное выше правило, получим: равносильно , что равносильно , что равносильно .

 

Упражнения.

 

№ 1. Какие из следующих выражений являются предикатами:

а) х делится на три (х пробегает множество натуральных чисел);

б) у = х² (х пробегает множество действительных чисел);

в) х² + х + 1 = 0 (х пробегает множество действительных чисел);

г) x²+2x+1 (х пробегает множество действительных чисел);

д) х есть мать у (х и у пробегают множество всех людей);

е) х и у (х и у пробегают множество всех людей).

№2. Пусть х, у, z пробегают множество действительных чисел. От какого числа переменных зависят следующие предикаты:

а) х² + у² = z²;

б) для всякого х найдется такой у, что х + у = 1;

в) существует z, такое, что для всякого х имеет место неравенство

х + у<z.

№3. Даны два предиката:
Ф₁( х): х есть собака;

Ф₂(х): х обладает хорошим обонянием (х пробегает мно­жество всех живых существ).

Прочесть символическое выражение ("х)( Ф₁(х) ÞФ₂(х))

№4. В следующих высказываниях выделить входящие в них предикаты и записать эти высказывания с помощью символики исчисления предикатов:

а) снег белый;

б) я живу в городе Саратове;

в) 2<3;

г) 2·2 = 4;

д) некоторые змеи ядовиты.

 

№5. Предикаты P₁ и Р₂ заданы на N высказывательными фор­мами «х — простое число» и «х — четное число». Найдите множест­во истинности предиката Р, заданного конъюнкцией этих высказы­вательных форм.

№6. Задайте множество значений переменной так, чтобы на этом множестве данные высказывательные формы были равносильны: а) «х кратно 3»; «х кратно 5»; б) «у — четное число»; «у — простое число»; в) x³—1 = 0; х²+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; в) х² — 5х + 6 = 0;

г) х² + у²≠ 0.

№9 Как записать символически равносильность двух уравнений

f₁ (х, у) = 0 и f₂ (x, у) = 0?

№10. Записать с помощью логической символики, что си­стема уравнений: f₁(х, у) = 0 и f₂ (x, у) = 0 несовместна (не имеет решений).

№11. Записать с помощью логической символики высказывания:

а) существует точно одно х, такое, что Ф(х);

б) существует по крайней мере два х, таких, что Ф(х);

в) существует не более двух х, таких, что Ф(х).

 

№12. Записать с помощью логической символики высказывания:

1. Для всех х, удовлетворяющих условию Ф₁ (x), имеет ме­сто Ф₂ (х).

2. Существует х, удовлетворяющий условию Ф₁ (x)и та­кой, что имеет место Ф₂(х) .

№13. Определите, следует ли одна высказывательная форма из другой, если M=R:

а) |х]<3; х²—Зх+2=0; б) х⁴=16; х²=-2; в) х²+х-6=0; (х— 1)(х—2)(х—3) = 0; г) х—1>0; (х—2) (х—5) =0; д) sinx=2; х² + 5=0; е) х²+5х—6>0; х+1 = 1+х.

 

 

4. Приложение математической логики.

4.1. Виды теорем и их взаимосвязь.