Лекции Общие понятия математики. Высказывания и операции над ними. Равносильные высказывания

Скачать 0.79 Mb.

Название	Высказывания и операции над ними. Равносильные высказывания
Анкор	Лекции Общие понятия математики.doc
Дата	30.04.2017
Размер	0.79 Mb.
Формат файла
Имя файла	Лекции Общие понятия математики.doc
Тип	Курс лекций #4969
страница	5 из 9

1 2 3 4 5 6 7 8 9

Глава 5. Предикаты и теоремы

§ 1. Предикаты и операции над ними

В математике часто встречаются предложения, содержащие одну или несколько переменных, например: «х + 2 = 7», «город стоит на Волге». Эти предложения не являются высказываниями, т.к. о них нельзя сказать, истинны они или ложны. Однако при подстановке конкретных значений переменной х они обращаются в истинные или ложные высказывания. Так, в первом примере при х = 5 получаем истинное высказывание, а при х = 3 – ложное высказывание.

Определение. Предложение с переменными, которое при конкретных значениях переменных обращается в высказывание, называется высказывательной формой или предикатом.

По числу входящих в предикат переменных различают одноместные, двухместные и т.д. предикаты и обозначают А(х), В(х;у)…

Пример: А(х): «х делится на 2» – одноместный предикат, В(х; у): «прямая х перпендикулярна прямой у» – двухместный предикат.

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

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

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

Так, предикат «х > 2» можно рассматривать на множестве натуральных чисел или действительных чисел.

Каждый предикат А(х), х  Х определяет множество Т  Х, состоящее из элементов, при подстановке которых в предикат А(х) вместо х получается истинное высказывание.

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

Пример. Рассмотрим предикат А(х): «х < 5», заданный на множестве натуральных чисел. Т = {1; 2; 3; 4}.

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

Пусть Т_А – область истинности предиката А(х), Т_В – область истинности предиката В(х).
Определение. Конъюнкцией предикатов А(х) и В(х) называется предикат А(х)  В(х), который истинен для тех и только тех значениях х  Х, для которых оба предиката истинны.

Покажем, что Т_А _ _В = Т_АТ_В.

Доказательство. 1) Пусть а  Т_А _ _В  А(а)  В(а) – истинное высказывание. По определению конъюнкции имеем: А(а) – истинно, В(а) – истинно  а  Т_А  а  Т_В  а  Т_А  Т_В  Т_А _ _В  Т_А  Т_В.

2) Пусть b Т_А  Т_В  b  Т_А  b  Т_В  А(b) – истинно, В(b) – истинно  по определению конъюнкции А(b)  В(b) – истинное высказывание  b  Т_А _ _В  Т_А  Т_В Т_А _ _В.

Т.к. Т_А _ _В  Т_А  Т_В и Т_А  Т_В Т_А _ _В, то по свойству равенства множеств Т_А _ _В = Т_АТ_В, что и требовалось доказать.

Заметим, что полученное правило справедливо и для предикатов, содержащих более одной переменной.

Пример. Рассмотрим предикаты А(х): «х < 10», В(х): «х делится на 3», заданные на множестве натуральных чисел. Найдем область истинности предиката А(х)  В(х): «х < 10 и делится на 3».

Т_А = {1; 2; 3; 4; 5; 6; 7; 8; 9; 10}, Т_В = {3; 6; 9; 12; 15; …}, тогда Т_А _ _В = {3; 6; 9}.
Определение. Дизъюнкцией предикатов А(х) и В(х) называется предикат А(х)  В(х), который истинен для тех и только тех значениях х  Х, для которых истинен хотя бы один из предикатов.

Можно доказать (самостоятельно), что Т_А _ _В = Т_АТ_В.

Пример. Рассмотрим предикаты А(х): «х делится на 2 », В(х): «х делится на 3», заданные на множестве натуральных чисел. Найдем область истинности предиката А(х)  В(х): «х делится на 2 или на 3».

Т_А = {2; 4; 6; 8; 10;…}, Т_В = {3; 6; 9; 12; 15; …}, Т_А _ _В = {2; 3; 4; 6; 8; 9; …}.
Определение. Отрицанием предиката А(х)называется предикат

. Он истинен для тех и только тех значениях х  Х, для которых предикат А(х) ложен и наоборот.

