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

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

        Теор. 1.6. Мощность множества всех подмножеств непустого множества А больше, чем мощность исходного множества А.         Док-во. Мощность множества В подмножеств любого множества А не меньше, чем мощность А (В содержит подмножества, состоящие из одного элемента; мощность множества B₁={B_1,a| B_1,a ={a}} таких подмножеств равна мощности А в силу силу взаимно-однозначного соответствия а B_1,a). Докажем, что мощность В не может быть равна мощности А. Применим доказательство от противного. Предположим, что существует взаимно-однозначное соответствие между элементами А и В, т.е. каждому элементу х ∈ А поставлено в соответствие подмножество А_х⊆A. Возможны два случая: х ∈ А _х и хА_х. Элементы х, такие, что х ∈ А_х, будем называть элементами первого типа, элементы х, такие, что хА_х, назовём элементами второго типа. Рассмотрим множество С элементов второго типа. В соответствии х ↔ А_х множеству С ∈ В соответствует элемент x_c ∈ А. Каков тип элемента х_c? х_c не может быть элементом первого типа, так как в этом случае должно быть х_С ∈ С, а С состоит из элементов второго типа. х_С не может быть элементом второго типа, так как в этом случае должно быть х_СС, а С содержит все элементы второго типа. Полученное противоречие показывает, что взаимно-однозначного соответствия между элементами А и В существовать не может, т.е. мощность В больше мощности А.

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

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

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

        Примеры: (A) число 6 больше числа 2; (B) число 6 меньше или равно числу 2; (C) Волга впадает в Каспийское море; (D) Путин - наш президент; (Е) чтобы хорошо жить, надо хорошо учиться.         Утверждения A, C - истинные высказывания; В - ложное; D - утверждение, истинное в настоящий момент, однако об его истинности через два года мы ничего сказать не можем; такие утверждения мы высказываниями считать не будем; (Е) - не высказывание, так как проверить его истинность невозможно. В дальнейшем мы будем рассматривать в основном математические утверждения, для которых неоднозначности в понимании смысла утверждений возникать не будет.         Итак, высказывание - утверждение, которое или истинно, или ложно (третья возможность исключена); никакое высказывание не может быть одновременно и истинным, и ложным.         Для описания истинности высказываний необходимы два символа - один для истинных высказываний, другой - для ложных. Можно применять буквы "и" и "л"; однако чаще применяются цифры 0 и 1. Именно, ложному высказыванию припишем значение 0, истинному - значение 1. Таким образом, для вышеприведённого примера истинность высказываний A и D равна 1; истинность высказывания B равна 0. А") называется высказывание, которое ложно тогда, когда А - истинно, и истинно, когда А ложно.         Для приведённых примеров В = А.

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

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

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

        Опр. 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" или "10>7" (истинно хотя бы одно из этих утверждений)) - истинно.
A	B	А	А∧В	А∨В	А⇒В	А⇔В
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

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