Шпаргалка по "Высшей математике"
Автор: Екатерина Вербова • Январь 11, 2022 • Шпаргалка • 5,228 Слов (21 Страниц) • 332 Просмотры
1.Теория множеств. Понятие множества и подмножества. Опр.1(Кантор) Множество - всякое собрание определённых и различимых между собой объектов, мысленное как единое целое. Опр.2 Множества, состоящие из конечного числа элементов, называются конечными, в противном случае бесконечными. Способы задания множеств: 1) путем перечисления: А={а1, а2..аn}; А={1,2,3,4,5}; 2)при помощи правил: В={x|x^2-5x+6=0} C={(x;y)|x^2+y^2<=1} Опр.3 Множество, не содержащее ни одного элемента, называется пустое множество. Опр.4 Множество В называется подмножеством множества А, если все элементы мн-ва В являются и элементами мн-ва А. Замечания: 1. Мн-во А является подмножеством самого себя (АсА), а также самым широким подмножеством мн-ва А. 2. Пустое мн-во является подмножеством любого мн-ва. З. Мн-во А и пустое мн-во являются не собственными подмножествами подмн-ва А, а остальные подмн-ва – собственными. !![2^n]!! Мощность мн-ва характеризует кол-во входящих в него элементов |A|=n Счетные – бесконечны. Мн-во равномощное мн-ву натуральных чисел называется счетным. Бесконечное мн-во – равномощное мн-во вещественных чисел, единичного отрезка имеет мощность континуума, т.е непрерывного 7. Бинарные отношения и их св-ва. Бинарным отношением на мн-ве х называется всякое подмн-во декартового произведения ХхХ Свойства: 1.Рефлексивность (х R x) –«x нах.в отн.R с самим собой» 2. Симметричность (хRy => yRx) 3. Транзитивность (хRy, а yRz => xRz) Отношение R является отношением эквивалентности, если оно обладает всеми 3-мя свойствами. 4. отношение R называется ассиметричным, если aRb и bRa => a=b 8. Бином Ньютона. | 2. Операции над множествами 1)Два мн-ва А и В называются равными, если они состоят из одних и тех же элементов. А=В 2)Два мн-ва объединены (А и В), когда есть такое новое мн-во С=АÙВ, которое состоит из элементов входящих хотя бы в одно из этих мн-в. С=АÙВ={X|x€A или X€B } 3)Пересечением двух мн-в А и В называется мн-во С=АᴒВ состоящее из общих для А и В элементов. С=АᴒВ={x|x€A и X€B} 4)Разностью двух мн-в А и В называется такое мн-во С=А\B которое состоит из элементов мн-ва А и не входящих во мн-во В. С= А\B={x|x€A и xȼB} Если мн-во В является подмн-ом мн-ва А,то разность А\B называется дополнением к мн-ву В до мн-ва А. 3. Св-ва операций над мн-ми: 1)АÙВ=ВÙА; АᴒВ=ВᴒА(коммутативность) 2)(АÙВ)ÙС=АÙ(ВÙС); (АᴒВ)ᴒС=Аᴒ(ВᴒС) (ассоциативность) 3)(АÙВ)ᴒС=(АᴒС)Ù(ВᴒС); (АᴒВ)ÙС=(АÙС)ᴒ(ВÙС) (дистрибутивность) свойства пуст.мн-ва.1)АU0=A 2)An0=0 св-ва вычит.1)(А\В) \С=(А\С) \В 2)(АUB) \C=(A\C)U(B\C) 3)(A\B) ᴒC=(AᴒC) \(BᴒC) 4)А\(BUC)=(A\B)n(A\C) 5)A\(BnC)=(A\B)U(A\C) | 9.Комбинаторика. Основные определения (выборка, виды) Комбинаторика – раздел математики, объектом изучения которого являются дискретные мн-ва произвольной природы. Основная задача комбинаторики — это определённые числа комбинаций, которые могут быть получены у объектов одного множества. Совокупность: 1). подмножество 2). выборка Пусть мн-во А состоит из а элементов A = {a1, a2, …, an}. Произвольная последовательность элементов мн-ва А называется выборкой объема R из мн-ва А, причём каждый элемент мн-ва А может повторяться произвольное количество раз. Если в выборке все элементы различны, то она называется подмножеством. Если при перемене двух элементов выборки(подмн-ва) свойства выборки(подмн-ва) изменяются, то такая выборка(подмн-во) называется упорядоченной, в противном случае – неупорядоченной. 10.Комбинаторика.Основные правила: 2). Правило произведения: если объект А может быть выбран n способами, а объект В m способами, то выбрать пару А и В можно n*m способами. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
4. Понятие декартова произведения Декартовым произведением двух мн-в А и В называется мн-во С=АхВ состоящее из упорядоченных пар (а,в) где первая компонента принадлежит мн-ву А, а вторая мн-ву В. АхВ={(а,в)|a€A и b€B} Способы задания декартового произведения:1). граф 2). таблично 3). координатная плоскость 5. Мощность декартового произведения (разности и объединения мн-в):1). |AxB|=|A|*|B|; 2). если ВcА, то |A\B|=|A|-|B|; 3). Если А,В не пересекаются: |AUB|=|A|+|B|; Если пересекаются -|AᴒB| |AÙB|=|A|+|B|+|C|-|AᴒB|-|AᴒC|-|BᴒC|=|AᴒBᴒC|- формула включений и исключений. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
11.Комбинаторные методы. Размещения и сочетания. Перестановки Опр.1 Упорядоченное m подмн-во n мн-ва называется размещением из n по m и обозначается буквой Опр.2. Неупорядоченное m-подмн-во, n-мн-ва наз-ся сочетанием из n по m и обозначается [pic 3] [pic 4] Д-во: Опр.3 Перестановкой множества из n элементов называется расположение элементов в определенном порядке. перестановки можно считать частным случаем размещений, где m=n. Число всех перестановок из n элементов обозначается [pic 5] | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
6.Разбиение мн-ва на классы Пусть мн-ва А1, А2, …, Аn являются подмн-ми мн-ва А. Мн-во А разбито на классы, если: 1). Подмн-ва А1, А2, …, An попарно не пересекаются; 2). Объединение мн-в А1, А2, …, An есть само мн-во А. При задании одного характеристического свойства мн-ва делятся на II класса: I класс – элементов обладающим данным свойством; II класс – элементов не обладающим их. Такая классификация получила название дихотомической. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
12.Комбинаторные методы. Размещения и сочетания с повторениями Опр.1 Упорядоченное m-выборка из n-мн-ва называется размещением с повторением и обозначается (над А отрицание). Док-во: [pic 6]
[pic 9] Док-во: (С отрицание) = Опр.3 Всякое размещение с повторениями, в котором элемент a1 повторяется n1 раз, элемент a2 повторяется n2 раз и т.д. элемент an повторяется nk раз, где n1,n2,…nk— данные числа, называется перестановкой с повторениями порядка. [pic 10] | 13.Метод включений и исключений Опр.1Пусть имеется n-предметов некоторые из них обладают свойствами а1,а2…аn. Число предметов, обладающих двумя св-ми: N(ai,aj) I,j=1,…n; ij Число предметов,обладающих всеми св-ми: N(a1,a2…an),тогда N(a1,a2…an)=n-N(a1)-N(a2)-…N(an)+N(a1.a2)+N(a1,a3)+…+N(an-1,an)-N(a1,a2,a3)-…+(*N(a1,a2…an) – формула включений и исключений. | 14.Общие сведения о науке математическая логика. Исторический аспект. Логика–наука о способах и формах человеческого мышления. IV тыс. до н. э.– Аристотель XIII в. н. э– Р. Луллий (изобретатель первой логич. машины) XVII–Лейбниц (идея исчисления логики) XIX–Дж. Буль (истина=1; ложь=0) XX–Гильберт (предл. программу на языке мат. логики) Матем. логика состоит из двух осн. теорий:1). Исчисление высказываний (1 логич. теория); 2). Исчисление предметов (2 логич.теория) Логика высказываний: 1). Высказывание – это простое повествовательное предложение, утвержд. что-либо, о чем-либо и принимающее значение «истина» или «ложь». 2). высказывание наз-ся сложным или составным, если оно состоит из 2-ух или более простых связанных между собой логическими связками «не, и, или, если, то, тогда и только тогда». | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
15.Высказывания математической логики. Простые и сложные высказывания. Любое повествовательное предложение, утверждающее что-либо о чем-либо, которое может быть признано истинным или ложным. Логическим значением высказывания являются “истина” или “ложь”. Высказывание называется сложным или составным если оно состоит из двух и более простых, связанных между собой логическими связями | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
16.Основные логические операции. Отрицание(инверсия) пусть х - простое высказывание, отрицанием высказывания Х называется такое высказывание, которое принимает значение истина, если х-ложь и значение ложь если х-истина.
Дизъюнкция двух высказ наз-ся такое высказ которое принимает знач ложь-если оба ложные и истина-во всех др.случаях (+)(или;или оба;либо-либо) 17.Логические операции: импликация, эквиваленция
Импликация двух высказываний это такое высказывание которое принимает значение ложь если х - истина, у - ложь, и значение истина-во всех других случаях (следствие) (если; если то; тогда когда)
Эквиваленция - такое высказывание, которое принимает значение истина, когда оба высказывания истинны или оба ложны и значение ложь при других случаях (необходимо и достаточно; тогда и только тогда)
2. ассоциативность (Х^У)^Z=X^(Z^Y)и(ХvУ)vZ=Хv(ZvУ) 3.дистрибутивность (Х^Y)vZ=(X^Z)v(Y^Z)и (XvY)^Z=(XvZ)^(ZvY) | 18.Основные логические операции: Штрих Шеффера и Стрелка Пирса
Штрих Шеффера - пусть х и у простые высказывания. Штрихом Шеффера двух высказываний называется такое высказывание, которое принимает значение «ложь» только тогда когда оба высказывания «истины» и «истина во всех других случаях»
Стрела Пирса двух высказываний - это такое высказывание, которое принимает значение истина, когда оба ложь и значения ложь во всех других случаях. | 20.Формулы алгебры логики. Приоритет выполнения логических операций. Таблица истинности. Пусть а1,а2,а.. некоторые постоянные элементарные высказывания, х1,х2,х…некоторые переменные элементарные высказывания заданы на множествах М1,М2… Формулой алгебры высказываний называется сложное высказывание, состоящее из простых. а1, а2, а3…х1, х2, х3…, связанных между собой логическими операциями: отрицание, конъюнкция и т. д. Формулы алгебры логики обозначаются заглавными буквами латинского алфавита A, B, C… Порядок действий:
Таблица истинности — это такая таблица, в которой показываются все выходные состояния элемента для любых комбинации входных сигналов. Иными словами, с помощью таблиц истинности можно определять истинностное значение любого высказывания для всех возможных случаев значений истинности составляющих его высказываний. Общее количество всех возможных комбинаций в таблице можно определить по формуле N=2n; где N - общее число возможных комбинаций, n - количество входных переменных. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
14.Свойства логических операций 1.Законы рефлексивности a ∨ a = a a ∧ a = a 2.Законы коммутативности a ∨ b = b ∨ a a ∧ b = b ∧ a 3.Законы ассоциативности (a ∧ b) ∧ c = a ∧ (b ∧ c) (a ∨ b) ∨ c = a ∨ (b ∨ c) 4.Законы дистрибутивности a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c) a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c) 5.Закон отрицания отрицания ¬ (¬ a) = a 6.Законы де Моргана ¬ (a ∧ b) = ¬ a ∨ ¬ b ¬ (a ∨ b) = ¬ a ∧ ¬ b 7.Законы поглощения a ∨ (a ∧ b) = a a ∧ (a ∨ b) = a | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
21. Тождественность логических формул: тождественно-истинные и тождественно-ложные (примеры!!) Формулы алгебры высказываний делятся на тождественно-истинные, тождественно-ложные и выполнимые 1.Тождественно-истинная (тавтология), если на всех наборах значений она принимает только значение «истина» 2. Тождественно-ложной (противоречие), если на всех наборах значений принимает только значение «ложь» Выполнимой, если на всех наборах она принимает значение «истина» хотя бы на одном наборе значений и не является тождественно-истинной. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
22. Законы математической логики. Основные равносильности Две формулы алгебры логики А и В называются равносильными, если они принимают одинаковые логические значения на любом наборе значений входящих в них высказываний. Свойства: Основные равносильности: [pic 11] | 23. Равносильности, выражающие одни логические операции через другие: Две формулы алгебры логики А и В называются равносильными, если они принимают одинаковые логические значения на любом наборе значений входящих в них высказываний. [pic 12] | 24. Равносильные формулы. Способы доказательства равносильности двух логических формул. [pic 13] Применяют два способа доказательства равносильности формул: переход от одной формулы к другой с помощью законов, и имея законы логики высказываний, построение совместной таблицы истинности. Этот способ состоит в переходе от одной формулы к другой с помощью законов. В его основе лежит следующее легко доказываемое утверждение: если в некоторой формуле F заменить подформулу G равносильной ей формулой G′, то получим формулу F′, равносильную исходной формуле F. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
25. Нормальные формы: ДНФ и КНФ Все формулы алгебры делятся на дизъюнктивно-нормальные формы(ДНФ) и конъюнктивно-нормальные формы(КНФ) ДНФ называется дизъюнкция элементарных конъюнкций, состоящих из переменных входящих формулу или их отрицаний. Пр-р: -КНФ [pic 16]
| 26-27-28. СКНФ И СДНФ. Приведение логических формул к СДНФ и СКНФ. Элементарная конъюнкция (дизъюнкция) называется совершенной, если она состоит из всех переменных, входящих в формулы. Алгоритм СДНФ - Привести к ДНФ - Если в какой-либо элементарной конъюнкции не содержится одна из переменных, домножить на 1, представив дизъюнкцию недостающей переменной и её отрицания. - Применить законы дистрибутивности и законы поглощения Алгоритм СКНФ - Привести к КНФ - Если в какой-либо элементарной дизъюнкции не содержится одна из переменных, добавить 0, представив конъюнкцию недостающей переменной и её отрицания. - Применить законы дистрибутивности и законы поглощения. | 29. Логическое следствие. Алгоритм решения логических задач. G (х1, х2, …, хn) называется логическим следствием формул F1(х1, х2, …, хn), …, Fm, если она обращается в истинное высказывание на всяком наборе значений переменных, для которой в истинное высказывание обращаются все формулы F1, …, Fm. Алгоритм решения логических задач: - изучить условие, выделить простые условия, обозначить буквами - записать условия на языке алгебры логики - используя логические операции составить конечную формулу - упростить формулу с помощью законов поглощения или составить таблицу истинности - проанализировать результат | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
30. Логическое следствие. Теорема о логическом следствии. G (х1, х2, …, хn) называется логическим следствием формул F1(х1, х2, …, хn), …, Fm, если она обращается в истинное высказывание на всяком наборе значений переменных, для которой в истинное высказывание обращаются все формулы F1, …, Fm. | 31. Логика предикатов. Понятие предиката. Предикат-св-во. ЛОГИКА ПРЕДИКАТОВ – раздел символической логики, изуч. Рассужд-я и др. яз-е контексты с учетом внутр-ей структуры вход-их в них простых высказ-й, при этом выраж-я яз.трактуются функционально, т.е. как знаки некоторых функ-й или же знаки арг-ов этих фун-й. Предикат-утверждение,высказанное о субьекте. Предикат-св-во указ.на св-во объекта. Пусть М – непустое множество. Тогда n-местным предикатом, заданным на М, называется выражение, содержащее n переменных и обращающееся в высказывание при замене этих переменных элементами множества М. Предик-ы различ-ся, своей местностью: предикаты, представляющ.предметно-истинностные функц.от одного арг-та, назыв.одномест-и, те, которым соотв.функц.от 2-х арг-ов, – двухместными и т.д. Др.отлич.чертой логики предик.явл.использов-е особого типа логич.символов – кванторов и связываемых ими (квантифицируемых) переменных для воспроизв-я логич.форм множественных высказ-й. Наиб.употребимы в логике квантор всеобщности ∀ («всякий», «каждый», «любой», «произвольный») и квантор существования ∃ («существует», «найдется», «имеется», «некоторый»). | 33. понятие n-мерного предиката. Область истинности предиката. Примеры. N-местный предикат. Пусть M1,M2,M3-некот-е предметные области; X1,X2,X3,..Xn-переменные, задан-е на М1,М2..Мn соотв. N-местным предик. P(X1,X2..Xn) назыв.фун-я от N перем-й X1,X2..Xn; определ-я на декартовом произ-ии М1*М2*..*Мn и приним.знач.из множества {1;0}, где 1-истина,0-ложь. Пр-р: X1єM1=N(мн-о нат.чисел). X1єM1=N(мн-о нат.чисел). P(x1,x2)= «x1<x2». Р(5;7)= «5<7»=1. (x1,x2)єN*N. P(9;7)= «9<7»=0 Мн-о М на котором задана перемен.х назыв.ОБЛАСТЬЮ ОПРЕД.ПРЕДИКАТА. Под мн-м М,на кот.приним-т только знач. Истин.-назыв.ОБЛАСТЬЮ ИСТИННОСТИ ПРЕДИКАТА и обозн Ip. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
35. кванторы. Всеобщности и существования Кв.всеоб явл.обобщ ^ на бесконеч.мн-во М или когда n явл бесконеч.Кв сущ явл обобщ V на бесконеч мн-во М. Кв.всеобщ.:P(x)=[квант.всеобщ.все х из мн-а М обладают св-ми Р]. Для любого х из этой области. Предикат Р(х)-«истин». Р(х)= «х-прост.число». =P(x)истина.=P(x)=все натур.числа явл.прост.=0. (кругМ в круге Р) Кв.сущест.:= «сущ.такой х из мн-ва М. Р-истина.». «некот.х из мн-а М обладают св-м Р». Пр-р.Р(х)=х-прост.число. =некотор.из натур.чисел явл.прост.=1. (круг М заходит на к.Р) 36.Кванторы.Понижение местности предикатов | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
40. Равносильности для формул логики предикатов, содержащих кванторы. Отн.формулы приним.одинак. знач. (0или1). [pic 17] [pic 18] [pic 19] =[pic 20][pic 21] [pic 22] [pic 23] Пр-р.: | 37. Формулы логики предикатов. Примеры. | 34- Логические операции логики предикатов. 2)- Конъюнкцией двух предикатов P(x) и Q(x) называется новый предикат который принимает значение «истина», когда оба «истина» и значение «ложь» во всех ост. случаях.
5)- Эквиваленцией предикатов P(x) и Q(x) называется новый предикат , который является «истинным», когда оба либо «ложь», либо «истина», и значение «ложь» в ост.случаях.[pic 34][pic 33]
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
38-Классификация формул алгебры предикатов. 1)Формула наз-ся тождественно истинной на области отрезка M, если она принимает значение «истина» для всех X из области М. [pic 36] [pic 37] [pic 38] [pic 39] [pic 40] 39.общезнач и выполним. | - [pic 41][pic 42] | 49.Теория графов.Деревья.Лес.Покрывающее дерево Дерево-связный граф не имеющий циклов наз деревом,а его ребра-ветвями(у дерева с п-вершинами есть п-1-ветка) Несвязный граф без циклов наз лесом Ориентированное дерево-наз прадеревом с корнем у,если из вершины у-сущ путь к др.вершине. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
44 Частичный граф и подграф.Пример Граф наз частичным если он содержит все вершины исходного графа и лишь нек.ребра.Граф наз подграфом если он содержит подмн-во исх графа и все ребра соед.все эти вершины Пример. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
43 Планарный граф.Пример Графы-отличающиеся только нумерацией вершин наз. Изоморфными Граф наз планарным(плоским) если сущ изоморф ему граф который мб изображен,без пересечения ребер Пример | 41- Релейно-контактные схемы. РКС-схема :физ устр-ва элементами кот явл 1)переключатели 2)клеммы на кот подается и снимается напряжение(входы и выходы) 3)проводники соед переключатели и клеммы. | 50-Парадоксы в математике Аутологические и гетерологические слова (Греллинг) Пусть K — множество всех множеств, которые не содержат себя в качестве своего элемента. Содержит ли K само себя в качестве элемента? Если да, то, по определению K, оно не должно быть элементом K — противоречие. Если нет — то, по определению K, оно должно быть элементом K — вновь противоречие. Берри. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
42-Определение графа. Пример. Граф- система объектов произвольной природы (вершин) и связок (ребер), соединяющих некоторые пары этих объектов. [pic 43][pic 44] [pic 45] [pic 46] [pic 47], где [pic 48] — множество вершин, а [pic 49] — множество рёбер. [pic 50] | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
48.Теория графов. Гамильтонов граф. Гамильтоновым циклом графа G называется путь, проходящий через каждую вершину G в точности по одному разу. Граф, обладающий гамильтоновым циклом, называется гамильтоновым. Граф, который содержит простой путь, проходящий через каждую его вершину, называется полугамильтоновым. Это определение можно распространить на ориентированные графы, если путь считать ориентированным. [pic 51] | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
45.Ориентированный граф.Матрица инцедентности. Ориентированным графом наз пара мно-в (D=(x,A));x-мн-во вершин,А-мн-во упорядоч пар (А=(Xi,Xj))-называемых дугами,где 1-я компонента в паре,наз началом дуги,а 2-я концом дуги Двигаемся только по стрелкам ориент.графа,используется матрица: Для формулизации инцидентности (строками и столбцами,которой явл.вершины графа,а эл-ты Сij-определяются 1)если дуга выходит из вершины ,то эл-т матрицы равен-1 2)если дуга входит в данную вершину,то ставим 1 | 46- Теория графов. Маршруты на графах. Маршрут в графе — последовательность вершин, имеющая для каждой вершины ребро, соединяющее её со следующей вершиной в последовательности. |
...