Элементы теории множеств

Размещено на http://www.allbest.ru/

1

1. Элементы теории множеств

1.1 Множества, подмножества, элементы множества

В отличие от других объектов, изучаемых математикой, термин "множество" не имеет строгого определения. Этот термин употребляется как синоним понятий совокупность, собрание, коллекция некоторых элементов. Так, можно говорить (а) о множестве пчёл в улье, (б) о множестве точек отрезка, (в) о множестве вершин квадрата или (г) о множествах его сторон и (д) диагоналей, (е) о множестве студентов в аудитории и т.д. В приведённых примерах в случаях (а), (в)-(е) соответствующие множества состоят из определённого конечного числа предметов, такие множества называются конечными. Множество точек отрезка (пример (б)) пересчитать невозможно, такие множества называются бесконечными. Наконец, множество, не содержащее ни одного элемента, называется пустым множеством.

Задаются множества различными способами. Наиболее простая форма задания множества - перечисление его элементов, например А={2, 6, 15} (множество А состоит из трёх элементов - целых чисел 2, 6, 15). Другая часто применяемая форма задания - указание свойств элементов множества, например - множество чисел х, удовлетворяющих указанному условию . множество мощность антидистрибутивность

Множества обычно обозначаются большими буквами А, В, С,…., а их элементы - малыми: а, в, с,… Запись (читается: а принадлежит А) или (читается: А содержит а) означает, что а есть элемент множества А. Записи , , (а не принадлежит А) означает, что а не является элементом множества А. Пустое множество обозначается значком Ш.

Опр.1.1.1. Если каждый элемент множества В является также элементом множества А, множество В называется подмножеством множества А (обозначение - или ).

Согласно этому определению, каждое множество является своим подмножеством (это самое "широкое" подмножество множества). Пустое множество является подмножеством любого множества (это самое "узкое" подмножество). Любое другое подмножество множества А содержит хотя бы один элемент множества А, но не все его элементы. Такие подмножества называются истинными, или собственными подмножествами. Для истинных подмножеств множества А применяется обозначение или . Если одновременно и , т.е каждый элемент множества В принадлежит А, и в то же время каждый элемент А принадлежит В, то А и В, очевидно, состоят из одних и тех же элементов и, следовательно, совпадают. В этом случае применяется знак равенства множеств =: A=B. (Символы называются символами включения).

Размещено на http://www.allbest.ru/

1

Общепринятые обозначения множеств:

N = { 1, 2, 3, …} - множество натуральных чисел;

Z = {… ,-4, -3 -2,- 1, 0, 1, 2, 3, ….} - множество целых чисел;

Q = - множество рациональных чисел.

R - множество вещественных чисел.

Рассмотрим простой пример. Пусть А, В, С - подмножества множества N: А={1, 2, 6, 18}; В={6, 1, 18}; С={2, 18, 6, 1},. В этом случае А = С; и , .

Геометрически множества обычно изображаются как некоторые множества точек плоскости. В любой имеющей смысл задаче обычно рассматриваются подмножества некоторого "наибольшего" множества U, которое называют универсальным множеством. Так, на рис. 1 изображено универсальное множество U и два его подмножества - множества А и В, . Сами картинки типа рис. 1 называются диаграммами Эйлера-Венна.

1.2 Операции над множествами

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

Опр.1.2.1. Пусть даны множества А и В. Их объединением называется множество С, состоящее из элементов, принадлежащих хотя бы одному из множеств А, В.

Объединение множеств обозначается символами "+" и "": . Пусть, например, А={-6, -3, 0, 3, 6} B={0, 2, 4, 6, 8}. Тогда . Геометрически объединение множеств изображено на рис. 2.

Размещено на http://www.allbest.ru/

1

Аналогично определяется объединение большего числа множеств.

