Материал: Дискретная математика. учебное пособие. Горбунов В.В., Лапшина М.Л

Вопросы для самопроверки

1. Что такое комбинаторика и для чего она нужна?

2. Что называется перестановкой n-элементного множества?

3. Дайте определение размещения из п элементов по т элементов.

4. Дайте определение сочетания из п элементов по т элементов.

5. В чем отличие размещений от перестановок?

6. В чем отличие сочетаний от размещений?

7. Сколькими способами можно разместить три книги на книжной полке?

8. Запишите формулу для вычисления числа сочетаний элементов, используемую в формуле бинома Ньютона.

9. Как найти число перестановок с повторениями?

10. Покажите, что сумма делится на р, где р — простое число.

11. Докажите свойства биномиальных коэффициентов.

Задачи по теме «Комбинаторные формулы. Бином Ньютона»

Задача 1. Составьте все перестановки:

1) из трех букв: а, b, с;

2) из четырех цифр: 5, 4, 3, 2.

Ответ:

1) abc, acb, bac, bca, cab, cba;

2) 5432, 5423, 5342, 5324, 5243, 5234, 4532, 4523, 4325, 4352, 4235, 4253, 3542,3524,3452,3425,3245, 3254, 2345, 2354, 2435, 2453, 2534, 2543.

Задача 2. Составьте все размещения:

1) из четырех букв а, b, с, d по 3 буквы в каждом (без повторений);

2) из четырех цифр: 1, 3, 5, 7 по 2 цифры в каждом.

Ответ:

1) аbс, abd, acb, acd, adb, adc, bac, bad, bca, bcd, bda, bdc, cab, cad, cba, cbd, cda, cdb, dab, dac, dba, dbc, dca, dcb;

2)13, 15, 17, 31, 35, 37, 51, 53, 57, 71, 73, 75.

Задача 3. Вычислите: 1) ; 2) .

Ответ: 120, 5.

Задача 4. Вычислите: 1)Р₆ , 2) ; 3) .

Ответ: 720, 54, 116.

Задача 5. Составьте все сочетания (без повторений) из пяти букв: а, b, с, d, е по 3 буквы в каждом.

Ответ: abc, abd, abe, acd, асе, ade, bed, bee, bde, cde.

Задача 6. Вычислите: 1) ; 2) ; 3) .

Ответ: 15, 4450, 1020.

Задача 7. Проверьте равенства:

l) ; 2) .

Задача 8. Сколько номеров, состоящих из трех букв, за которыми идут две цифры, можно составить, используя 32 буквы и 10 цифр?

Решение. Обозначим множество из 32 букв через А, а множество из 10 цифр через В. Тогда = 32; |В| = 10. Каждый номер требуемого вида является кортежем длины 5 из декартова произведения . Тогда = .

Задача 9. Сколькими способами можно распределить уроки в шести классах между тремя учителями, если каждый учитель будет преподавать в двух классах?

Решение: Первый учитель может выбрать два класса из шести различными способами. После выбора первого учителя второй может выбрать два класса из четырех оставшихся различными способами. Два учителя могут выбрать по два класса различными способами. Если они уже сделали выбор, то третий может взять только оставшиеся два класса. Поэтому число способов, которыми можно распределить уроки в шести классах между тремя учителями равно

Задача 10. Сколько существует пятизначных номеров:

1) не содержащих цифру 8;

2) составленных из цифр 2,3,5,7?

Ответ: 1) 59 049, 2) 1024. Указание: здесь .

Задача 11. Сколькими способами можно разложить 28 различных предметов по четырем ящикам, так, чтобы в каждом ящике оказалось по 7 предметов?

Ответ: Число способов равно: Р(7, 7, 7, 7) =

Задача 12. Сколько имеется четырехзначных чисел, у которых каждая следующая цифра больше предыдущей?

Ответ: для чисел от 1234 до 6789 существует комбинаций.

Задача 13. Сколько имеется четырехзначных чисел, у которых каждая следующая цифра меньше предыдущей?

Ответ: для чисел от 9876 до 3210 существует комбинаций.

3. Логические операции

3.1. Основные понятия

