Отношение эквивалентности. Примеры. Класса эквивалентности.

Отношение R на мн-ве Х наз отношением эквивалент

ности, если оно одновременно обладает cв-вами рефлексивности, симметричности и транзитивности.

Если на .мн-ве Х задано отношение эквuва лентности, то оно порождает разбиение этого мн-ва на попарно непересекающиеся подмн-ва (классы эквива­лентности).

Бинарным отношением на мн-ве Х наз всякое подмн-во декартова произведения ХХ.

1º R рефлексивно на Х  хRх для любого хХ. 

2º симметрично хRу  уRу (туда-сюда)

3º транзитивности хRу, уRz } хRz ху, уz  хz

Классы: 1. элементы одного класса эквивалентности взаимозаменяемы. Так в дробь 3/6 можно заменить на ½.

2. класс эквивалентности опр-ся любым своим представителем

3. разбиение мн-ва на классы исп-ся для введения новых понятий.

Отношение R на мн-вe Х наз отношением порядка, если оно одновременно обладает св-вом антисuмметричности и транзитивности. Примеры: отношения «меньше» на мн-ве N, «короче» на мн-ве отрезков.

Теорема. 1. Каждое отношение эквивалентности порождает разбиение мн-ва на классы, подчиненное данному отношению.

Теорема. 2. Если есть разбиение на мн-ва М на классы, то существует отношение эквивалентности на этом мн-ве М, которому подчинено данное разбиение.

Отношения порядка. Примеры.

Определение. Бинарное отношение f на M называется отношением порядка, если f транзитивно и антисимметрично (т.е. для различных a и b из afb всегда следует bfa). Можно сказать что из afb и bfa всегда следует, что a=b.

Примеры. 1) N₀={0, 1, 2, 3, …}. Отношения >, <, ≤, ≥ транзитивны и антисимметричны (a>b следовательно b>a). 2) A – все студенты. Пусть afb, если a – не старше b (выше, тяжелее, веселее и т.д.). Если под «не старше» понимать что человек a родился в тот же день, что и b, или позже, то антисимметричности нет, т.к. есть «нарушители» - «однодневки». Если учитывать еще и время рождения, то это отношение антисимметрично. 3) T – множество треугольников. afb, если S_a>S_b. f – транзитивно и антисимметрично. 4) . Попробуем ввести в этом множестве отношение порядка. , если a<b – порядок. , если a и b взаимно простые числа. g – не транзитивно. Контрпример: , , но .

Частные виды порядков: Определения. Порядок f называется строгим, если он антирефлексивен, т.е. всегда afa. Порядок f называется нестрогим, если он рефлексивен.

Примеры. В рассмотренных выше примерах строгими будут из 1) отношения <, >; отношения порядка из 3) и из 4). К нестрогим порядкам относятся из 1) примера отношения ≤, ≥; из 2) примера отношения порядка.

Определение. Порядок f называется линейным, если для любых различных a и b справедливо afb или bfa.

Примеры. Порядок из примера 1) будет строгим (<, >) или нестрогим (≤, ≥) линейным порядком; порядок из 2) примера.

Б ао как отображение МxМ м. Свойства и примеры бао.

Определение. Если на некотором множестве M задан закон, по которому любым двум элементам a и b из M (может быть a=b) сопоставляется вполне определенный элемент a*b из этого же множества то говорят, что на M задана бинарная алгебраическая операция *.

Примеры. 1) сложение и вычитание на множестве всех векторов, 2) конъюнкция, дизъюнкция, импликация, разделительная дизъюнкция, штрих Шеффера и стрелка Пирса на множестве всех высказываний, 3) сложение, умножение, вычитание и деление на множестве целых чисел, 4) объединение, пересечение, разность множеств, декартово произведение множеств.

Свойства:

1) Коммутативность. БАО коммутативно, если для любых а и b из M выполняется равенство а*b=b*а. Примеры. 2∙5=5∙2.

2) Ассоциативность. БАО ассоциативно, если для любых а, b и c из M выполняется равенство (а*b)*c=а*(b*c). Примеры. (4+7)+9=4+(7+9).

3) Идемпотентность. БАО идемпотентно, если для любого а из M выполняется равенство а*а=а. Примеры. 1∙(:)1=1, 0+0=0.

4) Нейтральный и поглощающий элементы (левый, правый, просто). Нейтральный элемент e из множества M относительно БАО, если для любого элемента a из M выполняется равенство e*a=a или a*e=a. Примеры. 2+0=0+2=2 (для сложения в Z – 0), 2∙1=1∙2=2 (для умножения в Z – 1), 2-0=2 (правый нейтральный элемент для вычитания).

Поглощающий элемент e из множества M относительно БАО, если для любого элемента a из M выполняется равенство e*a=е или a*e=е. 2∙0=0∙2=0 (для сложения в Z – 0), 0:2=0 (левый поглощающий элемент для вычитания).

5) Дистрибутивность (левый, правый, просто). БАО ◦ дистрибутивно относительно БАО *, если для любых элементов а, b и c из M выполняются равенства (a*b)◦c=(a◦c)*(b◦c), c◦(a*b)=(c◦a)*(c◦b). Примеры. (1+3)∙6=(1∙6)+(3∙6), 6∙(1+3)=(6∙1)+(6∙3).

6) Закон поглощения. Если для любых а и b из M выполняется равенство (a*b)◦a=a◦(a*b)=a, то это закон поглащения. Примеры. (АvВ)ʌA=Aʌ(АvВ)=A (на множестве высказываний).

Понятие УАО на множестве M. Примеры. Свойства УАО: инволютивность + закон А. де Моргана (1806-1871) в логике и теории множеств + законы исключенного третьего (Tertium non datur) и противоречия (там же).

УАО как (~5 вопросов по лекциям).

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

Примеры. 1) отрицание высказываний, 2) дополнение множества до универсального, 3) центральная и осевая симметрия.

Свойства:

1) Инволютивность. УАО инволютивно, если для любого а из M выполняется равенство а*=а. Примеры. 1) U=N (U – универсальное множество). Для множества N₂ его дополнением до универсального будет множество , в свою очередь его дополнением до универсального будет , а по свойству N₂= . 2) 7>5, , =7>5.

2) Закон де Моргана. Если для любых а и b из M выполняется равенство (a◦b)*=a*▫b*=a, то это закон де Моргана. Примеры. 1) , 2) .

3) Закон исключенного третьего. Если для любых а из M выполняется равенство a◦а*=е, то это закон исключенного третьего. Примеры. 1) Аv =И, 2) А =U.

4) Закон противоречия. Если для любых а из M выполняется равенство a◦а*=е, то это закон противоречия. Примеры. 1) Аʌ =Л, 2) А =Ø.

Примеры комбинаторных задач

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

Примеры: 1) Сколько квадратов на рисунке? (всего 5)

2) Сколько здесь прямоугольников? (1×1-4, 2×1-2, 1×2-2, 2×2-1 всего 9)

3) Сколько треугольников на рисунке?