Доказательство тождеств с множествами позволяет получать записи минимальной длины для построения эффективных логических схем.

 

Условность нужно соблюдать в частном, а порядок в общем.

Ж. Бернарден

Глава 3. Упорядоченные множества

Упорядоченное множество (кортеж), равенство кортежей, декартово произведение множеств, степень множества, операции над упорядоченными множествами, график, диагональ, инвертирование, проектирование и композиция упорядоченных множеств и графиков, функциональные и инъективные графики.

ЦЕЛИ

Освоив эту главу, студенты должны:

· знать определение упорядоченного множества (кортежа);

· уметь выполнять операции над кортежами;

· знать правила выполнения совместных операций над кортежами и множествами;

· уметь выполнять операции инверсии и композиции;

· уметь доказывать тождества с кортежами;

· иметь понятие о графиках и их проекциях на заданные оси;

· знать основные свойства графиков.

3.1. Кортеж (Упорядоченное множество)

Кортеж, как и множество, является исходным неопределенным понятием. Синонимами термину кортеж являются вектор и набор. Кортеж обозначается строчными греческими буквами. Компоненты кортежа — строчными латинскими буквами.

a = < 2, 2, 3, 4, 4 > — пример кортежа.

В этом примере кортеж a состоит из пяти компонент: “2”, расположенная на первом месте; “2”, расположенная на втором месте; “3”; расположенная на третьем месте; “4”, расположенная на четвертом месте; “4”, расположенная на пятом месте. Т.е. в отличие от множества, кортеж может иметь повторяющиеся элементы, но все эти элементы различны. Число компонент кортежа называется его длиной. Длиной кортежа может быть любое целое неотрицательное число. Компонента кортежа эквивалентна элементу множества. Кортеж a длины S записывается a = < a ₁, a ₂, a ₃,..., a _S >, то есть |a| = S.

Компоненты кортежа могут обозначать любые понятия, объекты, в том числе элементы множества или кортежа. Например, a = < 3, Æ, 2 x - 1, {2, 1}, <3, 7> > — кортеж длины 5. Первая компонента число - 3, вторая — пустое множество, третья — многочлен, четвертая — множество и пятая компонента — кортеж длины 2.

В отличие от элементов множества, компоненты кортежа могут частично или полностью совпадать. Например, b = < 4, 4, 4, 4, 4 > — кортеж длины 5. Кортеж длины 2 называется двойка или пара, длины 3 — тройка и так далее. Наряду с кортежами длины 2, 3, 4,... существуют кортежи длины 1. Например, g = < 6 >.

Кортеж, который не содержит компонентов в своем составе, называется пустым кортежем и обозначается a = < >. Длина этого кортежа равна нулю.

Говорят, что два кортежа равны (a = b), если a и b имеют одинаковую длину и каждая компонента кортежа a совпадает с каждой компонентой кортежа b.

Кортежи a и b неравны (a ¹ b), когда они имеют разную длину или отдельные компоненты кортежа a не совпадают с соответствующими компонентами кортежа b.

Для любых кортежей a, b, g справедливы утверждения:

· если a = b, то b = a,

· если a = b и b = g, то a = g.

Например, два кортежа a = < 3, 5 > и b = < 5, 3 > не равны между собой, а кортежи a = < 9, 10 > и b = < 9, 10 > — равны.

В отличие от множеств, порядок следования компонент кортежа существенен. Отметим, что иногда кортеж называют упорядоченным множеством. Теоретико-множественная запись равенства кортежей имеет следующий вид:

для кортежей длины два: a = < a, b >, b = < c, d >, a = b ® a = c & b = d;

для кортежей длины три: a = <a₁, a₂, a₃>, b = <b₁, b₂, b₃>, a = b ® a₁ = b₁ & a₂ = b₂ & a₃ = b₃.

Кортеж a называют кортежем над множеством М, если каждая компонента кортежа a принадлежит М. Согласно определению пустого кортежа, данный кортеж является кортежем над любым множеством, в том числе и над пустым множеством.

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

Декартовым произведением множеств А и В называется множество, состоящее из всех тех и только тех пар, т.е. кортежей длины 2, первая компонента которых принадлежит множеству А, а вторая — множеству В.

А × В — декартово произведение множеств А и В.

Из определения этого произведения следует, что для произвольного кортежа длины 2:например,< х ₁, х ₂>, принадлежащего декартову произведению множеств, истинно высказывание: