Міністерство освіти Республіки Білорусь
Міністерство освіти і науки Російської Федерації
ГУВП «Білорусько-Російський університет»
Кафедра «Автоматизовані системи управління»
Завдання №21
з курсу «Дискретна математика»
Виконав:
студент групи АСОІ - 091
Людаговская В.В.
Перевірив:
доцент каф. АСУ, к.т.н.
Якимов А.І.
Могильов 2010
Питання 1
Нехай U - безліч точок площини, на якій задана декартова система координат. Знайти перетин множин A? B, об'єднання AUB, різниці множин A B, B A, доповнення множин A`, B`, зобразити їх на площині:
={ lt; x, y gt; | y? x2}, B={ lt; x, y gt; | - 3? y? 5, - 7? x? 1}.
Рішення:
За визначенням:
1.
.
.
.
.
.
Питання 2
[Довести здійснимість наступного співвідношення.
Доказ:
Нехай,,.
а) Розглянемо. Знайдемо безліч. За визначенням
.
Позначимо через x всі елементи, які задовольняють наступним умовам:,, а через у всі елементи з, такі що.
Отже,,.
За визначенням декартового твори множин
(1)
б) Розглянемо вираз.
За визначенням декартового твори множин
;
.
Тоді складається з безлічі всіх упорядкованих пар lt; a, c gt ;, lt; b, c gt; таких, що a=b=x, c=y, т. е.
(2)
З рівності правих частин співвідношень (1) і (2) випливає, що.
Питання 3
Побудувати композиції відображень і; перевірити, чи є вони ін'єкційних, сюр'ектівнимі або биективная.
.
Рішення:
Композиція функцій не є сюр'єкція, так як немає жодного елемента, для якого y=0 є образ. Композиція функцій не є ін'єкцією, так як різним може відповідати одне значення. Композиція не є біекція.
Композиція функцій і є відображенням
Питання 4
На множинах А і В задані відносини порядку і відповідно і поставлено відображення, де. Визначити, чи є воно ИЗОТОНА, изоморфизмом або автоморфізмом.
А={2,3,6,12,24}, B={1,2,3,5,6,10,15,30}; f (2)=1; f (3)=1; f (6)=5; f (12)=10; f (24)=30; =: {х дільник у}.
Рішення:
Нам відомі образи функції f:. f (2)=1; f (3)=1; f (6)=5; f (12)=10; f (24)=30.
Безліч А - решітка, в якій можна виділити два ланцюги. Для ланцюга 261 224 відображення f зберігає порядок, так як 151030, т.е
f (2) f (6) f (12) f (24). Для ланцюга 361224 відображення f також зберігає порядок, так як 151030, тобто f (3) f (6) f (12) f (24). Отже, відображення ИЗОТОНА. Відображення також є ізоморфізмом, оскільки зворотне відображення f зберігає порядок: для значень f (2) f (3) (1=1) прообрази 2 і 3 порівнянні.
Отже, відображення f ИЗОТОНА і є ізоморфізмом.
Питання 5.
Перевірити повноту системи функцій
Рішення:
Згідно з теоремою Посту, для повноти системи функцій необхідно і достатньо, щоб до неї входили хоча б одна немонотонна, хоча б одна нелінійна, хоча б одна несамодвойственная, хоча б одна не зберігає нуль і хоча б одна не зберігає одиницю функції. Позначимо:
Т0 - клас функцій, що зберігають 0;
T1 - клас функцій, що зберігають 1;
S - клас самодвоїстих функцій;
М - клас монотонних функцій;
L - клас лінійних функцій.
Для досліджуваної системи складемо таблицю Посту. Якщо функція входить у функціонально замкнутий клас, то в таблиці Посту у відповідній клітинці ставиться знак «+», інакше - знак «-».
Для дослідження системи на повноту побудуємо таблиці
істинності функцій.
. Позначимо.
yxf1 (x, y) +001011100111
Функція f (x) не зберігається 0 і 1, оскільки на нульовому наборі вона приймає значення 1, а на одиничному - 0. Очевидно, що дана функція немонотонна. Функція самодвоїстих, оскільки на протилежних наборах функція приймає протилежні значення.
Для перевірки лінійності побудуємо...
