10303

что a A, но a C . Но так как B C , то a B . Получили противоречие: a A, a B, но A B .

Если все рассматриваемые в ходе рассуждений множества являются подмножествами некоторого фиксированного множество U , то это множе-

ство называют универсальным множеством или универсом для рассмат-

риваемого набора множеств.

Истинным, строгим или собственным подмножеством множества

A называется такое его подмножество B , что B A и B ¹ A (записывается B A), где – знак строгого включения. По отношению к множеству A пустое множество и само множество A называются несобственными подмножествами множества A.

Рассмотрим следующие три множества A= {0, 1}, B = {{0, 1},2} и

C = {{{0, 1},2},3}. Обратим здесь внимание на следующий факт: AÎB (т.к. множество A является элементом множества B), B C (т.к. множество B является элементом множества C ), но A C (т.к. множество A не является элементом множества C ). Но множество A не является подмножеством множества B(т.к. 0 Aно 0 B ) и множество B не является подмножеством множества C (т.к. 2 B , но 2 C ).

Рассмотрим множество A = {a,b,c}. Для этого множества A = 3 . Най-

дем все его различные подмножества. Таковыми будут: пустое множество Ø, три одноэлементных подмножества {a ,},{b},{c}, три двухэлементных подмножества {a , b}, {a , c}, {b , c}и одно трёхэлементное множество{a,b,c} (само множество A). Т.е. существует всего 8 подмножеств этого множества.

Для произвольного множества A множество всех его подмножеств называется булеаном множества Aи обозначается как S ( A ) или 2 A. Последнее обозначение происходит из того факта, что для конечного множества A = {a1,a2 ,…,a k }, состоящего из k элементов

S ( A ) = 2 A .

Действительно, для k=1,2 в этом легко убедиться. Для k=3 нас убеждает равенство 8=23. Теперь будем рассуждать по индукции. Допустим данное равенство справедливо для множества A = {a1,a2 ,…,a k }, состояще-

го из kэлементов. Покажем его справедливость для множества A1 = {a1,a2 ,…,a k , ak +1}, состоящего из (k+1) элемента. Существует ровно

2k подмножеств этого множества, которые не содержат элемента . Ес-

ли к каждому из таких подмножеств добавить элементak +1 , то получим все подмножества, содержащие элемент ak+1. Таким образом,

172

S(A1) = 2k + 2k = 2k + 1 ,

и, следовательно, приведенное равенство справедливо при любом значении k.

62.3. Алгебраич еские операции над множествам и. Операции над множествами позволяют из имеющегося набора множеств получать другие множества. Наиболее употребительными являются следующие операции.

Объединением множеств A и B называется множ ество, обозначаемое A B, содержащ ее в себе как элементы множества A, так и элементы множестваB.

Пересечением множеств A и B называется множество, обозначаемое A Ç B , состоящее из элементов, входящих одновременнно в A и в B.

Разностью множ еств A и B называется множество, обозначаемое A \ B ,состоящее из элементов множества A, не входящих в множество B.

Симметрической разностью множеств A и B называется множест-

во

AÅ B = (A \ B) È(B \ A) .

Дополнением множества A до универсума U называется множество

A =U \ A.

На рис. 62. 2,а приведены два множества A и B. На рис. 62.2,б-62.2,е заштрихованы результаты соответствующих операций над этими множествами. На рис. 62.2ж- 6 2.2з приведено множество А и его д ополнение до универсума U .

Рис. 62.2

Если AÇ B=Ø, то говорят, что множества A и B не пересекаются.

173

Между введенными операциями существуют определенные взаимозависимости, которые называются законами алгебры множ еств. Среди таковых выделяются так называемые законы де Моргана

A È B = A Ç B и A Ç B = A È B

и свойства дистрибутивности пересечения относительно объединения и

