Відповідності і відображення

Відповідності на множинах володіють такими ж властивостями, як і бінарні відношення, тобто відповідність QÍА² є: рефлексивною, якщо якщо (a,a)ÎQ (або aQa) для всіх aÎА, що беруть участь у відповідності; антирефлексивною, якщо для всіх (a,b)ÎQ має місце нерівність a≠b; симетричною, якщо для всіх пар (a,b)ÎQ існують пари (b,a)ÎQ; антисиметричною, якщо для всіх aÎА і bÎА із (a,b)ÎQ і (b,a)ÎQ слідує a=b; транзитивною, якщо для всіх aÎА, bÎА і cÎА з того що (a,b)ÎQ і (b,c)ÎQ слідує (а,c)ÎQ, а також лінійною, якщо b=a, aQb і bQa для всіх a,bÎА.

Читачеві надається можливість самостійно виявити особливості матриць і графів, якими задаються відповідності, що володіють такими властивостями.

Для кожної відповідності q=(X, Y, Q), QÍX´Y існує обернена відповідність, яка отримується, якщо дану відповідність q розглядати в зворотному напрямку, тобто визначати елементи xÎX, з якими зіставляються елементи yÎY. Відповідність, обернена до відповідності q, позначається так: q^–1=(Y, X, Q^–1), де Q^–1ÍY´X, причому (Q^–1)^–1=Q.Зрозуміло, що перехід від Q до Q^–1 здійснюється взаємною перестановкою координат кожної впорядкованої пари. Слід зазначити, що при переході від Q до Q^–1 область визначення стає областю значень і навпаки. Матриця графіка відповідності Q^–1 – це транспонована матриця графіка Q.

Означення 1.21. Якщо матриця графіка Q прямої відповідності (X, Y, Q) співпадає зі своєю транспонованою відносно головної діагоналі матрицею, то відповідність (X, Y, Q) називається взаємно однозначною. При цьому транспонована матриця є матрицєю графіка Q^–1 відповідності (Y, X, Q^–1), оберненої до прямої відповідності (X, Y, Q).

Означення 1.22. Композицією відповідностей (як і будь-яких відношень) називається послідовне застосування двох відповідностей, тобто композиція p○q відповідностей q і p – це операція над трьома множинами X, Y, Z, на яких визначені дві відповідності: q=(X, Y, Q), QÍX´Y; p=(Y, Z, P), PÍY´Z, причому область значень першої відповідності (q) збігається з областю визначення другої відповідності (p): Пр2Q = Пр1Р.

Для опису відповідностей між множинами використовують поняття відображення однієї множину в іншу, як частковий випадок відповідності. Для задання відображення потрібно вказати: множину А, яка відображається, тобто область визначення відображення; множину В, в яку відображається область визначення, тобто область значень відображення; закон відповідності між цими множинами, за яким для елементів першої множини вибираються елементи із другої множини.

Означення 1.23. Відображенням множини А в множину В називається відповідність φ: А→В (за іншою позначкою ), згідно якої кожному елементу множини А ставиться у відповідність не більш ніж один елемент множини В. Елемент bÎВ називається образом елемента aÎА, а останній, у свою чергу, називається прообразом елемента bÎВ.

Іншими словами, відповідність (А, В, F), де F=А´В, називаеться відображенням А в В, якщо область визначення відповідності збігається з її областю відправлення: Пр1F=А.

Запись φ:А→В означає, що множина В складається з образів всіх элементів множини А (позначка образу (a)φ). Згідно означення відображення, кожному елементу bÎВ (образу відповідних елементів aÎА) може відповідати один або більше елементів aÎА (прообразів відповідного елемента bÎВ), а кожному елементу aÎА може відповідати не більше одного елемента bÎВ, тобто відображення є однозначним. Цією обставиною клас відображень виділяється із загального класу відповідностей як частковий випадок. Помітимо, що так само як відповідність загального виду, відображення не передбачає обов’язкової участі у відповідності всіх елементів bÎВ.

Кількість можливих відображень множини А в множину В визначити нескладно. Припустимо, що потужності множин А і В дорівнюють n і m відповідно. Побудувавши матрицю выдображення (А, В, F) розмірністю n´m, дійдемо висновку, що кількість можливих відображень дорівнює mⁿ.

Означення 1.24. Відображення множини А в множину В називається сюр’єкцією, якщо для кожного bÎВ існує елемент aÎА такий, що має місце відповідність aφb.

Якщо відображення φ:А→В є сюр’єкцією, то на його стрілковій діаграмі (графі) в кожну точку, що позначає елемент bÎВ, входить принаймі одна стрілка і всі bÎВ беруть участь у відображенні. Очевидно, що сюр’єкція множини А в множину В можлива тільки в тому випадку, якщо потужності цих множин знаходяться у співвідношенні |А|≥|В|.

