Математическая логика, множества, функции

Множества

Множества и элементы множеста - основные математические понятия.

Множество - это совокупность объектов, рассматриваемая как одно целое. Объекты, составляющие данное множество, называются его элементами.

Множество можно задать указанием всех его элементов

$A = \left\{ {x,y,z,...} \right\}$

или с помощью определяющего свойства

$A = \left\{ {x|P\left( x \right)} \right\}$,

где $P$ описывает свойство всех элементов, входящих в множество.

Основное отношение между элементом $x$ и содержащим его множеством $А$ обозначается так $x \in A$, что читается

  • $x$ есть элемент множества $А$,
  • $x$ принадлежит  $А$,
  • множество $А$ содержит элемент $x$ .

Если $x$ не является элементом множества $А$, то пишут $x \notin A$, а читают

  • $x$ не входит в $А$,
  • $x$ не принадлежит $А$,
  • $А$ не содержит $x$.

 

Подмножество 

Если каждый элемент множества $А$ входит в множество $B$, то $А$ называется подмножеством $B$, а $B$ называется надмножеством $А$.

Записывают $A \subset B$ или, $B \supset A$, а читают ($А$ входит в $B$ или $А$ содержится в $B$, или $B$ содержит $А$).

Используя логические символы можем записать:

$A \subset B \Leftrightarrow \left( {\forall x} \right)\left( {x \in A \Rightarrow x \in B} \right)$

Пустое множество по определению считается подмножеством любого множества.

Равные множества

Два множества $А$ и $B$ равны, если $A \subset B$ и $B \supset A$, записывают $A = B$.

Если множества $А$ и $B$ не равны, то записывают $A \ne B$.

 

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

Если је $A \subset B$ и $A \ne B$,тогда $А$ является собственным подмножеством $B$.

 

Объединение множеств

Объединением множеств $А$ и $B$ называется множество элементов, принадлежащих по крайней мере одному из данных множеств (т. е. либо $А$, либо $B$, либо одновременно и $А$ и $B$). Обозначают $A \cup B$ и читают "объединение $А$ и $B$".

Используя логические символы можем записать:

$A \cup B = \left\{ {x|x \in A \vee x \in B} \right\}$

 

Пересечение множеств

Пересечением множеств $А$ и $B$ называется множество элементов, принадлежащих одновременно и A и B. Обозначают $A \cap B$ и читают "пересечение $А$ и $B$".

Используя логические символы можем записать: 

$A \cap B = \left\{ {x|x \in A \wedge x \in B} \right\}$

 

Разность множеств

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


Используя логические символы можем записать: 

$A\backslash B = \left\{ {x|x \in A \wedge x \notin B} \right\}$.

 

Симметрическая разность двух множеств

Симметрическая разность двух заданных множеств  $А$ и $B$ — это такое множество $A\Delta B$, куда входят все те элементы первого множества, которые не входят во второе множество, а, также те элементы второго множества, которые не входят в первое множество:

$A\Delta B = (A\backslash B) \cup (B\backslash A)$

skupovi unija skupovi presek skupovi razlika skupovi simetricna razlika

Диаграмма Венна: а) объединение, б) пересечение, в) разность, г) симметрическая разность двух множеств.

 Дополнение множества

Пусть $А$ подмножество множества $I$, т.е. $A \subset I$. Дополнением множества $А$ до  множества  $I$ называется множество ${C_I}A = I$, содержащее все элементы множества $I$, которые не принадлежат множеству $А$.   

Пустое множество

Множество не содержащее ни одного элемента называется пустым (обозначается: $\emptyset $).

Используя логические символы можем записать: 

$A = \emptyset \Leftrightarrow (\forall x) \notin A$

 

Непересекающиеся множества

Два множества $А$ и $B$ являются непересекающими, если их пересечение пустое множество

$A \cap B = \emptyset $

 

Разбиение множества

