Обсуждение участника:MetaMockery — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Ссылки)
(Метки: правка с мобильного устройства, правка из мобильной версии)
 
(не показано 55 промежуточных версий 2 участников)
Строка 1: Строка 1:
−
== Функция Эйлера ==
+
[[Категория:Математический анализ 1 курс]] [[Категория:Дискретная математика и алгоритмы]] [[Категория:Отношения]]
 +
 
 +
==Определения==
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
Функция <tex>f : \mathbb{N} \to \mathbb{Z} </tex> называется ''мультипликативной'', если <tex>f(mn) = f(m)f(n)</tex> для любых взаимно-простых <tex>m, n</tex>.
+
''Множество'' {{---}} первичное математическое понятие, которому не дано строгое математическое определение. Представляет собой набор, совокупность каких-либо объектов, объединенных общим свойством.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
''Функция Эйлера'' <tex>\varphi (n) </tex> - определяется как количество натуральных чисел, не превосходящих <tex>n</tex> и взаимно-простых с <tex>n</tex>.
+
Объекты, из которых состоит множество, называют ''элементами'' этого множества. Если <tex>a</tex> {{---}} элемент множества <tex>A</tex>, то записывают <tex>a \in A</tex> («<tex>a</tex> принадлежит <tex>A</tex>»). Если <tex>a</tex> не является элементом множества <tex>A</tex>, то записывают <tex>a \notin A</tex> («<tex>a</tex> не принадлежит <tex>A</tex>»). В отличие от мультимножества каждый элемент множества уникален, и во множестве не может быть двух идентичных элементов.
 
}}
 
}}
  
−
{{Теорема
+
==Способы задания множеств==
−
|about = Мультипликативность функции Эйлера
 
−
|statement = Для любых взаимно-простых чисел <tex>m, n</tex>
 
−
: <math>\varphi(mn)=\varphi(m)\varphi(n).</math>
 
−
|proof =
 
−
Запишем <math>nm</math> натуральных чисел, не превосходящих <math>nm</math>, в виде прямоугольной таблицы с <math>n</math> столбцами и <math>m</math> строками, располагая первые <math>n</math> чисел в первой строке, вторые <math>n</math> чисел во второй и т.д.
 
  
−
Поскольку <math>n</math> и <math>m</math> взаимно-просты, то целое <math>s</math> взаимно-просто с <math>nm</math> если и только если оно взаимно-просто как с <math>n</math>, так и с <math>m</math>. Итак, нужно доказать, что количество чисел в таблице, взаимно-простых с <math>n</math> и с <math>m</math> равно <math>\varphi(m)\varphi(n)</math>. Мы знаем, что число <math>s</math> взаимно-просто с натуральным <math>k</math> если и только если его остаток при делении на <math>k</math> взаимно-просто с <math>k</math>. Поэтому, числа в таблице, взаимно-простые с <math>n</math>, заполняют ровно <math>\varphi(n)</math> столбцов таблицы.
+
Существуют два основных способа задания множеств: перечисление и описание.
  
−
Давайте рассмотрим <math>m</math> последовательных членов арифметической прогрессии <math>a, a + d, \dots , a + (m - 1)d</math>. Тогда, если <math>GCD(d, m) = 1</math>, то остатки всех этих <math>m</math> чисел по модулю <math>m</math> разные, а значит образуют все множество остатков <math>\{0, \dots , m - 1\}</math>, причем каждый остаток получается ровно из одного из членов прогрессии.
+
==== Перечисление ====
 +
Первый способ состоит в том, что задаётся и перечисляется полный список элементов, входящих в множество.
 +
 
 +
<tex> A = \{a_1, a_2 ..., a_n, ...\} </tex>
  
−
Подставив в данные рассуждения <math>d = n</math>, получим, что в каждом столбце таблицы имеется ровно <math>\varphi(m)</math> чисел, взаимно-простых с <math>m</math>. Следовательно всего чисел, взаимно-простых и с <math>n</math> и с <math>m</math> равно <math>\varphi(m)\varphi(n)</math>, что и требовалось доказать.
+
==== Описание ====
−
}}
+
Второй способ применяется, когда множество нельзя или затруднительно задать с помощью списка. В таком случае множества определяются свойствами их элементов.
  
 +
