ВОПРОСЫ и ответы К ЭКЗАМЕНУ. Ответы к экзамену комбинаторный признак умножения. Количество битовых строк длины
![]()
|
|
| |
Свойство бинарных отношений:
1) Рефлексивность. Пусть на множестве А задано бинарное отношение R. Бинарное отношение называется рефлексивным, если для любого элемента А упорядоченная пара из этого элемента принадлежит R: для любого A(a,a) Î R. Т.е. бинарное отношениена множественазываетсярефлексивным, если всякий элемент этого множества находится в отношениис самим собой.
Матрица рефлексивного отношения на диагонали содержит 1, а граф бинарного отношения имеет петли.
2)Антирефлексивность. Бинарные отношения являются антирефлексивными, если: для любого A(a,a) Ï R.
Матрица антирефлексивного отношения на диагонали содержит 0, а граф не имеет петель.
3)Симметричность.Бинарное отношениена множестве X называетсясимметричным, если для каждой пары элементов множествавыполнение отношениявлечёт выполнение отношения. Отношениесимметрично, если
![](1120624_html_b62fd316c6779866.png)
Матрица симметричного бинарного отношения симметрична относительно главной диагонали. В графе все пары вершин соединены 2-мя противоположно направленными дугами.
4)Антисимметричночть. В математике бинарное отношениена множестве X называетсяантисимметричным, если для каждой пары элементов множествавыполнение отношенийивлечёт, или, что то же самое, выполнение отношенийивозможно только для равныхи.
| |
Матрица антисимметричного бинарного отношения не симметрична относительно главной диагонали, в графе отсутствуют противоположно направленные дуги.
5)Транзитивность.Бинарное отношение называют транзитивным, если:
![](1120624_html_611e45cc9d701d5d.png)
В графе задающего транзитивное бинарное отношение для каждой пары дуг таких, что конец первой совпадает с началом второй, существует дуга, соединяющая начало первой дуги с концом второй.
Специальные бинарные отношения:
1) Отношение Эквивалентности на множестве А это отношение, обладающее свойством рефлекисвности, симметричности и транзитивности. (Отношение равенства, отношение параллельности).
2) Отношения строгого порядка: это бинарное отношение на множестве А, обладающее свойствами антирефлексивности, антисимметричности и транзитивности.
3) Отношения нестрого порядка- бинарные отношения, обладающие свойствами рефлексивности. Антисимметричности и транзитивности.
Множество M, на котором задано отношение частичного порядка, называется частично упорядоченным. Если быть совсем точным, то частично упорядоченным множеством называется пара
![](1120624_html_b9cb46bffd9c538d.png)
![](1120624_html_a003ff4868d37130.png)
26. Граф. Ориентируемый граф.
Ориентированный граф (или сокращенно орграф) G = (V, Е) состоит из множества вершин V и множества дуг Е. Вершины также называют узлами, а дуги – ориентированными ребрами. Дуга представима в виде упорядоченной пары вершин (v, w), где вершина v называется началом, a w – концом дуги. Дугу (v, w) часто записывают как v → w и изображают в виде
![](1120624_html_f615b88ee67a384f.png)
Ориентированный граф –граф вершины которого соединены дугами
27. Отношение эквивалентности. Классы эквивалентности. Разбиение множеств.
Бинарное отношение называется Отношение эквивалентности если оно рефлексивно симметрично транзитивно. обозначение .
Классом эквивалентностиMa
называется множество всех элементовM, находящихся в отношенииRк элементуa, то есть множество
Ma={x∈M:xRa}.
Пример
Пусть M — множество всех жителей России и R — отношение эквивалентности «проживать в одном городе». Найти классы эквивалентных элементов Ma для a∈M.
Класс элементов, эквивалентных элементу a, имеет вид:
Ma={x∈M:x проживает в одном городе с человеком a}
28. Сравнения. Вычеты. Множество классов вычетов по модулю n. Сложение и умножение классов вычетов по модулю n.
Сравнение по модулю Определение. Число a делится на натуральное b с остатком r, если a = bk + r, причем 0 6 r < b и k ∈ Z . Чтобынайтиостатокучисла a приделениина b, нужно из a вычесть ближайшее число, не превосходящее a, делящееся на b.
Сравнение - Целые числа, разность которых делится на m, называются сравнимыми по модулю m. Запись: a ≡ b (mod m).
Свойства сравнений. 1. a ≡ b (mod m) ⇔числа a и b даютодинаковыеостаткипомодулю m. Замечание. Несмотря на это свойство, если вы хотите проверить сравнимы ли два числа по модулю, то чаще всего удобнее рассматривать их разность, а не пытаться найти остатки для каждого. 2. a ≡ b (mod m), c ≡ d (mod m) ⇒ a + c ≡ b + d (mod m).
При делении целых чисел на натуральное число m существует m различ- ных остатков: 0, 1, 2,…, m – 1.
Соответственно этим остаткам Z разбивается на m непересекающихся классов сравнимых друг с другом чисел,
имеющих,один и тот же остаток от деления на m. В соответствии с остат-
ками от деления на m будем обозначать эти классы 0 , 1,…, m - 1. Таким обра- зом, класс i = { m * q + i | q э Z}
для каждого i = 0, 1, 2,…, m – 1. Любой пред- ставитель класса однозначно определяет свой класс, т. е. для каждого
m *q + i класс m * q + i= i .
Поскольку английское residue – «остаток» – переводится на русский язык еще и как «вычет»,
то множество всех классов сравнимых друг с другом чисел по модулю m называют множеством
классов вычетов по модулю m и обозна- чают Z/mZ.
Кольцом называется (непустое) множество K, на котором определены две операции (сложение и умножение), обладающие следующими свойствами:
1) множество K относительно сложения образует коммутативную группу;
2) умножение ассоциативно: для любых а, b, с ∈K
(ab)c = a(bc);
3) сложение и умножение подчиняются дистрибутивному закону:
(а + b)с = ас + bc, с(а + b) = са + сb
для любых а, b, с ∈K.
При этом множество K, рассматриваемое лишь относительно операции сложения, называется аддитивной группой кольца.
Приведем некоторые примеры колец.
. Множество целых чисел с операциями сложения и умножения - кольцо целых чисел Z.
. Множество многочленов от одного неизвестного с действительными коэффициентами с операциями сложения и умножения многочленов - кольцо многочленов R[X].
. Множество классов вычетов по модулю n с операциями сложения и умножения классов - кольцо классов вычетов Zn.
29. Функция. Область определения и область значений функции. Образ и прообраз подмножества. Композиция функций.
Фундаментальную роль в математике играет понятие функции (отображения), которое является частным случаем функционального отношения.
Определение 1.Бинарное отношение f между элементами множеств А и В (то есть
![](1120624_html_cf6a88c9979bb45.png)
![](1120624_html_aca36ce790b811ca.png)
![](1120624_html_bc4ad1c812f0562f.png)
![](1120624_html_3f83f696bd8d00e0.png)
Из определения 1 следует, что бинарное отношение является функциональным, когда каждому значению первой координаты пары из f соответствует единственная вторая координата, которая обозначается через y=f(x). И говорят в этом случае, что y является функцией от x.
Определение 2.
![](1120624_html_3dfccfd4a3684341.png)
Определение 3.Функциональное отношение f между элементами множеств А и В называетсяфункциейилиотображениемА в В, если
![](1120624_html_e9c2dd3712d4f35c.png)
![](1120624_html_39557ce120157ff6.png)
Множество А называется областью определения функции, множество В -областью значения функции.
Если y=f(x), то y называетсяобразомпри отображении f точки x, а x называетсяпрообразомпри отображении f точки y.
Пусть
![](1120624_html_ea79ac9c054fbb13.png)
![](1120624_html_6b2986d9cfbd8e30.png)
![](1120624_html_9e99a228779f367a.png)
Пусть
![](1120624_html_602ef03b4bc829d7.png)
![](1120624_html_4197948aa984ea41.png)
![](1120624_html_32daa1a79e54033.png)
Композиция
Определение1.Пусть f и g – функции, причем g: A→B, f: B→C.Композицией(суперпозицией, произведением) функций f и g называется отображение A в C, значением которого для произвольного
![](1120624_html_4b59aa8438177ad9.png)
Обозначение:
![](1120624_html_6ddccea515395833.png)
![](1120624_html_a64a576747a4c72a.png)
Определение2.Отображение
![](1120624_html_94f42c5e91dd6804.png)
![](1120624_html_c0a610bff3770faa.png)
![](1120624_html_bfc501aac5760dd5.png)
Пример:Пусть
![](1120624_html_780e4a618f27f9e8.png)
![](1120624_html_27dee34fb508d076.png)
![](1120624_html_52baf5dbd8eb2724.png)
![](1120624_html_e6132a5ef38903bb.png)
![](1120624_html_4d4db771c58382d3.png)
Из примера видно, что
![](1120624_html_adc07c9023a608a9.png)
Теорема1:Пусть
![](1120624_html_a9c50bb4f2de765f.png)
![](1120624_html_9ac74a75dca00f04.png)
![](1120624_html_c20de7ba9c8073d9.png)
![](1120624_html_7a977d5b7dc8166a.png)
![](1120624_html_c43b0648ad9dfce4.png)
![](1120624_html_c52f8c60cbdd15c9.png)
Доказательство.
![](1120624_html_2eb16b74d7dd87e0.png)
![](1120624_html_7f324573a38c885b.png)
Следовательно, равенство (1) справедливо.Что и требовалось доказать.