Краткие ответы на экзаменационные вопросы по дисциплине "Дискретная математика" (Предмет дискретной математики. Метод Блейка-Порецкого), страница 3

Соглашение о приоритетах:

1. Отрицание

2. Конъюнкция

3. Дизъюнкция

4. Импликация

5. Эквиваленция

16. Сложные высказывания.

A v¬B v¬A<=>¬B лили

17. Предикаты

Выск-е (сложное) получают не только с помощью лог-х операций, но и с помощью кванторов. В ДМ исп-ся 2 квантора: квантор всеобщности  и квантор существования

Предикат – выск-е, содерж-е одно или несколько переменных.

Х – есть нечетное число

Х – целочисленная пер-я

(xÎA)P(x)

Для любого х из мн-ва А истинно Р(х)

(x,уÎA) t,P(x,y,t)

Для любых х,у из мн-ва А сущ-т t, что истинно P(x,y,t)

18. Кортеж

Рассм-м А и В. Неупорядоченная пара на мн-вах А и В есть мн-во {a,b}, где aÎA, bÎB или aÎВ, bÎА.

Упорядоченная пара на мн-вах А и В обозн-ся (а, b) , опр-ся не только самими эл-ми aÎA, bÎB, но и порядком записи. Сущ-ю роль порядка, в к-м записываются эл-ты в упоряд-й паре, фикс-т в опр-и равенства упорядоченных пар.

2 пары (а, b) и (а’, b’) наз-ся равными, если они определены на мн-х А и В  и a=a’ и b=b’

Кортеж  - упорядоченный набор (а₁,…,a_n) на мн-х А,…A_n хар-ся не только входящими в него эл-ми, но и порядком.

Число n – длина кортежа (размерность), a_i – и –тая проекция (компонента) кортежа.

Кортеж, не содержащий ни одной компоненты (т.е. кортеж длины нуль), называется пустым

19. Декартово произведение.

Мн-во всех кортежей длины N на мн-х А,…A_n наз-т Декартовым (прямым) произведением мн-в А,…A_n и обозн-т: А₁А₂…A_n

На языке предикатов:

={(a₁,…,a_n):( a₁ÎA₁, a_nÎA_n) }

Св-ва:

А(BÈC)=(AB) È (AC)

A (BÇC)=(AB) Ç (AC)

AÆ=ÆA=Æ

20. Соответствие.

Если элементу хÎА сопоставлен не один, а несколько образов в мн-ве В, то говорят, что задано соответствие из мн-ва А в мн-во В ((x))

Область определения соответствия

 AB из мн-ва А в мн-во В – это мн-во всех первых компонент упорядоченных пар из :

D()={x:( yÎB)(x,yÎ)

Область знач-й соотв-я  - это мн-во всех вторых компонент упорядоченных пар из :

R:()={y:( xÎA)(x,yÎ)

21.Бинарное соотношение

Соотв-е АA из мн-ва А в себя, т.е. подмножество мн-ва А², наз-т бинарным отношением на множестве А.

Отображение f из мн-ва А в мн-во В считается заданным, если каждому эл-ту х, принадлежащему мн-ву А сопоставлен единственных эл-т у, принадлежащий В

f:AB

х-образ эл-та у f(x), у – прообраз х

f:AB наз-т инъективным, если каждый эл-т из области его значений имеет единственный прообраз, т.е. из f(x₁)=f(x₂) следует, что x₁=x₂

f:AB наз-т сюръективным, если его область значений совпадает со всем множеством В

f:AB наз-т биективным, если оно одновременно явл-ся и инъективны и сюръективным

Биекция А на себя – автоморфизм

22. Натуральные числа, их св-ва.

Системой натуральных чисел наз-ся опр-е фиксированное мн-во эл-в, к-е исп-ся при счете предметов, т.е. 1,2,3…, n

На мн-ве нат-х чисел определены св-ва:

1. на N определена бинарная операция сложения, которая коммутативна и ассоциативна

2. на N определена бинарная операция умножения, которая коммутативна и ассоциативна.

3. Сложение и умножение на N связаны соотношением дистрибутивности.

4. на N определено отношение сравнения числе по величине.

а)  для а, b из мн-ва N выполняется только одно из соотн-й a>b, b>a, a=b (линейность)

б) для а, b из мн-ва N выполняется соотн-е a<b титтк сущ-т какой-то xÎN, такой что a+x=b (пол-сть)

в) в любом мн-ве М, явл-ся подмножеством мн-ва N найдецца мин-е число а; a<=x для любого xÎM (миним-сть)

г) для любого а из мн-ва N имеет место равенство 1* a =a (св-ва сущ-я единичного эл-та)

дополнительные свойства:

- сокращение сложения если а+х=а+у, то х=у

- сокращение умножения если а*х=а*у, то х=у

- трансзитивности если a<b, b<c, то a<c

- стаб-сти слож-я для любых a,b,cÎN, если a<b, то a+с<b+с

- стаб-сти умнож-я для любых a,b,cÎN, если a<b, то a*с<b*с

- для любых a,bÎN, где а1 a*b>b