<tex> A = \{a \mid P\} </tex> , где <tex>P</tex> {{---}} определенное свойство элемента <tex>a</tex>.
  
−
== Функции <tex>\sigma(n)</tex>, <tex>\tau(n)</tex> и <tex>\varphi(n)</tex>, их мультипликативность и значения ==
+
== Отношения между множествами ==
  
−
Каноническое разложение числа <tex>\displaystyle n = \prod_{i=1}^{r}p_i^{s_i} </tex>
+
Два множества <tex>A</tex> и <tex>B</tex> могут вступать друг с другом в различные отношения.
  
−
==== Функция <tex>\sigma(n)</tex> ====
+
==== Включение ====
 +
* <tex>A</tex> включено в <tex>B</tex>, если каждый элемент множества <tex>A</tex> принадлежит также и множеству <tex>B</tex> :
 +
*: <tex>\displaystyle A\subseteq B\Leftrightarrow \forall a\in A \ \colon \ a\in B</tex>
  
−
Функция <tex>\sigma : \mathbb{N} \to \mathbb{N} </tex> определяется как сумма делителей натурального числа <tex>n</tex>
+
* <tex>A</tex> включает <tex>B</tex>, если <tex>B</tex> включено в <tex>A</tex>:
−
<center><tex>\displaystyle\sigma(n) = \sum_{d | n}d </tex></center>
+
*: <tex>{\displaystyle A\supseteq B\Leftrightarrow B\subseteq A}</tex>
  
−
Для простого числа <math>p</math> легко посчитать <tex>\displaystyle\sigma(p) = p + 1</tex>. При этом легко обобщается для некоторой степени <math>p</math>:  
+
* <tex>A</tex> строго включено в <tex>B</tex>, если <tex>A</tex> включено в <tex>B</tex>, но не равно ему:
−
<center><tex>\displaystyle\sigma(p^s) = \sum_{k=0}^{s}p^k = \frac{p^{s + 1} - 1}{p - 1} </tex></center>
+
*: <tex>{\displaystyle A\subset B\Leftrightarrow (A\subseteq B)\land (A\neq B)}</tex>
  
−
В силу мультипликативности функции:
+
==== Равенство ====
−
<center><tex> \displaystyle \sigma (n) = \prod_{i = 1}^{r}{\frac{p_{i}^{s_i+1}-1} {p_{i}-1}}. </tex></center>
+
* <tex>A</tex> равно <tex>B</tex>, если <tex>A</tex> и <tex>B</tex> включены друг в друга:
 +
*: <tex>{\displaystyle A=B\Leftrightarrow (A\subseteq B)\land (B\subseteq A)}</tex>
  
 +
==== Общие элементы ====
 +
* <tex>A</tex> и <tex>B</tex> не пересекаются, если у них нет общих элементов:
 +
*: <tex>A</tex> и <tex>B</tex> не пересекаются <tex>{\displaystyle \Leftrightarrow \forall a\in A \ \colon a\notin B}</tex>
  
−
==== Функция <tex>\tau(n)</tex> ====
 
  
−
Функция <tex>\tau: \mathbb{N} \to \mathbb{N} </tex> определяется как число положительных делителей натурального числа <tex>n</tex>:
+
== Специальные множества ==
−
<center><tex>\displaystyle\tau(n) = \sum_{d | n}1 </tex></center>
 
  
−
Если <math>m</math> и <math>n</math> взаимно-просты, то каждый делитель произведения <math>mn</math> может быть единственным образом представлен в виде произведения делителей <math>m</math> и делителей <math>n</math>, и обратно, каждое такое произведение является делителем <math>mn</math>. Отсюда следует, что функция <tex>\tau(n)</tex>  мультипликативна:
+
{{Определение
−
<center><math>\tau(mn)=\tau(m)\tau(n).</math></center>
+
|definition=
−
 
+
''Пустое множество'' {{---}} множество, не содержащее ни одного элемента. Обычно пустое множество обозначают как <tex>\varnothing</tex>.
−
Для простого числа <math>p</math> легко посчитать <tex>\displaystyle\tau(p) = 2</tex>. При этом легко обобщается для некоторой степени <math>p</math>:
+
}}
−
<center><tex>\displaystyle\tau(p^s) = s + 1 </tex></center>
 
