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

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

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

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

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


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

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


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


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


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


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




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


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


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




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


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


[math]A\cup B= \bigl\{x\colon\, x\in A \lor x\in B\bigr\}.[/math]

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


[math]A\cap B= \bigl\{x\colon\, x\in A \land x\in B\bigr\}.[/math]

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


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

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


[math]\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\}.[/math]



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


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


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

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


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


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


[math]\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}[/math]

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


[math]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[/math]

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


[math]\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}[/math]

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


[math]x\in A\cap B \Leftrightarrow x\in A\land x\in B \Rightarrow x\in A.[/math]

21)

[math]\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}[/math]

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




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


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


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


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

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


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


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

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


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


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


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


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


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




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


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


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


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


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


[math]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\}.[/math]

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


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


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


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

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


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


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

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