Білет № 13

Стуруктура – розміщення або відношення елементів (таких як частки, частини, деталі, органи) у речовині, тілі або системі.

Відношення.

Вираз виду (a, b), де a Î A і b Î B, називається впорядкованою парою. Рівність виду (a, b) = (c, d) позначає, що a = c і b = d. У загальному випадку, якщо з елементів a₁ Î A₁, a₂ Î A₂, …, a_n Î A_n множин A₁, A₂, …, A_n утворити n-ку (a₁, a₂, …, a_n), то рівність виду

(a₁, a₂, …, a_n) = (b₁, b₂, …, b_n)

аналогічна рівності a_i = b_i для i = 1,…,n. Якщо взяти усі елементи a_i множин A_i, то множина виду

{(a₁, a₂, …, a_n)| a_i Î A_i}

називається прямим (декартовим) добутком множин A₁, A₂, …, A_n і записується наступним чином:

A₁ Í A₂, Í…Í A_n

Для підмножин прямого (декартового) добутку операції об’єднання, перетину та різниці визначаються аналогічно до операцій над множинами.

Декартовий добуток АхВ={аі;ві: аі є А, ві є В} – множина впорядкованих пар, першим елементом яких єелемент з множини А, другий – з множини В.

Відношенням R на множинах A₁, A₂, …, A_n називається деяка підмножина прямого (декартового) добутку A₁ Í A₂, Í…Í A_n:

R Î A₁ Í A₂, Í…Í A_n

. Відношення еквівалентності.

Відношення R на множині M = { x, y, …, z } є відношенням еквівалентності, якщо воно має наступні властивості:

1. xRx для усіх x Î M (рефлексивність);

2. Якщо xRy, то yRx для усіх x,y Î M (симетричність);

3. Якщо xRy, yRz, то xRz для усіх x, y, z Î M (транзитивність).

Якщо відношення R задовольняє перелічені вище властивості, то кажуть, що відношення R рефлексивне, симетричне та транзитивне. Для позначення відношення еквівалентності використовується знак =.

Якщо для довільного елемента x множини M взяти множину [ x ] усіх елементів множини M, які еквівалентні x, то можна записати вираз

[ x ] = { y | x = y }

Відношення еквівалентності поділяє множину M на підмножини, що взаємно не перетинаються (класи еквівалентності). У такому разі [ x ] можна розглядати як символ, що позначає підмножину еквівалентних між собою елементів, яка містить x.

Наприклад, відношення «бути родичем» на множині людей можна вважати відношенням еквівалентності. Відношення, яке є рефлексивним і симетричним, проте не є транзитивним, називається відношенням сумісності.

. Відношення порядку.

Відношення R на множині M = { x, y, …, z } є відношенням порядку, якщо воно має наступні властивості:

1. xRx для усіх x Î M (рефлексивність);

2. xRy, yRx –> x = y для усіх x,y Î M (антисиметричність);

3. xRy, yRz –> xRz для усіх x, y, z Î M (транзитивність).

Кажуть, що відношення R, яке задовольняє цим властивостям, є рефлексивним, антисиметричним і транзитивним. Для позначення відношення порядку послуговуються символом <=.

Множина з заданим на ній відношенням порядку називається (повністю) впорядкованою множиною.

2.1.6. Повна впорядкованість.

Якщо для будь-яких двох довільних елементів x, y впорядкованої множини M виконується

x <= y або y <= x,

то <= є відношенням повного порядку, а множина M називається повністю впорядкованою множиною. Впорядкована множина, що не є повністю впорядкованою, називається частково впорядкованою множиною (не всі елементи можна порівняти).

Відношення R «бути родителем» є відношенням порядку, проте відношення «бути братом або сестрою» є відношенням часткового порядку.

Візьмемо підмножину P впорядкованої множини S. Якщо елемент s множини S та всі елементи p множини P пов’язані відношенням p <= s, то s називається верхньою межею множини P. Якщо верхня межа s множини P стосовно до усіх верхніх меж s` множини P пов’язана відношенням s <= s`, то s називається найменшою верхньою межею (супремум) множини P. Аналогічно визначаються нижня межа та найбільша нижня межа (інфінум). Для пари елементів {a, b} повністю впорядкованої множини L завжди існує верхня та нижня межа {a, b}.

2.1.7. Лексикографічний порядок.

Введемо поняття лексикографічного порядку. Нехай задані повністю впорядковані множини M₁, M₂, …, M_n, кожне з яких повністю впорядковане відповідним відношенням R_i (i = 1,…, n). Для елементів x та y прямого добутку M₁ Í M₂ Í … Í M_n, де

x = (x₁, x₂, …, x_n), x_i Î M_i,

y = (y₁, y₂, …, y_n), y_i Î M_i,

можливо визначити відношення повного порядку наступним чином:

1. x_i = y_i для усіх i (i <= j); /скільки рівних пар/

2. якщо x_j+1 < y_j+1 для j (<= n), то x < y

Такий порядок називається лексикографічним порядком.

2. Тип данных Boolean (Visual Basic)

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

Дата добавления: 2015-05-26