−
 
 
−
В силу мультипликативности функции:
 
−
<center><tex> \displaystyle \tau(n) = \prod_{i = 1}^{r}(s_i + 1). </tex></center>
 
−
 
 
−
 
 
−
==== Функция <tex>\varphi(n)</tex> ====
 
−
 
 
−
Для простого числа <math>p</math> легко посчитать <tex>\displaystyle\varphi(p) = p - 1</tex>. На некоторую степень <math>p</math> формулу можно обобщить:
 
−
<center><tex>\displaystyle\varphi(p^s) = p^s - p^{s - 1} </tex></center>
 
−
Обосновывается следующим образом: Все не взаимно-простые с <math>p^s</math> числа в диапазоне от 1 до <math>p^s</math>, очевидно, кратны <math>p</math>. Всего таких чисел <math>p^{s - 1}</math>.
 
−
 
 
−
В силу мультипликативности функции:
 
−
<center><tex> \displaystyle \varphi(n) = \prod_{i = 1}^{r}(p_i^{s_i} - p_i^{s_i - 1}) = \prod_{i = 1}^{r}p_i^{s_i}(1 - \frac{1}{p_i}) = n\prod_{i = 1}^{r}(1 - \frac{1}{p_i}) </tex></center>
 
−
 
 
−
 
 
−
 
 
−
== Малая теорема Ферма и теорема Эйлера ==
 
−
 
 
−
{{Теорема
 
−
|about= Теорема Эйлера
 
−
 
 
−
|statement = Если <math>n</math> и <math>a</math> - взаимно-простые целые числа, то <math>a^{\varphi(n)} \equiv 1 \ (mod \ n)</math>
 
−
 
 
−
|proof =
 
−
Число <math>\overline{x}</math> называется вычетом по модулю <math>n</math>, если <math>\overline{x} \equiv x \ (mod \ n)</math>. Вычет <math>\overline{x}</math> называется обратимым вычетом, если существует вычет <math>\overline{y}</math>, что <math>\overline{x}\overline{y} \equiv 1 \ (mod \ n)</math>. Заметим, что вычет <math>\overline{x}</math> обратим тогда и только тогда, когда <math>\overline{x}</math> и <math>n</math> взаимно-просты. В таком случае, у числа <math>n</math> существует всего <math>\varphi(n)</math> обратимых вычетов. Пусть <math>\mathbb{Z}_{n}^{*}</math> - множество всех обратимых вычетов по модулю <math>n</math>.
 
−
 
 
−
Рассмотрим вычеты по модулю <math>n</math>. Так как <math>n</math> и <math>a</math> взаимно-просты, то вычет <math>\overline{a}</math> обратим. Пусть <math>\overline{b_1}, \overline{b_2}, \dots , \overline{b_{\varphi(n)}}</math> - все обратимые вычеты по модулю <math>n</math>. Тогда вычет <math>\overline{b} = \overline{b_1}\overline{b_2}\dots\overline{b_{\varphi(n)}}</math>, равный произведению всех обратимых вычетов, тоже обратим. Заметим, что отображение <math>\mathbb{Z}_{n}^{*} \to \mathbb{Z}_{n}^{*}</math>, заданное формулой <math>\overline{x} \mapsto \overline{a}\cdot\overline{x}</math> является биекцией.  В таком случае в выражении <math> \overline{a}^{\varphi(n)}\overline{b} = (\overline{a} \overline{b_1}) \dots (\overline{a} \overline{b_{\varphi(n)}}) </math>, в правой части стоит произведение всех обратимых вычетов, но взятое в другом порядке. Тогда <math>\overline{a}^{\varphi(n)}\overline{b} = \overline{b}</math>. Умножая обе части на вычет, обратный к <math>\overline{b}</math>, получим, что <math>\overline{a}^{\varphi(n)} \equiv 1 \ (mod \ n) </math>, что и требовалось доказать.
 
  
 +
{{Определение
 +
|definition=
 +
''Универсальное множество'' {{---}} множество, содержащее все объекты и все множества. В тех аксиоматиках, в которых универсальное множество существует, оно единственно. Обычно универсальное множество обозначают как <tex> \ \displaystyle \mathbb {U}</tex>.
 
}}
 
}}
  
