Элементы теории множеств.

Элементы математической логики. Исчисление высказываний. Исчисление предикатов.

Соответствия и отображения.

Бинарные отношения.

Примеры решения индивидуалных заданий первого уровня

Задача 1. A, B  некоторые множества, ય  универсальное множество. Найдите AB, AB, A\B, B\A, A, B, AB.

1) A = {2, 1, 8}, B = {9, 7, 2, 5, 1}, ય = {1, 2, 3, 4, 5, 6, 7, 8, 9};

2) A = (10; 1], B = (5; 20), ય = R.

Решение:

1) A = {2, 1, 8}, B = {9, 7, 2, 5, 1}, ય = {1, 2, 3, 4, 5, 6, 7, 8, 9}

AB = {x | xA и xB} = {1, 2};

AB = {x | xA или xB} = {1, 2, 5, 7, 8, 9};

A\B = {x | xA и xB} = {8};

B\A = {x | xB и xA} = {9, 7, 5};

A = ય\A = {x | xA} = {3, 4, 5, 6, 7, 9};

B = ય\B = {x | xB} = {3, 4, 6, 8}.

Найдем AB, где   симметрическая разность.

XY = (X\Y)(Y\X) = (XY)\(XY).

AB = {1, 2, 3, 4, 5, 6, 7, 9}; AB = {5, 7, 9};

AB = (AB)\(AB) = {1, 2, 3, 4, 6}.

2) A = (10; 1], B = (5; 20), ય = R

AB = {x | xA и xB} = (5; 1];

AB = {x | xA или xB} = (10; 20);

A\B = {x | xA и xB} = (10; 5];

B\A = {x | xB и xA} = (1; 20);

A = ય\A = {x | xA} = (; 10](1; +);

B = ય\B = {x | xB} = (; 5][20; +).

Найдем AB, где   симметрическая разность.

AB = (; 10](5; +); AB = (1; 20);

AB = (AB)\(AB) = (; 10](5; 1][20; +).

Задача 2. На диаграмме Эйлера отметьте области, соответствующие данному множеству X: 1) X = (A\B)(B\A); 2) X = A \(BC\(AB)).

Решение:

1) X = (A\B)(B\A)

На диаграмме Эйлера пронумеруем области (рисунок 1).

Последовательно выполним опреации:

Множество B состоит из областей 0, 1.

Множество A\B состоит из области 3.

Множество B\A состоит из области 2.

Множество X = (A\B)(B\A) пустое (области 3 и 2 не пересекаются).

Итак, X=, следовательно, на диаграмме Эйлера не будет закрашенных областей.

2) X = A \(BC\(AB))

На диаграмме Эйлера пронумеруем области (рисунок 2):

Последовательно выполним опреации:

Множество A состоит из областей 0, 2, 3, 5.

Множество BC состоит из областей 2, 3, 4, 5, 6, 7.

Множество AB состоит из областей 4, 7.

Множество BC\(AB) состоит из областей 2, 3, 5, 6.

Множество X = A \(BC\(AB)) состоит из области 0. Закрасим на рисунке область 0 (рисунок 3).

Задача 3. Упростите теоретико-множественные выражения, данные в задаче 2.

Решение:

Можно восстановить упрощенные выражения по диаграммам, составленным в пункте 2. Но для проверки можно упростить теоретико-множественные выражения, используя свойства операций над множествами.

1) X = (A\B)(B\A)

(A\B)(B\A) = AB(BA) = ABBA = 

2) X = A \(BC\(AB))

A \(BC\(AB)) = A \(BC(AB)) = A(BC(AB)) =

= A(BC(AB)) = (ABC)(AAB) = (ABC) =

= ABC = (ABC)

Задача 4. Высказывание задано формулой F, где X, Y, Z  высказывательные символы. Удалите все возможные скобки так, чтобы получилось высказывание, равносильное исходному. Затем расставьте приоритет выполнения операций и постройте таблицу истинности данного высказывания.

F  (((X & ( Z))  (( Y) V X))  Y)

Решение:

Удалив все возможные скобки, получим F  (X &  Z   Y V X)  Y.

В зависимости от приоритета выполнения операций введем обозначения:

F₁  X &  Z ; F₂   Y V X; F₃  F₁  F₂; F  F₃  Y.

Построим таблицу истинности высказывания F:

