Лекция: Задачи повышенной сложности

1.1.При голосовании в городскую думу в бюллетене в списке из трех кандидатов требовалось оставить не более одного. При подведении итогов оказалось, что кандидатов и вычеркнули 60% избирателей, кандидатов и — 80% избирателей, а кандидатов и — 70% избирателей. Какой процент избирателей проголосовал против всех кандидатов и какой кандидат набрал наибольшее число голосов?

1.2. Сколько бинарных отношений можно определить на множестве из элементов?

1.3. На множестве задано бинарное отношение. Какими свойствами обладает это бинарное отношение? Является ли оно отношением эквивалентности? порядка? В том случае, если — отношение эквивалентности, указать разбиение множества на классы эквивалентности .

1.4. Рассмотрим на множестве действительныхчисел бинарные отношения, определенные условиями:,,,. Выяснить, какими свойствами обладают перечисленные бинарные отношения.

1.5. Привести пример рефлексивного, транзитивного, но не симметричного бинарного отношения на множестве из четырех элементов.

1.6. Привести пример рефлексивного, симметричного, но не транзитивного бинарного отношения на множестве из четырех элементов.

1.7. Привести пример транзитивного, симметричного, но не рефлексивного бинарного отношения на множестве из четырех элементов.

1.8. Пусть — конечное множество. Сопоставим каждому бинарному отношению на матрицу размера, называемую матрицей отношения, в которой на пересечении -й строки и -го столбца стоит 1, если, и 0 — в противном случае. Определить, что представляет собой матрица отношений в случае, если :

а) рефлексивно;

б) симметрично;

в) антисимметрично.

1.9. Пусть — конечное множество. Определим на булеане бинарное отношение: (здесь, ). Является ли отношение отношением эквивалентности? отношением частичного (линейного) порядка?

1.10. Доказать, что если бинарное отношение одновременно симметрично и антисимметрично, то оно транзитивно.

Ответы и указания к упражнениям

1.133. 1.2. Разбиения:,,. Разбиения: 1.; 2.; 3.; 4.; 5.; 6.; 7.; 8.; 9.; 10.; 11.; 12.; 13.; 14.; 15.. 1.3. — рефлексивно, симметрично, транзитивно, отношение эквивалентности;,; — симметрично.