matan1semestr (773486), страница 2
Текст из файла (страница 2)
Запишем таблицу истинностиA1100B A ∧ B ¬(A ∧ B) ¬A ¬B ¬A ∨ ¬B110000001011101101001111Так как столбцы ¬(A ∧ B) и ¬A ∨ ¬B совпадают, то свойство 3) доказано.Определение 1.3. Повествовательное предложение, содержащее переменную и обращающееся в высказывание при подстановке вместо переменной конкретного значения, называется предикатом. Обозначение:A(x), B(x), C(x, y).Например: x2 = 1 – предикат. Если x = 1 или x = −1, то имеем истинноевысказывание. В противном случае – ложное.Определение 1.4. Выражение "существует"называется квантором существования, обозначается ∃.
Выражение "для всех"или "для любых"называется квантором общности и обозначается ∀Кванторы используют для того, чтобы превратить предикат в высказывание.9Например: ∀ x, x2 = 1 –ложное высказывание;∃ x, x2 = 1 –истинное высказывание.Замечание.
Очевидно, что справедливы следующие равенства¬(∀ x, P (x)) = ∃ x, ¬P (x); ¬(∃ x, P (x)) = ∀ x, ¬P (x);2.Множества и операции над нимиПод множеством будем понимать некоторую совокупность объектов произвольной природы. Объекты, составляющие множество, называются элементами. Обозначаются множества A, B, X, Z и так далее.
Обозначениядля элементов a, b, c, d, x, z, y, ....Если a и b – элементы множества A, то пишут a ∈ A, b ∈ A и говорят,что a принадлежит множеству A. Множество, не содержащее ни одногоэлемента, называют пустым, обозначают ∅. Пустое множество единственно. Способы задания:1) перечислением всех элементов множества, например X = {2, 3, 8};2) с помощью характеристического свойства: X = {x : P (x)}, напримерX = {x : x2 = 1}.Определение 2.1. Пусть A и B множества.1) Множества A и B называются равными, если они состоят из однихи тех же элементов, т.е.
A = B ⇔ (x ∈ A ⇒ x ∈ B) ∧ (x ∈ B ⇒ x ∈ A).2) A ⊂ B, если любой элемент множества A является элементом множества B. Читается: A подмножество B или A включается в B илиB включает A.dfКоротко: A ⊂ B ⇐⇒ (x ∈ A =⇒ x ∈ B).Предложение 2.1. A = B ⇐⇒ A ⊂ B ∧ B ⊂ AДоказательство. A = B ⇐⇒ A и B состоят из одинаковых элементов,т.е. любой элемент x, принадлежащий A, обязательно принадлежит B илюбой элемент x, принадлежащий B, обязательно принадлежит A. Замечание.
Графически включение A ⊂ B изображается с помощьюдиаграмм Эйлера.Определение 2.2. Пусть A и B множества. Тогда101) множество, состоящее из элементов, принадлежащиходновременно∩A и B, называется пересечением. Обозначается A B;2) множество, состоящее из элементов, принадлежащих хотя бы одному∪ из множеств A или B, называется объединением. ОбозначаетсяA B;3) множество, состоящее из элементов, принадлежащих A, но не принадлежащих B, называется разностью и обозначается A \ B.aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa∩∪A BA BТаким образом, по определению∩ dfA B = {x : x ∈ A ∧ x ∈ B},∪ dfA B = {x : x ∈ A ∨ x ∈ B},A\BdfA \ B = {x : x ∈ A ∧ x ∈/ B}.Определение 2.3.
Обычно рассматриваемые множества являютсяподмножествами некоторого универсального множества. Его обозначают Ω.В этом случае разность Ω\A называют дополнением и обозначаютA′ .aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaСвойства∩ ∪ операций.∩∪ ∩1) A∪ (B∩ C) = (A∪ B)∩ (A∪ C);2)A ∪(B C) = ∩(A B) (A C);′′3) (A ∩ B) = A ∪ B ′ ;4) (A∩ B)′ = ∩A′ B ′ .5) ∪A B =∪B A – коммутативностьA B∩= B∩ A.∩∩6) ∪A (BC)=(AB)∪∪∪ CA (B C) = (A B) C – ассоциативность.Доказательство.∪ ∩∩2) x ∈ A (B C) ⇐⇒ x ∈ A ∨ x ∈ B C ⇐⇒ x∪∈ A ∨ (x ∈ ∪B∧x ∈C) ⇐⇒∪(x ∈∩A∨x∪∈ B)∧(x ∈ A∨x ∈ C) ⇐⇒ x ∈ (A B)∧x ∈ A C ⇐⇒x ∈ (A B) (A C).11Определение 2.4.
Если Aдизъюнктными.∩B = ∅, то множества A и B называютсяОпределение 2.5. Множества A1 , A2 , . . . , An называютсядизъюнктны∩ми или попарно непересекающимися, если ∀ i ̸= j Ai Aj = ∅.Замечание. Объединение множеств A1 , A2 , . . . , An обозначаютn∪Aj .
Ес-j=1ли множества A1 , A2 , . . . , An дизъюнктны, то их объединение обозначаютnn⊔∩Aj . Пересечение множеств A1 , A2 , . . . , An обозначаютAj .j=1j=13. Декартово произведение, отношения между множествамиОпределение 3.1. Пусть X, Y – два множества, x ∈ X, y ∈ Y . Тогдамножество {{x}, {x, y}} называется упорядоченной парой и обозначается (x, y).Теорема 3.1 (Основная теорема об упорядоченных парах).(x1 , y1 ) = (x2 , y2 ) ⇐⇒ x1 = x2 ∧ (y1 , y2 ).Доказательство.Необходимость.
(x1 , y1 ) = (x2 , y2 ) =⇒ {{x1 }, {x1 , y1 }} ={{x2 }, {x2 , y2 }} =⇒ x1 = x2 ∧ {x1 , y1 } = {x2 , y2 } =⇒ x1 = x2 ∧ y1 = y2 .Достаточность. x1 = x2 ∧ y1 = y2 =⇒ {{x1 }, {x1 , y1 }} = {{x2 }, {x2 , y2 }}Определение 3.2. Если X и Y два множества, то множествоdfX × Y = {(x, y) : x ∈ X ∧ y ∈ Y }называется декартовым произведением.Замечание.
Если X = {x1 , x2 , ...xn }, Y = {y1 , y2 , ...ym } –конечные множества, то элементы декартова произведения можно записать в виде прямоугольной таблицы(x1 , y1 ) (x1 , y2 )(x2 , y1 ) (x2 , y2 )······(xn , y1 ) (xn , y2 )· · · (x1 , ym )· · · (x2 , ym )······· · · (xn , ym )Таким образом, если X ♯ = n, Y ♯ = m =⇒ (X × Y )♯ = m · n12Определение 3.3. Любое подмножество R ⊂ X × Y называется отношением между множествами X и Y . Подмножество R ⊂ X × Xназывается отношением на множестве X.Определение 3.4. Пусть R ⊂ X × Y – отношение, x ∈ X.
МножествоR(x) = {y ∈ Y : (x, y) ∈ R}называют сечением отношения по элементу x. МножествоR−1 (y) = {x ∈ X : (x, y) ∈ R}называют сечением отношения R по элементу y.Определение 3.5. Если R ⊂ X × Y – отношение, то множество пар(y, x) ∈ Y × X таких, что (x, y) ∈ R, называют обратным отношениемк R и обозначают R−1 , т.е. R−1 = {(y, x) : (x, y) ∈ R}.Определение 3.6. 1) Отношение R ⊂ X ×X называется рефлексивным,если ∀ x ∈ X, (x, x) ∈ R, т.е. ∆ ⊂ R, где ∆ = {(x, x) : x ∈ X} –диагональ.2) Отношение R ⊂ X × X называется симметричным, если(x, y) ∈ R =⇒ (y, x) ∈ R3) Отношение R ⊂ X × X называется транзитивным, если(x, y) ∈ R ∧ (y, z) ∈ R =⇒ (x, z) ∈ R.4) Отношение R ⊂ X × X называется антисимметричным, если(x, y) ∈ R ∧ (y, x) ∈ R =⇒ x = yОпределение 3.7.
Отношение, которое одновременно рефлексивно, симметрично и транзитивно, называется отношением эквивалентности.Замечание. Если R отношение эквивалентности и (x, y) ∈ R, то частопишут x ∼ y. В этих обозначениях1) x ∼ x (рефлексивность);2) x ∼ y =⇒ y ∼ x (симметричность);3) x ∼ y ∧ y ∼ z =⇒ x ∼ z (транзитивность).Пример. Отношение = есть отношение эквивалентности, так как1) x = x;2) x = y =⇒ y = x;3) x = y ∧ y = z =⇒ x = z.13Теорема 3.2.
Если R есть отношение эквивалентности на множествеX, то множество X распадается на непересекающиеся классы эквивалентных элементов.Доказательство. Пусть x ∈ X и R(x) = {y ∈ X : y ∼ x} есть∪ последовательность всех элементов, эквивалентных x. Очевидно, что R(x) = X.xПокажем, что классы R(x1 ) и R(x2 ) или∩ не пересекается, или совпадает.Выбираем R(x∩ 1 ) и R(x2 ). Если R(x1 ) R(x2 ) = ∅, то все выполняется.Пусть R(x1 ) R(x2 ) ̸= ∅. Покажем, что тогда R(x1 ) = R(x2 ).В самом деле, пусть y ∈ R(x1 ) ∧ y ∈ R(x2 ) =⇒ y ∼ x1 ∧ y ∼ x2 =⇒ x1 ∼ x2 .Пусть теперь x ∈ R(x1 ), т.е.
x ∼ x1 =⇒ x ∼ x2 =⇒ x ∈ R(x2 ).Аналогично, x ∈ R(x2 ) =⇒ x ∈ R(x1 ), т.е. R(x1 ) ⊃ R(x2 ). Определение 3.8. Отношение R на X называют отношением нестрогого порядка, если1) ∀ x, (x, x) ∈ R (рефлексивность);2) (x, y) ∈ R ∧ (y, x) ∈ R =⇒ x = y (антисимметричность);3) (x, y) ∈ R ∧ (y, z) ∈ R =⇒ (x, z) ∈ R (транзитивность).Обычно, если R отношение нестрогого порядка и (x, y) ∈ R, то пишутx ≤ y.В этих обозначениях:1) x ≤ x; 2) x ≤ y ∧ y ≤ x =⇒ x = y; 3) x ≤ y ∧ y ≤z =⇒ x ≤ z.Пример.
Отношение ≤ для натуральных чисел есть отношение нестрогогопорядка.Определение 3.9. Отношение R на X называется отношением строгого порядка, если1) (x, x) ∈/ R - антирефлексивно;2) (x, y) ∈ R =⇒ (y, x) ∈/ R - антисимметрично;3) (x, y) ∈ R ∧ (y, z) ∈ R =⇒ (x, z) ∈ R - транзитивно.Если R отношение строгого порядка и (x, y) ∈ R, то часто пишут x < y.∪Теорема 3.3. Если R отношение строгого порядка, то R ∆ есть отношение нестрогого порядка.Доказательство.
Пусть R – отношение∪ строгого порядка.1) x ∈ X =⇒ (x, x) ∈ ∆ =⇒ (x, x) ∈ R ∆, т.е. рефлексивность есть.2) Пусть x ̸= y. Тогда (x, y) ∈/ ∆ =⇒ (x, y) ∈ R ∧ (y, x) ∈ R, что невозможно, т.е. ассимметричностьдоказана.∪∪3) (x, y) ∈ R ∆ ∧ (y, z) ∈ R ∆;14∪если x = y =⇒ (x, z) ∈ R ∆;∪если x ̸= y =⇒ (x, y) ∈ R или y = z =⇒ (x, z) ∈ R =⇒ ∪(x, z) ∈ R ∆.Если y ̸= z =⇒ (y, z) ∈ R =⇒ (x, z) ∈ R =⇒ (x, z) ∈ R ∆. Замечание.Эту теорему записывают, обычно, в видеx ≤ y ⇐⇒ x < y ∨ x = y.4.
Отображения, классификация отображенийОпределение 4.1. Пусть X и Y – множества, R ⊂ X ×Y – отношение.МножествоdfR(x) = {y ∈ Y : (x, y) ∈ R}называется сечением отношения R по элементу x. МножествоdfR(A) = {y ∈ Y : ∃x ∈ A, (x, y) ∈ R}называется образом множества E. МножествоdfR−1 (y) = {x ∈ X : (x, y) ∈ R}называется сечением отношения R по элементу y.Определение 4.2. Пусть R ⊂ X × Y . Отношение R называется отображением множества X в множество Y , если ∀ x ∈ X множество R(x)содержит ровно один элемент множества Y .Если R отображение X в Y , то пишут:R : X → Y.Сечение R(x) называют в этом случае образом элемента x при отображении R, сечение R−1 (y) называется прообразом элемента y.Определение 4.3. Пусть R : X → Y - отображение.
Если пара (x, y) ∈R, то соединяем точку x c точкой y стрелкой в направлении от x к y.Полученный рисунок называется графом отображения R.Определение 4.4. Пусть R : X → Y и A ⊂ X. Множество {y ∈ Y :∃ x ∈ A, y = R(x)} называется образом множества A при отображенииR.Определение 4.5. Отображение R : X → Y называется отображением X на Y , если R(X) = Y , т.е. любой элемент y ∈ Y есть образнекоторого элемента x ∈ X.15наОпределение 4.6.
Отображение R : X → Y называется взаимно однозначным, еслиx1 ̸= x2 =⇒ R(x1 ) ̸= R(x2 ).Пример. X = {x1 , x2 , x3 , x4 }, Y = {y1 , y2 , y3 }. Отображение R зададим равенствами R(x1 ) = y1 , R(x2 ) = y2 , R(x3 ) = y3 , R(x4 ) = y1 . Оно отображаетX на Y , но не является взаимно однозначным. Граф отображения R имеетвидXY- y1x1x2 y2x3 - y3x4 наОпределение 4.7. Если R : X → Y взаимно однозначно, то отображенание R−1 : Y → X, определяемое равенством R−1 (y) = x ⇐⇒ R(x) = y,называется обратным к R.Определение 4.8. Пусть R : X → Y и S : Y → Z. Тогда отображение, которое элементу x ставит в соответствие элемент S(R(x)),называется композицией или суперизацией отображений и обозначаетсяS ◦ R.Очевидно,что S ◦ R : X → Z и по определениюdf(S ◦ R)(x) = S(R(x)).наТеорема 4.1. Если R : X → Y взаимно однозначно, то1) (R ◦ R−1 )(y) = y, ∀ y ∈ Y ;2) (R−1 ◦ R)(x) = x, ∀ x ∈ X;Доказательство.
1) Пусть y = R(x) =⇒ R−1 (y) = x =⇒ (R ◦ R−1 )(y) =R(R−1 (y)) = R(x) = y и (R−1 ◦ R)(x) = R−1 (R(x)) = R−1 (y) = x. наОпределение 4.9. Отображение E : X → X, определяемое равенствомE(x) = x, называется тождественным.Таким образом, теорема 4.1 утверждает, чтона1) R−1 ◦ R есть тождественное отображение X → X;16на2) R ◦ R−1 есть тождественное отображение Y → Y .Замечание. Определение отображения часто формулируют в виде:Если каждому элементу x ∈ X поставлен в соответствие единственныйэлемент y ∈ Y , то говорят, что задано отображение множества X в Y .Замечание 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
