Дискретная математика.

 

Элементы комбинаторики.

 

Если из некоторого количества элементов, различных меду собой, составлять различные комбинации, то среди них можно выделить три типа комбинаций, носящих общее название – соединения.

Рассмотрим подробнее эти три типа соединений:

 

1) Перестановки.

 

Определение. Если в некотором множестве переставлять местами элементы, оставляя неизменным их количество, то каждая полученная таким образом комбинация называется перестановкой.

 

Общее число перестановок из m элементов обозначается Pm и вычисляется по формуле:

2) Размещения.

 

Определение. Если составлять из т различных элементов группы по n элементов в каждой, располагая взятые элементы в различном порядке. Получившиеся при этом комбинации называются размещениями из т элементов по п.

 

Общее число таких размещений расчитывается по формуле:

 

Вообще говоря, перестановки являются частным случаем размещений.

 

 

3) Сочетания.

 

Определение. Если из т элементов составлять группы по п элементов в каждой, не обращая внимания на порядок элементов в группе, то получившиеся при этом комбинации называются сочетаниями из т элементов по п.

 

Общее число сочетаний находится по формуле:

 

Также одним из вариантов комбинаций являются перестановки с повторяющимися элементами.

Если среди т элементов имеется т1 одинаковых элементов одного типа, т2 одинаковых элементов другого типа и т.д., то при перестановке этих элементов всевозможными способами получаем комбинации, количество которых определяется по формуле:

 

 

Пример. Номер автомобиля состоит из трех букв и трех цифр. Сколько различных номеров можно составить, используя 10 цифр и алфавит в 30 букв.

 

Очевидно, что количество всех возможных комбинаций из 10 цифр по 4 равно 10.000.

Число всех возможных комбинаций из 30 букв по две равно .

Если учесть возможность того, что буквы могут повторяться, то число повторяющихся комбинаций равно 30 (одна возможность повтора для каждой буквы). Итого, полное количество комбинаций по две буквы равно 900.

Если к номеру добавляется еще одна буква из алфавита в 30 букв, то количество комбинаций увеличивается в 30 раз, т.е. достигает 27.000 комбинаций.

Окончательно, т.к. каждой буквенной комбинации можно поставить в соответствие числовую комбинацию, то полное количество автомобильных номеров равно 270.000.000.

 

 

Бином Ньютона. (полиномиальная формула)

 

В дальнейшем будет получена формула бинома Ньютона с помощью приемов дифференциального исчисления.

Бином Ньютона – это формула, выражающая выражение (a + b)n в виде многочлена. Эта формула имеет вид:

 

- число сочетаний из п элементов по k.

 

Широко известные формулы сокращенного умножения квадрата суммы и разности, куба суммы и разности, являются частными случаями бинома Ньютона.

Когда степень бинома невысока, коэффициенты многочлена могут быть найдены не расчетом по формуле количества сочетаний, а с помощью так называемого треугольника Паскаля. (Блез Паскаль (1623 – 1662) – французский математик).

Этот треугольник имеет вид:

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

1 7 21 35 35 21 7 1

1 8 28 56 70 56 28 8 1

…………………

 

 

Формула бинома Ньютона может быть обобщена для произвольного числа слагаемых.

 

Напомним, что при вычислениях 0! принимается равным 1.

 

 

Пример. В разложении найти члены, содержащие хa, если k=3, p=2, n=8, a=9.

 

По фомуле бинома Ньютона имеем:

C учетом числовых значений:

 

В принципе, можно написать разложение этого выражения в многочлен, определить коэффициеты либо непосредственно, либо из треугольника Паскаля (степень бинома сравнительно невелика), однако, делать это не обязательно, т.к. необходимо найти только член разложения, содержащий х9.

Найдем число i, соответствующее этому члену:

 

Находим:

 

 

Пример. В разложении найти члены, содержащие xg. т=9, g=6.

 

По обобщенной формуле бинома Ньютона получаем:

 

