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

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

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

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

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

Задачи.

Доказать:

1. А\(ВÈС) = (А\В)\С.	6. D=AÈ(B\C) Þ (AÈB)\CÌD.
2. А=ВÈС Þ А\ВÌС.	7. (A1ÈA2)\(B1ÈB2) Ì (A1\B1)È(A2\B2).
3. А\В=С Þ АÌ( ВÈС).	8. .
4. АÍВ Û АÇВ=А.	9. .
5. АÍВ Û АÈВ=В.

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

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") - истинно;