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

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

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

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

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


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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

21)

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

Источник

Поделитесь с другими:

Если материал понравился Вам и оказался для Вас полезным, поделитесь им со своими друзьями!

Читать по теме:

Интересные статьи: