лекция 4. Документ Microsoft Word. Лекция4 Основные понятия дискретной математики. Комбинаторика. Теория вероятности
 Скачать 18.92 Kb.
|
|
Лекция№4 Основные понятия дискретной математики. Комбинаторика. Теория вероятности Дискретная (прерывная или конечная) математика представляет собой область математики, в которой изучаются свойства структур конечного характера, а также бесконечных структур, предполагающих скачкообразность происходящих в них процессов или отделимость составляющих их элементов. Бурное развитие дискретной математики обусловлено прогрессом компьютерной техники, необходимостью создания средств обработки и передачи информации, а также представления различных моделей на компьютерах, являющихся по своей природе конечными структурами. Дискретная математика включает в себя такие разделы: теорию множеств, алгебраические системы, числовые системы, теорию графов, комбинаторику, алгебру логики. Элементы математической логики Математическая логика - это раздел математики, который занимается исследованием высказываний с точки зрения их формального строения. Под высказыванием понимается некоторая фраза, высказанная словами, или высказанное суждение. 1. Высказывания Определение. Высказывание – это повествовательное предложение, о котором можно однозначно сказать истинно оно или ложно. Например, к высказываниям относятся следующие предложения: 1. Москва – столица России. 2. К форменным элементам крови относятся эритроциты, лейкоциты и тромбоциты. 3. У здоровых людей температура тела 26,6°С. Из приведенных высказываний первые два относятся к истинным, а последнее – к ложным. Высказывания обычно обозначаются большими буквами латинского алфавита: , , … Если высказывание истинно, то это записывается так: [А] = 1, если ложно, то [А] = 0. Следовательно, если приведенные выше высказывания обозначить соответственно: А1, А2, А3, то [А1] = [А2] = 1, [А3 ] =0. Из этого видно, что в математической логике важна не содержательная часть высказывания, а истинно или ложно данное высказывание. Была разработана специальная символика для компактной записи утверждений и описание операций над ними. Таким образом, используя логические операции, возможно из простых высказываний построить сложные высказывания. 2. Логические операции К наиболее часто встречаемым логическим операциям относятся: отрицание, дизъюнкция, конъюнкция. Отрицание Определение. Отрицанием высказывания А называется новое высказывание, которое обозначается А (читается «не А») и истинно, если А ложно, и ложно, если А истинно. Отрицание высказывания определяется таблицей истинности
Например. Высказывание А – «Пенициллин относится к антибиотикам», тогда высказывание 𝐴̅– «Пенициллин не относится к антибиотикам». Если для первого высказывания значение [А] = 1, т. е. истинно, то для второго [А̅] = 0, ложно. Дизъюнкция Определение. Дизъюнкцией высказываний АиВ называется новое высказывание, которое обозначается А ∪ В (читается А или В) и ложно только в том случае, если ложны оба высказывания, а в остальных случаях истинно. Дизъюнкция (сумма высказываний). Значение дизъюнкции для различных вариантов высказываний А и В приведены в таблице
Например. Высказывание A — «Экзамены проводятся в письменной форме»; высказывание В — «Экзамены проводятся в устной форме». Эти два высказывания являются истинными, т.е. [А] = [В] = 1. Тогда A ∪В = 1. Следовательно, сложное высказывание будет истинным: «Экзамены проводятся в письменной или в устной форме». Если возьмем отрицание этих двух высказываний, то получим следующее: 𝐴̅— «Экзамены не проводятся в письменной форме»; и 𝐵̅ — «Экзамены не проводятся в устной форме», т.е. [𝐴̅] = [𝐵̅] = 0. Тогда 𝐴̅ ∪ 𝐵̅ = 0. То есть высказывание «Экзамены не проводятся в письменной или в устной форме» будет ложным. Конъюнкция Определение. Конъюнкцией высказываний А и В называется новое высказывание, которое обозначается А∩В (читается А и В) и истинно только в том случае, когда истинны оба высказывания, в остальных случаях— ложно. Конъюнкция(произведение высказываний Значения конъюнкции представлены в таблице
Например. Высказывание А — «Сердце относится к сердечно -сосудистой системе» и высказывание В — «Сосуды относятся к сердечно -сосудистой системе» являются истинными. Тогда А∩ В = 1. Следовательно, истинным будет и высказывание — «Сердце и сосуды относятся к сердечно - сосудистой системе». Если взять отрицание высказываний А и В,то их комбинации будут ложными Таким образом, в математической логике можно определить истинность сложного высказывания, полученного с помощью логических операций, если известны значения истинности простых высказываний, из которых оно состоит. Основные понятия комбинаторики Комбинаторика — раздел математики, в котором изучаются задачи выбора элементов из заданного множества и размещения этих элементов в каком-либо порядке. Множество называется конечным, если существует число, указывающее на количество его элементов. Иначе множество бесконечное. Существует два способа задания множеств: 1. Перечисление всех элементов данного множества; 2. Задание множеств с помощью характерных свойств, которыми обладают все элементы данного множества и не обладают элементы других множеств. Упорядоченные множества – это множества, в которых задан порядок следования элементов. В таких множествах каждому элементу отведено свое место, на котором он расположен среди других элементов. И, если этот порядок изменить, то будет уже другое множество. Факториал п! - это произведение всех натуральных чисел от 1 до n включительно п! = 1·2·3·... ·п (читается п – факториал) При нахождении факториалов следует помнить, что 0! = 1! = 1 (по определению) Основные задачи комбинаторики Перестановки. Размещения. Сочетания Перестановки Определение. Перестановкой из п элементов называется каждая последовательность этих элементов в каком-либо порядке. Так как каждая перестановка содержит все п элементов, то различные перестановки отличаются друг от друга только порядком следования элементов. Число всех возможных перестановок из п элементов обозначают Рп, Теорема. Число всех возможных перестановок из п элементов равно произведению всех натуральных чисел от 1 до п: Рп =1·2·3...п = п! Пример 1. Число всех возможных перестановок букв а,b,с равно: а,b,с; a.c.b; b,а,с; b,с,а; с,а,b; с,b,а. Всего 6 перестановок, что соответствует: Р3= 3! = 1·2·3 = 6. Пример 2. Сколько имеется вариантов расстановки 5 книг на одной полке? Решение. Искомое число вариантов равно: Р5 =1·2·3·4·5 = 120. Иногда задача заключается в упорядочении не всех п объектов, а лишь некоторой последовательности из п объектов. Такие упорядоченные последовательности называются размещениями из п элементов по k элементов. Размещения Определение. Размещениями из п элементов по к в каждом называются такие последовательности, каждая из которых содержит к элементов, взятых из числа данных п элементов, и которые отличаются друг от друга либо самими элементами, либо порядком их расположения. Число размещений из п элементов по k обозначается А (читается «А из п по к») и вычисляется по формуле: Пример 3. Из трех букв а, b, с можно составить: три размещения по одной букве: а, b, с; шесть размещений по две буквы: а,b; а,с; b,а; b,c; с,а; с,b; шесть размещений по три буквы: а,b,с; а,с,b; b,а,с; b,с,а; с,а,b; с,b,а. Проверим по формуле: Пример 4. В конкурсе медсестер участвуют 12 человек. Имеется три призовых места (1, 2, 3 место). Сколько имеется вариантов распределения трех призовых мест. Решение. В данной задаче имеют значение и выбор трех участников конкурса, и распределение мест среди них. Следовательно, необходимо найти размещение из 12 элементов по 3. Иногда возникает необходимость не учитывать порядок следования элементов в размещении. Такие последовательности называются сочетаниями. Сочетания Определение. Сочетанием из п элементов по к называются любые последовательности из к элементов, входящих в число данных п элементов, и отличающиеся друг от друга хотя бы одним элементом. Число сочетаний из п элементов по k обозначается С (читается «С из п по к) и вычисляется по формуле: Пример 5. Из трех букв а, b, с можно составить : три сочетания по одной букве: а, b, с три сочетания по две буквы: а,b;b,с;а,с; и одно сочетание по три буквы: а,b,с. Проверим по формуле: Пример 6. В клетке содержится 10 мышей. Необходимо отобрать 4 мыши для проведения эксперимента. Сколькими способами это можно сделать? Решение. Так как порядок выбранных мышей не имеет значения, то используем формулу для нахождения сочетаний из 10 по 4: |