X	Y	Z	 Y	 Z	F1	F2	F3	F
0	0	0	1	1	0	1	0	1
0	0	1	1	0	0	1	0	1
0	1	0	0	1	0	0	1	1
0	1	1	0	0	0	0	1	1
1	0	0	1	1	1	1	1	0
1	0	1	1	0	0	1	0	1
1	1	0	0	1	1	1	1	1
1	1	1	0	0	0	1	0	1

Итак, F(1,0,0)=0 и F(X,Y,Z)=1 для остальных наборов значений высказывательных символов X, Y, Z.

Задача 5. Упростите данную формулу F исчисления высказываний.

F  ( X  Y ) & ( X   Y )

Решение:

( X  Y ) & ( X   Y )  (X  Y) & (X   Y)  X  (Y &  Y)  X  0  X

Задача 6. P(x), T(x,y)  предикаты, определенные на множестве A. Найдите области истинности данных предикатов.

Пусть A = {0, 10, 3, 14, 1}; P(x) = «x делитель числа 30»; T(x,y) = = «x+y  четное натуральное число».

Решение: Обозначим I_P, I_T  области истинности предикатов P(x) и T(x,y) соответственно. Поскольку P(x)  одноместный, а T(x,y)  двуместный предикаты, то I_P  A, I_T  AA.

В область истинности одноместного предиката P(x) входят все xA, для которых P(x) принимает значение “ИСТИНА”, т.е. все x, являющиеся делителями числа 30. Итак, I_P = {10, 3, 1}.

Область истинности двуместного предиката T(x,y) состоит из всех пар (x,y), для которых T(x,y) принимает значение “ИСТИНА”. В данном случае среди всех сумм по два элемента выбираем те, которые больше 0 (натуральные числа) и делятся на 2 (четные). Итак, I_T = {(0; 10), (10; 0), (0; 14), (14; 0), (10; 10), (10; 14), (14; 10), (14; 14)}.

Задача 7. Найдите область истинности предиката P(x) = «», определенного на множестве R действительных чисел.

Решение: Так как P(x)  одноместный предикат, то I_P  R.

Чтобы найти область истинности предиката P(x), определенного на множестве действительных чисел, нужно решить соответствующее неравенство относительно x.

1) Если , то исходное неравенство равносильно системе:

Итак, x[5; 2,5).

2) Если , то исходное неравенство равносильно системе:

Решим первое неравенство системы:

;; ; .

Вернемся к системе неравенств:

Итак, x[2,5; 4].

Объединим решения, полученные в пунктах 1 и 2:

x[2,5; 4]  [5; 2,5), т.е. x[5; 4].

Задача 8. F  соответствие из A в B. Проверьте выполнимость свойств соответствия (всюду определенность, однозначность, соответствие «на», разнозначность). Выясните, является ли данное соответствие отображением.

1) A = {1, 5, 3, 7, 2}, B = {10, 2, 4}, F = {(1,10), (5,2), (2,10), (7,2), (3,2)};

2) A = B = N (множество натуральных чисел), F = {(x,y)  y  вторая цифра числа x}.

Решение:

1) Проверим свойства соответствия F = {(1,10), (5,2), (2,10), (7,2), (3,2)} из A = {1, 5, 3, 7, 2} в B = {10, 2, 4}.

Всюду определенность: Для любого xA существует хотя бы один элемент yB, такой, что (x,y)F, т.е. F  всюду определенное соответствие.

Однозначность: Для любого xA существует не более одного yB, такого, что (x,y)F, т.е. F  однозначное соответствие.

Соответствие «на»: Элемент 4B не имеет прообраза во множестве A, т.е. F не является соответствием «на».

Разнозначность: Поскольку (1,10)F и (2,10)F, то элемент 10 множества B имеет более одного прообраза во множестве A, т.е. F не является разнозначным соответствием.

Так как F  всюду определенное однозначное соответствие, то F  отображение.

2) Проверим свойства соответствия F = {(x,y)  y  вторая цифра числа x} из N в N.

Всюду определенность: Не у каждого xN есть вторая цифра (например, если x  однозначное число), т.е. не у каждого xN есть образ. Итак, F не является всюду определенным соответствием.

Однозначность: Каждое xN может иметь не более одной второй цифры, т.е. F  однозначное соответствие.

Соответствие «на»: Не у всякого натурального числа есть прообраз при соответствии F. Например, число 10 не может быть цифрой натурального числа. Итак, F не является соответствием «на».

