Курсовая по дискретной математике

Министерство общего и профессионального образования Российской Федерации.

Уфимский Государственный Авиационный Технический Университет.

Кафедра ПСИ

Курсовая работа по дискретной математике на тему:

«Функции»

Выполнили:

Студенты ФИРТ, гр. АСОИ-229

Ягудин Тимур

Проверил:

Галимов А.К.

Уфа—2005 год.

Содержание

1. Теория функций………………………………………………………………… 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, x²+ 2x+ 1> ׀x R} - функция y=x²+2x+1

Определение. N- местной функцией называют отношение f, если f: Xⁿ→Y.

Обозначение y= f(x₁ ,…,x_n).

Определение.Функция f: X→Y называется инъективной, если x₁, x₂, y:=f(x₁), y:=f(x₂) x₁=x₂. ( То есть, одинаковые значения Y могут соответствовать одинаковым значениям X ).

Определение.Функция f:Х→У называется сюръективной, если yY xX:

Y=f(x). ( То есть, каждому значению у соответствует некоторое значение х).

Определение. Функция называется биективной если она одновременно и сюръективна и инъективна.

Примеры

f(x)=e^x – инъективна, но не сюръективна при х R;

f(x)=x³-x – сюръективна, но не инъективна.

Утверждение. Композиция двух функций есть функция.

Доказательство.

Допустим, композиции gf принадлежат две пары:

.

Поскольку f – функция, то u=v. Поскольку g – функция и u=v, то y=z, т.е. gof – функция.

Утверждение. Композиция двух биективных функций есть биективная функция. Следует из взаимной однозначности отображений, осуществляемых биективными функциями.

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

e_x: XX такое, что xX e_x(x)=x. Тогда fe_x=f, e_yf=f.

Утверждение. Отображение f: XY имеет обратное отображение f^1: YX тогда и только тогда, когда f – биекция.

Доказательство.

Пусть f – биекция. Поскольку f – сюръективна, то отношение f^-1 определено на множестве Y (каждому y соответствует определенное x).

В связи с инъективностью функции f обратное отношение f^-1 является функцией (так как функция – однозначна, а инъективность означает невозможность соответствия различных x одному y). Прямое утверждение доказано.

Пусть теперь отображение f имеет обратное – f^-1, определенное на множестве Y со значениями во множестве X. Тогда f сюръективно.

Но f также инъективно, так как f^-1 – функция.

Утверждение доказано.

Замечание. Для того, чтобы обратное отношение f^-1 было функцией на множестве значений R_f функции f, достаточно, чтобы функция f была инъективной. Тогда для инъективных функций выполняются следующие свойства бинарных отношений

1) (f^)^=f; 2) (gf) ^=f^g^.

Свойства биективных функций

3) f^f=e_x; 4) ff^=e_y.

Примеры

№ 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 называется инъективной, если x₁, x₂, y:=f(x₁), y:=f(x₂) x₁=x₂. ( То есть, одинаковые значения 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 называется инъективной, если x₁, x₂, y:=f(x₁), y:=f(x₂) x₁=x₂. ( То есть, одинаковые значения 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 называется инъективной, если x₁, x₂, y:=f(x₁), y:=f(x₂) x₁=x₂. ( То есть, одинаковые значения Y могут соответствовать одинаковым значениям X ).

2) функция не сюръективна так как каждому значению X (в данном случае) должно соответствовать некоторое значение Y, чего в нашем примере нет, а именно для того, чтобы функция была сюръективна, не хватает значения Y=7 ( функция f:Х→У называется сюръективной, если yY xX: Y=f(x) то есть, каждому значению Y соответствует некоторое значение X).

Отсюда следует, что данное отношение не является биективной функцией так как она инъективна, но не сюръективна.

Список используемой литературы

1. Житников В.И. Лекции по дискретной математике. УГАТУ- 2005г.

2. Яблонский С.В. Введение в дискретную математику. – М.: Высшая школа.; 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>>"";

}

8