Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 3 часа [ Летнее время ]


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

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


Напомним некоторые необходимые в дальнейшем понятия так называемой наивной или интуитивной теории множеств.


Понятие множества


Понятие множества первично, исходно, неопределяемо, т.е. не может быть сведено к другим понятиям. Под множеством понимается совокупность объектов (предметов), которая рассматривается, мыслится как одно целое, как нечто единое. Объекты, составляющие множество, называются его элементами. Множества обозначают заглавными буквами латинского алфавита: A,B,C,\ldots, а элементы множеств — малыми латинскими буквами: a,b,c,\ldots, a_1,a_2, a_3,\ldots. Если некоторый объект a является элементом множества A, т.е. объект a принадлежит множеству A, то пишут a\in A. Если же элемент a не принадлежит множеству A, то пишут a\notin A. Символ \in называется знаком принадлежности.


Множество, состоящее из элементов a_1,a_2,\ldots,a_n, обозначается \{a_1,a_2,\ldots,a_n\}. Символ \{x\colon\, S(x)\} применяется для обозначения множества всех таких объектов x, которые удовлетворяют некоторому свойству S(x). Если объекты берутся из некоторого множества A, то множество всех таких объектов, удовлетворяющих свойству S(x), обозначается \{x\in A\colon\, S(x)\}. Например, \{x\in \mathbb{R}\colon\, x^2-x-6 \leqslant 0\} — множество всех действительных чисел x, удовлетворяющих соотношению x^2-x-6 \leqslant 0 (нетрудно проверить, что это множество есть замкнутый отрезок [-2;3] числовой прямой).




Включение и равенство множеств


Множество A называется подмножеством множества B, или говорят, что A включается в B, если каждый элемент множества A принадлежит множеству B. Запись: A\subseteq B. Множества A и B называются равными, если A состоит из тех и только тех элементов, которые принадлежат B, т. е. если x\in A тогда и только тогда, когда x\in B. Запись: A=B. Ясно, что A=B тогда и только тогда, когда A\subseteq B и B\subseteq A. Множество A называется собственным подмножеством множества B, если A\subseteq B и A\ne B. Обозначение: A\subset B. Символ \subset называется знаком включения.


Множество называется пустым, если оно не содержит ни одного элемента. Существует единственное пустое множество, оно обозначается символом \varnothing. Значит, \varnothing \subseteq A для любого множества A.




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


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


A\cup B= \bigl\{x\colon\, x\in A \lor x\in B\bigr\}.

Пересечением множеств A и B называется множество, обозначаемое A\cap B, состоящее из тех и только тех элементов, которые принадлежат как множеству A, так и множеству B. Следовательно, по определению


A\cap B= \bigl\{x\colon\, x\in A \land x\in B\bigr\}.

Разностью множеств A и B называется множество, обозначаемое A\setminus B, элементами которого являются все те элементы множества A, которые не принадлежат множеству B, и только они. Таким образом, по определению


A\setminus B= \bigl\{x\colon\, x\in A\land x\notin B\bigr\}.

Если A \subseteq U (где U — некоторое универсальное множество, которое содержит в качестве подмножеств все рассматриваемые нами множества), то дополнением множества A в множестве U называется множество, обозначаемое \overline{A}, состоящее из всех тех элементов множества U, которые не принадлежат множеству A. Итак,


\overline{A}= U\setminus A= \bigl\{x\colon\, x\in U\land x\notin A\bigr\}= \bigl\{x\in U\colon\, x\notin A\bigr\}.



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


Перечислим некоторые наиболее важные свойства операций над множествами и отношения включения множеств:


1) A\cup A=A (идемпотентность объединения);
2) A\cap A=A (идемпотентность пересечения);
3) A\cup B=B\cup A (коммутативность объединения);
4) A\cap B=B\cap A (коммутативность пересечения);
5) (A\cup B)\cup C= A\cup (B\cup C) (ассоциативность объединения);
6) (A\cap B)\cap C= A\cap (B\cap C) (ассоциативность пересечения);
7) A\cup (B\cap C)= (A\cup B)\cap (A\cup C) (дистрибутивность объединения относительно пересечения);
8) A\cap (B\cup C)= (A\cap B)\cup (A\cap C) (дистрибутивность пересечения относительно объединения);
9) A\cup (B\cap A)=A (1-й закон поглощения);
10) A\cap (B\cup A)=A (2-й закон поглощения);
11) \overline{A\cup B}= \overline{A}\cap \overline{B} (1-й закон де Моргана);
12) \overline{A\cap B}= \overline{A}\cup \overline{B} (2-й закон де Моргана);
13) A\cup U,~ A\cap U=A;
14) [A\cup \varnothing= A,~ A\cap\varnothing= \varnothing;
15) A\cup\overline{A}=U,~ A\cap\overline{A}=\varnothing;
16) \overline{\varnothing}=U,~ \overline{U}=\varnothing;
17) \overline{\overline{A}}=A (закон инволюции);
18) A\setminus B= A\cap \overline{B};
19) A\ \subseteq A\cup B,~ B \subseteq A\cup B;
20) A\cap B \subseteq A,~ A\cap B \subseteq B;
21) A \subseteq B~ \Leftrightarrow~ A\cap B=A;
22) A \subseteq B~ \Leftrightarrow~ A\cap B=B;
23) A \subseteq B~ \Leftrightarrow~ \overline{A}\cap B=U.

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


