Множество

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

Понятие «множество», как и любое другое исходное понятие математической теории не является строго определяемым. Его синони­мами являются «совокупность», «семейство», «класс», «система», «собрание», «ансамбль», «коллекция» и др.

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

Примеры множеств:

• 
  множество столов в комнате;
• 
  множество всех атомов на Марсе;
• 
  множество всех рыб в океане;
• 
  множество футболистов команды «Сибскана»
• 
  множество всех футбольных команд

Ниже перечислены основные операции над множествами:

§ объединение:

§ пересечение:

§ разность:

§ симметрическая разность:

§ дополнение:

Диаграмма Венна — схематичное изображение всех возможных пересечений нескольких (часто — трёх) множеств. Если пересечения позволяется указывать не все, получается более общий случай — круги Эйлера.

14 билет

Размещения, перестановки, сочетания

Пусть у нас есть множество из трех элементов . Какими способами мы можем выбрать из этих элементов два? .

Определение. Размещениями множества из различных элементов по элементов называются комбинации, которые составлены из данных элементов по элементов и отличаются либо самими элементами, либо порядком элементов.

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

Теорема. Число размещений множества из элементов по элементов равно

Доказательство. Пусть у нас есть элементы . Пусть — возможные размещения. Будем строить эти размещения последовательно. Сначала определим — первый элемент размещения. Из данной совокупности элементов его можно выбрать различными способами. После выбора первого элемента для второго элемента остается способов выбора и т.д. Так как каждый такой выбор дает новое размещение, то все эти выборы можно свободно комбинировать между собой. Поэтому имеем:

Пример. Сколькими способами можно составить флаг, состоящий из трех горизонтальных полос различных цветов, если имеется материал пяти цветов?

Решение. Искомое число трехполосных флагов:

Определение. Перестановкой множества из элементов называется расположение элементов в определенном порядке.

Так, все различные перестановки множества из трех элементов — это

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

Число всех перестановок из элементов обозначается (от начальной буквы французского слова “permutation”, что значит “перестановка”, “перемещение”). Следовательно, число всех различных перестановок вычисляется по формуле

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

Решение. Искомое число расстановки 8 ладей

по определению!

Определение. Сочетаниями из различных элементов по элементов называются комбинации, которые составлены из данных элементов по элементов и отличаются хотя бы одним элементом (иначе говоря, -элементные подмножества данного множества из элементов).

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

Числа

Все сочетания из множества по два — .

.

15 билет

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

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

Таблица истинности для отрицания.

Х
0	1
1	0

Конъюнкцией двух высказываний Х и У называется высказывание , которое истинно только в том случае, когда Х и У оба истинны.

Таблица истинности для конъюнкций.

Х	Y
0	0	0
0	1	0
1	0	0
1	1	1

Дизъюнкцией двух высказываний Х и У называется высказывание которое истинно, когда хотя бы одно из них истинно.

Таблица истинности дизъюнкций.

Х	Y
0	0	0
0	1	1
1	0	1
1	1	1

Импликацией двух высказываний Х и У. называется высказывание , которое ложно тогда и только тогда, когда Х истинно, а У ложно.

Таблица истинности для импликации.

Х	Y
0	0	1
0	1	1
1	0	0
1	1	1

Эквивалентностью высказываний Х и У называется высказывание , которое истинно тогда и только тогда, когда Х и У оба истинны или ложны.

Таблица истинности для эквивалентности.

Х	Y
0	0	1
0	1	0
1	0	0
1	1	1

Название	Прочтение	Обозначение
Отрицание	не	-
Конъюнкция	и
Дизъюнкция	или
Импликация	если... то
Эквивалентность	тогда и только тогда, когда

Высказывание — это повествовательное предложение, о котором можно сказать, истинно оно или ложно.
«Земля — планета Солнечной системы» — истинно.
«2+8<5» — ложно.
«5*5=25» — истинно.
«Каждый квадрат есть параллелограмм» — истинно.
«Каждый параллелограмм есть квадрат» — ложно.
«2*2=5» — ложно.
А вот примеры, не являющиеся высказываниями:

«Уходя, гасите свет»
«Да здравствует мыло душистое и полотенце пушистое!»

«Который час?»
Высказывание, представляющее собой одно утверждение принято называть простым или элементарным.

Сложное высказывание получается путем объединения простых высказываний связанные — союзами И, ИЛИ, и частицей НЕ.

16 билет

Испытания и события.
Выше событие названо случайным, если при осуществлении определенной совокупности условий S оно может либо произойти, либо не произойти. В дальнейшем, вместо того чтобы говорить «совокупность условий S осуществлена», будем говорить кратко: «произведено испытание». Таким образом, событие будет рассматриваться как результат испытания.

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

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

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

17 билет

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

Представим, что у нас проводится эксперимент с пространством из n элементарных исходов, которые равновероятны. Элементарные исходы являются несовместными событиями (напомним, что несовместные события - это те, которые не могут произойти одновременно), поэтому вероятность каждого из них равна 1/n. Допустим, нас интересует событие А, которое наступает только при реализации благоприятных элементарных исходов, количество последних m (m< n). Тогда, согласно классическому определению, вероятность такого события:

Р(А)=m/n.

Для любого события А справедливо неравенство: 0 < P(A) <1. n>

Пример 1. Лотерея состоит из 1000 билетов, среди них 200 выигрышных. Наугад вынимается один билет из 1000. Чему равна вероятность того, что этот билет выигрышный?

Решение: различных исходов в этом примере 1000 (n=1000). В интересующее нас событие А входят 200 исходов (m=200). Таким образом,

Совместные (совместимые) события – это события, для которых наступление одного из них не исключает возможности наступления других в данном испытании, т.е. они могут появиться вместе.

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

Например, получение студентом на экзамене по одной дисциплине оценок “отлично”, “хорошо”, “удовлетворительно” – события несовместные, а получение этих же оценок на экзамене по трем дисциплинам – события совместные

18 билет