Все эти законы, а также другие соотношения в алгебре множеств могут быть установлены с помощью поэлементной схемы доказательства, заключающейся в проверке принадлежности элементов множеств, стоящих в левой части равенств множествам, стоящим в правой части, и наоборот.

парно не пересекаются, то эта система множеств называется разбиением множества X .

Пусть, например, X ={1,2,3,4,5.6,7,8}. Система множеств

биение множества X . На рис.62.3,а система областей, ограниченных контурами AAA, BBB , CCC , образуют покрытие множества X , а на рис.63.2,b области A, B,C образуют разбиение множества X .

Рис. 62.3

174

62.4. Эквивален тность множеств. Мощность множеств. Множест-

ва A и B. называются эквивалентными, если между их элементами можно установить взаим но однозначное соответствие. Если имеются два конечных множества A = {a1 ,a 2 ,…,a k }и B = {b1 ,b 2 ,…,b k ,состоящие из

одинакового количества элементов, то, поставив в соответствие элементу ai (i=1,2,…, k) из мно жества Aэлемент bi из множества B,мы тем самым устанавливаем взаимно однозначное соответствие между этими множествами. Таким образом, любые два конечных множества, с одержащие одинаковое количество эле ментов, эквивалентны.

Рис. 62.4

На рис. 62.4 установлено взаимно однозначное соответствие между точками числового ин тервала (-1,1) (он нарисован вертикально ) и точками числовой прямой (-∞, +∞). Числу 0 из интервала (-1,1) соответствует число 0 на прямой (-∞,+∞). Положительному числу x1 интервала (-1,1) соответствует положительное число y1 на прямой (-∞,+∞). Отрицательному числу x2 интервала (-1,1) соответствует отрицательное число y2 на прямой (-∞,+∞). Таким образом, множество чисел на интервале (-1,1) эквивалентно множеству чисел на прямой (-∞,+∞).

Под мощностью множества естественно подразум евать количество

Для бесконечн ых множеств понятие мощности о пирается на понятие эквивалентности множеств. Естественно считать два эквивалентных множества равномощ ными. Также естественно считать, что если B A , то мощность множества B меньше или равна мощност и A . Вышеприведенный пример показывает, что множество чисел на интервале (-1,1) равномощно множеству чисел на прямой (-∞,+∞).

175

Говоря, что множество бесконечно, мы имеем в виду, что из него можно взять элемент, два элемента и т.д., причем после каждого такого шага в этом множестве ещё останутся элементы. «Простейшим» среди бесконечных множеств является множество натуральных чисел. Счетным множеством называется всякое множество эквивалентное множеству натуральных чисел N . Иначе говоря, элементы счетного множества A можно перенумеровать натуральными числами или, что то же самое, можно представить в виде последовательности a1 ,a 2 ,…,a k .... .

Множество целых чисел Z является счетным, ибо все целые числа мы можем расположить в виде такой последовательности:

0,1,(-1),2,(-2),…

Нетрудно также понять, что счетными множествами являются множество всех четных положительных (отрицательных) чисел или множество натуральных степеней числа 2. Не так очевиден тот факт, что множество всех рациональных чисел Q также является счетным.

Создатель теории множеств Георг Кантор показал, что мощность булеана любого множества A больше мощности множества A. И таким образом, не существует множества наибольшей мощности. Можно показать, что множество действительных чисел на отрезке (-1,1) эквивалентно бу-

леану множества натуральных чисел и потому не является счетным. Оно называется множеством мощности континуум. Из вышесказанного следует, что множество чисел на всей числовой прямой также является множеством мощности континуум. Такой же мощностью обладают множества точек плоскости или трехмерного пространства.

62.5.Прямое произведение множеств. Прямым (декарто-

вым)произведением множеств A и B называется множество A × B = {( a , b ){a A, b B}, т.е. множество тех и только тех пар, первый элемент которых принадлежит множеству A, а второй множеству B .

Если, к примеру,

A = {a, b, c, d , e, f , g , h}, а B ={1,2,3,4,5.6,7,8},

то A × B совпадает с нумерацией клеток на шахматной доске.

Множество A2 называется декартовым квадратом множества A , а

Это понимается таким образом, что если на плоскости введена декартова

176

система координат, то паре ( x, y) R 2 ставится взаимно однозначно точ-

ка M , имеющая координаты (x, y) . Точно также R3 эквивалентно множеству точек в трехмерном пространстве с введенной декартовой системой координат.

Очевидно, что для конечного множества A верно равенство:

An = An

62.6. Бинарные отношения. Отношение эквивалентности. Пусть имеется множество A. Любое подмножество G A × A называется бинарным отношением, определенным на множестве A . Т.е. бинарное отношение G есть некоторая совокупность пар (x, y) из элементов множе-

ного отношения на множестве действительных чисел является отношение « x ≤ y ». Его можно рассматривать как подмножество тех пар (x, y) из множества R × R , в которых первое число меньше второго или равно второму числу.

Пусть N есть множество натуральных чисел. Будем считать, что

(mod 5).

Бинарные отношения на множестве A могут обладать или не обладать следующими свойствами.

1) Бинарное отношение G называется рефлексивным, если для любого x A справедливо, что xGx .

2)Бинарное отношение G называется симметричным, если из того, что xGy следует, что yGx .