Для нахождения полного разложения необходимо определить все возможные значения ni, однако, это связано с громадными вычислениями. Однако, т.к. надо найти только члены, содержащие х6, то n1 = 6, а сумма всех четырех значений п равна 9. Значит, сумма п2 + п3 + п4 = 3.

 

Рассмотрим возможные значения этих величин:

 

n2
n3
n4

 

Искомые члены разложения:

 

 

 

 

Элементы математической логики.

 

Математическая логика – разновидность формаьной логики, т.е. науки, которая изучает умозаключения с точки зрения их формального строения.

 

Определение. Высказыванием называется предложение, к которому возможно применить понятия истинно или ложно.

 

В математической логике не рассматривается сам смысл высказываний, определяется только его истинность или ложность, что принято обозначать соответственно И или Л.

Понятно, что истинные и ложные высказывания образуют соответствующие множества. С помощью простых высказываний можно составлять более сложные, соединяя простые высказывания союзами “и”, “или”.

Таким образом, операции с высказываниями можно описывать с помощью некоторого математического аппарата.

 

Вводятся следующие логические операции (связки) над высказываниями

 

1) Отрицание. Отрицанием высказывания Р называется высказывание, которое истинно только тогда, когда высказывание Р ложно.

Обозначается Р или .

 

Соответствие между высказываниями определяется таблицами истинности. В нашем случае эта таблица имеет вид:

 

P Р
И Л
Л И

 

2) Конъюнкция. Конъюнкцией двух высказываний P и Q называется высказывание, истинное тогда и только тогда, когда истинны оба высказывания.

Обозначается P&Q или РÙQ.

 

P Q P&Q
И И И
И Л Л
Л И Л
Л Л Л

 

3) Дизъюнкция. Дизъюнкцией двух высказываний P и Q называется высказывание, ложное тогда и только тогда, когда оба высказывания ложны.

Обозначается PÚQ.

 

P Q PÚQ
И И И
И Л И
Л И И
Л Л Л

 

4) Импликация. Импликацией двух высказываний P и Q называется высказывание, истинное тогда и только тогда, когда высказывание Р истинно, а Q – ложно.

Обозначается PÉQ (или РÞQ). Высказывание Р называется посылкой импликации, а высказывание Q – следствием.

 

P Q PÞQ
И И И
И Л Л
Л И И
Л Л И

 

5) Эквиваленция. Эквиваленцией двух высказываний P и Q называется высказывание, истинное тогда и только тогда, когда истинности высказываний совпадают.

Обозначается Р~Q или РÛQ.

 

P Q P~Q
И И И
И Л Л
Л И Л
Л Л И

 

С помощью этих основных таблиц истинности можно составлять таблицы истинности сложных формул.

 

 

Пример. С помощью таблиц истинности проверить, являются ли эквивалентными формулы j и y.

Составим таблицы истинности для каждой формулы:

 

p r (pÙr)
И И Л И И
И Л Л Л И
Л И И Л Л
Л Л И Л Л

 

p r
И И Л Л Л И
И Л Л И И И
Л И И Л И И
Л Л И И И И

 

Данные формулы не являются эквивалентными.

 

Пример. С помощью таблиц истинности проверить, являются ли эквивалентными формулы j и y.

 

 

Составим таблицы истинности для заданных формул.

 

 

p q r pÛq (pÛq)Úr
И И И И И
И И Л И И
И Л И Л И
И Л Л Л Л
Л И И Л И
Л И Л Л Л
Л Л И И И
Л Л Л И И

 

 

p q r pÞq qÞp (pÞq)Ú(qÞp) (pÞq)Ú(qÞp)Úr
И И И И И И И
И И Л И И И И
И Л И Л И И И
И Л Л Л И И И
Л И И И Л И И
Л И Л И Л И И
Л Л И И И И И
Л Л Л И И И И

 

Из составленных таблиц видно, что данные формулы не равносильны.

 








Дата добавления: 2015-08-14; просмотров: 936;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.033 сек.