Соотношения между множествами

Если все элементы множества А являются элементами множества В (из x A следует x B), говорят, что А является подмножеством множества В и пишут А В.

Если при этом А не совпадает с В , то А называется собственным подмножеством множества В; в этом случае пишут А В.

Для любого множества А выполнимо соотношение А А.

Множества А и В равны тогда и только тогда, когда А В и В А.

Для любых трех множеств А, В, С из А В и В С следует А С.

Для любого множества А имеет место соотношение А, то есть пустое множество является подмножеством всех множеств.

Мы можем выделить из множества А все элементы, обладающие некоторым общим свойством, и образовать из них новое множество В.

Например, множество четных чисел можно определить так: {x : x Z и x/2 –целое число}. Иногда вместо двоеточия используется вертикальная черта.

X z называют характеристическим предикатом.

Лекция 14

Теоретико – множественные операции для любых множеств А и В.

• Пересечение (intersection) множеств А и В определяется как множество

элементов, принадлежащих одновременно и А , и В.

A B = { x : x A и x B }; связка И -конъюнкция

А={М, А, Н. Я}

В={ В, А, Н. Я}

A B = {А, Н, Я}

• Объединение (union) множеств А и В определяется как множество, состоящее из элементов, принадлежащих хотя бы одному из них.

A B = { x : x A или x B }; связка ИЛИ - дизъюнкция

А={М, А, Н. Я}

В={ В, А, Н. Я}

A B = {М, А, Н, Я, В}

• Разность (difference) множеств А и В определяется как множество элементов, принадлежащих одному их них и не принадлежащих другому.

A \ B

B \ A

A \ B = { x : x A и x B };

A \ B = {М}

В \ A ={x : x B и x A }

В \ А ={В}

• Декартово произведение двух множеств А и В определяется как множество всех упорядоченных пар, у которых первый элемент принадлежит А, а второй - В. Обозначается А В.

А В = {(a,b): a A и b B}

Пример 1

{a,b} {a,b,c}= { (a,a), (a,b), (a,c), (b,a), (b,b), (b,c)}

Пример2

Пусть А ={1,6} B={2,4,7}