1) x\in A\cup A \Leftrightarrow x\in A \lor x\in A \Leftrightarrow x\in A. На последнем шаге применена тавтология из теоремы 3.2, пункт а): (P\lor P) \leftrightarrow P. Итак, множество A\cup A состоит из тех и только тех элементов, из которых состоит множество A. Следовательно, по определению равенства множеств, A\cup A=A;


6) Воспользуемся тавтологией из теоремы 3.2, (пункт г): \bigl((P\land Q)\land R\bigr) \leftrightarrow \bigl(P\land (Q\land R)\bigr)\colon


\begin{aligned}x\in (A\cap B)\cap C & \Leftrightarrow x\in A\cap B\land x\in C \Leftrightarrow (x\in A\land x\in B)\land x\in C \Leftrightarrow\\ & \Leftrightarrow x\in A\land (x\in B\land x\in C) \Leftrightarrow x\in A \land x\in B\cap C \Leftrightarrow\\ & \Leftrightarrow x\in A\cap (B\cap C).\end{aligned}

9) Воспользуемся тавтологией из теоремы 3.2, (пункт е): \bigl(P\lor (Q\land P)\bigr) \leftrightarrow P:


x\in A\cup(B\cap A) \Leftrightarrow x\in A\lor x\in B\cap A \Leftrightarrow x\in A\lor (x\in B\lor x\in A) \Leftrightarrow x\in A

11) Воспользуемся тавтологией из теоремы 3.2, (пункт ж): \lnot(P\lor Q) \leftrightarrow (\lnot P\land\lnot Q):


\begin{aligned}x\in \overline{A\cup B} &\Leftrightarrow x\notin A\cup B \Leftrightarrow \lnot (x\in A\cup B) \Leftrightarrow \lnot (x\in A\lor x\in B) \Leftrightarrow\\ &\Leftrightarrow \lnot (x\in A) \land\lnot (x\in B)\Leftrightarrow x\notin A\land x\notin B \Leftrightarrow\\ &\Leftrightarrow x\in \overline{A}\land x\in\overline{B} \Leftrightarrow x\in \overline{A}\cup \overline{B}\,. \end{aligned}

20) Воспользуемся тавтологией из теоремы 3.2, (пункт ж): (P\land Q)\to P


x\in A\cap B \Leftrightarrow x\in A\land x\in B \Rightarrow x\in A.

21)

\begin{aligned}A\cap B= A & \Leftrightarrow A\cap B \subseteq A \land A \subseteq A\cap B \Leftrightarrow\\[2pt] &\Leftrightarrow (x\in A\cap B\to x\in A) \land (x\in A\to x\in A\cap B) \Leftrightarrow\\[2pt] &\Leftrightarrow \bigl((x\in A\land x\in B)\to x\in A\bigr)\land \bigl(x\in A\to (x\in A\land x\in B)\bigr) \Leftrightarrow\\[2pt] &\Leftrightarrow 1\land \bigl(x\in A\to (x\in A\land x\in B)\bigr) \Leftrightarrow x\in A\to (x\in A\land x\in B) \Leftrightarrow \\[2pt] &\Leftrightarrow \lnot(x\in A)\lor (x\in A\land x\in B) \Leftrightarrow \bigl(\lnot(x\in A)\lor x\in A\bigr) \land \bigl(\lnot(x\in A)\lor x\in B\bigr) \Leftrightarrow\\[2pt] &\Leftrightarrow 1\land \bigl(\lnot(x\in A)\lor x\in B\bigr) \Leftrightarrow (x\in A\to x\in B) \Leftrightarrow A \subseteq B\,.\end{aligned}

