Ответы: Архив шпаргалок для РК и экзамена
Описание
Характеристики ответов (шпаргалок)
Список файлов
- Архив шпаргалок для РК и экзамена
- Булева функция.doc 2,36 Mb
- Графы.doc 72 Kb
- Для подготовки к экзамену.pdf 106,56 Kb
- Матрица смежности.PNG 15,19 Kb
- Свойства операций над множествами.png 30,75 Kb
- Шпаргалка.doc 1,15 Mb
- Шпорки
- img007.jpg 61,21 Kb
- img008.jpg 68,31 Kb
- img009.jpg 74,08 Kb
- img010.jpg 66,97 Kb
- img016.jpg 18,38 Kb
- img017.jpg 59,82 Kb
- img018.jpg 23,37 Kb
- img019.jpg 8,76 Kb
- img031.jpg 53,23 Kb
- img032.jpg 53,09 Kb
- img033.jpg 82,33 Kb
- img034.jpg 57,9 Kb
- img035.jpg 13,97 Kb
- img037.jpg 51,52 Kb
- img038.jpg 55,31 Kb
- img041.jpg 19,12 Kb
- img043.jpg 59,97 Kb
- img045.jpg 33,26 Kb
- img046.jpg 12,02 Kb
- img047.jpg 18,66 Kb
- img048.jpg 6,53 Kb
- img049.jpg 91,26 Kb
- img051.jpg 8,38 Kb
- img053.jpg 54,93 Kb
- img054.jpg 82,41 Kb
- img055.jpg 44,54 Kb
- img056.jpg 47,42 Kb
- img057.jpg 46,09 Kb
- img058.jpg 13,65 Kb
- img059.jpg 14,82 Kb
- КА.jpg 70,16 Kb
- КА2.jpg 39,65 Kb
- лемма о разр.jpg 63,2 Kb
- п к.jpg 86,04 Kb
- поиск в глубину.jpg 95,61 Kb
- т в замкнутом п к.jpg 50 Kb
- теоремы.jpg 60,22 Kb
Распознанный текст из изображения:
Свонства оверацнн над нножес4ванн
1) АОВ=ВОА;
2) АПВ=ВПА,
3) АО)ВОС) = )АОВ)ОС!
4) АП)ВпС)=)АПВ)ПС;
3) АП)ВОС)=)АПВ)О)АПС);
4) АО(ВПС)=)АОВ)П)АОС),
1) ХОЗ=АПВ;
8) АПВ= АОВ;
9) А О В = А,
10) АПВ=В;
!1) АСС=А;
!2) АСС=С;
13) АОА — С,
14) АПА=В,
13) АОА= А;
16) АПА= А;
12) А=А;
18) А)В=АПВ;
!8) АЬВ=)АОВ)ЦАПВ),
Ю) )АЬВ)ЬС=АЬ)ВЬС2
21) АЬВ=ВЬА;
22) АП)ВЬС) = )АПВ) Ь)АСС)
Распознанный текст из изображения:
Множества
Понятие множества является исходным, для него нельзя дать строгого
математического определения. Множество состоит из элементов, !';
Основоположник теории множеств Георг Кантор, поясняя интуитивную
идею множества, писал: ~':
„Под ... множеством, я понимаю вообще все многое, которое возможно мыслить как единое, т.е. такую совокупность определенных элементов, которая посредством одного закона может быть соединена в одно целое."
Принадлежность элемента ге множеству А обозначается с помощью знака
Е ~„принадлежит"): х Е А.
Распознанный текст из изображения:
Элеыентьг формальной лвгнк»
Ляя сокраогення записи мы булем использовать элементы формальной
логики. оперирующей с высказыванннмв. ".
Вьгсказыаянне это предюжение. которое нпжез быль истинно или ложно
Д»я записи иыскюываний нсполюупзт готические синкопы. г
° Символ Л )коньюикпня) заьгеияст в речи союз „в".
° Символ р )дизьюикпня) — сазов,или". '
° Символ ::ь (импзнкапия) — слова „сслп ..., го"
° Символ Оь — слово,рапносильно".
° Символ — слова „нс". б
Будем шкжс пользоваться кванторами з) )всеобшносги) и Э )существова-
ния).
Равенства мимкеств. Подмножества
Два чнолмсзва А п В считаютсл рввныии, саги любой элемент х нз множества 1 )гс с А) является элементом миажеспю В )х б В) и наоборот:
А = В оз ))гх)ьг и Л со з' б В).
уоаарят, что В есть подмножество множества А, если всякий эземент В есть элемент .4 1)ггх))х с В ю х и А)). Йсггозгьзуютзапись: В С А. Символ С пазьгвают симеоном «квюченвя. 1
бели В С А, но В и' А, зо пишу~ В с А, п В называют строгим, или собственным иоливожеством множесзва з1, а симвоя С вЂ” еимаоюм строило «ключевп».
Пустое множества есп. подмножество любого множества, те.
)з)А))гб С А),
н собственное падиножсство любого непусюго множества.
Распознанный текст из изображения:
Теоретико-множественные операнин
Дла любых двух множеств А н В определены новые множества, называемые обьедипением, пересечением, разностью и симметрической разностью. 1
° АО — — )л ) э' Е АУн б В) — обьслинение А и В есть множество
всех таких .г,, что т «влвется элементом хотя бы одного из множеств
А. В;г,
° АйВ == (т ~ к б Адг Е В) — пересечение А и В есгь множсство
асах таких х, что з' — олноврсменно элемент А и элемент В;с
° А ~ В = (з:)х б А д х ф В) — разность А н В есть множества
всех таких х, что э --элемеат А, нонс элемент В г.г ф В); з
° А Л В = (А ~ В) а (В г, А), асимметрнчсскав разность А и В—
множество всех эаких х, что к — элемент А, но пе элемент В пли
х — элемент В,но не элемент А .
Удобно рассматривать все множества как подмножества некоторого универсального множества В. В этом случае можно оггрегзелгпь дополнение мнмкеетвв А:
А = )к~к ф А)..:
Дополнение А состоит из всех элементов универсального множества гг,
«старые ие явлюотся элементамн множества А . У
Другимнсловамн А =. В'гА. В общем случае разность В~А,тле А ~ В
называют дополненислг множеспа А до множества В .
Распознанный текст из изображения:
Свойстве теорецгке-множественных операций
Введенные операции над чножсствамн, обладают следующими свойстюьги.
2) ЛГ) В = ВГ)А
а)АВ()зсс) =(Асв)сс
Метод щрактеристическпх функций
Харвлырнстическан функции 1» мнюкества 4 С В, гле В унивсрсалыкю множество, есть фупкциа, отображающее универсальное чно кестен С в лвухэламситнае ьгножоство (О. 1) .
) 1, если «б А.
( О, сслп т й А.
Справедливы следующие равенства;
(в) 1 (г)' =- й»(')В
(б) т».а(т) = Х»(г))в(г) б
(в1 й»ов(т):: Д»гэ) ' До(л) — Д»(т)йв(,.г1;г
(г) х В«):= 1 — й г(л) .
Хараюсристнческис функции множеств ноюогцют докаэыв«гь теоретнкочножесиенныеюждоства
Метод харакгсрисгических функпий лонююсаьотва тсоретиюиножествснного тождества эаклгочается в аычнслсани характеристические фунюгигг обеих его истой.
Гождсс! во верно тогда и тольао тогдк когда эти фун клан совпадают.
1) ЛОВ =- ВО»!
3)»! О (В ' С) =- (.4 ' В) О С
3) А Гт)ВО С) = (А В В) О (АГ1С)
б) А О (В 1Ч С') =- (А О (3) С (.4 О С)
7) А '.! В =- А Г) В
9) А О ю = А
11) А Г) С -- А
!3) А О А = ГГ
15) А О А =: А
!7).4 = А
М) А В В = (А О В) г, (А Г) В)
81 А АГэ В = А О В
! О) А Г! ю = з
12)АОВ=В
14) А Г'. А =. Ю
16) А!14.= А
1В) А 'г В = А Г! В
Распознанный текст из изображения:
ОТНОШЕНИЯ И СООТВЕТСТВИЯ
1. Основные определения
Определение ЗЛ. и -арным (или и -местным ) отношением
н( ин((я(сотнях А(,..., А„, на(ынаст(я пззо(гзн(зп(н(х' подмны!пс11ю (3
дскарто(м пр(жзнед('шы А, х... х Л„:
НСА, х...хЛ„.:.
В гнктн(етп. ПРП Р = Е ПОД1"(аеи НУСтОЕ ОТНОШЕНИЕ, а ПРП
р (онпядаюпяы (о всем уыиянпым д(юцлоным пронзведенжм
универсальное отношение
Вя кнып нитный гпучай попузяем прн и =- '1 тогда шяорят о
соответствии из множества Л( в множество Ая.,"
Ес.зп Л, .=- Аз — — ... =. А„, =.- А, то р называют и -арным отношением на множестве А, прп п =. 2 попу ыеи бинарное отношение на множестве А
Распознанный текст из изображения:
Рассмотрим более подробно соответствия и бнпорныс отношения Лаос соответствие эта множества упорядо ннснык пвр. Например, егли А = Й' сясножсство денствнтсльных пнзл), то быанрное отношение нв Ж' . это лессага)хк. множество 10 !ск плоскити 2
Определение 3.2. Область определения соответствия из множестве А, в множества Аг р С А, х А — ж ть множество
'Рхсд) =- сх )ДУ Е Агсгссг, У) Е Р) г
Область значения соответствия р зто множс ство
Я~Ф = Ь Нбх б АсНх, у) б д) "
Из олрсдсления вытеки г, что ьсс,'р) С А,, сссг6а) С Аг -."!
СЪответствссе явзыввкзг всюду определенным., если гсср) =- Ас
Определение 3.3. Сс сснысм ссоатвегствия р дзя фньснроввннога
х с А, называют множество
рсх) = 'су ! 'сх.у) Е р).
Распознанный текст из изображения:
2. Операции над соответствиями
Поскольку соответствия являются множествами, то все операции над множествами (пересечение, объединение, разность, дополнение и т.д.) применимы и к соответствиям. Однако для соответствий можно определить специальные операции: композицию соответствий и получение обратного соответствия 1
1) Композиция соответствий.::
Если р С А, х Ае, о. С Аг х А,, то композиция (произведение)
соответствий р и а есть соответствие рог, определяемое как
Р о т = 1(х, Я) ~ (ЭУ)((х, У) Е Р) Л ИУ, -) Е а)1.~:
Пример 2. Соответствие р берем из предыдущего примера. а соответствие п С 11, 2, 3, 4)' зададим непосредственно как множество пар и = ((1,2), (1,3), (3,4)1.':
Задание. Построить граф композиции р о и.
Распознанный текст из изображения:
Коьсссозсссси«з отношении с самим содсзй вшывают квадратом отно-
шении
Определение 3.4. Отношение к) с = ((«, х) ) Е А) называют
диагонапъю множества А
Снойетва композидиис
с ц р о (о о т) = (р о о) о т.
(2) роЗ=З»Р= О,
(3) р о (о СЗ т) =- р о и О р о т, с
(1) ро (о ССт) Е ро о ус рот
(равенство в обще«с случае не имеет места')
(сд) росс(а = к)вор = р, где РС Ав . Езснарссоеотнашеша на А
Рассмотрим доказательство свокства (1) Используем метод двух
вкпюченид „.
Псразе вклкс инно.
(«, «) ер о (о о тА~ Яу)(((«, у) е р) Л ((у, ) Е и о ти м:
=" (пзу)(Зт) И(«, у) е р) л (((ссл й е ст) л ((д «) е т))) ~ в
-' (пуйзс)((((г, у) е Р) л ((сл 6 е и)) л ((д «) е т)) м з
~ (пг)(((«г) е ран) л ((г «) е т)) =ь «
~ («,«) Е (роо)
Второе вклю'к ние
(«,«) европ) от ы (ег)(((г, с) е ров) л ((с,«) е т)) м
м (Зу)91)((((« у) е р) л ((уй е а)) л ((т, «) е т)) ю '
м (Зу)(Эг)(((и, сс) е р) л (((у. О е о) л ((е «)» т))) м с
М (Ну)(((т,ус Е р) Л ((у,«) Е о т)) М
(««) Е р О (о О т).
Распознанный текст из изображения:
отношкния и соотвктствия
Специальные свойства
бинарных отношений
Бинарное отнопзенза р С Аа называется .',
Ц рефлексивным. если (Чг Е Аах. и) Е р),
тс. )я С р
2) иррофлексннным, есле (ух Е А)((х, х) т р),
те, нзаезр =: СЛ,
3) симметричным, если (ухяу)((та у) Е р =.а (у, х) Е р)
т' Р '=-РА
-)) антисимметричным, если
(Чхуу)(((а: у) Е р Л (:у, и) Е р) — (т = у)).
т.е. РО р ' С н)а (в лестности, и. б., лто ре р ' =- я !).'
Эквивалентное определение.
(ахи) ((х, У) е Р л х т- У) ~ ((У., х)) а Р):!
Распознанный текст из изображения:
5) транзитивным, сслп
ФвЮ~вНйя р) р д ~ р я~ 6 Гг) =в ГГг .1 Е рБ ':
те. рсрС р. а
6г плотным. если
РГтГрИИв М 6 р~ ЯвИ~яФх1д~лФд~лйт,гз 6гг) Л(Гя,Ф Е ГзБ
Бинарное отношение называется:
Г) эквивалентностью, сслв оно рсфлекснвно. сик.к1стр~гшо я
тр,гнзптивно:
2) толерантностью, если опо рефлексивно н симметрично. ',
3) порядком Гни частичным порядком), если оно рефлезгнвно,
антнснммегрнзно н транзнтивнор
Ц предпорядком Гялгг квазипорядком). осли оно рефлексивно и
транзитнвно„:.
5) строгим порядком, если оно иррсфлсггсшзно. ан пк вмметрпзно н
граызггтзгвпо:
6) строгим предпорядком, если оно нррвфлексивно н транзитивно,".'
Боворят , отношение эквивалентности, толерантности. порядка, пред-
порядка .,'и т.п
Распознанный текст из изображения:
Индексированное семейство множеств ~В;)„у называется разбиением множества А, если:
1) 0В,=
~с!
2) если г ~ э', то В; Г~ В, = Я::
Таким образом, разбиение множества А зто семейство попарно не пересекающихся подмножеств А., объединснис которых равно А.:: Например, множества [О, 1/3), [1/3,2/?) и [2/3,1) образуют разбиение отрезка [О, 1] .
Теорема. Любое отношение эквивалентности определяет однозначно пекоторос разбиение данпого множества и обратно, любое разбиение множества однозначно определяет некоторое отношение эквивалентности на нем.."
Распознанный текст из изображения:
Полугруппы и группы
Пусть на множестве А определена бинарная операдия, обозначаемая е Определение 7Л. Бинарная опсрапня а называется;:,,:
)) ассоциатавной, если ддя любых т, у „- ~нар) я=хе~рва);
2) коммутативиой, если для любых х, у
л е ф =- П е х:
3) илемнотентной, если для гпобого т
Распознанный текст из изображения:
Определение 7.5. Полуцэуппа называстс» мапопдом, сали в ней существует нейтральный элемент относи шльна операции (етгиггпгга).) Пример 75. а) Алгебра ~ 2'. ()) является ыоноидом, поскочьку операция О ассоциативна и Π— ие(пральиьш элсмегп относительно онерапии объединения множсстн. б) Множество всех бинарных отношений н» множестве .1 с операцией композиции булет монондом, поскольку операция композиции оннарвых отношений ассоциативна (гр о г) оп .=- р а '(г о о)), а единицей служит диагональ п)ч (н!гор = р о Ыл = р)д Задача 5. Пусть .4 = (.г„р,, ) — ыножсс~во букв, а А" — множество всех азов, которые можно состав~гть нз этих букв с повторениями. Конкатенмгггей двух алов называется слово, полученное их .сжгеиванием", например гзд + рлззг .= ггтррллг. Пустое слово обозначагот Л. Показать, что
(А', -:) — моноид.
Определение 7.5. Элемент й множества А называегс» ясным (правым) ябратиыьг к ээемегпу л относительно данной операции, если р *,г = 1 гз * у = 1). 'Элемент у, который является одновременно левым и правым обратным, называется ггросго обратным к т относптелыю данной эпсрацпи.
Опрелелепие 7.7. Монокл называется группой. если в нем для кажного
элемента существует обратный.
ейобы проверить. что гшгебра (А, * ) является группой, нужно—
П проверить ассодиативность операции гга множестве А; )
2) найти элемент мвожества А — единицу отвосительна операции
3) убедиться, что для каждого эленеюа из,4 сушествуег образный..
Полугрупда (в частности, грушга) называешн поммутативной (абелевой).
соли сс операция комиупппвна.
Распознанный текст из изображения:
7.1. Региеиие уравиевеие в группах
Распознанный текст из изображения:
ЭЛЕМЕНТЫ ОБЩЕЙ АЛГЕБРЫ
Циклические полугруппы и группы
Определение 8.1.
В поп)труппз ',А, *) и, -я степень элемента а егггь згюмснт ь'— '-: — " 'з
и раз
а=2,3,... -:
Если (А,*,1) . моноид, то вводят пудовую степень а" = 1.
Если (А, ем 1) —. группа, то дпя любого элемента а вводят отрипатепьную ~теионь согласно равенству: а ' = (а ')" и, = 1,2.... (Отрипатеаьвэя степень элемента а группы есть попожнтеаьн,1я степень элемента, обратно!в я а .) ':
Свойства степеней
Утверждение 8.1.
!) Лпя пязбой попугруппы а'" * ау =- а '": (а")"' =- а"'" (т. и б И) .
2) пая любой группы а " = !а") ' (и Е И), а," з а" =-. а"""
(т,п б Е)
Распознанный текст из изображения:
Определение 8.2. !1опугрз пну (гришу) (Л, *) называют пикнической, если ш"ществует твкои зпсмент а, гго лкйой элемент :с полэтруппы (грзппы) «впяется нокотори (ценой) спепеззью эдемецтв и Элемент а нвзывьвзт образующим элементом полугруппы '(группы)
Замечание. П1ш зддитцвной форме звшюи вместо а" пишут и а. Пример 1. и) !)опзтруззив (((, т, 0) - цикинзоскья, с обр,жюощим элементом 1
Гзсиуя опредозению В 1. подучим б 1 = б 1
авды 1 1=1з2 1=1-1-1=2 итд
11пя произвольного и имеем
и, 1=.~~,. т =и,.'.
рвз
б) Грз'ппа (Уо. щм 1) цнкли веская с (ябзразующнм з.жментом 2 1 Лействитс"льна дпя 2 ю.осм 2о = 1.:2' .= 2 узз =
"2" =- 2 г1з 2' — — 2 Зз 4 = 3 . )2' =. 2 Рз 3 = 1
Порядком конечной группы вкзыввют количегтж сс ззементов Аде)записная группа аьз ~сизов по модулю 1 имеет порядок 1с Группа аодсшаиоеоя Я„есть группа ос рядка п! .. й!уяьптпязскаглпоиая еруппа еызстов гьо жос(уяю р (р - простое пнпо!) нмжт порядыс р — 1
Определение 8.3.
Гру:пгг Х =- (Н, з. ', 1) называют подгруппой группы (С,, ',1).сопи
Н ать попмпожощво С . жыкнутое относитщьно операции ь. 1 же(аквшес едпшщу 1 группы и э
и вщты г кв.ьдым злемюггом х б Н содерзкюце" злеысгп обратный к я
Определение 8.4.
(!одгруппу группы й, задвинь ю на зсноже~ з не вссх отепснеи фикстйюванного элемента а, ивзыввют циклэзческой подгруппой грузшы а, порожденной элементом а
Распознанный текст из изображения:
Пусть Д = ГС, Н 1~ -- еруппа, а 'Ц = ГН, э,!) . сс подврутта Определение 8,8. Левым смежным классом подгруппы Я по элементу а е С наэывавэт множество
аН = ~ГГ)у = а *6, Ь б Н'у.':.
Соответственно, правый смежный класс подгруппы 'Н по элементу п Е С это ьпгожссгво Па = (у ~ у =- й * и, 6 Е ПГ Задача 2. Найти ясный смюкный класс оЧ пиьлиэескои подгруппы 'Н с обраэуюипгм элементом 6 = 4 мультнплнкативпой группы У;, по элементу и = 3
Теорема 1. ~Лагранж) Порядок нонниной группы делится на порядок
любой ее подгруппы.
Распознанный текст из изображения:
Кольца. Поля. Решение СЛАУ
Определение В.б. Кольпо зто алгебра с двумя бинарными н двумя
нульарпымп оиорациямн
такса !то:::
Ц алгебра (22, +,0~ комиттзпивная группа;:.
2~~ алгебра (и, ь Н вЂ”. ьюнонд,
3) имеет тюгто дистрпбутивногть операдии н- (сложения кольца) относительно операции ~уз|поженив кольца)
а ° (бес)=-о, 6~о с, (бес) а=6 пес об
Операцию -~- пазыва|от сложением кольца, '' умножением кольца, элемент 0 — нулем кольца, элемент 1 — — единицей кольца.
Определение В.Т. Кольцо называют коммутативным. еслп
операция умножения в нем коммутатииы
Распознанный текст из изображения:
Пример 2.
е~ Ллгебра ГК. ', .О, 11 есть коммутатниное кольцоЗ
б) Ллгебра 1И, ';.,0,1~ кольцом не будет, поскольку (М, <-)
татианый моноид, ио нс Пзуппад
б)Л б1
комму-
Определение 8.8. Нснулепы~ злементы а н Ь кольца гь назыпаюз
делителями нуля. если а б = О '.
ж, =: ЯО.1,У,....~ — 1),бм,ебыО,Ц
(при й > 1ь аддитианая группа которого ость аддаглиатая еруппа выметав ао модули 1с;й операция ушиокення по иодулзо 1с определена
гнелопгчно сложснгпо по ыодулкз 1с, зсс л~ сб 71 раино остатку от
леления на 1с *пыла т л,есть коммугатнаног кольцо. Гго иазылсип кольцом вычетов по модулю Ф
Начать зарабатывать