Множества, отображения, логика (стр. 1 )

 

МИНЕСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

государственное образовательное учреждение высшего профессионального образования

«ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ НЕФТЕГАЗОВЫЙ

УНИВЕРСИТЕТ»

 

МНОЖЕСТВА, ОТОБРАЖЕНИЯ, ЛОГИКА

методические указания

к практическим занятиям

для студентов специальностей

ССО, РВ, ИСТ

 

 

 

Тюмень 2005

§ 1. Структура математики

 

Любая теоретическая дисциплина рождается из практики и ею же проверяется, отвечая на три главных вопроса — что? для чего? как? Это относится и к математике, которая имеет: содержание (что?), цель (для чего?) и технологию исследований (как?). Под содержанием понимается триада: Содержание = [множества Å алгоритмы Å логика].

1.1. Математика изучает абстрактные модели с целью установить истинность утверждений не на основании опыта и наблюдения (как это делается в естественных науках), а выводится (дедуцируется) из небольшого числа исходных утверждений. Состав математики порождена триадой:

Состав = [понятия Å утверждения Å доказательства].

1.2. Понятия делятся на неопределяемые понятия, неопределяемые отношения и определяемые понятия. Неопределяемые понятия (например, точка, прямая, плоскость, число) и неопределяемые отношения (например, отношение Î «принадлежать») являются основой для введения определяемых понятий. Они вводятся в математике с помощью определений, которые имеют специальную структуру, удовлетворяющую некоторым требованиям (см. п. 4.21).

1.3. Утверждения делятся на: 1) аксиомы; 2) теоремы; 3) приложения.

1.4. Аксиома — это утверждение, принимаемое без доказательства.[1]

1.5. Теорема доказывается логическим путем с помощью аксиом или уже доказанных теорем.[2] При доказательствах применяются так называемые правила вывода (см. п. 4.19).

1.6. Приложение математической теории может осуществляться в виде готовых формул, теорем или алгоритмов: 1) для решения инженерной задачи, 2) в других науках, 3) внутри самой математики. Первичной же движущей силой существования теорем является практика, конкретная инженерная задача.[3]

1.7. Пример. В теореме: «Если целое число делится (без остатка) на 4, то оно — четное» условием служит предложение А = «целое число делится на 4», заключением — предложение В = «это число — четное». Логическая структура этой теоремы имеет вид: «Если А, то В».■

 

§ 2. Множества

2.1. Краеугольным камнем математики является теория множеств, которую создал Г. Кантор (о нем Д. Гильберт сказал: «Никто и никогда не изгонит нас из его рая»).

2.2. В триаде

Теория множеств = [множества Å элементы Å принадлежность]

 

понятия множество, элемент, принадлежность являются неопределяемыми. Для любого элемента х и любого множества М есть ровно две альтернативы:

либо х принадлежит М (обозначение: хÎМ),

либо х не принадлежит М (обозначение: хÏМ).

Среди множеств особняком стоит пустое множество Æ, которому, по определению, не принадлежит никакой элемент. Это означает, что для любого элемента х следует: хÏÆ.

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

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

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

2.3. Пример. Z2 = {0, 1} — множество всех цифр двоичной системы счисления; при этом 0Î Z2, 1Î Z2, 7Ï Z2; . ■

2.4. Пример.

W = {a, b, g, d, e, z, h, q, i, k, l, m, n, x, o, p, r, s, t, u, j, c, y, w}

— множество всех букв греческого алфавита; .■

2.5. Пример. Z10 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} — множество всех цифр десятичной системы счисления; .■

2.6. Пример. D = {x Î Z10 | x — чётное число} — множество всех чисел х Î Z10, таких, что x — чётное число. В другой записи, D = {0, 2, 4, 6, 8}. Знак | читается «такой, что»; причем слева от него указывается родовой признак (x Î Z10) элементов множества D, а справа записывается их характеристическое свойство — видовое отличие (x — чётное число).■

2.7. Среди множеств особо выделяются стандартные числовые множества, которые обозначаются жирными прямыми заглавными буквами:

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

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

Q = ,  — несократимая дробь} — множество рациональных чисел,

R — множество действительных чисел[4],

С = {x + yi | x, yÎR, i2 = -1} — множество комплексных чисел.

2.8. Множество А, все элементы которого принадлежат и множеству В, называется подмножеством множества В. Это отношение между множествами называют включением и обозначают символом Ì, т.е. А Ì В (А включено, содержится в В) или В É А (В включает, содержит А). Для множеств п. 2.7 справедлива цепочка включений: N Ì Z Ì Q Ì R Ì C.

Любое множество А содержит себя, А Ì А.

Считается, что Æ Ì А для любого множества А.

Если А Ì В и В Ì А, то А = В. Обратно, если А = В, то А Ì В и В Ì А.

Среди подмножеств любого непустого множества А всегда имеется два несобственных подмножества: пустое множество Æ и само множество А. Остальные подмножества называются собственными. Конечные собственные подмножества образуются всевозможными сочетаниями по одному, по два, по три, и т.д. элементов данного множества.

Множество, элементами которого являются все подмножества множества А, называют множеством подмножеств (множеством-степенью) А и обозначают P (A). Так, для множества Z2 из п. 2.3

P (Z2) = {Æ, {0}, {1}, Z2}.

Если А — конечное множество, то | P (A)|= 2|A|. Действительно, пусть n = | A |. Тогда мы можем занумеровать элементы А от 1 до n и каждому подмножеству приписать упорядоченный набор длины n, записанный с помощью двух цифр 0 (если элемент не принадлежит подмножеству) и 1 (если элемент принадлежит подмножеству). Так как разным подмножествам соответствуют различные наборы длины n, то число подмножеств А равно числу таких наборов, т.е. | P (A)|= 2n.

В частности, | P (Æ)|= 2|Æ| =20 = 1.

2.9. Декартовым (прямым) произведением множеств А и В называется множество всех упорядоченных пар вида (х, у), таких, что первый элемент х этой пары принадлежит множеству А, а второй элемент у —множеству В. Декартово произведение множеств А и В обозначается А ´ В (читается «А крест В»):

.

Вообще говоря, А ´ В ¹ В ´ А.

Если В = А, то декартово произведение А ´ А = А2 (читается «А крест А равно А два») двух экземпляров множества А называется декартовым квадратом (второй декартовой степенью) множества А. Обобщая вторую декартову степень, определим любую натуральную декартову степень Аn множества А следующим образом:

.

(Запись  означает, что индекс i принимает все возможные целочисленные значения от 1 до n.) Так, например, множество  называется n-мерным арифметическим пространством; в частности, 1-мерное арифметическое пространство R называется числовой прямой, 2-мерное пространство R2 — числовой плоскостью, 3-мерное пространство R3 — числовым пространством.