Разнозначность: Например, 5  вторая цифра натуральных чисел 256 и 3578, т.е. (256, 5)F и (3578, 5)F. Итак, элемент 5 множества B имеет более одного прообраза во множестве A, т.е. F не является разнозначным соответствием.

Так как F не является всюду определенным соответствием, то F  не отображение.

Задача 9. F  отображение из N в N. Проверьте выполнимость свойств отображения (сюръективность, инъективность, биективность).

N  множество натуральных чисел, xN F(x)=(x3)²+1.

Решение:

Проверим свойства отображения.

Сюръективность: Не у всякого натурального числа есть прообраз при отображении F. Например, для числа 3 нет прообраза во множестве N, т.к. если (x3)²+1 = 3, т.е. (x3)² = 2, то x не может принадлежать N. Итак, F не является сюръективным отображением.

Инъективность: Поскольку (23)²+1=2 и (43)²+1=2, т.е. F(2)=2 и F(4)=2. Итак, элемент 2 множества B имеет более одного прообраза во множестве A, т.е. F не является инъективным отображением.

Так как F не сюръективное отображение, следовательно, F  не биективное отображение.

Задача 10.   бинарное отношение, определенное на множестве натуральных чисел N. Проверьте выполнимость свойств бинарного отношения (рефлексивность, симметричность, транзитивность, антирефлексивность, антисимметричность, линейность) .

Пусть : «A,BN A  B  произведение цифр числа A равно сумме цифр числа B».

Решение:

1) Рефлексивность: AN (A  A)

Рефлексивность выполнится, если произведение цифр любого натурального числа A будет равно сумме цифр числа A.

Очевидно, что   не рефлексивно, т.к., например, произведение цифр числа 12 не равно сумме его цифр (23).

2) Симметричность: A,BN (A  B  B  A)

Если из того, что произведение цифр числа A равно сумме цифр числа B, следует, что произведение цифр числа B равно сумме цифр числа A, то отношение  будет симметричным.

Отношение  не симметрично, т.к. можно подобрать контрпример. Возьмем A=23, B=33, тогда произведение цифр числа A равно 6 и равно сумме цифр числа B, но произведение цифр числа B не совпадает с суммой цифр числа A (95).

3) Транзитивность: A,B,CN (A  B & B  C  A  C)

Если из того, что произведение цифр числа A равно сумме цифр числа B и произведение цифр числа B равно сумме цифр числа C, следует, что произведение цифр числа A равно сумме цифр числа C, то отношение  будет транзитивным.

Отношение  не транзитивно, т.к. можно подобрать контрпример. Возьмем A=23, B=33, C=45. Произведение цифр числа A равно 6 и равно сумме цифр числа B, произведение цифр числа B равно 9 и равно сумме цифр числа C, но произведение цифр числа A не совпадает с суммой цифр числа C (69).

4) Антирефлексивность: AN  (A  A)

Антирефлексивность выполнится, если произведение цифр любого натурального числа A не будет равно сумме цифр этого числа.

Поскольку есть такие натуральные числа (например, A=123), у которых произведение цифр совпадает с суммой цифр, то  не является антирефлексивным.

5) Антисимметричность: A,BN (A  B & B  A  A=B)

Если из того, что произведение цифр числа A равно сумме цифр числа B и произведение цифр числа B равно сумме цифр числа A, следует, что A=B, то отношение  будет антисимметричным.

Отношение  не антисимметрично, т.к. можно подобрать контрпример. Возьмем A=123, B=321, тогда произведение цифр числа A равно 6 и равно сумме цифр числа B, произведение цифр числа B равно сумме цифр числа A, но AB.

6) Линейность: A,BN (A  B  B  A  A=B)

Отношение  линейно, если для любых натуральных A и B выполняется хотя бы одно из утверждений: произведение цифр числа A равно сумме цифр числа B; произведение цифр числа B равно сумме цифр числа A; A=B.

Отношение  не линейно, т.к. можно подобрать контрпример. Возьмем A=12, B=24, тогда произведение цифр числа A не равно сумме цифр числа B (26), произведение цифр числа B не равно сумме цифр числа A (83) и AB.

Итак, отношение  не рефлексивно, не симметрично, не транзитивно, не антирефлексивно, не антисимметрично, не линейно.