−
Следствием теоремы Эйлера является малая теорема Ферма. У нее также есть доказательство без использования более общей теоремы Эйлера, однако его мы приводить не будем.
+
== Операции над множествами ==
−
 
 
−
 
 
−
{{Теорема
 
−
|about = Малая теорема Ферма
 
−
 
 
−
|statement = Если целое число <math>a</math> и простое число <math>p</math> - взаимно-просты, то <math>a^{p - 1} \equiv 1 \ (mod \ p)</math>
 
  
−
|proof = Так как <math>p</math> - простое, то <math>\varphi(p) = p - 1</math>. Воспользуемся теоремой Эйлера, тогда <math>a^{\varphi(p)} = a^{p - 1} \equiv 1 \ (mod \ p)</math>, что и требовалось доказать.
+
==== Бинарные операции над множествами ====
  
−
}}
+
* Пересечение <tex>A</tex> и <tex>B</tex>.
 +
*: <tex>{\displaystyle A\cap B =\{x\mid x\in A\land x\in B\}}</tex>
  
−
== Различные свойства функции Эйлера ==
+
* Объединение <tex>A</tex> и <tex>B</tex>.
 +
*: <tex>{\displaystyle A\cup B =\{x\mid x\in A\lor x\in B\}}</tex>
  
−
{{Теорема
+
* Разность <tex>A</tex> и <tex>B</tex>.
−
|about =  
+
*: <tex>{\displaystyle A\setminus B =A\cap {\overline {B}}=\{x\mid x\in A\land x\notin B\}}</tex>
  
−
|statement = Для любого натурального числа <math>n</math> выполнено равенство <math>\displaystyle n = \sum_{d | n} \varphi(d)</math>
+
* Симметрическая разность <tex>A</tex> и <tex>B</tex>.
 +
*: <tex> {\displaystyle A \bigtriangleup B \equiv A - B  = (A \cup B) \setminus (A \cap B) }</tex>
  
−
|proof = Данную теорему можно доказать "напролом", пользуясь формулой для <math>\varphi(d)</math>, а можно более элегантно:
+
==== Унарные операции над множествами ====
  
−
Рассмотрим <math>n</math> дробей <math>\frac{1}{n}, \frac{2}{n}, \dots , \frac{n}{n}</math>. Каждую дробь представим в виде несократимой дроби <math>\frac{p}{q}</math>.
+
* Дополнение определяется следующим образом:
−
Заметим, что множество значений <math>q</math> - это множество делителей числа <math>n</math>. Так как дробь <math>\frac{p}{q}</math> несократима, то <math>p</math> и <math>q</math> взаимно-просты. Зная, что <math>p \leq q</math>, легко понять, что всего дробей со знаменателем <math>q</math> ровно <math>\varphi(q)</math>. Так как, все <math>n</math> дробей мы представили в несократимом виде, где знаменатель является делителем <math>n</math>, то <math>\displaystyle \sum_{d | n} \varphi(d) = n</math>, так как всего дробей <math>n</math>, что и требовалось доказать.
+
*: <tex>{\displaystyle {{\overline {A}}\equiv A^{\complement }=\{x\mid x\notin A\}}=U\setminus A}</tex>.
  
−
}}
+
== Теорема де Моргана ==
−
 
 
−
:
 
  
 