Разбиение множества  — это представление его в виде объединения произвольного количествапопарно непересекающихся подмножеств. Пусть $\left\{ {{A_1},{A_2}} \right.,...,\left. {{A_n}} \right\}$ множество непустых подможеств множества $А$, говорят, что множество $А$   разбито на подможества, если:

  1. $\left( {{\forall _i}} \right)\left( {{\forall _j}} \right)\left( {i \ne j \Rightarrow {A_i} \cap {A_j} = \emptyset } \right)$ , i=1,...,n; j=1,....n
  2. ${A_1} \cup {A_2} \cup ... \cup {A_n} = A$

Булеан

Булеан множества $А$ (обозначается $P(А)$) - это множество всех подмножеств множества $А$, а также и само множество $А$ и пустое множество.

$P\left( A \right) = \left\{ {X\backslash X \subset A} \right\}$

 

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

  1. Коммутативность объединения, пересечения и  и симметрической разности
    $A \cap B = B \cap A,{\text{  }}A \cup B = B \cup A,{\text{  }}A\Delta B = B\Delta A$
  2. Ассоциативность объединения, пересечения и  и симметрической разности
    $\left( {A \cap B} \right) \cap C = A \cap \left( {B \cap C} \right)$, $\left( {A \cup B} \right) \cup C = A \cup \left( {B \cup C} \right)$ и $\left( {A\Delta B} \right)\Delta C = A\Delta \left( {B\Delta C} \right)$
  3. Идемпотентность пересечения и объединения
    $A \cap A = A,{\text{  }}A \cup A = A$.
  4. Дистрибутивность 
    $A \cap \left( {B \cup C} \right) = \left( {A \cap B} \right) \cup \left( {A \cap C} \right)$, ${\text{A}} \cup \left( {B \cap C} \right) = \left( {A \cup B} \right) \cap \left( {A \cup C} \right)$
  5. $A \cap \left( {A \cup B} \right) = A,{\text{  }}A \cup \left( {A \cap B} \right) = A$
  6. Инволютивность дополнения
    ${C_I}\left( {{C_I}A} \right) = A$
  7. Транзитивность
    $\left( {C \subset B} \right) \wedge \left( {B \subset A} \right) \Rightarrow C \subset A$
  8. $\left( {A \cap B} \right) \cap C = \left( {A \cap C} \right) \cap \left( {B \cap C} \right)$, $\left( {A \cup B} \right) \cup C = \left( {A \cup C} \right) \cup \left( {B \cup C} \right)$
  9. Для любого множества $A \subset I$ и пустого  $\emptyset $ справедливо
    $\emptyset \subset A \subset I$,
    $A \cap \emptyset  = \emptyset  \cap A = \emptyset $,
    $A \cup \emptyset  = \emptyset  \cup A = A$,
    $A \cap I = I \cap A = A$,
    $A \cup I = I \cup A = I$.

 

Декартово произведение

Упорядоченная пара  — это пара $(a, b)$, где первый элемент $a$, а второй $b$.

Упорядоченные пары $(a, b)$ и $(c, d)$ равны, если $a=c$ и $b=d$.
Упорядоченная n-ка элементов обозначается $\left( {{a_1},{a_2},...,{a_n}} \right)$, а их равенство записываем:


$\left( {{a_1},{a_2},...,{a_n}} \right) = \left( {{b_1},{b_2},...,{b_n}} \right) \Leftrightarrow {a_1} = {b_1} \wedge {a_2} = {b_2} \wedge ... \wedge {a_n} = {b_n}$.


Декартовым произведением множеств $А$ и $B$ называется такое результирующее множество пар вида $(a, b)$, построенных таким образом, что первый элемент пары — из множества $А$ , а второй элемент пары —  из множества $B$. Общепринятое обозначение:

 

$A \times B = \left\{ {\left( {x,y} \right)|x \in A \wedge y \in B} \right\}$

 

Декартово произведение конечного числа множиств $А_1, А_2,.....,А_n$ , есть

${A_1} \times {A_2} \times ..... \times {A_n} = \left\{ {\left( {{x_1},{x_2},...,{x_n}} \right)|{x_1} \in {A_1} \wedge {x_2} \in {A_2} \wedge ... \wedge {x_n} \in {A_n}} \right\}$

Декартовы произведения $A \times A,A \times A \times A$,... обозначаются ${A^2}, {A^3}$,...