3)Бинарное отношение называется транзитивным, если из того, что xGy и yGz следует, что xGz .

Очевидно, что отношение « x ≤ y » является рефлексивным и тран-

зитивным, но не является симметричным. А вот отношение x = y(mod 5) обладает всеми перечисленными выше свойствами.

177

Бинарное отношение G на A называется отношением эквивалентности, если оно реф лексивно, симметрично и транзити вно. Из приведенного определения следует, что отношение x = y(mod 5) является отношением эквивалентност и, а отношение « x ≤ y » таковым не является.

Рис. 62.5

На рис. 62.5 представлены 2 графа с тремя вершинами. Будем считать, что вершина с номером i находится в отношении G к вершине с номером j, если они соединены дугой. Нетрудно видеть, на втором графе отношение G является отношением эквивалентности, а на первом графе отношение G не является отношением эквивалентности, т.к . не выполняется свойство транзитивно сти: имеем дугу из вершины 1 в в ершину 2, дугу из вершины 2 в вершину 3, но отсутствует дуга из вершины 1 в вершину 3.

Пусть A есть множество точек на плоскости с введенной на ней де-

одном и том же расс тоянии от прямой 2x +3y = 6 . Очевидно, отношение

D есть отношение эквивалентности.

Пусть на множе стве A задано отношение эквивалентности G и а есть некоторый элеме нт из A. Пусть С(a) есть подмножество элементов из A, эквивалентных элементу а. Если множество A\ С(a ) не пусто, то вы-

берем из него элемен т bи образуем подмножество С(b) элементов из

A, эквивалентных элементу b и т.д. до тех пор, пока в оставшейся части множества A не останется ни одного элемента. Полученная система подмножеств является р азбиением множества A и назы вается системой классов эквивалент ности бинарного отношения G .

178

Например, введенное выше отношение x = y(mod 5) разбивает все множество натуральных чисел на 5 классов эквивалентности. Отношение эквивалентности G , определенное вторым графом на рис.62.5, разбивает вершины графа на два подмножества: {1} и {2.3}.

Классом эквивалентности отношения D , веденного выше на плоскости, является любая прямая, параллельная прямой 2x +3y = 6 , и, следовательно, плоскость разбивается на бесконечное число классов эквивалентности.

Пусть A множество студентов некоторой группы. Будем считать, что студент x находится в отношении G к студенту y , если они имеют одну и ту же словесную оценку за экзамен по математике в прошедшей сессии. Очевидно, отношение G есть отношение эквивалентности, и все множество студентов разбивается не более, чем на 4 класса эквивалентности. Если все студенты сдали экзамен на отлично, то вся группа состоит из одного класса эквивалентности.