{{Теорема
 
{{Теорема
−
|about = Обобщённая мультипликативность
+
|about=
−
 
+
де Моргана
−
|statement = Пусть <math>n</math> и <math>m</math> {{---}} любые два натуральных числа, а <math>d = GCD(n,\ m)</math>, тогда:
+
|statement=  
−
: <math>\varphi(m \cdot n) = \varphi(m) \cdot \varphi(n)\cdot\frac{d}{\varphi(d)},</math>
+
<tex>\displaystyle {\overline{\bigcup\limits_\alpha A_\alpha} = \bigcap\limits_\alpha \overline{A_\alpha} \\
−
 
+
\overline{\bigcap\limits_\alpha A_\alpha} = \bigcup\limits_\alpha \overline{A_\alpha}} </tex>
−
|proof =  
+
|proof=
 +
Докажем первое утверждение, второе доказывается аналогично.
 +
Для того, чтобы доказать равенство множеств, докажем, что первое множество включает второе и наоборот (частый приём при доказательстве равенства двух множеств).
  
−
Пусть <math>(m,\,n)=d,</math> тогда <math>m = m'd, \; n = n'd,</math> причем в общем случае <math>(m',\,d) \neq 1</math> и <math>(n',\,d) \neq 1.</math> Поэтому можно записать:
+
Сначала докажем, что <tex> \ \displaystyle \overline{\bigcup\limits_\alpha A_\alpha} \displaystyle \subseteq \bigcap\limits_\alpha \overline{A_\alpha}</tex>.
−
:<math>d = d_1^{\delta_1} \cdot\ldots\cdot d_k^{\delta_k} \cdot d_{k+1}^{\delta_{k+1}} \cdot\ldots\cdot d_{K}^{\delta_{K}},</math>
 
−
:<math>m' = d_1^{\alpha_1} \cdot\ldots\cdot d_k^{\alpha_k} \cdot p_1^{\beta_1} \cdot\ldots\cdot p_r^{\beta_r},</math>
 
−
:<math>n' = d_{k+1}^{\gamma_{k+1}} \cdot\ldots\cdot d_{K}^{\gamma_{K}} \cdot q_1^{\varepsilon_1} \cdot\ldots\cdot q_s^{\varepsilon_s}.</math>
 
−
Здесь первые <math>k</math> делителей <math>d</math> являются также делителями <math>m',</math> а последние <math>K-k</math> делителей <math>d</math> являются делителями <math>n'.</math> Распишем:
 
−
:<math>\varphi(mn)= \varphi(d^2 \cdot m'n')
 
−
= \varphi((d_1^{\delta_1} \cdot\ldots\cdot d_k^{\delta_k} \cdot d_{k+1}^{\delta_{k+1}} \cdot\ldots\cdot d_{K}^{\delta_{K}})^2 \cdot d_1^{\alpha_1} \cdot\ldots\cdot d_k^{\alpha_k} \cdot p_1^{\beta_1} \cdot\ldots\cdot p_r^{\beta_r} \cdot d_{k+1}^{\gamma_{k+1}} \cdot\ldots\cdot d_{K}^{\gamma_{K}} \cdot q_1^{\varepsilon_1} \cdot\ldots\cdot q_s^{\varepsilon_s}).</math>
 
−
В силу мультипликативности функции Эйлера, а также с учётом формулы
 
−
:<math>\varphi(p^n) = p^n(1-\frac{1}{p}),</math>
 
−
где <math>p</math> — простое, получаем:
 
−
:<math>
 
−
\begin{align}
 
−
\varphi(mn)
 
  
−
&= d_1^{\alpha_1+\delta_1}\left(1-\frac{1}{d_1}\right) \cdot\ldots\cdot d_k^{\alpha_k+\delta_k}\left(1-\frac{1}{d_k}\right) \cdot p_1^{\beta_1}\left(1-\frac{1}{p_1}\right) \cdot\ldots\cdot p_r^{\beta_r}\left(1-\frac{1}{p_r}\right) \cdot d_{k+1}^{\delta_{k+1}}\left(1-\frac{1}{d_{k+1}}\right) \cdot\ldots\cdot d_{K}^{\delta_{K}}\left(1-\frac{1}{d_{K}}\right)\times \\
+
Пусть <tex>x \in \left ( \overline{\bigcup\limits_\alpha A_\alpha} \right )</tex>. Значит, <tex>\nexists \ \alpha_i</tex> такого, что <tex>x \in A_{\alpha_i}</tex>. Следовательно, <tex>\forall \alpha : \ x \in \overline{A_\alpha} \Rightarrow x \in \left (\bigcap\limits_\alpha \overline{A_\alpha} \right )</tex>.
 +
В силу выбора <tex>x</tex> (любой элемент множества <tex>\overline{\bigcup\limits_\alpha A_\alpha}</tex>) следует искомое включение.
  
−
&\; \times \; d_{k+1}^{\gamma_{k+1}+\delta_{k+1}}\left(1-\frac{1}{d_{k+1}}\right) \cdot\ldots\cdot d_{K}^{\gamma_{K}+\delta_{K}}\left(1-\frac{1}{d_{K}}\right) \cdot q_1^{\varepsilon_1}\left(1-\frac{1}{q_1}\right) \cdot\ldots\cdot q_s^{\varepsilon_s}\left(1-\frac{1}{q_s}\right) \cdot d_1^{\delta_1}\left(1-\frac{1}{d_1}\right) \cdot\ldots\cdot d_{k+1}^{\delta_{k+1}}\left(1-\frac{1}{d_{k+1}}\right)\times \\
 
  
−
&\; \times \; \frac{1}{\left(1-\frac{1}{d_1}\right) \cdot\ldots\cdot \left(1-\frac{1}{d_K}\right)}.
+
Теперь докажем, что <tex> \ \displaystyle \bigcap\limits_\alpha \overline{A_\alpha} \subseteq \overline{\bigcup\limits_\alpha A_\alpha}</tex>
−
\end{align}
 
−
</math>
 
−
В первой строке записано <math>\varphi(m),</math> во второй — <math>\varphi(n),</math> а третью можно представить, как <math>\frac{d}{\varphi(d)}.</math> Поэтому:
 
−
:<math>\varphi(m \cdot n) = \varphi(m) \cdot \varphi(n) \cdot \frac{d}{\varphi(d)}.</math>
 
  
 +
Пусть <tex>x \in \left ( \bigcap\limits_\alpha \overline{A_\alpha} \right )</tex>. Тогда <tex>\forall \alpha : \ x \in \overline{A_\alpha} \Rightarrow x \notin A_\alpha</tex>. Поскольку <tex>x</tex> не входит ни в одно объединяемое множество, то <tex>x \notin \bigcup\limits_\alpha A_\alpha \Rightarrow x \in \overline{\bigcup\limits_{\alpha} A_\alpha}</tex>
 +
Аналогично, в силу выбора <tex>x</tex> выполняется искомое включение.
 
}}
 
}}
  