Проанализируйте приведенную цепочку рассуждений и выявите использованные тавтологии.




Бинарные отношения и функции


Пусть даны два (не обязательно различных) множества A и B. Bыберем элементы a\in A и b\in B. Упорядоченной парой, составленной из элементов a и b, называется пара (a,b), в которой указано, какой элемент является первым, а какой — вторым. Таким образом, упорядоченная пара (b,a) отлична от упорядоченной пары (a,b), если a\ne b. Упорядоченные пары (a,b) и (c,d) называются равными, если и только если a=c и b=d.


Прямым (или декартовым) произведением двух множеств A и B называется множество A\times B всевозможных упорядоченных пар (a,b), таких, что a\in A и b\in B:


A\times B=\bigl\{(a,b)\colon\, a\in A\land b\in B\bigr\}.

Бинарным отношением между элементами множеств A и B называется любое множество упорядоченных пар (a,b), таких, что a\in A и b\in B, т.е. любое подмножество прямого произведения A\times B. Если \rho — бинарное отношение и записано (x,y)\in\rho, то говорят, что x и y связаны отношением \rho, или x находится с y в отношении \rho, или для x и y выполняется отношение \rho. Вместо записи (x,y)\in\rho используют также запись x\,\rho\,y.


Бинарное отношение f \subseteq A\times B называется функцией, заданной на множестве A и принимающей значения в множестве B (или отображением множества A в B), если:


а) для любого x\in A найдется y\in B, такой, что (x,y)\in f;
б) для любых x\in A,~ y_1,y_2\in B из того, что (x,y_1)\in f и (x,y_2)\in f, следует, что y_1=y_2.

Другими словами, f — функция, если для любого x\in A существует единственный y\in B, такой, что (x,y)\in f. Этот единственный элемент y называется значением функции f для аргумента x и обозначается f(x). Если (x,y)\in f, то используется запись y=f(x).


Множество A называется областью определения функции f, B — областью ее изменения.


То, что f есть функция (отображение) из A в B, записывают в виде f\colon A\to B или A\overset{f}{\to}B.


Функция f\colon A\to B называется инъективной (или взаимнооднозначной), если для любых x_1,x_2\in A из равенства f(x_1)=f(x_2) непременно вытекает равенство аргументов x_1=x_2.


Функция f\colon A\to B называется сюръективной (или отображением A на B), если для любого y\in B найдется хотя бы один x\in A, такой, что y=f(x).


Функция f\colon A\to B называется биективной (или биекцией), если она одновременно инъективна и сюръективна.




Понятие n-арного отношения


Обобщением понятия упорядоченной пары элементов является понятие кортежа (упорядоченного набора) объектов.


Кортеж n объектов a_1,a_2,\ldots,a_n обозначается (a_1,a_2,\ldots,a_n).


Два кортежа (a_1,\ldots,a_n) и (b_1,\ldots,b_n) называют равными и пишут (a_1,\ldots,a_n)= (b_1,\ldots,b_n), если и только если a_1=b_1,\ldots, a_n=b_n.


Прямым произведением n множеств A_1,\ldots,A_n называется множество


A_1\times \ldots\times A_n= \bigl\{(x_1,\ldots,x_n)\colon\, x_1\in A_1,\ldots, x_n\in A_n\bigr\}.

Если A_1=\ldots=A_n=A, то прямое произведение A\times \ldots\times A называют n-й прямой степенью множества A и обозначают A^n. При этом будем считать, что A^1=A.


Таким образом, n-арным отношением между элементами множеств A_1,\ldots,A_n называется любое подмножество прямого произведения A_1\times \ldots\times A_n.


Функцией n аргументов, заданной на множестве A и принимающей значения в множестве B, называется такое (n+1)-арное отношение f \subseteq A^n\times B, что:


а) для любых x_1,\ldots,x_n\in A найдется y\in B, такой, что (x_1,\ldots,x_n,y)\in f;
б) для любых x_1,\ldots,x_n\in A,~ y,z\in B из того, что (x_1,\ldots,x_n,y)\in f и (x_1,\ldots,x_n,z)\in f следует, что y=z.

Другими словами, f — функция, если для любых x_1,\ldots,x_n\in A существует единственный элемент y\in B, такой, что (x_1,\ldots,x_n,y)\in f. Аналогично тому, как это делалось для функции одного аргумента, для функции n аргументов также вводятся понятия инъективности, сюръективности, биективности.

Перейти на форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"

Часовой пояс: UTC + 3 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2018 MathHelpPlanet.com. All rights reserved