179

Лекция 63. Элементы математической логики

63.1. Введение. Согласно одному из определений, логика есть анализ методов рассуждений. Изучая эти методы, логика в первую очередь интересуется формой, а не содержанием доводов в том или ином рассуждении. Иначе говоря, логика интересуется лишь одним аспектом рассуждений, а именно, правильно ли делается вывод (заключение) из предварительно проведенных рассуждений, т.е. вытекает ли истинность заключения данного рассуждения из истинности его посылок. Рассмотрим два примера.

1.Все натуральные числа, сумма цифр которых в десятичной записи делится на 9, делятся на 9. Число а делится на 9, следовательно, сумма его цифр делится 9.

2.Все мужчины, пришедшие на презентацию, в красных галстуках. Гоcподин Х в красном галстуке. Следовательно, он пришел на презентацию.

Несмотря на схожесть рассуждений, в первом рассуждении сделанное заключение истинно, а во втором рассуждении сделанное заключение не является истинным.

Математическая логика занимается изучением математических рассуждений. Главная ее цель дать точное и адекватное определение понятия «математическое доказательство». Особый интерес к логике и, прежде всего математической, проявился, когда были открыты парадоксы, т.е. рассуждения, приводящие к противоречиям.

Парадокс лжеца. Некто говорит «Я лгу». Если при этом он лжет, то сказанное им есть ложь и он не лжет. Если же он при этом не лжет, то сказанное им есть истина, и, следовательно, он лжет. В любом случае оказывается ,что он лжет и не лжет одновременно.

Парадокс Бери 1906г. Некоторые фразы русского языка выделяют вполне конкретные натуральные числа. Например, фраза: «Наименьшее четное число» выделяет число 2». Эта фраза содержит менее 50 слогов. Существует лишь конечное число слогов в русском языке. Следовательно, существует лишь конечное число таких фраз русского языка, которые содержат не более пятидесяти слогов. Поэтому с помощью таких фраз можно охарактеризовать только конечное число натуральных чисел. Пусть K

есть наименьшее из натуральных чисел, которые нельзя охарактеризовать никакой фразой русского языка, которая содержит не более 50

слогов. Но нетрудно видеть, что сама эта фраза, которая характеризует число K , содержит менее 50 слогов.

Анализ парадоксов привел к различным планам их устранения. Углубилось исследование языка логики и математики и в результате на стыке логики и математики возникло целое научное направление: «математическая логика». С самыми элементарными понятиями математической логики нам предстоит познакомиться в данной лекции.

180

63.2. Высказывания. Алгебра высказываний. В математической логике основными неопределяемыми являются следующие понятия: высказывание, истина, ложь. Под высказыванием понимается

любое повествовательное предложение, относительно которого можно сказать истинно оно или ложно. Например, высказывание «Студент, сдавший экзаменационную сессию на «отлично», получает повышенную стипендию» есть истинное высказывание; а высказывание «Число 6 делится на 4» есть ложное высказывание.

Пропозициональными переменными, обозначаемыми заглавными латинскими буквами А,В,С,… , будем называть переменные, значениями которых являются произвольные высказывания (истинные или ложные). К высказываниям можно применять те или иные операции. В результате появляются новые высказывания, истинностные значения которых зависят от истинностных значений высказываний, к которым операция применена. Приведем определения наиболее употребительных операций над высказы-

Конъюнкцией двух высказываний А и В называется высказывание, обозначаемое A & B (читается: "А и В''), которое истинно, если истинны оба высказывания A и В, и ложно в остальных случаях (см. таб. 2).

таб. 2

Дизъюнкцией двух высказываний А и В называется высказывание, обозначаемое A B (читается: "А или В''),которое ложно, когда оба высказывания А и В ложны, и истинно, в остальных случаях (см. таб. 3):

таб. 3