Пусть имеется М={ 
, 
}. Пустое множество Ø входит в это множество как подмножество. Одноэлементные множества тоже. Поставим каждому подмножеству кортеж длиной n, состоящий из 0 и 1.
0-если соответствующий элемент не входит в подмножество.
1-если входит.
Например, подмножеству { 
} будет соответствовать кортеж 010100000….0000…
Для вех подмножеств получим (0,0,0,…0), (1,0,0,…0), (0,1,0,0,...,0)… (1,1,1,…1)
Кортежей столько, сколько подмножеств. Это размещения, состоящие из двух элементов (0 и 1) и отличающиеся друг от друга либо элементами, либо их порядком. Это размещения с повторениями из двух по n: Получим
Ậ 
= 
.
Таким образом, мы доказали теорему:
Число подмножеств n-элементного множества равно .
Следствие: Так как число пустых подмножеств С 
(0)=1, одноэлементных-С 
= n, двухэлементных-С 
, трехэлементных-С 
, n-элементных С 
, то сумма 
С 
= .
Перестановки с повторениями.
Пусть мы имеем n элементов , , 
= n!. Пусть элемент повторяется 
раз, элемент 
- 
раз,…., 
- 
раз, где 
. Тогда число различных перестановок будет в ! меньше за счет одинаковых элементов , в ! раз меньше за счет одинаковых элементов ,…и в ! раз меньше за счет одинаковых элементов . Тогда число различных перестановок будет равно: (, ,…, )= 
.
Пример:
Сколько различных перестановок можно составить из слова МОЛОТОК?
Решение:
(М)=1; (О)=3; 
(Л)=1; 
(Т)=1; 
(К)=1;
(1,3,1,1,1)= 
= 840.
Сочетания с повторениями.
Пример:
На почте имеются открытки четырех видов: красные, желтые, зеленые и синие. Требуется 10 открыток. Сколькими способами можно их скомбинировать?
Решение:
Пусть мы отобрали 4 красных, 2 желтых, 2 зеленых и 2 синих открытки. Составим кортеж из 0 и 1. Выпишем столько единиц, сколько красная открытка встречается в нашем наборе, и поставим 0: 11110. Затем добавим кортеж для желтых -110. Получим 11110110. Добавим кортеж для зеленых и синих открыток. В последнем 0 не ставим. Получим кортеж 1111011011011. В нем 10 единиц и 3 нуля. Общая длина кортежа – 13. Таких кортежей можно составить столько, сколько перестановок с повторениями из 13.
|
|
(10,3)= 
= 286 – это и будет число сочетаний с повторениями из 4 по 10.
(10,3)= 
Таким образом, Ĉ 
.
В общем случае.
Пусть мы имеем n элементов , 
, из которых создаются сочетания с повторениями, и каждое сочетание содержит k элементов. Составим кортеж, который запишем вначале столько единиц, сколько элемент входит в сочетание, затем запишем 0. припишем кортеж из единиц и нуль для элемента 
и т.д. без последнего нуля. Получим: 111…1011…10…11…1
Единиц – k. Нулей – n-1. Длина кортежа n+ k -1
Общее число сочетаний с повторениями
Ĉ = 
(k,n-(k -1))= 
= 
,
Итак, Ĉ = ,
Основы математической логики.
Высказывания.
Повествовательное предложение, относительно которого можно сказать истинно или ложно утверждение, заключающееся в этом предложении, называется высказыванием.
Например:
«Какая прекрасная погода!»- предложение не является высказыванием, так как оно не повествовательное.
«Белгород-столица РФ»,- высказывание ложное.
«Белгород- центр Белгородской области»,- высказывание истинное.
В дальнейшем высказывания мы будем обозначать малыми латинскими буквами, и нас будет интересовать истинно (1) или ложно (0) его значение.
Приведенные примеры- примеры простых высказываний. Но очень часто произносятся предложения сложной структуры.
|
|
Например:
«Для того чтобы два треугольника были равны, необходимо и достаточно, чтобы у них были соответственно равны три стороны ».
Для анализа подобных высказываний, а в дальнейшем для анализа правильности рассуждений, необходимо рассмотреть основные логические операции.