Функции
.docМинистерство общего и профессионального образования Российской Федерации.
Уфимский Государственный Авиационный Технический Университет.
Кафедра ПСИ
Курсовая работа по дискретной математике на тему:
«Функции»
Выполнили:
Студенты ФИРТ, гр. АСОИ-229
Ягудин Тимур
Проверил:
Галимов А.К.
Уфа—2005 год.
Содержание
-
Теория функций………………………………………………………………… 3
а) сюръективная функция
б) инъективная функция
в) биективная функция
2. Примеры решения на определение типа функции……………………………… 4
3. Список используемой литературы………………………………………………. 5
4. Приложение: листинг программы………………………………………….. 6
Определение. Бинарное отношение f называется функцией, если из < X,Y> f и <X,Z> f следует, что Y=Z. (Функция является однозначной).
Две функции равны, если они состоят из одних и тех же элементов. Область определения: Df , область значений: Rf.
Если Df=X и RfY, то говорят, что f осуществляет отображение множества X на множестве Y. Обозначения:f: X→Y или X→fY. <x,y>f y=f(x); y- образ, x- прообраз элемента y.
Примеры
{<1,2>, <2,3>, <Θ, Δ>} –функция;
{<1,2>, <1,3>, <2,4>} – не функция (1 отображается сразу на два элемента);
{<x, x2+ 2x+ 1> ׀x R} - функция y=x2+2x+1
Определение. N- местной функцией называют отношение f, если f: Xn→Y.
Обозначение y= f(x1 ,…,xn).
Определение.Функция f: X→Y называется инъективной, если x1, x2, y:=f(x1), y:=f(x2) x1=x2. ( То есть, одинаковые значения Y могут соответствовать одинаковым значениям X ).
Определение.Функция f:Х→У называется сюръективной, если yY xX:
Y=f(x). ( То есть, каждому значению у соответствует некоторое значение х).
Определение. Функция называется биективной если она одновременно и сюръективна и инъективна.
Примеры
f(x)=ex – инъективна, но не сюръективна при х R;
f(x)=x3-x – сюръективна, но не инъективна.
Утверждение. Композиция двух функций есть функция.
Доказательство.
Допустим, композиции gf принадлежат две пары:
.
Поскольку f – функция, то u=v. Поскольку g – функция и u=v, то y=z, т.е. gof – функция.
Утверждение. Композиция двух биективных функций есть биективная функция. Следует из взаимной однозначности отображений, осуществляемых биективными функциями.
Определение. Тождественным отображением множества X в себя называется отображение
ex: XX такое, что xX ex(x)=x. Тогда fex=f, eyf=f.
Утверждение. Отображение f: XY имеет обратное отображение f1: YX тогда и только тогда, когда f – биекция.
Доказательство.
Пусть f – биекция. Поскольку f – сюръективна, то отношение f-1 определено на множестве Y (каждому y соответствует определенное x).
В связи с инъективностью функции f обратное отношение f-1 является функцией (так как функция – однозначна, а инъективность означает невозможность соответствия различных x одному y). Прямое утверждение доказано.
Пусть теперь отображение f имеет обратное – f-1, определенное на множестве Y со значениями во множестве X. Тогда f сюръективно.
Но f также инъективно, так как f-1 – функция.
Утверждение доказано.
Замечание. Для того, чтобы обратное отношение f-1 было функцией на множестве значений Rf функции f, достаточно, чтобы функция f была инъективной. Тогда для инъективных функций выполняются следующие свойства бинарных отношений
1) (f)=f; 2) (gf) =fg.
Свойства биективных функций
3) ff=ex; 4) ff=ey.
Примеры
№ 1
Дано отношение <x,y> Є ρ x Є { 1, 2, …, 9 }, y Є {1, 2, …,9}
X |
1 |
3 |
2 |
4 |
8 |
5 |
3 |
6 |
9 |
7 |
Y |
4 |
2 |
3 |
1 |
7 |
6 |
3 |
9 |
6 |
5 |
Определить является ли это отношение функцией? Является ли инъективной функцией? Является ли сюрьективной функцией? Является ли биективной функции- ей?
Решение:
1)функция не инъективна так как значению Y=6 соответствует сразу два значения X=5 и X=9, а согласно определению функция f: X→Y называется инъективной, если x1, x2, y:=f(x1), y:=f(x2) x1=x2. ( То есть, одинаковые значения Y могут соответствовать одинаковым значениям X ).
2)функция не сюръективна так как в строке значений Y отсутствует значение 8 чего
не может быть по определению для сюръективной функции: функция f: Х→У называется сюръективной, если yY xX: Y=f(x). ( То есть, каждому значению у соответствует некоторое значение х).
Узнав, что функция не сюръективна и не инъективна приходим к тому, что функция не биективна(функция называется биективной если она одновременно и сюръективна и инъективна).
№ 2
Дано отношение <x,y> Є ρ x Є{ 1, 2, …, 9 }, y Є {1, 2, …,9}
X |
1 |
5 |
3 |
6 |
4 |
7 |
9 |
8 |
3 |
2 |
Y |
1 |
2 |
5 |
7 |
9 |
6 |
3 |
4 |
5 |
8 |
Определить является ли это отношение функцией? Является ли инъективной функцией? Является ли сюрьективной функцией? Является ли биективной функ- цией?
Решение:
1)функция инъективна так как значения Y =1и Y=5 соответствуют одинаковым значениям X=1и X=3( по определению функция f: X→Y называется инъективной, если x1, x2, y:=f(x1), y:=f(x2) x1=x2. ( То есть, одинаковые значения Y могут соответствовать одинаковым значениям X ).
2)функция сюръективна так как каждому значению Y соответствует некоторое значение X( функция f: Х→У называется сюръективной, если yY xX: Y=f(x) то есть, каждому значению Y соответствует некоторое значение X).
Отсюда следует, что данное отношение является биективной функцией так как она одновременно инъективна и сюръективна.
№ 3
X |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
2 |
9 |
Y |
2 |
5 |
4 |
3 |
8 |
1 |
6 |
9 |
5 |
1 |
Определить является ли это отношение функцией? Является ли инъективной функцией? Является ли сюрьективной функцией? Является ли биективной функ- цией?
Решение:
1) функция инъективна так как значения Y=5 соответствует тем же одинаковым значениям X=2( по определению функция f: X→Y называется инъективной, если x1, x2, y:=f(x1), y:=f(x2) x1=x2. ( То есть, одинаковые значения Y могут соответствовать одинаковым значениям X ).
2) функция не сюръективна так как каждому значению X (в данном случае) должно соответствовать некоторое значение Y, чего в нашем примере нет, а именно для того, чтобы функция была сюръективна, не хватает значения Y=7 ( функция f:Х→У называется сюръективной, если yY xX: Y=f(x) то есть, каждому значению Y соответствует некоторое значение X).
Отсюда следует, что данное отношение не является биективной функцией так как она инъективна, но не сюръективна.
Список используемой литературы
-
Житников В.И. Лекции по дискретной математике. УГАТУ- 2005г.
-
Яблонский С.В. Введение в дискретную математику. – М.: Высшая школа.; 2001.- 384с.
Листинг программы
#include <stdio.h>
#include <math.h>
#include <iostream.h>
int obraz[40];
int proobraz[40];
int i,j,a,s,n,m=0;
void main()
{
cout<<"Vvedite chisla. Vvod zakanchivaetsa esli vveden 0";
cout<<endl;
cout<<" 0<Y<11";
cout<<endl<<endl;
for (i=0;i<40;i++)
{
cout<<"X=";
cin>>proobraz[i];
cout<<endl;
if(proobraz[i]==0){break;}
x: cout<<"Y=";
cin>>obraz[i];
cout<<endl;
if(obraz[i]==0){break;}
if(obraz[i]>10||obraz[i]<0){goto x;}
else{n++;}
}
for (i=0;i<n;i++)
{
cout<<"<"<<proobraz[i]<<","<<obraz[i]<<">"<<" ";
}
cout<<endl;
for (i=0;i<n;i++) // цикл определяющий принадлежность данного отношения к
{
for (j=i+1;j<n;j++) // функциям
{
if(proobraz[i]==proobraz[j]&&obraz[i]!=obraz[j])
{
cout<<"Eto ne funkcia"<<endl;
goto b;
}
}
}
for (i=0;i<n;i++) // цикл по которому определяется является ли введенное
{
for (j=i+1;j<n;j++) // нами отношение не инъективной функцией
{
if(obraz[i]==obraz[j]&&proobraz[i]==proobraz[j])
{
a=1;
}
if(obraz[i]==obraz[j]&&proobraz[i]!=proobraz[j])
{
a=-1;
cout<<"Eto ne in'ektivna9| funkcia"<<endl;
goto e;
}
}
}
for (i=0;i<n;i++);
{
if(obraz[i])
{
for(j=i+1;j<n;j++)
{
if(obraz[i]==obraz[j])
{
obraz[i]=0;
}
}
}
}
e: if(a==1){cout<<"Eto in'ektivna9| funkcia"<<endl;} // определение инъективности
for (i=0;i<11;i++) // данного отношения
{
m=m+obraz[i];
}
if(m-55>-1) // цикл определяющий является ли введенное нами отношение
{
cout<<"Eta funkcia sur'ektivna9|"; // сюръективной функцией или же
s=1;
}
else{cout<<"Eta funkcia ne sur'ektivna9|";} //не сюръективной функцией
if(a==1&&s==1) // в данном цикле определяется является ли наше отношение
{
cout<<"Eto biektivna9| funkcia"; // биективной функцией
}
b:cin>>"";
}