Page 52 - 2589

2 [ 2 ( ,  k k  ) 1 ]  , де k  , 0  , 1  2 . Таким чином, область визначення
композиції може бути вужчою від областей визначення обох

початкових функцій і навіть виявитися порожньою.
Приклад 3.31: Множина K  {k ,...,k } команд ЕОМ
1 m
відображається в машинні коди ЕОМ, тобто в натуральні числа.
Кодувальна функція  має тип K  N . За допомогою

суперпозиції цієї функції та арифметичних функцій стають
можливими арифметичні дії над командами (які самі по собі не є
числами), тобто ( k )  (  k ), (  k )  4 і т.д.
1 2 1

Приклад 3.32: Кожне натуральне число n єдиним способом
розкладається на добуток простих чисел. Тому якщо домовитися

розташовувати прості дільники n у певному порядку (наприклад,

i
у порядку неспадання), то матимемо функцію (nq ) типу N   N ,
i1
яка відображає N у множину векторів довільної довжини.

Наприклад, ( q 42 )  7 , 3 , 2 ( ),q ( 23 )  ( 23 ),q ( 100 )  ) 5 , 5 , 2 , 2 ( . Це
відображення не є сюр'єктивним, оскільки в область значень q не

входять вектори, для компонент яких не виконується умова
неспадання, а також вектори з непростими компонентами

3.7 Типиві відношення

3.7.1 Відношення еквівалентності

Відношення еквівалентності є експлікацією (перекладом

інтуїтивних уявлень у ранг строгих математичних понять) таких
слів, як «подібність», «нерозрізненість», «взаємозамінність»,
«рівносильність».

Бінарне відношення в множині X називається відношенням
еквівалентності (позначається « ~ »), якщо виконуються такі
властивості:

 рефлексивність (x ~ ) x ,

 симетричність (x ~ y  y ~ x)
 транзитивність (x ~ y  y ~ z  x ~ ) z

Найважливіше значення відношення еквівалентності полягає
в тому, що воно задає ознаку для розбиття множини X на
непересічні підмножини.

Приклад 3.33: Приклади відношень еквівалентності

52