Задачи по теории множеств

Задача 1. Докажите тождество A U B=A U (BA).

Решение: Чтобы доказать это тождество, нужно показать, что каждый элемент первого множества принадлежит второму и наоборот, то есть эти множества совпадают.

Пусть x? AU B, то есть x? A или x? B. Если x? A, то x? A U (BA). Если x? A, но x? B, то x? BA, следовательно, x? A U (BA).

Пусть x? A U (BA), то есть x? A или x? BА. Если x? A, то x? A U B. Если x? В, но x? A (x? BА), то x? A U B.

Таким образом, тождество доказано.

Задача 2 (Льюиса Керрола). В одной из повестей Льюиса Керрола — автора «Алисы в стране чудес», «Алисы в зазеркалье» и др. — есть такая задача: «В ожесточенном бою 70 из 100 пиратов потеряли один глаз, 75 — одно ухо, 80 — одну руку и 85 одну ногу. Каково минимальное количество потерявших одновременно глаз, ухо, руку и ногу?».

Решение: Обозначим через, А — множество пиратов, потерявших один глаз, через В — одно ухо, через С — одну руку, через D — одну ногу. Тогда множество потерявших и глаз, и ухо, и руку, и ногу одновременно — АВСD. Универсальное множество I можно представить в виде:

I = () (АВСD). По закону Моргана Законы де Моргана (правила де Моргана) — логические правила, связывающие пары логических операций при помощи логического отрицания. Открыты шотландским математиком Огастесом де Морганом. Они гласят, что: =. (На рис. 1. множество АВСD выделено на диаграмме темно-серым цветом, множество — светло-серым).

Рис. 5.

Так как множества и АВСD не пересекаются, то N (I)= N ()+N (АВСD). Множества, , и могут попарно пересекаться. Значит N ()N ()+N ()+N ()+N (). N ()=N (I) — N (A) = 100 — 70 = 30, N ()=N (I) — N (В) = 100 — 75 = 25, N ()=N (I) — N© = 100 — 80 = 20, N ()=N (I) — N (D) = 100 — 85 = 15. Таким образом, N (I) N ()+N ()+N ()+N ()+N (АВСD), а N (АВСD)N (I)-N ()-N ()-N ()-N ()=100 — 30 — 25 — 20 — 15=10.

Итак, N (АВСD)10, т. е. не менее 10 пиратов одновременно лишились и глаза, и уха, и руки, и ноги.

Задача 3. Начертите фигуры, изображающие множества:

А={(x, y)? R² | x²+y²<=1},.

В={(x, y)? R² | x²+(y-1)²<=1}, где R² — вещественная плоскость. Какие фигуры изображают множества АUВ, А? В, R²А?

Решение:

Задача 4. Определите свойства следующих отношений:

• 1. «прямая x пересекает прямую y» (на множестве прямых);
• 2. «число x больше числа y на 2» (на множестве натуральных чисел);
• 3. «число x делится на число y без остатка» (на множестве натуральных чисел);
• 4. «x — сестра y» (на множестве людей).

Решение:

1. xRy = «прямая x пересекает прямую y» (на множестве прямых).

Это отношение:

Рефлексивное, так как «прямая x пересекает прямую x» выполняется для любой прямой (она пересекает себя в каждой точке);

Симметрическое, так как из того, что «прямая x пересекает прямую y» следует, что «прямая y пересекает прямую x» для любых прямых x, y.

Также можно заметить, что это отношение не является тождественным, транзитивным и полным.

2. xRy = «число x больше числа y на 2» (на множестве натуральных чисел).

Это отношение:

Антирефлексивное, так как ни для одного элемента из множества натуральных чисел не выполняется «число x больше числа x на 2»;

Антисимметрическое, так как для любых элементов x, y из множества натуральных чисел из того, что «число x больше числа y на 2» следует невыполнение того, что «число y больше числа x на 2».

Также можно заметить, что это отношение не является тождественным, транзитивным и полным.

3. xRy = «число x делится на число y без остатка» (на множестве натуральных чисел).

Это отношение:

Рефлексивно, так как для любого элемента x из множества натуральных чисел выполняется «число x делится на число x без остатка»;

Тождественно, так как для любых элементов x, y из множества натуральных чисел из того, что «число x делится на число y без остатка» и «число y делится на число x без остатка», следует, что x = y;

Транзитивное, так как для любых элементов x, y, z из множества натуральных чисел из того, что «число x делится на число y без остатка» и «число y делится на число z без остатка», следует, что «число x делится на число z без остатка».

Также можно заметить, что это отношение не является симметрическим, антисимметрическим и полным.

4. xRy = «x — сестра y» (на множестве людей) Это отношение:

Антирефлексивно, так как для любого человека x неверно, что «x — сестра x»;

Транзитивно, так как для любых людей x, y, z таких что «x — сестра y» и «y — сестра z» следует, что «x — сестра z».

Также можно заметить, что это отношение не является симметрическим, антисимметрическим, тождественным и полным.

Задача 5. Проверить, является ли отношением эквивалентности на множестве всех прямых на плоскости отношение «непересекающихся прямых».

Решение: Введем множество X — множество всех прямых на плоскости и отношение R = {x, y? X: x не пересекает y} = {x, y? X: x параллельна y}. Это отношение будет отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно (см. предыдущую задачу). Проверим наличие этих свойств.

• 1) R рефлексивно, так как для любой прямой x? X справедливо xRx (считаем, что прямая параллельна самой себе).
• 2) R симметрично, так как для любых прямых x, y? X выполняется xRy? yRx (так как если x параллельна y, то и y параллельна x).
• 3) R транзитивно, так как для любых прямых x, y, z? X выполняется xRy, yRz? xRz (так как две прямые (x и z), параллельные третьей (y), параллельны).

Таким образом, R — отношение эквивалентности.