Математическая логика изучает различные способы построения логических рассуждений, т.е. исследует соотношения между основными понятиями математики, на базе которых доказываются математические утверждения. Начальным разделом математической логики является алгебра высказываний.

Высказыванием называется повествовательное предложение, о котором можно сказать истинно оно или ложно. Возможность одновременной истинности и ложности высказывания в классической математической логике исключается. Высказывания обозначают прописными буквами латинского алфавита A, B, Х, P, Q и т.д. Например, предложения «Воронеж - столица России» и «семь – простое число» являются высказываниями, причем первое высказывание оказалось ложным, а второе – истинным. На высказывание можно смотреть как на величину, которая может принимать только одно из двух значений: «истина» (другие варианты: «И», «1») или «ложь» (другие варианты: «Л», «0»). В логике высказываний главное – не содержание высказывания, а его истинность или ложность.

Высказывания, верные в одних ситуациях и ложные в других ситуациях, называются переменными высказываниями.

Множество или называется множеством истинностных значений. Использование 0 и 1 позволяет развить алгебру высказываний в виде двоичной (булевой) алгебры, заданной на множестве элементов: 0 и 1. Переменные, принимающие значения на множестве 0 и 1, называются булевыми переменными.

3.2. Простейшие связки (операции)

Алгебра высказываний изучает различные способы сочетания отдельных высказываний для построения новых высказываний. Эти новое высказывание называется составным, в то время как высказывания, из которых они образованы, называются простыми (элементарными) составляющими, компонентами, «пропозициональными переменными». Любое высказывание, даже такое, которое на самом деле является сложным, может быть использовано в качестве одного из простых составляющих какого-то другого составного высказывания.

Значение истинности составного высказывания определяется значениями истинности его компонент.

Формулой высказывания называется выражение, составленное из простых высказываний с помощью операций над высказываниями и скобок, обращающееся в конкретное высказывание при подстановке вместо переменных высказываний конкретных высказываний.

Среди операций над компонентами основными считаются дизъюнкция, конъюнкция, отрицание, импликация, эквивалентность.

Дизъюнкцией (логической суммой, операцией «ИЛИ») высказываний и называется высказывание, обозначаемое , ложное, когда оба высказывания ложны, и истинное во всех других случаях. Дизъюнкция, например, может быть использована для записи логической формулы высказывания «идет дождь или снег». В качестве простых высказываний используются высказывания =«идет дождь», =«идет снег». Высказыванию «идет дождь или снег» соответствует формула .

Задача 14. В технической библиотеке имеются книги по математике, физике, химии и т.д., всего по 16 разделам науки. Поступили очередные четыре заказа на литературу. Сколько наборов из четырех заказов можно составить по 16 разделам науки?

Решение. Искомое число равно числу сочетаний с повторениями из 16 элементов по 4, т. е.

Задача 15. Сколькими способами можно составить дозор из трех солдат и одного офицера. Если имеется 80 солдат и 3 офицера?

Ответ: 246 480.

Задача 15. Сколько можно образовать различных трехзначных положительных целых чисел в десятичной системе счисления?

Решение

Из 10 цифр 0, 1, 2, 3, 4, 5, б, 7, 8, 9 можно образовать .

Но из них следует исключить те числа, которые начинаются с нуля. Таких чисел столько, сколько можно образовать размещений из 9 цифр по 2 (без нуля), т. е. . Следовательно, различных трехзначных чисел можно образовать 720 — 72 = 648.

Действие всех логических операций удобно иллюстрируется с помощью таблиц истинности. В частности, дизъюнкции высказываний соответствует следующая таблица истинности:

Таблица 1.

Например, имеются два высказывания P=«два - делитель пяти» и Q=«шесть - простое число». Дизъюнкция данных высказываний является ложным высказыванием.

Конъюнкцией (логическим произведением, операцией «И») высказываний и называется высказывание, обозначаемое , истинное, когда оба высказывания истинны, и ложное во всех других случаях. Конъюнкции соответствует следующая таблица истинности:

Таблица 2.

Например, имеются два высказывания P= «дважды два четыре» и Q= «регистрация фирмы требует наличия устава». Конъюнкция данных высказываний является истинным высказыванием.