1610915389-9cf4bb28a9b372fd268dec258c2fd2e7 (Кудрявцев 2003 Сборник задач по математическому анализу т1), страница 2

е. х Е А й В, а это означает, что х Е (А О В)'. Таким образом, доказано включение А'ОВ' С (А О В)'. Из включений (А й В)' с лр и В' и А' и В' с (А й В)' следует, что множества (А й В)' и А' О В' состоят нз одних и тех же элементов, т. е. равны. а Пример 2. Группа студентов изучает семь учебных дисциплин. Сколькими способами можно составить расписание занятий на понедельник, если на этот день недели запланированы занятия по четырем дисциплинамГ а Различных способов составления расписания столько, сколько существует чстырсхэлементных упорядоченных подмножеств у семиэлементного множества, т. е, равно числу размещений из семи элементов по четыре элемента.

По формуле (1), полагая в ней п = 7, л = 4, находим Ал 7.6.5 4 = 840. А П р и м е р 3. Сколько шестизначных чисел, кратных пяти, можно составить из цифр 1, 2, 3, 4, 5, 6 при условии, что в числе цифры не повторяютсяГ а Для того чтобы число, составленное из заданных цифр, делилось на 5, необходимо и достаточно, чтобы цифра 5 стояла на последнем месте.

Остальные пить цифр могут стоять на оставшихся пяти местах в любом порндке. Следовательно, искомое число шестизначных чисел, кратных пяти, равно числу перестановок нз пяти элементов, т. е. 5! = 5 4 . 3 . 2 1 = 120. а Э1. Множества. Комбинаторика П р и м е р 4. В чемпионате страны по футболу (высшая лига) участвуют 18 команд, причем каждые две команды встречаются между собой 2 раза. Сколько матчей играется в тсченис сезонаГ А В первом круге состоится столько матчей, сколько существует двухэлементных подмнсакеств у множества, содержащего 18 элементов, т. е.

их число равно С1зз. По формуле (3) находим 18 17 С,з = = 153. 2 Во втором круге играется столько же матчей, поэтому в течение сезона состоится 306 встреч. д ЗАДАЧИ 1. Даны множества А, В, С. С помощью операций объединения и пересечения записать лсножество, состонщес из элементов, принадлежащих: Ц всем трем множествам; 2) хотя бы одному множеству; 3) по крайней мере двум из этих множеств. 2. Доказать, что равенства: 1) А 0 В = В, :2) АГАВ = А; верны тогда и только тогда, когда А С В.

3. Доказать, что равенство А 1 (В 1 С) = (А 1В) О С верно тогда и только тогда, когда .4 о С. 4. Доказать равенство; 1) А'1(А~В) =АйВ: 2) (А1В) 0(В1А) =(.40В) ~(Ар1В); 3) (А '1 В) 1 С = А ~ (В г1 С); 4) (А '1 В) и С = (А й С) 1 (В и С). 5. Доказать, что включение А 1 В С С верно тогда и только тогда, когда А С В с1 С. 6. Доказать, что: 1) Аи(В~С) Э(4иВ)1С; 2) (АСС)~В С(А~В)ис. 7. Определить, в каком отношении (Л С 1', Х З 1', Х = 1') находятся множества Л и У, если: Ц Х=Аь1(В1С), 1 =(Аг1В)~(АиС); 2) Х=(АйВ)1С, 1'=(А~С)й(В~С); 3) Х = А '1 (В О С), 1с = (А '1 В) Г1 (А ~ С).

8. Пусть А и В произвольные подмножества множества 77. Доказать равенство: 1) (А 1В)' = А'Г1В; 2) (АР1В) О(А'Р1 В) = АОВ; 3) (.41о В) П (А'0 В') = А О В. 9. Пусть .4 с Г, В с П. Найти множество Х с С, удовлетворяющее уравнению (ХОА)'О(Хг1А') =В. 10 Гл. 1. Введение 10. Найти подмножества А и В множества С, если известно, что для любого множества Х С сГ верно равенство Х й А = Х 0 В.

11. Пусть А„С С,. в Е Я. Доказать 1) ())А,) = ПА',; 2) ())А,) =))А',. 12. Дана система произвольных множеств А„, в Е И. н ее Ое 1) ПУсть В„= Ц А„п Е И. Доказатеч что О В, = 1) А,. е=1 В=1 б=1 и ее ее 2) Пусть В„= П А„п е И. Доказать, что П В, = П Ал. е=-1 в=1 13. Доказать, что множество является бесконечным тогда и только тогда, когда оно эквивалентно некоторому своему собственному подмножеству. 14. Доказагтч ч1о если мнолшсгво А бесконечное, а множес1во В счетное, то (А 0 В) А. 15.

