Банк задач по математике

Задача 1

Найти все подмножества следующих множеств: $\varnothing ,\left\{ \varnothing \right\} ,\left\{ 1,2,3\right\}$ , $\left\{ a, \left\{ 1,2\right\} , \varnothing \right\}$ .

?

Задача 2

Пусть $A=\left\{ 0,1\right\} , B=\left\{ a, b, c\right\}$ . Найти множества $A \times B$ и $B \times A$ .

?

Задача 3

(а)(б)

Доказать следующие включения:

?

(а)

$A \cap B \subseteq A \subseteq A \cup B$ ;

(б)

$A \backslash B \subseteq A$ .

Задача 4

Доказать следующие тождества для любых множеств $A, B, C$ :

?

(а)

$A \cup A=A \cap A=A$ ;

(б)

$A \cap (B \cup C)=(A \cap B) \cup (A \cap C)$ ;

(в)

$(A \cup B) \cap A=(A \cap B) \cup A=A$ ;

(г)

$A \backslash (B \cup C)=(A \backslash B) \cap (A \backslash C)$ ;

(д)

$A \backslash (B \cap C)=(A \backslash B) \cup (A \backslash C)$ ;

(е)

$(A \backslash B) \cap C=(A \cap C) \backslash B$ ;

(ж)

$A \backslash (B \backslash C)=(A \backslash B) \cup (A \cap C)$ ;

(з)

$(A \backslash B) \backslash C=A \backslash (B \cup C)$ ;

(и)

$A \div B=(A \cup B) \backslash (A \cap B)$ ;

(к)

$A \cup \varnothing =\varnothing \cup A=A$ ;

(л)

$A \cap \varnothing =\varnothing \cap A=\varnothing$ ;

(м)

$A \div \varnothing =\varnothing \div A=A$ ;

(н)

$A \div A=\varnothing$ .

Задача 5

(а)(б)(в)(г)

Доказать, что

?

(а)

$A \times (B \cup C)=(A \times B) \cup (A \times C)$ ;

(б)

$A \times (B \cap C)=(A \times B) \cap (A \times C)$ ;

(в)

$A \times (B \backslash C)=(A \times B) \backslash (A \times C)$ ;

(г)

если $A \subseteq B$ и $C \subseteq D$ , то $(A \times C)=(A \times D) \cap (B \times C)$ .

Задача 6

Доказать, что включение $A \subseteq B$ выполнено тогда и только тогда, когда выполнено $\mathrm{P}(A) \subseteq \mathrm{P}(B)$ .

?

Задача 7

Для каждого из следующих отношений найти $\operatorname {dom} R, \operatorname {rng} R, R^{-1}$ , $R \circ R, R \circ R^{-1}$ :

?

(а)

$R=\left\{ (x, y): x, y \in \omega \text{ и }x\text{ делит }y\right\} , x$ делит $y$ , если существует такое $z$ , что $x z=y$ ;

(б)

$R=\left\{ (x, y): x, y \in \omega \text{ и }x+y \leqslant 10\right\}$ ;

(в)

$R=\left\{ (x, y): x, y \in \omega \text{ и }y=3 x+1\right\}$ ;

(г)

$R=\left\{ \left(x, x^{2}\right): x \in \omega \text{ и } x \leqslant 10\right\}$ ;

(д)

$R=\left\{ (a, b),(b, c),(b, d),(c, d),(d, b)\right\}$ .

Задача 8

(а)(б)

Пусть множество $S=\left\{ (i, j): 1 \leqslant i, j \leqslant 8\right\}$ задаёт клетки шахматной доски. Описать следующие бинарные отношения на $S$ :

?

(а)

$L=\left\{ (a, b)\text{ : ладья за один ход может перейти с клетки }a\text{ на клетку }b\right\}$ ;

(б)

$K=\left\{ (a, b)\text{ : конь за один ход может перейти с клетки }a\text{ на клетку }b\right\}$ .

Будут ли эти отношения эквивалентностями? Описать отношение $L \circ L$ .

Задача 9

(а)(б)

Пусть П — множество всех прямых на евклидовой плоскости. Определить, будут ли следующие отношения на П отношениями эквивалентности:

?

(а)

параллельность прямых (будем считать, что прямая параллельна себе самой);

(б)

перпендикулярность прямых.

Задача 10

Пусть П — множество многоугольников на плоскости. Будут ли следующие отношения отношениями эквивалентности на П:

?

(а)

$x$ и $y$ возможно совместить;

(б)

$x$ и $y$ подобны;

(в)

$x$ и $y$ имеют одинаковый угол;

(г)

$x$ и $y$ пересекаются;

(д)

$x$ и $y$ имеют одинаковую площадь;

(е)

$x$ и $y$ имеют общую вершину;

(ж)

$x$ и $y$ равносоставлены.

Задача 11

Пусть $W$ — множество слов алфавита $\Sigma$ . Будут ли следующие отношения отношениями эквивалентности на $W$ :

?

(а)

$x$ и $y$ состоят из одних и тех же символов без учёта количества;

(б)

$x$ и $y$ состоят из одних и тех же символов с учётом количества;

(в)

$x y$ имеет чётную длину;

(г)

$x$ и $y$ имеют одинаковую длину;

(д)

$x$ и $y$ имеют одинаковую длину и отличаются не более чем в одной позиции;

(е)