−
== Применение теоремы Эйлера в других задачах ==
+
Теорема де Моргана устанавливает двойственность понятий объединения и пересечения множеств. То есть, имея некоторое верное равенство, содержащее объединения и пересечения, можно переписать его, заменив пересечения на объединения и наоборот. Например, из равенства
−
 
+
:<tex>(A \cup B) \cap C = (A \cap C) \cup (B \cap C) \Rightarrow (A \cap B) \cup C = (A \cup C) \cap (B \cup C)</tex>
−
==== Задача об ожерельях ====
+
Доказывается это следующим образом: равны множества, значит, равны дополнения. После раскрытия дополнений приходим к написанному равенству.
−
 
 
−
{{Задача
 
−
|definition=
 
−
Требуется посчитать количество ожерелий из <tex>n</tex> бусинок, каждая из которых может быть покрашена в один из <tex> k </tex> цветов. При сравнении двух ожерелий их можно поворачивать, но не переворачивать (т.е. разрешается сделать циклический сдвиг).}}
 
−
 
 
−
В ходе решения задачи мы приходим к формуле <tex>|C| =</tex> <tex> \dfrac{1} {n}</tex><tex>\sum\limits_{i = 1}^{n} k^{\mathrm{gcd}(i,n)}</tex>
 
−
 
 
−
Мы можем улучшить эту формулу, если рассмотрим выражение <math>\mathrm{gcd}(i,n)</math>. Пусть <math>\mathrm{gcd}(i,n) = q</math>, тогда числа <math>i</math> и <math>n</math> оба делятся на <math>q</math> и больше не имеют общих делителей. Тогда <math>\mathrm{gcd}(\frac{i}{q},\frac{n}{q}) = 1</math>. Таких натуральных <math>i \in [1 ; n]</math> и имеющих <math>\mathrm{gcd}(i,n) = q</math> ровно <tex>\varphi\left(\dfrac{n}{q}\right)</tex>.
 
