дискретная-математика — Разрешимые множества
Рассмотрим перечислимое, но не разрешимое множество X. Для него существует тотальная вычислимая функция f:N->N такая, что f(N)=X. В качестве B возьмём множество всех нечётных чисел. Оно разрешимо. В качестве A возьмём множество всех чисел вида 2^
В то же время, множество A/B неразрешимо, так как степень двойки 2^k принадлежит этому множеству тогда и только тогда, когда k имеет вид f(n), однако X=f(N) у нас неразрешимо.
§ 1. Множества и операции над ними
Как правило, множества обозначают прописными буквами латинского алфавита. Например, если множество М состоит из чисел 1; 2; 3, то его обозначают так: М = <1; 2; 3>. Тот факт, что число 2 входит в это множество (является элементом данного множества М), записывается с помощью специального значка ∈ следующим образом: 2 ∈ М; а то, что число 5 не входит в это множество (не является элементом данного множества), записывается так: 5 ∉ М.
Можно рассматривать также множество, не содержащее ни одного элемента, — пустое множество.
Например: множество простых делителей числа 1 — пустое множество.
Для некоторых множеств существуют специальные обозначения. Так, пустое множество обозначается символом ∅, множество всех натуральных чисел — буквой N, множество всех целых чисел — буквой Z, множество всех рациональных чисел — буквой Q, а множество всех действительных чисел — буквой R.
Множества бывают конечными и бесконечными в зависимости от того, какое количество элементов они содержат. Так, множества А = <7>и M = <1; 2; 3>— конечные, потому что содержат конечное число элементов, а множества N, Z, Q, R — бесконечные.
Множества задают или с помощью перечисления их элементов (это можно сделать только для конечных множеств), или с помощью описания, когда задается правило (характеристическое свойство), которое позволяет определить, принадлежит или нет данный объект рассматриваемому множеству. Например, А = <–1; 0; 1>(множество задано перечислением элементов), B — множество всех четных целых чисел (множество задано характеристическим свойством всех элементов множества). Последнее множество иногда записывают так: B = или так: B =
В общем виде запись множества с помощью характеристического свойства можно обозначить так: A =
- Равенство множеств. Пусть А — множество всех цифр трехзначного числа 312, то есть A = <3; 1; 2>, а B — множество всех натуральных чисел, меньших четырех, то есть B = <1; 2; 3>. Поскольку эти множества состоят из одних и тех же элементов, то они считаются равными. Это записывают так: A = B. Для бесконечных множеств таким способом (сравнивая все элементы) установить их равенство невозможно. Поэтому в общем случае равенство множеств определяется следующим образом.
Два множества называются равными, если каждый элемент первого множества является элементом второго множества и, наоборот, каждый элемент второго множества является элементом первого множества.
Из приведенного определения равенства множеств следует, что в множестве одинаковые элементы не различаются. Действительно, например, <1; 2; 2>= <1; 2>, поскольку каждый элемент первого множества (1 или 2) является элементом второго множества и, наоборот, каждый элемент второго множества (1 или 2) является элементом первого. Поэтому, записывая множество, чаще всего каждый его элемент записывают только один раз.
- Подмножество
Если каждый элемент множества A является элементом множества B, то говорят, что множество A является подмножеством множества B.
Это записывают следующим образом: A ⊂ B.
Например, <1; 2>⊂ <0; 1; 2; 3>, N ⊂ Z (поскольку любое натуральное число — целое), Z ⊂ Q (поскольку любое целое число — рациональное), Q ⊂ R (поскольку любое рациональное число — действительное).
Полагают, что всегда ∅ ⊆ A, то есть пустое множество является подмножеством любого множества.
Иногда вместо записи A ⊂ B используется также запись A ⊆ B.
Сопоставим определение равенства множеств с определением подмножества. Если множества А и В равны, то: 1) каждый элемент множества А является элементом множества В, следовательно, А — подмножество В (A ⊆ B); 2) каждый элемент множества В является элементом множества А, следовательно, В — подмножество А (B ⊆ A). Таким образом,
два множества равны тогда и только тогда, когда каждое из них является подмножеством другого.
Иногда соотношения между множествами удобно иллюстрировать с помощью кругов (которые часто называют кругами Эйлера–Венна). Например, рисунок 1 иллюстрирует определение подмножества, а рисунок 2 — отношения между множествами N, Z, Q, R.
1 Теория множеств Декартово произведение. Задание Существуют ли такие множества А, В и С, что А ВØ, А С=Ø и (А В)\С=Ø? Определить множества:
Презентация на тему: » 1 Теория множеств Декартово произведение. Задание Существуют ли такие множества А, В и С, что А ВØ, А С=Ø и (А В)\С=Ø? Определить множества:
1 1 Теория множеств Декартово произведение
2 Задание Существуют ли такие множества А, В и С, что А ВØ, А С=Ø и (А В)\С=Ø? Определить множества: \; ; .
3 Задания Из группы студентов на занятия физкультурой ходят 20 человек, а в секции — 18, причем 15 человек одновременно ходят и в секции и на занятия по физкультуре. Сколько студентов освобождены от занятий спортом, если всего в группе 25 человек?
4 Задание Дать геометрическую интерпретацию множества A B\C, если A=<(x,y)| x,y R и |x|4, |y|4>; B=<(x,y)| x,y R, x 2 +y 225>; C=<(x,y)| x,y R и y>0>. Изобразить на координатной прямой множества A B, A B и A B, если: A= и B=, A= и B=.
5 5 Декартово произведение Декартовым или прямым произведением множеств A 1, A 2. A n называется множество <(x 1, x 2. x n )|x 1 A 1, x 2 A 2. x n A n >, обозначаемое через A 1 ×A 2 ×. ×A n. Если A 1 =A 2 =. =A n, то множество A 1 ×A 2. ×A n называется n-ой декартовой степенью множества A и обозначается A n. Положим по определению A 0 =. Если хотя бы одно из множеств A i пусто, то A 1 ×A 2. ×A n =.
6 6 Задание 1 Пусть А – множество точек отрезка [0, 1]; B – множество точек отрезка [2, 3]; C=<4, 5, 6>; D – множество точек квадрата с вершинами в точках (0,0), (0,1), (1,0), (1,1). Найти геометрическую интерпретацию множеств: A×B, A×C, C×B, A×D, C×D, D×B.
7 7 Задание 2 Пусть N= <1,3,7>и M=<0,1,3,4,8>. Из каких элементов состоят множества N×M и M×N? (N×M) (M×N) и (N×M) (M×N)? (N M)×(M N) и (N M)×(M N)? Найти число элементом множества X×Y, если множество X состоит из n элементов, а множество Y из m элементов.
9 9 Задание 4 Определить множества
10 10 Задание 5 Определить множества A и B, если известно, что
11 11 Задание 6 Пусть даны множества A= B=<1,2,3,4,5,6,7,8>. Тогда A×B есть множество клеток шахматной доски. Описать подмножество белых клеток шахматной доски.
12 12 Задание 7 Доказать, что (A×B) (C×D) (A C)×(B D). При каких A, B, C, D включение можно заменить равенством? Доказать, что для произвольных A, B, C, D: (A B)×C=(A×C) (B×C), (A\B)×C=(A×C)\(B×C), A×(B\C)=(A×B)\(A×C), (AB)×(СD)=(A×C)(B×D), A×B=(A×D)(C×B), где A C и B D. Пусть A, B и (A×B) (B×A)=C×D. Доказать, что в этом случае A=B=C=D.
13 13 Задание 8 Доказать, что существуют такие множества А, В и С, что A×BB×A, (А×В)×СА×(В×С). Доказать, что если А, В, С и D непустые, то A B и C D A×C B×D A=B и C=D A×C=B×D
Презентация на тему: » 1 Теория множеств Декартово произведение. Задание Существуют ли такие множества А, В и С, что А ВØ, А С=Ø и (А В)\С=Ø? Определить множества:
1 1 Теория множеств Декартово произведение
2 Задание Существуют ли такие множества А, В и С, что А ВØ, А С=Ø и (А В)\С=Ø? Определить множества: \; ; .
3 Задания Из группы студентов на занятия физкультурой ходят 20 человек, а в секции — 18, причем 15 человек одновременно ходят и в секции и на занятия по физкультуре. Сколько студентов освобождены от занятий спортом, если всего в группе 25 человек?
4 Задание Дать геометрическую интерпретацию множества A B\C, если A=<(x,y)| x,y R и |x|4, |y|4>; B=<(x,y)| x,y R, x 2 +y 225>; C=<(x,y)| x,y R и y>0>. Изобразить на координатной прямой множества A B, A B и A B, если: A= и B=, A= и B=.
5 5 Декартово произведение Декартовым или прямым произведением множеств A 1, A 2. A n называется множество <(x 1, x 2. x n )|x 1 A 1, x 2 A 2. x n A n >, обозначаемое через A 1 ×A 2 ×. ×A n. Если A 1 =A 2 =. =A n, то множество A 1 ×A 2. ×A n называется n-ой декартовой степенью множества A и обозначается A n. Положим по определению A 0 =. Если хотя бы одно из множеств A i пусто, то A 1 ×A 2. ×A n =.
6 6 Задание 1 Пусть А – множество точек отрезка [0, 1]; B – множество точек отрезка [2, 3]; C=<4, 5, 6>; D – множество точек квадрата с вершинами в точках (0,0), (0,1), (1,0), (1,1). Найти геометрическую интерпретацию множеств: A×B, A×C, C×B, A×D, C×D, D×B.
7 7 Задание 2 Пусть N= <1,3,7>и M=<0,1,3,4,8>. Из каких элементов состоят множества N×M и M×N? (N×M) (M×N) и (N×M) (M×N)? (N M)×(M N) и (N M)×(M N)? Найти число элементом множества X×Y, если множество X состоит из n элементов, а множество Y из m элементов.
9 9 Задание 4 Определить множества
10 10 Задание 5 Определить множества A и B, если известно, что
11 11 Задание 6 Пусть даны множества A= B=<1,2,3,4,5,6,7,8>. Тогда A×B есть множество клеток шахматной доски. Описать подмножество белых клеток шахматной доски.
12 12 Задание 7 Доказать, что (A×B) (C×D) (A C)×(B D). При каких A, B, C, D включение можно заменить равенством? Доказать, что для произвольных A, B, C, D: (A B)×C=(A×C) (B×C), (A\B)×C=(A×C)\(B×C), A×(B\C)=(A×B)\(A×C), (AB)×(СD)=(A×C)(B×D), A×B=(A×D)(C×B), где A C и B D. Пусть A, B и (A×B) (B×A)=C×D. Доказать, что в этом случае A=B=C=D.
13 13 Задание 8 Доказать, что существуют такие множества А, В и С, что A×BB×A, (А×В)×СА×(В×С). Доказать, что если А, В, С и D непустые, то A B и C D A×C B×D A=B и C=D A×C=B×D
1 1 Теория множеств Декартово произведение
2 Задание Существуют ли такие множества А, В и С, что А ВØ, А С=Ø и (А В)\С=Ø? Определить множества:
3 Задания Из группы студентов на занятия физкультурой ходят 20 человек, а в секции — 18, причем 15 человек одновременно ходят и в секции и на занятия по физкультуре. Сколько студентов освобождены от занятий спортом, если всего в группе 25 человек?
4 Задание Дать геометрическую интерпретацию множества A B\C, если A=<(x,y)| x,y R и |x|4, |y|4>; B=<(x,y)| x,y R, x 2 +y 225>; C=<(x,y)| x,y R и y>0>. Изобразить на координатной прямой множества A B, A B и A B, если: A=
5 5 Декартово произведение Декартовым или прямым произведением множеств A 1, A 2. A n называется множество <(x 1, x 2. x n )|x 1 A 1, x 2 A 2. x n A n >, обозначаемое через A 1 ×A 2 ×. ×A n. Если A 1 =A 2 =. =A n, то множество A 1 ×A 2. ×A n называется n-ой декартовой степенью множества A и обозначается A n. Положим по определению A 0 =. Если хотя бы одно из множеств A i пусто, то A 1 ×A 2. ×A n =.
6 6 Задание 1 Пусть А – множество точек отрезка [0, 1]; B – множество точек отрезка [2, 3]; C=<4, 5, 6>; D – множество точек квадрата с вершинами в точках (0,0), (0,1), (1,0), (1,1). Найти геометрическую интерпретацию множеств: A×B, A×C, C×B, A×D, C×D, D×B.
7 7 Задание 2 Пусть N= <1,3,7>и M=<0,1,3,4,8>. Из каких элементов состоят множества N×M и M×N? (N×M) (M×N) и (N×M) (M×N)? (N M)×(M N) и (N M)×(M N)? Найти число элементом множества X×Y, если множество X состоит из n элементов, а множество Y из m элементов.
9 9 Задание 4 Определить множества
10 10 Задание 5 Определить множества A и B, если известно, что
11 11 Задание 6 Пусть даны множества A=
12 12 Задание 7 Доказать, что (A×B) (C×D) (A C)×(B D). При каких A, B, C, D включение можно заменить равенством? Доказать, что для произвольных A, B, C, D: (A B)×C=(A×C) (B×C), (A\B)×C=(A×C)\(B×C), A×(B\C)=(A×B)\(A×C), (AB)×(СD)=(A×C)(B×D), A×B=(A×D)(C×B), где A C и B D. Пусть A, B и (A×B) (B×A)=C×D. Доказать, что в этом случае A=B=C=D.
13 13 Задание 8 Доказать, что существуют такие множества А, В и С, что A×BB×A, (А×В)×СА×(В×С). Доказать, что если А, В, С и D непустые, то A B и C D A×C B×D A=B и C=D A×C=B×D