Алгебраические операции и их свойства
| Разделы | Объекты | Операции | Свойства операций |
| Общее понятие алгебраической операции | а, b, c, d… | *; ○; □... | 1. Коммутативность: а * b = b * а 2. Ассоциативность: (а * b) * с = а * (b * с) 3. Дистрибутивность слева: с ○ (а * b) = (с ○ а) * (с ○ b) справа: (а * b) ○ с = (а ○ с) * (b ○ с) 4. Существование нейтрального элемента е: а * е = е * а = а 5. Существование поглощающего элемента р: а * р = р * а = р |
| Теория множеств | множества А, В, С, … | пересечение Ç объединение È разность \(дополнение (…)1) декартово произведение ´ | 1. А Ç В = В Ç А А È В = В È А 2. (А Ç В) Ç С = А Ç (В Ç С) (А È В) È С = А È (В È С) 3. (А È В) Ç С = (А Ç С) È (В Ç С) (А Ç В) È С = (А È С) Ç (В È С) (А \В)Ç С = (А Ç С)\(В Ç С) (А \В)´ С = (А ´ С)\(В´ С) (А Ç В)\С = (А \С)Ç (В \С) (А È В)\С = (А \С)È (В \С) (А Ç В)´ С = (А ´ С) Ç (В´ С) (А È В)´ С = (А ´ С) È (В ´С) 4. А ÈÆ= Æ ÈА = А 5. АÇ Æ=Æ ÇА = Æ 6. С \(А Ç В) = (С \А) È (С \В) С \(А È В) = (С\А)Ç (С \В) |
| Элементы математической логики | высказывания А, В, С, … высказывательные формы А(х), В(х; у), С(z), … | конъюнкция Ù дизъюнкция Ú отрицание Ø ¯ импликация Þ эквиваленция Û | 1. А Ù В = В Ù А А Ú В = В Ú А А Û В = В Û А 2. (А Ù В) ÙС = А Ù (В Ù С) (А Ú В)Ú С = А Ú (В Ú С) 3. (А ÚВ) Ù С = (А Ù С) Ú (В Ù С) (А Ù В) ÚС = (А Ú С) Ù (В Ú С) 4. А Ù 1 = 1 Ù А = А АÚ 0 = 0 ÚА = А 5. А Ù 0 = 0 Ù А = 0 А Ú1 = 1Ú А = 1 6. Ø(А Ú В) = ØА Ù ØВØ(А Ù В) = ØА Ú ØВ |
| Арифметические действия на числовых множествах | Числа а, b, c, d, … | сложение + вычитание – умножение · деление: | 1. а + b = b + a a · b = b · a 2. (a + b) + c = a + (b + c) (a · b) · c = a · (b · c) 3. (a + b) · c = (a · c) + (b · c) (a – b) · c = (a · c) – (b · c) (a + b):c = (a: c) + (b: c) (a – b): c = (a: c) – (b:c) 4. а + 0 = 0 + а = а а · 1 = 1 · а = а 5. а · 0 = 0 · а = 0 |
Свойства бинарных отношений
| Название | Определение | Вид графа | Пример | |||
Рефлексивность
| Отношение Р, заданное на множестве М, называется рефлексивным, если каждый элемент этого множества связан сам с собой этим отношением. Р рефлексивно Û "аÎМ, аРа | Около каждой точки графа есть петля: · · · · | Р: «число х равно числу у » на множестве чисел. «" х, х = х »– верно, следовательно отношение «быть равными» рефлексивно. | |||
Антирефлексивность
| Отношение Р, заданное на множестве М, называется антирефлексивным, если ни один элемент этого множества не связан сам с собой этим отношением.
Р антирефлексивно Û "аÎМ, 
| Нет ни одной точки с петлей: · · · · | Р: «человек х выше человека у » на множестве людей. «" х, человек х выше человека х »– не верно, рефлексивность не выполняется; «" х, человек х не выше человека х » – верно, следовательно отношение «быть выше» антирефлексивно. | |||
Симметричность
| Отношение Р, заданное на множестве М, называется симметричным, если для любых двух элементов этого множества, из того, что первый элемент связан со вторым, следует, что и второй связан с первым. Р симметричноÛ ("а, bÎМ, аРb Þ bРа) | Каждой стрелке графа есть обратная (все стрелки графа двойные): · · · · | Р: «слово х имеет тот же корень, что и слово у » на множестве слов. «" х,у; если слово х имеет тот же корень, что и слово у, то слово у имеет тот же корень, что и слово х » – верно, следовательно отношение «иметь один и тот же корень» симметрично. | |||
Антисимметричность
| Отношение Р, заданное на множестве М, называется антисимметричным, если для любых двух элементов этого множества, из того, что первый элемент связан со вторым, следует, что второй не связан с первым.
Р антисимметрично Û
("а,bÎМ, а¹b и аРb Þ  )
| Нет ни одной обратной стрелки (все стрелки графа одинарные): · · · · | Р: «арбуз х тяжелее арбуза у » на множестве арбузов. «" х,у; если арбуз х тяжелее арбуза у, то арбуз у нетяжелее арбуза х » – верно (т.к. арбуз у легче арбуза х), следовательно отношение «быть тяжелее» антисимметрично. | |||
Транзитивность
| Отношение Р, заданное на множестве М, называется транзитивным, если для любых трех элементов этого множества, из того, что первый элемент связан со вторым, а второй связан с третьим, следует, что первый связан с третьим. Р транзитивно Û ("а,b,сÎМ, аРb и bРс Þ аРс) | Для любых трех точек графа выполняется «правило треугольника» (правило сложения векторов по правилу треугольника): · · · · | Р: «город х находится восточнее города у » на множестве городов России. «" х,у,z; если город х находится восточнее города у и город у находится восточнее города z, то город х находится восточнее города z» - верно, следовательно отношение «находиться восточнее» транзитивно. | |||
Антитранзитивность | Отношение Р, заданное на множестве М, называется антитранзитивным, если для любых трех элементов этого множества, из того, что первый элемент связан со вторым, а второй связан с третьим, следует, что первый не связан с третьим.
Р антитранзитивно Û
("а,b,сÎМ, аРb и bРс Þ  )
| Для любых трех точек графа, если есть три последовательно связанных элемента, то нет связи между первым и третьим элементом: · · · · | Р: «прямая х перпендикулярна прямой у » на множестве прямых плоскости. «" х,у,z; если прямая х перпендикулярна прямой у и прямая у перпендикулярна прямой z, то прямая х не перпендикулярна прямой z » - верно (прямые х и z параллельны), следовательно отношение «быть перпендикулярным» антитранзитивно. | |||
Связанность
| Отношение Р, заданное на множестве М, называется связанным, если любые два не равные между собой элемента связаны между собой. Р связанноÛ ("а,bÎМ, а¹b, аРb или bРа) | Все точки графа связаны между собой стрелкой (одинарной или двойной): · · · · | Р: «число х больше числа у» на множестве чисел. «" х,у; при х ¹ у, верно х > у или у > х » - верно, следовательно отношение «быть больше» является связанным. |
Операции над множествами их свойства. 
| Операции | ОБЪЕДИНЕНИЕ | ПЕРЕСЕЧЕНИЕ | РАЗНОСТЬ | ДОПОЛНЕНИЕ | ДЕКАРТОВО ПРОИЗВЕДЕНИЕ | |||
| Определение | Объединением множеств А и В называется множество, состоящее из элементов, входящих хотя бы в одно из данных множеств. хÎ АÈВ Û х ÎА или хÎ В | Пересечением множеств А и В называется множество, состоящее из элементов, входящих в каждое из данных множеств. х Î АÇВ Û х Î А и х Î В | Разностью множеств А и В называется множество, состоящее из элементов, входящих во множество А, но не входящих во множество В. хÎ А\ В Û х Î А и х Ï В |
Дополнением множества. В до множества А, при условии, что В является подмножеством А, называется множество, состоящее из элементов, входящих во множество А, но не входящих во множество В.
при В Í А
хÎ  Û хÎ А и хÏ В
| Декартовым произведением множеств А и В, называется множество, состоящее из всех упорядоченных пар, в которых первой компонентой является элемент множества А, а второй – элемент множества В. А´В ={(а;b)| аÎА и bÎ В} | |||
| Графическое изображение |
 А
В
А È В
|
 А
В
А Ç В
|
 А
В
А \ В
|
 А
В
|
А ´ В
| |||
| Д и а г р а м м ы Э й л е р а - В е н н а | график | |||||||
| Операции | ОБЪЕДИНЕНИЕ | ПЕРЕСЕЧЕНИЕ | РАЗНОСТЬ | ДОПОЛНЕНИЕ | ДЕКАРТОВО ПРОИЗВЕДЕНИЕ | |||
| Свойства операций | А È В = В È А (А È В) È С = А È (В È С) (АÈВ)ÇС=(А ÇС) È (ВÇС) (АÇВ)ÈС=(АÈС)Ç(ВÈС) (АÈВ)\ С=(А\ С)È(В \ С) (АÈВ)´С =(А´С)È(В´С) С\ (АÈВ) = (С\ А) Ç (С\В) С\ (АÇВ) =(С\ А) È (С\ В) | А Ç В = В Ç А (А Ç В) Ç С = А Ç (В Ç С) (АÈВ)ÇС=(АÇС) È (ВÇС) (АÇВ)ÈС=(АÈС)Ç(ВÈС) (АÇВ)\С=(А\С)Ç(В\С) (А\ В)ÇС=(АÇС)\ (ВÇС) (АÇВ)´С=(А´С)Ç(В´С) С\ (АÇВ) =(С\ А) È (С\ В) С\ (АÈВ) = (С\ А) Ç (С\ В) | (АÈВ)\ С=(А\С)È(В\С) (АÇВ)\С=(А\С)Ç(В\С) (А\ В)ÇС=(АÇС)\ (ВÇС) (А\ В)´С = (А´С) \ (В´С) С\ (АÇВ) =(С\ А) È (С\ В) С\ (АÈВ) = (С\ А) Ç (С\ В) | В Ë А, - не существует
(АÈВ)  A  Ç B
(АÇВ) A È B
| (АÈВ)´С =(А´С)È(В´С) (АÇВ)´С=(А´С)Ç(В´С) (А\ В)´С = (А´С)\ (В´С) | |||
| Частные случаи | А ÈÆ = Æ È А = А А ÈА = А È А = А АÌВ, А È В = В | АÇ Æ =Æ Ç А = Æ АÇ А =А Ç А = А АÌВ, А Ç В = А | А\ Æ = А
Æ\ А = Æ
А\ А = Æ
АÌВ, А\ В = Æ
В\ А = 
| A  = Æ
Æ = А
|
Логические операции и их свойства
| Операции | КОНЪЮНКЦИЯ | ДИЗЪЮНКЦИЯ | ОТРИЦАНИЕ | ИМПЛИКАЦИЯ | ЭКВИВАЛЕНЦИЯ | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Логическая связка | …и … | …или… | Неверно, что… | Если…, то… | … тогда и только тогда, когда … | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Символ | Ù | Ù |
Ø, `
| Þ | Û | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| над высказываниями: | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Определение | Конъюнкцией высказываний называется составное высказывание, полученное из элементарных высказываний при помощи логической связки «и», и истинное только когда истинны все составляющие его высказывания. | Дизъюнкцией высказываний называется составное высказывание, полученное из элементарных высказываний при помощи логической связки «или», и истинное когда истинно хотя бы одно из составляющих его высказываний. | Отрицанием высказывания называется составное высказывание, полученное из элементарного высказывания при помощи логической связки «не», и истинное когда исходное высказывание ложно. | Импликацией высказываний называется составное высказывание, полученное из элементарных высказываний при помощи логической связки «если…, то… », и ложное только когда первое высказывание истинно, а второе высказывание – ложно. | Эквиваленцией высказываний называется составное высказывание, полученное из элементарных высказываний при помощи логической связки «..тогда и только тогда, когда..», и истинное когда составляющие его высказывания имеют одинаковое значение истинности. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Таблица истинности |
|
|
|
|
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| над высказывательными формами: | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Определение | Конъюнкцией высказывательных форм называется составная высказывательная форма, полученная из элементарных при помощи логической связки «и», и принимающая значение истины только когда становятся истинными высказываниями все составляющие его высказывательные формы. | Дизъюнкцией высказывательных форм называется составная высказывательная форма, полученная из элементарных при помощи логической связки «или», и принимающая значение истины когда становится истинным высказыванием хотя бы одна из составляющих его высказывательных форм. | Отрицанием высказывательной формы называется составная высказывательная форма, полученная из элементарной при помощи логической связки «не», и принимающая значение истины когда исходная высказывательная форма становится ложным высказыванием. | Импликацией высказывательных форм называется составная высказывательная форма, полученная из элементарных при помощи логической связки «если.., то..», и принимающая значение лжи только когда первая высказывательная форма становится истинным высказыванием, а вторая высказывательная форма –ложным высказыванием. | Эквиваленцией высказывательных форм называется составная высказывательная форма, полученная из элементарных при помощи логической связки ««..тогда и только тогда, когда..», и принимающая значение истины когда составляющие его высказывательные формы становятся высказываниями с одинаковым значением истинности | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Множество истинности |
 Х
ТА
ТВ
ТАÙВ = ТА Ç ТВ
|
 Х
ТА
ТВ
ТАÚВ = ТА È ТВ
|
 Х
ТА
Т`А = (ТА)¢Х
|
 Х
ТА
ТВ
ТАÞВ = (ТА\В)¢Х
|
  Х
ТА
ТВ
ТАÛВ = ТАÙВ È (ТАÚВ)¢Х
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Свойства операций | А Ù В = В Ù А (А Ù В) ÙС = А Ù (В Ù С) (АÚВ)ÙС=(А ÙС)Ú (ВÙС) (АÙВ)ÚС=(АÚС) Ù (ВÚС) А Ù ØА = 0 Ø(А Ú В) = ØА Ù ØВØ(А Ù В) = ØА Ú ØВ | А Ú В = В Ú А (А Ú В)Ú С = А Ú (В Ú С) (АÚВ)ÙС= (АÙС)Ú(ВÙ С) (АÙВ)ÚС=(АÚС) Ù (ВÚС) А ÚØА = 1 Ø(А Ú В) = ØА Ù ØВØ(А Ù В) = ØА Ú ØВ | А Ù ØА = 0 А ÚØА = 1 Ø(А Ú В) = ØА Ù ØВØ(А Ù В) = ØА Ú ØВ | (АÞВ) Ù(ВÞА) = А Û В АÞВ = ØВ Þ ØА | А Û В = В Û А | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Частные случаи | А Ù 1 = 1 Ù А = А А Ù 0 = 0 Ù А = 0 | АÚ0 = 0 ÚА = А А Ú1 = 1 Ú А = 1 | Логическое следование
При условии ТА Ì ТВ
Х
ТА ТВ
ТАÞВ = Х
В(х) логически следует из А(х);
А(х) – достаточное условие для В(х), а
В(х) – необходимое условие для А(х).
| Равносильность
При условии ТА = ТВ
Х
ТА ТВ
ТАÛВ = Х
А (х) логически следует из В (х); а
В(х) логически следует из А(х);
А(х) – необходимое и достаточное условие для В(х), а
В(х) – необходимое и достаточное условие для А(х).
|