А В = {(1 , 2),(6 , 2),(1 , 4),(6 , 4),(1 , 7)(6 , 7) и имеет 6 элементов (2 3=6)

Число элементов в множестве S называется его мощностью (cardinality) и обозначается | S | . Кардинальное число для конечных множеств – натуральное.

Для конечных множеств А и В мощность их произведения равна произведению мощностей:

|A B| =|A| * |B| .

Декартово произведение n множеств А_1, А₂, …., А_n определяется как множество n-ок (энок):

A₁ A₂ ….. A_n = {(a_1, a₂, ….. ,a_n) : a_i A_i при всех i=1,2,….,n}

Операция декартова умножения ассоциативна, но не коммутативна ( то есть выполняется сочетательный закон, но не переместительный)

Число элементов в декартовом произведении равно произведению мощностей сомножителей:

| A₁ A₂ …. A_n | = | A₁ | *| A₂ |*….| A_n |.

Декартова степень

Aⁿ = A A …. A -произведение одинаковых множителей

Для конечного А мощность Аⁿ =| A | ⁿ .

Свойства теоретико-множественных операций

• Свойства пустого множества ( empty)

A = , A =A;

• Идемпотентность – (idempotency)

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

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

A A = A, A A = A;

• Коммутативность - (commutative) (переместительный закон)

A B =B A, A B = B A;

• Ассоциативность - (associative) (сочетательный закон)

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

A (B C) = (A B) C, A (B C) = (A B ) C;

• Дистрибутивность – (distributive) –(распределительный)

A (B C) = (A B) (A C),

A (B C) = (A B) (A C);

• Законы поглощения – (absorption)

A (A B) = A, A (A B ) = A;

• Законы де Моргана – (DeMorgan’s laws)

A \ (B C )=(A \ B) (A \ C),

A \ (B C )=(A \ B) (A \ C).

Можно множество рассматривать как подмножество некоторого фиксированного множества, называемого универсумом. Если, например, речь идет о множестве целых чисел, то в качестве универсума можно взять множество Z целых чисел. Если универсум U фиксирован, можно определить

_ _

дополнение множества А как А=U \ A. Для любого А U верны такие утверждения:

= _ _

A= A, A A= , A A = U.

Из законов де Моргана следует, что для любых множеств А , В U имеет место равенство:

______ _ _ ______ _ _

A B = A B, A B = A B.

Два множества А и В называются непересекающимися, если они не имеют общих элементов, то есть если

А В= .

Говорят, что семейство S={ S_i } непустых множеств образует разбиение множества S на классы, если:

• Множества S_i попарно не пересекаются, то есть

S_i S_j = при i j,

• Их объединение есть S, то есть

S= S_i .

s_i s

Это значит, что семейство S образует разбиение множества S , если любой элемент множества s S принадлежит ровно одному из множеств S_i семейства.

Два множества имеют одну и ту же мощность, если между их элементами можно установить взаимно однозначное соответствие.

Мощность пустого множества равна нулю | |=0.

Мощность конечного множества - натуральное число.

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

Множество целых чисел Z–счетно.

Множество вещественных чисел R – несчетно.

Элементы КОМБИНАТОРИКИ в приложении к множествам

Комбинаторика – это математика счета. В вычислительной технике и программировании часто встречаются несколько типов счетных задач. Обычно их решение связано с логикой и проницательностью.

Существуют три основных правила счета, из которых получаются все остальные.

(правила сложения, умножения и перестановки) Важно понять, какое конкретное правило надо применять в вашей задаче.

• Правило умножения

Если существует |A| вариантов из множества А и |B| вариантов из множества В, то тогда существует |А| |В| комбинаций одного варианта из множества А и одного варианта из множества В.

Пример1

Например, пусть у меня есть 5 шляпок и 4 шарфика. Тогда у меня есть 5*4=20 различных вариантов комбинаций головного убора с шарфиками .

Пример2

Пусть есть 10 блинчиков и 5 видов начинки к ним. 10*5 =50 вариантов блинчиков с начинкой можно получить.

• Правило сложения

Если существует |А| вариантов из множества А и |В| вариантов из множества В, то тогда существует |А|+|В| вариантов, что случится А или В при условии, что элементы А и В различны.

Пример1

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

Пример2

Если символ на номере машины должен быть либо русской буквой, либо цифрой, то всего есть 33+10=43 возможности , так как букв 33, а цифр 10.

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

Набор n упорядоченных объектов, в котором каждый объект встречается ровно один раз, называется перестановкой. Всего существует

n != различных перестановок.

Например, 3!=6 перестановок трех объектов: 123, 132, 213, 231, 312, 321.

Для n=10 имеем n! =3 628 800, то есть начинаем приближаться к пределу возможностей полного перебора. Поэтому хорошо бы знать, с какой скоростью растет число объектов, чтобы определиться, когда полный перебор перестанет подходить нам в качестве алгоритма.

================================================

• Формула включений – исключений.

Правила сложения являются специальным случаем более общей формулы, когда два множества могут пересекаться:

|A B|= |A| + |B| – |A B|.

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

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

Есть еще методика под названием биекция. Это взаимно - однозначное соответствие между элементами одного множества и другого. Если такое соответствие есть, то при подсчете размера одного множества вы автоматически получаете размер другого. Для использования биекций нужен набор множеств, которые мы умеем считать, тогда можно привязать к ним другие объекты. Наиболее часто мы применяем следующие комбинаторные объекты:

• Подмножества. Произвольная выборка элементов из n возможных объектов, называется подмножеством. Для n объектов существует 2ⁿ различных подмножеств. Таким образом, 2³ =8 подмножеств трех объектов: 1, 2, 3, 12, 13, 23, 123 и пустое множество. Для n= 20 имеем 2ⁿ =1048576, так что начинаем приближаться к пределу возможностей полного перебора.

• Размещения без повторений

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

Пусть фиксировано множество S из n элементов и некоторое k, не превосходящее n. Размещением без повторений из n по k называют последовательность длины k, составленную из различных элементов S. Число таких размещений равно

n*(n-1)*(n-2)*…….*(n-k+1) = n! / (n-k)!

Так как существует n способов выбора первого элемента, n-1 способов выбора второго элемента , и так далее до k-ого элемента, который можно выбрать n-k+1 способами.

Например, существует 12=4*3 последовательностей из k=2 различных n=4 элементов множества {a,b,c,d}:

a b , a c , a d , b a , b c , b d , c a , c b , c d , d a , d b , dc.

Частным случаем этой формулы является формула для числа перестановок( так как перестановки являются частным случаем размещений при n=k.

• Размещения с повторениями.(Strings). Это последовательность символов, набираемая с возможностью повторения.

Существует mⁿ различных последовательностей из n объектов m различных видов.

27 размещений длиной 3 для набора 123: 111, 112, 113, 121, 122, 123, 131, 132, 133, 211, 212, 213, 221, 222, 223, 231, 232, 233, 311, 312, 313, 321, 322, 323, 331,332, 333. Число двоичных размещений длины n равняется числу подмножеств n объектов, и число возможных вариантов растет еще быстрее с увеличением m.

• Сочетания из n элементов по k называются k-элементные подмножества какого-либо n-элементного множества. Например, у множества {a,b,c,d} из 4 элементов имеется 6 двухэлементных подмножеств

{a,b} , {a,c} , {a,d} , {b,c} , {b,d} , {c,d}.

Число сочетаний из n по k в k! раз меньше числа размещений без повторений ( для тех же n и k),так как из каждого сочетания из n элементов по k можно сделать k! размещений без повторений, переставляя его элементы. Поэтому число сочетаний из n элементов по k равно

n!/ k!(n-k)!

Для k=0 эта формула дает 1, как и должно быть, т.к. есть ровно одно пустое подмножество. Напомним, что 0!=1.

Рекуррентные соотношения

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

Рекуррентное равенство, определенное через себя самого.

Примеры:

a_n=a_n-1 + 1, a₁=1 -> a_n=n.

a_n=2 a_n-1, a₁=2 -> a_n=2ⁿ.

a_n=n a_n-1, a₁=1 -> a_n=n!

Замечание: Компьютерные программы легко вычисляют значение заданного рекуррентного соотношения, даже если аналитической формы не существует.

• Биномиальные коэффициенты

Для числа сочетаний из n по k используется обозначение C_n^k или :

C_n^k =n! / k!(n-k)!

Эта формула симметрична относительно замены k на n-k:

C_n^k =C_n^n-k .

Числа C_n^k называют биномиальными коэффициентами, появляющимися в биноме Ньютона:

(x+y)ⁿ =

( если раскрыть скобки в (x+y)ⁿ , то количество членов, содержащих k множителей x и n-k множителей y равно количеству способов выбрать k мест из n , то есть C_n^k ).

При x=y=1 ,бином Ньютона дает

2ⁿ =

(Комбинаторный смысл: 2ⁿ двоичных строк длины n сгруппированы по числу единиц: имеется как раз C^k_n строк с k единицами.)

Рекурсия и индукция были рассмотрены в лекции№9.

Самостоятельно:

1. Даны два отрезка А=[1,3] и В=[2,4].

Найти: их объединение, пересечение, разность .

2. Дано: A={-6,-3,0,3,6}, B={0,2,4,6,8} .

Найти : объединение множеств

3.Зная, что С_n^k =C_n-1^k +C_n-1^k-1 составьте таблицу для C_n^k при n=0,1,2,…6 и при k от 0 до n в виде равнобедренного треугольника ( C⁰₀ сверху, C₁⁰ и C₁¹ в следующей строке и так далее) Этот треугольник называют треугольником Паскаля.

Лекция 15

Алфавиты, слова, языки.

Для обработки информации мы представляем данные (объекты обработки) как последовательности символов. Мы фиксируем для представления данных специальный набор символов – алфавит.

Определение: Алфавитом называется любое непустое конечное множество. Каждый элемент алфавита называется символом.

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

Примеры:

_bool ={0,1} –булевский алфавит

_лат ={a,b,c,d,…..,z} –латинский алфавит

_keyboard = _лат {A,B,C,… , >,<,(,), …..,!} – алфавит всех символов на клавиатуре

_ип1п = _лат {A,B,C,…Z} { , ,&, } { } N₀ –алфавит для языка исчисления предикатов 1 порядка

Здесь N={1,2,3,…….} –множество натуральных чисел

N₀=N {0}

_m ={0,1,2,….,m-1} для каждого m >=1 – алфавит для записи чисел в m-ичной системе счисления.

Определим слово как некоторую последовательность символов. Слово у нас будет означать произвольный текст.

Определение Пусть - некоторый алфавит. Слово над - любая конечная последовательность символов алфавита .

Пустое слово - единственное слово, состоящее из нулевого количества символов.

Длина слова w над , обозначаемая как | w | , есть число символов в этом слове.

^* - множество всех слов над алфавитом .

⁺= ^*- { } - означает множество всех слов за исключением пустого.

Символ пробела над алфавитом клавиатуры отличен от , так как пробел –элемент алфавита _keyboard , то | пробел|=1.

Примеры

1. ( _bool)^*={ ,0,1,00,01,10,11,000,001,010,100,011,…..}

= { } {x₁ x₂ ……x_i | i N₀, x_{j bool} для j=1,…,i}

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

2.Дан двухбуквенный алфавит ²={a,b}

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

Например, множество всех слов длины 2 :

+ ²={aa, bb, ab, ba};

Упражнения:

1.Напишите множество всех слов длины 3;

+ ³ = ?

2 Пусть дан язык ₁={aⁿb^m} ; n=1,2….., m=1,2….

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

?

А слово bab?

?

3 Пусть дан язык ₂={aⁿbⁿ}; n=1,2…..

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

? abab?

? bbaa?

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

Слово x = x₁ x₂ …..x_n ( _bool)^* , x_{i bool} для i=1,….,n

можно рассматривать как двоичное представление неотрицательного числа

Number(x) = (2⁰*1+2¹*0+2²*1+….)

Наоборот, для любого неотрицательного целого числа m запись

Bin(m) ( _bool)^*

обозначает наиболее короткое двоичное представление числа m.( Наиболее короткое означает, что первый символ должен быть равен единице). Поэтому

Number(Bin(m))=m.

Как определить зеркальный язык?

₄= {aa^-1} , где a ⁺

Слова abba ₄,

baaaab ₄ ,

а слова aba и aaa не принадлежат ₄.

Вывод:

Мы видим, что любой язык суть некоторое n-арное отношение на множестве всех слов ⁺, где n=1,2……(арность – это размерность)

Давайте представим булевскую формулу с помощью операторов отрицания, конъюнкции и дизъюнкции ( ). Для этого будем использовать алфавит

_лог = {0,1,x,(,), }

где x –булевы переменные, используемые как символы алфавита (x_1, x₂,…..) и кодировка булевской переменной x_i как слова

xBin(i) для всех i N.

Все остальные символы в формуле переписываются в ее представлении один к одному. Тогда формула

(x₁ x₇) (x₁₂) (x₄ x₈ (x₂))

имеет следующее представление:

(x1 x111) (x1100) (x100 x1000 (x10)).

Полезная операция над словами – простая конкатенация двух слов.

Определение Пусть - некоторый алфавит. Конкатенация относительно - это отображение K : ^{* * *}, заданное в виде

K(x,y)=x*y=xy

для всех x, y ^*

Пример

Пусть x=0aa1bb и y=111b для ={0,1,a,b}.

Тогда K(x,y) = x*y=0aa1bb111b.

Замечания

1. Конкатенация K для -ассоциативная операция над ^* , так как

K(u, K(v,w)) = u*(v*w) = uvw = (u*v)*w =( K (K(u, v), w)

для всех u,v,w ^*

2.Кроме того, для каждого x ^* выполнено следующее:

x * = * x =x

3. Конкатенация коммутативна только для алфавитов, состоящих из одной буквы.

4. Для всех x,y ^* ,

| xy | =|x*y| = |x|+|y| Часто пишут xy вместо K(x,y) и x*y.

Определение

Пусть - некоторый алфавит. Для каждого x ^* и каждого натурального i определим i-ю итерацию xⁱ слова x как

xⁱ = xx^i-1 ,

где x⁰ = .

Пример

K(aabba, aaaaa) =aabbaaaaaa = a² b² a⁶=a² b² (aa)³ Введенное обозначение позволяет нам находить более короткое представление некоторых слов.

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

Связанные части слова

ab…..

bb………..c

ac……..b

подслово

ab…….b

b…….a

префикс

a……b

bb…ab

Суффикс

Определение Пусть v,w ^* для некоторого алфавита . Тогда:

• v- подслово слова w x,y ^* : w=xvy;

• v- суффикс слова w x ^*: w=xv;

• v- префикс слова w y ^*:w=vy.

Определение Пусть x ^* и пусть a для некоторого алфавита .

Определим |x|_a как число вхождений символа а в x.

(посмотреть множества – мощность и множество всех подмножеств)

Пример

|(abbab)|_a =2 и |(11bb0)|₀ =1

Для каждого x ^* |x|= _a

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

Определение: Язык над алфавитом -это некоторое подмножество ^* . Дополнение L^C языка L относительно -это язык ^* _{_}- L.

L₀=0 – пустой язык

L ={ } –язык, содержащий единственное слово - пустое слово.

Если L₁ и L₂ - языки над алфавитом , то L₁*L₂=L₁L₂={ vw | v L₁, w L₂}

Это конкатенация языков L₁ и L₂.

Пусть L – некоторый язык над алфавитом . ( то есть язык есть некоторое множество слов над заданным алфавитом). Определим

L⁰:=L ,

Lⁱ⁺¹=Lⁱ*L для всех i N_0,

L^*= - звезда Клини языка L

L⁺= ₌ L*L^*

Примеры языков над алфавитом ={a,b}:

L1=0;

L2={ };

L3= { ,ab,abab};

L4= ^* = { ,a,b,aa,bb,…..};

L5= ⁺ ={a,b,aa,bb,….};

L6={a}^* ={ ,a,aa,aaa,……}={aⁱ : i N₀}

L7= ³ ={aaa, aab, aba, abb, baa ,bab, bba, bbb}

Все грамматически правильные тексты (английские) и множество всех синтаксически правильных программ на ЯВУ – всегда некоторый язык над алфавитом _keyborard .

Замечание

Законы дистрибутивности относительно объединения и конкатенации выполняются:

Лемма: Пусть L_1,L₂ и L₃ - языки над алфавитом . Тогда

L₁ L₂ L₁ L₃=L₁ (L2 L₃)

Но закон дистрибутивности для конкатенации и пересечения не выполняется.

Лемма: пусть L₁,L₂ и L₃ -языки над алфавитом . Тогда

L₁(L₂ L₃) L₁L₂ L₁L₃

Вы видите, что вместо дистрибутивного закона выполняется только соответствующее включение. Достаточно указать три конкретных языка U₁, U₂,U₃, таких, что

U₁(U₂ U₃) U₁U₂ U₁U₃ . ( обдумать док-во)

Алгоритмические проблемы.

(Проблема принадлежности, проблема существования Гамильтонова цикла( HC), проблема выполнимости, оптимизационная проблема)

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

А : ^* ₁ -> ^*₂ для некоторых алфавитов ₁ и ₂ .

Это значит, что:

- входы представлены как слова над алфавитом ₁;

- выходы представлены как слова над алфавитом ₂;

- А однозначно определяет выход по каждому входу.

Для некоторого алгоритма А и входа x обозначим записью A(x) выход алгоритма А для этого входа. Два алгоритма (программы) A и B эквивалентны, если они работают над одним и тем же алфавитом , и при этом A(x) =B(x) для всех x ^*.

Проблема принадлежности

Определение: для заданных алфавита и языка L ^* проблема принадлежности ( , L) заключается в том, что для любого x ^* необходимо ответить на вопрос, какое именно условие из следующих двух выполнено :

x L или x L.

Алгоритм А решает проблему принадлежности (L, ), если для всех x ^* выполнено следующее:

A(x)= 1, если x L

0, если x L.

тогда говорят, что А распознает язык L.

Если есть алгоритм для некоторого языка L, который распознает L,то говорят, что язык L является рекурсивным.

Проблема принадлежности ( , L)описывается так:

( , L)

Вход : x ^*.

Выход : A(x) _bool={0,1}, где

A(x)= 1,если x L (да)

0, если x L (нет)

Пример

({a,b}, {aⁿbⁿ} | n N₀

Вход: x {a,b}^*

Выход : Да, если x=aⁿ bⁿ для некоторого n N₀

Нет – в противном случае.

Сложность по Колмогорову

Как измерить количество информации в словах?

Что такое колмогоровская сложность?

Все мы архивировали свои файлы (arj, rar, zip, bи т.д.). Это происходит с помощью программ, которые сжимают эти файлы. Применив такую программу к некоторому файлу, содержащему текст или программу , мы на выходе получаем его сжатую версию. Она ,как правило, короче исходного файла. По ней можно восстановить исходный файл.

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

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

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

Пример