Опр.1.2.2. Объединением множеств А1, А2, А3, …, Аn (обозначение называется множество, состоящее из элементов, принадлежащих хотя бы одному из множеств А1, А2, А3, …, Аn.

Свойства операции объединения.

Теор. 1.2.1. Справедливы следующие равенства:

(коммутативность);

(АВ)С=А(ВС) (ассоциативность);

Если , то АВ= А;

А Ш= А.

Док-во. Формулы, подобные формулам 1-2, обычно доказываются так. Берётся элемент, принадлежащий правой части равенства, и доказывается, что он принадлежит левой части. В результате для формулы 1, например, будет доказано, что . Затем берётся элемент, принадлежащий левой части, и доказывается, что он принадлежит правой части равенства; для формулы 1 это будет означать, что . Из включений и следует, что .

Размещено на http://www.allbest.ru/

1

Итак, пусть . Это значит, что либо , либо , либо одновременно и . Во всех трех случаях . Включение доказано. Пусть теперь . Это значит, что либо , либо , либо одновременно и . Во всех трех случаях . Включение доказано. Следовательно, , что и требовалось доказать.

Другой способ доказательства - изобразить левую и правую часть равенства для одних и тех же множеств на диаграммах Эйлера-Венна и убедиться, что они изображают одно и тоже множество. Так, для формулы 1 диаграммы приведены слева.

Задание. Самостоятельно доказать включения соответствующих множеств и изобразить диаграммы для формул 2-4.

Опр.1.2.3. Пересечением множеств А и В называется множество С, состоящее из элементов, принадлежащих одновременно и множеству А, и множеству В. Если множества А и В не имеют общих элементов, их пересечение равно пустому множеству; в этом случае множества А и В называются непересекающимися.

Пересечение множеств обозначается символами "" и "" (знак умножения): или С=АВ. Для примера, приведенного после опр.1.2.1, . Геометрически пересечение множеств представлено на рис. 3.

Размещено на http://www.allbest.ru/

1

Свойства операции пересечения множеств.

Теор. 1.2.2. Справедливы следующие равенства:

(коммутативность);

(АВ) С=А (ВС) (ассоциативность);

Если , то АВ= В;

А Ш= Ш.

Задание. Самостоятельно доказать включения соответствующих множеств и изобразить диаграммы для формул 5-8.

Опр. 1.2.4 пересечения множеств для большего числа множеств: Пересечением множеств А1, А2, А3, …, Аn (обозначение ) называется множество, состоящее из элементов, входящих в каждое из множеств А1, А2, А3, …, Аn.

Теор. 1.2.3. Для операций объединения и пересечения множеств справедливы законы дистрибутивности:

;

.

Док-во: Докажем формулу 9. Пусть . Тогда либо (следовательно, и , т.е. ); либо (следовательно, одновременно, () и (), т.е. ); либо одновременно и (в этом случае можно применить любое из приведённых выше рассуждений). Таким образом, доказано, что .

Пусть . Рассмотрим два случая. 1. Пусть .Тогда . 2. Пусть , но , т.е. одновременно и , и . Это возможно, только если одновременно и , и ; т.е. , откуда следует, что . Включение доказано.

Задание. Самостоятельно доказать формулу 10.

Опр. 1.2.5. Разностью множеств А и В называется множество А\В, содержащее те элементы множества А, которые не принадлежат множеству В.

В опр. 1.2.5 не предполагается, что (рис. 4). Если же , то разность А\В называется дополнением множества В до множества А (рис. 5). Для дополнения множества А до универсального множества U применяется обозначение (рис. 6).

Размещено на http://www.allbest.ru/

1

Теор. 1.2.4. Операции разности и дополнения антидистрибутивны относительно операций объединения и пересечения:

11. ;

.

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

Док-во. Докажем формулу 11. Пусть . Это означает, что и , т.е. , . Следовательно, и , т.е. . Включение доказано.

Пусть . Это означает, что одновременно и (т.е. и ), и (т.е. и ). Так как и , то . Но , следовательно, . Включение доказано. Из справедливости доказанных включений следует справедливость формулы 11.

Задание. Самостоятельно доказать формулу 12 и обобщение формул 11, 12 на большее число множеств:

13. ; 14. .

1.3 Мощность множества

Количество элементов в конечном множестве естественно характеризовать их числом. В этом смысле множество чисел {-2, 0, 3,8} и множество букв {с, х, ф, а} эквивалентны, так как они содержат одинаковое число элементов. Для бесконечных множеств такого простого правила сравнения количеств элементов в них нет; чтобы получить возможность описывать количество элементов в бесконечных множествах, введём следующие определения.

Опр. 1.3.1. Между множествами А и В установлено взаимно-однозначное соответствие, если каждому элементу множества А каким-либо образом сопоставлен единственный элемент множества В, при этом каждому элементу множества В сопоставляется единственный элемент множества А.

Опр. 1.3.2. Множества, между которыми можно установить взаимно-однозначное соответствие, называются равномощными (имеющими одинаковую мощность, эквивалентными). Равномощность множеств обозначается символом "~": А~В.

Так, для приведённых выше множеств взаимно-однозначное соответствие устанавливается соотношениями -2с, 0ф, 3а, 8х. Однако ценность опр. 1.8 эквивалентности множеств заключается в том, что оно применимо к любым, в том числе бесконечным, множествам. Так, рассмотрим множество N натуральных чисел и множество N2={ 2, 4, 6, …} четных чисел. Взаимно-однозначное соответствие между этими множествами устанавливается соотношениями n2n, следовательно, эти множества равномощны: N~N2. Этот пример показывает, что собственное подмножество может быть равномощным всему множеству; естественно, это может быть только для бесконечных множеств.

Соотношение ~ эквивалентности множеств транзитивно: если А~В, В~С, то А~С. Взаимно-однозначное соответствие между элементами а множества А и с множества С устанавливается по цепочке а вс.

Опр. 1.3.4. Множество, эквивалентное множеству натуральных чисел N называется счётным множеством.

Размещено на http://www.allbest.ru/

1

Другими словами, множество счётно, если его элементы можно перенумеровать всеми натуральными числами. Счётны множества N2 чётных натуральных чисел, множество нечётных чисел (соответствие n2n-1), множество всех целых чисел {0,1,2,3,4,…} (соответствие 10, 2-1, 31, 4-2, 52, …; вообще n(n-1)/2 для нечётных n и n-n/2 для чётных n).

Равномощны множества точек любых двух отрезков [a,b] и [c,d] (соответствие можно установить, например, с помощью центрального проектирования; рис. 7). Так же можно доказать равномощность множеств точек любых двух интервалов. Множество точек интервала равномощно множеству точек всей прямой (рис. 8). Сложнее ответить на вопрос, равномощны ли множества точек отрезка и интервала. Положительный ответ на этот вопрос даёт следующая теорема:



Размещено на http://www.allbest.ru/

1

Теор. 1.3.1. Если множество А равномощно подмножеству В1 множества В, а множество В равномощно подмножеству А1 множества А, то множества А и В равномощны.

Опр. 1.3.5. Множество, эквивалентное множеству точек любого отрезка, называется множеством мощности континуум.

Рассмотрим более подробно свойства счётных множеств и множеств мощности континуум.

1.3.1 Счётные множества

1. Любое бесконечное подмножество В счётного множества А также счётно.

Элементы В можно перенумеровать в порядке их следования в А; так как В бесконечно, для нумерации будут использованы все натуральные числа.

2. Объединение конечной или счётной совокупности счётных множеств - счётное множество.

Докажем это утверждение сначала для двух счётных множеств А={a1, a2, a3,…} и В={b1, b2, b3,…}. Выпишем все элементы этих множеств в одну строчку a1, b1, a2, b2, a3, b3,… и сопоставим каждому элементу его номер в этой строчке (если Ш, т.е. какой-то элемент входит и в А, и в В, он получает номер только в первый раз, а во второй раз пропускается). В результате будут пронумерованы все элементы множества , что доказывает его счётность. Также доказывается счётность объединения трёх, четырёх и вообще любого конечного числа счётных множеств. В случае счётного числа счётных множеств {A1, A2, A3, A4, …}способ нумерации может быть, например, таким:

A1={a11, a12, a13, a14,…} A2={a21, a22, a23, a24,…} A3={a31, a32, a33, a34,…} A4={a41, a42, a43, a44,…} …………………………	Нумерация начинается с элемента a11 и продолжается в направлении стрелок, повторяющиеся элементы при этом пропускаются.

3. Множество Q рациональных чисел счётно.

Множество рациональных чисел (чисел вида p/q, где p,q - целые числа, q0) можно представить как объединение счётного числа следующих счётных множеств:

множества Q1 всех целых чисел n=0,1,2,3,….;

множество Q2 всех дробей вида n/2, множество Q3 всех дробей вида n/3,…………….,

множество Qк всех дробей вида n/к, n=0,1,2,3,…..; следовательно, оно счётно.

Задание. Самостоятельно доказать следующие утверждения:

4. Если А={an|nZ} и В={bn|nZ} - счётные множества, то множество всех пар {(an,bк)|n,кZ} - счётно.

5. Множество всех многочленов (произвольных степеней) с рациональными коэффициентами (aiQ) счётно.

6. Алгебраическим числом называется число, которое может быть корнем многочлена с рациональными коэффициентами. Доказать, что множество алгебраических чисел счётно.

7. Множество всех отрезков [a,b] с рациональными концами a, b счётно.

8. Множество взаимно не пересекающихся интервалов (a,b) на оси счётно.

9. Множество точек разрыва монотонной функции счётно.

1.3.2 Множества мощности континуум

Множество мощности континуум несчётно.

Применим метод доказательства от противного. Множество мощности континуум - множество, равномощное множеству точек любого отрезка. Возьмём отрезок [0,1]. Каждой точке х[0,1] сопоставим представление числа х в виде бесконечной десятичной дроби вида х=0, 123…..; это представление единственно, если договориться, что в случаях возможной неоднозначности (число 0,5, например, можно представить и в виде 0,5000000…., и в виде 0,4999999….) применяется представление с периодом, равным нулю. Предположим, что множество точек, а следовательно, и множество таких дробей счётно, т.е. они могут быть пронумерованы, в качестве номера используем верхний индекс:

х(1)=0(1), 1(1)2(1)3(1)…….; х(2)=0(2), 1(2)2(2)3(2)…….; х(3)=0(3), 1(3)2(3)3(3)…….; ……………………………...; х(n)=0(n), 1(n)2(n)3(n)…….; ……………………………….	Построим точку х=0, 123…..[0,1], заведомо не принадлежащую этой последовательности. Возьмём 0=0. В качестве 1 возьмём любую цифру, неравную 1(1) и 9; в качестве 2 - любую цифру, неравную 2(2) и 9 и т.д.; вообще в качестве n возьмём любую цифру, неравную n(n) и 9.

Построенная точка не может входить в последовательность х(1), х(2), х(3),…, х(n),…(х х(n),т.к. (n)n(n))- получено противоречие с предположением о счётности точек отрезка.

Если А - бесконечное множество, В - конечное или счётное множество, то -множество, равномощное А.

Выберем в А счётное подмножество С и пусть D=А\С. Тогда А= DС; АВ= D (СВ). С и В - счётные множества, следовательно, СВ -также счётное множество, т.е. существует взаимно-однозначное соответствие между элементами С и СВ. Применяя это соответствие и тождественное соответствие между элементами множества D, получим взаимно-однозначное соответствие между элементами DС и D (СВ), что означает равномощность множеств А и АВ.

Следует отметить, что из этого свойства непосредственно следует равномощность множеств точек отрезка и интервала.

Задание. Самостоятельно доказать следующие утверждения:

Множество иррациональных чисел имеет мощность континуум.

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

1.3.3 Множества высших мощностей

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

Минимальной мощностью обладает пустое множество. Счётное множество имеет большую мощность, чем любое конечное, континуум - большую мощность, чем счётное. Существуют ли множества большей мощности? Следующая теорема показывает, что для любого множества можно построить более мощное множество.

Теор. 1.3.2. Мощность множества всех подмножеств непустого множества А больше, чем мощность исходного множества А.

Док-во. Мощность множества В подмножеств любого множества А не меньше, чем мощность А (В содержит подмножества, состоящие из одного элемента, мощность множества B1={B1,a| B1,a={a}} таких подмножеств равна мощности множества А в силу взаимно-однозначного соответствия а B1,a). Следовательно, мощность В больше или равна мощности А. Докажем, что мощность В не может быть равна мощности А. Применим доказательство от противного. Предположим, что существует взаимно-однозначное соответствие между элементами А и В, т.е. каждому элементу хА поставлено в соответствие подмножество АхА. Возможны два случая: хАх и хАх. Элементы х, такие, что хАх, будем называть элементами первого типа, элементы х, такие, что хАх, назовём элементами второго типа. Рассмотрим множество С элементов второго типа. В соответствии хАх множеству СВ соответствует элемент хСА. Каков тип элемента хС? хС не может быть элементом первого типа, так как в этом случае должно быть хСС, а С состоит из элементов второго типа. хС не может быть элементом второго типа, так как в этом случае должно быть хСС, а С содержит все элементы второго типа. Полученное противоречие показывает, взаимно-однозначного соответствия между элементами А и В существовать не может, т.е. мощность В больше мощности А.

Задачи.

Доказать:

1. А\(ВС) = (А\В)\С.	6. D=A(B\C) (AB)\CD.
2. А=ВС А\ВС.	7. (A1A2)\(B1B2) (A1\B1)(A2\B2).
3. А\В=С А( ВС).	8. .
4. АВ АВ=А.	9. .
5. АВ АВ=В.

Привести пример таких множеств, что

1. A B(A\B).	3. D=A(B\C), но D(AB)\C.
2. A = BC, но A\BC.	4. (A1A2)\(B1B2) (A1\B1)(A2\B2).

2. Элементы математической логики

2.1 Высказывания и действия над ними

Опр.2.1.1. Утверждение, относительно которого известно, истинно оно или ложно, будем называть высказыванием.

Примеры: (A) число 6 больше числа 2; (B) число 6 меньше или равно числу 2; (C) Волга впадает в Каспийское море; (D) Путин - наш президент; (Е) чтобы хорошо жить, надо хорошо учиться.

Утверждения A, C - истинные высказывания; В - ложное; D - утверждение, истинное в настоящий момент, однако об его истинности через два года мы ничего сказать не можем, такие утверждения мы высказываниями считать не будем; (Е) - не высказывание, так как проверить его истинность невозможно. В дальнейшем мы будем рассматривать в основном математические утверждения, для которых неоднозначности в понимании смысла утверждений возникать не будет.

Итак, высказывание - утверждение, которое или истинно, или ложно (третья возможность исключена); никакое высказывание не может быть одновременно и истинным, и ложным.

Для описания истинности высказываний необходимы два символа - один для истинных высказываний, другой - для ложных. Можно применять буквы "и" и "л"; однако чаще применяются цифры 0 и 1. Именно, ложному высказыванию припишем значение 0, истинному - значение 1. Таким образом, для вышеприведённого примера истинность высказываний A и С равна 1; истинность высказывания B равна 0.

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

Опр.2.1.2. Отрицанием высказывания А (обозначение А; читается: "не А") называется высказывание, которое ложно тогда, когда А - истинно, и истинно, когда А ложно.

Для приведённых примеров В=А.

Опр.2.1.3. Конъюнкцией высказываний А и В (обозначение АВ, читается: А и В) называется высказывание, истинное тогда, когда истинны оба высказывания А и В, и ложное в остальных случаях.

Опр. 2.1.4. Дизъюнкцией высказываний А и В (обозначение АВ, читается: А или В) называется высказывание, истинное тогда, когда истинно хотя бы одно из высказываний А и В, и ложное, если и А и В ложны.

Опр. 2.1.5. Импликацией высказываний А и В (обозначение АВ, читается: из А следует В; если А, то В) называется высказывание, ложное в случае, если А истинно, а В ложно, и истинное в остальных случаях.

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

Рассмотрим простой пример интерпретации введённых операций. Пусть даны высказывания: А="5>3" (истинное); В="10>7" (истинное); С="6<1" (ложное); D="8<0" (ложное). Результаты применения логических операций к этим высказываниям будут таковы:

А (неверно, что "5>3") - ложно; С (неверно, что "6<1") - истинно; АВ ("5>3" и "10>7" (одновременно)) - истинно; АС ("5>3" и "6<1" (одновременно)) - ложно; АС ("5>3" и "6<1" (одновременно)) - ложно; АС ("5>3" или "6<1" (истинно хотя бы одно из этих утверждений)) - истинно; АВ (из А следует В; если А, то В; если"5>3", то "10>7") - истинно;

Таблица истинности операций		АС (из А следует С; если А, то С;
A	B	А	АВ	АВ	АВ	АВ		если"5>3", то "6<1") - ложно; СА (из С следует А; если С, то А; если"6<1", то "5>3") - истинно; АВ (А эквивалентно В; А справедливо тогда и только тогда, когда справедливо В; для А необходимо и достаточно, чтобы выполнялось В; "5>3""10>7") - истинно; АС ("5>3""6<1") - ложно; DС ("8<0""6<1") - истинно.
1	1	0	1	1	1	1
1	0	0	0	1	0	0
0	1	1	0	1	1	0
0	0	1	0	0	1	1

Свойства логических операций.

1. ( А) (А).	7. ((АВ)С) (А(ВС)).
2. ( (АВ)) (АВ).	8. ((АВ)С) ((АС)(ВС)).
3. ( (АВ)) (АВ).	9. ((АВ)С) ((АС)(ВС)).
4. (АВ) (ВА).	10. (АВ) ( АВ).
5. (АВ) (ВА).	11. (АВ) ( В А).
6. ((АВ)С) (А(ВС)).	12. (АВ) (АВ)(ВА).

Док-во. Для доказательства любой из приведённых формул требуется построить таблицы истинности для частей формулы, стоящих слева и справа от символа эквивалентности , для всех значений истинности входящих в формулу высказываний, и показать, что они совпадают. Докажем, например, формулу 8. Таблица истинности:

А	В	С	АВ		(АВ)С		АС	ВС		(АС)(ВС)
0	0	0	0		0		0	0		0
0	0	1	0		0		0	0		0
0	1	0	1		0		0	0		0
0	1	1	1		1		0	1		1
1	0	0	1		0		0	0		0
1	0	1	1		1		1	0		1
1	1	0	1		0		0	0		0
1	1	1	1		1		1	1		1

Значения истинности для левой и правой частей формулы совпадают при любых истинностях входных высказываний, следовательно, левая и правая части формулы действительно эквивалентны. (Отметим аналогию между этой формулой и формулой 10. из раздела "1. Элементы терии множеств").

В дальнейшем мы будем отождествлять высказывание и его значение истинности, т.е. считать, что А = 1, если А - истинно, и А = 0, если А - ложно.

2.2 Кванторы

В этом разделе мы расширим понятие термина "высказывание", чтобы ввести в рассмотрение утверждения вида х>7. Строго говоря, это утверждение не является высказыванием в смысле опр.2.1.1, так как мы не можем сказать, истинно оно или ложно (оно истинно, если, например, x[12,15] и ложно, если x[ 2, 5]). Тем не менее, утверждения, содержащие переменные x, y, z,… с областями возможных значений X, Y, Z,…, обладающие тем свойством, что для каждого набора переменных x X, y Y, z Z,…истинность утверждения может быть установлена, в дальнейшем тоже будем называть высказываниями. Зависимость высказываний А, В, … от переменной x будем обозначать как А(х), В(х),… x X. Подмножество Х(А)Х множества Х такое, что для любого хХ(А) высказывание А(х) истинно, будем называть областью истинности высказывания А (так, для высказывания х>-2, X=[-5, 5] будет Х(А) = (-2, 5]).

Кванторы - логические операции, с помощью которых по некоторому высказыванию А(х) получают новые высказывания, характеризующие область истинности высказывания А(х).

Опр. 2.2.1. Квантором всеобщности (обозначение - ) высказывания А(х), x X, называется логическая операция, имеющая значение "истина", если высказывание А(х) истинно для любого элемента x X, и значение "ложь" в противоположном случае (т.е. в случае, когда хотя бы для одного x X высказывание А(х) ложно).

Формула хХ, А(х) читается как "для любого х, принадлежащего Х, справедливо А(х)"; "все х из Х удовлетворяют условию А(х)" и т.д. Формальное определение квантора всеобщности:

Примеры: высказывание (х[-2,4], x2>-2) - истинно, высказывание (х[-2,4], x2>16) - ложно, высказывание (хN, x2>0) - истинно, высказывание (хR, x2>0) - ложно.

Опр. 2.2.2. Квантором существования (обозначение -) высказывания А(х), x X, называется логическая операция, имеющая значение "истина", если высказывание А(х) истинно хотя бы для одного элемента x X, и значение "ложь" в противоположном случае (т.е. в случае, когда высказывание А(х) ложно для всех x X).

Формула хХ, А(х) читается как "существует (найдётся) (хотя бы один) элемент х, принадлежащий Х, для которого справедливо А(х)". Формальное определение квантора существования:

Примеры: высказывание (х[-2,4], x2 > 20) - ложно, высказывание (х[-2,4], x2 > 10) - истинно, высказывание (хN, x2 = 0) - ложно, высказывание (хR, x2 = 0) - истинно.

Опр. 2.2.3. Квантором существования и единственности (обозначение -!) высказывания А(х), x X, называется логическая операция, имеющая значение "истина", если на множестве X существует элемент x, для которого высказывание А(х) истинно, и такой элемент единственен, и значение "ложь" в противоположном случае (т.е. в случае, когда высказывание А(х) ложно для любого элемента x X либо А(х) истинно более чем для одного элемента x X).

Формула ! хХ, А(х) читается как "существует единственный элемент х, принадлежащий Х, для которого справедливо А(х)”. Формальное определение квантора существования и единственности:

Примеры: высказывание (! х[-2,4], x2 16) - истинно, высказывание (!х[-2,4], x2 > 15) - ложно, высказывание (!хN, x2 1) - истинно, высказывание (!хR, x2 1) - ложно.

Применение кванторов позволяет компактно записывать формулировки теорем, определений и других математических утверждений. Например, теорема о существовании корней квадратного уравнения запишется так:

.

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

Пусть дано определение: "Группа называется хорошей, если любой ()студент этой группы - хороший", требуется построить логически следующее из этого определения новое - определение плохой группы.

Правильный ответ: "Группа называется плохой, если хотя бы один ()студент этой группы - плохой". Этот пример подсказывает следующие правила взаимодействия кванторов существования и единственности с операцией отрицания:

1. (хХ, А(х))хХ, А(х);

2. (хХ, А(х)) хХ, А(х).

Док-во. Докажем первую эквивалентность. Если истинно высказывание (хХ, А(х)) (не для хХ истинно А(х)), то хХ, для которого А(х) ложно, т.е. истинно А(х). Импликация (хХ, А(х)) хХ, А(х) доказана. Если истинно высказывание хХ, А(х) (существует хХ, для которого А(х) ложно), то не для любого хХ истинно А(х), т.е.(хХ, А(х)). Импликация хХ,А(х) (хХ, А(х))доказана. По формуле 12 таблицы Свойства логических операций из доказанных импликаций следует эквивалентность левой и правой частей первой формулы.

Аналогично доказывается вторая формула. Формулы 1 и 2 имеют простой смысл. Именно, если мы хотим опровергнуть утверждение хХ, А(х) (для любого х из Х верно А(х)), достаточно найти хотя бы один х, для которого А(х) неверно: хХ, А(х). Если опровергается утверждение хХ, А(х) "существует х, для которого верно А(х)", необходимо доказать, что А(х) неверно для любого х: хХ, А(х).

Задание. Самостоятельно доказать формулу 2.

Если высказывание А(х) содержит несколько кванторов, то операция отрицания меняет каждый из них. Так, отрицание утверждения "число b есть предел функции f(x) в точке x=a…."

запишется так:

.

2.3 Математические теоремы, их виды и логическая структура

2.3.1 Теоремы прямая, обратная, противоположная

Простейшая форма математической теоремы такова: хХ (А(х)В(х)) (дальше это утверждение будем называть прямой теоремой). Смысл этой записи: если элемент х множества Х имеет свойство А(х) (условие теоремы), то он имеет и свойство В(х) (заключение теоремы). Пусть, для примера, П ={Р1, Р2, Р3, …}- множество точек плоскости. Тогда формулировка теоремы Пифагора будет такова:

{ (Р1П, Р2П, Р3П) Р1Р2Р3=/2 | Р1Р2| 2+| Р2Р3| 2=| Р1Р3| 2}.

Исходя из утверждения хХ (А(х)В(х)) можно построить новые утверждения:

хХ (В(х)А(х)) (обратная теорема);

хХ (А(х) В(х)) (противоположная теорема);

хХ (В(х) А(х)) (теорема, противоположная обратной).

Сформулируем эти утверждения для теоремы Пифагора:

обратная теорема: { (Р1П, Р2П, Р3П) | Р1Р2|2+| Р2Р3|2=| Р1Р3|2 Р1Р2Р3=/2} (если квадрат какой-либо стороны треугольника равен сумме квадратов остальных сторон, то угол, противолежащий этой стороне - прямой) - верное утверждение;

противоположная теорема: { (Р1П, Р2П, Р3П) Р1Р2Р3/2 | Р1Р2|2+| Р2Р3|2| Р1Р3|2} (если какой-либо угол треугольника не прямой ,то квадрат противолежащей стороны не может быть равен сумме квадратов остальных сторон - верное утверждение (следствие теоремы косинусов));

теорема, противоположная обратной: { (Р1П, Р2П, Р3П) | Р1Р2|2+| Р2Р3|2| Р1Р3|2 Р1Р2Р3/2} (если квадрат какой-либо стороны треугольника не равен сумме квадратов остальных сторон, то угол, противолежащий этой стороне, не может быть прямым) - верное утверждение.

Однако если верна прямая теорема, это не означает, что всегда будут верны все остальные. Рассмотрим утверждение: "если десятичная запись натурального числа заканчивается нулем, то это число делится на пять без остатка" . Обратная теорема ("если натуральное число делится на пять без остатка, то десятичная запись этого числа заканчивается нулем") - ложна (число х=15 делится нацело на 5, но не оканчивается нулём). Противоположное утверждение "если десятичная запись натурального числа не заканчивается нулем, то это число не делится на пять без остатка" () тоже ложно (опровергающий пример - х=15). Утверждение, противоположное обратному: "если натуральное число не делится на пять без остатка, то десятичная запись этого числа не может заканчиваться нулем" - истинно. Докажем общее утверждение

Теор. 2.3.1. Теоремы прямая и противоположная обратной, обратная и противоположная попарно либо обе истинны, либо обе ложны.

Док-во. Составим таблицу истинности для высказываний А, В и требуемых импликаций:

А	В	А	В	АВ	ВА	ВА	АВ	Эта таблица является, по существу, подмножеством таблицы Свойства логических операций раздела 2.1. Высказывания и действия над ними. Из неё следуют
1	1	0	0	1	1	1	1
1	0	0	1	0	0	1	1
0	1	1	0	1	1	0	0
0	0	1	1	1	1	1	1

эквивалентности (АВ)( ВА); (ВА) ( АВ), которые и требовалось доказать.

2.3.2 Достаточность и необходимость; существование и единственность

Переведём формулировку теоремы хХ (А(х)В(х)) на термины "необходимо", "достаточно": если для элемента х множества Х истинно утверждение А(х), то истинно и утверждение В(х). Таким образом, свойство В(х) необходимо для выполнения А(х) (если ложно В(х), то не может быть истинно А(х); необходимо целое число делится на 5 без остатка, если его десятичная запись оканчивается нулём). С другой стороны, условие А(х) достаточно для того, чтобы имело место В(х) (равенство последней цифры десятичной записи целого числа нулю достаточно, чтобы это число делилось на 5 без остатка).

В математике часто встречаются теоремы, для которых утверждения А(х) и В(х) имеют совпадающие области истинности и эквивалентны на этих областях: хХ (А(х) В(х) ("для истинности А(х) необходима и достаточна истинность В(х)"; " А(х) истинно тогда и только тогда, когда истиино В(х)"). Как следует из формулы 12. (АВ) (АВ)(ВА) таблицы "Свойства логических операций", в этом случае одновременно должны быть справедливы и прямая, и обратная теоремы ("треугольник прямоугольный тогда и только тогда, когда квадрат какой-либо стороны равен сумме квадратов остальных сторон"). Закономерен вопрос: зачем вводить два свойства (термина, определения) для описания одной и той же сущности? Ответ заключён в приведённом примере: каждое из свойств может лучше описывать ту или иную сторону этой сущности (одно свойство относится к углам, другое - к сторонам).

Особый класс математических теорем образуют теоремы существования. Их структура - хХ А(х) (на множестве Х существует элемент х, для которого верно утверждение А(х)). Пример: если непрерывная на отрезке [a,b] функция f(x) принимает на концах отрезка значения разных знаков, то на [a,b] существует (хотя бы один) корень уравнения f(x)=0 (приведённая на иллюстрации функция имеет три корня). В некоторых случаях принципиальна единственность такого элемента х. Так, при численном решении уравнения f(x)=0 многие итерационные процессы перестают работать, если на [a,b] имеется более одного корня уравнения. Существование единственного корня обеспечит такая формулировка теоремы: "если непрерывная на отрезке [a,b] функция f(x) монотонна и принимает на концах отрезка значения разных знаков, то на [a,b] существует единственный корень уравнения f(x)=0".

Размещено на http://www.allbest.ru/

1

Размещено на http://www.allbest.ru/

1

Структура теорем существования и единственности: !хХ А(х).

2.3.3 Доказательство от противного; метод математической индукции

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

2.3.3.1 Доказательство от противного основано на доказанной нами эквивалентности (АВ)( ВА) (эквивалентны теоремы прямая и противоположная обратной). Пример - известное доказательство того факта, что не может быть рациональным числом (предположим, что =p/q, где p/q - несократимая дробьp2=2 q2 p - чётно, p=2т 4m2=2 q2

q2=2m2 q - чётно - противоречие с предположением о несократимости дроби). Таким образом, для доказательства хХ (А(х)В(х)) мы предполагаем, что истинно утверждение В, доказываем хХ (В(х)А(х)), и противоречие между А(х) и А(х) приводит к выводу В = В.

2.3.3.2 Метод математической индукции часто применяется, если Х=N (или Х - бесконечное подмножество множества N). Доказательство утверждения nN (А(n)В(n)) проводится в два этапа: 1. Доказывается утверждение А(1); 2. Доказывается n1 А(n)А(n+1). Рассмотрим простой пример: доказать, что для любого натурального числа n сумма квадратов целых чисел от 1 до n равна n(n+1)(2n+1)/6:

.

При n =1 равенство справедливо: .

Пусть равенство справедливо для n, докажем что оно справедливо для n+1:

Формула доказана.

2.3.4 Бином Ньютона

Набор элементов , (всего m элементов), выбранных без повторения из множества {a1, a2, a3, …, an}, содержащего n элементов, где называется выборкой объема m из n элементов. Пусть, например, даны выборки {a1, a4}, {a2, a3, a4}, {a3, a2, a4}; все приведенные выборки разные: первые две отличаются количеством элементов, последние две выборки отличаются порядком элементов.

Выборки , в которых учитывается не только набор элементов, но и их порядок, называются размещениями. Число различных возможных размещений из n элементов множества по m (m - объем выборки) обозначается символом . Имеет место формула

Доказательство: если все множество содержит n элементов, то имеется ровно n вариантов выбора одного элемента; при любом выборе первого элемента вариантов выбора второго элемента будет n-1; следовательно, вариантов выбора двух элементов будет n(n-1); вариантов выбора третьего элемента из оставшихся n-2 элементов будет тоже n-2; следовательно, три элемента можно выбрать n(n -1)( n -2) способами; таким образом, для любого числа , получаем

где ; при этом по определению полагается 1!=1, 0!=1.

Выборки, для которых m = n, называются перестановками. Например, {a1, a2, a3}, {a2, a3, a1}, {a3, a1, a2} и т.д. Число перестановок из n элементов обозначается символом Pn, так как

Pn = = n(n - 1)(n - 2) ... (n - n + 1), то Pn = n!

Если учитывается только набор элементов в выборке (независимо от их порядка), то такие выборки называются сочетаниями. Пусть, например, имеются выборки {a1, a2, a3}, {a2, a3, a1},

{a3, a6, a2}; первые две из них получаются друг из друга перестановкой элементов, поэтому как сочетания они не различаются (но различаются как перестановки); две последние выборки содержат разные наборы элементов, поэтому как сочетания они разные. Число сочетаний из n элементов по m обозначим . Если набор содержит n элементов, то из этих элементов можно сделать размещений, при этом каждому размещению соответствует еще Pm - 1 размещение, отличающееся от него только порядком элементов, т.е. тождественные с ним как сочетания. Поэтому , то есть .

Частные случаи: если m = 0, то ; если m = 1, то ; если

m = 2, то ; …; если m = n - 1, то ; если

m = n, то .

Биномом Ньютона называют разложение выражения по степеням a и b (n - натуральное число).

Количество слагаемых в многочлене до приведения подобных членов при увеличении показателя степени на единицу увеличивается в два раза (поэтому общее количество слагаемых до приведения подобных членов будет равно 2n + 1). Когда приводятся подобные члены в многочлене , то определяются по сути количества одинаковых слагаемых, то есть числа сочетаний из n элементов по m (ясно, что ).

До сложения показателей слагаемые в разложении бинома имеют вид: ; каждое слагаемое содержит n множителей. Количество слагаемых, которые содержат множитель m раз совпадает с количеством сочетаний по m из n элементов; такие слагаемые будут иметь вид ; общее число таких слагаемых равно , что приводит к так называемой формуле бинома Ньютона:

Для наглядного представления значений биномиальных коэффициентов применяют таблицу, называемую треугольником Паскаля:

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

Рассмотрим некоторые свойства биномиальных коэффициентов, которые хорошо просматриваются в треугольнике Паскаля:

а). Свойство, используемое при построении треугольника Паскаля:

.

б). Число элементов в строке (в разложении бинома степени n) на единицу больше показателя степени бинома.

в). Сумма биномиальных коэффициентов в любой строке равна 2n, то есть

.

г). , так как .

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

д). Сумма биномиальных коэффициентов, стоящих на четных местах, равна сумме биномиальных коэффициентов, стоящих на нечетныx местах.

е).Каждый элемент строки равен предшествующему, умноженному на коэффициент, равный , то есть . В самом деле,

.

Размещено на Allbest.ru