−
 
 
−
Пользуясь функцией Эйлера, мы можем привести формулу к финальному виду <tex>|C| =</tex> <tex> \dfrac{1} {n}</tex><tex>\sum\limits_{q|n}\varphi\left(\dfrac{n}{q}\right)k^q</tex>.
 
−
 
 
−
 
 
−
 
 
−
== Ссылки ==
 
−
* [https://ru.wikipedia.org/wiki/Функция_Эйлера Wikipedia {{---}} Функция Эйлера]
 
−
* [https://e-maxx.ru/algo/euler_function Алгоритм нахождения функции Эйлера]
 

Текущая версия на 23:03, 16 июня 2021


Определения

Определение:
Множество — первичное математическое понятие, которому не дано строгое математическое определение. Представляет собой набор, совокупность каких-либо объектов, объединенных общим свойством.


Определение:
Объекты, из которых состоит множество, называют элементами этого множества. Если [math]a[/math] — элемент множества [math]A[/math], то записывают [math]a \in A[/math] («[math]a[/math] принадлежит [math]A[/math]»). Если [math]a[/math] не является элементом множества [math]A[/math], то записывают [math]a \notin A[/math] («[math]a[/math] не принадлежит [math]A[/math]»). В отличие от мультимножества каждый элемент множества уникален, и во множестве не может быть двух идентичных элементов.


Способы задания множеств

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

Перечисление

Первый способ состоит в том, что задаётся и перечисляется полный список элементов, входящих в множество.

[math] A = \{a_1, a_2 ..., a_n, ...\} [/math]

Описание

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

[math] A = \{a \mid P\} [/math] , где [math]P[/math] — определенное свойство элемента [math]a[/math].

Отношения между множествами

Два множества [math]A[/math] и [math]B[/math] могут вступать друг с другом в различные отношения.

Включение

  • [math]A[/math] включено в [math]B[/math], если каждый элемент множества [math]A[/math] принадлежит также и множеству [math]B[/math] :
    [math]\displaystyle A\subseteq B\Leftrightarrow \forall a\in A \ \colon \ a\in B[/math]
  • [math]A[/math] включает [math]B[/math], если [math]B[/math] включено в [math]A[/math]:
    [math]{\displaystyle A\supseteq B\Leftrightarrow B\subseteq A}[/math]
  • [math]A[/math] строго включено в [math]B[/math], если [math]A[/math] включено в [math]B[/math], но не равно ему:
    [math]{\displaystyle A\subset B\Leftrightarrow (A\subseteq B)\land (A\neq B)}[/math]

Равенство

  • [math]A[/math] равно [math]B[/math], если [math]A[/math] и [math]B[/math] включены друг в друга:
    [math]{\displaystyle A=B\Leftrightarrow (A\subseteq B)\land (B\subseteq A)}[/math]

Общие элементы

  • [math]A[/math] и [math]B[/math] не пересекаются, если у них нет общих элементов:
    [math]A[/math] и [math]B[/math] не пересекаются [math]{\displaystyle \Leftrightarrow \forall a\in A \ \colon a\notin B}[/math]


Специальные множества

Определение:
Пустое множество — множество, не содержащее ни одного элемента. Обычно пустое множество обозначают как [math]\varnothing[/math].


Определение:
Универсальное множество — множество, содержащее все объекты и все множества. В тех аксиоматиках, в которых универсальное множество существует, оно единственно. Обычно универсальное множество обозначают как [math] \ \displaystyle \mathbb {U}[/math].


Операции над множествами

Бинарные операции над множествами

  • Пересечение [math]A[/math] и [math]B[/math].
    [math]{\displaystyle A\cap B =\{x\mid x\in A\land x\in B\}}[/math]
  • Объединение [math]A[/math] и [math]B[/math].
    [math]{\displaystyle A\cup B =\{x\mid x\in A\lor x\in B\}}[/math]
  • Разность [math]A[/math] и [math]B[/math].
    [math]{\displaystyle A\setminus B =A\cap {\overline {B}}=\{x\mid x\in A\land x\notin B\}}[/math]
  • Симметрическая разность [math]A[/math] и [math]B[/math].
    [math] {\displaystyle A \bigtriangleup B \equiv A - B = (A \cup B) \setminus (A \cap B) }[/math]

Унарные операции над множествами

  • Дополнение определяется следующим образом:
    [math]{\displaystyle {{\overline {A}}\equiv A^{\complement }=\{x\mid x\notin A\}}=U\setminus A}[/math].

Теорема де Моргана

Теорема (де Моргана):
[math]\displaystyle {\overline{\bigcup\limits_\alpha A_\alpha} = \bigcap\limits_\alpha \overline{A_\alpha} \\ \overline{\bigcap\limits_\alpha A_\alpha} = \bigcup\limits_\alpha \overline{A_\alpha}} [/math]
Доказательство:
[math]\triangleright[/math]

Докажем первое утверждение, второе доказывается аналогично. Для того, чтобы доказать равенство множеств, докажем, что первое множество включает второе и наоборот (частый приём при доказательстве равенства двух множеств).

Сначала докажем, что [math] \ \displaystyle \overline{\bigcup\limits_\alpha A_\alpha} \displaystyle \subseteq \bigcap\limits_\alpha \overline{A_\alpha}[/math].

Пусть [math]x \in \left ( \overline{\bigcup\limits_\alpha A_\alpha} \right )[/math]. Значит, [math]\nexists \ \alpha_i[/math] такого, что [math]x \in A_{\alpha_i}[/math]. Следовательно, [math]\forall \alpha : \ x \in \overline{A_\alpha} \Rightarrow x \in \left (\bigcap\limits_\alpha \overline{A_\alpha} \right )[/math]. В силу выбора [math]x[/math] (любой элемент множества [math]\overline{\bigcup\limits_\alpha A_\alpha}[/math]) следует искомое включение.


Теперь докажем, что [math] \ \displaystyle \bigcap\limits_\alpha \overline{A_\alpha} \subseteq \overline{\bigcup\limits_\alpha A_\alpha}[/math]

Пусть [math]x \in \left ( \bigcap\limits_\alpha \overline{A_\alpha} \right )[/math]. Тогда [math]\forall \alpha : \ x \in \overline{A_\alpha} \Rightarrow x \notin A_\alpha[/math]. Поскольку [math]x[/math] не входит ни в одно объединяемое множество, то [math]x \notin \bigcup\limits_\alpha A_\alpha \Rightarrow x \in \overline{\bigcup\limits_{\alpha} A_\alpha}[/math]

Аналогично, в силу выбора [math]x[/math] выполняется искомое включение.
[math]\triangleleft[/math]

Теорема де Моргана устанавливает двойственность понятий объединения и пересечения множеств. То есть, имея некоторое верное равенство, содержащее объединения и пересечения, можно переписать его, заменив пересечения на объединения и наоборот. Например, из равенства

[math](A \cup B) \cap C = (A \cap C) \cup (B \cap C) \Rightarrow (A \cap B) \cup C = (A \cup C) \cap (B \cup C)[/math]

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Обсуждение_участника:MetaMockery&oldid=81064»