Заметим, что

.
Определение. Импликацией предикатов А(х) и В(х) называется предикат А(х)  В(х) (читают: «Если А(х), то В(х)»). Он обращается в ложное высказывание при тех значениях х  Х, для которых предикат А(х) истинен, а предикат В(х) ложен.

Из определения имеем, что предикат А(х)  В(х) ложен на множестве Т_А 

, а следовательно истинен на дополнении к этому множеству. Воспользовавшись законами операций над множествами, имеем:

.
Контрольные вопросы

Что называется высказывательной формой или предикатом?
Какие различают предикаты по числу входящих в них переменных? Приведите примеры.
Какое множество называют областью определения предиката?
Какое множество называют множеством истинности предиката?
Что называют конъюнкцией предикатов? Докажите равенство, связывающее область истинности конъюнкции предикатов с областями истинности этих предикатов.
Дайте определения дизъюнкции, отрицания, импликации предикатов. Запишите равенства, связывающие области истинности конъюнкции предикатов с областями истинности этих предикатов.

§ 2. Высказывания с кванторами и их отрицания

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

Например, если на множестве натуральных чисел задан предикат А(х): «х – четное число», то подставив вместо переменной число 4, получим истинное высказывание «4 – четное число», а, подставив вместо переменной число 5, получим ложное высказывание «5 – четное число».

Существуют и другие способы получения высказывания из предиката. Подставим перед этим предикатом слово «всякое», получим ложное предложение «Всякое натуральное число – четное». Если же перед предикатом подставим слово «некоторые», то получим истинное высказывание «Некоторые натуральные числа – четные».

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

Высказывание ( х  Х) А (х) выражает свойства всех объектов множества Х.

Выражение «для некоторых х» ( «существует х, такое, что …», «хотя бы один», «найдется») называют квантором существования и обозначают  х.

Высказывание ( х  Х) А (х) выражает существование объектов из данного множества, обладающих определенными свойствами или находящимися в определенном отношении с другими объектами.

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

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

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

Истинность высказывания с квантором существования устанавливается при помощи конкретного примера. Чтобы убедиться в ложности такого высказывания, необходимо провести доказательство.
Выясним, как построить отрицание высказываний, содержащих кванторы. Рассмотрим высказывание: «все натуральные числа – четные». Оно ложно. В этом легко убедиться, приведя контрпример: 5 не является четным числом. Можно перед данным предложением поставить слова «неверно, что». Тогда отрицанием высказывания: «все натуральные числа – четные» будет высказывание «неверно, что все натуральные числа – четные». Оно имеет тот же смысл, что и предложение «некоторые натуральные числа четными не являются».

Вообще если дано предложение ( х) А (х), то его отрицанием будут предложения

и ( х)

, имеющие один и тот же смысл.

Рассмотрим высказывание «некоторые однозначные числа делятся на 10». Оно ложно. Отрицанием данного высказывания будет высказывание «неверно, что некоторые однозначные числа делятся на 10», которое имеет тот же смысл, что и высказывание «все однозначные числа делятся на 10».

Вообще если дано предложение ( х) А (х), то его отрицанием будут предложения

и ( х)

, также имеющие один и тот же смысл.

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

Контрольные вопросы

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

§ 3. Отношение следование и равносильности между предложениями.
Необходимое и достаточное условие

Часто встречаются такие предикаты, что из истинности одного из них следует истинность другого. Например, можно сказать, что из предиката А (х): «число х кратно 9» следует предикат В(х): «число х кратно 3», т.к. мы знаем, что при всех значениях х, при которых истинно утверждение «число х кратно 9» будет и истинно утверждение «число х кратно 3».

Определение. Предикат В (х) следует из предиката А (х), если В (х) обращается в истинное высказывание при всех тех значениях х, при которых истинен предикат А (х).

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

Выясним в каком отношении находятся области истинности предикатов А (х) и В (х).
Т_А = {9; 18; 27; …}, Т_В = {3; 6; 9; 12; 15; 18; …}. Видим, что Т_А Т_В.

Таким образом, А (х)  В (х)  Т_А Т_В.

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

Так, утверждение о том, что если число кратно 9, то оно кратно 3, можно сформулировать так: «кратность числа 9 является достаточным условием кратности числа 3» или «кратность числа 3 является необходимым условием его кратности 9».