$x$ и $y$ имеют хотя бы одну общую букву;

(ж)

$x$ и $y$ начинаются одной и той же буквой.

Задача 12

(а)(б)

Пусть $\Sigma =\left\{ a_{1}, \ldots , a_{m}\right\}$ — произвольный конечный алфавит, то есть множество символов. Обозначим через $\Sigma^{n}$ множество слов длины $n$ в алфавите $\Sigma$ (это обозначение согласовано с тем же обозначением декартовой степени $\Sigma$ , так как степень $\Sigma^{n}$ состоит из всех последовательностей элементов $\Sigma$ длины $n$ ).

?

(а)

Определим следующее отношение $R_{1}$ на словах из $\Sigma^{n}$ . Пусть $v=a_{i_{1}} a_{i_{2}} \ldots a_{i_{n}}, w=a_{j_{1}} a_{j_{2}} \ldots a_{j_{n}}$ . Тогда $(v, w) \in R_{1}$ тогда и только тогда, когда $i_{k} \leqslant j_{k}$ для всех $k$ от 1 до $n$ и $i_{k}<j_{k}$ для некоторого такого $k$ , то есть номер каждой буквы слова $v$ не больше номера той же буквы в слове $w$ и хотя бы у одной из букв он меньше. Определить, является ли это отношение $R_{1}$ отношением частичного (линейного) порядка.

(б)

Определим следующее отношение $R_{2}$ на словах из $\Sigma^{*}$ . Пусть $v=a_{i_{1}} a_{i_{2}} \ldots a_{i_{n}}, w=a_{j_{1}} a_{j_{2}} \ldots a_{j_{r}}$ . Тогда $(v, w) \in R_{2}$ тогда и только тогда, когда существует такое $k$ в интервале от 1 до $n$ , что $i_{l}=j_{l}$ при $l<k$ и $i_{k}<j_{k}$ или $n<r$ и первые $n$ символов $w$ совпадают со словом $v$ . Определить, является ли это отношение $R_{2}$ отношением частичного (линейного) порядка.

Примечание.

?

Замечание 3 (Упорядочение наборов). Определённое в пункте (а) отношение $R_{1}$ называется отношением покоординатного порядка, а отношение $R_{2}$ из пункта (б) — отношением лексикографического порядка. В соответствии с лексикографическим порядком упорядочены, например, слова в словарях и энциклопедиях.

Задача 13

Доказать, что в условиях задачи 12 на противоположной странице на множестве $\Sigma^{k}$ лексикографический порядок расширяет покоординатный, то есть из $R_{1} \subseteq R_{2}$ .

?

Задача 14

Доказать, что если $X \subseteq Y$ — конечные подмножества $\omega$ , то $\rho (X) \leqslant \rho (Y)$ , где функция $\rho$ — из примера 2 на стр. 31. Продемонстрировать, что обратное неверно.

Пример 2: пусть $\mathrm{P}_{f}(A)$ означает множество всех конечных подмножеств $A$ . Функция $\rho : \mathrm{P}_{f}(\omega ) \rightarrow \omega$ определяется как $\rho (X)=\sum_{i \in X} 2^{i}$ .

?

Задача 15

Доказать, что функция $f$ на множестве $A$ является частичным порядком на $A$ в том и только том случае, когда $f(f(x))=f(x)$ для всех $x \in A$ .

?

Задача 16

(а)(б)(в)(г)

Доказать, что если множества $A$ и $B$ конечны, то для мощностей выполнены следующие равенства

?

(а)

(б)

$|A \cup B|=|A|+|B|-|A \cap B|$ ;

(в)

$\left|\left\{ 0,1\right\}^{n}\right|=2^{n}$ ;

(г)

$\left|\mathrm{P}(A)\right|=2^{\left|A\right|}$ .

Задача 17

Доказать счётность множества пар $\omega^{2}$ .

?

Задача 18

Доказать счётность множества упорядоченных $n$ -ок $\omega^{n}$ .

?

Задача 19

Доказать, что объединение счётного числа счётных множеств снова будет счётным.

?

Задача 20

Доказать счётность множества рациональных чисел $\mathbb {Q}$ .

?

Задача 21

Доказать счётность множества многочленов $n$ -й степени с целыми коэффициентами для фиксированного $n$ .

?

Задача 22

Доказать счётность множества всех многочленов с целыми коэффициентами.

?

Задача 23

Доказать счётность множества алгебраических чисел.

?

Задача 24

С помощью теоремы Кантора-Бернштейна доказать, что множество $S$ последовательностей действительных чисел $\left(a_{i}\right)_{i \in \omega }, a_{i} \in \mathbb {R}$ , равномощно $\mathbb {R}$ .

?

Задача 25

Доказать, что всякий язык в конечном алфавите счётен.

?

Задача 26

Найти $L_{1} \cap L_{2}, L_{2} \backslash L_{1}, \bar{L}_{1}$ для следующих языков в алфавите $\Sigma =\left\{ a, b\right\}$ :

\begin{align} & L_{1}=\left\{ w \in \Sigma ^{*}: \text{ количества букв } a \text{ и } b \text{ в } w \text{ совпадают }\right\} \\ & L_{2}=\left\{ a^{i} b^{j}: i, j \in \omega \right\} . \end{align}

?

Задача 27

Найти все префиксы и суффиксы слова $a^{2} b^{2} c$ .

?

Множества и отношения