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


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

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



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

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

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

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

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

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

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

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

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

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

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

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

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

Например:

1) 0!=1

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

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

Пусть Е2={0, 1}. Булевой функцией f наз. отображение вида f: E2n®E2 или f=f(x1, x2, …xn). Всевозможные упорядоченые последовательности из нулей и единиц наз. набором. |E2n|=2n. Область определения ф-ции конечна, поэтому ее удобно описывать с помощьб таблиц истиности. Каждый набор x1, x2, …xn можно рассматривать как некоторое двоичное число. будем предполагать, что наборы x1, …xn упорядочены в таблице по возрастанию (как двоичные числа). Каждый последующий набор получается из предыдущего прибавлением двоич. единицы (00…1). Последний столбец табл. истиности обозначается Nf или af. Бул. ф-ция от n переменных однозначно определяется столбцом своих значений. Длинна столбца 2n и каждый эл. принимает одно из двух значений. Поэтому число бул. функций равно 22^n. Если мн-во всех бул. функций Р2(n), то |Р2(n)|=22^n. Ф-ции 2n и 22^n быстро растут с ростом n и поэтому распознование св-в бул. ф-ций полным перебором строк таблицы истиности и полным перебором бул. ф-ций от n переменных на практике возможно только для небольших n. Перебор строк – для n£40. Перебор бул. ф-ций – для n£6. Этот результат не зависит от быстродействия машин.

Переменную xi наз. несуществественной (фиктивной) для ф-ции f(x1, x2, …xn), если ее значение не влияет на значение ф‑ции. Пусть a=(a1, a2,…ai-1, 0, ai+1,… an) и a’=(a1, a2,…ai-1, 1, ai+1,… an). Тогда a и a’ – соседние наборы по переменной ai, понятно, что хi несущественна для f, если "a и a’ f(a)=f(a’). В противном случае переменную будем наз. существенной. Удаление фиктивной переменной осуществляется след. образом: из каждой пары соседних наборов оставляем один, а второй удаляем и даляем столбец, соот-щий фиктивной переменной. Операция введения фиктивной переменной осущ. в обратном порядке.

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

x1 x2 & V Å ® º ­ ¯
                 

Задание функций алгебры логики.

Булевую функцию n-переменных можно задать таблицей истинности:

х1 х2 х3 f(x1,x2,x3)
       
       
       
       
       
       
       
       

В левой части таблицы истинности записываются все 2n возможных значений переменных, в правой части зап. значения функций на этих наборах. Наборы, на которых функция принимает значение 1 наз. единичными, а те – на которых 0 – нулевыми.

Обычно наборы переменных располагают в лексикографическом порядке, который совпадает с порядком возрастания наборов, рассматриваемых как двоичные числа.

Число булевых функций от n переменных быстро возрастает с увеличением n.

 



Поделиться:


Последнее изменение этой страницы: 2017-02-21; просмотров: 349; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 54.226.242.26 (0.005 с.)