Лекции Общие понятия математики 14. Элементы теории множеств
 Скачать 0.75 Mb.
|
Глава 2. Математические предложения§ 1. Высказывания и операции над ними. Равносильные высказыванияКогда мы говорим, пишем, то свои мысли выражаем при помощи предложений. Рассмотрим ряд простых повествовательных предложений:
Все эти предложения различны по содержанию, но есть для них нечто общее – в одних предложениях утверждается нечто истинное (правильное, верное), а в других нечто ложное (неправильное, неверное). Так, предложения 1 и 3 считаем истинными, а предложения 2 и 4 ложными. Определение. Повествовательное предложение, о котором можно сказать, истинно оно или ложно, называется высказыванием. Вопросительные, восклицательные предложения высказываниями не являются. Например, предложения «Который час?», «Пусть всегда будет мир!» высказываниями не являются. Предложения, содержащие переменные, которые могут принимать различные значения, тоже не считают высказываниями, т.к. при одних значениях переменных они становятся истинными высказываниями, а при других – ложными. Например, предложение х + 2 < 5 не является высказыванием, т.к. при х = 2 получим истинное предложение, а при х = 7 – ложное предложение. Высказывания могут обозначаться не только с помощью слов, но и с помощью различных символов: 5 · 5 = 25, 7 · 8 < 50, Н2О – вода (первое и третье высказывание являются истинными, а второе – ложным). Условимся обозначать высказывания заглавными буквами латинского алфавита, значение истинного высказывания буквой «И», ложного высказывания – буквой «Л». Уже с первых уроков математики учащиеся начальных классов встречаются с высказываниями, в основном, с истинными, например: 1 < 2, 2 + 3 = 5 и т.д. Позже появляются высказывания о числах двузначных и трехзначных, геометрических фигурах и т.д. Так, выполняя упражнение: «Проверьте, правильно ли выполнено действие: 364 + 287 = 641», требуется установить, истинным или ложным является данное предложение. Легко определить, что оно ложно. Высказывания бывают элементарные (простые) и составные. Определение. Высказывание называется элементарным, если его нельзя расчленить на другие высказывания. Определение. Высказывание называется составным, если его можно расчленить на другие высказывания. Пример. «Число 135 делится на 5.» – элементарное высказывание, а «Число 135 трехзначное и делится на 5.» - составное высказывание. Составные высказывания образуются из элементарных при помощи связок «и», «или», «если, то», «неверно, что», «тогда и только тогда», причем их смысловая характеристика не рассматривается. Допускаются, например, такие высказывания: «Земля вращается вокруг Солнца и параллельные прямые не пересекаются». Операции над высказываниями
Пусть А – некоторое высказывание. Определение. Высказывание «не А» называют отрицанием высказывания А (обозначают  ). Оно истинно, когда высказывание А ложно, и ложно, когда высказывание А истинно.Связь между высказыванием и его отрицанием можно изобразить с помощью таблицы, которую называют таблицей истинности:
Чтобы получить отрицание некоторого высказывания А, можно перед данным высказыванием поставить слова «неверно, что» или к сказуемому добавить частицу «не» (или ее отбросить, если она стоит перед сказуемым в высказывании). Например, если В – высказывание «8 делится на 2», то  – высказывание «неверно, что 8 делится на 2» или «8 не делится на 2».Пусть А – некоторое высказывание. Его отрицание тоже является высказыванием, и, следовательно, можно рассмотреть отрицание высказывания , т.е. высказывание  . Оно называется двойным отрицанием высказывания А. Легко показать, что двойное отрицание высказывания А есть само высказывание А, т.е. отрицая дважды какое-либо высказывание, получаем исходное высказывание.
Определение. Высказывание «А и В» (обозначают А В называют конъюнкцией высказываний А, В (от латинского слова соnjunctio – связываю). Оно истинно тогда и только тогда, когда оба высказывания А, В истинны; если хотя бы одно из высказываний ложно, то и конъюнкция ложна. Из определения следует, что таблица истинности будет такой:
Рассмотрим высказывание «Глазов расположен на севере Удмуртии и является ее столицей». Оно является конъюнкцией двух высказываний «Глазов расположен на севере Удмуртии» и «Глазов является столицей Удмуртии». Первое высказывание истинно, а второе ложно, следовательно, все высказывание будет ложным. Высказывание «2 < 4 и 3 · 3 = 9» является истинным, т.к. истинны оба высказывания, входящие в конъюнкцию. С конъюнкцией двух высказываний мы встречаемся, оперируя двойным неравенством. Так, неравенство 23 < 34 < 45 является конъюнкцией двух высказываний «23 < 34» и «34 < 45», т.е. его можно записать так: «23 < 34 34 < 45» и оно истинно, т.к. истинны оба высказывания, из которых оно составлено.
Определение. Высказывание «А или В» (обозначают А В называют дизъюнкцией высказываний А, В (от латинского слова disjunctio – различаю). Оно ложно тогда и только тогда, когда оба высказывания А, В ложны; если хотя бы одно из высказываний истинно, то и конъюнкция истинна. Из определения следует, что таблица истинности имеет вид:
Высказывание «Стихотворение «Идет бычок, качается» написал Пушкин или Лермонтов» является ложным, т.к. ложны оба элементарные высказывания, в него входящие. Высказывание «2 · 2 = 4 или 2 · 2 = 5» является истинным, т.к. одно из элементарных высказываний «2 · 2 = 4» истинно. Нестрогое неравенство, например, «12 4» представляет собой дизъюнкцию высказываний «12 > 4» и «12 = 4». Поскольку одно из высказываний истинно, то и вся дизъюнкция истинна.
Определение. Высказывание «если А, то В» (обозначают А В) называют импликацией высказываний А, В (от латинского слова implicatio – тесно связываю). Оно ложно тогда и только тогда, когда оба высказывания А истинно, а высказывание В ложно; во всех остальных случаях импликация истинна. Из определения следует, что таблица истинности имеет вид:
Рассмотрим импликацию: «Если 3 < 5, то 7 · 8 = 48». Т.к. условие импликации «3 < 5» истинно, а заключение импликации «7 · 8 = 48» ложно, то все высказывание является ложным. Высказывание «Если 2 · 2 = 5, то Земля – спутник Луны» истинно, т.к. представляет собой импликацию, условие и заключение которой – ложные высказывания.
Определение. Высказывание «А в том и только в том случае, если В» (обозначают А В) называют эквиваленцией высказываний А, В. Оно истинно тогда и только тогда, когда оба высказывания А, В истинны или оба высказывания А, В ложны; если одно из высказываний истинно, а другое ложно, то эквиваленцию считают ложной. Таблица истинности для эквиваленции имеет вид:
Например, высказывание «Число 123 делится на 3 тогда и только тогда, когда сумма его цифр делится на 3» истинно, т.к. оба высказывания истинны. Высказывание «Число 29 делится на 3 в том и только в том случае, когда сумма его цифр делится на 3» является истинным, т.к. оба элементарных высказывания ложные. Высказывание «Число 27 делится на 3 тогда и только тогда, когда последняя цифра числа делится на 3» будет ложным, т.к. высказывание «Число 27 делится на 3» истинно, а высказывание «Последняя цифра числа 27 делится на 3» ложно. Определение. Составные высказывания А и В называются равносильными, если принимают одинаковые значения истинности при любых значениях истинности входящих в них элементарных высказываний (обозначают А В) § 2. Законы алгебры высказываний
А В В А А В В А
А (В С) (А В) С А (В С) (А В) С
А (В С) (А В) (А С) А (В С) (А В) (А С)
А А А
А И И
А Л А
А И8.   9. 
Докажем равенство 10: А В В. Для этого составим таблицу истинности.
Т.к. формулы принимают одинаковые значения истинности при всех наборах значений истинности переменных, то они тождественно равны. Аналогично с помощью таблиц истинности доказываются остальные законы. С помощью таблиц истинности и законов алгебры высказываний можно доказать равносильность составных формул высказываний (смотри рекомендации по решению задач). Контрольные вопросы
§ 3. Предикаты и операции над нимиВ математике часто встречаются предложения, содержащие одну или несколько переменных, например: «х + 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; …}. Определение. Отрицанием предиката А(х)называется предикат  . Он истинен для тех и только тех значениях х Х, для которых предикат А(х) ложен и наоборот.Заметим, что  =  .Определение. Импликацией предикатов А(х) и В(х) называется предикат А(х) В(х) (читают: «Если А(х), то В(х)»). Он обращается в ложное высказывание при тех значениях х Х, для которых предикат А(х) истинен, а предикат В(х) ложен. Из определения имеем, что предикат А(х) В(х) ложен на множестве ТА  , а следовательно истинен на дополнении к этому множеству. Воспользовавшись законами операций над множествами, имеем:  .Контрольные вопросы
§ 4. Высказывания с кванторами и их отрицанияЕсли задан предикат, то, чтобы превратить его в высказывание, достаточно вместо каждой из переменных, входящих в предикат, подставить ее значение. Например, если на множестве натуральных чисел задан предикат А(х): «х – четное число», то подставив вместо переменной число 4, получим истинное высказывание «4 – четное число», а, подставив вместо переменной число 5, получим ложное высказывание «5 – четное число». Существуют и другие способы получения высказывания из предиката. Подставим перед этим предикатом слово «всякое», получим ложное предложение «Всякое натуральное число – четное». Если же перед предикатом подставим слово «некоторые», то получим истинное высказывание «Некоторые натуральные числа – четные». Выражение «для всякого х» в логике называют квантором общности, обозначают х. В математике наряду со словом «всякий» употребляют слова «все», «каждый», «любой». Высказывание ( х Х) А (х) выражает свойства всех объектов множества Х. Выражение «для некоторых х» ( «существует х, такое, что …», «хотя бы один», «найдется») называют квантором существования и обозначают х. Высказывание ( х Х) А (х) выражает существование объектов из данного множества, обладающих определенными свойствами или находящимися в определенном отношении с другими объектами. Таким образом, чтобы превратить предикат в высказывание, достаточно связать квантором общности или существования содержащиеся в нем переменные. Х. Выясним, как установить значение истинности высказываний, содержащих кванторы. Истинность высказываний с квантором общности устанавливается путем доказательства. Нужно убедиться в том, что при подстановке каждого из значений х в предикат последний обращается в истинное высказывание. Если множество Х конечно, то это можно сделать путем перебора всех случаев; если же Х бесконечно, то необходимо провести рассуждение в общем виде. Чтобы убедиться в ложности таких высказываний (опровергнуть их), достаточно привести контрпример. Истинность высказывания с квантором существования устанавливается при помощи конкретного примера. Чтобы убедиться в ложности такого высказывания, необходимо провести доказательство. Выясним, как построить отрицание высказываний, содержащих кванторы. Рассмотрим высказывание: «все натуральные числа – четные». Оно ложно. В этом легко убедиться, приведя контрпример: 5 не является четным числом. Можно перед данным предложением поставить слова «неверно, что». Тогда отрицанием высказывания: «все натуральные числа – четные» будет высказывание «неверно, что все натуральные числа – четные». Оно имеет тот же смысл, что и предложение «некоторые натуральные числа четными не являются». Вообще если дано предложение ( х) А (х), то его отрицанием будут предложения  и ( х) , имеющие один и тот же смысл.Рассмотрим высказывание «некоторые однозначные числа делятся на 10». Оно ложно. Отрицанием данного высказывания будет высказывание «неверно, что некоторые однозначные числа делятся на 10», которое имеет тот же смысл, что и высказывание «все однозначные числа делятся на 10». Вообще если дано предложение ( х) А (х), то его отрицанием будут предложения  и ( х), также имеющие один и тот же смысл.Правило: для того чтобы построить отрицание высказывания с квантором общности (существования), достаточно заменить его квантором существования (общности) и построить отрицание предложения, стоящего после квантора. Контрольные вопросы
§ 5. Отношение следование и равносильности между предложениями. |
,
.