Означення 1.25. Відображення множини А в множину В називається ін’єкцією, якщо різним елементам aÎА відповідають різні елементи bÎВ, тобто для a_i,a_jÎА, a_i≠a_j мають місце відповідності a_iφb_i та a_jφb_j такі, що b_i≠b_j.

Якщо відображення φ:А→В є ін’єкцією, то на його графі в кожну точку, що позначає елемент bÎВ, входить не більше ніж одна дуга. Очевидно, що ін’єкція множини А в множину В можлива тільки в тому випадку, якщо потужності цих множин знаходяться у співвідношенні |А|≤|В|.

Означення 1.26. Якщо відображення φ: А→В є одночасно сюр’єктивним і ін’єктивним, то оно називається взаємно-однозначним відображення множини А на множину В, або бієкцією А на В.

Для бієкції має виконуватись рівність |А|=|В|.

Означення 1.27. Відображення f: X→Y (або )називається функцією, якщо воно є однозначним, тобто якщо для будь-яких пар (x₁,y₁)Îf та (x₂,y₂)Îf з x₁=x₂ випливає, що y₁=y₂.

Для функції можна записати таке визначення: f={(x,y)ÎX´Y| y=f(x)}, тобто функцією є множина, елементами якої є пари (x, y), які беруть участь у функціональному відображенні. Значення y=f(x) для будь-якої пари (x,y)Îf називається функцією від х. Елемент xÎX називають аргументом функції y=f(x). Символичне позначення функціональної залежності y від x може бути і одним з таких: , x→y, xfy.

Якщо область визначення функції f містить тільки один елемент, то її називають функцією-константою.

Для задання функції використовуються такі способи: перерахуванням всіх пар (x,y) елементів множин X і Y; формулою y=f(x), xÎX, yÎY, якщо X та Y - множини чисел (натуральних, цілих, дійсних, комплексних тощо); у вигляді графіка (x,y)Îf, xÎX, yÎY, якщо X та Y - множини дійсних чисел.

Кількість аргументів функції (їх називають ще незалежними змінними) може бути більше одиниці. Наприклад, функція двох змінних f=f(x, y), де xÎX, yÎY, має областю визначення декартов добуток X´Y. Формально таку функцію можна означити так: f={(x,y,z)ÎX´Y´Z| y=f(x, y)}. Аналогічно означаються функції більшого числа змінних. Додавання, віднімання, множення і ділення є двомісними (бінарними) функціями на R (множині дійсних чисел), тобто функціями виду f: R²→R, або z=f(x,y),де x, y, zÎR.

Оскільки функції відносяться до класу однозначних відображень, то ім притаманні всі властивості останніх. Зокрема, функції можуть бути сюр’єктивними, ін’єктивними і бієктивними, а в останньому випадку функціональна залежність є взаємно однозначною, тобто функція f^-1: Y→X, обернена до функції f: X→Y, буде також однозначною.

Композиція функцій f: X→Y і g: Y→Z визначає множину значень zÎZ, що відповідають за за послідовно застосованими законами f і g елементам xÎX: z=(g∘f)x=g(f(x)). Функцію f, отриману з функцій g, q, …, u підстановкою їх одне в одне з перейменуванням аргументів, називають суперпозицією функцій g, q, …, u. Наприклад, суперпозицією є функція р=f(z), де z=g(y), y=q(x), тобто р=f(g(q(x))). Вираз, що описує суперпозицію з використання символів аргументів та знакив математичних операцій, називається формулою.

Більш загальним видом відображення, ніж функція, є функціонал, який встановлює залежність між множиною чисел та множиною функцій (іншими словами – числові оцінки функцій). Приклад функціонала: .

За допомогою функціоналів визначають, зокрема, цільові функції (мінімізації, максимізації функціоналу) в задачах оптимального управління динамічними системами.

Ще більш загальним видом відображення є оператор, ним встановлюється така відповідність між двома множинами функцій, що кожній функції з однієї множини відповідає певна функція з іншої. Наприклад, інтеграл Лапласа є оператором (з умовним позначенням f(t)lf(р), який здійснює інтегральне перетворення множини функцій f(t) дійсної перемінної t, 0<t<¥, у множину функцій f(р) комплексної перемінної р. Інтегральне перетворення Лапласа широко використовується в теорії автоматичного управління.

Розділ 2 Елементи математичної ЛОГІКИ

Математична логіка – це наука, предметом дослідження якої є методи логічного виведення. При цьому розглядаються форми, а не сенс суджень. Формалізація процедур логічного виведення базується на поняттях істинності та хибності посилань і висновків, причому формалізована оцінка істинності та хибності здійснюється за допомогою символів 1 та 0 відповідно, тобто в алфавіті алгебри логіки (алгебри Буля). У даному розділі розглядаються основні поняття об’єктів алгебри логіки, її закони та методи приведення логічних функцій до виду, придатного для вирішення задач побудови моделей обчислювальних і керуючих пристроїв дискретної дії.