Доказать, что если А 1,В В 11 А, то А - В. 16. Доказать, что если А С В С С и .4 - С, то А В. 17. Доказать счетность следующих множеств: 1) множества всех чисел вида 21, й Е И; 2) множества всех треугольников па плоскости, вершины которых имеют рациональные координаты; 3) леножества всех точек плоскости с рациональными координатами; 4) множества всех многочленов с рациональными коэффициентами. 18. Доказать, что следующие множества имеют мощность континуума: 1) множество всех точек непустого интервала (а; 5); 2) множество всех последовательностей, составленных из цифр 0 и 1; 3) множество всех последовательностей действительных чисел; 4) множество всех точек квадрата; 5) множество всех точек круга; 6) множество всех подмножеств счетного множества: 7) множество всех счетных подмножеств множества мощности континуума.

19. В группе 30 студентов. Сколькими способами можно выделить двух человек для дежурства, если: 1) один из них должен быть старшим; 2) старшего быть не дол1кноГ 5 д Множества. Комбинаторика 20. На пять сотрудников выделены три путевки. Сколькими способами их можно распределить, если: 1) все путевки различны; 2) все путевки одинаковыГ 21. Сколькиьси способами можно расположить в ряд пять белых и четыре черных шара так, чтобы черные шары не лескали рядомГ Рассмотреть два случая: 1) шары одного цвета неотличимы друг от друга; 2) все шары разные. 22. Сколько диагоналей имеет ныпуклый и-угольникГ 23.

Никакие три диагонали выпуклого деснтиугольника не пересекаютсн в одной точке. Определить число точек пересечения диагоналей. 24. На первой из двух параллельных прямых лежат 15 точек, на второй 21. Сколько сушоствует треугольников с вершинами в втих точкахГ 25. Сколькими способами на шахматной доске можно расставить 8 падей одного цвета, чтобы они не били друг друга и стояли только на черных клеткахГ 26. Из цифр О, 1, 2, 3 составлены всевозможные четырехзначные числа так, что в каждом числе нет одинаковых цифр.

Сколько получилось чиселГ Сколько среди них четных чиселГ 27. Сколько различных десятизначных чисел можно записать, используя цифры 1 и 2Г 28. Сколько различных перестановок можно образовать из букв следующих слов: 1) зебра; 2) баран; 3) водород; 4) абракадабраГ 29. Сколькими способами можно раздать 28 костей домино четырем игрокам так, чтобы каждый получил 7 костейГ 30. Хоккейная команда состоит из 2 вратарей, 7 защитников и 10 нападающих. Сколькими способами тренер может образовать стартовую шестерку, состоящую из вратаря., двух защитников и трех на- падающихГ 31.

Сколько существует шестизначных чисел, все цифры которых нечетны (1, 3, 5, 7, 9)Г 32. Сколько делителей имеет число 462Г 33. На полке стоят гн книг в черных переплетах и и книг в синих переплетах, причем все книги разные. Сколькими способами можно расставить книги так, чтобы книги в черных переплетах стояли рядомГ 34. Сколькими способами можно упаковать 9 разных книг в 5 бандеролей, если 4 бандероли должны содержать по 2 книгиГ Гл. 1. Введение ОТВЕТЫ 7.1) ХЗУ; 2) Х=У; 3) ХС1.

