Задача о числе подмножеств данного множества.

↑

▷ Содержание

⇐ ПредыдущаяСтр 3 из 15Следующая ⇒

Пусть имеется М={ , }. Пустое множество Ø входит в это множество как подмножество. Одноэлементные множества тоже. Поставим каждому подмножеству кортеж длиной 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) его значение.

Приведенные примеры- примеры простых высказываний. Но очень часто произносятся предложения сложной структуры.

Например:

«Для того чтобы два треугольника были равны, необходимо и достаточно, чтобы у них были соответственно равны три стороны».

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

Познавательные статьи:



Как правильно слушать собеседника

Типичные ошибки при выполнении бросков в баскетболе

Принятие христианства на Руси и его значение

Средства массовой информации США