Множество всех многочленов

Р(х) = а₀ + а₁х + а₂x² +... + а_nхⁿ любых степеней с рациональными коэффициентами а₀, а₁, + а₂,... а_n счетно.

Множество всех корней многочленов любых степеней с рациональными коэффициентами счетно.

Реляционная алгебра

Объектами, над которыми в реляционной (лат. relation - связь, отношение) алгебре выполняются операции, являются и n-арные отношения. Так как отношения - это множества, то над ними можно выполнять теоретико-множественные операции, такие как объединение, пересечение, разность, симметрическая разность и дополнение. Проиллюстрируем это примером.

Пример 1.22.

Пусть даны бинарные отношения:

Р= {(1,2), (1,3), (2,3), (3,4), (4,3)};

Q= {(1,3), (3,1), (3,2), (3,3), (3,4), (4,3)},

являющиеся подмножествами множества АxА=А², где А- {1,2,3,4}.

Объединение множеств Р и Q образуют все пары, входящие в эти множества: P Q = {(1,2), (1,3), (2,3), (3,1), (3,2), (3,3), (3,4), (4,3)}.

Пересечение множеств Р и Q - это множество, элементы которого входят одновременно в оба множества:

Разность множеств P\Q имеет вид:

/Л 0= {(1,2), (2,3)}.

Аналогично находим:

Q\P={(3,1),(3,2),(3,3)}.

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

Для нахождения дополнений множеств Р и Q сначала необходимо определить универсальное множество I. Так как | A| = 16, то универсальное множество I содержит 16 элементов:

I = {(1, 1), (1, 2), (1, 3), (1,4), (2,1), (2, 2), (2, 3), (2, 4), (3,1), (3, 2), (3,3), (3,4), (4,1), (4, 2), (4,3), (4,4)}.

Следовательно:

Р = {(1,1), (1,4), (2,1), (2,2), (2,4), (3,1), (3,2), (3, 3), (4,1), (4,2), (4,4)};

Q = {(1,1), (1,2), (1,4), (2,1), (2,2), (2,3), (2,4), (4,1), (4,2), (4,4)}.

В реляционной алгебре кроме теоретико-множественных используются и другие операции. Рассмотрим некоторые их них:

а) обмен позициями. Пусть n-арное отношение представлено множеством F кортежей длины п. Пронумеруем все элементы, входящие в кортеж. Суть операции обмена позициями, обозначаемой (i j) F, заключается в том, что знаки, стоящие в одном и том же кортеже на местах i и j, меняются местами (i,j=1,2,...,n; i=j ). Эта операция выполняется над всеми кортежами множества F.

Пример 1.23.

Рассмотрим отношение вида:

F= {(0,0,1,1,1), (0,1,1,1,0), (1,1, 0,0,1)},

являющееся подмножеством множества А⁵, где А = {0, 1}. В множестве F три кортежа. Применим к ним операцию обмена позициями, приняв i = 3,j = 5. Тогда получим новое отношение

(3 ~ 5)F= {(0,0,1,1,1), (0,1,0,1,0), (1,1,1,0, 0)}, не совпадающее с F. Очевидно, что если к множеству (3 ↔ 5) F снова применить ту же операцию при i = 3, j ≠ 5, то получим множество F;

б) расширение отношения. Эта операция имеет обозначение V_a F, где F -множество кортежей длины я, a - некоторый элемент, записываемый слева в каждый кортеж множества F. В результате получится новое множество с тем же числом кортежей, но длина каждого кортежа равна n + 1.

Пример 1.24.

Пусть F= {{a,b,c), (a,b,b), (b,b,b)}. Возьмем в качестве элемента а цифру 6. Тогда получим множество R:

R = V₆ F= {(6, а, b, с), (6, a, b, b), (6, b, b, b)}.

Если операцию расширения отношения применить к двум множествам F и Т, используя в качестве элемента а эти же символы F и T, а затем выполнитьоперацию объединения двух получившихся множеств, то получим новое отношение Q, представляющее собой композицию отношений F и Т:

в) исключение позиции. Обозначение этой операции имеет вид (i,j,..., k ) F, где i,j,..., k - номера позиций кортежа, из которых удаляются элементы. Эту операцию применяют ко всем кортежам множества F. В результате длина каждого кортежа уменьшится и могут появиться повторы одних и тех же укороченных кортежей. Все повторы необходимо удалить. Тогда останется множество, являющееся результатом операции исключения позиции.

Пример 1.25

Исключив 2-й и 4-й элементы в каждом кортеже множества F= {(а, b, b, с, d), (а, а, b, с, d), (а, с, с, с, d)}, получим новое множество М:

M=(2,A)F={(a,b,d),(a,c,d));

г) удвоение позиции. Пусть F— множество кортежей длины n. Выберем J- ю позицию какого-либо кортежа и повторно запишем находящийся в этой позиции элемент в заранее указанное место в том же кортеже. Тем самым мы выполним операцию удвоения позиции. Условное обозначение этой операции имеет вид D_j F. Выполняется она для каждого кортежа множества F.

Пример 1.26.

Рассмотрим отношение вида:

F= {(1,3,4), (1,3,5), (5,6,8), (4,5,7)}.

Допустим, что j-й элемент повторно записывается в каждый кортеж справа. Пусть j = 2, тогда

D₂F= {(1, 3,4, 3), (1, 3, 5, 3), (5, 6, 8,6), (4, 5, 7, 5)}.

Рассмотренных операций достаточно для того, чтобы получить представление о том, что является объектом изучения в реляционной алгебре. С другими операциями этой алгебры можно ознакомиться, обратившись к специальной литературе. Например, в некоторых источниках рассмотрена операция конкатенации (расширенного декартова произведения двух отношений).

Основы логики