дискретка. Теорема о мощности множествастепени
 Скачать 270.76 Kb.
|
|
1. Основные понятия теории множеств: понятие множества, элемент множества, способы задания множеств; подмножество, свойства отношения включения; теорема о мощности множества-степени. Множество - это любое собрание вполне определенных и различимых объектов нашей интуиции или интеллекта, мыслимое как единое целое. Это описание множества принадлежит основателю теории множеств Георгу Кантору (1845 — 1918). Множества делятся на конечные и бесконечные. Конечное множество — множество, содержащее определённое (конечное) количество элементов. Бесконечное множество — множество, содержащее бесконечно много элементов. К бесконечным множествам можно отнести множества натуральных и целых чисел. Множества, не содержащие ни одного элемента называются пустыми. Объекты, из которых состоит множество, называются его элементами. Множества будем обозначать прописными буквами латинского алфавита (A, B, C, X, Y, Z, . . .) , а элементы множеств — строчными (x, y, z, a, b, c, . . .) . Зафиксируем следующие обозначения для наиболее важных числовых множеств: N — множество натуральных чисел, Z — множество целых чисел, R — множество действительных чисел. Рассмотрим способы задания множеств. Множество может быть задано: ● а) описанием характеристического свойства его элементов, ● б) при помощи списка или перечисления элементов множества, ● в) при помощи порождающей процедуры и т. д. При задании множества A при помощи его характеристического свойства P (x) пишут A = {x| P (x)}. При помощи списка могут задаваться только конечные множества, т. е. множества, состоящие из конечного числа элементов. Порождающая процедура описывает способ получения элементов множества из уже полученных элементов или других объектов. Весьма распространенной порождающей процедурой является образование множеств из других множеств при помощи операций, которые рассмотрим ниже. Подмножество — это множество, все элементы которого, являются частью другого множества. Визуально продемонстрировать отношение множества и входящего в него подмножества можно с помощью кругов Эйлера. Круги Эйлера — это геометрические схемы, помогающие визуализировать отношения различных объектов, в нашем случае, множеств. Рассмотрим два множества: L = {2, 4, 6, 8} и M = {2, 4, 6, 8, 10, 12}. Каждый элемент множества L принадлежит и множеству M, значит, множество L является подмножеством множества M. Такое соотношение множеств обозначают знаком ⊂: L⊂M. Запись L⊂M читается так: множество L является подмножеством множества M. Множества, состоящие из одних и тех же элементов, независимо от их порядка, называются равными и обозначаются знаком =. Свойства отношения включения: Множество A называется подмножеством множества B (обозначается - A ⊆ B , знак ⊆ называется знаком включения),если каждый элемент множества A является элементом множества B . Множества A и B равны ( A = B ), если одновременно имеют место включения A ⊆ B и B ⊆ A . Принадлежность элемента x множеству A обозначается x ∈ A , непринадлежность элемента x множеству A обозначается x ∈/ A . Множество, не содержащее элементов, называется пустым и обозначается ∅ . Множество, включающее элементы всех рассматриваемых в конкретной ситуации множеств, называется универсальным для данной ситуации и обозначается U . Для любого множества имеют место включения: ∅ ⊆ A ⊆ U . Мощность множества — это обобщение понятия количества (числа элементов множества), которое имеет смысл для всех множеств, включая бесконечные. Существуют бо́льшие, есть ме́ньшие бесконечные множества, среди них счётное множество является самым маленьким. Мощность множества, как и другие основные конструкции традиционной теоретико-множественной математики, может достаточно плодотворно рассматриваться и под углом зрения, отличным от широко известной интуиционистской критики в рамках альтернативной теории множеств. Пусть даны два множества и Тогда они называются равномощными, если между ними существует биекция . Из свойств биекции следует, что равномощность является отношением эквивалентности . Мощностью или кардинальным числом множества называется соответствующий ему класс эквивалентности . Мощность множества обозначается . Тот факт, что два множества равномощны, записывается: Свойства · Если конечно, и - его булеан , то · Множество является бесконечным тогда и только тогда, когда оно содержит подмножество равномощное себе. · В предположении выполненности аксиомы выбора любое бесконечное множество содержит счётное подмножество. · Декартово произведение бесконечного множества с самим собой равномощно 2. Основные понятия теории множеств: понятие алгебры множеств, операции над множествами; свойства операций над множествами. Операции над множествами и их свойства Объединением множеств A и B называется множество A ∪ B , состоящее из тех и только тех элементов, которые принадлежат хотя бы одному из множеств A или B : A ∪ B = {x | x ∈ A или x ∈ B}. Пересечением множеств A и B называется множество A ∩ B , состоящее из тех и только тех элементов, которые принадлежат одновременно множествам A и B : A ∩ B = {x | x ∈ A и x ∈ B}. Разностью множеств A и B называется множество A \ B тех и только тех элементов из A , которые не принадлежат множеству B : A \ B = {x | x ∈ A и x ∈/ B}. Дополнение определяется равенством - универсальное множество. Симметричной разностью множеств A и B называется множество: Эти операции можно наглядно проиллюстрировать следующим образом: Приведенные здесь рисунки называются диаграммами Эйлера-Венна. Операции над множествами обладают следующими свойствами: 1. = A (закон двойного отрицания); 2. A ∪ B = B ∪ A (коммутативность объединения); 3. A ∩ B = B ∩ A (коммутативность пересечения); 4. A ∪ (B ∪ C) = (A ∪ B) ∪ C (ассоциативность объединения); 5. A ∩ (B ∩ C) = (A ∩ B) ∩ C (ассоциативность пересечения); 6. A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) (1-й дистрибутивный закон); 7. A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) (2-й дистрибутивный закон); 8. 9. 10. A ∪ (A ∩ B) = A (закон поглощения); 11. A ∩ (A ∪ B) = A (закон поглощения); 12. A ∪ ø = A ; 13. A ∩ ø = ø; 14. A ∪ U = U ; 15. A ∩ U = A . 3. Основные понятия теории множеств: диаграмма Эйлера-Венна; теорема о пяти возможностях. Диаграмма Эйлера-Венна — геометрическая схема, которая используется для моделирования множеств и для схематичного изображения и отношений между ними.Диаграмма позволяет наглядно отразить различные утверждения о множествах. При использовании этого метода универсальное множество изображается в виде прямоугольника, подмножества изображают кругами. Диаграммы нашли свое применение в математике, логике, менеджменте и других прикладных направлениях. Для отражения отношений между множествами математики Джон Венн и Леонард Эйлер использовали для способа. Если Венн использовал для обозначения множеств замкнутые фигуры, то Эйлер использовал круги. Диаграммы Эйлера-Венна являются важным частным случаем кругов Эйлера. Диаграммы изображают все 2^n комбинаций n свойств, что является конечной булевой алгеброй. В случае n = 3 диаграмма Эйлера-Венна обычно состоит из трёх кругов с центрами в вершинах равностороннего треугольника и одинаковым радиусом, приближенно равным длине стороны треугольника. 4. Основные понятия теории множеств: набор; декартово произведение множеств. Математическое понятие множества постепенно выделилось из привычных представлений о совокупности, собрании, классе и т.д. Один из создателей теории множеств – Георг Кантор представлял множество как «совокупность или набор определенных и различимых между собой объектов, мыслимых как единое целое». Координатное представление точек плоскости было впервые предложено Р.Декартом и исторически является первым примером прямого произведения. Поэтому часто прямое произведение множеств называют декартовым произведением. Декартово (прямое) произведение множеств Х и – это множество, обозначаемое , элементами которого являются упорядоченные пары , первая компонента которых принадлежит множеству Х, а вторая множеству . Задается в виде Согласно определению элементами прямого произведения множеств являются упорядоченные пары, составленные из элементов исходных множеств. В этих парах первый элемент (компонента) всегда принадлежит первому множеству, а второй элемент (компонента) второму. Порядок множеств определяется исходной записью и, если , то , так как в упорядоченной паре компонента имеет номер 1, а компонента – номер 2, но в упорядоченной паре : – номер 1, а – номер 2. 5. Основные понятия теории множеств: отношения, операции над отношениями, свойства отношений. Определение: Подмножество называется -местным ( — мерным) отношением на множестве А. Говорят, что элементы находятся в отношении , если . Одноместное (одномерное) отношение - это просто некоторое подмножество А. Такие отношения называют признаками. Говорят, что обладает признаком R, если . Свойства одноместных отношений - это свойства подмножеств А, поэтому для случая = 1 термин "отношения" употребляется редко. Наиболее часто встречающимися и хорошо изученными являются двухместные или бинарные отношения. Если а и b находятся в отношении R , это обычно записывается в виде . Операции над отношениями Поскольку отношения на множестве А являются подмножествами множества , для них можно определить те же операции, что и для множеств: объединение, пересечение, дополнение, разность. Так отношение на множестве натуральных чисел является объединением отношений Отношение является дополнением отношения , а отношение равенства является пересечением отношений на множестве действительных чисел. Отношение называется обратным к отношению , если тогда и только тогда, когда Произведением отношений и на множестве А называется отношение , состоящее из пар (х, у), для которых существует, элемент z € А, такой, что Транзитивным замыканием отношения на множестве А называется отношение , которое определяется следующим образом: тогда и только тогда, когда существует цепочка из конечного числа элементов , в которой для каждой пары соседних элементов выполняется отношение Транзитивным замыканием отношения «быть сыном» является отношение «быть прямым потомком». Оно представляет собой объединение отношений «быть сыном», «быть внуком» , «быть правнуком» и т.д. Транзитивным замыканием «жить в одном городе» является то же отношение. Свойства отношений Определение: Отношение называется рефлексивным, если для любого элемента имеет место . Главная диагональ матрицы рефлексивного отношения содержит только единицы. Определение: Отношение называется антирефлексивным, если ни для какого элемента не выполняется . Главная диагональ матрицы рефлексивного отношения содержит только нули. Например, отношения и "иметь общий делитель" являются рефлексивными. Отношения и "иметь сына" являются антирефлексивными. Отношение "быть симметричным относительно оси абсцисс" не является ни рефлексивным, ни антирсфлексив-ным: точка плоскости симметрична сама себе, если лежит на этой оси, и не симметрична себе, если не лежит на ней. Определение: Отношение называется симметричным, если для любой пары из отношения следует . Иными словами, отношение R является симметричным тогда и только тогда, когда для любой пары оно выполняется в обе стороны (или вовсе не выполняется). Матрица симметричного отношения симметрична относительно главной диагонали: . Определение: Отношение называется антисимметричным, если из отношений и следует, что . Отношение "быть симметричным относительно оси абсцисс" является симметричным: если первая точка симметрична второй относительно этой оси, то и вторая точка симметрична первой. Отношение является антисимметричным. Действительно, если , это означает, что . Нетрудно убедиться в том, что отношение симметрично тогда и только тогда, когда . Определение: Отношение называется транзитивным, если для любых а,b,с из отношений и следует . Отношения "быть равным", "жить в одном городе", "быть параллельным" являются транзитивными. Отношения "пересекаться", "быть сыном" не являются транзитивными. Замечание. В отличие от отношений рефлексивности и симметричности, для отношения транзитивности не формулируется противоположного понятия (антитранзитивности). Определение: Транзитивным замыканием отношения называется отношение, определяемое следующим образом: если в множестве существует цепочка из элементов , в которой между каждыми двумя соседними элементами выполняется отношение , то говорят, что существует транзитивное замыкание . Замечание. Замыкание является весьма общим математическим понятием. Упрощенно говоря, замкнутость означает, что многократное повторение допустимых шагов не выводит за определённые границы. Например, множество натуральных чисел замкнуто относительно операции сложения, однако открыто (то есть незамкнуто) относительно операции деления. Если отношение транзитивно, то, очевидно, (и наоборот). Например, отношение "быть делителем" транзитивно для любой цепочки элементов и само является транзитивным замыканием этого отношения. Если отношение не транзитивно, то Например, транзитивным замыканием отношения "быть сыном" является отношение "быть прямым потомком", включающее в себя понятия "быть сыном", "быть внуком", "быть правнуком" и так далее. 6. Основные понятия теории множеств: отношение эквивалентности и отношение частичного порядка Отношения эквивалентности Определение: Отношение называется отношением эквивалентности (или просто эквивалентностью), если оно рефлексивно, симметрично и транзитивно. Будем говорить, что имеет место разбиение множества А на классы, если существует система непустых, попарно не пересекающихся множеств такая, что Теорема. Между совокупностью различных разбиений множества А на классы, и семейством всех отношений эквивалент пост а на этом множестве существует взаимнооднозначное соответствие. Пример 1. а) Отношение равенства (часто обозначается ) на любом множестве является отношением эквивалентности. Равенство - это минимальное отношение эквивалентности в том смысле, что при удалении любой пары из этого отношения (то есть любой единицы на главной диагонали матрицы ) оно перестаёт быть рефлексивным и, следовательно, уже не является эквивалентностью. Отношения порядка Определение 1. Отношение называется отношением нестрогого порядка, если оно является рефлексивным, антисимметричным и транзитивным. Определение 2. Отношение называется отношением строгого порядка, если оно является антирефлексивным, антисимметричным и транзитивным. Оба типа отношений вместе называются отношениями порядка. Элементы сравнимы по отношению порядка , если выполняется одно из двух отношений или . Множество , на котором задано отношение порядка, называется полностью упорядоченным, если любые два его элемента сравнимы. В противном случае, множество называется частично упорядоченным. Пример 3. а) Отношения и являются отношениями нестрогого порядка, отношения и - отношениями строгого порядка (на всех основных числовых множествах). Оба отношения полностью упорядочивают множества и . 7. Основные понятия теории множеств: классы эквивалентности, разбиение множества, фактор-множество, утверждения об отношениях, порожденных разбиениями множеств. Если отношение эквивалентности на А и , соответствующее ему разбиение множества А на классы, то множества называются классами эквивалентности, а семейство обозначается, символом и называется фактор-множеством множества А по отношению . Мощность множества называется индексом разбиения. Фактор-множество множества N по отношению «иметь общий остаток от деления на 5» состоит из пяти счетных классов: Одной из наиболее часто встречающихся операций над множествами является операция разбиения множества на систему подмножеств. Так, система курсов данного факультета является разбиением множества студентов факультета; система групп данного курса является разбиением множества студентов курса. Пример. Продукция предприятия: — высший сорт, I, II, брак. Рассмотрим некоторое множество M и систему множеств М = {X 1 , X 2 , ..., X n } Система множеств M называется разбиением множества M, если она удовлетворяет следующим условиям: 1. Любое множество X из M является подмножеством множества М ∀ X∈M: X⊆M; 1. Любые два множества X и Y из М являются непересекающимися ∀ X∈М, ∀Y∈M: X≠Y → X∩Y=∅. 1. Объединение всех множеств, входящих в разбиение, дает множество M X 1 ∪ X 2 ∪ ...∪ X n =M. 8. Основные понятия теории множеств: функции, их области определения и области значений; обратная функция, суперпозиции функций. 9. Основные понятия теории множеств: функции со специальными свойствами: сюръективная, инъективная, биективная, константная, тождественная. 10. Основные понятия теории множеств: понятие счетного множества, множество натуральных чисел, рациональных чисел, вещественных чисел, диагональный принцип Кантора. 11. Основные понятия теории множеств: понятие бесконечного множества, теорема Дедекинда. 12. Основы комбинаторики: типы задач комбинаторики, понятие выборки, типы выборок. Основные правила комбинаторики Основными способами решения комбинаторных задач являются методы, которые мы будем именовать «правило суммы» и «правило произведения ». Правило суммы. Правило суммы для двух объектов: Пусть объект а можно выбрать m способами, а объект b — n способами, и существует к общих способа выбора объектов а и b. тогда один из объектов а или b можно выбрать способами. Это правило эквивалентно следующему свойству мощности: Правило суммы можно сформулировать для произвольного числа объектов. Для этого достаточно использовать формулу для мощности объединения конечного числа множеств. Для случая трех множеств формула имеет вид: Правило суммы для трех объектов: Пусть объект а можно выбрать способами, объект b — способами и объект с — способами, и существует общих способа выбора одного из объектов а и b, общих способа выбора одного из объектов а и с, общих способа выбора одного из объектов b и с, а также известно общих способа выбора одного из объектов а, b и с, тогда число всех способов выбора одного из объектное а или b или с вычисляется по формуле: Понятие выборки и типы +Набор элементов из множества называется выборкой объема из элементов или -выборкой. Выборка называется упорядоченной, если порядок следования элементов в ней задан. Две упорядоченные выборки, различающиеся лишь порядком следования элементов, считаются различными. Если порядок следования элементов не является существенным, то выборка называется неупорядоченной. В выборках могут допускаться или не допускаться повторения элементов. В зависимости от способа формирования все выборки в комбинаторике классифицируют как размещения, перестановки и сочетания с повторениями и без повторений элементов. Понятие k-выборки Понятие -выборки Пусть конечное непустое множество. Возможны два способа выбора элементов из множества А : выбор с возвращением и выбор без возвращения. Опишем их при помощи следующей таблицы. При реализации описанных в таблице процедур мы получаем комбинацию элементов из множества А вида , которая называется -выборкой из а элементов. В случае «выбора с возвращением» эта комбинация может содержать повторяющиеся, элементы, и называется, -выборкой из n элементов с повторениями. При реализации процедуры «выбор без возвращения» полученная комбинация не содержит повторяющихся элементов и называется r-выборкой из n элементов без повторений. Выборка называется упорядоченной, если существенным является не только состав элементов в ней, но и порядок их выбора. Две упорядоченные -выборки считаются различными, если они отличаются либо составом элементов, либо порядком их расположения. В неупорядоченных выборках порядок расположения элементов не существенен, две различные неупорядоченные-выборки имеют разный состав элементов. Элементы упорядоченной выборки заключаются в круглые скобки (например (1,2)). Элементы неупорядоченной выборки без повторений заключаются в фигурные скобки (например {1,2}), а элементы неупорядоченной выборки с повторениями в квадратные скобки (например [1,2]). Упорядоченные выборки (3,2) и (2,3) считаются различными, хотя и составлены из одних и тех же элементов. Для тех же самых элементов «2» и «3» неупорядоченные выборки {3,2} и {2,3} (или [3,2] и [2,3]) считаются одной и той же. Рассмотрим множество, которое содержит три элемента А — {1, 2, 3} . Составим из элементов этого множества всевозможные 2 - выборки. Упорядоченные 2-выборки без повторений: (1,2), (2,1), (1,3), (3, 1), (2,3), (3,2). Упорядоченные 2-выборки с повторениями: (1,2), (2, 1), (1,3), (3,1), (2,3), (3,2), (1,1), (2,2), (3,3). Неупорядоченные 2-выборки без повторений: {1,2}, {1,3}, {2,3}. Неупорядоченные 2-выборки с повторениями: [1,2], [1,3], [2,3 , [1,1], [2,2], [3,3]. 13. Основы комбинаторики: правило произведения. Правило произведения. Правило произведения для двух объектов: Пусть объект а можно выбрать m способами и после каждого такого выбора объект b можно выбрать n способами, тогда выбор пары объектов а и b в указанном порядке можно осуществить m • n способами. Данное правило произведения равносильно утверждению Правило произведения является следствием теоремы о мощности прямого произведения конечного числа конечных множеств. Правило произведения для случая произвольного числа объектов формулируется следующим образом: Пусть объект можно выбрать способами, способами, . . . , способами, причем выбор каждого из последующих объектов не зависит от выбора предыдущих объектов, тогда общее число полученных таким образом упорядоченных наборов можно выбрать способами. Последнее правило применяется, если требуется выполнить одно за другим одновременно действий, на одно из которых наложено ограничение. 14. Основы комбинаторики: размещение без повторений. Размещениями из n элементов по к называются упорядоченные -выборки из n элементов. Размещениями без повторений из n элементов по называются упорядоченные -выборки из n элементов без повторений. Их число обозначается Перестановками из n элементов называются размещения без повторений из n элементов по n . Их число обозначается, . Теорема. Имеют место следующие равенства: где Доказательство. Пусть произвольное множество, — упорядоченная -выборка без повторений, составленная из элементов множества. Она представляет собой набор длины вида , в котором Число таких наборов равно мощности прямого произведения множеств В силу теоремы о мощности прямого произведения имеем: Умножим и разделим последнее выражение на и получим первое равенство из (3.1). 15. Основы комбинаторики: размещение с повторениями. Размещениями с повторениями из n элементов по называются упорядоченные -выборки из n элементов с повторениями. Их число обозначается Размещения с повторениями из элементов множества А по к представляют собой упорядоченный набор , в котором каждый из элементов , может быть выбран n способами. В силу правила произведения указанный набор может быть выбран способами, что и доказывает второе из равенств (3.1). Третье получается из первого при Теорема доказана. 16. Основы комбинаторики: сочетание без повторений. 17. Основы комбинаторики: сочетание с повторениями. Сочетаниями из а элементов по называются неупорядоченные k-выборки из n элементов. Сочетаниями без повторений из n элементов по k называются неупорядоченные k -выборки из n элементов без повторений. Их число обозначается . Сочетаниями с повторениями из n элементов по k называются неупорядоченные k -выборки из n элементов с повторениями. Их число обозначается . Теорема. Имеют место следующие равенства: (3.2) Доказательство. Прежде чем доказать равенство для в общем случае, рассмотрим пример. Пусть , тогда выборки, , представляют собой сочетания без повторений по 2, составленные из элементов множества А. Из каждого сочетания можно получить, производя в нем «перестановку» элементов, размещения без повторений по 2 из элементов множества А. Этот процесс изобразим в виде следующей схемы (см. рис. 13). На основании вышеизложенного имеем равенство: Аналогичная ситуация имеет место в общем случае: чтобы получить все размещений, нужно получить всевозможные сочетания из а элементов по к (их число равно ), затем в каждом из сочетаний сделать всевозможные «перестановки». Число перестановок, которые можно получить из одного сочетания длины k, равно Р(k). Очевидно, что из разных сочетаний без повторений не могут получиться одинаковые перестановки. Поэтому , откуда следует первое из равенств (3.2). Перейдем к доказательству второго равенства (3.2). Введем обозначения: - множество сочетаний с повторениями из чисел {1,2,..., n) по , множество сочетаний без повторений из натуральных чисел Неупорядоченная k-выборка однозначно определяется комбинацией из номеров ее элементов . Не ограничивая общности рассуждений, можно считать, что . Положим, , тогда для и выборка Пусть произвольная комбинация из так как она не зависит от порядка расположения элементов, то можно считать, что . Положим , так как для , следовательно, Мы установили взаимооднозначное соответствие между множествами , откуда следует, что их мощности совпадают Теорема доказана. 18.Основы комбинаторики: бином Ньютона. Свойства сочетаний. Бином Ньютона При помощи формулы (3.2) посредством алгебраических преобразований легко получить следующие свойства сочетаний: Биномом Ньютона называется равенство Докажем его, пользуясь методом математической индукции. При n = 1 имеем очевидное равенство: Предположим, что равенство (3.3) имеет место при n = k и, исходя из этого предположения, докажем его для случая n = к + 1: Из равенства (3.3), положив сначала х = а = 1, затем х = {—а) — 1, получим новые свойства сочетаний: Так как сочетание без повторений из n элементов по k представляет собой k-элементное подмножество множества мощности n, то величина равна числу различных подмножеств этого множества. В связи с этим из свойства 5) сочетаний получаем теорему о мощности булеана. 19. Рекуррентные соотношения: решение однородных рекуррентных уравнений с постоянными коэффициентами. (4.10) известно как соотношение Фибоначчи. Характеристическое уравнение для соотношения (4.10) имеет вид: . Корни характеристического уравнения Таким образом, общее решение соотношения Фибоначчи находится по формуле: (4.11) Числами Фибоначчи называется решение соотношения (4.10), удовлетворяющее начальным условиям F( 1) = 0, F(2) = 1. Полагая в формуле (4.11) n = 1 и n = 2, получим для и систему уравнений: откуда находим Поэтому Отметим, что это последнее выражение при всех натуральных значениях а принимает целые неотрицательные значения. Рекомендации к решению задач: Нахождение общего и частного решений рекуррентного соотношения состоит из следующих шагов: 1) выписывается характеристическое уравнение и находятся его корни 2) если , общее решение ЛРС записывается в виде: 3) если , общее решение ЛРС также содержит две произвольные и постоянные 4) для нахождения частного решения , удовлетворяющего условию составляется система уравнений с неизвестными и . В случае 2) она имеет вид в случае 3) - Затем найденное решение системы подставим в формулу для 2) в случаях 2) или 3) соответственно, получим частное решение ЛРС. Если (это возможно, когда , решение рекуррентного соотношения имеет вид . Решением в этом случае будет функция . 20. Основные понятия переключательных функций: понятие ПФ, полностью и неполностью(частные) определенные ПФ; способы задания ПФ; теорема о числе различных ПФ от n аргументов. 21. Основные понятия переключательных функций: теорема о полноте ПФ, содержащих отрицание, конъюнкцию и дизъюнкцию; получение аналитического описания ПФ по таблице истинности. 22. Основные понятия переключательных функций: полиномиальное представление ПФ, теорема Жегалкина, класс линейных ПФ. 23. Основные понятия переключательных функций: класс самодвойственных ПФ, доказательство замкнутости класса. 24. Основные понятия переключательных функций: класс монотонных ПФ, доказательство замкнутости класса. 25. Основные понятия переключательных функций: класс монотонных ПФ, теорема о немонотонных функциях. 26. Основные понятия переключательных функций: теорема Поста о функциональной полноте. 27. Основные понятия логики высказываний: понятие высказывания, аксиомы алгебры логики, проблема разрешимости. 28. Основные понятия исчисления высказываний: понятие аксиоматической системы, доказательство в теории, правило вывода. 29. Основные понятия исчисления высказываний: теорема дедукции. 30. Основные понятия исчисления высказываний: связь между алгеброй логики, теорией множеств и аксиоматическим исчислением высказываний. 31. Основные понятия исчисления высказываний: проблемы исчисления высказываний - разрешимость, непротиворечивость, полнота, независимость. 32. Основные понятия логики предикатов: понятие предиката, логические операции над предикатами, области истинности предиката, кванторные операции. 33. Основные понятия логики предикатов: основные тождества — коммутативность, ассоциативность, дистрибутивность, законы де-Моргана, законы поглощения. 34. Основные понятия логики предикатов: приведенная и предваренная нормальная форма, теорема о представимости любой формулы в предваренной нормальной форме. 35. Алгоритмические модели: машина Тьюринга. 36. Алгоритмические модели: частично-рекурсивные функции. 37. Алгоритмические модели: нормальные алгоритмы Маркова. 38. Основы теории графов: графы, орграфы, вершины, ребра, дуги; представление графа матрицей смежности и матрицей инцидентности. 39. Основы теории графов: локальные степени вершин графа, теорема о числе вершин графа нечетной степени. 40. Основы теории графов: циклы Эйлера в графе, критерий существования эйлеровых циклов. 41. Основы теории графов: маршруты в графах, достижимость вершин, компоненты связности графа и сильной связности орграфа, алгоритм Уоршалла вычисления матрицы достижимости. 42. Основы теории графов: маршруты в графах, алгоритм Беллмана-Форда нахождения оптимального маршрута в графе. 43. Основы теории графов: маршруты в графах, алгоритм Дейкстры нахождения оптимального маршрута в графе. 44. Основы теории графов: понятие дерева, способы обхода деревьев. 45. Основы теории графов: теорема Кэли о числе различных деревьев на n вершинах. 46. Основы теории графов: понятие остовного дерева графа, алгоритм Примы. 47. Основы теории графов: задача о потоках в сетях, теорема о потоке в сечении, алгоритм Форда-Фалкерсона нахождения максимального потока. 48. Основы теории графов: метод ветвей и границ в приложении к задаче коммивояжера. |