9.Х=В'. 10. А = 17, В = о. 19. 1) 870; 2) 435. 20. 1) 60; 2) 10. 21. 1) 15: 2) 43200. 22. ™ ) . 23. 210. 24. 5355. 25. 576. 26. 18; 10. 27. 1024. 28. 1) 120: 2) 60; 3) 420; 4) 83160. 29. '. 30. 5040. 31. 15625. 32. 16. 33. (и+1)!тгьй 34. 945. (28)! (7!)з 8 2. Элементы логики. Метод математической индукции СПРАВОЧНЫЕ СВЕДЕНИЯ 1. Высказывания. Операции над высказываниями.

1) Под высказыванием понимают вснкое утверждение, о котором имеет смысл говорить, что оно истинно или ложно. Никакое высказывание не может быть одновременно истинным или ложным. Предложение, о котором невозможно однозначно сказать, истинно оно или ложно, высказыванием не является. 2) Из всякого высказывания .4 можно получить новое высказывание, отрицая его, т. е. утверждая, что высказывание А ложно, иначе говоря, не имеет места, не выполняетсн.

Отрицакие высказывании А обозначается символом .4 или ) А. Каково бы ни было высказывание .4, из двух высказываний .4 и .4 одно является истинныьц а другое ложным. 3) Высказывание "истинны оба высказывании А и В" называется конъюнкцией высказываний А и В и обозначаетсн А А В. 4) Высказывание "истинно хоти бы одно из высказываний А и В" называется дизъюккцией высказываний А и В и обозначается А Ч В.

5) Высказывание, полученное из данных высказываний А и В при помаши слоя "если ..., то ...", называют импликацией и обозначают А ь В или .4 з В (читают: если А, то В). Высказывание А называют при этом условием, а высказывание В заключением. Говорят также, что А является достаточным условием длн В, а В является необходимым условием для .4.

Высказывание А ~ В считается ложным только в том случае, когда А истинно, а В ложно. 6) Высказывание, полученное из данных высказываний А и В при помаши слов "тогда и только тогда, когда", называют эквиваленцией или двойной импликацией и обозначают А сь В или А ~-з В. Высказывание А ъз В истинно только тогда, когда либо оба высказывания А н В истинны, либо оба ложны. В этом случае говорят также, что высказывания А и В равносильны и что каждое из них явлиетсн необходимым и достаточным условием другого.

Хй Элементы логики. Метод математическая индукции 2. Предложения, зависящие от переменной. Знаки (символы) общности и существования. 1) Предложение Р(х), зависящее от переменной х, принадлежащей некоторому множеству М (х Е ЛХ), нс являотся, вообще говоря, высказыванием. Например, об истинности предложения Р(х) = (х простое число) ничего нельзя сказать, если не указать число х. Это предложение является истинным при одних значениях х (например, при х = 5, х = 7) и ложным при других значениях х (например, при х, = 8, х = 15). Такие предложения называют неопределенными высказываниями (предикитами). 2) Знак общности у' (перевернутая первая буква английского слова АП вЂ” все) заменяет слова "все", "всякий", "каждый", "любой".

Если Р(х) некоторое неопределенное высказывание, то запись гух Р(х) (или (гух) Р(х)) означает, что для любого элемента х Е ЛХ истинно Р(х), и представляет собой высказывание. Это высказывание истинно, если Р(х) истинно для каждого х Е ЛХ. Чтобы убедиться в ложности высказывания г7х 1'(х), достаточно указать хотя бы один элемент а Е ЛХ, для которого Р(а) - ложное высказывание (найти один противоречащий пример). 3) Знак существования В (перевернутая первая буква английского слова Ех1эга --.

существует) заменяет слова "существует", "найдется". Запись Зх Р(х) представляет собой высказывание; оно истинно, если существует такой элемент а Е ЛХ, для которого Р(и) истинно. В противном случае (если в множестве М нет ни одного элемента а, для которого Р(а) истинно) высказывание Вх Р(х) ложно. 4) Правила построения отрицаний для предложений, содержащих символы гу и В (их в логике называют кваяторами), можно записать гух Е М Р(х) С=> Эхо Е ЛХ Р(хо), (1) Вхо е ЛХ Р(хо) цэ ггх е Л1 Р(т). (2) Таким образом, для построения отрицания предложения, содержащего знаки Ч и Э и утверждение Р, следует знак г' заменить на В, знак Э -- на знак гХ, а утверждение Р -- на его отрицание Р.