Частични функции

  • Частична функция f:Nn-o->N наричаме функция, която е дефинирана върху подмножество на Nn, което наричаме дефиниционна област (домейн) - dom(f). За x$$\in$$dom(f) пишем !f(x), за x$$\notin$$dom(f) пишем $$\neg$$!f(x).
  • Празната (никъде недефинираната) функция $$\emptyset$$ наричаме тази функция, за която дефиниционната област е празното множество. Ако dom(f) = N, казваме, че f е тотална. Ако dom(f) е крайно, казваме че f е крайна.
  • Графика на функцията f наричаме множеството Gf = { (x,y) | !f(x) = y }
  • Казваме, че f е условно равна на g в точката x (f(x)$$\simeq$$g(x)), ако !f(x) = !g(x) или $$\neg$$!f(x) & $$\neg$$!g(x), т.е. ($$\forall$$ y)(x,y)$$\in$$Gf <=> (x,y)$$\in$$Gg
  • Казваме, че f е подфункция на g, (f$$\subseteq$$g) ако Gf$$\subseteq$$Gg, т.е. ($$\forall$$ x)(f(x)$$\simeq$$y => g(x)$$\simeq$$y). Това е нестрога частична наредба (транзитивна, рефлексивна и антисиметрична релация). Интуитивно: g дава поне толкова информация, колкото f, евентуално повече.
  • Празната функция е най-малък и единствен минимален елемент на частично нареденото множество на частичните функции. Всяка тотална функция е максимален елемент. Най-голям елемент няма.
  • Всяка монотонно растяща редица от функции f0,f1,...,fn,... има точна горна граница ($$\bigcup$$ fn)(x)$$\simeq$$y <=> ($$\exists$$ n)(fn(x)$$\simeq$$y). Точната горна граница е най-малката от горните граници на редицата.
  • Fn = { f : Nn -o-> N } - множество от всички частични функции на n аргумента

Оператори

  • Оператор $$\Gamma$$:Fn -> Fm от тип (n,m) наричаме изображение, което съпоставя на всяка частична функция на n аргумента частична функция на m аргумента.
  • Казваме, че операторът $$\Gamma$$ е монотонен, ако $$(\forall f,g)(f\subseteq g\Rightarrow\Gamma(f)\subseteq\Gamma(g))$$. Интуитивно - ако дадем повече информация на монотонен оператор, той ни връща повече информация.
  • Стр. 172 / Зад. 2 - има оператори, които не са монотонни
  • Казваме, че операторът $$\Gamma$$ е компактен, ако $$(\forall f)(\forall \mathbf{x},y)(\Gamma(f)(\mathbf{x})\simeq y \Leftrightarrow (\exists\theta\subseteq f)(\Gamma(\theta)(\mathbf{x})\simeq y))$$, където $$\theta$$ е крайна функция. Интуитивно - компактният оператор използва крайна част от функцията - аргумент за всяко фиксирано x. Компактните оператори са точно програмируемите оператори.
  • Стр. 173 / Зад. 3 - Всеки компактен оператор е монотонен.
  • Стр. 174 / Зад. 7 - Има монотонни оператори, които не са компактни.
  • Стр. 173 / Зад. 5 - Един оператор е компактен <=> е монотонен и краен.
  • Стр. 172 / Зад. 1 - Докажете, че операторите са:
    1. монотонни
    2. компактни
  • Стр. 174 / Зад. 11 - Последователно прилагане на компактни оператори е компактен оператор.
Последно модифициране: събота, 12 ноември 2011, 17:38