Как и любое высказывание, предложение А (х)  В (х) может быть истинным либо ложным. Но так как оно может быть сформулировано в виде «всякое А (х) есть В (х)», то его истинность устанавливается путем доказательства, а то, что оно ложно – с помощью контрпримера.

Рассмотрим два предиката: А (х): «число оканчивается нулем» и В (х): «число делится на 10». Из школьного курса математики известно, что если число оканчивается нулем, то оно делится на 10. Верно и обратное. В этом случае говорят, что предложения А (х) и В (х) равносильны.

Определение. Предикаты А (х) и В (х) равносильны, если из предиката А (х) следует предикат В (х), а из предиката В (х) следует предикат.

Для обозначения отношения равносильности используется знак .

Высказывание А (х)  В (х) можно прочитать так: А (х) равносильно В (х), А (х) тогда и только тогда, когда В (х), А (х) необходимое и достаточное условие для В (х), В (х) необходимое и достаточное условие для А (х).

Заметим, что А (х)  В (х) тогда и только тогда, когда Т_А= Т_В.

Контрольные вопросы

Что значит предикат В (х) следует из предиката А (х)? В каком отношении находятся множества истинности этих предикатов?
В каком случае предикат А (х) будет являться необходимым условием для предиката В (х), достаточным условием для В (х)?
В каком случае предикаты А (х) и В (х) будут равносильны?

§ 4. Строение и виды теорем

Теорема – это высказывание, истинность которого устанавливается посредством рассуждения (доказательства).

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

Рассмотрим теорему: «Если натуральное число делится на 2 и на 3, то оно делится на 6». Условие теоремы: «число делится на 2 и на 3», заключение теоремы: «число делится на 6». Условие и заключение теоремы представляют собой предикаты, заданные на множестве Х натуральных чисел. Данное предложение истинно при всех х из множества Х, следовательно, запись теоремы будет следующей: ( х  Х) А (х)  В (х).

Т.о. в записи теоремы можно выделить 3 части:

1) разъяснительную ( х  Х) – в ней описываются множества объектов, о которых идет речь в теореме;

2) условие теоремы: предикат А (х), заданный на множестве Х;

3) заключение теоремы: предикат В (х), заданный на множестве Х.

Для всякой теоремы вида ( х  Х) А (х)  В (х) можно сформулировать предложения:

обратное данному ( х  Х) В (х)  А (х),

противоположное данному ( х  Х)

,

обратное противоположное данному ( х  Х)

.

Заметим, что эти предложения не всегда является теоремами. Например, предложение, обратное для теоремы «если каждое слагаемое делится на данное число, то и сумма делится на данное число» будет ложным. Оно будет формулироваться так: «Если сумма делится на данное число, то и каждое слагаемое делится на данное число». Чтобы убедиться в том, что оно ложное, можно привести контрпример: 3 + 7 = 10. Сумма 10 делится на 5, но ни одно слагаемое на 5 не делится. Данные предложения будут теоремами только в том случае, если они истинны.

Пример. Рассмотрим предложение: «Если каждое слагаемое – четное число, то и сумма – четное число». В нашем примере предикат А (х): «каждое слагаемое – четное число», В (х): «сумма – четное число». Данное предложение является истинным, поэтому его можно назвать теоремой.

Построим обратное предложение: «Если сумма – четное число, то и каждое слагаемое – четное число». Оно ложное, т.к. можно привести контрпример 8 = 5 + 3.

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

Обратное противоположному предложение: «Если сумма – нечетное число, то хотя бы одно слагаемое – нечетное число». Оно истинно, поэтому оно также является теоремой.
Заметим, что прямое и обратное противоположному предложения всегда имеют одинаковые значения истинности, т.к. имеется равносильность (А  В)  (В  А), называемая законом контрапозиции. Из этого предложения также следует, что предложения, обратное данному и противоположное данному также имеют одинаковые значения истинности. Поэтому, рассматривая их, достаточно доказать (или опровергнуть) какое-нибудь одно, тем самым будет доказано (или опровергнуто) другое.

Если для данное теоремы А (х)  В (х) существует обратная В (х)  А (х), то их можно соединить в одну А (х)  В (х), в формулировке которой будут использоваться слова «необходимо и достаточно», «тогда и только тогда».

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