21. Симметричное отношение. Композиция отношений.

Исходя из того, что отношение – это множество, над ними можно выполнять все теоретико-множественные операции.

Кромке того вводятся некоторые спец. операции.

Специальные операции:

1) Обращение

Отношение, симметричное отношению АХХ обозначается А^-1 и является подмножеством множества А^-1 ХУ, для которых (х,у)А

2) Композиция отношений

Пусть заданы 3 множества X,Y,Z и AXY BYZ

Композицией отношений А и В является отношение С, являющееся подмножеством Х Z . (x,z)y (x,y)A (y,z)B)

xAy, yBz xCz=xABz

22. Функциональное отношение.

Отношения АХУ будем называется функциональным, если все его элементы (упорядоченные пары) имеют различные первые координаты.

Х={х₁ х₂ х₃ х₄ х₅}

У={у₁ у₂ у₃}

АХ*У={(x1 у1), (х1 у2) (х1 у3) (х2 у1)…}

Функциональное отношение из множества Х в У называется функцией и обозначается:

f:XY

Обычно для задания функции используют префиксную запись:

y=f(x), х-аргумент, у – значение.

Пусть задана f(x) f:XY

Область определения функции:

f_x={x| y f(x)=y}

f_y={y| x y=f(x)}

Если обл. определения f(x) является вся мн. Х, то функция называется тотальной.

f_xХ – частичная.

Пусть f:XY, а f₁:QY

QX

Причем для хQ f и f₁ значения сходятся, тогда функцию f₁ называют схождением функции f на множестве Q, а функцию f – продолжением функции f₁ на мн. Х.

23. Типы отображений (инъекция, биекция, сюръекция).

Мн. X в Y, каждый элемент хХ имеет только один образ уУ, такой что y=f(x). Однако совсем не обязательно, чтобы любой элемент у имел образ в множестве Х.

Если любой элемент мн. У является образом только одного элемента из Х, то говорят, что имеет место отображение множества Х на мн. У, которое называют сюръекцией.

Если 2 различных элемента х₁,х₂ мн. Х ставятся в соответствие у₁,у₂ мн. У и они тоже различны, то такое отображение называется инъективным.

Отношение, которое является сюръективным и инъективным, то оно называется биективным.

Биективное отображение является взаимооднозначным отображением а между элементами х, у установлено взаимнооднозначное соответствие.

Обратное отображение является взаимнооднозначным.

24. Способы задания функций.

1) Таблица – списко параметров х, f(x), позволяющих задать функцию на конечном множестве. В ЭВМ – массивом определенного типа, функция нескольких переменных.

2) Задание функции формулой, описывает функцию как суперпозицию других более простых функций.

3) Задание функции графиком.

4) Рекурсивная процедура – задает функции используя значения, вычисленные на предыдущем шаге. Задать рекурсивную процедуру можно следующим образом:

а) задать значение f(0) или f(1);

б) значение f(n+1) вычисляется как суперпозиция значения f(n) и других считающихся известными функциями.

Например:

1) 0!=1

2) n!=(n-1)!*n

25. Функции алгебры логики.

Пусть Е₂={0, 1}. Булевой функцией f наз. отображение вида f: E₂ⁿE₂ или f=f(x₁, x₂, …x_n). Всевозможные упорядоченые последовательности из нулей и единиц наз. набором. |E₂ⁿ|=2ⁿ. Область определения ф-ции конечна, поэтому ее удобно описывать с помощьб таблиц истиности. Каждый набор x₁, x₂, …x_n можно рассматривать как некоторое двоичное число. будем предполагать, что наборы x₁, …x_n упорядочены в таблице по возрастанию (как двоичные числа). Каждый последующий набор получается из предыдущего прибавлением двоич. единицы (00…1). Последний столбец табл. истиности обозначается N_f или _f. Бул. ф-ция от n переменных однозначно определяется столбцом своих значений. Длинна столбца 2ⁿ и каждый эл. принимает одно из двух значений. Поэтому число бул. функций равно 2^{2^n}. Если мн-во всех бул. функций Р₂(n), то |Р₂(n)|=2^{2^n}. Ф-ции 2ⁿ и 2^{2^n} быстро растут с ростом n и поэтому распознование св-в бул. ф-ций полным перебором строк таблицы истиности и полным перебором бул. ф-ций от n переменных на практике возможно только для небольших n. Перебор строк – для n40. Перебор бул. ф-ций – для n6. Этот результат не зависит от быстродействия машин.

Переменную x_i наз. несуществественной (фиктивной) для ф-ции f(x₁, x₂, …x_n), если ее значение не влияет на значение ф‑ции. Пусть =(₁, ₂,…_i-1, 0, _i+1,… _n) и ’=(₁, ₂,…_i-1, 1, _i+1,… _n). Тогда  и ’ – соседние наборы по переменной _i, понятно, что х_i несущественна для f, если  и ’ f()=f(’). В противном случае переменную будем наз. существенной. Удаление фиктивной переменной осуществляется след. образом: из каждой пары соседних наборов оставляем один, а второй удаляем и даляем столбец, соот-щий фиктивной переменной. Операция введения фиктивной переменной осущ. в обратном порядке.

Две бул. ф-ции наз. равными, если одна из них получается из другой путем добавления или удаления фиктивной переменной. Среди бул. ф-ций выделяются элементарные бул. ф-ции: 1)константы: 1, 0; 2)тождественная ф-ция: х; 3)отрицание:х; 4)

x1	x2		V					
0 0 1 1	0 1 0 1	0 0 0 1	0 1 1 1	0 1 1 0	1 1 0 1	1 0 0 1	1 1 1 0	1 0 0 0